UCLA

In blockchain systems, light nodes are vulnerable to data availability (DA) attacks, in which a malicious block producer withholds block data from the network. To protect against DA attacks, block data is encoded with an erasure code, and each light node performs data availability sampling (DAS), in which a node randomly samples a small set of coded symbols to test whether data is available to the network. Two-dimensional Reed-Solomon (2D-RS) codes are a leading choice for use in DAS systems.Standard DAS analysis treats the erasure code and sampling strategy separately. The undecodable erasure patterns of a 2D-RS code have structured geometry that can be exploited using joint code-sampler design. We measure each sampler design by a light node’s probability of failure to detect a DA attack. Holding the code fixed, we design a biregular sampler which spreads sample queries evenly across rows and columns. In the regime where light nodes take few samples, we prove that the biregular sampler minimizes probability of failure against minimum-distance erasure patterns. We then derive upper bounds for the worst-case probability of failure over all undecodable erasure patterns. We then study our samplers asymptotically, where we characterize the exponential decay rate of probability of failure and identify an explicit code parameter regime in which minimum-distance erasure patterns are provably worst-case. Holding the sampler fixed, we design a sampler-aware 2D-RS subcode whose added parity checks improve worst-case probability of failure behavior for our sampler. Our joint sampler-subcode design shows that worst-case probability of failure can be improved by targeting a code’s structural properties beyond the minimum distance.