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

We present Baloo, the first protocol for lookup tables where the prover work is linear on the amount of lookups and independent of the size of the table. Baloo is built over the lookup arguments of Caulk and Caulk+, and the framework for linear relations of Rafols and Zapico. 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 prove relation with the committed element. This feature makes Baloo especially suitable for prover input-ouput relations on hash functions, and in particular to instantiate the Ethereum Virtual Machine (EVM).

Available format(s)
Cryptographic protocols
Publication info
SNARK Lookup Scalability EVM
Contact author(s)
arantxa zapico @ upf edu
ariel gabizon @ gmail com
khovratovich @ gmail com
mary maller @ ethereum org
carla rafols @ upf edu
2022-11-10: approved
2022-11-10: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.