Notes on Plonk Prover's and Verifier's Algorithm

Disclaimer: This documentation was written on July, 2021. It is intended to give readers a high-level understanding. The codebase is the canonical source of truth, and over time this document might fall behind the implementation details of the code.

Author: Arijit

This is a brief note about my understanding of the prover's and verifier's algorithms in the Plonk paper. The note directly jumps to Section 8.4 of the paper and tries to answer some questions which I had while going through the various steps of the algorithms. I would like to acknowledge the help and clarifications I got from Zac, Ariel, and Suyash in writing this note.

The goal of the prover is described in the language

$R_{\text{snark}}(\lambda )$ given in Section 8.3 of the paper. In the polynomial setting, this boils down to proving knowledge of the wire polynomials

$a(X),b(X)$,

$c(X)$, and the permutation polynomial

$z(X)$ such that,

1. $a(X)b(X)q_M(X)+a(X)q_L(X)+b(X)q_R(X)+c(X)q_O(X)+PI(X)+q_C(X)=0$ holds for all
   $X\in H$, where
   $H$ is the set containing the roots of unity.
2. $$\begin{gathered} (a(X)+\beta X+\gamma )(b(X)+\beta k_{1}X+\gamma )(c(X)+\beta k_{2}X+\gamma )z(X)- \\ (a(X)+\beta S_{\sigma 1}(X)+\gamma )(b(X)+\beta S_{\sigma 2}(X)+\gamma )(c(X)+\beta S_{\sigma 3}(X)+\gamma )z(X\omega )=0 \end{gathered}$$ holds for all
   $X\in H$.
3. $(z(X)-1)L_1(X)=0$ holds for all
   $X\in H$.
   As explained in the paper, the first condition will validate the gate contraints (the witnesses satisfy the plonk circuit) and the second and third conditions will validate the copy constraints (all the connections of the plonk circuit are verified by the grand product argument). However, the prover should prove that the above conditions hold in zero-knowledge i.e. without revealing the polynomials
   $a(X),b(X)$,
   $c(X)$, and
   $z(X)$. To do so the prover proceeds as follows.

Round 1:

The prover constructs the polynomials

$a(X),b(X)$, and

$c(X)$ with some randomizations. Then it computes the commitments of

$a(X),b(X)$, and

$c(X)$ as per the Kate's polynomial commitment scheme. Here the commitment

${[k]}_1$ to a polynomial

$k(X)=\sum _i{k}_i{X}^i$ is defined as the evaluation of the polynomial at the unknown SRS point

$x$ in the exponent of the generator

$G_1$ of the first group i.e.,

$$\begin{array}{r}{[k]}_1=(\sum _i{k}_i{x}^i)G_1.\end{array}$$

Note: The random parts of

$a(X),b(X)$, and

$c(X)$ are,

$$b_{1}X+b_2,b_{3}X+b_4,b_{5}X+b_6,$$
respectively. Note that they have zero contributions when the polynomials are evaluated at the roots of unity. This is due to the multiplication with the vanishing polynomial

$Z_H(X)=X^n-1$ which has all

$n$ roots of unity as its roots.
Q: Why do we need two random scalars to randomize

$a(X),b(X)$ and

$c(X)$.
A: The prover needs to send the commitments to

$a(X),b(X)$, and

$c(X)$ and also their evaluations at

$\mathfrak{z}$ to the verifier. Roughly, the two revelations costs two random scalars for the protocol to satisfy the special honest-verifier zero-knowledge (SHVZK) property.

Round 2:

Like the wire polynomials, the permutation polynomial

$z(X)$ is computed by adding some randomization. In Section 5 (Polynomial protocols for identifying permutations), it is explained what should be the value of

$z(X)$ for each roots of unity. Those values are set by using the Lagrange bases

$L_i(X)$s.
Q: Why do we need three random scalars to randomize

$z(X)$.
A: Unlike

$a(X),b(X)$, and

$c(X)$, the permutation polynomial

$z(X)$ has been used to evaluate two opening proof polynomials

$W_{\mathfrak{z}}(X)$ and

$W_{\mathfrak{z}\omega }(X)$. This costs three random scalars to ensure the SHVZK property of the protocol.

Round 3:

Q: What is the quotient polynomial

$t(X)$ and why it is computed?
A: The quotient polynomial

$t(X)$ has four elements. The numerators of the four elements are from the three conditions given above that the prover has to satisfy. Each of them are divided by

$Z_H(X)$ and added after some random scaling by

$\alpha$ and

${\alpha }^2$. The fact that the prover has successfully computed a "valid" commitment to

$t(X)$ will ensure that

$t(X)$ does not have any

$a_i{X}^{-i}$ term. This is because the SRS used to compute the commitment does not have any

$x^{-i}{G}_1$ term.

This in turn proves that

$Z_H(X)$ divides all the numerator i.e. the numerators evaluate to zero at every roots of unity. Hence the three conditions given above are satisfied.

Instead of computing commitment to

$t(X)$, the prover breaks

$t(X)$ into three parts

$t_{lo}(X)$,

$t_{mid}(X)$, and

$t_{hi}(X)$ and computes their commitments. This is done because of the folloing reasons.

1. We want the max degree of our polynomials to be n.
2. Kate opening proof
   $W_{\mathfrak{z}}(X)$ computation (in terms of
   $r(X)$) would require committing to size 3n polynomials which is very inefficient.

Round 4:

To prove the definition of

$t(X)$,

$a(X)$,

$b(X)$,

$c(X)$,

$S_{\sigma 1}(X)$,

$S_{\sigma 2}(X)$ are evaluated at a random challenge point

$\mathfrak{z}$ which is generated non-interactively by Fiat-Shamir heuristic.
Q: Why every polynomial in

$t(X)$ is not evaluated?
A: This is because of the linearization trick (described in page 18) where a partial evaluation of polynomials is done to prove an identity involving them. This is to reduce the communication cost of the prover.
Q: Why

$z(X)$ is evaluated at a different point

$\mathfrak{z}\omega$?
A: In

$t(X)$, both

$Z(X)$ and

$Z(X\omega )$ appear. We do not evaluate

$Z(X)$ to make use of the linearization trick and only evaluate

$Z(X)$ at

$\mathfrak{z}\omega$. As

$Z(X)$ is opened in

$\mathfrak{z}\omega$ instead of

$\mathfrak{z}$, we need a separate opening polynomial

$W_{\mathfrak{z}\omega }(X)$ for

$Z(X)$ defined in Round 5.

Round 5

Q: What is the linearization polynomial

$r(X)$?
A: To simplify, let

$$\begin{array}{rl}& t(x)=t_{lo}(X)+X^n{t}_{mid}(X)+X^{2n}{t}_{hi}(X)=\frac{l(X)}{Z_H(X)}.\end{array}$$
This implies,

$r(X)=l(X{)}_{par}-Z_H(\mathfrak{z})(t_{lo}(X)+{\mathfrak{z}}^n{t}_{mid}(X)+{\mathfrak{z}}^{2n}{t}_{hi}(X))$ is zero if it is evaluated at

$\mathfrak{z}$. Here

$l(X{)}_{par}$ has a mixed form of polynomials and evaluations at

$\mathfrak{z}$.

Note that the verifier can calculate the commitment of

$r(X)$ using the elements of the proof

${\pi }_{SNARK}$ generated so far i.e.

$({[a]}_1,{[b]}_1,{[c]}_1,{[z]}_1,{[t_{lo}]}_1,{[t_{mid}]}_1,{[t_{hi}]}_1,\overline{a},\overline{b},\overline{c},{\overline{s}}_{\sigma 1},{\overline{s}}_{\sigma 2},{\overline{z}}_{\omega })$. Thus the prover does not have to send the commitment to

$r(x)$ to prove that it vanishes at

$\mathfrak{z}$.

Now let us observe

$W_{\mathfrak{z}}(X)$. Let,

$$\begin{array}{r}{W}_{\mathfrak{z}}(X)=\frac{M(X)}{X-\mathfrak{z}}\end{array}$$
If the prover can compute the commitment to

$W_{\mathfrak{z}}(X)$, then it is verified that

$(X-\mathfrak{z})$ divides

$M(X)$ (As the SRS does not have negetive exponents of

$x$). Now consider each part of

$M(X)$. As

$v$ is random,

$(X-\mathfrak{z})$ divides each term.

$(X-\mathfrak{z})$ divides

$r(X)$ implies

$r(\mathfrak{z})=0$. Similarly

$(X-\mathfrak{z})$ divides

$(a(X)-\overline{a})$ implies

$\overline{a}$ is the evaluation of

$a(X)$ at

$\mathfrak{z}$.

To show that if

$(X-\mathfrak{z})$ divides

$(a(X)-\overline{a})$, then

$\overline{a}=a(\mathfrak{z})$.
We have

$(a(X)-\overline{a})=q(X)(X-\mathfrak{z})$. Putting

$x=\mathfrak{z}$, we get

$\overline{a}=a(\mathfrak{z})$.

This applies for other polynomials and their evaluations as well. In this way the commitment to

$W_{\mathfrak{z}}(X)$ verifies every evaluations of the polynomials and also

$r(\mathfrak{z})=0$.

As discussed above, we need a separate opening polynomial

$W_{\mathfrak{z}\omega }(X)$ to validate the evaluation

${\overline{z}}_{\omega }$ of the polynomial

$z(X)$ at

$\mathfrak{z}\omega$.

Finally, the prover outputs commitments

${[W_{\mathfrak{z}}]}_1$,

${[W_{\mathfrak{z}\omega }]}_1$ to these two opening polynomials and construct the proof

${\pi }_{\text{SNARK}}$.

Verifier's algorithm:

In steps 1 to 3, the verifier checks the sanity of different elements of

${\pi }_{\text{SNARK}}$. Steps 4 to 11 are the various steps that prepare the verifier for the pairing check.

Let

$W_{\mathfrak{z}}(X)=\frac{M(X)}{X-\mathfrak{z}}$ and

$W_{\mathfrak{z}\omega }(X)=\frac{N(X)}{X-\mathfrak{z}\omega }$. After rearranging we get,

$$\begin{array}{rl}X{W}_{\mathfrak{z}}(X)& =M(X)+\mathfrak{z}{W}_{\mathfrak{z}}(X)\\ X{W}_{\mathfrak{z}\omega }(X)& =N(X)+\mathfrak{z}\omega W_{\mathfrak{z}\omega }(X)\end{array}$$
Combining these two identities with the multi-point evolution challenge

$u$ gives,

$$\begin{array}{r}X(W_{\mathfrak{z}}(X)+u{W}_{\mathfrak{z}\omega }(X))=\mathfrak{z}{W}_{\mathfrak{z}}(X)+u\mathfrak{z}\omega W_{\mathfrak{z}\omega }(X)+M(X)+uN(X)\end{array}$$
Step 12 checks the above identity in the exponent using pairing and all the commitments and the evaluations of polynomials sent by the prover. Using the polynomial commitments, the unknown SRS value

$x$ is used instead of the indeterminate

$X$ and accumulated in

$F$. The components involving constant terms and evaluations are accumulated in

$E$. This is similar to the batch verification of the Kate commitment scheme described in Section 3 of the paper.

This validates the opening commitments

${[W_{\mathfrak{z}}]}_1$,

${[W_{\mathfrak{z}\omega }]}_1$ and all the three statements to be proved by the prover are verified.