Quote from: Taek on October 06, 2014, 04:30:35 PM

Treechains are not particularly similar to the quorums that Sia builds, Sia's quorum's [were] built out of a paxos-like message passing system. Treechains are a bunch of merge-mined POW blockchains that follow some special rules to build a tree.

Unforturnately everything that I thought was working for quorums is still broken. The problem is that when you have hundreds or millions of quorums, an attacker with 50% strength will be able to compromise at least a handful of quorums in the 70-80% range, and the attacker can pull successful attacks on those. It'd be easy to solve that problem if you could provide a proof-of-public-data, but the only way to prove that is to have the data yourself. Otherwise you're trusting whoever says the data is public or not public, and you'd have to go with the majority, which sometimes is an attacker.

We could weaken our assumptions to 33% global corruption of storage, and then increase the quorum size, and then it's much less likely for an attacker to break 51% strength in any quorum. But then you have failure modes that might destroy everything. IE if an attacker does manage to break 51% control of a particular quorum, he'll be able to continually inflate (by lying) the amount of storage he has, and eventually take 51% control of every quorum.

The source of the problem comes from the fact that not every node knows about every transaction. With a file storage system, you have to be able to handle many, many, many transactions, or have some way to allow the system to change state without using a transaction. But if you're doing proof-of-storage, and someone edits a file, the rest of the network has to know that the file has been edited so that they can change how they read a storage proof. Therefore, I don't think it's possible to edit a file without having a transaction. If most of the files are computer backups or large static files (videos, music, etc.), it might be okay but the real goal is to support files like web pages. Ideally you'd never need an HDD again (an SDD + large amount of RAM would be sufficient).

So I guess we have two options then:

1. Everyone sees every transaction
2. Not everyone sees every transaction

In the case of 1, the amount of transactions would need to be limited, and you'd have fees and they'd get pretty large. Something like this could potentially be done right on top of Bitcoin. This would probably only be useful for large _and_ important files. I don't really see Netflix using something like this, but it could be a worthwhile alternative to bittorrent (which suffers from the same problem of having files that are very hard to edit).

In the case of 2, you have to have some way of knowing that everything is okay, even though you can't see all of the transactions. The general strategy is to have a large but finite number of people verifying each piece of information, and you randomly assign who gets to verify what. You have some metric for protecting against sybil attacks during your assignment. (storage in our case). The problem is that if you're relying on something like a blockchain, you need to assume that each subset of verifiers is able to stay honest.

Consider the situation where 51% are dishonest. They are the majority, and so they can tell the network that things look like X. The network doesn't know, so it just has to accept X as true. The 49% honest people complain, saying that things actually look like Y. The dishonest group can be completely dishonest (change balances and such), because they don't ever tell anyone what Y is (Y is just a hash to keep things scalable). They just keep it to themselves and successfully corrupt the network.

So say you give the honest hosts some tool to claim that Y doesn't exist and is a made up hash. Then, in honest quorums you can have a dishonest set of hosts claim that the honest hosts are releasing data which doesn't exist. The network now needs to verify somehow that the honest hosts really have made the data public and aren't actually dishonest hosts in disguise. The only way to do this is for the network to download all of the data and verify for itself that the data exists. But now dishonest hosts will always claim that they can't see the data, and the rest of the network is always forced to download the data to verify that it's publicly available. So you end up with a situation that's not any different from a single blockchain.

Moon math aside, there doesn't seem to be any way around this. That's where Sia is stuck right now. The quorum's in the currently available whitepaper suffer from a related problem. Someone who manages to take control of >50% of a large number of quorums can start kicking out honest hosts, which will result in fines for the honest hosts and also result in a higher percentage of the hosts across the network as a whole being dishonest. Sia becomes pretty vulnerable once someone gets around 33% of the network.

=======

So let's say that we accept our limitations of 33%. What happens when someone breaks 33%? Unfortunately, they get a lot of power. In Bitcoin, when someone breaks 50% they control the blockchain for a while, they can attempt double spends and they can block transactions, but they can't spend other people's money. But in a network where the majority of hosts don't see all of the data, someone who manages to break a portion of the data CAN spend money from other wallets. They just lie about the state of the network, because they don't have to provide signatures of accuracy.

Even if we were able to prove that the dishonest hosts hadn't dishonestly spent a wallet's money (eg without a signature) (this proof could be done using snarks/scip), the dishonest hosts could still refuse to reveal what data had made it into the blockchain. The biggest issue here is that honest transactions could make it into the blockchain, and while the snarks would verify that everything was legal, honest hosts might not be able to know if their transactions had gone through. A dishonest party could prove that they had the network in a legal state without ever revealing what that state is. So the rest of the world just sees this giant black void that they can't reason about or make transactions through. The wallets within it might as well not have any coins.

Undecided

=======

So, what do we do? I'm going to keep looking at this but it doesn't seem like highly scalable storage is going to work in a decentralized way on today's technologies. I don't think it's reasonable to assume that nobody will ever get to 33% control (even without pools) because Bitcoin has a single factory that's got something like 25% of the mining power. Sia might fall to the same thing. It would be highly desirable to have some sort of response to the failure mode, such that if the honest set of people once again got above 67%, the network could quickly restore to a functioning, fully informed state.

Another big issue with proof-of-storage-for-consensus is that it's not progress free. You have to announce that you have the storage, you have to download files (and people have to be willing to upload the files to you - another issue we aren't certain how to solve). A malicous party controlling the network can just refuse to accept you as a contributor, and it won't matter how much storage you have because you will be ignored. This doesn't happen on Bitcoin because any random person can submit a proof of work. In Sia, this isn't currently possible.

=======

Dark days for Sia =/. But filecoin is also broken, permacoin is not efficient, maidsafe is opaque and very difficult to audit, and storj is underspecified. Cryptography is very hard, something I didn't properly appreciate until the past month or two. But Sia is not dead yet, we're just back to square 1 for the time being. The money hasn't run out yet and we won't give up until it does. Our total expenses since doing the crowd sale have been about 1/2 of what we raised. (through the crowd sale. We also have venture funding although that's in a completely different pool of money. Our responsibilities following the crowd sale is to make Sia, our responsibilities following venture funding is to make Nebulous Inc. a succesful corporation).

In the worst case, I think we will be able to create a less powerful system for peer to peer storage. Instead of selling storage to a broader network, you'd sell storage to individual peers. The peers would need to be responsible for picking reliable and honest hosts, which they could achieve by using reputation, randomness, and redundancy.

Huh

sorry guys I hope the next major update has more positive news. As always, happy to walk you through anything and explain exactly what's broken. Also happy to highlight questions you have about other systems, though it's very time consuming to take a close look.

Just a reminder