We can create a simplified scalable consensus algorithm that attempts to provide guarantees of only data availability; that is, the basic "unit" of consensus is a data block, a small header that cryptographically points to, say, 1 MB of data, and the only purpose of this system is to provide only the guarantee that the data committed to by these block headers is readily available. This is a challenging problem to solve scalably because the usual technique for scalable validation, incentivized interactive verification with penalties, does not work well for data availability because a malicious attacker can always reveal data just before they are supposed to be penalized. However, using the mechanism described here we can combine rapid shuffling and a form of graceful degradation to solve the scalable data availability validator problem rather effectively.
We can model the protocol by assuming access to a "DHT oracle" where nodes can call
DHTget(hash) and get back the preimage if the preimage has been publis