Paper 2022/1565

Baloo: Nearly Optimal Lookup Arguments

Arantxa Zapico, Universitat Pompeu Fabra
Ariel Gabizon, Zeta Function Technologies
Dmitry Khovratovich, Ethereum Foundation
Mary Maller, Ethereum Foundation
Carla Ràfols, Universitat Pompeu Fabra
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.