Paper 2024/248

FRIDA: Data Availability Sampling from FRI

Mathias Hall-Andersen, ZkSecurity
Mark Simkin, Ethereum Foundation
Benedikt Wagner, Ethereum Foundation

As blockchains like Ethereum continue to grow, clients with limited resources can no longer store the entire chain. Light nodes that want to use the blockchain, without verifying that it is in a good state overall, can just download the block headers without the corresponding block contents. As those light nodes may eventually need some of the block contents, they would like to ensure that they are in principle available. Data availability sampling, introduced by Bassam et al., is a process that allows light nodes to check the availability of data without download it. In a recent effort, Hall-Andersen, Simkin, and Wagner have introduced formal definitions and analyzed several constructions. While their work thoroughly lays the formal foundations for data availability sampling, the constructions are either prohibitively expensive, use a trusted setup, or have a download complexity for light clients scales with a square root of the data size. In this work, we make a significant step forward by proposing an efficient data availability sampling scheme without a trusted setup and only polylogarithmic overhead. To this end, we find a novel connection with interactive oracle proofs of proximity (IOPPs). Specifically, we prove that any IOPP meeting an additional consistency criterion can be turned into an erasure code commitment, and then, leveraging a compiler due to Hall-Andersen, Simkin, and Wagner, into a data availability sampling scheme. This new connection enables data availability to benefit from future results on IOPPs. We then show that the widely used FRI IOPP satisfies our consistency criterion and demonstrate that the resulting data availability sampling scheme outperforms the state-of-the-art asymptotically and concretely in multiple parameters.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2024
Data Availability SamplingProofs of ProximityFRI
Contact author(s)
mathias @ zksecurity xyz
mark simkin @ ethereum org
benedikt wagner @ ethereum org
2024-06-06: revised
2024-02-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mathias Hall-Andersen and Mark Simkin and Benedikt Wagner},
      title = {{FRIDA}: Data Availability Sampling from {FRI}},
      howpublished = {Cryptology ePrint Archive, Paper 2024/248},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.