Permissionless Verifiable Information Dispersal (Data Availability for Bitcoin Rollups)

Rollups are special applications on distributed state machines (aka blockchains) for which the underlying state machine only logs, but does not execute, transactions. Rollups scale throughput by using auxiliary machines that have higher throughput and lower cost of executing transactions than the underlying blockchain. State updates are periodically posted to the underlying blockchain and either verified directly through succinct cryptographic proofs (zk rollups) or can be challenged for a defined period of time in a verifiable way by third parties (optimistic rollups). However, once computation is reduced, communication quickly becomes the new bottleneck. The critical service that the underlying blockchain provides, in addition to verification, is data availability: that necessary data can always be recovered upon request. However, directly broadcasting data requires communication per participant that is linear in the data size. Verifiable information dispersal (VID) systems achieve sublinear blowup in the Ethereum's security and same participation model, where all nodes have a strong public-key identity. However, it is not known how to do so in the permissionless model (the Bitcoin model), where participants are unauthenticated and participation is dynamic. We construct a VID system that is secure under the same model as Bitcoin, with one minimal additional requirement on the existence of reliable participants. Our system uses a state machine replication (SMR) protocol (e.g., Bitcoin) as a black box, and is therefore backward compatible. We implemented the system on top of Bitcoin core with the Regression Test Network (regtest), and our analysis shows that it can reduce communication costs and latency up to more than $1, 000\times$ and $10\times$, respectively, for certain parameter choices.