Landmark Papers

The origins of zero-knowledge proofs

This foundational paper introduced the concept of knowledge complexity in interactive proof systems, defining the relationship between the prover and verifier and formalizing zero-knowledge proofs with quadratic residuosity as an example.

First practical applications

Fiat and Shamir introduced the first practical applications of zero-knowledge proofs, including an identification scheme and a signature scheme, using the Fiat-Shamir heuristic to convert interactive proofs into non-interactive ones.

Proving NP statements in zero-knowledge

This paper demonstrated that every NP language admits a zero-knowledge proof system, providing a specific example with the graph 3-colorability problem, which could be proven without revealing any additional information.

Zero-knowledge for all languages

This work proved that every language in NP admits a zero-knowledge proof system, which was a major theoretical milestone for zero-knowledge proofs, further expanding the scope of provable languages.

Efficient zero-knowledge arguments

Kilian proposed an efficient zero-knowledge argument system that demonstrated the feasibility of practical zero-knowledge proofs for cryptographic protocols.

IP = PSPACE

Shamir showed that the complexity class IP (Interactive Polynomial time) is equivalent to PSPACE, providing a deeper understanding of the computational power of interactive proof systems.

Proof verification and approximation hardness

This paper introduced algebraic methods for proof verification and provided key insights into the hardness of approximation problems, contributing to the development of PCPs and interactive proof systems.

Efficient zero-knowledge arguments

Kilian proposed an efficient zero-knowledge argument system that demonstrated the feasibility of practical zero-knowledge proofs for cryptographic protocols.

Algebraic methods for proofs

Lund, Fortnow, and Karloff introduced algebraic methods for interactive proof systems, contributing to the development of efficient proof systems that use algebraic structures for verification.

First SNARK construction

Micali’s paper introduced the first succinct non-interactive proof (SNARK) construction, transforming probabilistically checkable proofs (PCPs) into efficient non-interactive proofs using Merkle trees.

Efficient delegation of computation

The GKR protocol introduced an interactive proof system for delegating computation with arithmetic circuits, achieving doubly-efficient proofs where both the prover and verifier run in polynomial time.

Incrementally verifiable computation

Valiant proposed the concept of incrementally verifiable computation, allowing proofs of long computations to be verified step by step, enhancing proof efficiency and scalability.

Short pairing-based SNARKs

Groth introduced a short, pairing-based non-interactive zero-knowledge argument, which became one of the first widely-used SNARK systems, particularly suitable for practical applications like blockchain.

Polynomial commitment scheme

The KZG commitment scheme introduced constant-size commitments to polynomials, which is foundational for polynomial-based proof systems like PlonK and other zk-SNARKs.

Practical SNARK construction

This paper presented a practical SNARK construction based on quadratic span programs, offering significant improvements in efficiency over previous theoretical SNARKs and laying the groundwork for later systems like Groth16.

Decentralized anonymous payment system

Zerocash introduced a decentralized anonymous payment system based on zk-SNARKs, allowing for privacy-preserving transactions in blockchain systems.

zkVM architecture

This paper introduced the concept of zkVMs, enabling the execution of arbitrary programs while generating verifiable proofs for their correctness, which became foundational for zk-rollups in blockchain systems.

GKR protocol overview

Thaler’s note provided a detailed overview of the GKR protocol, explaining how it can be used to verify computations performed by arithmetic circuits, contributing to the practical application of interactive proofs.

Verifiable computation via Pinocchio

The Pinocchio protocol provided a practical, verifiable computation framework using SNARKs, enabling secure and efficient computation delegation with cryptographic guarantees.

Efficient pairing-based SNARK

Groth’s 2016 paper optimized pairing-based SNARKs for efficiency, becoming a standard in the field due to its reduced proof sizes and improved verification times.

Post-quantum secure integrity

This paper proposed scalable, transparent, and post-quantum secure computational integrity systems using zero-knowledge proofs, advancing the field of quantum-resistant cryptographic protocols.

Reed-Solomon IOPs

The introduction of fast Reed-Solomon interactive oracle proofs (IOPs) improved the efficiency of verifiable computation protocols, enhancing the performance of zero-knowledge systems.

Introduced universal SNARK

The PlonK SNARK introduced a universal SNARK based on polynomial interactive oracle proofs, greatly enhancing the scalability and flexibility of zk-SNARKs for general applications.

STARK-friendly CPU

The Cairo CPU architecture, optimized for STARK-based proof systems, provided a Turing-complete architecture that could be efficiently proven with zero-knowledge proofs.

Recursive ZK arguments

The Nova paper introduced recursive zero-knowledge arguments, a major step forward in achieving efficient and scalable proofs for increasingly complex computations.