Baloo: algebraic lookup arguments

Zapico Barrionuevo, Victoria Arantxa; Gabizon, Ariel; Khovratovich, Dmitry; Maller, Mary; Ràfols, Carla

doi:http://dx.doi.org/10.62056/ae890l5vt

Baloo: algebraic lookup arguments

License

Citation

Zapico A, Gabizon A, Khovratovich D, Maller M, Ràfols C. Baloo: algebraic lookup arguments. IACR Communications in Cryptology. 2025 Jul 7;2(2):1-35. DOI: 10.62056/ae890l5vt

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).