Information Dispersal with Provable Retrievability for Rollups
Information Dispersal with Provable Retrievability for Rollups
The ability to verifiably retrieve transaction or state data stored off-chain is crucial to blockchain scaling techniques such as rollups or sharding. We formalize the problem and design a storage- and communication-efficient protocol using linear erasure-correcting codes and homomorphic vector commitments. Motivated by application requirements for rollups, our solution Semi-AVID-PR departs from earlier Verifiable Information Dispersal schemes in that we do not require comprehensive termination properties or retrievability from any but only from some known sufficiently large set of storage nodes. Compared to Data Availability Oracles, under no circumstance do we fall back to returning empty blocks. Distributing a file of 22 MB among 225 storage nodes (up to 75 of which may be adversarial) requires in total ~65 MB of communication and storage, ~9 seconds of cryptographic computation, and ~9 seconds of Reed-Solomon encoding on a single-threaded consumer-grade laptop computer. Our solution requires no modification to on-chain contracts of Validium rollups such as StarkWare's StarkEx. Additionally, it provides privacy of the dispersed data against honest-but-curious storage nodes. Finally, we discuss an application of our Semi-AVID-PR scheme to data availability verification schemes based on random sampling.
Note: a recording of this talk is not available per the speaker's request.
About the speaker
PhD student, Stanford University
Joachim is a 4th year PhD student at Stanford working with David Tse on Internet-scale open-participation consensus (in more hype terms: the technical foundations of blockchains). His current research focus is provable consensus security for next-generation Ethereum, and provable security and performance of proof-of-stake consensus under bandwidth constraints and network-level attacks. While a Masters student at Technical University of Munich and a visiting student researcher at MIT, EPFL, and KAUST, he published in information and coding theory. He has been supported by Protocol Labs PhD Fellowship, Ethereum Foundation, Stanford Graduate Fellowship, and German Academic Scholarship Foundation.
Monash University values the privacy of every individual's personal information and is committed to the protection of that information from unauthorised use and disclosure except where permitted by law. For information about the handling of your personal information please see Data Protection and Privacy Procedure and the relevant Data Protection and Privacy Collection Statement that applies to you depending on the nature of your interaction with us.
If you have any questions about how Monash University is collecting and handling your personal information, please contact our Data Protection and Privacy Office at dataprotectionofficer@monash.edu.