Paper 2022/1565
Baloo: Nearly Optimal Lookup Arguments
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).
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published by the IACR in CIC 2025
- Keywords
- SNARKLookupScalabilityEVM
- Contact author(s)
-
arantxa zapico @ upf edu
ariel gabizon @ gmail com
khovratovich @ gmail com
mary maller @ ethereum org
carla rafols @ upf edu - History
- 2025-07-08: revised
- 2022-11-10: received
- See all versions
- Short URL
- https://ia.cr/2022/1565
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1565, author = {Arantxa Zapico and Ariel Gabizon and Dmitry Khovratovich and Mary Maller and Carla Ràfols}, title = {Baloo: Nearly Optimal Lookup Arguments}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/1565}, year = {2022}, url = {https://eprint.iacr.org/2022/1565} }