In 2020, plookup showed how to create lookup proofs. Proofs that some witness values are part of a lookup table. Two years later, an independent team published plonkup showing how to integrate Plookup into Plonk.
This document specifies how we integrate plookup in kimchi. It assumes that the reader understands the basics behind plookup.
We integrate plookup in kimchi with the following differences:
The following document explains the protocol in more detail
As per the Plookup paper, the prover will have to compute three vectors:
Essentially, plookup proves that all the elements in are indeed in the lookup table if and only if the following multisets are equal:
where is a new set derived by applying a "randomized difference" between every successive pairs of a vector. For example:
Note: This assumes that the lookup table is a single column. You will see in the next section how to address lookup tables with more than one column.
The equality between the multisets can be proved with the permutation argument of plonk, which would look like enforcing constraints on the following accumulator:
Note that the plookup paper uses a slightly different equation to make the proof work. I believe the proof would work with the above equation, but for simplicity let's just use the equation published in plookup:
Note: in plookup is too large, and so needs to be split into multiple vectors to enforce the constraint at every . We ignore this for now.
Kimchi uses a single lookup table at the moment of this writing; the XOR table. The XOR table for values of 1 bit is the following:
l | r | o |
---|---|---|
1 | 0 | 1 |
0 | 1 | 1 |
1 | 1 | 0 |
0 | 0 | 0 |
Whereas kimchi uses the XOR table for values of 4 bits, which has entries.
Note: the (0, 0, 0) entry is at the very end on purpose (as it will be used as dummy entry for rows of the witness that don't care about lookups).
The plookup paper handles a vector of lookups which we do not have. So the first step it to create such a table from the witness columns (or registers). To do this, we define the following objects:
Let's go over the first item in this section.
For example, the following query tells us that we want to check if
l | r | o |
---|---|---|
1, r0 | 1, r2 | 2, r1 |
The grand product argument for the lookup consraint will look like this at this point:
Not all rows need to perform queries into a lookup table. We will use a query selector in the next section to make the constraints work with this in mind.
The associated query selector tells us on which rows the query into the XOR lookup table occurs.
row | query selector |
---|---|
0 | 1 |
1 | 0 |
Both the (XOR) lookup table and the query are built-ins in kimchi. The query selector is derived from the circuit at setup time. Currently only the ChaCha gates make use of the lookups.
The grand product argument for the lookup constraint looks like this now:
where is constructed so that a dummy query () is used on rows that don't have a query.
Since we allow multiple queries per row, we define multiple queries, where each query is associated with a lookup selector.
At the moment of this writing, the ChaCha
gates all perform queries in a row. Thus, is trivially the largest number of queries that happen in a row.
Important: to make constraints work, this means that each row must make 4 queries. (Potentially some or all of them are dummy queries.)
For example, the ChaCha0
, ChaCha1
, and ChaCha2
gates will apply the following 4 XOR queries on the current and following rows:
l | r | o | - | l | r | o | - | l | r | o | - | l | r | o |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1, r3 | 1, r7 | 1, r11 | - | 1, r4 | 1, r8 | 1, r12 | - | 1, r5 | 1, r9 | 1, r13 | - | 1, r6 | 1, r10 | 1, r14 |
which you can understand as checking for the current and following row that
The ChaChaFinal
also performs (somewhat similar) queries in the XOR lookup table. In total this is 8 different queries that could be associated to 8 selector polynomials.
Associating each query with a selector polynomial is not necessarily efficient. To summarize:
ChaCha0
, ChaCha1
, and ChaCha2
gates that make queries into the XOR tableChaChaFinal
gate makes different queries into the XOR tableUsing the previous section's method, we'd have to use different lookup selector polynomials for each of the different queries. Since there's only use-cases, we can simply group them by queries patterns to reduce the number of lookup selector polynomials to .
The grand product argument for the lookup constraint looks like this now:
where is constructed as:
where, for example the first pattern for the ChaCha0
, ChaCha1
, and ChaCha2
gates looks like this:
Note:
There are two things that we haven't touched on:
The first vector is quite straightforward to think about:
What about the second vector?
The second vector is of size
That is, it contains the elements of each query vectors (the actual values being looked up, after being combined with the joint combinator, that's per row), as well as the elements of our lookup table (after being combined as well).
Because the vector is larger than the domain size , it is split into several vectors of size . Specifically, in the plonkup paper, the two halves of (which are then interpolated as and ).
Since you must compute the difference of every contiguous pairs, the last element of the first half is the replicated as the first element of the second half (), and a separate constraint enforces that continuity on the interpolated polynomials and :
which is equivalent with checking that
Since this vector is known only by the prover, and is evaluated as part of the protocol, zero-knowledge must be added to the polynomial. To do this in kimchi, we use the same technique as with the other prover polynomials: we randomize the last evaluations (or rows, on the domain) of the polynomial.
This means two things for the lookup grand product argument:
The first problem can be solved in two ways:
The snake technique rearranges into the following shape:
so that the denominator becomes the following equation:
and the snake doing a U-turn is constrained via something like
If there's an (because the table is very large, for example), then you'd have something like:
with the added U-turn constraint:
Note that at setup time, cannot be sorted as it is not combined yet. Since needs to be sorted by (in other words, not sorted, but sorted following the elements of ), there are two solutions:
We do the second one, but there is an edge-case: the combined entries can repeat.
For some such that , we might have
For example, if and , then would be one way of sorting things out. But would be incorrect.
So to recap, to create the sorted polynomials , the prover: