notes - May 15, 2023

Permutation argument




There’s one very important idea in PLONK that I didn’t mention last time – the permutation argument.

Remember, we are in the field

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

We observed how the prover can prove that for each

But sometimes the prover needs to prove additional relations, like:

There is a very efficient way to do this, and it’s called a permutation argument. Below is the basic idea of it.

Let’s define the function

for elements from

The function

determines the equalities that should hold between
elements and is known to both – the prover and the verifier.

Let’s now observe the product (called the grand product):

Note that

is a challenge computed by the verifier.

Actually, let’s observe the product only for

(as for
the factors are the same in the numerator and the denominator because we required only the equalities
and
):

Note that:

We can see that these factors cancel out each other too.

It’s easy to see that when

equalities hold, the grand product is 1. That’s because the same factors appear in the numerator and the denominator.

The other way around, there is only a tiny probability that the prover can make up

for which
equalities don’t hold, but such a product is still 1.

So, if the prover can prove that the grand product is 1, it will prove that

equalities hold. To prove this, the prover needs to prove that the grand product is properly constructed and that it’s 1.

Let’s construct the polynomial

We can see that

is the grand product.

And we can see that for

Thus, for

Now, to prove that the above equation holds, we observe the following polynomial:

The same trick is applied as described last time. The prover commits to the polynomial

The verifier chooses a random challenge

and the prover opens
at
That means the verifier checks:

Note that the verifier computes

as:

If the verification succeeds, the prover proves the grand product is constructed properly. Finally, the prover needs to prove that

For this, the prover constructs the polynomial:

where

is a polynomial such that:

The prover then divides the polynomial

by
and proceeds as above for the polynomial

Note that multi-opening can be used to optimize the proof.

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