Boomy: Batch Opening Of Multivariate polYnomial commitment
Authors
Thomas Lavaur, Jérôme Lacan
Thomas Lavaur
ISAE-SUPAERO, France
University Toulouse III Paul Sabatier, France
thomas dot lavaur at isae-supaero dot fr
University Toulouse III Paul Sabatier, France
thomas dot lavaur at isae-supaero dot fr
Jérôme Lacan
ISAE-SUPAERO, France
jerome dot lacan at isae-supaero dot fr
jerome dot lacan at isae-supaero dot fr
Abstract
We present Boomy, a multivariate polynomial commitment scheme enabling the proof of the evaluation of multiple points, i.e., batch opening. Boomy is the natural extension of two popular protocols: the univariate polynomial commitment scheme of Kate, Zaverucha and Goldberg[KZG10] and its multivariate counterpart from Papamanthou, Shi and Tamassia[PST13]. Our construction is proven secure under the selective security model. In this paper, we present Boomy's complexity and the applications on which it can have a significant impact. In fact, Boomy is perfectly suited to tackling blockchain problems by greatly improving data availability sampling and shrinking existing challenges. We also present special lower-complexity cases that occur frequently in practical situations.
References
[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, FC 2021: 25th International Conference on Financial Cryptography and Data Security, Part II, volume 12675 of Lecture Notes in Computer Science, pages 279–298, Virtual Event. March 1–5, 2021. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-662-64331-0_15
[BBB+18]
Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short Proofs for Confidential Transactions and More. In 2018 IEEE Symposium on Security and Privacy, pages 315–334, San Francisco, CA, USA. May 21–23, 2018. IEEE Computer Society Press. DOI: 10.1109/SP.2018.00020
[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.
[BFL20]
Balthazar Bauer, Georg Fuchsbauer, and Julian Loss. A Classification of Computational Assumptions in the Algebraic Group Model. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part II, volume 12171 of Lecture Notes in Computer Science, pages 121–151, Santa Barbara, CA, USA. August 17–21, 2020. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-56880-1_5
[BN23]
Dan Boneh and Valeria Nikolaenko. Data availability sampling and danksharding: An overview and a proposal for improvements. https://a16zcrypto.com/posts/article/an-overview-of-danksharding-and-a-proposal-for-improvement-of-das/. a16zcrypto. April. 2023.
[Buc76]
Bruno Buchberger. A theoretical basis for the reduction of polynomials to canonical forms. ACM SIGSAM Bulletin, 10(3):19–29, 1976. DOI: 10.1145/1088216.1088219
[But22]
Vitalik Buterin. Proto-danksharding faq. https://notes.ethereum.org/@vbuterin/proto_danksharding_faq. HackMD. July. 2022.
[CBBZ23]
Binyi Chen, Benedikt Bünz, Dan Boneh, and Zhenfei Zhang. HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part II, volume 14005 of Lecture Notes in Computer Science, pages 499–530, Lyon, France. April 23–27, 2023. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-30617-4_17
[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, Advances in Cryptology – EUROCRYPT 2020, Part I, volume 12105 of Lecture Notes in Computer Science, pages 738–768, Zagreb, Croatia. May 10–14, 2020. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-45721-1_26
[CLOS94]
David Cox, John Little, Donal O'Shea, and Moss Sweedler. Ideals, varieties, and algorithms. American Mathematical Monthly, 101(6):582–586, 1994. DOI: 10.1007/978-3-319-16721-3
[CT05]
Christian Cachin and Stefano Tessaro. Asynchronous verifiable information dispersal. In 24th IEEE Symposium on Reliable Distributed Systems (SRDS'05), pages 191–201. 2005. IEEE. DOI: 10.1109/RELDIS.2005.9
[Dam98]
Ivan Damgård. Commitment schemes and zero-knowledge protocols. In School organized by the European Educational Forum, pages 63–86. 1998. Springer. DOI: 10.1007/3-540-48969-X_3
[FG06]
Jeffrey B Farr and Shuhong Gao. Computing Gröbner bases for vanishing ideals of finite sets of points. In International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, pages 118–127. 2006. Springer. DOI: 10.1007/11617983_11
[FKL18]
Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The Algebraic Group Model and its Applications. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part II, volume 10992 of Lecture Notes in Computer Science, pages 33–62, Santa Barbara, CA, USA. August 19–23, 2018. Springer, Cham, Switzerland. DOI: 10.1007/978-3-319-96881-0_2
[GMC07]
Fuchun Guo, Yi Mu, and Zhide Chen. Identity-Based Encryption: How to Decrypt Multiple Ciphertexts Using a Single Decryption Key. In Tsuyoshi Takagi, Tatsuaki Okamoto, Eiji Okamoto, and Takeshi Okamoto, editors, PAIRING 2007: 1st International Conference on Pairing-based Cryptography, volume 4575 of Lecture Notes in Computer Science, pages 392–406, Tokyo, Japan. July 2–4, 2007. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-540-73489-5_22
[GWC19]
Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. https://eprint.iacr.org/2019/953. Cryptology ePrint Archive, Report 2019/953. 2019.
[HASW25]
Mathias Hall-Andersen, Mark Simkin, and Benedikt Wagner. Foundations of Data Availability Sampling. IACR Communications in Cryptology, 1(4), 2025. DOI: 10.62056/a09qudhdj
[HBHW16]
Daira Hopwood, Sean Bowe, Taylor Hornby, and Nathan Wilcox. Zcash protocol specification. GitHub: San Francisco, CA, USA. 2016.
[KAR+23]
Michał Król, Onur Ascigil, Sergi Rene, Etienne Rivière, Matthieu Pigaglio, Kaleem Peeroo, Vladimir Stankovic, Ramin Sadre, and Felix Lange. Data Availability Sampling in Ethereum: Analysis of P2P Networking Requirements. arXiv preprint arXiv:2306.11456. 2023.
[KMSV21]
Markulf Kohlweiss, Mary Maller, Janno Siim, and Mikhail Volkhov. Snarky Ceremonies. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, Part III, volume 13092 of Lecture Notes in Computer Science, pages 98–127, Singapore. December 6–10, 2021. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-92078-4_4
[KZG10]
Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-Size Commitments to Polynomials and Their Applications. In Masayuki Abe, editor, Advances in Cryptology – ASIACRYPT 2010, volume 6477 of Lecture Notes in Computer Science, pages 177–194, Singapore. December 5–9, 2010. Springer Berlin Heidelberg, Germany. DOI: 10.1007/978-3-642-17373-8_11
[Lee21]
Jonathan Lee. Dory: Efficient, Transparent Arguments for Generalised Inner Products and Polynomial Commitments. In Kobbi Nissim and Brent Waters, editors, TCC 2021: 19th Theory of Cryptography Conference, Part II, volume 13043 of Lecture Notes in Computer Science, pages 1–34, Raleigh, NC, USA. November 8–11, 2021. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-90453-1_1
[PST13]
Charalampos Papamanthou, Elaine Shi, and Roberto Tamassia. Signatures of correct computation. In Theory of Cryptography Conference, pages 222–242. 2013. Springer. DOI: 0.1007/978-3-642-36594-2_13
[Rab89]
Michael O Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM (JACM), 36(2):335–348, 1989. DOI: 10.1145/62044.62050
[TSH22]
Louis Tremblay Thibault, Tom Sarry, and Abdelhakim Senhaji Hafid. Blockchain scaling using rollups: A comprehensive survey. IEEE Access, 2022. DOI: 10.1109/ACCESS.2022.3200051
[VDH17]
Joris Van Der Hoeven. On the complexity of multivariate polynomial division. In Applications of Computer Algebra: Kalamata, Greece, July 20–23 2015, pages 447–458. 2017. Springer. DOI: 10.1007/978-3-319-56932-1_28
[VZGG13]
Joachim Von Zur Gathen and Jürgen Gerhard. Modern computer algebra. Cambridge university press 2013. DOI: 10.1017/CBO9781139856065
[XZS22]
Tiancheng Xie, Yupeng Zhang, and Dawn Song. Orion: Zero Knowledge Proof with Linear Prover Time. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, Part IV, volume 13510 of Lecture Notes in Computer Science, pages 299–328, Santa Barbara, CA, USA. August 15–18, 2022. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-15985-5_11
[YYV17]
Xixun Yu, Zheng Yan, and Athanasios V Vasilakos. A survey of verifiable computation. Mobile Networks and Applications, 22:438–453, 2017. DOI: 10.1007/s11036-017-0872-3
[ZBK+22]
Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu, and Mark Simkin. Caulk: Lookup Arguments in Sublinear Time. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022: 29th Conference on Computer and Communications Security, pages 3121–3134, Los Angeles, CA, USA. November 7–11, 2022. ACM Press. DOI: 10.1145/3548606.3560646
PDF
History
Submitted: 2024-12-09
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Thomas Lavaur and Jérôme Lacan, Boomy: Batch Opening Of Multivariate polYnomial commitment. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/an5tx4e-.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.