notes - September 27, 2023

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.

As last time, let’s have:

We need to prove that all elements of

are in
We can pad
with repetitions of the last element:

The original lookup doesn’t permute

as halo2 does to have the same values as
at the positions where the value in
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

and
And let’s completely ignore that
has to be a power of
And let’s assume the length of
and
is the same.

Let’s observe:

And:

When

we have:

Let

be the sorted version of the concatenation of
and

So:

Let’s have:

It holds that

if and only if
is
sorted by
That means
if and only if

The proof of the equivalence is in the paper, but the intuition behind is that when the element

is from
we have the element
from
such that
so
So we have a factor of
which is the same as some factor of
When
is not from
we have two factors
of
that appear in

What was at first surprising to me in this scheme is that we don’t need to prove that

contains some prescribed values, we just prove that the polynomial
is properly constructed (has the correct number of factors and factors of the correct form), but nothing about its values (we prove nothing about
). It follows from the equivalence above that if
we have

To encode the values

into a polynomial, we actually need two polynomials because there are
values and we only have
that can be used to encode the values.

So we construct

and
such that:

Note that

and
This is needed, otherwise one factor is missing.

Now we construct for

:

It needs to hold:

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

needs to be
so that we have the starting point for the next check (polynomial
is constructed properly).

Polynomial z is constructed properly

We need to ensure that the polynomial

is constructed properly:

Correct transition in h

We need to ensure that:

That means the last value of

is the same as the first value of
Note that
and the first value of the set is stored at

Grand product is 1

We need to ensure that the grand product is

:

Note that:

So only at

we get all the factors we need (note that, for example,
).

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