# 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 fromThe 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 ):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 polynomialNote that multi-opening can be used to optimize the proof.