notes - June 9, 2023

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 too but it’s much more expensive.

Imagine we have a witness

and we would like to prove that
We could write a custom gate,
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

and we have the multiplicative subgroup
We also have the polynomial
for which it holds:

We’ve observed how the prover can prove, for example, that for each

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

where

As mentioned above we could do this by proving:

But let’s pretend that

is huge and it’s totally inefficient to use the standard PLONK approach. The technique presented here is the halo2 lookup variant, not the original plookup.

For demonstration purposes, let’s say

and:

We now permute this vector to get the same values grouped together:

And we extend

with duplicates to be of the same length as
and then permute it to have the same values as
at the positions where the value in
changes. Let’s denote it by

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

The prover needs to prove that either

or
holds.

This way, the prover proves that elements in

are only elements from

Let’s say we have polynomials

and
such that:

So, the prover needs to prove:

for
This is done by dividing by the vanishing polynomial and opening the commitment as discussed last time.

If the prover then proves that

is the permutation of
and that
is the permutation of
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:

I will write a bit about the original plookup next time.

Boogie Math Newsletter

Some characters on this website might be partially or entirely fictional. You have been warned, my friend!

© 2023 Boogie Math, all rights reserved Follow us: Twitter