Paper 2021/1544

Information Dispersal with Provable Retrievability for Rollups

Kamilla Nazirkhanova, Joachim Neu, and David Tse

Abstract

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. Compared to Data Availability Oracles, under no circumstance do we fall back to returning empty blocks. Distributing a file of 22 MB among 256 storage nodes, up to 85 of which may be adversarial, requires in total ~70 MB of communication and storage, and ~41 seconds of single-thread runtime (<3 seconds on 16 threads) on an AMD Opteron 6378 processor when using the BLS12-381 curve. 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
blockchainconsensusrollup
Contact author(s)
nazirk @ stanford edu
jneu @ stanford edu
dntse @ stanford edu
History
2022-05-05: last of 2 revisions
2021-11-29: received
See all versions
Short URL
https://ia.cr/2021/1544
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1544,
      author = {Kamilla Nazirkhanova and Joachim Neu and David Tse},
      title = {Information Dispersal with Provable Retrievability for Rollups},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1544},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1544}},
      url = {https://eprint.iacr.org/2021/1544}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.