Paper 2023/1079

Foundations of Data Availability Sampling

Mathias Hall-Andersen, Aarhus University
Mark Simkin, Ethereum Foundation
Benedikt Wagner, CISPA Helmholtz Center for Information Security, Saarland University

Towards building more scalable blockchains, an approach known as data availability sampling (DAS) has emerged over the past few years. Even large blockchains like Ethereum are planning to eventually deploy DAS to improve their scalability. In a nutshell, DAS allows the participants of a network to ensure the full availability of some data without any one participant downloading it entirely. Despite the significant practical interest that DAS has received, there are currently no formal definitions for this primitive, no security notions, and no security proofs for any candidate constructions. For a cryptographic primitive that may end up being widely deployed in large real-world systems, this is a rather unsatisfactory state of affairs. In this work, we initiate a cryptographic study of data availability sampling. To this end, we define data availability sampling precisely as a clean cryptographic primitive. Then, we show how data availability sampling relates to erasure codes. We do so by defining a new type of commitment schemes which naturally generalizes vector commitments and polynomial commitments. Using our framework, we analyze existing constructions and prove them secure. In addition, we give new constructions which are based on weaker assumptions, computationally more efficient, and do not rely on a trusted setup, at the cost of slightly larger communication complexity. Finally, we evaluate the trade-offs of the different constructions.

Available format(s)
Publication info
Data Availability SamplingCommitmentsErasure CodesCoupon Collector
Contact author(s)
ma @ cs au dk
mark simkin @ ethereum or
benedikt wagner @ cispa de
2023-07-16: approved
2023-07-11: received
See all versions
Short URL
Creative Commons Attribution


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