Foundations of Data Availability Sampling
Authors
Mathias Hall-Andersen, Mark Simkin, Benedikt Wagner
Mathias Hall-Andersen
ZkSecurity, Denmark
mathias at zksecurity dot xyz
mathias at zksecurity dot xyz
Mark Simkin
Independent Researcher, Denmark
mark at univariate dot org
mark at univariate dot org
Benedikt Wagner
Ethereum Foundation, Germany
benedikt dot wagner at ethereum dot org
benedikt dot wagner at ethereum dot org
Abstract
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.
References
[ABC+07]
Giuseppe Ateniese, Randal C. Burns, Reza Curtmola, Joseph Herring, Lea Kissner, Zachary N. J. Peterson, and Dawn Song. Provable data possession at untrusted stores. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson, editors, ACM CCS 2007, pages 598–609. October 2007. ACM Press. DOI: 10.1145/1315245.1315318
[ADVZ21]
Nicolas Alhaddad, Sisi Duan, Mayank Varia, and Haibin Zhang. Succinct Erasure Coding Proof Systems. https://eprint.iacr.org/2021/1500. Cryptology ePrint Archive, Report 2021/1500. 2021.
[AHIV17]
Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: Lightweight Sublinear Arguments Without a Trusted Setup. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 2087–2104. 2017. ACM Press. DOI: 10.1145/3133956.3134104
[AHIV23]
Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. Ligero: lightweight sublinear arguments without a trusted setup. Des. Codes Cryptogr., 91(11):3379–3424, 2023. DOI: 10.1007/S10623-023-01222-8
[ASBK21]
Mustafa Al-Bassam, Alberto Sonnino, Vitalik Buterin, and Ismail Khoffi. Fraud and Data Availability Proofs: Detecting Invalid Blocks in Light Clients. In Nikita Borisov and Claudia Díaz, editors, Financial Cryptography and Data Security - 25th International Conference, FC 2021, Virtual Event, March 1-5, 2021, Revised Selected Papers, Part II, volume 12675 of Lecture Notes in Computer Science, pages 279–298. 2021. Springer. DOI: 10.1007/978-3-662-64331-0_15
[BBHR18]
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, ICALP 2018, volume 107 of LIPIcs, pages 14:1–14:17. July 2018. Schloss Dagstuhl. DOI: 10.4230/LIPIcs.ICALP.2018.14
[BCG+17]
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Interactive Oracle Proofs with Constant Rate and Query Complexity. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, ICALP 2017, volume 80 of LIPIcs, pages 40:1–40:15. July 2017. Schloss Dagstuhl. DOI: 10.4230/LIPIcs.ICALP.2017.40
[BDFG20]
Dan Boneh, Justin Drake, Ben Fisch, and Ariel Gabizon. Efficient polynomial commitment schemes for multiple points and polynomials. https://eprint.iacr.org/2020/081. Cryptology ePrint Archive, Report 2020/081. 2020.
[BFM88]
Manuel Blum, Paul Feldman, and Silvio Micali. Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). In 20th ACM STOC, pages 103–112. May 1988. ACM Press. DOI: 10.1145/62212.62222
[BGH+06]
Eli Ben‐Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan. Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM Journal on Computing, 36(4):889-974, 2006. DOI: 10.1137/S0097539705446810
[BGKS20]
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness. In Thomas Vidick, editor, ITCS 2020, volume 151, pages 5:1–5:32. January 2020. LIPIcs. DOI: 10.4230/LIPIcs.ITCS.2020.5
[CDD+16]
Ignacio Cascudo, Ivan Damgård, Bernardo David, Nico Döttling, and Jesper Buus Nielsen. Rate-1, Linear Time and Additively Homomorphic UC Commitments. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS, pages 179–207. August 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-53015-3_7
[CF13]
Dario Catalano and Dario Fiore. Vector Commitments and Their Applications. In Kaoru Kurosawa and Goichiro Hanaoka, editors, PKC 2013, volume 7778 of LNCS, pages 55–72. 2013. Springer, Heidelberg. DOI: 10.1007/978-3-642-36362-7_5
[CFM08]
Dario Catalano, Dario Fiore, and Mariagrazia Messina. Zero-Knowledge Sets with Short Proofs. In Nigel P. Smart, editor, EUROCRYPT 2008, volume 4965 of LNCS, pages 433–450. April 2008. Springer, Heidelberg. DOI: 10.1007/978-3-540-78967-3_25
[CGKS23]
Matteo Campanelli, Chaya Ganesh, Hamidreza Khoshakhlagh, and Janno Siim. Impossibilities in Succinct Arguments: Black-Box Extraction and More. In Nadia El Mrabet, Luca De Feo, and Sylvain Duquesne, editors, Progress in Cryptology - AFRICACRYPT 2023 - 14th International Conference on Cryptology in Africa, Sousse, Tunisia, July 19-21, 2023, Proceedings, volume 14064 of Lecture Notes in Computer Science, pages 465–489. 2023. Springer. DOI: 10.1007/978-3-031-37679-5_20
[CHL+05]
Melissa Chase, Alexander Healy, Anna Lysyanskaya, Tal Malkin, and Leonid Reyzin. Mercurial Commitments with Applications to Zero-Knowledge Sets. In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 422–439. May 2005. Springer, Heidelberg. DOI: 10.1007/11426639_25
[CHM+20]
Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas P. Ward. Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 738–768. May 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-45721-1_26
[CKW13]
David Cash, Alptekin Küpçü, and Daniel Wichs. Dynamic Proofs of Retrievability via Oblivious RAM. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 279–295. May 2013. Springer, Heidelberg. DOI: 10.1007/978-3-642-38348-9_17
[CT05]
Christian Cachin and Stefano Tessaro. Asynchronous Verifiable Information Dispersal. In Pierre Fraigniaud, editor, Distributed Computing, 19th International Conference, DISC 2005, Cracow, Poland, September 26-29, 2005, Proceedings, volume 3724 of Lecture Notes in Computer Science, pages 503–504. 2005. Springer. DOI: 10.1007/11561927_42
[DVW09]
Yevgeniy Dodis, Salil P. Vadhan, and Daniel Wichs. Proofs of Retrievability via Hardness Amplification. In Omer Reingold, editor, TCC 2009, volume 5444 of LNCS, pages 109–127. March 2009. Springer, Heidelberg. DOI: 10.1007/978-3-642-00457-5_8
[Fei23]
Dankrad Feist. Data availability encoding. Accessed: 2023-05-08. https://notes.ethereum.org/ReasmW86SuKqC2FaX83T1g. 2023.
[Fel87]
Paul Feldman. A Practical Scheme for Non-interactive Verifiable Secret Sharing. In 28th FOCS, pages 427–437. October 1987. IEEE Computer Society Press. DOI: 10.1109/SFCS.1987.4
[FK23]
Dankrad Feist and Dmitry Khovratovich. Fast amortized KZG proofs. https://eprint.iacr.org/2023/033. Cryptology ePrint Archive, Report 2023/033. 2023.
[FKL18]
Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The Algebraic Group Model and its Applications. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part II, volume 10992 of LNCS, pages 33–62. August 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-96881-0_2
[Gro16]
Jens Groth. On the Size of Pairing-Based Non-interactive Arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 305–326. May 2016. Springer, Heidelberg. DOI: 10.1007/978-3-662-49896-5_11
[GW11]
Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In Lance Fortnow and Salil P. Vadhan, editors, 43rd ACM STOC, pages 99–108. June 2011. ACM Press. DOI: 10.1145/1993636.1993651
[HSW24]
Mathias Hall-Andersen, Mark Simkin, and Benedikt Wagner. FRIDA: Data Availability Sampling from FRI. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part VI, volume 14925 of Lecture Notes in Computer Science, pages 289–324. 2024. Springer. DOI: 10.1007/978-3-031-68391-6_9
[JK07]
Ari Juels and Burton S. Kaliski Jr.. Pors: proofs of retrievability for large files. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson, editors, ACM CCS 2007, pages 584–597. October 2007. ACM Press. DOI: 10.1145/1315245.1315317
[Kil92]
Joe Kilian. A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract). In 24th ACM STOC, pages 723–732. May 1992. ACM Press. DOI: 10.1145/129712.129782
[KZG10]
Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-Size Commitments to Polynomials and Their Applications. In Masayuki Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS, pages 177–194. December 2010. Springer, Heidelberg. DOI: 10.1007/978-3-642-17373-8_11
[LRY16]
Benoît Libert, Somindu C. Ramanna, and Moti Yung. Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, ICALP 2016, volume 55 of LIPIcs, pages 30:1–30:14. July 2016. Schloss Dagstuhl. DOI: 10.4230/LIPIcs.ICALP.2016.30
[LY10]
Benoît Libert and Moti Yung. Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs. In Daniele Micciancio, editor, TCC 2010, volume 5978 of LNCS, pages 499–517. February 2010. Springer, Heidelberg. DOI: 10.1007/978-3-642-11799-2_30
[Mer88]
Ralph C. Merkle. A Digital Signature Based on a Conventional Encryption Function. In Carl Pomerance, editor, CRYPTO'87, volume 293 of LNCS, pages 369–378. August 1988. Springer, Heidelberg. DOI: 10.1007/3-540-48184-2_32
[NNT22]
Kamilla Nazirkhanova, Joachim Neu, and David Tse. Information Dispersal with Provable Retrievability for Rollups. In Maurice Herlihy and Neha Narula, editors, Proceedings of the 4th ACM Conference on Advances in Financial Technologies, AFT 2022, Cambridge, MA, USA, September 19-21, 2022, pages 180–197. 2022. ACM. DOI: 10.1145/3558535.3559778
[Ped92]
Torben P. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In Joan Feigenbaum, editor, CRYPTO'91, volume 576 of LNCS, pages 129–140. August 1992. Springer, Heidelberg. DOI: 10.1007/3-540-46766-1_9
[Rab89]
Michael O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. J. ACM, 36(2):335–348, 1989. DOI: 10.1145/62044.62050
[SSP13]
Elaine Shi, Emil Stefanov, and Charalampos Papamanthou. Practical dynamic proofs of retrievability. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, pages 325–336. November 2013. ACM Press. DOI: 10.1145/2508859.2516669
[SW08]
Hovav Shacham and Brent Waters. Compact Proofs of Retrievability. In Josef Pieprzyk, editor, ASIACRYPT 2008, volume 5350 of LNCS, pages 90–107. December 2008. Springer, Heidelberg. DOI: 10.1007/978-3-540-89255-7_7
[SXKV21]
Peiyao Sheng, Bowen Xue, Sreeram Kannan, and Pramod Viswanath. ACeD: Scalable Data Availability Oracle. In Nikita Borisov and Claudia Díaz, editors, FC 2021, Part II, volume 12675 of LNCS, pages 299–318. March 2021. Springer, Heidelberg. DOI: 10.1007/978-3-662-64331-0_16
[YSL+20]
Mingchao Yu, Saeid Sahraei, Songze Li, Salman Avestimehr, Sreeram Kannan, and Pramod Viswanath. Coded Merkle Tree: Solving Data Availability Attacks in Blockchains. In Joseph Bonneau and Nadia Heninger, editors, FC 2020, volume 12059 of LNCS, pages 114–134. February 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-51280-4_8
PDF
History
Submitted: 2024-10-09
Accepted: 2024-12-03
Published: 2025-01-13
Accepted: 2024-12-03
Published: 2025-01-13
How to cite
Mathias Hall-Andersen, Mark Simkin, and Benedikt Wagner, Foundations of Data Availability Sampling. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a09qudhdj.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.