How Zero-Knowledge Proofs Work

Zero-knowledge proofs (ZKPs) are one of the most consequential ideas in modern cryptography. They allow one party (the prover) to convince another party (the verifier) that a statement is true, without revealing any information beyond the truth of the statement itself. First formalized by Goldwasser, Micali, and Rackoff in 1985, ZKPs have evolved from a theoretical curiosity into infrastructure that underpins blockchain scaling, private transactions, and verifiable computation. This article explains the mathematics, the proof systems, and the real-world systems built on them.

The Three Properties of a Zero-Knowledge Proof

A zero-knowledge proof system must satisfy three formal properties. Every ZKP construction, from simple interactive protocols to complex SNARKs, is designed around these requirements:

Prover knows witness w proves statement x Verifier learns only that x is true proof / commitment challenge (interactive) Zero-Knowledge Proof Protocol Verifier learns nothing about witness w Completeness Soundness Zero-Knowledge

The power of zero-knowledge proofs lies in the separation between what the prover knows and what the verifier learns. The prover holds a witness — some private data that makes the statement true — and the proof convinces the verifier of the statement's truth without leaking the witness or any partial information about it.

Interactive vs Non-Interactive Proofs

The original formulation of zero-knowledge proofs was interactive: the prover and verifier exchange multiple rounds of messages. The prover sends a commitment, the verifier sends a random challenge, and the prover responds. After enough rounds, the verifier becomes convinced.

The classic pedagogical example is the "Ali Baba cave." Imagine a cave with a ring-shaped tunnel and a locked door in the middle. The prover claims to know the password. The verifier stands outside while the prover enters and takes a random path (left or right). The verifier then shouts which path the prover should emerge from. If the prover knows the password, they can always comply by unlocking the door if needed. If they don't, they can only succeed with 50% probability per round. After 128 rounds, the probability of a cheating prover succeeding is 2-128 — negligible.

Interactive proofs are impractical for most real applications because they require the verifier to be online and engaged. Non-interactive zero-knowledge proofs (NIZKs) solve this by eliminating the back-and-forth. The prover generates a single proof message that anyone can verify independently, at any time, without interaction.

The Fiat-Shamir heuristic transforms an interactive proof into a non-interactive one by replacing the verifier's random challenges with the output of a cryptographic hash function applied to the prover's commitments. Since the hash function is deterministic and unpredictable, it simulates an honest verifier's random choices. This technique is the foundation of virtually every practical ZKP system in use today, from digital signatures (which are themselves a form of NIZK) to the proof systems that power ZK-rollups.

Arithmetic Circuits: The Language of ZKPs

Before a statement can be proven in zero knowledge, it must be expressed as a mathematical structure that the proof system can operate on. Modern ZKP systems work with arithmetic circuits over a finite field. An arithmetic circuit is a directed acyclic graph where each node is either an addition gate or a multiplication gate, and the wires carry elements of a finite field Fp (integers modulo a prime p).

Any computation can be converted into an arithmetic circuit. For example, proving "I know x such that x3 + x + 5 = 35" becomes a circuit with multiplication and addition gates. The prover's witness is x = 3, and the circuit evaluates to verify the equation holds. The conversion from arbitrary programs to arithmetic circuits is called arithmetization, and the efficiency of this step heavily influences the overall performance of the proof system.

Different proof systems use different arithmetization strategies. SNARKs typically use R1CS (Rank-1 Constraint System) or Plonkish arithmetization. STARKs use AIR (Algebraic Intermediate Representation). Each approach involves tradeoffs in circuit size, prover time, and the types of operations that are efficient to express.

SNARKs: Succinct Non-Interactive Arguments of Knowledge

A SNARK (Succinct Non-interactive ARgument of Knowledge) is a proof system where the proof is extremely small (typically a few hundred bytes) and verification is fast (a few milliseconds), regardless of the complexity of the statement being proven. The "succinct" property is what makes SNARKs revolutionary: you can prove that you correctly executed a computation with billions of steps, and the verifier checks it in constant time.

The "argument" (as opposed to "proof") distinction is technical: SNARKs provide computational soundness rather than information-theoretic soundness. A computationally unbounded adversary could, in theory, forge proofs. In practice, this distinction is irrelevant because breaking the underlying cryptographic assumptions would require solving problems like the discrete logarithm that have resisted attack for decades.

Groth16

Groth16 (Jens Groth, 2016) is the most deployed SNARK for specific, fixed computations. It produces the smallest proofs of any general-purpose SNARK — just 3 group elements on a pairing-friendly elliptic curve, which encode to about 192 bytes on BN254 or about 288 bytes on BLS12-381. Verification requires 3 pairing operations, making it extremely fast.

The critical tradeoff is that Groth16 requires a trusted setup ceremony that is specific to each circuit. During the setup, a structured reference string (SRS) is generated using secret randomness (often called "toxic waste"). If anyone learns this randomness, they can forge proofs. Multi-party computation (MPC) ceremonies distribute the setup across many participants so that the system is secure as long as at least one participant honestly discards their share. Zcash's Sapling upgrade, for example, used a ceremony with 90 participants.

Groth16 uses R1CS arithmetization: the computation is expressed as a system of constraints of the form (ai . s) * (bi . s) = (ci . s), where s is the witness vector and a, b, c are coefficient vectors. The prover computes polynomial evaluations at a secret point embedded in the SRS and constructs the proof using elliptic curve pairings.

PLONK

PLONK (Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge, 2019) introduced a universal and updatable trusted setup. Unlike Groth16, the same setup ceremony works for any circuit up to a maximum size. This means you run the setup once and can use it for any program, eliminating the need for per-circuit ceremonies.

PLONK uses a different arithmetization called Plonkish, based on a gate equation of the form qLa + qRb + qOc + qMab + qC = 0, where a, b, c are wire values and q terms are selector polynomials that define the gate type. Copy constraints ensure that wires connecting different gates carry the same value, enforced through a permutation argument.

PLONK proofs are larger than Groth16 (about 400-800 bytes) and verification is somewhat slower, but the universal setup and support for custom gates make it far more flexible. Many modern ZK systems, including the proof systems used by Polygon zkEVM and Scroll, are built on PLONK variants such as HyperPlonk, UltraPlonk, and TurboPlonk.

SNARKs vs STARKs: Key Tradeoffs Property SNARKs STARKs Proof size ~200-800 B ~40-200 KB Verification ~3-5 ms ~10-50 ms Prover time Moderate Fast (hash-based) Trusted setup Required* Transparent Post-quantum No (ECC-based) Yes (hash-based) Assumptions Elliptic curves Hash functions * Some SNARKs (e.g., PLONK) use universal setup; some avoid setup entirely

STARKs: Scalable Transparent Arguments of Knowledge

STARKs (Scalable Transparent ARguments of Knowledge), introduced by Eli Ben-Sasson and collaborators at StarkWare in 2018, eliminate the trusted setup entirely. Instead of relying on elliptic curve pairings and secret structured reference strings, STARKs are built on hash functions and the FRI (Fast Reed-Solomon Interactive Oracle Proof) protocol.

The "transparent" property means that all of the randomness used in the protocol is public — derived from the Fiat-Shamir heuristic applied to hash function outputs. There is no secret ceremony, no toxic waste, and no trust assumptions beyond collision resistance of the hash function. This also makes STARKs plausibly post-quantum secure, since hash functions are not known to be vulnerable to quantum algorithms the way elliptic curve discrete logarithms are.

FRI: The Engine Behind STARKs

FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) is the core component that makes STARKs work. It proves that a committed set of values lies close to a low-degree polynomial, which is the fundamental check needed to verify computational integrity.

The FRI protocol works through iterative folding. Starting with a polynomial of degree d, the prover commits to its evaluations over a large domain. The verifier sends a random challenge, and the prover uses it to fold the polynomial into a new polynomial of degree d/2 over a domain half the size. This process repeats logarithmically many times until the polynomial is small enough to check directly. At each step, the verifier can sample and check consistency between the layers using Merkle proofs.

The tradeoff is proof size. STARK proofs are significantly larger than SNARK proofs — typically 40 to 200 kilobytes, compared to a few hundred bytes for Groth16. However, STARK provers are very fast (the core operations are FFTs and hash computations, which parallelize well on modern hardware), and proof sizes are shrinking with techniques like DEEP-FRI and Circle STARKs.

Polynomial Commitment Schemes

At the heart of most modern proof systems is a polynomial commitment scheme (PCS) — a cryptographic protocol that lets a prover commit to a polynomial and later prove evaluations at specific points. The choice of PCS largely determines a proof system's properties:

ZK-Rollups: Scaling Blockchains with Zero Knowledge

The most impactful application of zero-knowledge proofs today is ZK-rollups — layer-2 scaling solutions for blockchains like Ethereum. A ZK-rollup executes transactions off-chain, generates a ZKP that the execution was correct, and posts only the proof and compressed transaction data to the layer-1 chain. The on-chain verifier contract checks the proof in constant time, regardless of how many transactions were batched.

This achieves massive throughput improvements. Instead of every consensus node re-executing every transaction, they only verify a single cryptographic proof. A proof covering 10,000 transactions costs the same to verify on-chain as one covering 100.

ZK-Rollup Architecture Layer 2 (Off-chain) tx1, tx2, ... tx10000 Execute + state update Generate ZK proof ZK Proof ~200 bytes Layer 1 (On-chain) Verifier contract Verify proof: O(1) State root updated Compressed calldata (data availability) 10,000 transactions verified with a single proof check

Major ZK-Rollup Systems

Several production ZK-rollups are live on Ethereum mainnet, each with distinct proof system choices:

Privacy Applications

Zcash: Private Transactions

Zcash was the first major blockchain to deploy zero-knowledge proofs in production. Launched in 2016, Zcash uses ZKPs (originally Groth16, now the Orchard protocol based on Halo 2) to enable shielded transactions where the sender, receiver, and amount are all encrypted on-chain. A zero-knowledge proof attached to each shielded transaction proves that:

All of this is proven without revealing which notes are being spent, who is sending to whom, or how much is being transferred. The Zcash Sapling upgrade (2018) used Groth16 with a multi-party trusted setup ceremony. The Orchard upgrade (2022) switched to Halo 2, which uses the IPA polynomial commitment scheme and eliminates the need for a trusted setup through recursive proof composition.

Identity Verification Without Disclosure

Zero-knowledge proofs enable a fundamentally new approach to identity and credential systems. Instead of revealing your full credentials, you prove specific properties about them:

Projects like Worldcoin (proof of unique personhood via iris scanning), Polygon ID (verifiable credentials), and Semaphore (anonymous group membership and voting) are building production systems around these ideas.

ZK-EVMs and Their Type Classification

A ZK-EVM is a zero-knowledge proof system that proves correct execution of Ethereum Virtual Machine computations. The goal is to generate a ZKP that a given set of EVM transactions were executed correctly, producing a specific state transition. This is the core technology behind EVM-compatible ZK-rollups.

Vitalik Buterin proposed a classification of ZK-EVMs into types based on how closely they replicate Ethereum's execution environment. Each type represents a different tradeoff between compatibility and proving efficiency:

ZK-EVM Type Classification Full equivalence High performance Type 1 Fully Ethereum equivalent Proves entire consensus logic Hours to prove Type 2 EVM equivalent Same bytecode diff state layout Minutes to prove Type 3 Almost EVM equivalent Some precompile differences Minutes to prove Type 4 Language-level equivalent Compiles Solidity to custom VM Fast proving Taiko, PSE Scroll, Polygon Linea (interim) zkSync, StarkNet Type 1: Maximum compatibility, contracts work unmodified Type 4: Maximum speed, contracts need recompilation Most projects aim to progress toward Type 1 over time

Proving Time and Verification Costs

The practical viability of ZKP systems depends heavily on two performance metrics: how long it takes the prover to generate a proof, and how much it costs the verifier to check it.

Prover time is the bottleneck. Generating a ZK proof for a complex computation (like an EVM state transition covering thousands of transactions) requires enormous computational resources. Current ZK-rollup provers use GPU clusters and specialized hardware. Proving a single Ethereum block can take minutes to hours depending on the proof system and hardware. Key factors include:

Verification cost on-chain is what the end user indirectly pays. Groth16 verification requires a constant amount of computation (3 pairings) regardless of circuit size, costing roughly 230,000 gas on Ethereum — about $2-15 depending on gas prices. PLONK verification costs somewhat more. STARK verification costs significantly more due to larger proofs and hash-based verification, which is why STARK-based systems often use a SNARK as a "wrapper" — prove the STARK verification circuit inside a SNARK to get small, cheap-to-verify final proofs. StarkNet uses this approach, with a STARK prover off-chain and a SNARK verifier on Ethereum.

Recursive Proofs

Recursive proof composition is one of the most powerful techniques in the ZKP toolbox. The idea is straightforward: you generate a ZKP that verifies another ZKP. This creates a chain of proofs where a single final proof attests to the correctness of an arbitrary number of previous computations.

Recursive proofs enable:

The technical challenge is that the proof system's verification algorithm must be expressible as an arithmetic circuit within the same proof system. This creates a circularity that requires careful construction. For pairing-based SNARKs, verifying a proof inside a circuit requires implementing elliptic curve arithmetic and pairing operations in-circuit, which is expensive. Systems like Halo 2 (used by Zcash Orchard) solve this elegantly using the IPA commitment scheme and a pair of elliptic curves (a 2-cycle of curves) where operations on one curve can be verified efficiently using the other.

Recursive Proof Composition Proof P1 Block 1 Proof P2 Block 2 + P1 Proof P3 Block 3 + P2 ... Proof Pn Block n + Pn-1 On-chain verify 1 proof covers all blocks Each proof verifies the computation AND the previous proof

Folding Schemes: Nova and Beyond

Folding schemes represent a fundamentally different approach to recursive proof composition. Instead of generating a full proof at each step and then proving the verification of that proof inside the next step, folding schemes accumulate instances without producing intermediate proofs. The key insight is that you can "fold" two instances of a computation into one, deferring the expensive proving work until the very end.

Nova, introduced by Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla in 2022, is the foundational folding scheme. Nova works with a relaxed version of R1CS (called "relaxed R1CS") and uses a single group-based commitment scheme. At each step of an incremental computation, the prover folds the current step's instance together with the accumulated instance from all previous steps. This folding operation is extremely lightweight — it requires only a single multi-scalar multiplication of size proportional to the number of public inputs, not the circuit size.

The result is dramatically faster IVC compared to traditional recursion. Where recursive SNARKs require running the full verifier circuit at each step (which might have millions of constraints), Nova's per-step overhead is just a few hundred constraints for the folding verification. The expensive SNARK proof is generated only once, at the very end, to prove the accumulated instance.

Since Nova, several extensions have been developed:

Folding schemes are still relatively new, but they are likely to become the dominant approach for IVC in the near future because of their superior per-step prover efficiency. Projects like Lurk (a Lisp-like language for verifiable computation) and Nexus are building production systems on top of Nova.

The ZK Proving Stack

Modern ZK systems are built as layered stacks, separating concerns and allowing different teams to optimize at each level:

The modularity of this stack means that improvements at one layer propagate upward. A faster MSM implementation on GPU directly speeds up every SNARK prover that uses it. A more efficient polynomial commitment scheme benefits every proof system built on top of it.

Current Limitations and Research Frontiers

Despite remarkable progress, zero-knowledge proof systems face real limitations:

Active research areas include:

Cryptographic Foundations

The security of zero-knowledge proof systems rests on well-studied cryptographic assumptions:

The choice between these foundations depends on the application's security requirements, performance needs, and threat model. For systems that must survive the advent of large-scale quantum computers, hash-based constructions are the safest bet. For systems optimizing for proof size and verification speed today, pairing-based constructions remain dominant.

The Connection to Networking and Verification

While zero-knowledge proofs are most commonly associated with blockchains, the underlying principle — proving the correctness of a computation without revealing the inputs — has broader implications for internet infrastructure. Consider how RPKI uses cryptographic certificates to verify that a BGP route announcement is authorized. ZKPs could extend this model: a network could prove it has a valid routing policy without revealing the full policy, or prove that traffic passed through a compliant path without revealing the exact route.

More immediately, ZKPs are already connected to the infrastructure that Ethereum and other blockchains rely on. ZK-rollup provers, verifiers, and sequencers are all internet-connected services running on networks with autonomous systems, BGP routes, and the same DNS infrastructure that the rest of the internet depends on. The consensus mechanisms that secure base layers are themselves distributed systems with the same networking dependencies as any other internet service.

You can explore the network infrastructure behind major ZK-rollup systems by looking up their RPC endpoints and sequencer nodes in the looking glass to see which autonomous systems host them, what BGP routes serve their traffic, and how they are connected to the global internet.

See BGP routing data in real time

Open Looking Glass
More Articles
How Blockchain Domains Work: ENS, Unstoppable Domains, and Web3 Naming
How IPFS Works: Content-Addressed Storage
How ENS (Ethereum Name Service) Works
How the Bitcoin Network Works
How Blockchain Consensus Mechanisms Work
How the Lightning Network Works