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.

Private Information Retrieval (PIR) is a two player protocol where the client, given some query x ε [N], interacts with the server, which holds a N-bit string DB, in order to privately retrieve DB[x]. In this work, we focus on the single-server client-preprocessing model, initially proposed by Corrigan-Gibbs and Kogan (EUROCRYPT 2020), where the client and server first run a joint preprocessing algorithm, after which the client can retrieve elements from DB privately in time sublinear in N. Most known constructions of single-server client-preprocessing PIR follow one of two paradigms: They feature either (1) a linear-bandwidth offline phase where the client downloads the whole database from the server, or (2) a sublinear-bandwidth offline phase where however the server has to compute a large-depth (Ωλ(N)) circuit under fully-homomorphic encryption (FHE) in order to execute the preprocessing phase.