The PLONK Prover
Last updated
Last updated
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
{ , , , , , , , , , , } which was obtained when PLONKish arithmetization was applied to the circuit including the witness.
Objective This round aims to create the polynomials 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;
()
encode assignment vectors creating a polynomial by interpolating this matrix columns at the domain (roots of unity).
create polynomial by blinding 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;
Objective To enforce consistency across shared wires in the circuit using a permutation argument.
Procedure
Mathematical translation;
$r_7,r_8,r_9 \in F$
Procedure
This ensures that:
The prover commits to the split polynomials:
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.
Polynomials and Their Evaluations:
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
To prove consistency between committed polynomials and their evaluations, the prover computes two opening proof polynomials:
The final proof output by the prover is:
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.
poly-commit(a,b,c) ->
Compute permutation challenges and
Compute , a polynomial encoding the wiring/copy-constraint of the circuit.
Blind following the same concept use in Round One
.
Commit to the to obtain
poly_commit(z) = and append this commitment to the transcript
Objective Round three, being the most complicated and computationally intense round, the goal that is to be achieved is to create a polynomial 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 where 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.
Sample from the transcript
compute
commit to , , and and append to the transcript
Mathematical translation
The polynomial is split into smaller polynomials of degree at most :
,
where are polynomials of degree .
Random scalars are used to introduce randomness to the split polynomials:
,
,
.
.
Procedure obtain fromTranscript
The prover computes the evaluations of various polynomials at and , where is a primitive root of unity for the evaluation domain.
Wire Polynomials: representing the evaluations of the left, right, and output wires at .
Permutation Selectors: representing the evaluations of the first and second permutation selector polynomials at .
Shifted Permutation Polynomial: , where is the permutation polynomial and is the evaluation point shifted by a root of unity.
The prover outputs the following evaluations: .
The linearisation polynomial aggregates all circuit constraints into a single polynomial for evaluation at :
Opening Proof Polynomial :
Shifted Opening Proof Polynomial :
. The prover commits to these polynomials: .
The multipoint evaluation challenge u is derived for subsequent verification: obtain from the transcript.