Halo2 lookups

Lookups allow us to check whether a particular witness value is an element of some set. Such a check can be done using PLONK (opens new window) too but it’s much more expensive.

Imagine we have a witness $x$ and we would like to prove that $x \in \{0, 1, 2, 3, 4\}.$ We could write a custom gate, $x(x-1)(x-2)(x-3)(x-4) = 0,$ using PLONK, but this becomes inefficient when the set is big (the bigger the degree of the gate, the slower the protocol).

Let’s see an example. As usual, we are in the field $F_p$ and we have the multiplicative subgroup $H = \{1, w, w^2, ..., w^{n-1}\} \; \text{of} \; F_p$. We also have the polynomial $Z_H(x),$ for which it holds:

$Z_H(x) = 0 \; \text{for} \; x \in H$

We’ve observed how the prover can prove, for example, that for each $x \in H$:

$a(x) b(x) + 1 = 0$

$\begin{pmatrix} a(1) \\ a(\omega) \\ ... \\ a(\omega^{n-1}) \end{pmatrix} \begin{pmatrix} b(1) \\ b(\omega) \\ ... \\ b(\omega^{n-1}) \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \\ ... \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ ... \\ 0 \end{pmatrix}.$

But let’s say we also want to prove that:

$a(x) \in S \; \text{for} \; \text{all} \; x \in H$

where

$S = \{3, 4, 11, 13\}$

As mentioned above we could do this by proving:

$(a(x) - 3) (a(x) - 4) (a(x) - 11) (a(x) - 13) = 0 \; \text{for} \; \text{all} \; x \in H$

But let’s pretend that $S$ is huge and it’s totally inefficient to use the standard PLONK approach. The technique presented here is the halo2 (opens new window) lookup variant, not the original plookup (opens new window).

For demonstration purposes, let’s say $n = 8$ and:

$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 now permute this vector to get the same values grouped together:

$A_1 = \sigma(A) = \begin{pmatrix} 3 \\ 3 \\ 3 \\ 3 \\ 11 \\ 13 \\ 13 \\ 13 \end{pmatrix}$

And we extend $S$ with duplicates to be of the same length as $A_1$ and then permute it to have the same values as $A_1$ at the positions where the value in $A_1$ changes. Let’s denote it by $S_1$:

$S_1 = \begin{pmatrix} 3 \\ ... \\ ... \\ ... \\ 11 \\ 13 \\ ... \\ ... \end{pmatrix}.$

At positions denoted by "...", it can be any value from $S$.

The prover needs to prove that either

$A_1[i] = S_1[i]$

or

$A_1[i] = A_1[i-1]$

holds.

This way, the prover proves that elements in $A_1$ are only elements from $S$.

Let’s say we have polynomials $A'$ and $S'$ such that:

$A'(\omega^i) = A_1[i]$

$S'(\omega^i) = S_1[i]$

So, the prover needs to prove:

$(A'(x) - S'(x))(A'(x) - A'(\omega^{-1} x)) = 0$

for $x \in H$. This is done by dividing by the vanishing polynomial and opening the commitment as discussed last time.

If the prover then proves that $A_1$ is the permutation of $A$ and that $S_1$ is the permutation of $S,$ the prover is done. This can be achieved using the same approach (grand product) as for the permutation arguments. The grand product in this case would contain the elements:

$\frac{(A'(x) + \beta) (S'(x) + \gamma)}{(A(x) + \beta) (S(x) + \gamma)}.$

I will write a bit about the original plookup (opens new window) next time.