> For the complete documentation index, see [llms.txt](https://developeruche.gitbook.io/plonk/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://developeruche.gitbook.io/plonk/the-plonk-prover.md). # 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](https://hackmd.io/@0xdeveloperuche/rkSR2_Vz1l) * `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$$ 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: $$\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. --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://developeruche.gitbook.io/plonk/the-plonk-prover.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.