Paper 2025/1851

Locally Recoverable Data Availability Sampling

Abstract

Data Availability Sampling (DAS) enables light clients to probabilistically verify that a large published object remains retrievable by sampling a small number of coded symbols and checking consistency. Most existing DAS designs are predicated on MDS-style global recovery thresholds and therefore yield an essentially binary availability signal: either sufficient evidence accumulates to enable global reconstruction, or it does not. In this work we introduce Locally Recoverable Data Availability Sampling (LR-DAS), which leverages locally recoverable codes with disjoint recovery groups to provide graded availability evidence. A verifier sequentially certifies groups: once it has verified $r$ distinct openings in a group, it can reconstruct the entire group locally and monotonically increase a certified availability fraction. The central cryptographic challenge is preventing splicing attacks, where an adversary mixes locally consistent views that do not arise from a single global codeword. We define locality-aware erasure-code commitments that formalize position binding, local binding, and an explicit local-global consistency requirement, and we give a construction that enforces local-global consistency using a single out-of-domain algebraic linking check per certified group. We prove graded soundness via overshoot bounds that decompose into a sampling term and a negligible cryptographic failure term, covering both missing-groups and missing-fraction withholding patterns. We provide two concrete instantiations: a succinct pairing-based realization and a transparent realization based on low-degree/proximity testing, and we evaluate the resulting trade-offs against representative DAS and repair-oriented approaches.