{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:20:48Z","timestamp":1775067648401,"version":"3.50.1"},"reference-count":40,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2024,10,9]],"date-time":"2024-10-09T00:00:00Z","timestamp":1728432000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,12,3]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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. <\/jats:p>","DOI":"10.62056\/a09qudhdj","type":"journal-article","created":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T17:00:52Z","timestamp":1736787652000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":6,"title":["Foundations of Data Availability Sampling"],"prefix":"10.62056","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0195-6659","authenticated-orcid":false,"given":"Mathias","family":"Hall-Andersen","sequence":"first","affiliation":[{"name":"ZkSecurity","place":["Denmark"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7325-5261","authenticated-orcid":false,"given":"Mark","family":"Simkin","sequence":"additional","affiliation":[{"name":"Independent Researcher","place":["Denmark"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4620-7264","authenticated-orcid":false,"given":"Benedikt","family":"Wagner","sequence":"additional","affiliation":[{"name":"Ethereum Foundation","place":["Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2025,1,13]]},"reference":[{"key":"ref1:FC:BasSonBut21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-662-64331-0_15","article-title":"Fraud and Data Availability Proofs: Detecting Invalid Blocks\n  in Light Clients","volume":"12675","author":"Mustafa Al-Bassam","year":"2021"},{"key":"ref2:FC:YSLAKV20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-030-51280-4_8","article-title":"Coded Merkle Tree: Solving Data Availability Attacks in\n  Blockchains","volume":"12059","author":"Mingchao Yu","year":"2020"},{"key":"ref3:FC:SXKV21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-662-64331-0_16","article-title":"ACeD: Scalable Data Availability Oracle","volume":"12675","author":"Peiyao Sheng","year":"2021"},{"key":"ref4:AFT:NazNeuTse22","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1145\/3558535.3559778","article-title":"Information Dispersal with Provable Retrievability for\n  Rollups","author":"Kamilla Nazirkhanova","year":"2022"},{"key":"ref5:CCS:JueKal07","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1145\/1315245.1315317","article-title":"Pors: proofs of retrievability for large files","author":"Ari Juels","year":"2007"},{"key":"ref6:CCS:ABCHKP07","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1145\/1315245.1315318","article-title":"Provable data possession at untrusted stores","author":"Giuseppe Ateniese","year":"2007"},{"key":"ref7:AC:ShaWat08","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-540-89255-7_7","article-title":"Compact Proofs of Retrievability","volume":"5350","author":"Hovav Shacham","year":"2008"},{"key":"ref8:TCC:DodVadWic09","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-00457-5_8","article-title":"Proofs of Retrievability via Hardness Amplification","volume":"5444","author":"Yevgeniy Dodis","year":"2009"},{"key":"ref9:EC:CasKueWic13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-642-38348-9_17","article-title":"Dynamic Proofs of Retrievability via Oblivious RAM","volume":"7881","author":"David Cash","year":"2013"},{"key":"ref10:CCS:ShiStePap13","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1145\/2508859.2516669","article-title":"Practical dynamic proofs of retrievability","author":"Elaine Shi","year":"2013"},{"key":"ref11:DBLP:journals\/jacm\/Rabin89","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1145\/62044.62050","article-title":"Efficient dispersal of information for security, load\n  balancing, and fault tolerance","volume":"36","author":"Michael O. Rabin","year":"1989","journal-title":"J. ACM"},{"key":"ref12:DBLP:conf\/wdag\/CachinT05a","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/11561927_42","article-title":"Asynchronous Verifiable Information Dispersal","volume":"3724","author":"Christian Cachin","year":"2005"},{"key":"ref13:robust-pcpps","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1137\/S0097539705446810","article-title":"Robust PCPs of Proximity, Shorter PCPs, and Applications to\n  Coding","volume":"36","author":"Eli Ben\u2010Sasson","year":"2006","journal-title":"SIAM Journal on Computing"},{"key":"ref14:ICALP:BCGRS17","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.40","article-title":"Interactive Oracle Proofs with Constant Rate and Query\n  Complexity","volume":"80","author":"Eli Ben-Sasson","year":"2017"},{"key":"ref15:ITCS:BGKS20","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.5","article-title":"DEEP-FRI: Sampling Outside the Box Improves Soundness","volume":"151","author":"Eli Ben-Sasson","year":"2020"},{"key":"ref16:EC:CHLMR05","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/11426639_25","article-title":"Mercurial Commitments with Applications to Zero-Knowledge\n  Sets","volume":"3494","author":"Melissa Chase","year":"2005"},{"key":"ref17:EC:CatFioMes08","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/978-3-540-78967-3_25","article-title":"Zero-Knowledge Sets with Short Proofs","volume":"4965","author":"Dario Catalano","year":"2008"},{"key":"ref18:TCC:LibYun10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-642-11799-2_30","article-title":"Concise Mercurial Vector Commitments and Independent\n  Zero-Knowledge Sets with Short Proofs","volume":"5978","author":"Beno\u00eet Libert","year":"2010"},{"key":"ref19:AC:KatZavGol10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-17373-8_11","article-title":"Constant-Size Commitments to Polynomials and Their\n  Applications","volume":"6477","author":"Aniket Kate","year":"2010"},{"key":"ref20:EPRINT:BDFG20","volume-title":"Efficient polynomial commitment schemes for multiple points\n  and polynomials","author":"Dan Boneh","year":"2020"},{"key":"ref21:EC:CHMMVW20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1007\/978-3-030-45721-1_26","article-title":"Marlin: Preprocessing zkSNARKs with Universal and\n  Updatable SRS","volume":"12105","author":"Alessandro Chiesa","year":"2020"},{"key":"ref22:ICALP:LibRamYun16","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2016.30","article-title":"Functional Commitment Schemes: From Polynomial Commitments\n  to Pairing-Based Accumulators from Simple Assumptions","volume":"55","author":"Beno\u00eet Libert","year":"2016"},{"key":"ref23:EPRINT:ADVZ21","volume-title":"Succinct Erasure Coding Proof Systems","author":"Nicolas Alhaddad","year":"2021"},{"key":"ref24:C:HalSimWag24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-031-68391-6_9","article-title":"FRIDA: Data Availability Sampling from FRI","volume":"14925","author":"Mathias Hall-Andersen","year":"2024"},{"key":"ref25:ICALP:BBHR18","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.14","article-title":"Fast Reed-Solomon Interactive Oracle Proofs of Proximity","volume":"107","author":"Eli Ben-Sasson","year":"2018"},{"key":"ref26:STOC:BluFelMic88","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/62212.62222","article-title":"Non-Interactive Zero-Knowledge and Its Applications\n  (Extended Abstract)","author":"Manuel Blum","year":"1988"},{"key":"ref27:STOC:Kilian92","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/129712.129782","article-title":"A Note on Efficient Zero-Knowledge Proofs and Arguments\n  (Extended Abstract)","author":"Joe Kilian","year":"1992"},{"key":"ref28:EC:Groth16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-662-49896-5_11","article-title":"On the Size of Pairing-Based Non-interactive Arguments","volume":"9666","author":"Jens Groth","year":"2016"},{"key":"ref29:C:Pedersen91","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/3-540-46766-1_9","article-title":"Non-Interactive and Information-Theoretic Secure Verifiable\n  Secret Sharing","volume":"576","author":"Torben P. Pedersen","year":"1992"},{"key":"ref30:C:Merkle87","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/3-540-48184-2_32","article-title":"A Digital Signature Based on a Conventional Encryption\n  Function","volume":"293","author":"Ralph C. Merkle","year":"1988"},{"key":"ref31:FOCS:Feldman87","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1109\/SFCS.1987.4","article-title":"A Practical Scheme for Non-interactive Verifiable Secret\n  Sharing","author":"Paul Feldman","year":"1987"},{"key":"ref32:CCS:AHIV17","doi-asserted-by":"publisher","first-page":"2087","DOI":"10.1145\/3133956.3134104","article-title":"Ligero: Lightweight Sublinear Arguments Without a Trusted\n  Setup","author":"Scott Ames","year":"2017"},{"key":"ref33:C:CDDDN16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-662-53015-3_7","article-title":"Rate-1, Linear Time and Additively Homomorphic UC\n  Commitments","volume":"9816","author":"Ignacio Cascudo","year":"2016"},{"key":"ref34:PKC:CatFio13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-36362-7_5","article-title":"Vector Commitments and Their Applications","volume":"7778","author":"Dario Catalano","year":"2013"},{"key":"ref35:C:FucKilLos18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-319-96881-0_2","article-title":"The Algebraic Group Model and its Applications","volume":"10992","author":"Georg Fuchsbauer","year":"2018"},{"key":"ref36:STOC:GenWic11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/1993636.1993651","article-title":"Separating succinct non-interactive arguments from all\n  falsifiable assumptions","author":"Craig Gentry","year":"2011"},{"key":"ref37:AF:CGKS23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-031-37679-5_20","article-title":"Impossibilities in Succinct Arguments: Black-Box Extraction\n  and More","volume":"14064","author":"Matteo Campanelli","year":"2023"},{"key":"ref38:ethereumDAShackmd","volume-title":"Data availability encoding","author":"Dankrad Feist","year":"2023"},{"key":"ref39:DES:AHIV23","doi-asserted-by":"publisher","first-page":"3379","DOI":"10.1007\/S10623-023-01222-8","article-title":"Ligero: lightweight sublinear arguments without a trusted\n  setup","volume":"91","author":"Scott Ames","year":"2023","journal-title":"Des. Codes Cryptogr."},{"key":"ref40:EPRINT:FeiKho23","volume-title":"Fast amortized KZG proofs","author":"Dankrad Feist","year":"2023"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T17:12:33Z","timestamp":1736788353000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/4\/34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,13]]},"references-count":40,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,1,13]]}},"URL":"https:\/\/doi.org\/10.62056\/a09qudhdj","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,13]]},"assertion":[{"value":"2024-10-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-4-74"}}