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
• Proof Elements
Contains commitments
• 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
• Validate that field elements
• Confirm public inputs
Compute Challenges
Challenges
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 r and Batch Polynomial Commitment
The verifier splits the r polynomial into constant and non-constant terms:
• Constant Term
• Non-Constant Term:
Remaining terms of
Compute Full Batched Polynomial Commitment
The verifier aggregates polynomial commitments into a single point
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.