The PLONK verifier
Last updated
Last updated
The PLONK (Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge) verification algorithm is a cornerstone of modern zk-SNARKs, enabling succinct, non-interactive proofs of arbitrary computations. In this blog, we’ll break down the PLONK verification algorithm step by step, demystifying its inner workings.
At a high level, PLONK verification ensures that the proof generated by the prover is valid for a specific computation. The verifier performs various checks, leveraging cryptographic commitments and field operations to validate the integrity of the proof without needing to re-execute the computation.
Before diving into the steps, let’s clarify the inputs and mathematical tools involved:
• Verifier Preprocessed Input:
Preprocessed elements include commitments to selector polynomials , permutation polynomials , and a generator .
• Proof Elements :
Contains commitments and other elements such as , along with evaluations in the field .
• Challenges :
Generated deterministically from the proof and public input.
Validate Proof Components The verifier starts by checking the structural validity of the proof elements:
• Ensure , where is the elliptic curve group.
• Validate that field elements .
• Confirm public inputs .
Compute Challenges Challenges is derived from the proof, public inputs, and common reference string (CRS). These challenges provide randomness and ensure security.
Evaluate Polynomials Several critical polynomial evaluations are computed:
• Zero Polynomial Evaluation: This polynomial vanishes on the roots of unity.
• Lagrange Polynomial Evaluation: Evaluates the first Lagrange polynomial at .
• Public Input Polynomial:
Construct and Batch Polynomial Commitment The verifier splits the r polynomial into constant and non-constant terms:
• Constant Term :
• Non-Constant Term: Remaining terms of are grouped into the batched polynomial commitment:
Compute Full Batched Polynomial Commitment The verifier aggregates polynomial commitments into a single point , incorporating proof elements and field challenges:
Group-Encoded Batch Evaluation The verifier encodes batch evaluations into another group element:
Pairing Check The final validation step involves pairing-based checks. The verifier ensures:
This pairing equation confirms the consistency of all evaluations.
• Batched Evaluations: Combines multiple checks into a single equation, reducing computation.
• Scalability: Independent of circuit size, making it ideal for large computations.
• Zero-Knowledge: The verifier learns nothing beyond the validity of the proof.
The PLONK verification algorithm showcases the power of cryptographic techniques to enable succinct and efficient proofs. By leveraging polynomial commitments, batched evaluations, and pairings, PLONK provides a secure, scalable solution for validating computations in zk-SNARKs. Understanding this algorithm not only deepens our appreciation for modern cryptography but also paves the way for exploring advanced applications in decentralized systems.