plonk
  • ⚛️PLONK for **mmies
  • Introduction to the PLONK protocol and 'KZG Universal Trusted setup
  • Plonkish Arithmetization
  • The PLONK Prover
  • The PLONK verifier
Powered by GitBook
On this page

The PLONK verifier

PreviousThe PLONK Prover

Last updated 1 month ago

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 [qM]1,[qL]1,[qR]1,[qO]1,[qC]1[qM]1, [qL]1, [qR]1, [qO]1, [qC]1[qM]1,[qL]1,[qR]1,[qO]1,[qC]1, permutation polynomials [sσ1]1,[sσ2]1,[sσ3]1[sσ1]1, [sσ2]1, [sσ3]1[sσ1]1,[sσ2]1,[sσ3]1, and a generator xxx.

• Proof Elements (πSNARK)(π_{SNARK})(πSNARK​):

Contains commitments [a]1,[b]1,[c]1,[z]1[a]1, [b]1, [c]1, [z]1[a]1,[b]1,[c]1,[z]1 and other elements such as [tlo]1,[tmid]1,[thi]1[tlo]1, [tmid]1, [thi]1[tlo]1,[tmid]1,[thi]1, along with evaluations in the field (a‾,b‾,c‾,sσ1‾,sσ2‾,zω)(\overline{a}, \overline{b}, \overline{c}, \overline{sσ1}, \overline{sσ2}, z_{\omega})(a,b,c,sσ1,sσ2,zω​).

• Challenges (β,γ,α,ζ,v,u)(β, γ, α, ζ, v, u)(β,γ,α,ζ,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ω]1)∈G19([a]1, [b]1, [c]1, [z]1, [tlo]1, [tmid]1, [thi]1, [Wz]1, [Wzω]1) \in G_1^9([a]1,[b]1,[c]1,[z]1,[tlo]1,[tmid]1,[thi]1,[Wz]1,[Wzω]1)∈G19​, where G1G_1G1​ is the elliptic curve group.

    • Validate that field elements (a‾,b‾,c‾,sσ1‾,sσ2‾,zω)∈F6(\overline{a}, \overline{b}, \overline{c}, \overline{sσ1}, \overline{sσ2}, z_{\omega}) \in F^6(a,b,c,sσ1,sσ2,zω​)∈F6.

    • Confirm public inputs (wi)i∈[ℓ]∈Fℓ(w_i)_{i\in[\ell]} \in F^\ell(wi​)i∈[ℓ]​∈Fℓ.

  2. Compute Challenges Challenges β,γ,α,ζ,v,uβ, γ, α, ζ, v, uβ,γ,α,ζ,v,u is 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: ZH(z)=zn−1Z_H(z) = z^n - 1ZH​(z)=zn−1 This polynomial vanishes on the roots of unity.

    • Lagrange Polynomial Evaluation: L1(z)=ω(zn−1)n(z−ω)L_1(z) = \frac{\omega(z^{n-1})}{n(z - \omega)}L1​(z)=n(z−ω)ω(zn−1)​ Evaluates the first Lagrange polynomial at zzz.

    • Public Input Polynomial: PI(z)=∑i∈[ℓ]wiLi(z)PI(z) = \sum_{i \in [\ell]} w_i L_i(z)PI(z)=∑i∈[ℓ]​wi​Li​(z)

  4. Construct rrr and Batch Polynomial Commitment [D]1[D]_1[D]1​ The verifier splits the r polynomial into constant and non-constant terms:

    • Constant Term (r0)(r_0)(r0​): r0=PI(z)−L1(z)α2−α(a‾+βsσ1‾+γ)(b‾+βsσ2‾+γ)(c‾+γ)z‾ωr_0 = PI(z) - L_1(z)\alpha^2 - \alpha(\overline{a} + β\overline{sσ1} + γ)(\overline{b} + β\overline{sσ2} + γ)(\overline{c} + γ)\overline{z}_{\omega}r0​=PI(z)−L1​(z)α2−α(a+βsσ1+γ)(b+βsσ2+γ)(c+γ)zω​

    • Non-Constant Term: Remaining terms of r(X)r(X)r(X) are grouped into the batched polynomial commitment: [D]1=a‾b‾⋅[qM]1+a‾⋅[qL]1+b‾⋅[qR]1+c‾⋅[qO]1+[qC]1+(other terms)[D]1 = \overline{a}\overline{b} \cdot [qM]1 + \overline{a} \cdot [qL]1 + \overline{b} \cdot [qR]1 + \overline{c} \cdot [qO]1 + [qC]1 + \text{(other terms)}[D]1=ab⋅[qM]1+a⋅[qL]1+b⋅[qR]1+c⋅[qO]1+[qC]1+(other terms)

  5. Compute Full Batched Polynomial Commitment [F]1[F]_1[F]1​ The verifier aggregates polynomial commitments into a single point [F]1[F]_1[F]1​, incorporating proof elements and field challenges: [F]1=[D]1+v⋅[a]1+v2⋅[b]1+v3⋅[c]1+v4⋅[sσ1]1+v5⋅[sσ2]1[F]1 = [D]1 + v \cdot [a]1 + v^2 \cdot [b]1 + v^3 \cdot [c]1 + v^4 \cdot [sσ1]1 + v^5 \cdot [sσ2]1[F]1=[D]1+v⋅[a]1+v2⋅[b]1+v3⋅[c]1+v4⋅[sσ1]1+v5⋅[sσ2]1

  6. Group-Encoded Batch Evaluation [E]1[E]1[E]1 The verifier encodes batch evaluations into another group element: [E]1=(−r0+va‾+v2b‾+v3c‾+v4sσ1‾+v5sσ2‾+uz‾ω)⋅[1]1[E]1 = \left(-r_0 + v\overline{a} + v^2\overline{b} + v^3\overline{c} + v^4\overline{sσ1} + v^5\overline{sσ2} + u\overline{z}_{\omega}\right) \cdot [1]1[E]1=(−r0​+va+v2b+v3c+v4sσ1+v5sσ2+uzω​)⋅[1]1

  7. Pairing Check The final validation step involves pairing-based checks. The verifier ensures: e([Wz]1+u⋅[Wzω]1,[x]2)=e(z⋅[Wz]1+uz‾ω⋅[Wzω]1+[F]1−[E]1,[1]2)e([Wz]1 + u \cdot [Wzω]1, [x]2) = e(z \cdot [Wz]1 + u\overline{z}_{\omega} \cdot [Wzω]1 + [F]1 - [E]1, [1]2)e([Wz]1+u⋅[Wzω]1,[x]2)=e(z⋅[Wz]1+uzω​⋅[Wzω]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.