Paper 2025/1851

Locally Recoverable Data Availability Sampling with Derived Group Commitments

Abstract

Data availability sampling (DAS) enables a verifier to assess whether an encoded object is available for reconstruction without downloading it in full. Nodes that accumulate partial data additionally require disjoint recovery groups that they can certify and serve independently. We present LR-DAS, which commits to the source-group restrictions of a Tamo-Barg codeword, enabling every verifier to derive each group commitment as a public linear combination of the published commitments. While leveraging a linear derivation analogous to two-dimensional KZG designs, LR-DAS evaluates each derived group on its dedicated coset of a multiplicative subgroup, requiring only one diagonal scaling per group and achieving the optimal Singleton-type minimum distance. In the reference configuration, the minimum distance is $3.91$ times that of the source-compressed product code with the same commitment size, reference string, and local serving interface, and the number of uniform samples required for a light client to detect any fixed unrecoverable withholding pattern with probability $1-2^{-128}$ decreases from $991$ to $218$. The reference string has the degree of the local dimension rather than that of the global polynomial, no Fiat-Shamir transform is used, and a node holding authenticated values at any $r$ distinct positions of a group can produce valid openings for that group without auxiliary data. Against adaptive adversaries, we prove position binding, code binding, and canonicality in the algebraic group model under a discrete-logarithm assumption with auxiliary inputs, and we show by an explicit attack that degree enforcement is necessary.