Some ideas behind PLONK

PLONK (opens new window) stands for Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. But do not mind the incomprehensible words – PLONK is an incredibly useful cryptographic protocol.

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

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

For example, we would like to prove that for each $x \in H:$

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

That means:

$\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}.$

Let’s denote:

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

The prover needs to prove:

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

To achieve this, the prover computes the polynomial $h_v(x) = \frac{h(x)}{Z_H(x)}.$

The prover then computes commitments $[a(s)]_1,$ $[b(s)]_1,$ and $[h_v(s)]_1$ to the polynomials $a, b, \; \text{ and } \; h_v$, respectively. The prover then proves that it knows the polynomials behind the commitments. It opens the polynomials at $\chi$ (chosen by a verifier):

$\bar{a} = a(\chi)$

$\bar{b} = b(\chi)$

$\bar{h_v} = h_v(\chi)$

That means the prover proves that $a, b \; \text{ and } \; h_v$ evaluate to $\bar{a}, \bar{b}, \text{and } \bar{h_v}$ at $\chi,$ respectively. The prover provides:

$[g_a(s)]_1 \text{ where } a(x) - a(\chi) = (x-\chi)g_a(x)$

$[g_b(s)]_1 \text{ where } b(x) - b(\chi) = (x-\chi)g_b(x)$

$[g_{h_v}(s)]_1 \text{ where } h_v(x) - h_v(\chi) = (x-\chi)g_{h_v}(x)$

The verifier checks:

$e([a(s) - \bar a]_1, [1]_2) = e([g_a(s)]_1, [(s - \chi)]_2)$

$e([b(s) - \bar b]_1, [1]_2) = e([g_b(s)]_1, [(s - \chi)]_2)$

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

Note that the verifier computes $\bar{h_v}$ as follows:

$\bar{h_v} = \frac{a(\chi)b(\chi) + 1}{Z_H(\chi)}$

Why is this secure?

This will be just a bit of hand-waving (I say this too many times).

Let’s say the attacker does not know $a(x)$ and $b(x)$ such that:

$h_v(x) Z_H(x) = a(x)b(x) + 1$

Note that the equation above ensures:

$a(x)b(x) + 1 = 0 \; \text{ for } \; x \in H$

The attacker could easily take polynomials $a(x),$ $b(x)$ and define $c(x)$ such that (considering $Z_H(\chi)$ as a constant):

$c(x) Z_H(\chi) = a(x)b(x) + 1$

However, the prover needs to commit to $c(x)$ before knowing the challenge $\chi.$ That means that the prover cannot subsequently change the polynomial $c(x).$ When committing to $a(x), b(x), c(x),$ the value $Z_H(\chi)$ could be any element of $F_p,$ and the probability of the prover guessing it is negligible.

Multi-opening

What if the prover needs to prove multiple relations?

Let’s say the prover would like to prove for $x \in H:$

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

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

$a(x)^2 - b(x) + 1 = 0.$

Could opening a polynomial for each relation be avoided? Could one opening suffice?

It could and the reason, again, is probability.

Another challenge is needed for this, let’s say $\chi_1.$

Our new polynomial of interest is:

$h(x) = (a(x) b(x) + 1) + (a(x) + b(x)) \chi_1 + (a(x)^2 - b(x) + 1) \chi_1^2.$

The steps are then the same as for the single opening, but note that the verifier computes $\bar{h_v}$ as follows:

$\bar{h_v} = \frac{(a(\chi)b(\chi) + 1) + (a(\chi)+b(\chi))\chi_1 + (a(\chi)^2 - b(\chi) + 1)\chi_1^2}{Z_H(\chi)}.$

Zero-knowledge

We didn’t care about zero-knowledge above - about disclosing nothing about $a(x)$ and $b(x)$ to the verifier.

To achieve zero-knowledge we need to add random multiples of $Z_H(x)$ to the witness based polynomials ($a(x)$ and $b(x)$), such as:

$a_{new}(x) = (b_1 x + b_2)Z_H(x) + a(x)$

$b_{new}(x) = (b_3 x + b_4)Z_H(x) + b(x).$

where $b_1, b_2, b_3, \text {and } b_4$ are scalars chosen randomly from $F_p.$

Note that one very important PLONK idea is totally ignored here: the permutation argument.