PLONK

PLONK is a universal, updatable zero-knowledge proof system designed for proving the satisfiability of arithmetic circuits. It is a type of zk-SNARK that aims to provide short proofs, fast verification, and the ability to prove different circuits without a new trusted setup for each one. A defining feature of PLONK is the use of a universal setup that can be reused across circuits and updated as new circuits are added, reducing the need for fresh trusted setups per circuit.

Key features and design choices include the use of polynomial commitments based on the KZG scheme to bind to polynomials that encode the circuit and the witness, and a permutation argument to enforce that the wiring of the circuit satisfies specified constraints across all gates. PLONK supports a wide range of gate types and can be extended with lookups to efficiently handle larger domains of values. Verifier efficiency is a focus: proofs are short and verification relies on a small, fixed number of elliptic-curve pairings, largely independent of the circuit size.

At a high level, a circuit is encoded as a set of algebraic constraints over a finite field. The prover constructs polynomials that encode the witness, selector information, and permutation constraints, commits to these polynomials with the universal setup, and then demonstrates that the polynomials satisfy the required identities at a few random evaluation points. The verifier checks these identities through the commitments and a handful of field evaluations, yielding a succinct proof.

PLONK has seen wide adoption in blockchain and privacy-preserving applications, where scalable, flexible zero-knowledge proofs are valuable. It does, however, rely on a trusted setup (albeit a universal and updatable one) and involves cryptographic primitives that require careful parameter management.