Baloo: Nearly Optimal Lookup Arguments

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

Paper 2022/1565 Original: eprint.iacr.org/2022/1565 ↗

Baloo: Nearly Optimal Lookup Arguments

Arantxa Zapico

Ariel Gabizon

Dmitry Khovratovich

Mary Maller

Carla Ràfols

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: Preprint.
History: 2025-07-08: last updated; 2022-11-10: published
Short URL: https://ia.cr/2022/1565
License: https://creativecommons.org/licenses/by/4.0/

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}
}