Baloo: Algebraic Lookup Arguments
Authors
Arantxa Zapico, Ariel Gabizon, Dmitry Khovratovich, Mary Maller, Carla Ràfols
Arantxa Zapico
Ethereum Foundation, Singapore
arantxa dot zapico at ethereum dot org
arantxa dot zapico at ethereum dot org
Dmitry Khovratovich
Ethereum Foundation, Singapore
Carla Ràfols
Universitat Pompeu Fabra, Spain
Abstract
We present Baloo, a protocol for lookup tables where the prover work is linear on the number of lookups and independent of the table size. Baloo is built over previous lookup arguments, and the framework for SNARKs from Ràfols and Zapico (CRYPTO 21). Our protocol supports commit-and-prove expansions: the prover selects the subtable containing the elements used in the lookup, that is unknown to the verifier, commits to it and later proves its relation with the committed elements. This feature makes Baloo especially suitable for proving input-output relations on hash functions, and in particular to instantiate the Ethereum Virtual Machine (EVM).
References
[ac22]
arkworks contributors. arkworks zkSNARK ecosystem. 2022.
[AR20]
Shashank Agrawal and Srinivasan Raghuraman. KVaC: Key-Value Commitments for Blockchains and Beyond. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part III, volume 12493 of LNCS, pages 839–869. December 2020. Springer, Cham. DOI: 10.1007/978-3-030-64840-4_28
[AST24]
Arasu Arun, Srinath T. V. Setty, and Justin Thaler. Jolt: SNARKs for Virtual Machines via Lookups. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part VI, volume 14656 of LNCS, pages 3–33. May 2024. Springer, Cham. DOI: 10.1007/978-3-031-58751-1_1
[BB04]
Dan Boneh and Xavier Boyen. Short Signatures Without Random Oracles. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 56–73. May 2004. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-24676-3_4
[BBCCL21]
Olivier Bégassat, Alexandre Belling, Théodore Chapuis-Chkaiban, and Nicolas Liochon1. A specification for a ZK-EVM. https://ethresear.ch/t/a-zk-evm-specification/11549. 2021.
[BCC+15]
Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Essam Ghadafi, Jens Groth, and Christophe Petit. Short Accountable Ring Signatures Based on DDH. In Günther Pernul, Peter Y. A. Ryan, and Edgar R. Weippl, editors, ESORICS 2015, Part I, volume 9326 of LNCS, pages 243–265. September 2015. Springer, Cham. DOI: 10.1007/978-3-319-24174-6_13
[BCF+21]
Daniel Benarroch, Matteo Campanelli, Dario Fiore, Kobi Gurkan, and Dimitris Kolonelos. Zero-Knowledge Proofs for Set Membership: Efficient, Succinct, Modular. In Nikita Borisov and Claudia Díaz, editors, FC 2021, Part I, volume 12674 of LNCS, pages 393–414. March 2021. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-64322-8_19
[BCG+13]
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 90–108. August 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-40084-1_6
[BCG+18]
Jonathan Bootle, Andrea Cerulli, Jens Groth, Sune K. Jakobsen, and Mary Maller. Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part I, volume 11272 of LNCS, pages 595–626. December 2018. Springer, Cham. DOI: 10.1007/978-3-030-03326-2_20
[BCR+19]
Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent Succinct Arguments for R1CS. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part I, volume 11476 of LNCS, pages 103–128. May 2019. Springer, Cham. DOI: 10.1007/978-3-030-17653-2_4
[BG13]
Stephanie Bayer and Jens Groth. Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 646–663. May 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-38348-9_38
[BGH19]
Sean Bowe, Jack Grigg, and Daira Hopwood. Halo: Recursive Proof Composition without a Trusted Setup. Cryptology ePrint Archive, Report 2019/1021. 2019.
[CDGM19]
Melissa Chase, Apoorvaa Deshpande, Esha Ghosh, and Harjasleen Malvai. SEEMless: Secure End-to-End Encrypted Messaging with less Trust. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 1639–1656. November 2019. ACM Press. DOI: 10.1145/3319535.3363202
[CEO22]
Matteo Campanelli, Felix Engelmann, and Claudio Orlandi. Zero-Knowledge for Homomorphic Key-Value Commitments with Applications to Privacy-Preserving Ledgers. In Clemente Galdi and Stanislaw Jarecki, editors, SCN 22, volume 13409 of LNCS, pages 761–784. September 2022. Springer, Cham. DOI: 10.1007/978-3-031-14791-3_33
[CFF+21]
Matteo Campanelli, Antonio Faonio, Dario Fiore, Anaïs Querol, and Hadrián Rodríguez. Lunar: A Toolbox for More Efficient Universal and Updatable zkSNARKs and Commit-and-Prove Extensions. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part III, volume 13092 of LNCS, pages 3–33. December 2021. Springer, Cham. DOI: 10.1007/978-3-030-92078-4_1
[CFF+24]
Matteo Campanelli, Antonio Faonio, Dario Fiore, Tianyu Li, and Helger Lipmaa. Lookup Arguments: Improvements, Extensions and Applications to Zero-Knowledge Decision Trees. In Qiang Tang and Vanessa Teague, editors, PKC 2024, Part II, volume 14602 of LNCS, pages 337–369. April 2024. Springer, Cham. DOI: 10.1007/978-3-031-57722-2_11
[CFG+20]
Matteo Campanelli, Dario Fiore, Nicola Greco, Dimitris Kolonelos, and Luca Nizzardo. Incrementally Aggregatable Vector Commitments and Applications to Verifiable Decentralized Storage. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part II, volume 12492 of LNCS, pages 3–35. December 2020. Springer, Cham. DOI: 10.1007/978-3-030-64834-3_1
[CFH+22]
Matteo Campanelli, Dario Fiore, Semin Han, Jihye Kim, Dimitris Kolonelos, and Hyunok Oh. Succinct Zero-Knowledge Batch Proofs for Set Accumulators. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022, pages 455–469. November 2022. ACM Press. DOI: 10.1145/3548606.3560677
[CFQ19]
Matteo Campanelli, Dario Fiore, and Anaïs Querol. LegoSNARK: Modular Design and Composition of Succinct Zero-Knowledge Proofs. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 2075–2092. November 2019. ACM Press. DOI: 10.1145/3319535.3339820
[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, Cham. DOI: 10.1007/978-3-030-45721-1_26
[DP25]
Benjamin E. Diamond and Jim Posen. Succinct Arguments over Towers of Binary Fields. , pages 93–122. June 2025. Springer, Cham. DOI: 10.1007/978-3-031-91134-7_4
[EFG22]
Liam Eagen, Dario Fiore, and Ariel Gabizon. cq: Cached quotients for fast lookups. Cryptology ePrint Archive, Report 2022/1763. 2022.
[Eth22]
ZKEVM Introduction. https://github.com/privacy-scaling-explorations/zkevm-specs/blob/master/specs/introduction.md. 2022.
[FK23]
Dankrad Feist and Dmitry Khovratovich. Fast amortized KZG proofs. 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, Cham. DOI: 10.1007/978-3-319-96881-0_2
[GG17]
Essam Ghadafi and Jens Groth. Towards a Classification of Non-interactive Computational Assumptions in Cyclic Groups. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part II, volume 10625 of LNCS, pages 66–96. December 2017. Springer, Cham. DOI: 10.1007/978-3-319-70697-9_3
[GK15]
Jens Groth and Markulf Kohlweiss. One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, pages 253–280. April 2015. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-46803-6_9
[GK22]
Ariel Gabizon and Dmitry Khovratovich. flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size. Cryptology ePrint Archive, Report 2022/1447. 2022.
[GKL+22]
Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, Markus Schofnegger, and Roman Walch. Reinforced Concrete: A Fast Hash Function for Verifiable Computation. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022, pages 1323–1335. November 2022. ACM Press. DOI: 10.1145/3548606.3560686
[GM24]
Albert Garreta and Ignacio Manzur. FLI: Folding Lookup Instances. In Kai-Min Chung and Yu Sasaki, editors, ASIACRYPT 2024, Part V, volume 15488 of LNCS, pages 402–435. December 2024. Springer, Singapore. DOI: 10.1007/978-981-96-0935-2_13
[GW20]
Ariel Gabizon and Zachary J. Williamson. plookup: A simplified polynomial protocol for lookup tables. Cryptology ePrint Archive, Report 2020/315. 2020.
[GWC19]
Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. Cryptology ePrint Archive, Report 2019/953. 2019.
[Hab22]
Ulrich Haböck. Multivariate lookups based on logarithmic derivatives. Cryptology ePrint Archive, Report 2022/1530. 2022.
[HHK+21]
Yuncong Hu, Kian Hooshmand, Harika Kalidhindi, Seung Jin Yang, and Raluca Ada Popa. Merkle$^2$: A Low-Latency Transparency Log System. In 2021 IEEE Symposium on Security and Privacy, pages 285–303. May 2021. IEEE Computer Society Press. DOI: 10.1109/SP40001.2021.00088
[KST22]
Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla. Nova: Recursive Zero-Knowledge Arguments from Folding Schemes. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part IV, volume 13510 of LNCS, pages 359–388. August 2022. Springer, Cham. DOI: 10.1007/978-3-031-15985-5_13
[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, Berlin, Heidelberg. DOI: 10.1007/978-3-642-17373-8_11
[MKL+20]
Sarah Meiklejohn, Pavel Kalinnikov, Cindy S. Lin, Martin Hutchinson, Gary Belvin, Mariana Raykova, and Al Cutter. Think Global, Act Local: Gossip and Client Audits in Verifiable Data Structures. CoRR, abs/2011.04551, 2020.
[PH23]
Shahar Papini and Ulrich Haböck. Improving logarithmic derivative lookups using GKR. Cryptology ePrint Archive, Report 2023/1284. 2023.
[PK22]
Jim Posen and Assimakis A. Kattis. Caulk+: Table-independent lookup arguments. Cryptology ePrint Archive, Report 2022/957. 2022.
[Pol22]
Polygon zkEVM Documentation. https://docs.hermez.io/zkEVM/Overview/Overview/. 2022.
[PZ22]
Team Polygon Zero. Plonky2: Fast Recursive Arguments with PLONK and FRIO. 2022.
[RZ21]
Carla Ràfols and Arantxa Zapico. An Algebraic Framework for Universal and Updatable SNARKs. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, pages 774–804, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84242-0_27
[Sal23]
Robin Salen. Two additional instantiations from the Tip5 hash function construction. 2023.
[Set20]
Srinath Setty. Spartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part III, volume 12172 of LNCS, pages 704–737. August 2020. Springer, Cham. DOI: 10.1007/978-3-030-56877-1_25
[SLST23]
Alan Szepieniec, Alexander Lemmens, Jan Ferdinand Sauer, and Bobbin Threadbare. The Tip5 Hash Function for Recursive STARKs. Cryptology ePrint Archive, Report 2023/107. 2023.
[Sta22]
StarkNet. https://starkware.co/starknet/. 2022.
[STW24]
Srinath T. V. Setty, Justin Thaler, and Riad S. Wahby. Unlocking the Lookup Singularity with Lasso. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part VI, volume 14656 of LNCS, pages 180–209. May 2024. Springer, Cham. DOI: 10.1007/978-3-031-58751-1_7
[TAB+20]
Alin Tomescu, Ittai Abraham, Vitalik Buterin, Justin Drake, Dankrad Feist, and Dmitry Khovratovich. Aggregatable Subvector Commitments for Stateless Cryptocurrencies. In Clemente Galdi and Vladimir Kolesnikov, editors, SCN 20, volume 12238 of LNCS, pages 45–64. September 2020. Springer, Cham. DOI: 10.1007/978-3-030-57990-6_3
[TBP+19]
Alin Tomescu, Vivek Bhupatiraju, Dimitrios Papadopoulos, Charalampos Papamanthou, Nikos Triandopoulos, and Srinivas Devadas. Transparency Logs via Append-Only Authenticated Dictionaries. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 1299–1316. November 2019. ACM Press. DOI: 10.1145/3319535.3345652
[TFBT21]
Nirvan Tyagi, Ben Fisch, Joseph Bonneau, and Stefano Tessaro. Client-Auditable Verifiable Registries. Cryptology ePrint Archive, Report 2021/627. 2021.
[vzGG13]
Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra (3. ed.). Cambridge University Press 2013. DOI: https://doi.org/10.1017/CBO9781139856065
[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, pages 3121–3134. November 2022. ACM Press. DOI: 10.1145/3548606.3560646
[Zha22]
Ye Zhang. Introducing zkEVM. https://scroll.io/blog/zkEVM. 2022.
[zks22]
zkEVM FAQ. https://docs.zksync.io/zkevm/. 2022.
PDF
History
Submitted: 2024-10-09
Accepted: 2025-03-11
Published: 2025-07-07
Accepted: 2025-03-11
Published: 2025-07-07
How to cite
Arantxa Zapico, Ariel Gabizon, Dmitry Khovratovich, Mary Maller, and Carla Ràfols, Baloo: Algebraic Lookup Arguments. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/ae890l5vt.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.