8 min read
On this page

Zero-Knowledge Proofs

Interactive Zero-Knowledge Proofs

Zero-Knowledge Proof Prover-Verifier Workflow

A zero-knowledge proof allows a prover P to convince a verifier V that a statement x is in a language L without revealing any information beyond the validity of the statement.

Three properties:

  • Completeness: If x in L, honest prover convinces honest verifier with overwhelming probability
  • Soundness: If x not in L, no cheating prover can convince honest verifier except with negligible probability
  • Zero-knowledge: The verifier learns nothing beyond x in L. Formalized via simulation: there exists a PPT simulator S that produces transcripts indistinguishable from real interactions

Flavors of zero-knowledge:

  • Perfect ZK: Simulated and real transcripts are identically distributed
  • Statistical ZK: Distributions are statistically close (negligible statistical distance)
  • Computational ZK: Distributions are computationally indistinguishable

Fundamental results:

  • Every language in NP has a computational ZK proof (Goldreich-Micali-Wigderson, based on OWF)
  • IP = PSPACE (Shamir), and all of IP has ZK proofs
  • ZK proofs exist for all of NP under standard assumptions

Proof of knowledge (PoK): Stronger than proof of membership. There exists an extractor E that, given rewinding access to the prover, extracts a witness w. The knowledge error kappa is the probability a prover without a witness can still convince.

Sigma Protocols

Three-move (commit-challenge-response) honest-verifier ZK protocols with special structure.

General structure:

  1. Commitment: Prover sends first message a (commitment)
  2. Challenge: Verifier sends random challenge e from challenge space
  3. Response: Prover sends response z

Properties required:

  • Completeness: (a, e, z) with valid witness always verifies
  • Special soundness: Given two accepting transcripts (a, e, z) and (a, e', z') with e != e', a witness can be extracted
  • Honest-verifier ZK (HVZK): There exists a simulator producing valid-looking transcripts

Schnorr Protocol

Proof of knowledge of discrete logarithm: given g, h = g^x in group G of prime order q, prove knowledge of x.

  1. Prover: choose random r, send a = g^r
  2. Verifier: send random e in Z_q
  3. Prover: send z = r + e*x mod q
  4. Verifier: accept iff g^z = a * h^e

Special soundness: From (a, e, z) and (a, e', z') with e != e': x = (z - z') / (e - e') mod q.

HVZK simulator: Choose random z, e, set a = g^z * h^{-e}. Produces valid transcripts.

Generalizations: Sigma protocols exist for representations (knowledge of multiple discrete logs), AND/OR compositions (prove knowledge of one of several witnesses), range proofs, and general algebraic relations.

NIZK: Non-Interactive Zero Knowledge

Fiat-Shamir Transform

Converts a Sigma protocol to a non-interactive proof in the random oracle model by replacing the verifier's challenge with a hash of the commitment:

e = H(x || a)

The prover computes a, derives e, computes z, and outputs the proof pi = (a, z). The verifier recomputes e = H(x || a) and checks the verification equation.

Security: In the ROM, Fiat-Shamir preserves soundness (extraction via forking lemma / rewinding the random oracle) and zero-knowledge (simulator programs the random oracle).

Caution: Fiat-Shamir is insecure in the standard model for certain protocols (Goldwasser-Kalai). Careful domain separation and inclusion of the statement in the hash are essential for security.

Fiat-Shamir for General NP

Applied to any Sigma protocol for NP-complete languages (e.g., Hamiltonian cycle via GMW). In practice, this is rarely done directly; specialized protocols are preferred.

Correlation-intractability: A framework for proving Fiat-Shamir sound in the standard model for specific classes of relations, using hash functions from lattice assumptions.

zk-SNARKs

Succinct Non-interactive Arguments of Knowledge: proofs are short (constant or polylogarithmic size) and fast to verify (sublinear in computation size).

Key properties:

  • Succinctness: Proof size O(1) or O(log n), verification time O(|x| + polylog(n))
  • Non-interactive: Single message from prover to verifier (after optional setup)
  • Argument: Computationally sound (not information-theoretically)
  • Knowledge: Extraction of witness via rewinding or algebraic techniques

Groth16

The most widely deployed zk-SNARK (Zcash, many blockchain applications).

Setup: Trusted setup generates a structured reference string (SRS) specific to the circuit. The SRS contains encrypted evaluations of a polynomial at a secret point tau. If tau is leaked, soundness is broken ("toxic waste").

Proof structure: Based on quadratic arithmetic programs (QAP). The computation is compiled into a system of rank-1 constraints (R1CS): for each gate, (a_i . w) * (b_i . w) = (c_i . w) where w is the witness vector. This is converted to polynomial form and checked via pairings on elliptic curves.

Performance:

  • Proof size: 3 group elements (~128-192 bytes)
  • Verification: 3 pairings + public input processing (milliseconds)
  • Prover: O(n log n) exponentiations (seconds to minutes for large circuits)
  • Trusted setup: per-circuit (ceremony required for each new circuit)

PLONK (Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge)

Key innovation: Universal and updatable SRS. One trusted setup works for any circuit up to a maximum size.

Arithmetization: Uses a permutation argument (grand product check) to enforce copy constraints between wires, replacing R1CS with a custom gate framework. The core polynomial identity checked via Kate-Zaverucha-Goldberg (KZG) polynomial commitments.

Custom gates: PLONK supports application-specific gates (e.g., elliptic curve addition, hash functions) that reduce circuit size for common operations.

Variants: TurboPLONK (custom gates), UltraPLONK (lookup arguments via Plookup), HyperPLONK (multilinear polynomial commitments), and fflonk (fewer proof elements).

zk-STARKs

Scalable Transparent Arguments of Knowledge (Ben-Sasson et al.).

Key properties:

  • Transparent: No trusted setup. Uses only hash functions (public randomness).
  • Post-quantum: Security based on collision-resistant hashing, not elliptic curves or pairings.
  • Scalable: Prover time quasi-linear O(n polylog n), verifier time O(polylog n).
  • Proof size: O(polylog n) -- larger than SNARKs (typically 50-200 KB vs <1 KB).

FRI (Fast Reed-Solomon Interactive Oracle Proof)

The core polynomial commitment scheme in STARKs.

Protocol: Proves that a function f (evaluated on a domain D) is close to a polynomial of degree < d.

  1. Split f into even and odd parts: f(x) = f_even(x^2) + x * f_odd(x^2)
  2. Verifier sends random alpha
  3. Prover commits to g(y) = f_even(y) + alpha * f_odd(y) (degree halved)
  4. Recurse until degree is constant (direct check)

Soundness: Each round reduces degree by 2. Cheating requires the committed function to be far from low-degree, which is detected with high probability via random sampling.

Complexity: log(d) rounds, each with Merkle tree commitment. Proof size O(log^2 d * lambda) where lambda is security parameter.

Bulletproofs

Short proofs without trusted setup, based on the discrete logarithm assumption (Pedersen commitments).

Key application: Range proofs -- proving v in [0, 2^n) for a committed value v = g^v * h^r. Proof size: O(log n) group elements (vs O(n) for naive approaches).

Inner product argument: Core technique. Prove that <a, b> = c for committed vectors a, b. Recursive halving reduces the proof to O(log n) elements.

Performance: Proof size ~700 bytes for 64-bit range proofs. Verification: O(n) exponentiations (slower than SNARKs). No trusted setup required.

Aggregation: Multiple range proofs can be aggregated with only O(log(k*n)) additional elements for k proofs.

Bulletproofs+: Improved version with ~15% shorter proofs via weighted inner product argument.

Recursive Composition and IVC

Incrementally Verifiable Computation (IVC)

Prove that a computation z_n = F(F(...F(z_0)...)) was correctly executed, with the proof updated incrementally at each step.

Core idea: At step i, produce proof pi_i that:

  1. z_i = F(z_{i-1})
  2. pi_{i-1} was a valid proof for step i-1

This requires the SNARK to verify its own proofs inside the circuit -- recursive verification.

Recursive SNARKs

Challenge: The SNARK verifier must be expressible as a circuit small enough for the prover to handle efficiently.

Approaches:

  • Cycle of curves (Pasta curves: Pallas/Vesta): Two elliptic curves where the scalar field of one equals the base field of the other. Enables efficient recursive verification by alternating between curves. Used in Halo 2, Mina Protocol.
  • Accumulation/folding schemes (Nova): Instead of verifying the full proof at each step, accumulate claims into a single "running instance" that is checked only at the end. Nova folds R1CS instances with O(1) overhead per step. SuperNova extends to non-uniform computations.
  • Proof aggregation: Combine multiple proofs into one (SnarkPack, Groth16 aggregation).

Practical Systems

  • Halo 2 (Zcash): Recursive proof composition without trusted setup using inner product arguments + polynomial commitments on the Pasta curve cycle
  • Nova/SuperNova: Folding-based IVC with minimal per-step overhead. Particularly efficient for repeated computation of the same function
  • SP1/RISC Zero: zkVMs that prove correct execution of RISC-V programs. Combine STARKs for fast proving with SNARKs for succinct final proofs (STARK-to-SNARK wrapper)

Applications

  • Blockchain: Privacy-preserving transactions (Zcash), rollups (zkSync, StarkNet, Polygon zkEVM), identity verification
  • Authentication: Password-authenticated login without sending passwords
  • Compliance: Proving regulatory compliance (KYC/AML) without revealing underlying data
  • Verifiable computation: Cloud computing verification, ML model inference proofs
  • Voting: Proving vote validity without revealing the vote