Zero Knowledge
Key Glossary Terms
Essential vocabulary for this topic
Arithmetic Circuit
expertA mathematical circuit representation of computation using arithmetic constraints for zero-knowledge proof systems.
Bulletproofs
expertA non-interactive zero-knowledge proof system known for compact range proofs without a trusted setup.
Circuit
advancedA formal representation of the computation or constraints that a zero-knowledge prover must demonstrate were satisfied.
Groth16
expertA widely used zk-SNARK construction that creates very small proofs and fast verification but requires a trusted setup.
Halo
expertA family of zero-knowledge techniques enabling recursive proof composition without a conventional trusted setup.
PLONK
expertA universal and updatable zk-SNARK framework that can support many circuits with one structured reference setup.
Research Papers
Academic and industry research
Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
Abhiram Kothapalli, Srinath Setty, Ioanna Tzialla
Nova is a novel recursive zero-knowledge proof system designed to efficiently verify an arbitrary number of computations. It builds upon the concept of recursive proofs, allowing a proof of a computation to itself be part of a subsequent computation, thus enabling the verification of an unbounded number of steps. The key innovation in Nova is its use of a 'folding scheme' which combines multiple instances of a computation into a single, smaller instance. This folding process is executed within a zero-knowledge framework, specifically using a variant of the Nova protocol that relies on the PLONK proof system. Nova achieves a constant-time overhead for each step of the recursion, independent of the complexity of the computation being verified. This makes it exceptionally well-suited for scaling blockchains by enabling efficient batching and verification of off-chain computations. The system's ability to reduce large computation chains into a single verifiable proof with minimal overhead marks a significant advancement in the scalability and efficiency of zero-knowledge proofs for distributed ledgers.
PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge
Ariel Gabizon, Zachary J. Williamson, Oana Ciobotaru
This paper introduces PLONK (Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge), a new type of universal and updatable zero-knowledge proof system. Unlike previous SNARKs that often required custom circuits for each computation, PLONK introduces a generic circuit structure based on arithmetic circuits and permutation arguments. The core innovation lies in its ability to use a single trusted setup for all computations, significantly reducing the overhead for developers who no longer need to generate new setups for each new smart contract. The system leverages Lagrange polynomial bases and a permutation argument to efficiently prove the correct execution of arbitrary computations. PLONK achieves quadratic scaling in the size of the statement and logarithmic scaling in the size of the witness, making it a practical choice for various blockchain applications requiring efficient and verifiable computation. Its universality and updatability make it a foundational contribution to the field of zero-knowledge proofs, paving the way for more flexible and scalable privacy-preserving technologies in Web3.
An Incomplete Guide to zk-Rollups
Vitalik Buterin
Published in 2021, Vitalik Buterin's 'An Incomplete Guide to zk-Rollups' provides an accessible yet comprehensive explanation of zero-knowledge rollup (zk-rollup) technology as a Layer 2 scaling solution for blockchains, primarily Ethereum. The report details how zk-rollups bundle numerous transactions off-chain, generate a cryptographic proof (typically using zk-SNARKs or zk-STARKs) to verify their validity, and then submit this proof along with compressed transaction data to the main blockchain (Layer 1). This process significantly reduces the computational and storage burden on the Layer 1, thereby increasing transaction throughput and lowering fees. The 'incomplete' nature of the guide acknowledges the evolving landscape of ZK-proofs and rollup designs. The paper highlights the technical nuances, trade-offs, and potential future developments of zk-rollups, positioning them as a crucial technology for achieving blockchain scalability without compromising security.