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 trusted setup 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 these rounds, we would be understanding how the PLONK proof is generated; As the protocol progresses, we would be creating some polynomials and also for polynomial mathematical relationships which would be examined and sealed(polynomial 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, these polynomials are expressions of the computational trace of the circuit's execution given this witness;

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

• initialize the Transcript with some circuit binding values, this is to improve the soundness of the protocol (CommonPreprocessedInput). Note this transcript could be Merlin, Fiat Shamir, and so on.

• Compute random field elements, this would be used for the blinding_factors; ($r_1,r_2,r_3,r_4,r_5,r_6$)

• encode assignment vectors $a',b',c'$ creating a polynomial by interpolating this $T$ matrix columns at the domain $H$ (roots of unity).

• create polynomial $a,b,c$ by blinding $a',b',c'$ polynomials using the blinding factors created above, this is important to ensure the protocol is "Zero Knowledge". learn more about the concept of blinding polynomials 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_1X + r_2)Z_H + a'$

$b = (r_3X + r_4)Z_H + b'$

$c = (r_5X + r_6)Z_H + c'$

poly-commit(a,b,c) -> $[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 polynomial encoding the wiring/copy-constraint 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$

$(β, γ) ∈ F$

$$z(x) = (b_7X^2 + b_8X + 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^*(2n+j)\beta + \gamma) }$$

poly_commit(z) = $[z]_1$ and append this commitment to the transcript

Round Three

Objective Round three, being the most complicated and computationally intense round, the goal that is to be achieved is to create a polynomial $t$ that encodes all information the circuit is comprised of alongside the witness and commit to it. This would not be as straight forward as the last rounds because the degree of the polynomial is going to be $3n+5$ where $n$ is the number of gates, this would break because the trusted setup ceremony was not done to handle this number od gates. A clever solution to handle this is to break the polynomials in 3 before committing 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 ∈ F$

$\alpha ∈ 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) + b{10}X^n$,

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

$t_{\text{hi}}(X) := t^{\prime}{\text{hi}}(X) - b{11}$.

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, \quad [t{\text{mid}}]1 := [t{\text{mid}}(x)]1, \quad [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 cheaper.

Procedure obtain $\zeta$ fromTranscript

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: $\bar{a} = a(z), \quad \bar{b} = b(z), \quad \bar{c} = c(z),$ representing the evaluations of the left, right, and output wires at $z$ .
2. Permutation Selectors: $\bar{s}{\sigma_1} = S{\sigma_1}(z), \quad \bar{s}{\sigma_2} = S{\sigma_2}(z),$ representing the evaluations of the first and second permutation selector polynomials at $z$ .
3. Shifted Permutation Polynomial: $\bar{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: $(\bar{a}, \bar{b}, \bar{c}, \bar{s}{\sigma_1}, \bar{s}{\sigma_2}, \bar{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 combine all other polynomials that have been obtained in other rounds also making use of the optimization we explored in round 4.

Procedure

$v ∈ F$

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

$$r(X) = \bar{a} \bar{b} q_M(X) + \bar{a} q_L(X) + \bar{b} q_R(X) + \bar{c} q_O(X) + \text{PI}(z) + q_C(X)•\alpha \Big[ (\bar{a} + \beta z + \gamma)(\bar{b} + \beta k_1 z + \gamma)(\bar{c} + \beta k_2 z + \gamma) z(X) • (\bar{a} + \beta \bar{s}{\sigma_1} + \gamma)(\bar{b} + \beta \bar{s}{\sigma_2} + \gamma)(\bar{c} + \beta S_{\sigma_3}(X) + \gamma) \bar{z}_\omega \Big] • \alpha^2 \Big[(z(X) - 1)L_1(z)\Big] • Z_H(z) \Big[t_{\text{lo}}(X) + z^n t_{\text{mid}}(X) + z^{2n} t_{\text{hi}}(X)\Big]$$

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} \Bigg( r(X) + v (a(X) - \bar{a}) + v^2 (b(X) - \bar{b}) + v^3 (c(X) - \bar{c}) + v^4 (S_{\sigma_1}(X) - \bar{s}{\sigma_1}) + v^5 (S{\sigma_2}(X) - \bar{s}{\sigma_2}) \Bigg)$

Shifted Opening Proof Polynomial $W{z\omega}(X)$:

$W_{z\omega}(X) = \frac{z(X) - \bar{z}_\omega}{X - z\omega}$. The prover commits to these polynomials: $[W_z]_1 := [W_z(x)]1, \quad [W{z\omega}]1 := [W{z\omega}(x)]1$.

The final proof output by the prover is:

$$\pi{\text{SNARK}} = \big([a]_1, [b]_1, [c]1, [z]1, [t{\text{lo}}]1, [t{\text{mid}}]1, [t{\text{hi}}]1, [W_z]1, [W{z\omega}]1, \bar{a}, \bar{b}, \bar{c}, \bar{s}{\sigma_1}, \bar{s}{\sigma_2}, \bar{z}\omega\big).$$

The multipoint evaluation challenge u is derived for subsequent verification: obtain $u$ from the 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.