Permutation argument

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

Remember, we are in the field $F_p$ and we have the multiplicative subgroup $H = \{1, w, w^2, ..., w^{n-1}\}$ of $F_p$. We also have the polynomial $Z_H(x),$ for which it holds:

$Z_H(x) = 0 \; \text{for} \; x \in H$

We observed how the prover can prove that for each $x \in H$:

$a(x) b(x) + 1 = 0$

$\begin{pmatrix} a(1) \\ a(\omega) \\ ... \\ a(\omega^{n-1}) \end{pmatrix} \begin{pmatrix} b(1) \\ b(\omega) \\ ... \\ b(\omega^{n-1}) \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \\ ... \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ ... \\ 0 \end{pmatrix}$

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

$a(1) = a(\omega^2)$

$a(\omega) = a(\omega^3).$

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 $\sigma$ for elements from $H$:

$\sigma(1) = \omega^2$

$\sigma(\omega^2) = 1$

$\sigma(\omega) = \omega^3$

$\sigma(\omega^3) = \omega$

$\sigma(\omega^i) = \omega^i \; \text{for} \; \text{other} \; i$

The function $\sigma$ determines the equalities that should hold between $a(\omega^i)$ elements and is known to both – the prover and the verifier.

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

$\frac{(a(1) + \beta 1)(a(\omega) + \beta \omega) ... (a(\omega^{n-1}) + \beta \omega^{n-1})}{(a(1) + \beta\sigma(1))(a(\omega) + \beta\sigma(w))...(a(\omega^{n-1}) + \beta\sigma(w^{n-1}))}$

Note that $ \beta$ is a challenge computed by the verifier.

Actually, let’s observe the product only for $i \leq 3$ (as for $i > 4,$ the factors are the same in the numerator and the denominator because we required only the equalities $a(1) = a(\omega^2)$ and $a(\omega) = a(\omega^3)$):

$\frac{(a(1) + \beta 1)(a(\omega) + \beta \omega) (a(\omega^2) + \beta \omega^2) (a(\omega^3) + \beta \omega^3)}{(a(1) + \beta\sigma(1))(a(\omega) + \beta\sigma(w))(a(\omega^2) + \beta\sigma(w^2)) (a(\omega^3) + \beta\sigma(w^3))}$

Note that:

$a(1) + \beta 1 = a(\omega^2) + \beta \sigma(\omega^2)$

$a(\omega) + \beta \omega = a(\omega^3) + \beta \sigma(\omega^3)$

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

It’s easy to see that when $\sigma$ 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 $a(\omega^i)$ for which $\sigma$ 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 $\sigma$ 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 $z:$

$z(\omega^2) = \frac{(a(1)+\beta 1)}{(a(1) + \beta \sigma(1))}$

$z(\omega^3) = \frac{ (a(1)+\beta 1)(a(\omega)+\beta \omega)}{ (a(1) + \beta \sigma(1))(a(\omega) + \beta \sigma(\omega))}$

$z(\omega^4) = \frac{ (a(1)+\beta 1)(a(\omega)+\beta \omega)(a(\omega^2)+\beta \omega^2)}{ (a(1) + \beta \sigma(1))(a(\omega) + \beta \sigma(\omega))(a(\omega^2) + \beta \sigma(\omega^2))}$

$...$

$z(\omega^n) = z(1) = \frac{ (a(1)+\beta 1)(a(\omega)+\beta \omega)(a(\omega^2)+\beta \omega^2)...(a(\omega^{n-2})+\beta \omega^{n-2})}{ (a(1) + \beta \sigma(1))(a(\omega) + \beta \sigma(\omega))(a(\omega^2) + \beta \sigma(\omega^2))...(a(\omega^{n-2}) + \beta \sigma(\omega^{n-2}))}$

$z(\omega) = \frac{ (a(1)+\beta 1)(a(\omega)+\beta \omega)(a(\omega^2)+\beta \omega^2)...(a(\omega^{n-1})+\beta \omega^{n-1})}{ (a(1) + \beta \sigma(1))(a(\omega) + \beta \sigma(\omega))(a(\omega^2) + \beta \sigma(\omega^2))...(a(\omega^{n-1}) + \beta \sigma(\omega^{n-1}))}$

We can see that $z(\omega)$ is the grand product.

And we can see that for $x \in H$:

$z(x\omega) = z(x) \frac{(a(x) + \beta x)}{(a(x) + \beta \sigma(x))}$

Thus, for $x \in H:$

$z(x\omega)(a(x) + \beta \sigma(x)) - z(x) (a(x) + \beta x) = 0$

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

$r(x) = \frac{z(x\omega)(a(x) + \beta \sigma(x)) - z(x) (a(x) + \beta x)}{Z_H(x)}$

The same trick is applied as described last time. The prover commits to the polynomial $r(x): [r(x)]_1.$

The verifier chooses a random challenge $\chi$ and the prover opens $r$ at $\chi$. That means the verifier checks:

$e([r(s) - \bar r]_1, [1]_2) = e([g_{r}(s)]_1, [(s - \chi)]_2)$

Note that the verifier computes $\bar r$ as:

$\bar r = r(\chi) = \frac{z(\chi\omega)(a(\chi) + \beta \sigma(\chi)) - z(\chi) (a(\chi) + \beta \chi)}{Z_H(\chi)}$

If the verification succeeds, the prover proves the grand product is constructed properly. Finally, the prover needs to prove that $z(\omega) = 1$. For this, the prover constructs the polynomial:

$(z(\omega) - 1)L_1$

where $L_1$ is a polynomial such that:

$L_1(w) = 1$

$L_1(x) = 0 \; \text{for} \; x \neq w, x \in H$

The prover then divides the polynomial $(z(\omega) - 1)L_1$ by $Z_H$ and proceeds as above for the polynomial $r$.

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