{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:40:06Z","timestamp":1751924406596,"version":"3.41.2"},"reference-count":54,"publisher":"International Association for Cryptologic Research","issue":"2","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":[[2025,3,11]]},"abstract":"<jats:p>        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\u00e0fols 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). <\/jats:p>","DOI":"10.62056\/ae890l5vt","type":"journal-article","created":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:09:09Z","timestamp":1751922549000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Baloo: Algebraic Lookup Arguments"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9587-8494","authenticated-orcid":false,"given":"Arantxa","family":"Zapico","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/059r3nh67","id-type":"ROR","asserted-by":"publisher"}],"name":"Ethereum Foundation","place":["Singapore"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ariel","family":"Gabizon","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03x4rma83","id-type":"ROR","asserted-by":"publisher"}],"name":"Aztec Labs","place":["UK"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-0347-3378","authenticated-orcid":false,"given":"Dmitry","family":"Khovratovich","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/059r3nh67","id-type":"ROR","asserted-by":"publisher"}],"name":"Ethereum Foundation","place":["Singapore"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mary","family":"Maller","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/059r3nh67","id-type":"ROR","asserted-by":"publisher"}],"name":"Ethereum Foundation","place":["Singapore"]},{"id":[{"id":"https:\/\/ror.org\/03sdv7269","id-type":"ROR","asserted-by":"publisher"}],"name":"PQ Shield","place":["UK"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7035-9049","authenticated-orcid":false,"given":"Carla","family":"R\u00e0fols","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04n0g0b29","id-type":"ROR","asserted-by":"publisher"}],"name":"Universitat Pompeu Fabra","place":["Spain"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2025,7,7]]},"reference":[{"key":"ref1:EPRINT:GabWil20","volume-title":"plookup: A simplified polynomial protocol for lookup\n  tables","author":"Ariel Gabizon","year":"2020"},{"key":"ref2:CCS:ZBKMNS22","doi-asserted-by":"publisher","first-page":"3121","DOI":"10.1145\/3548606.3560646","article-title":"Caulk: Lookup Arguments in Sublinear Time","author":"Arantxa Zapico","year":"2022"},{"key":"ref3:EPRINT:PosKat22","volume-title":"Caulk+: Table-independent lookup arguments","author":"Jim Posen","year":"2022"},{"key":"ref4:ConsenSys","volume-title":"A specification for a ZK-EVM","author":"Olivier B\u00e9gassat","year":"2021"},{"key":"ref5:EFzkevm","volume-title":"ZKEVM Introduction","year":"2022"},{"key":"ref6:Polygon","volume-title":"Polygon zkEVM Documentation","year":"2022"},{"key":"ref7:starknet","volume-title":"StarkNet","year":"2022"},{"key":"ref8:scroll","volume-title":"Introducing zkEVM","author":"Ye Zhang","year":"2022"},{"key":"ref9:zksync","volume-title":"zkEVM FAQ","year":"2022"},{"key":"ref10: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":"ref11:EPRINT:BowGriHop19","volume-title":"Halo: Recursive Proof Composition without a Trusted Setup","author":"Sean Bowe","year":"2019"},{"key":"ref12:EPRINT:GabKho22","volume-title":"flookup: Fractional decomposition-based lookups in\n  quasi-linear time independent of table size","author":"Ariel Gabizon","year":"2022"},{"key":"ref13:EPRINT:EagFioGab22","volume-title":"cq: Cached quotients for fast lookups","author":"Liam Eagen","year":"2022"},{"key":"ref14:EC:BayGro13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1007\/978-3-642-38348-9_38","article-title":"Zero-Knowledge Argument for Polynomial Evaluation with\n  Application to Blacklists","volume":"7881","author":"Stephanie Bayer","year":"2013"},{"key":"ref15:EC:GroKoh15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-662-46803-6_9","article-title":"One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a\n  Coin","volume":"9057","author":"Jens Groth","year":"2015"},{"key":"ref16:ESORICS:BCCGGP15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-319-24174-6_13","article-title":"Short Accountable Ring Signatures Based on DDH","volume":"9326","author":"Jonathan Bootle","year":"2015"},{"key":"ref17:AC:BCGJM18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/978-3-030-03326-2_20","article-title":"Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct\n  Program Execution","volume":"11272","author":"Jonathan Bootle","year":"2018"},{"key":"ref18:C:BCGTV13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-40084-1_6","article-title":"SNARKs for C: Verifying Program Executions Succinctly\n  and in Zero Knowledge","volume":"8043","author":"Eli Ben-Sasson","year":"2013"},{"key":"ref19:CCS:CFHKKO22","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1145\/3548606.3560677","article-title":"Succinct Zero-Knowledge Batch Proofs for Set Accumulators","author":"Matteo Campanelli","year":"2022"},{"key":"ref20:CCS:CDGM19","doi-asserted-by":"publisher","first-page":"1639","DOI":"10.1145\/3319535.3363202","article-title":"SEEMless: Secure End-to-End Encrypted Messaging with less\n  Trust","author":"Melissa Chase","year":"2019"},{"key":"ref21:CCS:TBPPTD19","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1145\/3319535.3345652","article-title":"Transparency Logs via Append-Only Authenticated\n  Dictionaries","author":"Alin Tomescu","year":"2019"},{"key":"ref22:MeiklejohnKLHBRC20","article-title":"Think Global, Act Local: Gossip and Client Audits in\n  Verifiable Data Structures","volume":"abs\/2011.04551","author":"Sarah Meiklejohn","year":"2020","journal-title":"CoRR"},{"key":"ref23:SP:HHKYP21","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1109\/SP40001.2021.00088","article-title":"Merkle$^2$: A Low-Latency Transparency Log System","author":"Yuncong Hu","year":"2021"},{"key":"ref24:EPRINT:TFBT21","volume-title":"Client-Auditable Verifiable Registries","author":"Nirvan Tyagi","year":"2021"},{"key":"ref25:SCN:CamEngOrl22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1007\/978-3-031-14791-3_33","article-title":"Zero-Knowledge for Homomorphic Key-Value Commitments with\n  Applications to Privacy-Preserving Ledgers","volume":"13409","author":"Matteo Campanelli","year":"2022"},{"key":"ref26:AC:AgrRag20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1007\/978-3-030-64840-4_28","article-title":"KVaC: Key-Value Commitments for Blockchains and\n  Beyond","volume":"12493","author":"Shashank Agrawal","year":"2020"},{"key":"ref27:AC:CFGKN20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-64834-3_1","article-title":"Incrementally Aggregatable Vector Commitments and\n  Applications to Verifiable Decentralized Storage","volume":"12492","author":"Matteo Campanelli","year":"2020"},{"key":"ref28:FC:BCFGK21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/978-3-662-64322-8_19","article-title":"Zero-Knowledge Proofs for Set Membership: Efficient,\n  Succinct, Modular","volume":"12674","author":"Daniel Benarroch","year":"2021"},{"key":"ref29:EPRINT:PapHab23","volume-title":"Improving logarithmic derivative lookups using GKR","author":"Shahar Papini","year":"2023"},{"key":"ref30:PKC:CFFLL24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-031-57722-2_11","article-title":"Lookup Arguments: Improvements, Extensions and Applications\n  to Zero-Knowledge Decision Trees","volume":"14602","author":"Matteo Campanelli","year":"2024"},{"key":"ref31:EPRINT:Habock22b","volume-title":"Multivariate lookups based on logarithmic derivatives","author":"Ulrich Hab\u00f6ck","year":"2022"},{"key":"ref32:EPRINT:GabWilCio19","volume-title":"PLONK: Permutations over Lagrange-bases for Oecumenical\n  Noninteractive arguments of Knowledge","author":"Ariel Gabizon","year":"2019"},{"key":"ref33:C:RafZap21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1007\/978-3-030-84242-0_27","article-title":"An Algebraic Framework for Universal and Updatable\n  SNARKs","volume":"12825","author":"Carla R\u00e0fols","year":"2021"},{"key":"ref34: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":"ref35:EC:BCRSVW19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-030-17653-2_4","article-title":"Aurora: Transparent Succinct Arguments for R1CS","volume":"11476","author":"Eli Ben-Sasson","year":"2019"},{"key":"ref36:AC:CFFQR21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-92078-4_1","article-title":"Lunar: A Toolbox for More Efficient Universal and\n  Updatable zkSNARKs and Commit-and-Prove Extensions","volume":"13092","author":"Matteo Campanelli","year":"2021"},{"key":"ref37:C:Setty20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1007\/978-3-030-56877-1_25","article-title":"Spartan: Efficient and General-Purpose zkSNARKs Without\n  Trusted Setup","volume":"12172","author":"Srinath Setty","year":"2020"},{"key":"ref38:EC:SetThaWah24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-031-58751-1_7","article-title":"Unlocking the Lookup Singularity with Lasso","volume":"14656","author":"Srinath T. V. Setty","year":"2024"},{"key":"ref39:EC:AruSetTha24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-58751-1_1","article-title":"Jolt: SNARKs for Virtual Machines via Lookups","volume":"14656","author":"Arasu Arun","year":"2024"},{"key":"ref40:AC:GarMan24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/978-981-96-0935-2_13","article-title":"FLI: Folding Lookup Instances","volume":"15488","author":"Albert Garreta","year":"2024"},{"key":"ref41:C:KotSetTzi22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-031-15985-5_13","article-title":"Nova: Recursive Zero-Knowledge Arguments from Folding\n  Schemes","volume":"13510","author":"Abhiram Kothapalli","year":"2022"},{"key":"ref42:plonky2","volume-title":"Plonky2: Fast Recursive Arguments with PLONK and FRIO","author":"Team Polygon Zero","year":"2022"},{"key":"ref43:CCS:GKLRSW22","doi-asserted-by":"publisher","first-page":"1323","DOI":"10.1145\/3548606.3560686","article-title":"Reinforced Concrete: A Fast Hash Function for Verifiable\n  Computation","author":"Lorenzo Grassi","year":"2022"},{"key":"ref44:EPRINT:SLST23","volume-title":"The Tip5 Hash Function for Recursive STARKs","author":"Alan Szepieniec","year":"2023"},{"key":"ref45:Salen","volume-title":"Two additional instantiations from the Tip5 hash function\n  construction","author":"Robin Salen","year":"2023"},{"key":"ref46:EC:DiaPos25","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-031-91134-7_4","article-title":"Succinct Arguments over Towers of Binary Fields","author":"Benjamin E. Diamond","year":"2025"},{"key":"ref47: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":"ref48:AC:GhaGro17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-319-70697-9_3","article-title":"Towards a Classification of Non-interactive Computational\n  Assumptions in Cyclic Groups","volume":"10625","author":"Essam Ghadafi","year":"2017"},{"key":"ref49:EC:BonBoy04a","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-540-24676-3_4","article-title":"Short Signatures Without Random Oracles","volume":"3027","author":"Dan Boneh","year":"2004"},{"key":"ref50:SCN:TABDFK20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-030-57990-6_3","article-title":"Aggregatable Subvector Commitments for Stateless\n  Cryptocurrencies","volume":"12238","author":"Alin Tomescu","year":"2020"},{"key":"ref51:FeistK20","first-page":"33","volume-title":"Fast amortized KZG proofs","author":"Dankrad Feist","year":"2023","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref52:CCS:CamFioQue19","doi-asserted-by":"publisher","first-page":"2075","DOI":"10.1145\/3319535.3339820","article-title":"LegoSNARK: Modular Design and Composition of Succinct\n  Zero-Knowledge Proofs","author":"Matteo Campanelli","year":"2019"},{"key":"ref53:GathenG13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065","volume-title":"Modern Computer Algebra (3. ed.)","author":"Joachim von zur Gathen","year":"2013"},{"key":"ref54:arkworks","volume-title":"zkSNARK ecosystem","author":"arkworks contributors","year":"2022"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:09:14Z","timestamp":1751922554000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/2\/1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,7]]},"references-count":54,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,7,7]]}},"URL":"https:\/\/doi.org\/10.62056\/ae890l5vt","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,7]]},"assertion":[{"value":"2024-10-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-4-67"}}