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 ≈ 70MB of communication and storage, and ≈ 41 s of single-thread runtime (< 3 s 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. We discuss an application of our Semi-AVID-PR scheme to data availability verification schemes based on random sampling.

We investigate the distance properties of linear locally recoverable codes (LRC codes) with all-symbol locality and availability. New upper and lower bounds on the minimum distance of such codes are derived. The upper bound is based on the shortening method and generalized Hamming weights that are fundamental parameters of any linear codes with many useful applications. This bound improves existing upper bounds. To reduce the gap in between upper and lower bounds, we do not restrict the alphabet size and propose explicit constructions of codes with locality and availability via rank-metric codes. The first construction relies on expander graphs and is better in low rate region. The second construction utilizes the LRC codes developed by Wang et al. as inner codes and is better in high rate region. We also suggest one possible generalization of LRC codes in which the recovering sets can intersect in a small number of coordinates. This feature allows us to increase the achievable code rate and still meet load balancing requirements. We derive upper and lower bounds on the parameters of such codes and present explicit constructions of codes with such a property.

We continue our investigation of one possible generalization of locally recoverable codes (LRC) with all-symbol locality and availability when recovering sets can intersect in a small number of coordinates. This feature allows us to increase the achievable code rate and still meet load balancing requirements. In this paper we derive upper and lower bounds on the minimum distance of such codes. The upper bound is based on generalized Hamming weights (GHWs) that are fundamental parameters of any linear codes with many useful applications. In order to derive a lower bound we propose an explicit construction of (r, t, x), -LRC via rank-metric codes and previously developed high rate (r, t, x) -LRC codes.