Is the requirement for signature of more than 2/3 of validators, weighted by deposit, a solution for the data availability problem?

Question

The data availability problem is known to be one of the main problems in blockchain systems. So in case of a proof of stake scheme which requires a block to collect signatures of at least 2/3 of validators, weighted by deposit, does this problem exist anymore?

Answer 1

Yes, because a general proof of stake scheme with your only stated requirement being to collect signatures of at least 2/3 of validators, weighted by deposit (my edit, otherwise you could have 4,000 out of 6,000 validators with a minimum security deposit that is poorly designed to be too small, have more than 2/3 of the weighted deposit, and act faultily, with a higher expected return than the expected loss of losing the minimum deposit, and thus harm the blockchain) does not guarantee data availability, because more than a third of validators are not guaranteed to not be faulty and a generic proof-of-stake consensus protocol doesn't guarantee Byzantine fault tolerance. To express another way, it is not secure in a bribing attacker or coordinated majority model where more than 67% of validators are colluding.

In addition to using erasure codes, notaries can attempt to download (to check availability) and potentially also verify (to check validity, if acting as an executor as well) collations or blocks. If a notary cannot download a collation, they can vote 0 for it (0 is disapproval, 1 is approval). These notaries can be randomly shuffled, via a publicly verifiable randomness source such as RANDAO or BLS aggregate signatures. A committee of a random subset of notaries can then also perform a BLS aggregate signature on these votes. For very large transactions that exceed the gas limit, the transaction can be stored and verified off-chain, e.g. with IPFS, Truebit, etc.

See also snippets from CTRL+F "availab" from https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQs and https://github.com/ethereum/wiki/wiki/Sharding-FAQs.

• CAP theorem - "in the cases that a network partition takes place, you have to choose either consistency or availability, you cannot have both". The intuitive argument is simple: if the network splits in half, and in one half I send a transaction "send my 10 coins to A" and in the other I send a transaction "send my 10 coins to B", then either the system is unavailable, as one or both transactions will not be processed, or it becomes inconsistent, as one half of the network will see the first transaction completed and the other half will see the second transaction completed. Note that the CAP theorem has nothing to do with scalability; it applies to sharded and non-sharded systems equally. See also https://github.com/ethereum/wiki/wiki/Sharding-FAQs#but-doesnt-the-cap-theorem-mean-that-fully-secure-distributed-systems-are-impossible-and-so-sharding-is-futile. — https://github.com/ethereum/wiki/wiki/Sharding-FAQs#but-doesnt-the-cap-theorem-mean-that-fully-secure-distributed-systems-are-impossible-and-so-sharding-is-futile

Can one economically penalize censorship in proof of stake?

Unlike reverts, censorship is much more difficult to prove. The blockchain itself cannot directly tell the difference between "user A tried to send transaction X but it was unfairly censored", "user A tried to send transaction X but it never got in because the transaction fee was insufficient" and "user A never tried to send transaction X at all". See also a note on data availability and erasure codes. However, there are a number of techniques that can be used to mitigate censorship issues.

The first is censorship resistance by halting problem. In the weaker version of this scheme, the protocol is designed to be Turing-complete in such a way that a validator cannot even tell whether or not a given transaction will lead to an undesired action without spending a large amount of processing power executing the transaction, and thus opening itself up to denial-of-service attacks. This is what prevented the DAO soft fork.

In the stronger version of the scheme, transactions can trigger guaranteed effects at some point in the near to mid-term future. Hence, a user could send multiple transactions which interact with each other and with predicted third-party information to lead to some future event, but the validators cannot possibly tell that this is going to happen until the transactions are already included (and economically finalized) and it is far too late to stop them; even if all future transactions are excluded, the event that validators wish to halt would still take place. Note that in this scheme, validators could still try to prevent all transactions, or perhaps all transactions that do not come packaged with some formal proof that they do not lead to anything undesired, but this would entail forbidding a very wide class of transactions to the point of essentially breaking the entire system, which would cause validators to lose value as the price of the cryptocurrency in which their deposits are denominated would drop.

The second, described by Adam Back here, is to require transactions to be timelock-encrypted. Hence, validators will include the transactions without knowing the contents, and only later could the contents automatically be revealed, by which point once again it would be far too late to un-include the transactions. If validators were sufficiently malicious, however, they could simply only agree to include transactions that come with a cryptographic proof (e.g. ZK-SNARK) of what the decrypted version is; this would force users to download new client software, but an adversary could conveniently provide such client software for easy download, and in a game-theoretic model users would have the incentive to play along.

Perhaps the best that can be said in a proof-of-stake context is that users could also install a software update that includes a hard fork that deletes the malicious validators and this is not that much harder than installing a software update to make their transactions "censorship-friendly". Hence, all in all this scheme is also moderately effective, though it does come at the cost of slowing interaction with the blockchain down (note that the scheme must be mandatory to be effective; otherwise malicious validators could much more easily simply filter encrypted transactions without filtering the quicker unencrypted transactions).

A third alternative is to include censorship detection in the fork choice rule. The idea is simple. Nodes watch the network for transactions, and if they see a transaction that has a sufficiently high fee for a sufficient amount of time, then they assign a lower "score" to blockchains that do not include this transaction. If all nodes follow this strategy, then eventually a minority chain would automatically coalesce that includes the transactions, and all honest online nodes would follow it. The main weakness of such a scheme is that offline nodes would still follow the majority branch, and if the censorship is temporary and they log back on after the censorship ends then they would end up on a different branch from online nodes. Hence, this scheme should be viewed more as a tool to facilitate automated emergency coordination on a hard fork than something that would play an active role in day-to-day fork choice. Proof of work algorithms and chain-based proof of stake algorithms choose availability over consistency, but BFT-style consensus algorithms lean more toward consistency; Tendermint chooses consistency explicitly, and Casper uses a hybrid model that prefers availability but provides as much consistency as possible and makes both on-chain applications and clients aware of how strong the consistency guarantee is at any given time.

See also https://github.com/ethereum/wiki/wiki/Sharding-FAQs#what-might-a-basic-design-of-a-sharded-blockchain-look-like.

What might a basic design of a sharded blockchain look like?

A simple approach is as follows. For simplicity, this design keeps track of data blobs only; it does not attempt to process a state transition function.

There exist nodes called proposers that accept blobs on shard k (depending on the protocol, proposers either choose which k or are randomly assigned some k) and create collations, thus they also act as a collator, and so agents that act as both a proposer and collator may be referred to as prolators. A collation has a collation header, a short message of the form "This is a collation of blobs on shard k, the parent collation is 0x7f1e74 and the Merkle root of the blobs is 0x3f98ea". Collations of each shard form a chain just like blocks in a traditional blockchain.

There also exist notaries that download and verify collations in a shard that they are randomly assigned and where they are shuffled to a new shard every period via a random beacon chain (using some Verifiable Random Function such as a blockhash produced by a BLS aggregate signature or RANDAO, although the latter has been tested to be prone to manipulation), and vote on the availability of the data in a collation (assuming no EVM, with an EVM they may also act as an executor and vote on the validity of data).

A committee can then also check these votes from notaries and decide whether to include a collation header in the main chain, thus establishing a cross-link to the collation in the shard. Other parties may challenge the committee, notaries, proposers, validators (with Casper Proof of Stake), etc., e.g. with an interactive verification game, or by verifying a proof of validity.

A "main chain" processed by everyone still exists, but this main chain's role is limited to storing collation headers for all shards. The "canonical chain" of shard k is the longest chain of valid collations on shard k all of whose headers are inside the canonical main chain.

Note that there are now several "levels" of nodes that can exist in such a system:

• Super-full node - fully downloads every collation of every shard, as well as the main chain, fully verifying everything.
• Top-level node - processes all main chain blocks, giving them "light client" access to all shards.
• Single-shard node - acts as a top-level node, but also fully downloads and verifies every collation on some specific shard that it cares more about.
• Light node - downloads and verifies the block headers of main chain blocks only; does not process any collation headers or transactions unless it needs to read some specific entry in the state of some specific shard, in which case it downloads the Merkle branch to the most recent collation header for that shard and from there downloads the Merkle proof of the desired value in the state.

Answer 2

The short answer is Yes, these problems persist but at a small but tolerable scale.

The solution to this would be a perfectly Byzantine fault tolerant system(BFT).