New Lookup Argument
Authors: rkm0959 (Gyumin Roh), Wei Dai, Mark (majabbour), Andrew He
This work started from the problems Haichen Shen and Ying Tong presented at the ETH x ZK Research Workshop in Stanford. We thank them and many others from the research workshop for discussing the base of the results below together. We also thank Yan Zhang for helping us in reviewing this document.
In this post, we present a new lookup argument and analyze its efficiency, alongside with some comparisons with the PLOOKUP.
We will fix a field \mathbb{F} with a multiplicative subgroup of order N and its generator \omega.
Denote \mathcal{L}_i(x) as the Lagrange basis polynomials where \mathcal{L}_i(\omega^j) = 1 if i = j and 0 otherwise.
Representations of Multisets
Consider an nvector \vec a = (a_0, \ldots, a_{n1}) \in \mathbb F^n with n \le N. We identify \vec a with the multiset \mathcal A = \{a_i\}_{i=0,\ldots, n 1} and consider two representations of \vec a and A:
 The standard representation of A is the polynomial
 The roots representation of A is the polynomialZ_{A}(X) = \prod_{i=0}^{n1} (X  a_i) = \prod_{i=0}^{n1} (X  A(\omega^i))\,.
 The inverse roots representation of A is the rational polynomialW_A(X) = \sum_{a \in A} \frac{1}{X  a}
New Lookup Argument
Consider two multisets A = \{a_0, a_1, \cdots, a_{N1} \} and B = \{b_0, b_1, \cdots , b_{n1}\}.
If the size of A is less than N, we can pad it with some values in B.
Claim: Every element of \mathcal A is in \mathcal B iff R = Z_B \cdot W_A is a polynomial of degree less than n.
Proof sketch: Suppose there is some element of \mathcal A, say a, not in \mathcal B, then clearly there is a term (X  a)^{1} in the summands of the expression for R(X), which means that R(X) is not a low degree polynomial. On the other hand, suppose every element of \mathcal A is in \mathcal B, then it is straight forward to check that Z_B \cdot W_A is a polynomial of degree n  1.
Therefore, we can create a lookup argument that checks a single polynomial identity
We explicitly write out the entire lookup protocol. We assume that the lookup table B is fixed and known by both prover and verifier. Weâ€™ll first discuss the interactive version.
We assume that Z_B and its KZG commitment are precomputed.
Step 1
The prover computes the standard representation of A and commits to it as [A(x)]_1.
The prover also computes R(X) and commits to it as [R(x)]_1.
Step 2
The verifier sends the random challenge \gamma.
Step 3
The prover computes y = W_A(\gamma). To prove this, we use a grand product argument.
The grand product polynomial Z is constructed as
Here, we see that our recursive formula for Z(\omega^k) gives
for each 0 \le k < N and the final check forces
which is what we wanted.
The quotient polynomial we want is
which is degree at most N.
The prover sends y, the KZG commitment of Z(X), KZG commitment of t(X), and the evaluation for Z_B(\gamma).
Step 4
The verifier sends another challenge \delta for the grand product argument.
Step 5
The prover sends the KZG evaluation proofs of Z_B(\gamma), R(\gamma), Z(\delta), Z(\omega \delta), t(\delta), A(\delta). Here, R(\gamma) = Z_B(\gamma) y should be checked.
Mallerâ€™s optimization and the protocol from 2020/081 can be used here.
Step 6
The verifier checks the quotient polynomial identities with the given KZG proofs.
For the noninteractive version, the challenges are computed via FiatShamir.
Prover Time
We will consider a single FFT evaluating a polynomial with degree less than N at N roots of unity as â€śa single FFTâ€ť. This means that multiplying two polynomials of degree no more than N, which requires evaluating both at $2N$th roots of unity, multiplying the evaluations and turning it back to coefficient form, requires 6 FFTs.
We assume that the KZG commitments to all Lagrange basis are precomputed, which can be done in \mathcal{O}(N \log N) time by algorithms, for example, [FK20].
First, we explain that the computation of R(X) takes \mathcal{O}(n \log^2 n) field operations. We note that multiplying n linear polynomials can be done with Divide & Conquer along with FFT in \mathcal{O}(n \log^2 n).
Therefore, we can precompute Z_B(X) in \mathcal{O}(n \log^2 n). Also, the sum
can be represented in \mathcal{O}(N) time
where cnt_i is the number of times b_i appear in A.
This can be written as a quotient of two polynomials of degree no more than n in \mathcal{O}(n \log^2 n) field operations with a similar Divide & Conquer and FFT.
Letâ€™s take a look at the computations of prover.
The prover needs to compute
 KZG commitment to A(X)
 Assuming that A is given, this is a MSM of size N.
 They need to compute A(X) itself, which is one FFT.
 KZG commitment to R(X)
 Computing R(X) takes \mathcal{O}(n \log^2 n) field operations.
 Computing the KZG commitment is a MSM of size n.
 KZG commitment to Z(X)
 Computing the KZG commitment is a MSM of size N.
 Computing Z itself is one FFT as well.
 KZG commitment to t(X)
 Computation of t(X) requires one polynomial multiplication between Z(\omega X)  Z(X) and \gamma  A(X), both of degree no more than N, 6 FFTs.
 After computing t(X), the rest is a multiscalarmultiplication of size N.
The prover also needs to provide KZG proofs to R(\gamma), Z_B(\gamma), Z(\delta), Z(\omega \delta), and
at X = \delta, which should evaluate to 0.
These four distinct polynomials are all of degree at most N. Using the protocol from https://eprint.iacr.org/2020/081.pdf, we need to send
 2 G_1 elements to verifier
 at most 2N+1 G_1exponentiation
 7 G_1exponentiation and 2 pairings by verifier
All in all, the prover cost is
 3 MSMs of size N and 1 MSM of size n
 8 FFTs of size N
 one Divide & Conquer + FFT computation of cost \mathcal{O}(n \log^2 n) field operations
 one protocol of 2020/081 with degree no more than N over 4 distinct polys
The proof consists of [A(x)]_1, [R(x)]_1, y, [Z(x)]_1, Z_B(\gamma), [t(X)]_1 and the proofs from the polynomial evaluation protocol in 2020/081 (2 G_1 elements)
 which is 6 G_1 elements and 2 field elements.
A quick look back at PLOOKUP (PLONKUP Version)
In PLONKUP, with \mathbb{F} of order N and roots of unity \omega, there are
 The query vector f = (f_0, \cdots , f_{N1})
 The table vector t = (t_0, \cdots , t_{N1})
and s = (f, t) with s sorted w.r.t. t. Note that the query/tables are both size N.
In PLONKUP, the prover divides s into alternating halves h_1, h_2, i.e.
 h_1 = (s_0, s_2, \cdots , s_{2N2})
 h_2 = (s_1, s_3, \cdots , s_{2N1})
The grand product here is, with random \epsilon, \delta,
Therefore, the prover needs to KZG commit f, h_1, h_2. The prover also needs to commit to the grand product polynomial and the quotient polynomial.
The prover needs to compute
 KZG commitments to f(X), h_1(X), h_2(X)
 Each of these can be computed with a MSM of size N
 You also need an FFT to compute each polynomials.
 KZG commitment to Z(X)
 The KZG commitment calculations is a MSM of size N
 You also need an FFT to compute the polynomials.
 KZG commitment to q(X)
 This requires two multiplications of three polynomials of degree N, and the KZG commitment requires two multiscalarmultiplication of size N.
 This requires 32 FFTs (there may be better ways) and two MSM of size N.
 KZG proofs to f(\delta), t(\delta), t(\omega \delta), Z(\omega \delta), h_1(\omega \delta), h_2(\delta) and the linearization polynomial.
 These are all degree at most N, and the protocol from 2020/081 applies.
 There are 6 different polynomials, and two evaluation points.
Again, note that f, h_1, h_2, Z has degree \approx N and q has degree \approx 2N.
All in all, the prover cost is
 6 MSMs of size N
 36 FFTs of size N
 one protocol of 2020/081 with degree no more than N over 6 distinct polys
The proof consists of [f(x)]_1, [h_1(x)]_1, [h_2(x)], [Z(x)]_1, [q_{low}(X)]_1, [q_{high}(X)]_1, [t(X)]_1 and the proofs from the polynomial evaluation protocol in 2020/081 (2 G_1 elements)
 which is 9 G_1 elements
Therefore, the new lookup argument may be more efficient in the prover side in the regime N \gg n, i.e. where the \mathcal{O}(n \log^2 n) doesnâ€™t become the bottleneck.
A quick look back at Halo2â€™s Lookup
https://zcash.github.io/halo2/design/provingsystem/lookup.html
Here, with queries A and lookup table S, they provide a permutation A' and S' and check if
along with the permutation check with grand product
Therefore, we need to do (assuming S is fixed)
 KZG commitments to A, A', S'
 each of them require MSM of size N and FFT of size N
 KZG commitment to Z
 it requires an MSM of size N and FFT of size N
 Quotient Polynomial
 it requires one multiplication of two polynomials of degree less than N, and two multiplication of three polynomials less than N, so 6 + 16 * 2 = 38 FFTs. The KZG commitment requires two MSM of size N.
Therefore, it requires at least 6 MSM of size N and 42 FFTs of size N.
Supporting Vector Lookups
Assume that there is a size n table of length t vectors. Weâ€™ll denote it B_0, B_1, \cdots, B_{t1}.
We wish to prove that (A_{0, i}, A_{1, i}, \cdots , A_{t1, i}) = (B_{0, j}, B_{1, j}, \cdots, B_{t1, j}) for some j for all i.
Unlike the standard representation, the roots representation is not linear if we combine each columns with a random linear combination. Therefore, to compute the equivalent value for Z_B(\gamma), we would need another grand product argument.
We would need to consider
and commit to it.
To prove y = W_A(\gamma), the grand product polynomial Z is constructed as
The prover now also needs to prove and compute w = Z_B(\gamma). This is also done with a grand product. The grand product polynomial Z^* is constructed as
The rest is similar to the original protocol, but we donâ€™t need to open Z_B(\gamma).
Prover Time in Vector Lookup Case
Here, we will simply consider the variant where the prover also needs to provide proof for the evaluation of Z_B(\gamma) with a grand product argument.
We will assume that N \gg n, as this is the case where our new lookup is expected to outperform PLONKUP.
The additional element is the grand product polynomial Z^*, and the quotient polynomial requiring
 Computing Z^* requires one FFT and one MSM of size N.

t still has degree of at most N, and 6 additional FFT are required.
 there are some division by linear polynomials
 We need Z^*(\delta), Z^*(\omega \delta)'s proofs as well, but no need for Z_B(\gamma)'s proof.
 The number of polynomials for 2020/081 remains the same
All in all, the prover cost is
 4 MSMs of size N and 1 MSM of size n
 15 FFT of size N
 one Divide & Conquer + FFT computation of cost \mathcal{O}(n \log^2 n) field operations
 one protocol of 2020/081 with degree no more than N over 4 distinct polys
The proof consists of [A(x)]_1, [R(x)]_1, y, w, [Z(x)]_1, [Z^*(x)]_1, [t(X)]_1 and the proofs from the polynomial evaluation protocol in 2020/081 (2 G_1 elements)
 which is 7 G_1 elements and 2 field elements.
This is also still better than PLONKUP if N \gg n.
Appendix: Alternate Derivation of New Lookup Argument
For distinct a_i and e_i \ge 1, if
it can be proved that
and therefore
Now looking at the lookup argument, the claim that a \in B for each a \in A is equivalent to
which is equivalent to
i.e.
is a polynomial. This is the base of our new lookup argument.