PLONK: A Universal zk-SNARK Protocol for Efficient Verification

PLONK: A Universal zk-SNARK Protocol for Efficient Verification

PLONK (Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge) is a zk-SNARK protocol introduced by Aztec and researchers in 2019. Its distinguishing feature is a universal trusted setup that can be reused for all circuits of a given size, eliminating the need for per-circuit ceremonies. PLONK also offers efficient verification (constant time), flexible circuit design (custom gates, lookup tables), and is widely adopted in blockchain scaling solutions like zkSync, Polygon zkEVM, and other ZK-rollups.

To understand PLONK properly, it helps to be familiar with zk-SNARKs, elliptic curve pairings, and polynomial commitments.

┌─────────────────────────────────────────────────────────────────────────┐
│                              PLONK Protocol                               │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│   Key Innovations:                                                       │
│   • Universal Trusted Setup (one ceremony for all circuits)             │
│   • Constant-time verification (independent of circuit size)            │
│   • Custom gates and lookup tables (flexible constraints)               │
│   • Smaller proof size (~400 bytes)                                     │
│                                                                          │
│   Comparison with Groth16 (traditional SNARK):                          │
│   ┌───────────────────┬─────────────────────┬─────────────────────┐     │
│   │ Feature           │ Groth16             │ PLONK               │     │
│   ├───────────────────┼─────────────────────┼─────────────────────┤     │
│   │ Trusted Setup     │ Per-circuit         │ Universal (one)     │     │
│   │ Proof Size        │ ~200 bytes          │ ~400 bytes          │     │
│   │ Verification Time │ Very fast           │ Fast (constant)     │     │
│   │ Custom Gates      │ Limited             │ Yes (flexible)      │     │
│   │ Lookup Tables     │ No                  │ Yes (optimized)     │     │
│   │ Adoption          │ Zcash, early rollups│ zkSync, Polygon     │     │
│   └───────────────────┴─────────────────────┴─────────────────────┘     │
│                                                                          │
│   Universal Setup: Powers of Tau ceremony (one-time).                    │
│   Any circuit of size ≤ 2^N can use same parameters.                    │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

What Is PLONK?

PLONK is a zk-SNARK protocol that achieves universal trusted setup, constant-time verification, and flexible gate design. Unlike Groth16 which requires a separate trusted setup for every circuit, PLONK uses a single universal setup (structured reference string, SRS) that works for all circuits up to a maximum size. The protocol is based on polynomial commitments (KZG) and permutation arguments, enabling efficient verification and flexible constraint systems.

• Universal Trusted Setup (Powers of Tau): One ceremony for all circuits of a given size (e.g., 2^20 gates). No per-circuit setup required. Widely audited and participated (thousands of contributors). Toxic waste not catastrophic for new circuits.
• Constant-Time Verification: Verification time does not depend on circuit size. Proof size is constant (~400 bytes). Suitable for blockchains with variable gas costs.
• Custom Gates (Flexible Constraints): Not limited to addition and multiplication. Define custom gates (RANGE, XOR, AND, etc.). Reduces circuit size for certain operations.
• Lookup Tables (Plookup Extension): Efficiently prove that a value belongs to a table. Reduces constraints for range checks, bitwise operations, etc. Many folds reduction in proof size for common operations.

Why PLONK Matters

Traditional SNARKs (Groth16) suffer from per-circuit trusted setup. PLONK solves this and adds flexibility for real-world circuits.

• Reusable Trusted Setup (Cost Reduction): No need to rerun expensive MPC ceremonies for each circuit. New circuits can be deployed without additional ceremony. Reduces coordination overhead for ZK-rollups upgrading circuits.
• Faster Development Cycle: Deploy new circuits without trusted setup. Developers can iterate faster (important for zkEVM development). No dependency on multi-party computation participants.
• Flexible Constraints (Efficiency): Custom gates reduce proof size and prover time. Lookup tables massively reduce constraints for common operations (bitwise, range checks). PLONK circuits are often smaller than Groth16 for same computation.
• Verification Simplicity (Gas Efficient): Constant-time verification predictable gas. Popular in Ethereum rollups (zkSync, Polygon zkEVM, Scroll). Verifier smart contract efficient.
• Large Ecosystem: PLONK is the basis for many zkEVM implementations. Tools: Circom (with PLONK backend), Halo2 (PSE), Noir (Aztec). Also supported by most proving systems.

Aspect                  Groth16                     PLONK
─────────────────────────────────────────────────────────────────────────────
Trusted Setup           Per-circuit                 Universal (one time)
Proof Size              ~200 bytes                  ~400 bytes
Verification Time       Very fast                   Fast (constant)
Prover Time             Fast                        Slower (for small circuits)
Custom Gates            Limited                     Yes (flexible)
Lookup Tables           No                          Yes (Plookup)
Circuit Flexibility     Rigid (R1CS)                Flexible (custom constraints)
Ecosystem Maturity      Very high                   High (growing)
Gas for L1 Verification Lower (~150k)               Moderate (~250k)

How PLONK Works (Simplified)

1. Circuit Definition (Custom Gates)
   ────────────────────────────────────────────────────────────────────────
   Define arithmetic circuit with gates (+, *, custom, lookup tables).
   Example custom gate: out = a * b + c (polynomial constraint).

2. Arithmetization (Plonkish Constraints)
   ────────────────────────────────────────────────────────────────────────
   Convert circuit to polynomial equations.
   Each gate represented as polynomial identity.
   Enforce wiring via permutation argument (copy constraints).

3. Polynomial Commitment (KZG)
   ────────────────────────────────────────────────────────────────────────
   Prover commits to witness polynomials using KZG commitment scheme.
   Uses universal SRS (Powers of Tau).
   SRS contains powers of τ (tau secret) in G1.

4. Permutation Argument (Wiring Proof)
   ────────────────────────────────────────────────────────────────────────
   Prove that wires are connected correctly.
   Uses product of polynomials to encode permutation.
   Efficient verification with evaluation at random point.

5. Batch Evaluation (Linearization)
   ────────────────────────────────────────────────────────────────────────
   Combine multiple polynomial identities.
   Prover sends commitments to quotient polynomials.

6. Verification (Pairing Check)
   ────────────────────────────────────────────────────────────────────────
   Verifier checks pairing equation using SRS.
   Constant number of pairings (independent of circuit size).

Universal Trusted Setup (Powers of Tau)

The Powers of Tau ceremony generates a structured reference string (SRS) for PLONK. It is a one-time setup for a given circuit size bound (e.g., 2^20, 2^25, 2^30). Participants contribute random secret using multi-party computation. The SRS contains powers of τ in G1 and G2: [τ^0], [τ^1], [τ^2], ..., [τ^{N-1}] and the same powers in G2 for pairings. After ceremony, no single party knows τ (toxic waste) as long as one participant is honest. All circuits requiring up to N gates can reuse the same SRS.

τ (toxic waste) = sum of contributions from participants

SRS (Common Reference String):
  • {[τ^0]₁, [τ^1]₁, [τ^2]₁, ..., [τ^{N-1}]₁} in G1
  • {[τ^0]₂, [τ^1]₂, [τ^2]₂, ..., [τ^{N-1}]₂} in G2

Usage:
  • Prover commits to polynomial P using these powers
  • Commitment = [P(τ)]₁ = Σ P_i * [τ^i]₁
  • Verifier checks evaluations using pairings

Benefits:
  • One ceremony, many circuits
  • Participants join without coordination (Power of Tau)
  • Trust minimized (single honest participant)

Custom Gates and Lookup Tables

PLONK supports custom gates beyond standard multiplication. This reduces circuit size for specific operations.

Standard multiplication gate: a * b = c
  Constraint: q_M·a·b + q_L·a + q_R·b + q_O·c + q_C = 0
  (q_M, q_L, q_R, q_O, q_C are selectors)

Custom addition gate (q_M=0, q_L=1, q_R=1, q_O=-1, q_C=0):
  a + b - c = 0

Custom XOR gate (using bits):
  out = a XOR b (requires bit decomposition, custom constraints)

Custom range gate (value < 2^16):
  Less constraints than decomposing to bits (much cheaper)

Lookup table (Plookup):
  Proves that a value belongs to a table (e.g., is_valid_byte).
  Table: {0, 1, 2, ..., 255}
  Single constraint per lookup vs ~256 bit constraints.

PLONK in Production (zkEVM and Rollups)

PLONK is the leading proof system for zkEVM implementations due to its flexibility and universal setup.

Parameter               Value
─────────────────────────────────────────────────────────────────────────────
Gas per transaction     ~500-1000 gas (vs 21000 L1)
Throughput              2000-4000 TPS
Proof size              ~400-800 bytes
Verification time       ~50-100ms
Proving time (batch)    Minutes (optimized hardware)
Universal setup size    2^24 (16M gates)

PLONK Variants

Variant               Key Feature
─────────────────────────────────────────────────────────────────────────────
TurboPLONK            Additional custom gates (16 selectors)
UltraPLONK            Lookup tables (Plookup) integration
Halo 2 (Zcash)        Recursive proofs + PLONKish arithmetization
Kimchi (Mina)         PLONK variant with lookups and custom gates
PLONK (Aztec)         Original implementation (universal SRS)

PLONK Anti-Patterns

• Using PLONK for Tiny Circuits (Overhead): PLONK has fixed overhead (universal setup still beneficial, but proof size larger than Groth16). Groth16 is smaller for <10k constraints. Choose Groth16 for very small circuits.
• Not Leveraging Custom Gates: Writing circuits as raw R1CS misses PLONK advantage. Custom gates can reduce constraint count ~10-100x. Use lookup tables for range checks.
• Ignoring SRS Size Limit: Universal setup supports up to N constraints (e.g., 2^20). Circuits larger than maximum not supported without larger SRS. Choose SRS with sufficient capacity for growth (2^25, 2^30).
• Poor Proof Aggregation Strategy: Generating individual PLONK proofs for each block inefficient. Recursive proofs (Halo2) can aggregate many proofs into one.
• Undersized SRS for Scaling: Upgrading SRS later requires new ceremony (with same participants). Plan capacity far ahead (2x-5x margin).

Circuit Design:
□ Use lookup tables for range checks
□ Custom gates for common patterns (XOR, bit slicing)
□ Reduce number of constraints (optimize)
□ Profile proof generation time

SRS Planning:
□ Estimate maximum circuit size (N gates)
□ Use SRS capacity (2^20, 2^25, 2^30) with 2x margin
□ Participate in Powers of Tau ceremony

Proving Optimization:
□ Use GPU acceleration for MSM (multi-scalar multiplication)
□ Batch multiple proofs into one
□ Use parallel proving

PLONK Best Practices

• Use Universal Setup (SRS) with Sufficient Capacity: Participate in Powers of Tau ceremonies (or use existing well-audited SRS). Ensure SRS size (N) supports future circuit growth. Use SRS with at least 2-5x safety margin.
• Leverage Lookup Tables (Plookup): Convert range checks, arithmetic to table lookups. Use Plookup to prove membership in set. Much fewer constraints than native implementation.
• Profile Prover Time: PLONK prover slower than Groth16 for tiny circuits but similar for large. Use custom gates to reduce constraint count. Parallel proving (multithreading, GPU) for large circuits.
• Use Recursive Proofs for Aggregation: Halo2 variant supports recursive composition. Aggregate many PLONK proofs into one (amortize verification cost). Critical for rollup efficiency.
• Audit Circuit for Correctness: PLONK circuits more complex than R1CS. Formal verification for constraint correctness; test with positive and negative cases.

Requirement                         Recommended Protocol
─────────────────────────────────────────────────────────────────────────────
Single circuit, small size          Groth16
Multiple circuits, shared SRS       PLONK
Lookup tables (range, bit ops)      UltraPLONK
Recursive proof aggregation         Halo2 (PLONKish)
zkEVM (Ethereum rollup)             PLONK (zkSync, Polygon)
Small proof size priority            Groth16
Transparency (no trusted setup)      zk-STARKs, but PLONK universal

PLONK Libraries and Tooling

Frequently Asked Questions

1. What is the difference between PLONK and Groth16?
   PLONK has universal trusted setup (one ceremony for all circuits), Groth16 requires per-circuit setup. PLONK proof size is larger (~400 vs 200 bytes). PLONK supports custom gates and lookup tables (flexible). Groth16 is faster to verify (smaller gas) and faster prover for tiny circuits.
2. Is PLONK quantum-safe?
   No. PLONK relies on elliptic curve pairings (discrete log) and KZG polynomial commitments. Shor's algorithm breaks these. For post-quantum security, use STARKs or hash-based commitments (but much larger proofs).
3. What is the Powers of Tau ceremony?
   Multi-party computation to generate universal SRS. Thousands of participants contribute randomness (some may be malicious). Final parameters secure if any single participant is honest. Produces structured reference string for PLONK.
4. Can PLONK be used for zkEVM?
   Yes, most zkEVM rollups use PLONK or its variants. PLONK's custom gates and lookup tables are essential for efficient EVM opcode emulation. zkSync, Polygon zkEVM, Scroll are examples.
5. What is the difference between PLONK and UltraPLONK?
   UltraPLONK adds lookup tables (Plookup) to standard PLONK. Enable efficient range checks, bitwise operations, and other table lookups. Reduced constraint count dramatically.
6. What should I learn next after PLONK?
   After mastering PLONK, explore Halo2 for recursive proofs, KZG polynomial commitments, Plookup efficiency, Powers of Tau ceremony details, and zkEVM using PLONK.