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 = \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 $A$ are in $S = \{3, 4, 11, 13\}.$ We can pad $S$ with repetitions of the last element:

$S = \begin{pmatrix} 3 \\ 4 \\ 11 \\ 13 \\ 13 \\ 13 \\ 13 \\ 13 \end{pmatrix}$

The original lookup doesn’t permute $S$ as halo2 (opens new window) does to have the same values as $A_1$ at the positions where the value in $A_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\}$ and $S = \{1, 2, 5\}$. And let’s completely ignore that $n$ has to be a power of $2$. And let’s assume the length of $A$ and $S$ is the same.

Let’s observe:

$F_1 = \Pi_{i < n} (1 + \beta) (\gamma + a_i) = (1 + \beta)^3 (\gamma + 1 \beta) (\gamma + 1 \beta) (\gamma + 5 \beta)$

$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 = 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 + \beta)^3 (\gamma + 1 \beta) (\gamma + 1 \beta) (\gamma + 5 \beta) (\gamma (1 + \beta) + 1 + \beta 2) (\gamma (1 + \beta) + 2 + \beta 5)$

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

$\gamma (1 + \beta) + s_i + \beta s_{i+1} = (1 + \beta) (\gamma + s_i).$

Let $C = \{c_1, c_2, c_3, c_4, c_5, c_6\}$ be the sorted version of the concatenation of $A$ and $S$.

So:

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

Let’s have:

$G = \Pi_{i < 2n} (\gamma (1 + \beta) + c_i + \beta c_{i+1})$

It holds that $F = G$ if and only if $C = \{c_1, c_2, c_3, c_4, c_5, c_6\}$ is $A \cup S$ sorted by $S$. That means $F = G$ if and only if $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 $c_i$ is from $A,$ we have the element $c_{i+1}$ from $S$ such that $c_i = c_{i+1},$ so

$\gamma (1 + \beta) + c_i + \beta c_{i+1} = (1 + \beta) (\gamma + c_i).$

So we have a factor of $F_1$ which is the same as some factor of $G$. When $c_i$ is not from $A,$ we have two factors

$(\gamma (1 + \beta) + c_{i-1} + \beta c_i)(\gamma (1 + \beta) + c_i + \beta c_{i+1})$

of $G$ that appear in $F_2.$

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

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

So we construct $h_1$ and $h_2$ such that:

$h_1(\omega) = c_1$

$h_1(\omega^2) = c_2$

$h_1(\omega^3) = c_3$

$h_1(\omega^{n+1}) = h_1(1) = c_4$

$h_2(\omega) = c_4$

$h_2(\omega^2) = c_5$

$h_2(\omega^3) = c_6$

Note that

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

and

$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 $2 \leq j \leq n$:

$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(\omega) = 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(\omega)$ needs to be $1$ so that we have the starting point for the next check (polynomial $z$ is constructed properly).

Polynomial z is constructed properly

We need to ensure that the polynomial $z$ is constructed properly:

$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 + \beta) (\gamma + a(x)) (\gamma (1 + \beta) + s(x) + s(\omega x) \beta).$

Correct transition in h

We need to ensure that:

$h_1(1) = h_2(\omega).$

That means the last value of $h_1$ is the same as the first value of $h_2$. Note that $\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 $1$:

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

Note that:

$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(\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 $\omega^{n+1}$ we get all the factors we need (note that, for example, $h_1(\omega^{n+1}) = c_4$).