  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.
