[Resource Topic] 2022/1565: Baloo: Nearly Optimal Lookup Arguments

Welcome to the resource topic for 2022/1565

Baloo: Nearly Optimal Lookup Arguments

Authors: Arantxa Zapico, Ariel Gabizon, Dmitry Khovratovich, Mary Maller, Carla Ràfols


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

ePrint: https://eprint.iacr.org/2022/1565

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .