Welcome to the resource topic for 2025/1851
Title:
Locally Recoverable Data Availability Sampling
Authors: Seunghyun Cho, Eunyoung Seo, Young-Sik Kim
Abstract:We propose Locally Recoverable Data Availability Sampling (LR-DAS), which upgrades binary, threshold-based availability to graded verification by leveraging optimal locally recoverable codes (e.g., Tamo-Barg). Local groups of size r+\alpha serve as atomic certification units: once r verified openings fix a degree-<r local polynomial, the entire group is certified and accumulates monotonically toward global availability. We formalize a locality-aware commitment with a single algebraic local-global link that binds every accepted local proof to a unique global codeword, preventing cross-group splicing. Our verifier admits a two-tier IOP view (local RS-membership, global TB-proximity, one DEEP-style linking query). We instantiate this with (i) a two-layer KZG design and (ii) a transparent FRI/IOPP stack. Both support batched multi-point openings and cross-block random-weight aggregation, yielding \mathcal{O}(1) verifier work per certified batch with \mathcal{O}(r+\alpha) field payload per block. Security is captured by graded soundness against missing-fraction and missing-group adversaries with explicit overshoot bounds. A lightweight proof-of-custody layer—one unpredictable global opening at publish time plus periodic batched local checks—composes seamlessly to enforce possession without altering the core pipeline. Empirically and analytically, LR-DAS certifies availability with fewer samples than required for global recovery under the same encoding, providing a practical univariate alternative to multivariate repair-based DAS while retaining succinct proofs and a simple prover/verifier pipeline. Design levers (r,\alpha) allow tuning responsiveness versus distance, and the transparent instantiation offers a post-quantum-ready option.
ePrint: https://eprint.iacr.org/2025/1851
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .