Zero-Knowledge Proofs

A zero-knowledge proof lets a prover convince a verifier that a statement is true while revealing nothing beyond its truth — not the witness, not a hint toward it. Introduced by Goldwasser, Micali and Rackoff in 1985, the idea sat mostly in theory for twenty-five years, then became practical infrastructure: private transactions, blockchain rollups, anonymous credentials, and proofs that a computation was performed correctly without re-running it.

The three properties #

Schnorr's protocol, concretely #

The canonical example. The prover knows a discrete log $x$ with $P = xG$ (on an elliptic curve) and wants to prove it without revealing $x$:

sequenceDiagram
    participant P as Prover (knows x)
    participant V as Verifier
    P->>V: commitment R = rG, r random
    V->>P: challenge c (random)
    P->>V: response s = r + c·x
    Note over V: accept iff sG == R + cP

Check the algebra: $sG = (r + cx)G = rG + c(xG) = R + cP$ ✓

Soundness: a prover who could answer two different challenges for the same $R$ would yield $s_1 - s_2 = (c_1 - c_2)x$, revealing $x$ — so anyone who can reliably answer must actually know it. Zero-knowledge: pick $s$ and $c$ at random, set $R = sG - cP$, and you have a perfectly valid-looking transcript produced with no knowledge of $x$ — which is exactly the simulator.

Fiat–Shamir: removing the verifier #

Replace the verifier's random challenge with $c = H(R \,\|\, \text{statement} \,\|\, \text{context})$. The prover generates the challenge itself, but cannot control it, so the proof becomes non-interactive — a single message, publishable, verifiable by anyone, forever. This transform is what turns interactive proofs into signatures and into blockchain-usable artifacts.

SNARKs and STARKs #

Modern systems prove statements far larger than "I know a discrete log" — typically "I correctly executed this program", with the computation compiled into an arithmetic circuit.

Succinct is the key adjective: verification cost is independent of the size of the computation proved. Verifying that a million transactions executed correctly costs about the same as verifying one — which is precisely what makes blockchain rollups work.

Where it is used #

• Private transactions — Zcash shielded transfers, Monero range proofs.
• Rollups — zkSync, StarkNet, Scroll post a validity proof so an L1 verifies an L2 batch without re-execution.
• Anonymous credentials — prove "over 18" or "citizen of X" without revealing identity or date of birth; the basis of privacy-preserving digital identity work.
• Verifiable computation — prove an outsourced job ran correctly.
• Proof of solvency — an exchange proves reserves exceed liabilities without publishing the balance sheet.