Understand PLONK: The PLONK verifier

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.

What is PLONK Verification?

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.

Key Preliminaries

Before diving into the steps, let’s clarify the inputs and mathematical tools involved:
• Verifier Preprocessed Input:
Preprocessed elements include commitments to selector polynomials

$[qM]1,[qL]1,[qR]1,[qO]1,[qC]1$, permutation polynomials

$[s\sigma 1]1,[s\sigma 2]1,[s\sigma 3]1$, and a generator

$x$.
• Proof Elements

$({\pi }_{SNARK})$:
Contains commitments

$[a]1,[b]1,[c]1,[z]1$ and other elements such as

$[tlo]1,[tmid]1,[thi]1$, along with evaluations in the field

$(\bar{a},\bar{b},\bar{c},\overline{s\sigma 1},\overline{s\sigma 2},z_{\omega })$.
• Challenges

$(\beta ,\gamma ,\alpha ,\zeta ,v,u)$:
Generated deterministically from the proof and public input.

Step-by-Step Breakdown

1. Validate Proof Components
   The verifier starts by checking the structural validity of the proof elements:
   • Ensure

   $([a]1,[b]1,[c]1,[z]1,[tlo]1,[tmid]1,[thi]1,[Wz]1,[Wz\omega ]1)\in G_1^9$, where
   $G_1$ is the elliptic curve group.
   • Validate that field elements
   $(\bar{a},\bar{b},\bar{c},\overline{s\sigma 1},\overline{s\sigma 2},z_{\omega })\in F^6$.
   • Confirm public inputs
   $(w_i{)}_{i\in [\ell ]}\in F^{\ell }$.

2. Compute Challenges
   Challenges

   $\beta ,\gamma ,\alpha ,\zeta ,v,u$ are derived from the proof, public inputs, and common reference string (CRS). These challenges provide randomness and ensure security.

3. Evaluate Polynomials
   Several critical polynomial evaluations are computed:
   • Zero Polynomial Evaluation:
   

   $Z_H(z)=z^n-1$
   This polynomial vanishes on the roots of unity.
   • Lagrange Polynomial Evaluation:
   
   $L_1(z)=\frac{\omega (z^{n-1})}{n(z-\omega )}$
   Evaluates the first Lagrange polynomial at
   $z$.
   • Public Input Polynomial:
   
   $PI(z)=\sum _{i\in [\ell ]}{w}_i{L}_i(z)$

4. Construct r and Batch Polynomial Commitment

   $[D]1$
   The verifier splits the r polynomial into constant and non-constant terms:
   • Constant Term
   $(r_0)$:
   
   $r_0=PI(z)-L_1(z){\alpha }^2-\alpha (\bar{a}+\beta \overline{s\sigma 1}+\gamma )(\bar{b}+\beta \overline{s\sigma 2}+\gamma )(\bar{c}+\gamma ){\bar{z}}_{\omega }$
   • Non-Constant Term:
   Remaining terms of
   $r(X)$ are grouped into the batched polynomial commitment:
   
   $[D]1=\bar{a}\bar{b}\cdot [qM]1+\bar{a}\cdot [qL]1+\bar{b}\cdot [qR]1+\bar{c}\cdot [qO]1+[qC]1+\text{(other terms)}$

5. Compute Full Batched Polynomial Commitment

   $[F]1$
   The verifier aggregates polynomial commitments into a single point
   $[F]1$, incorporating proof elements and field challenges:
   
   $[F]1=[D]1+v\cdot [a]1+v^2\cdot [b]1+v^3\cdot [c]1+v^4\cdot [s\sigma 1]1+v^5\cdot [s\sigma 2]1$

6. Group-Encoded Batch Evaluation

   $[E]1$
   The verifier encodes batch evaluations into another group element:
   
   $[E]1=(-r_0+v\bar{a}+v^2\bar{b}+v^3\bar{c}+v^4\overline{s\sigma 1}+v^5\overline{s\sigma 2}+u{\bar{z}}_{\omega })\cdot [1]1$

7. Pairing Check
   The final validation step involves pairing-based checks. The verifier ensures:
   

   $e([Wz]1+u\cdot [Wz\omega ]1,[x]2)=e(z\cdot [Wz]1+u{\bar{z}}_{\omega }\cdot [Wz\omega ]1+[F]1-[E]1,[1]2)$
   This pairing equation confirms the consistency of all evaluations.

Why PLONK Verification is Efficient

• 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.