Deep-frida: transparent data availability sampling with smaller size

Abstract Data Availability Sampling (DAS) is a pivotal paradigm for addressing scalability challenges in blockchains. However, the predominant DAS schemes rely on KZG commitments, which necessitate a trusted setup. While the recently proposed FRIDA (Crypto’24) offers a transparent, FRI-based alternative, it suffers from large commitment sizes due to its restriction to the unique decoding radius. In this work, we generalize the protocol to the list decoding radius by leveraging the DEEP (Domain Extension for Eliminating Pretenders) technique. We provide a formal proof of the opening-consistency of the DEEP-FRI, established via the notion of mutual correlated agreement , instead of the weighted correlated agreement in the original DEEP-FRI protocol. In terms of efficiency, our scheme reduces the commitment size by a factor of $$1.2 \sim 1.8\times$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1.2</mml:mn> <mml:mo>∼</mml:mo> <mml:mn>1.8</mml:mn> <mml:mo>×</mml:mo> </mml:mrow> </mml:math> while preserving the computational efficiency of both the prover and the verifier.