Plookups

Last time I wrote about the purpose of lookups and specifically about the Halo2 lookups. However, the first scheme for checking that the values of a committed polynomial are contained in some table was introduced in plookup: A simplified polynomial protocol for lookup tables (opens new window).

As last time, let’s have:

A=(a(1)a(ω)a(ω2)a(ω3)a(ω4)a(ω5)a(ω6)a(ω7))=(313311131333)A = \begin{pmatrix} a(1) \\ a(\omega) \\ a(\omega^2) \\ a(\omega^3) \\ a(\omega^4) \\ a(\omega^5) \\ a(\omega^6) \\ a(\omega^7) \end{pmatrix} = \begin{pmatrix} 3 \\ 13 \\ 3 \\ 11 \\ 13 \\ 13 \\ 3 \\ 3 \end{pmatrix}

We need to prove that all elements of AA are in S={3,4,11,13}.S = \{3, 4, 11, 13\}. We can pad SS with repetitions of the last element:

S=(34111313131313)S = \begin{pmatrix} 3 \\ 4 \\ 11 \\ 13 \\ 13 \\ 13 \\ 13 \\ 13 \end{pmatrix}

The original lookup doesn’t permute SS as halo2 (opens new window) does to have the same values as A1A_1 at the positions where the value in A1A_1 changes. Instead, it uses the following trick.

I will make a few simplifications here, this is just a sketch, not the whole protocol. Also, for easier demonstration, let’s have A={1,1,5}A = \{1, 1, 5\} and S={1,2,5}S = \{1, 2, 5\}. And let’s completely ignore that nn has to be a power of 22. And let’s assume the length of AA and SS is the same.

Let’s observe:

F1=Πi<n(1+β)(γ+ai)=(1+β)3(γ+1β)(γ+1β)(γ+5β)F_1 = \Pi_{i < n} (1 + \beta) (\gamma + a_i) = (1 + \beta)^3 (\gamma + 1 \beta) (\gamma + 1 \beta) (\gamma + 5 \beta)

F2=Πi<n(γ(1+β)+si+βsi+1)=(γ(1+β)+1+β2)(γ(1+β)+2+β5)F_2 = \Pi_{i < n} (\gamma (1 + \beta) + s_i + \beta s_{i+1}) = (\gamma (1 + \beta) + 1 + \beta 2) (\gamma (1 + \beta) + 2 + \beta 5)

And:

F=F1F2=Πi<n(1+β)(γ+ai)Πi<n(γ(1+β)+si+βsi+1)=F = F_1 F_2 = \Pi_{i < n} (1 + \beta) (\gamma + a_i) \Pi_{i < n} (\gamma (1 + \beta) + s_i + \beta s_{i+1}) =

=(1+β)3(γ+1β)(γ+1β)(γ+5β)(γ(1+β)+1+β2)(γ(1+β)+2+β5)= (1 + \beta)^3 (\gamma + 1 \beta) (\gamma + 1 \beta) (\gamma + 5 \beta) (\gamma (1 + \beta) + 1 + \beta 2) (\gamma (1 + \beta) + 2 + \beta 5)

When si=si+1s_i = s_{i+1} we have:

γ(1+β)+si+βsi+1=(1+β)(γ+si).\gamma (1 + \beta) + s_i + \beta s_{i+1} = (1 + \beta) (\gamma + s_i).

Let C={c1,c2,c3,c4,c5,c6}C = \{c_1, c_2, c_3, c_4, c_5, c_6\} be the sorted version of the concatenation of AA and SS.

So:

C={1,1,1,2,5,5}C = \{1, 1, 1, 2, 5, 5\}

Let’s have:

G=Πi<2n(γ(1+β)+ci+βci+1)G = \Pi_{i < 2n} (\gamma (1 + \beta) + c_i + \beta c_{i+1})

It holds that F=GF = G if and only if C={c1,c2,c3,c4,c5,c6}C = \{c_1, c_2, c_3, c_4, c_5, c_6\} is ASA \cup S sorted by SS. That means F=GF = G if and only if C={1,1,1,2,5,5}C = \{1, 1, 1, 2, 5, 5\}.

The proof of the equivalence is in the paper, but the intuition behind is that when the element cic_i is from A,A, we have the element ci+1c_{i+1} from SS such that ci=ci+1,c_i = c_{i+1}, so

γ(1+β)+ci+βci+1=(1+β)(γ+ci).\gamma (1 + \beta) + c_i + \beta c_{i+1} = (1 + \beta) (\gamma + c_i).

So we have a factor of F1F_1 which is the same as some factor of GG. When cic_i is not from A,A, we have two factors

(γ(1+β)+ci1+βci)(γ(1+β)+ci+βci+1)(\gamma (1 + \beta) + c_{i-1} + \beta c_i)(\gamma (1 + \beta) + c_i + \beta c_{i+1})

of GG that appear in F2.F_2.

What was at first surprising to me in this scheme is that we don’t need to prove that CC contains some prescribed values, we just prove that the polynomial GG is properly constructed (has the correct number of factors and factors of the correct form), but nothing about its values (we prove nothing about cic_i). It follows from the equivalence above that if F=G,F = G, we have AS.A \subseteq S.

To encode the values cic_i into a polynomial, we actually need two polynomials because there are 2n2n values and we only have ω,ω2,...,ωn\omega, \omega^2, ..., \omega^n that can be used to encode the values.

So we construct h1h_1 and h2h_2 such that:

h1(ω)=c1h_1(\omega) = c_1

h1(ω2)=c2h_1(\omega^2) = c_2

h1(ω3)=c3h_1(\omega^3) = c_3

h1(ωn+1)=h1(1)=c4h_1(\omega^{n+1}) = h_1(1) = c_4

h2(ω)=c4h_2(\omega) = c_4

h2(ω2)=c5h_2(\omega^2) = c_5

h2(ω3)=c6h_2(\omega^3) = c_6

Note that

ωn+1=1\omega^{n+1} = 1

and

h1(ωn+1)=h1(1)=h2(ω1)=cn+1.h_1(\omega^{n+1}) = h_1(1) = h_2(\omega^1) = c_{n+1}.

This is needed, otherwise one factor is missing.

Now we construct for 2jn2 \leq j \leq n:

z(ωj)=Πi<j(1+β)(γ+a(ωi))Πi<j(γ(1+β)+s(ωi)+s(ωi+1)β)Πi<j(γ(1+β)+h1(ωi)+h1(ωi+1)β)Πi<j(γ(1+β)+h2(ωi)+h2(ωi+1)β)z(\omega^j) = \frac{\Pi_{i < j}(1 + \beta) (\gamma + a(\omega^i)) \Pi_{i < j}(\gamma (1 + \beta) + s(\omega^i) + s(\omega^{i+1}) \beta)}{\Pi_{i < j}(\gamma (1 + \beta) + h_1(\omega^i) + h_1(\omega^{i+1}) \beta) \Pi_{i < j}(\gamma (1 + \beta) + h_2(\omega^i) + h_2(\omega^{i+1}) \beta) }

It needs to hold:

z(ω)=1z(\omega) = 1

z(ωn+1)=z(1)=1.z(\omega^{n+1}) = z(1) = 1.

Note that the concept of the proof is the same as in the permutation argument. We need to prove the following relations.

z(ω) is 1

z(ω)z(\omega) needs to be 11 so that we have the starting point for the next check (polynomial zz is constructed properly).

Polynomial z is constructed properly

We need to ensure that the polynomial zz is constructed properly:

z(ωx)(γ(1+β)+h1(x)+h1(ωx)β)(γ(1+β)+h2(x)+h2(ωx)β)=z(\omega x) (\gamma (1 + \beta) + h_1(x) + h_1(\omega x) \beta) (\gamma (1 + \beta) + h_2(x) + h_2(\omega x) \beta) =

=z(x)(1+β)(γ+a(x))(γ(1+β)+s(x)+s(ωx)β).= z(x) (1 + \beta) (\gamma + a(x)) (\gamma (1 + \beta) + s(x) + s(\omega x) \beta).

Correct transition in h

We need to ensure that:

h1(1)=h2(ω).h_1(1) = h_2(\omega).

That means the last value of h1h_1 is the same as the first value of h2h_2. Note that ωn+1=1\omega^{n+1} = 1 and the first value of the set is stored at ω.\omega.

Grand product is 1

We need to ensure that the grand product is 11:

z(ωn+1)=z(1)=1.z(\omega^{n+1}) = z(1) = 1.

Note that:

z(ω2)=(a(ω1)+a(ω2)β)(s(ω1)+s(ω2)β)(h1(ω1)+h1(ω2)β)(h2(ω1)+h2(ω2)β)z(\omega^2) = \frac{(a(\omega^1) + a(\omega^2) \beta) (s(\omega^1) + s(\omega^2) \beta)}{(h_1(\omega^1) + h_1(\omega^{2}) \beta) (h_2(\omega^1) + h_2(\omega^{2}) \beta)}

........

z(ωn)=(a(ω1)+a(ω2)β)(s(ω1)+s(ω2)β)(a(ωn1)+a(ωn)β)(s(ωn1)+s(ωn)β)(h1(ω1)+h1(ω2)β)(h2(ω1)+h2(ω2)β)(h1(ωn1)+h1(ωn)β)(h2(ωn1)+h2(ωn)β).z(\omega^n) = \frac{(a(\omega^1) + a(\omega^2) \beta) (s(\omega^1) + s(\omega^2) \beta) \cdot \cdot \cdot (a(\omega^{n-1}) + a(\omega^n) \beta) (s(\omega^{n-1}) + s(\omega^n) \beta)}{(h_1(\omega^1) + h_1(\omega^{2}) \beta) (h_2(\omega^1) + h_2(\omega^{2}) \beta) \cdot \cdot \cdot (h_1(\omega^{n-1}) + h_1(\omega^{n}) \beta) (h_2(\omega^{n-1}) + h_2(\omega^{n}) \beta)}.

So only at ωn+1\omega^{n+1} we get all the factors we need (note that, for example, h1(ωn+1)=c4h_1(\omega^{n+1}) = c_4).