# 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 andSo:

Let’s have:

It holds that

if and only if is sorted by That means if and only ifThe 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 soWhat 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 haveTo 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

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.

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

### 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, ).