Understand PLONK: The PLONK Prover

At the heart of the PLONK protocol lies one of its most fascinating components: the prover. After the universal trusted setup and the arithmetic representation of our computation, the prover takes center stage in constructing a convincing zero-knowledge proof that will persuade the verifier without revealing any sensitive information.

The prover's role in PLONK represents a remarkable achievement in zero-knowledge proof systems, offering a delicate balance between efficiency and security. Unlike its predecessors, PLONK's prover leverages the protocol's universal preprocessing to generate proofs that are both compact and computationally efficient, while maintaining the critical property of zero-knowledge.

The PLONK prover is broken down into rounds and using this rounds, we would be understanding how the PLONK proof is genearted;
As the protocol progresses, we would be creating some polynomials and also for polynomial mathematical relationships which would be examine and sealed(polynomail commitment schemes) to be used to create the PLONK protocol's Proof.

Recall: CommonPreprocessedInput {

$S_{\sigma }^1$,

$S_{\sigma }^2$,

$S_{\sigma }^3$,

$q_L$,

$q_R$,

$q_O$,

$q_M$,

$q_C$,

$a$,

$b$,

$c$ } which was obtained when PLONKish arithmetization was applied to the circuit including the witness.

Round One

Objective
This round aims to create the polynomials

$a,b,c$ and commit to them, this polynomails are expressions of the computational trace of the circuit's exectution given this witnesses;

Procedure
The first round of the PLONK protocol tells us how to;

• initialize the Transcript with some circuit binding vaules, this is to improve soundness of the protocol (CommonPreprocessedInput).
• Compute random field elements, this would be used for the blinding_factor. (
  $r_1,r_2,r_3,r_4,r_5,r_6$)
• encode assignment vectors
  $a^{\prime },b^{\prime },c^{\prime }$ creating a polynomial by interpolating this
  $T$ matrix columns at the domain
  $H$ (roots of unity).
• create polynomial
  $a,b,c$ by blinding
  $a^{\prime },b^{\prime },c^{\prime }$ polynomials using the blinding factors created above, this is important to ensure the protocol is "Zero Knowledge". learn more about the concept of blinding polynomails here
• Commit to polynomial
  $a,b,c$ and append this commitment to the transcript.

Mathematical translation;

$r_1,r_2,r_3,r_4,r_5,r_6\in F$

$a=(r_{1}X+r_2)Z_H+a^{\prime }$

$b=(r_{3}X+r_4)Z_H+b^{\prime }$

$c=(r_{5}X+r_6)Z_H+c^{\prime }$

poly-commit

$[a{]}_1,[b{]}_1,[c{]}_1$

Round Two

Objective
To enforce consistency across shared wires in the circuit using a permutation argument.

Procedure

• Compute permutation challenges
  $\beta$ and
  $\gamma$
• Compute
  $z(x)$, a polynomails encoding the wiring/copy-constriant of the circuit.
• Blind
  $z(x)$ following the same concept use in Round One.
• Commit to the
  $z(x)$ to obtain
  $[z{]}_1$

Mathematical translation;

$r_7,r_8,r_9\in F$

$(\beta ,\gamma )\in F$

$z(x)=(b_7{X}^2+b_{8}X+b_9)Z_H(X)+L_1(X)+\sum _{i=1}^{n-1}{L}_{i+1}(X)\prod _{j=1}^Q\frac{(w_j+\beta {\omega }^j+\gamma )(w_{n+j}+\beta k_1{\omega }^j+\gamma )(w_{2n+j}+\beta k_2{\omega }^j+\gamma )}{(w_j+{\sigma }^{(}j)\beta +\gamma )(w_{n+j}+{\sigma }^{(}n+j)\beta +\gamma )(w_{2n+j}+{\sigma }^{\ast }(2n+j)\beta +\gamma )}$
poly_commit(z) =

$[z{]}_1$ and append this commitment to the transcript

Round Three

Objective
Round three, been the most complicated and computationaly intensed round, the goal that is to be achieved is to create a poolynomial

$t$ that encodes all information the circuit is comprised of along side the witness and commit to it. This would not be as striaght forward as the last rounds because the degree of the polynomial is going to be

$3n+5$ where

$n$ is the number of gate, this would breaks because the trusted setup ceremony was not done to handle this.
A clever solution to handle this, is to break the polynomail in 3 before commiting to the polynomial.

Procedure

• Sample
  $\alpha$ from the transcript
• compute
  $t(x)$
• commit to
  $t_{lo}(x)$,
  $t_{mid}$, and
  $t_{hi}(x)$ and append to the transcript

Mathematical translation

$\alpha \in F$

$$t(X)=\frac{(a(X)b(X)q_M(X)+a(X)q_L(X)+b(X)q_R(X)+c(X)q_O(X)+\text{PI}(X)+q_C(X))}{Z_H(X)}+\frac{\alpha \cdot (a(X)+\beta X+\gamma )(b(X)+\beta k_{1}X+\gamma )(c(X)+\beta k_{2}X+\gamma )z(X)}{Z_H(X)}-\frac{\alpha \cdot (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 )}{Z_H(X)}+\frac{{\alpha }^2\cdot (z(X)-1)L_1(X)}{Z_H(X)}$$

The polynomial

$t(X)$ is split into smaller polynomials of degree at most

$n+5$ :

$t(X)=t\prime \text{lo}(X)+X^{n}t\prime \text{mid}(X)+X^{2n}t\prime \text{hi}(X)$,
where

$t\prime \text{lo}(X),t\prime \text{mid}(X),t\prime \text{hi}(X)$ are polynomials of degree

$<n$ .
Random scalars

$b_{10},b_{11}\in \mathbb{F}$ are used to introduce randomness to the split polynomials:

$t_{\text{lo}}(X):=t\prime \text{lo}(X)+b10X^n$,

$t_{\text{mid}}(X):=t\prime \text{mid}(X)-b10+b_{11}{X}^n$,

$t_{\text{hi}}(X):=t\prime \text{hi}(X)-b11$.
This ensures that:

$t(X)=t_{\text{lo}}(X)+X^n{t}_{\text{mid}}(X)+X^{2n}{t}_{\text{hi}}(X)$.
The prover commits to the split polynomials:

$[t_{\text{lo}}]1:=[t\text{lo}(x)]1,[t\text{mid}]1:=[t\text{mid}(x)]1,[t\text{hi}]1:=[t\text{hi}(x){]}_1.$

Round Four

Objective
In the previous rounds we have obtained a good amount of polynomials, operations over polynomials are not very computationally friendly, to make this more efficient, we would be reducing this polynomial to a Scalar Field element which is significantly more cheaper.

Procedure
obtain

$\zeta$ from transcript

The prover computes the evaluations of various polynomials at

$z$ and

$z\omega$ , where

$\omega$ is a primitive root of unity for the evaluation domain.

Polynomials and Their Evaluations:

1. Wire Polynomials:
   
   $\overline{a}=a(z),\overline{b}=b(z),\overline{c}=c(z),$
   representing the evaluations of the left, right, and output wires at
   $z$ .
2. Permutation Selectors:
   
   $\overline{s}{\sigma }_1=S{\sigma }_1(z),\overline{s}{\sigma }_2=S{\sigma }_2(z),$
   representing the evaluations of the first and second permutation selector polynomials at
   $z$ .
3. Shifted Permutation Polynomial:
   
   ${\overline{z}}_{\omega }=z(z\omega )$,
   where
   $z(X)$ is the permutation polynomial and
   $z\omega$ is the evaluation point shifted by a root of unity.

The prover outputs the following evaluations:

$(\overline{a},\overline{b},\overline{c},\overline{s}{\sigma }_1,\overline{s}{\sigma }_2,{\overline{z}}_{\omega })$.

Round Five

Objective
This is the last stage of PLONK's proof generation algorithm, what would be done here is to create 2 polynomials that combines all other polynomaials that has been obtain in other rounds also making use of the optimization we explored in round 4.

Procedure

$v\in F$
The linearisation polynomial

$r(X)$ aggregates all circuit constraints into a single polynomial for evaluation at

$z$:

$$r(X)=\overline{a}\overline{b}{q}_M(X)+\overline{a}{q}_L(X)+\overline{b}{q}_R(X)+\overline{c}{q}_O(X)+\text{PI}(z)+q_C(X)•\alpha [(\overline{a}+\beta z+\gamma )(\overline{b}+\beta k_{1}z+\gamma )(\overline{c}+\beta k_{2}z+\gamma )z(X)•(\overline{a}+\beta \overline{s}{\sigma }_1+\gamma )(\overline{b}+\beta \overline{s}{\sigma }_2+\gamma )(\overline{c}+\beta S_{{\sigma }_3}(X)+\gamma ){\overline{z}}_{\omega }]•{\alpha }^2[(z(X)-1)L_1(z)]•Z_H(z)[t_{\text{lo}}(X)+z^n{t}_{\text{mid}}(X)+z^{2n}{t}_{\text{hi}}(X)].$$
To prove consistency between committed polynomials and their evaluations, the prover computes two opening proof polynomials:
Opening Proof Polynomial

$W_z(X)$:

$W_z(X)=\frac{1}{X-z}(r(X)+v(a(X)-\overline{a})+v^2(b(X)-\overline{b})+v^3(c(X)-\overline{c})+v^4(S_{{\sigma }_1}(X)-{\overline{s}}_{{\sigma }_1})+v^5(S_{{\sigma }_2}(X)-{\overline{s}}_{{\sigma }_2}))$
Shifted Opening Proof Polynomial

$W_{z\omega }(X)$:

$W_{z\omega }(X)=\frac{z(X)-{\overline{z}}_{\omega }}{X-z\omega }$.
The prover commits to these polynomials:

$[W_z{]}_1:=[W_z(x)]1,[Wz\omega ]1:=[Wz\omega (x){]}_1$.
The final proof output by the prover is:

${\pi }_{\text{SNARK}}=([a{]}_1,[b{]}_1,[c]1,[z]1,[t\text{lo}]1,[t\text{mid}]1,[t\text{hi}]1,[W_z]1,[Wz\omega ]1,\overline{a},\overline{b},\overline{c},\overline{s}{\sigma }_1,\overline{s}{\sigma }_2,\overline{z}\omega ).$
The multipoint evaluation challenge u is derived for subsequent verification:
obtain

$u$ from transcript.

This ensures randomness and ties the evaluations to the transcript’s integrity.

The PLONK prover exemplifies the brilliance of modern zero-knowledge proof systems, transforming abstract mathematical principles into a robust, efficient protocol. Through its structured rounds, the prover ensures that the commitments, constraints, and evaluations are securely generated, maintaining the balance between computational feasibility and cryptographic soundness. By leveraging techniques such as polynomial commitments, blinding, and linearization, the prover creates a succinct proof that encapsulates the circuit’s correctness without revealing any sensitive details.

This step-by-step breakdown of the PLONK prover highlights not only the ingenuity of its design but also the elegance of how its components work together. From initializing the transcript to generating the final proof, each stage contributes to the protocol’s goal of scalability and universality, paving the way for a wide range of real-world applications in privacy-preserving computations and decentralized systems.