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 FpF_p and we have the multiplicative subgroup H={1,w,w2,...,wn1}H = \{1, w, w^2, ..., w^{n-1}\} of FpF_p. We also have the polynomial ZH(x),Z_H(x), for which it holds:

ZH(x)=0forxHZ_H(x) = 0 \; \text{for} \; x \in H

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

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

(a(1)a(ω)...a(ωn1))(b(1)b(ω)...b(ωn1))+(11...1)=(00...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(ω2)a(1) = a(\omega^2)

a(ω)=a(ω3).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 HH:

σ(1)=ω2\sigma(1) = \omega^2

σ(ω2)=1\sigma(\omega^2) = 1

σ(ω)=ω3\sigma(\omega) = \omega^3

σ(ω3)=ω\sigma(\omega^3) = \omega

σ(ωi)=ωiforotheri\sigma(\omega^i) = \omega^i \; \text{for} \; \text{other} \; i

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

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

(a(1)+β1)(a(ω)+βω)...(a(ωn1)+βωn1)(a(1)+βσ(1))(a(ω)+βσ(w))...(a(ωn1)+βσ(wn1))\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 i3i \leq 3 (as for i>4,i > 4, the factors are the same in the numerator and the denominator because we required only the equalities a(1)=a(ω2)a(1) = a(\omega^2) and a(ω)=a(ω3)a(\omega) = a(\omega^3)):

(a(1)+β1)(a(ω)+βω)(a(ω2)+βω2)(a(ω3)+βω3)(a(1)+βσ(1))(a(ω)+βσ(w))(a(ω2)+βσ(w2))(a(ω3)+βσ(w3))\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)+β1=a(ω2)+βσ(ω2)a(1) + \beta 1 = a(\omega^2) + \beta \sigma(\omega^2)

a(ω)+βω=a(ω3)+βσ(ω3)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(ωi)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:

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

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

z(ω4)=(a(1)+β1)(a(ω)+βω)(a(ω2)+βω2)(a(1)+βσ(1))(a(ω)+βσ(ω))(a(ω2)+βσ(ω2))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(ωn)=z(1)=(a(1)+β1)(a(ω)+βω)(a(ω2)+βω2)...(a(ωn2)+βωn2)(a(1)+βσ(1))(a(ω)+βσ(ω))(a(ω2)+βσ(ω2))...(a(ωn2)+βσ(ωn2))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(ω)=(a(1)+β1)(a(ω)+βω)(a(ω2)+βω2)...(a(ωn1)+βωn1)(a(1)+βσ(1))(a(ω)+βσ(ω))(a(ω2)+βσ(ω2))...(a(ωn1)+βσ(ωn1))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(ω)z(\omega) is the grand product.

And we can see that for xHx \in H:

z(xω)=z(x)(a(x)+βx)(a(x)+βσ(x))z(x\omega) = z(x) \frac{(a(x) + \beta x)}{(a(x) + \beta \sigma(x))}

Thus, for xH:x \in H:

z(xω)(a(x)+βσ(x))z(x)(a(x)+βx)=0z(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)=z(xω)(a(x)+βσ(x))z(x)(a(x)+βx)ZH(x)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.r(x): [r(x)]_1.

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

e([r(s)r¯]1,[1]2)=e([gr(s)]1,[(sχ)]2)e([r(s) - \bar r]_1, [1]_2) = e([g_{r}(s)]_1, [(s - \chi)]_2)

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

r¯=r(χ)=z(χω)(a(χ)+βσ(χ))z(χ)(a(χ)+βχ)ZH(χ)\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(ω)=1z(\omega) = 1. For this, the prover constructs the polynomial:

(z(ω)1)L1(z(\omega) - 1)L_1

where L1L_1 is a polynomial such that:

L1(w)=1L_1(w) = 1

L1(x)=0forxw,xHL_1(x) = 0 \; \text{for} \; x \neq w, x \in H

The prover then divides the polynomial (z(ω)1)L1(z(\omega) - 1)L_1 by ZHZ_H and proceeds as above for the polynomial rr.

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