Baloo: Nearly Optimal Lookup Arguments

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

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

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: 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
History: 2022-11-10: approved; 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}
}