PLONK

In this note we describe PLONK, a recent zero-knowledge proof system. The goal is to walk through the scheme step by step and explain the cryptographic primitives at play.

Arithmetization

The arithmetization a program consists in expressing a program as a sequence of constraint which have a simple mathematic form. There are lots of ways to do this, but in this post we will look at a variation of Rank 1 Constraint System (R1CS).

Namely, the

$i-th$ constraint binds variables

$(w_i)$ by relations of this form:

$$\begin{array}{r}(q_L{)}_i{w}_{i_a}+(q_R{)}_i{w}_{i_b}+(q_M{)}_i{w}_{i_a}{w}_{i_b}+d_i=(q_c{)}_i{w}_{i_c}\end{array}$$

Any instance of NP-complete problem can be represented as a system of constraints of this sort. For instance the function

$f(x):x\to x^3$ can be expressed as:

$$\begin{array}{r}x\times x=w_0\\ w_0\times x=y\end{array}$$

$w_0$ is called an intermediate variable, because it's neither part of the input set {

$x$} nor the output set {

$y$}.

This constraint system has an intuitive matrice representation. We note

$q_L,q_R,q_M,d$ the vectors

$(q_L{)}_i,(q_R{)}_i,(q_M{)}_i,(d_i)$ and

$w$ the vector

$(w_i)$.

There are pseudo permutation matrices

$A,B,C$ (meaning that

$A,B,C$ have exactly one non zero entry per row, equal to

$1$), such that the arithmetization can be expressed as

$$q_L\circ (Aw)+q_R\circ (Bw)+q_M\circ (Aw\circ Bw)+d=q_c\circ (Cw)$$ where

$\circ$ denotes the entrywise product.

Our function

$f(x):x\to x^3$ can be represented using

$3$ variables

$x,w_0,y$ and

$3$ matrices, in the following way:

$$\left(\begin{array}{ccc}1& 0& 0\\ 1& 0& 0\end{array}\right)\left(\begin{array}{c}x\\ w_0\\ y\end{array}\right)\circ \left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\end{array}\right)\left(\begin{array}{c}x\\ w_0\\ y\end{array}\right)=\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\end{array}\right)\left(\begin{array}{c}x\\ w_0\\ y\end{array}\right)$$

Here

$q_L=q_R=d=0,q_M=q_c=(1,1{)}^t$, and

$A=\left(\begin{array}{ccc}1& 0& 0\\ 1& 0& 0\end{array}\right)$,

$B=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\end{array}\right)$,

$C=\left(\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\end{array}\right)$

The number of lines in the matrices

$A,B,C$, equal to the size of

$q_M,q_c,q_L,q_R,d$, correspond to the number of constraints.

If

$y$ was a public input, the role of a "prover" would be to find

$x$ such that

$x^3=y$, that is find

$x,w_0$ such that the equality above holds.

If one replaces

$f$ by a more complicated function, like SHA-

$256$, one would have a lot more variables

$w_i$ and the R1CS would be much more complicated. Solving the corresponding constraint system would boil down to finding

$x$ such that SHA-

$256(x)=y$: it's the job that the prover has to do, and it's supposedly impossible to do unless the prover actually knows

$x$.

For the next sections,

$p$ is a big prime number, we place ourselves in a finite field

${\mathbf{F}}_p$ of high characteristic

$p$, and the variables

$(w_i)$, the matrices

$(a_{ij}),(b_{ij}),(c_{ij})$ all live in

${\mathbf{F}}_p$.

The cryptographic toolbox

We describe fundamental tools that are used in most flavors of snarks, especially for the succintness part.

Schwartz Zippel lemma

The first tool is the Schwartz-Zippel lemma:

Take a non zero polynomial

$Q$ of degree

$d$<<

$p$ in

${\mathbf{F}}_p[X_1,\dots ,X_n]$. If one picks randomly

$\tau \in {\mathbf{F}}_p^n$, then

$Q(\tau )$, is almost surely not zero.

In practice, with the parameters chosen for crypto, you can translate "almost surely" by "surely". The probability that

$Q$ is not

$0$ is actually at most

$d/p$, and for cryptographic purposes

$p$ is typically a

$256$ bits number, while

$d$ ranges at most in the billion (about

$30$ bits number).

To justify this lemma, we proceed by induction on

$n$, the number of variables. For

$n=1$, we know that on

$F_p[X]$, a non zero polynomial

$P$ of degree

$d$ has at most

$d$ zeros, so sampling

$\tau$ in the set of zeros of

$P$ happens with a probability of at most

$d/p$. Now for

$n>1$, write

$P$, a non zero

$n$-variate polynomial, as

$P=\sum _{i\le d}{P}_i(X_1,\dots ,X_{n-1})X_n^i$, with

$P_i$ of degree at most

$d-i$. Let

$i_0$ the largest

$i$ such that

$P_i\ne 0$. Let

$({\tau }_1,\dots ,{\tau }_{n-1},\mu )=(\tau ,\mu )\in {\mathbf{F}}_p^n$ be a random element. Either

$P_i(\tau )=0$ for all

$i$, which by induction happens with probability

$\frac{d}{p}\times \frac{d-1}{p}\times \cdots \times \frac{d-i_0}{p}\le \frac{d-i_0}{p}$ and then

$P(\tau ,\mu )=0$ no matter

$\mu$, or there is a

$i$ such that

$P_i(\tau )\ne 0$, which happens with a probability bounded by

$1$, and

$P^{\prime }=\sum _{i\le d}{P}_i(\tau )X_n^i$ is a univariate polynomial of degree at most

$i_0$, so by the case

$n=1$ the probability that

$P^{\prime }(\mu )=0$ is less than

$\frac{i_0}{p}$. Averaging the

$2$ cases using our bounds, we have that the probability that

$P(\tau ,\mu )=0$ is less than

$(\frac{d-i_0}{p})\times 1+1\times \frac{i_0}{p}=\frac{d}{p}$.

For the various flavors of snarks that we will describe, the converse of the Schwartz-Zippel is equally useful:

Let

$Q\in {\mathbf{F}}_p[X_1,\dots ,X_n]$ be a polynomial of degree

$d$. If one picks randomly

$\tau \in {\mathbf{F}}_p^n$ and

$Q(\tau )=0$,

$Q$ is almost surely the zero polynomial.

Chosing

$\tau$ at random is crucial here, otherwise one just has to pick a root (if it exists) of

$Q$ to obtain

$Q(\tau )=0$.

Low degree extension (LDE)

The second is known as Low Degree Extension (or LDE) of a vector. In fact, this is just an interpolation of a vector: if one has a vector

$u\in {\mathbf{F}}_p^n$ with

$n<<p$, and a set

$S\subset {\mathbf{F}}_p$ with

$|S|=n$, the LDE of

$u$, which we name

$\tilde{u}$, is the interpolation of

$u$ on

$S$. Concretely it means that

$\tilde{u}$ is a polynomial of degree

$n-1$, and with a correct indexing of the elements

$s_i$ of

$S$, one has

$u_i=\tilde{u}(s_i)$.

Kate commitment

The Kate commitment scheme is a polynomial commitment scheme, meaning that it allows one to create a digest out of a polynomial that is binding to the polynomial and hiding.

We describe shortly how it works. Let

$(\mathbb{G},+)$ be a group of

$p$ elements in which the discret log is hard, and suppose that a trusted setup have been performed so that a sequence

$(g,\gamma g,\dots ,{\gamma }^{n-1}g)$, with

$n<p$, is publicly available, but nobody knows

$\gamma$.

Given a degre

$n-1$ polynomial

$P=\sum _{i\le n-1}{a}_i{X}^i\in {\mathbf{F}}_p[X]$, where

$n<<p$, the Kate commitment of

$P$ is the element

${\mathcal{K}}_P=\sum _i{a}_i{\gamma }^{i}g\in \mathbb{G}$.

Binding property Note that

${\mathcal{K}}_P=P(\gamma )g$. To find a collision, either one has to solve the discrete log to find the value of

$P(\gamma )$, which is supposedly hard, or one has to pick a polynomial

$Q$ such that

$Q(\gamma )=P(\gamma )$. But since

$\gamma$ is unknown, the Schwartz Zippel lemma tells us that this happens with probability less than

$\frac{n}{p}$.
Hiding porperty It stems from the fact that

$\gamma$ is unknown.

Note that

${\mathcal{K}}_P+{\mathcal{K}}_Q={\mathcal{K}}_{P+Q}$.

In what follows, the group

$\mathbb{G}$ needs an extra feature, called a pairing, which is a non degenerate bilinear application

$e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$, where

$({\mathbb{G}}_T,\times )$ is another group (the

$T$ stands for target, as

${\mathbb{G}}_T$ is often called the target group). It allows to "multiply"

$2$ elements in

$G$ (but only

$2$).

This feature allows a prover to open a commitment at a given value of the choice of a verifier:

• Prover computes
  $H=\frac{P-P(\alpha )}{X-\alpha }$, which is in
  ${\mathbf{F}}_p[X]$, and gives
  ${\mathcal{K}}_H$ and the claimed value
  $P(\alpha )$ to the verifier
• The verifier checks that
  $e({\mathcal{K}}_H,\alpha g-\gamma g)=e({\mathcal{K}}_P-P(\alpha )g,g)$ (remember that
  $g,\gamma g$ are public outputs from the trusted setup).

Completeness: it stems from the bilienarity and non degeneracy of the pairing.
Soundness: Since

$\gamma$ is unknown under the hardness of discrete log property, if the claimed evaluation is wrong, call it

$w$, the prover has to send a random

$\mathcal{K}(H^{\prime })=rg$, such that by luck

$\gamma$ is a root of

$\frac{P-w}{X-\alpha }-r$. The degree of

$H^{\prime }$ is at most

$n-1$ due to the trusted setup. The overall expression is at most of degree

$n$, so according to the Schwartz Zippel lemma the probability of that

$\gamma$ is a root of it is at most

$n/p$.

There is a way to batch reveal values of different commitments

${\mathcal{K}}_1,\dots ,{\mathcal{K}}_n$ at a single point

$z$ using a round of interaction with a verifier:

Let

${\mathcal{K}}_{P_1},\dots ,{\mathcal{K}}_{P_n}$ a list of Kate commitments to

$P_1,\dots ,P_n$. To query the values of these polynomial at

$z\in {\mathbf{F}}_p$:

• the prover sends the supposed evaluations
  $(s_i{)}_{i\in [n]}$ of
  $(P_i{)}_{i\in [n]}$ to the verifier
• the verifier sends a random challenge
  $v\in {\mathbf{F}}_p$ to the prover
• the prover computes the proof
  ${\mathcal{K}}_H$, where
  $H=\sum _{i\in [n]}{v}^i{P}_i/(X-z)$ and sends it to the verifier
• the verifier computes
  $s=\sum _{i\in [n]}{v}^i{s}_i$ and checks if
  $e({\mathcal{K}}_H,{\mathcal{K}}_{X-z})=e(\sum _{i\in [n]}{v}^i({\mathcal{K}}_{P_i}-{\mathcal{K}}_{s_i}),g)$
  If the last check holds, the claimed values are, with very high probability, corrects.

Since the commitments

$({\mathcal{K}}_{P_i})$ are given prior to the challenge

$v$, it's exactly the same argument as above.

Finally, we describe how to open different commitments at different points.

Let

$({\mathcal{K}}_{P_i}{)}_{i\in [n]}$ be a set of commitments and

$(z_1,\dots ,z_n)$ a set of points in

${\mathbf{F}}_p$. To open the commitments on the

$z_i$:

• a prover sends the individual proofs
  $({\mathcal{K}}_{H_i}{)}_{i\in [n]}$ as well as the evaluations
  $(s_i{)}_{i\in [n]}$
• a verifier choses random numbers
  $(r_i{)}_{i\in [n]}$, and computes
  $K^{\prime }=\sum _{i\in [n]}{r}_i{\mathcal{K}}_{H_i}$ and checks that
  
  $$e(K^{\prime },{\mathcal{K}}_{\sum _{i\in [n]}{r}_i(X-z_i)})=e(\sum _{i\in [n]}{r}_i({\mathcal{K}}_{P_i}-{\mathcal{K}}_{r_i}),{\mathcal{K}}_1)$$

Note: this method is fine as long as there are not too many points, because computing

$K^{\prime }$ is expensive (usually

$\mathbb{G}$ is a subgroup of the

$Fp$ rational points of an elliptic curve over

${\mathbf{F}}_p$, and computing

$K^{\prime }$ requires a multi exponentiation on this group).

PLONK

We have a constraint system such that the

$i$-th constraint looks like this:

$$\begin{array}{r}(q_L{)}_i{w}_{i_a}+(q_R{)}_i{w}_{i_b}+(q_M{)}_i{w}_{i_a}{w}_{i_b}+d_i=(q_c{)}_i{w}_{i_c}\end{array}$$
and the whole system has the matrix representation

$$q_L\circ (A\circ w)+q_R\circ (Bw)+d+q_M\circ (Aw\circ Bw)=q_c\circ (Cw)$$

where

$A,B,C$ are pseudo permutation matrices.

The goal of PLONK is to get rid of

$A,B,C$ by encoding the corresponding permutations using polynomials, so they can be commited using the Kate commitment scheme. A circuit is represented by

$$q_L\circ a+q_R\circ b+d+q_M\circ (a\circ b)=q_c\circ c$$
with the condition that

$a,b,c$ are permutations of set

$(w_i{)}_i$.

Example: Imagine a program computing

$w_0^5$ where

$w_0$ is a given input. The arithmetization of this circuit consists of the following set of constraints:

$$\begin{gathered} w_0\times w_0=w_1 \\ {w}_1\times w_0=w_2 \\ {w}_2\times w_2=w_3 \\ {w}_3\times w_0=w_4 \end{gathered}$$
The result is

$w_4$. With matrices, we have (we omit

$q_M$ and

$q_c$, containing only

$1$):

$$\left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}{w}_0\\ w_1\\ w_2\\ w_3\\ w_4\end{array}\right)\circ \left(\begin{array}{ccccc}1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0\end{array}\right)\left(\begin{array}{c}{w}_0\\ w_1\\ w_2\\ w_3\\ w_4\end{array}\right)=\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\end{array}\right)\left(\begin{array}{c}{w}_0\\ w_1\\ w_2\\ w_3\\ w_4\end{array}\right)$$

Notice that there is exactly

$1$ non zero entry in each line of the matrices.

To take the PLONK version of this, we get rid of the matrices

$A,B,C$ by applying the matrix multiplications, corresponding to permutations, and we end up with:

$$\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)\circ \left(\begin{array}{c}{w}_0\\ w_1\\ w_2\\ w_3\end{array}\right)\circ \left(\begin{array}{c}{w}_0\\ w_0\\ w_2\\ w_0\end{array}\right)=\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)\circ \left(\begin{array}{c}{w}_1\\ w_2\\ w_3\\ w_4\end{array}\right)$$
Here

$q_M=q_c=(1,1,1,1{)}^t$.

The general PLONK representation is therefore

$$\begin{gathered} q_M\circ a\circ b=q_c\circ c \\ a=(w_0,w_1,w_2,w_3) \\ b=(w_0,w_0,w_2,w_0) \\ c=(w_1,w_2,w_3,w_4) \end{gathered}$$

We need a compact way to encode that

$a,b,c$ are of this form, so a prover can convince the verifier of this.

If we concatenate

$a,b,c$ in that order, we obtain a vector

$d$ of size

$12$, and we observe that

$d$ is invariant under certain permutations of

$12$ elements. In fact,

$d=a||b||c$ should look like this:

$(w_0,w_1,w_2,w_3,w_0,w_0,w_2,w_0,w_1,w_2,w_3,w_4)$. The first, fourth, fifth, eighth entries are the same, equal to

$w_0$, so for instance d is invariant when the cycle

$1\to 5\to 6\to 8\to 1$ acts on the entries. Identifying all the cycles that leave

$d$ invariant (those cycles shift the entries of the duplicated variable, like

$w_0$ in the example), we end up with a permutation

$\sigma$ which completely characterize a circuit-compliant solution.

To prove the knowledge of a solution

$a,b,c$ to the system, he needs to:

• claim 1: prove that
  $q_L\circ a+q_R\circ b+q_M\circ a\circ b+d=q_c\circ c$
• claim 2: prove that
  $a||b||c$ is invariant under the action of
  $\sigma$.

In what follows, we drop

$q_L,q_R$ and

$d$ to simplify the notations. So claim 1 becomes

$$q\circ a\circ b=o\circ c$$
Without this shortcut the notations are overloaded and it's harder to read, and it changes nothing to the explanations.

claim 1

To prove the first claim, prover and verifier agree on a set

$S\subset {\mathbf{F}}_p$ of size

$n$, and the prover computes the LDE

$\tilde{a},\tilde{b},\tilde{c}$ of

$a,b,c$ on

$S$.

If

$I_S={\mathrm{\Pi }}_{i\in [n]}(X-s_i)\in {\mathbf{F}}_p[X]$, we have

$$q\circ a\circ b=o\circ c\iff \tilde{q}\tilde{a}\tilde{b}-\tilde{o}\tilde{c}=h{I}_S$$
where

$h=(\tilde{q}\tilde{a}\tilde{b}-\tilde{o}\tilde{c})/I_S$.

The general strategy to prove that an algebraic relation

$\mathcal{A}(P_1,\dots ,P_l)$ between polynomials

$(P_i{)}_{i\in [l]}$ holds is:

• Verifier asks the prover the commitments
  $({\mathcal{K}}_{P_i}{)}_{i\in [l]}$
• Verifier choses
  $\zeta$ at random, and queries the values
  $(P_i(\zeta ))$ for all but one polynomial (say
  $P_1$)
• Verifier computes
  $P_1(\zeta )$ by finding
  $x$ such that
  $\mathcal{A}(x,P_2(\zeta ),\dots ,P_l(\zeta ))$ holds
• Verifier asks a proof for the opening of all
  $(P_i{)}_{i\in [l]}$ at
  $\zeta$
• Verifier cheks that the proof is correct, and that
  $x=P_1(\zeta )$

To how this works, since the commitments

$({\mathcal{K}}_{P_i}{)}_{i\in [l]}$ are sent prior evaluating them at

$\zeta$, the Schwartz Zippel lemma tells us that the chances that

$P_1$ opens correctly at

$x$ such that

$\mathcal{A}(x,P_2(\zeta ),\dots ,P_l(\zeta ))$ are negligible if

$\mathcal{A}(P_1,\dots ,P_l)$ does not hold.

In what we need to prove,

$$\begin{gathered} \mathcal{A}(\tilde{a},\tilde{b},\tilde{c},\tilde{q},\tilde{o},h,I_S): \\ \tilde{q}\tilde{a}\tilde{b}-\tilde{o}\tilde{c}=h{I}_S \end{gathered}$$
The role of

$P_1$ in the example is played by

$h$.

So the procedure is the following, where

$\tilde{q},\tilde{o},I_S$ are public:

• The prover sends
  ${\mathcal{K}}_{\tilde{a}},{\mathcal{K}}_{\tilde{b}},{\mathcal{K}}_{\tilde{c}},{\mathcal{K}}_h$ to the verifier
• Verifier queries
  $\tilde{a}(\zeta ),\tilde{b}(\zeta ),\tilde{c}(\zeta )$ (but not
  $h(\zeta )$) at a random challenge
  $\zeta$
• Verifier computes
  $h^{\prime }=\tilde{q}(\zeta )\tilde{a}(\zeta )\tilde{b}(\zeta )-\tilde{o}(\zeta )\tilde{c}(\zeta )/I_S(\zeta )$
• verify checks a batch opening proof of
  ${\mathcal{K}}_{\tilde{a}}+v{\mathcal{K}}_{\tilde{b}}+v^2{\mathcal{K}}_{\tilde{c}}+v^3{\mathcal{K}}_h$ at
  $\zeta$ to check that it opens correctly to
  $\tilde{a}(\zeta )+v\tilde{b}(\zeta )+v^2\tilde{c}(\zeta )+v^3{h}^{\prime }$

We mention that there are ways to modify this protocol to use commitments of the public data

$K_{\tilde{q}},K_{\tilde{o}}$ instead of directly using

$\tilde{q},\tilde{o}$ for memory bounded verifiers.

claim 2

The goal is to prove that

$\sigma .d=d$ where

$d=a||b||c$, by characterizing it in term of divisibility by

$I_S$, so a similar strategy as in the first claim can be used.

The solution stems from the following property:

Let

$d$ a vector in

${\mathbf{F}}_p^n$, where

$n<<p$, let

$S\subset {\mathbf{F}}_p-\{0\}$ be a set of

$n$ distincts elements

$s_1,\dots ,s_n$ and

$\sigma$ a permutation of

$n$ elements. We have the following equivalence:

$$\sigma .d=d\iff {\mathrm{\Pi }}_{i\in [n]}(d_i+s_{i}X+Y)={\mathrm{\Pi }}_{i\in [n]}(d_i+s_{\sigma (i)}X+Y)$$
where the left hand side is in

${\mathbf{F}}_p[X,Y]$.

$(\Rightarrow )$ is obvious.

$(\Leftarrow )$ Since

${\mathbf{F}}_p[X,Y]$ is a unique factorization domain, meaning there is a unique way of decomposing polynomials in irreducible components, and the

$d_i+s_{i}X+Y$ are irreducible components, for each

$i$ there is a

$j$ such that

$d_i+s_{i}X+Y=d_j+s_{\sigma (j)}X+Y$ and therefore (with the same argument) that

$d_i=d_j$ and

$\sigma (j)=i$.

Now we assume that

$X,Y$ are replaced by random challenges

$\beta$ and

$\gamma$, chosen by the verifier. The Schwart Zippel lemma ensures that there is no loss of information.

To apply this property to

$d=a||b||c$, we would like to have the LDE of

$a||b||c$, but the problems are that

• this vector is of size
  $3n$, and computing its LDE of
  $d$ would require a set
  $S^{\prime }$ of interpolation of size
  $3n$
• we don't reuse the LDE
  $\tilde{a},\tilde{b},\tilde{c}$ of
  $a,b,c$ on
  $S=\{s_1,\dots ,s_n\}$ that the prover aleady computed.

Encoding the permutation

$\sigma$:

One thing not avoidable is to extend the set

$S=\{s_1,\dots ,s_n\}\in {\mathbf{F}}_p$ so that it becomes a set of

$3n$ elements for encoding the permutation.

To extend

$S$, pick

$k_1\in {\mathbf{F}}_p-S$ and add the set

$S1=k_{1}S$, then pick

$k_2\in {\mathbf{F}}_p-(S\cup S_1)$ and build the set

$k_{2}S$. Those

$3$ sets are disjoints (it stems from the fact that

$(\mathbf{F}\ast ,\times )$ is a group).

Now that the set

$S$ is extended to

$S^{\prime }=S\cup S_1\cup S_2$, we interpret

$\sigma$ as a permutation of

$S^{\prime }$, and we can rewrite the products in the property by grouping the entries of

$a,b,c$:

$$\begin{gathered} \sigma .d=d\iff \\ {\mathrm{\Pi }}_{i\in [n]}(\tilde{a}(s_i)+s_i\beta +\gamma )(\tilde{b}(s_i)+k_1{s}_i\beta +\gamma )(\tilde{c}(s_i)+k_2{s}_{i}X+\gamma )= \\ {\mathrm{\Pi }}_{i\in [n]}(\tilde{a}(s_i)+\sigma (s_i)\beta +\gamma )(\tilde{b}(s_i)+\sigma (k_i{s}_i)\beta +\gamma )(\tilde{c}(s_i)+\sigma (k_2{s}_2)\beta +\gamma ) \end{gathered}$$

This grouping allows to compute the LDE of

$\sigma$, and

$Id$ on

$S$ only, and not on something

$3$ times bigger. Namely

• $Id$ is encoded as
  $I{d}_1=X,I{d}_2=k1X=k_{1}I{d}_1,I{d}_3=k_{2}X=k_{2}I{d}_1$
• $\sigma$ is encoded
  $({\sigma }_1,{\sigma }_2,{\sigma }_3)$ where
  ${\sigma }_1$ is the LDE of
  $(\sigma (s_i){)}_{i\in [n]}$,
  ${\sigma }_2$ the LDE of
  $(\sigma (k1s_i{)}_{i\in [n]}$, and
  ${\sigma }_3$ the LDE of
  $(\sigma (k2s_i{)}_{i\in [n]}$

Now we can write the previous equivalence in this way:

$$\begin{gathered} \sigma .d=d\iff \\ {\mathrm{\Pi }}_{i\in [n]}(\tilde{a}(s_i)+I{d}_1(s_i)\beta +\gamma )(\tilde{b}(s_i)+I{d}_2(s_i)\beta +\gamma )(\tilde{c}(s_i)+I{d}_3(s_i)\beta +\gamma )= \\ {\mathrm{\Pi }}_{i\in [n]}(\tilde{a}(s_i)+{\sigma }_1(s_i)\beta +\gamma )(\tilde{b}(s_i)+{\sigma }_2(s_i)\beta +\gamma )(\tilde{c}(s_i)+{\sigma }_3(s_i)\beta +\gamma ) \end{gathered}$$

Everything is in polynomial form, and the polynomials involved are LDE on

$S$, so it is a huge step forward.

From now on we require that the domain of interpolation

$S$ is a multiplicative subgroup of

${\mathbf{F}}_p$, in particular it's a cyclic subgroup generated by

$\mu$ of size

$n$, its elements are (in that order)

$\{s_1,s_2,\dots ,s_n\}=\{1,\mu ,\dots ,{\mu }^{n-1}\}$.

We also set the following notations:

• Call
  $f=(\tilde{a}+I{d}_1\beta +\gamma )(\tilde{b}+I{d}_2\beta +\gamma )(\tilde{c}+I{d}_3\beta +\gamma )$
• Call
  $g=(\tilde{a}+{\sigma }_1\beta +\gamma )(\tilde{b}+{\sigma }_2\beta +\gamma )(\tilde{c}+{\sigma }_3\beta +\gamma )$
• Call
  $f_i=f(s_i)$ and
  $g_i=g(s_i)$.

The key idea to encode the permutation using polynomials is to take the LDE

$Z$ of the vector

$$(1,\frac{f_1}{g_1},\frac{f_1{f}_2}{g_1{g}_2},\dots ,\frac{f_1\dots f_{n-1}}{g_1\dots g_{n-1}})$$
, so

$Z(s_i)=1$ is

$i=1$, otherwise

$Z(s_i)=\frac{f_1\dots f_{i-1}}{g_1\dots g_{i-1}}$ for

$1<i\le n$.
The term

$(f_1\dots f_n)/(g_1\dots g_n)$ is not taken.

Observe that

$Z(s_{i+1})=Z(s_i)\frac{f_i}{g_i}$ for

$i$ from

$1$ to

$n-1$. Since

$s_{i+1}=\mu \times s_i$, we almost have a relation on all

$S$ which is

$Z(\mu X)=Z(X)f(X)/g(X)$. The only possibilty of failure if when

$i=n$.

In fact, on

$X=s_n$, since

$S$ is a cyclic group, we have

$\mu s_n={\mu }^n=1$. On the other hand,

$$Z(s_n)\frac{f_n}{g_n}=(\frac{f_1\dots f_{n-1}}{g_1\dots g_{n-1}})\frac{f_n}{g_n}$$ should be

$1$ if (and only if up to a to a negligible soudness error)

$\sigma .d=d$.

So the relation

$Z(\mu X)=Z(X)f(X)/g(X)$ and

$Z(s_0)=1$ is true on all

$S$ iff

$\sigma .d=d$.

Since

$Z(s_0)=1$ is characterized by

$L_{s_0}(X)(Z(X)-1)=0$ on

$S$, where

$L_{s_0}$ is the LDE of

$(1,0,\dots ,0)$, we have

$\sigma .d=d\iff Z(\mu X)g(X)-Z(X)f(X)=h_1(X)I_S(X)$ and

$L_{s_0}(X)Z(X)=h_2(X)I_S(X)$

We finally have a characterization of

$\sigma .d=d$ in term of divisibility by

$I_S$ involving

$\tilde{a},\tilde{b},\tilde{c}$ (since

$Z$ depends on those).

Since the permutations describe the circuit, there are part of the public data, and we suppose that

$({\mathcal{K}}_{{\sigma }_i}{)}_{i=1,2,3}$ are precomputed. Note that

$({\mathcal{K}}_{I{d}_i}{)}_{i=1,2,3}$ are directly available since

$I{d}_1=X$,

$I{d}_2=k1I{d}_1$,

$I{d}_3=k2I{d}_1$.

The

$2$ divisibility claims can be collapsed into one if the verifier checks that a random linear combination

$$Z(\mu X)g(X)-Z(X)f(X)+\alpha L_{s_0}(X)(Z(X)-1)$$ is divisible by

$I_S$, call the quotient

$h$.

We apply exactly the same strategy as in claim 1, where

$$\begin{gathered} \mathcal{A}(\tilde{a},\tilde{b},\tilde{c},{\sigma }_1,{\sigma }_2,{\sigma }_3,Z,h,I_S,L_{s_0}): \\ Z(\mu X)g(X)-Z(X)f(X)+\alpha L_{s_0}(X)(Z(X)-1)=h(X)I_S(X) \end{gathered}$$
and the role of

$P_1$ is played by

$h$.

Here is a description of the proof of claim 2, where

${\sigma }_1,{\sigma }_2,{\sigma }_3,L_{s_0},I_S$ are public:

claim 2:

• Prover sends
  ${\mathcal{K}}_{\tilde{a}},{\mathcal{K}}_{\tilde{b}},{\mathcal{K}}_{\tilde{c}}$
• Verifier sends challenges
  $\beta ,\gamma$ (used to compute
  $Z$)
• Prover sends
  ${\mathcal{K}}_Z$ (computed with
  $\beta ,\gamma$)
• Verifier sends a random
  $\alpha$ to the prover (used to collapse the
  $2$ divisibility claims)
• Prover computes
  $h$ and sends
  $K_h$ to the verifier
• Verifier queries
  $\tilde{a}(\zeta ),\tilde{b}(\zeta ),\tilde{c}(\zeta ),Z(\zeta ),Z(\mu \zeta )$ at a random
  $\zeta$
• Verifier computes
  ${\sigma }_1(\zeta ),{\sigma }_2(\zeta ),{\sigma }_3(\zeta ),I_S(\zeta ),L_{s_0}(\zeta )$
• verifier computes
  $h^{\prime }=(Z(\mu \zeta )g(\zeta )-Z(\zeta )f(\zeta )+\alpha L_{s_0}(\zeta )(Z(\zeta )-1))/I_S(\zeta )$
• The verifier sends a random challenge
  $v$ to the prover
• The prover sends a proof for the batch opening of
  $K={\mathcal{K}}_{\tilde{a}}+v{\mathcal{k}}_{\tilde{b}}+v^2{\mathcal{K}}_{\tilde{c}}+v^3{\mathcal{K}}_Z+v^4{\mathcal{K}}_h$ at
  $\zeta$ and for the opening of
  $K_Z$ at
  $\mu \zeta$
• The verifier choses a random
  $u$ and verifies the opening of
  $K+u{K}_Z$ (using the Kate reveal at different points).

Note that claim 1 and claim 2 can be collapsed into

$1$ claim. Namely, the

$\alpha$ used to check that

$Z(\mu X)g(X)-Z(X)f(X)+\alpha L_{s_0}(X)(Z(X)-1)$ is divisible by

$I_S$ can be reused to incorporate the first claim, so the final protocol checks that

$$Z(\mu X)g(X)-Z(X)f(X)+\alpha L_{s_0}(X)(Z(X)-1)+{\alpha }^2(\tilde{q}\tilde{a}\tilde{b}-\tilde{o}\tilde{c})$$
is divisible by

$I_S$.

There are ways to customize this protocol to use commitments of the public data

$({\sigma }_i)$ instead of their raw values, for memory bounded verifiers.

Conclusion

There are a lot of small variations to PLONK. Since PLONK relies on general polynomial commitment schemes (here only the Kate commitment scheme was presented), it is quite flexible and can be used for proof carrying data constructions such as Halo.

---

Author: Thomas Piellard.

I'm part of a research team at ConsenSys. If you are interested in our work (fast finite field arithmetic, elliptic curve pairings, and zero-knowledge proofs), give us a shout.