A Review of Lookup Arguments

1. Introduction

Lookup protocols are designed to handle specific operations that are challenging for SNARKs (Succinct Non-Interactive Arguments of Knowledge). Broadly speaking, these protocols enable one to prove a statement of the form:

• Given a table T={t_i​},i=0,…,N−1​ of distinct values (referred to as ‘rows’),
• and a list of lookups F={f_j​}j=0,…,m−1​ (which may occur multiple times),
• all the lookups are contained in the table, i.e., F⊆T.

In this framework, the table T is generally considered public, while the list of lookups F is treated as a private witness. One can conceptualize the table as holding all permissible values for a given variable, and the lookups as specific instances of this variable generated during the execution of a particular program. The statement being proven confirms that the variable remained within legal bounds throughout that program’s execution.

For the purposes of this discussion, it’s assumed that m<N, and in most cases m≪N, unless stated otherwise. We aim to review the evolution and variety of available lookup protocols and explore the diverse applications of proving such statements.

2. Lookup Argument Schemes

Plookup: Plookup is one of the earliest lookup protocols and is designed to prove that a committed polynomial f contains only elements from a public table t. The protocol uses auxiliary polynomials F and G to confirm this. The prover commits to polynomials h_1​ and h_2​ that represent a sorted vector s, and then responds to verifier challenges β and γ with a proof polynomial Z. The verifier checks specific identities to confirm correctness. The prover’s computational complexity is O(NlogN) field operations, and the protocol can be generalized to handle multiple tables and vector lookups.

Caulk: Caulk offers a way to prove that a committed vector cm is part of a larger committed vector C. It relies on polynomial commitments and shifts much of the computation to a preprocessing stage. This makes the prover’s work dependent on cm’s size m, not C’s size N. The prover identifies a subset C_I​ containing cm’s elements and shows C−C_I​=Z_I​(x)×H_I​(x) using KZG commitment. The protocol has a sublinear efficiency with O(mlogN) prover complexity.

Caulk+: Caulk+ refines Caulk by further reducing the prover’s computational complexity. It replaces the logN term with a more efficient divisibility check. The protocol involves computing polynomials Z_I​, C_I​, and U to show that Z_I​ divides C−C_I​ and X^n−1. It retains zero-knowledge properties by introducing blinding factors, lowering the prover complexity to O(m^2).

Baloo: Baloo extends Caulk+ by committing to a table subset in vanishing polynomial form, using quasi-linear time in the subset size. It introduces a “commit and prove” argument and a generalized Sumcheck protocol to reduce the proof to an inner product argument. The protocol is efficient and extends to multi-column lookups, offering promising applications for SNARKs like zkEVM.

Flookup: Flookup is designed to efficiently prove that the values of a committed polynomial are part of a large table. The protocol uses pairings to extract the vanishing polynomial of a relevant table subset, introducing a new polynomial IOP for proofs. After O(Nlog^2N) preprocessing, the prover operates in quasi-linear time O(mlog^2m), improving on previous quadratic prover complexities. It’s especially useful for SNARK proofs over large domains.

cq: cq utilizes the log derivative method to reduce membership proofs to rational identity checks. By precomputing “cached quotients” for quotient polynomials, it enables efficient computation for table entries. With O(NlogN) prover time and O(N) proof size, it surpasses the efficiency of Baloo and Flookup, while maintaining properties like homomorphic.

LogUp: Logup efficiently proves that a set of witness values exists in a Boolean hypercube lookup table. Using logarithmic derivatives, it converts set inclusion into a rational function equality check, requiring the prover to provide only a multiplicity function. LogUp is more efficient than multivariate Plookup variants, requiring 3–4 times fewer Oracle commitments. It also compares favorably to Plookup’s bounded multiplicity optimization for large batch sizes. The method is versatile, extending to vector-valued lookups, and adaptable for range proofs. It’s particularly relevant for SNARKs like PLONK and Aurora, and applications such as tinyRAM and zkEVM.

3. Applications

• Range Checks: Proving a number x is in the range {0,…,N-1} for N = 2^n can be done with n+1 arithmetic constraints, or a single lookup constraint checking x is in the table of all numbers in the range.
• Finite Domain Functions: Any finite domain function can be implemented with a lookup table containing all input-output pairs. This can implement complex functions like k-bit XOR more efficiently than using arithmetic constraints.
• Better XOR: Bitwise XOR can be implemented more efficiently by using zero-interleaving to combine XOR and AND results into a single table lookup. This reduces table size from 2^{2^k} to just 384kB for k=16.
• Finite State Machines: Lookup tables can encode transition tables for finite state machines. An execution trace can be proven valid by checking each (state, input, next state) transition in the table.
• zkEVM/zkVM: The lookup table can be applied to CPU and memory trace tables for real-time monitoring and validation. In CPU trace tables, the lookup table can contain valid instructions or states, helping to immediately flag unauthorized or erroneous operations. This aids in debugging and enhances security. For memory trace tables, the lookup table lists valid memory addresses and permissible operations. Each read or write is cross-referenced in real-time, ensuring data integrity and preventing unauthorized access. Both applications serve to increase system security and operational accuracy, making them valuable tools for debugging and performance optimization.

4. Conclusion

The main benefit of lookups is reducing constraint complexity for operations that are “SNARK-unfriendly” like bit operations, transitions, etc. Lookups trade off higher proof size for faster proving and verification. So in summary, lookups enable efficiently proving statements about complex functions, machine states, ranges, and more by checking membership in public tables encoding allowed values. This improves performance for non-arithmetic constraints.

5. References

1. Gabizon A, Williamson Z J. plookup: A simplified polynomial protocol for lookup tables[J]. Cryptology ePrint Archive, 2020.
2. Zapico A, Buterin V, Khovratovich D, et al. Caulk: Lookup arguments in sublinear time[C]//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022: 3121–3134.
3. Posen J, Kattis A A. Caulk+: Table-independent lookup arguments[J]. Cryptology ePrint Archive, 2022.
4. Gabizon A, Khovratovich D. flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size[J]. Cryptology ePrint Archive, 2022.
5. Zapico A, Gabizon A, Khovratovich D, et al. Baloo: Nearly optimal lookup arguments[J]. Cryptology ePrint Archive, 2022.
6. Eagen L, Fiore D, Gabizon A. cq: Cached quotients for fast lookups[J]. Cryptology ePrint Archive, 2022.
7. Haböck U. Multivariate lookups based on logarithmic derivatives[J]. Cryptology ePrint Archive, 2022.
8. A Brief History of Lookup Arguments. https://github.com/ingonyama-zk/papers/blob/main/lookups.pdf