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

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 byAt positions denoted by "...", it can be any value from

The prover needs to prove that either

This way, the prover proves that elements in

are only elements fromLet’s say we have polynomials

and such that:So, the prover needs to prove:

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.