Zero-Knowledge Proofs

Why ZKPs matter

• Privacy-preserving authentication. Prove "I am over 18" without revealing your birth date; prove "I have a valid ID" without showing the ID. Microsoft's ION DID, EU's eIDAS 2.0 wallets (rolling out 2026), and W3C Verifiable Credentials all use ZKP-based selective disclosure.
• zk-Rollups. Ethereum L2s (zkSync, StarkNet, Polygon zkEVM, Scroll) batch ~10000 transactions per block, prove validity with a single zk-SNARK posted to L1, and slash gas costs by 50–100x. Daily zk-Rollup transaction volume crossed 5 million in late 2025.
• Blockchain scaling. Beyond rollups, zk-proofs enable validium (off-chain data + on-chain proof), volition (user picks per tx), and zkPorter modes. They turn "execute and replicate everywhere" into "execute once, verify everywhere" — the only known path to Visa-scale on-chain throughput.
• Identity verification. Worldcoin uses ZKPs so an iris-scan-derived ID can vouch for personhood without leaking the iris template. Anon Aadhaar lets Indian citizens prove they hold a valid Aadhaar without revealing the underlying number.
• Anonymous credentials. Tor's Walking Onions and Privacy Pass use ZKP-based attestation tokens. Cloudflare issues these to skip CAPTCHAs without linking sessions.
• Confidential transactions. Zcash shielded pools, Tornado Cash mixers, Monero's range proofs (Bulletproofs) — all use ZKPs to hide amounts while proving conservation of value (no inflation, no double-spend).
• ML model verification. Emerging field of zkML proves "this output came from running model M on input x" without revealing M (proprietary weights) or x (private user data). EZKL, ezkl-rust, and Aztec's Noir are active projects.

The three formal properties

• Completeness. If the statement is true and both parties follow the protocol, the verifier accepts with probability 1 (or overwhelming probability). An honest prover with a valid witness always convinces an honest verifier.
• Soundness. If the statement is false, no cheating prover can convince an honest verifier — except with negligible probability ε. For interactive protocols, soundness error decays exponentially with rounds: 50% per round in the cave example becomes 2^(-20) after 20 rounds. For zk-SNARKs, soundness comes from cryptographic hardness assumptions; ε ≈ 2^(-128).
• Zero-knowledge. The verifier learns nothing beyond the validity of the statement. Formalized via simulator: there exists an efficient algorithm S that, given just the statement (not the witness), produces a transcript indistinguishable from a real prover-verifier interaction. If S can fake the proof without knowing the secret, the real proof can't be teaching the verifier anything about the secret.
• Argument vs proof. A proof is sound against unbounded provers (information-theoretic). An argument is sound only against polynomial-time provers (computational). Most modern systems are arguments: zk-SNARK = "Succinct Non-interactive ARgument of Knowledge". The 'K' adds extractability — a successful prover must "know" a witness in a formal sense.

Schnorr ID — a real ZKP with concrete numbers

The Schnorr identification protocol proves knowledge of a discrete log without revealing it. Public: prime p, generator g, public key y = g^x mod p (where x is Peggy's secret).

• Round 1 — Commit. Peggy picks random r, sends t = g^r mod p to Victor.
• Round 2 — Challenge. Victor picks random challenge c (e.g. 128-bit), sends to Peggy.
• Round 3 — Response. Peggy computes s = r + c·x mod (p-1), sends s.
• Verify. Victor checks g^s ≡ t · y^c (mod p). If equal, accept.
• Why it's zero-knowledge. Given any (t, c, s) satisfying the verification, a simulator can pick c, s first and compute t = g^s · y^(-c) — same distribution as the real protocol. So the transcript reveals nothing.
• Why it's sound. If a cheating prover answers two different challenges c1, c2 to the same t, then s1 - s2 = (c1 - c2)x, so x = (s1 - s2)(c1 - c2)^(-1). Knowledge extractor recovers the secret.
• Fiat-Shamir transform. Make non-interactive by setting c = H(g, y, t) — the verifier's "challenge" becomes a hash. This is exactly how Schnorr/EdDSA signatures work; the signature is a non-interactive ZKP of knowledge of the private key.

How a zk-SNARK is built

• Step 1 — Express computation as a circuit. Compile the program ("I know x such that hash(x) = h") into an arithmetic circuit over a finite field. Each gate is addition or multiplication; each wire holds a field element.
• Step 2 — R1CS or Plonkish. Encode the circuit as a Rank-1 Constraint System: each gate becomes ⟨a, w⟩ · ⟨b, w⟩ = ⟨c, w⟩ for vectors a, b, c and witness w. Modern systems use Plonkish constraints (custom gates, lookups) for efficiency.
• Step 3 — QAP or polynomial commitment. Convert the constraint system to polynomials over a finite field. The prover commits to the witness polynomials using KZG (with trusted setup) or FRI (transparent, hash-based).
• Step 4 — Prove. Apply Fiat-Shamir to derive challenges from the transcript, evaluate polynomials at challenge points, produce a succinct proof. Groth16 proof: 3 group elements (~128 bytes total). PLONK proof: ~9 group elements (~400 bytes). STARK proof: 50–200 KB.
• Step 5 — Verify. A few pairings or hash checks — milliseconds. The cost gap matters: proving might take seconds to hours for a complex circuit, while verification is constant or logarithmic in circuit size.

Major ZKP libraries and their use

• circom + snarkjs. Domain-specific language for arithmetic circuits, compiles to Groth16. Used by Polygon ID, Iden3, Tornado Cash. ~250000 GitHub stars across the ecosystem.
• arkworks. Rust libraries for curve arithmetic, SNARK frameworks (Marlin, Groth16, PLONK). Used by Aleo, Anoma, Mina.
• halo2. No trusted setup, recursive composition. Used by Zcash (Orchard), Scroll, Filecoin's storage proofs, Penumbra.
• StarkWare's stone / cairo. Cairo VM for STARK-provable computation; powers StarkNet (Ethereum L2 with ~10 TPS settled and growing) and StarkEx (used by dYdX v3, Sorare, Immutable X).
• RISC Zero. Prove arbitrary RISC-V program execution with STARK; "zkVM" model lets developers write Rust and prove its execution.
• Bulletproofs. No trusted setup, smaller proofs (~1–2 KB) but linear verification cost. Used by Monero for range proofs since 2018, dramatically shrinking transaction sizes.

Common misconceptions

• "ZKPs are always interactive." Original Goldwasser-Micali-Rackoff was interactive, but the Fiat-Shamir transform converts any public-coin interactive protocol into non-interactive by replacing the verifier's challenges with H(transcript). Schnorr signatures, Groth16, and PLONK are all non-interactive.
• "ZKPs are computationally cheap." No — proving is expensive. Generating a zk-SNARK for a non-trivial circuit (e.g. a Bitcoin-block validity proof) takes seconds to hours and gigabytes of RAM. Verification is fast; proving is not. Hardware acceleration (Cysic ASICs, GPU MSM) is an active area.
• "Zero-knowledge means information-theoretic zero." Most practical ZKPs are computational zero-knowledge — a polynomial-time verifier learns nothing. Statistical and perfect zero-knowledge exist but are rarer. A super-polynomial adversary might extract some information.
• "Trusted setup is always a backdoor." If even one of the multi-party-computation participants destroys their share of the toxic waste, the system is secure. Powers of Tau ceremonies have thousands of contributors making this assumption robust. Universal setups (PLONK) need only one ceremony for many circuits.
• "zk-SNARKs are quantum-safe." Most aren't. Pairing-based SNARKs (Groth16, KZG-PLONK) fall to Shor. STARKs and hash-based SNARKs (Halo 2 with IPA) are believed post-quantum.
• "Anyone can verify in constant time." Succinct verification scales as O(1) or O(log n) in circuit size, but still depends on output size and constants. STARK verifiers do tens of hash evaluations per proof.

Performance numbers (3 GHz x86_64, 2025 software)

• Groth16 (BN254 curve). Proof size 128–192 bytes; verify ~3 ms (3 pairings); prove time ~1 s per ~100k constraints; trusted setup required per circuit.
• PLONK (BN254). Proof size ~400 bytes; verify ~5 ms; universal trusted setup; better proving for repeated structure.
• Halo 2 (Pasta curves). Proof size ~1–10 KB; verify ~10 ms; no trusted setup; supports recursive composition.
• STARK (e.g. StarkNet's stone). Proof size 50–200 KB; verify ~50–500 ms; no trusted setup; quantum-safe.
• Bulletproofs. Proof size ~1–2 KB; verify O(n) — 100 ms+ for typical range proofs.
• End-to-end zk-Rollup. Batching 1000 transactions: prove ~30 seconds on GPU; verify ~5 ms on Ethereum L1; gas cost split across 1000 users → ~$0.001/tx vs ~$1/tx native.