Plonk

Plonk's most significant innovation is its universal setup ceremony. Unlike Groth16, which requires a new multi-party computation for every distinct circuit, Plonk generates a Structured Reference String (SRS) once. This single SRS can then be used to prove any computation whose circuit fits within its pre-defined size bound.

• Updatability: The SRS can be continuously updated by new participants, strengthening security over time.
• Efficiency: Developers can deploy new applications without coordinating a costly and logistically complex ceremony.
• Mechanism: The setup commits to a specific polynomial structure (using powers of tau) that is independent of the circuit's wiring.

Plonk transforms the problem of circuit satisfiability into a polynomial identity. The core protocol uses a Polynomial Interactive Oracle Proof where the prover commits to polynomials representing the circuit's gate values, wiring, and copy constraints.

• Gate Constraint: Proves that each gate (addition or multiplication) is evaluated correctly.
• Copy Constraint: Uses a permutation argument to ensure that a wire connected from one gate's output to another's input carries the same value.
• Quotient Polynomial: The prover combines all constraints into a single polynomial that must vanish on the evaluation domain if the circuit is satisfied.

A key technical breakthrough in Plonk is its method for handling circuit wiring without per-gate copy constraints. It introduces a grand product argument to prove that two sets of wire values are permutations of each other.

• Mechanism: The prover constructs a polynomial that accumulates the ratio of values from two sets. If the sets are permutations, the final product equals 1.
• Benefit: This compresses all wiring checks into a single polynomial identity, drastically reducing the prover's work compared to earlier R1CS-based systems.
• Result: The proof size and verification time remain constant regardless of the circuit's wiring complexity.

Plonk achieves highly desirable asymptotic complexity. The prover runs in O(n log n) time, dominated by Fast Fourier Transforms (FFTs) for polynomial arithmetic, and the proof size is O(1)—a constant number of group elements.

• Proof Composition: A Plonk proof typically consists of commitments to the wire polynomials, the quotient polynomial, and openings at a random challenge point.
• Verification: The verifier performs a constant number of pairing checks, making verification extremely fast (a few milliseconds).
• Comparison: While Groth16 has a smaller constant proof size, Plonk's universal setup makes it far more practical for diverse application ecosystems.

Modern Plonk implementations extend the base protocol with custom gates and lookup arguments to optimize non-arithmetic operations. Instead of decomposing a SHA-256 hash into thousands of bitwise operations, a custom gate can represent the hash function's logic more natively.

• PlonkUp: An extension that integrates a lookup argument, allowing the prover to efficiently prove that a value exists in a pre-computed table (e.g., a XOR table).
• TurboPlonk/UltraPlonk: Variants that incorporate custom gates for elliptic curve operations, bitwise logic, and range checks.
• Impact: These optimizations reduce the number of constraints (gates) required for complex statements, directly improving prover performance for real-world workloads like zkEVM execution.

Plonk's succinctness makes it ideal for recursive proof composition. The Plonk verifier algorithm itself can be encoded as an arithmetic circuit, allowing a prover to generate a proof that attests to the validity of a previous Plonk proof.

• Mechanism: The expensive part of recursion is verifying the inner proof's pairing checks. Systems like Halo2 use a cycle of elliptic curves to make this efficient.
• Application: This enables Proof Carrying Data (PCD) and Incrementally Verifiable Computation (IVC), where a single constant-size proof validates an entire chain of sequential computations.
• Use Case: Essential for blockchain rollups that need to compress thousands of transactions into a single validity proof posted on-chain.

A single, one-time trusted setup procedure that generates a structured reference string (SRS) capable of supporting any circuit up to a pre-defined maximum size. Unlike circuit-specific setups in protocols like Groth16, a universal setup allows developers to deploy new circuits without re-running the multi-party computation ceremony. The SRS contains monomial basis commitments that can be reused across all circuits bounded by the degree limit.

A cryptographic primitive allowing a prover to commit to a polynomial and later open it at specific points with a proof size independent of the polynomial's degree. Plonk uses the KZG (Kate-Zaverucha-Goldberg) commitment scheme, which relies on bilinear pairings over elliptic curves. The prover commits to the gate, permutation, and quotient polynomials, then opens them at a random challenge point to prove constraint satisfaction.

A set of mathematical equations encoding the valid execution of a computation, which a prover must satisfy to generate a valid proof. Plonk uses a unified constraint system that combines gate constraints and copy constraints into a single polynomial equation. This unified approach simplifies the arithmetization process compared to R1CS, enabling more efficient proof generation and verification.

A directed acyclic graph representing a computation as a series of addition and multiplication gates over a finite field. Plonk encodes circuits as algebraic execution traces where each row corresponds to a gate and columns represent wire values. The circuit is then transformed into a polynomial representation, enabling the use of polynomial identity testing for efficient verification.

A cryptographic transformation that converts an interactive public-coin proof into a non-interactive proof by replacing the verifier's random challenges with the output of a cryptographic hash function. Plonk applies this heuristic to generate the evaluation challenge point for the polynomial openings, making the protocol non-interactive and suitable for blockchain and decentralized applications.

A sub-protocol within a ZKP system that efficiently proves a value exists within a public table, enabling optimized verification of non-arithmetic operations like bitwise functions, range checks, and table lookups. Plonk's lookup argument, introduced in Plonkup variants, allows circuits to reference precomputed tables rather than encoding complex operations as arithmetic gates, dramatically reducing circuit size.