Proving without revealing
To buy a bottle of wine, you show a cashier your identity card. The cashier needs one bit — over 18, yes or no — and receives your full name, birth date, address, card number and photograph. To log in to a website, you send it your password, and the site must now protect a secret that was never its own. To show that a rollup's new state is correct, an operator could publish every transaction, which works on a public blockchain and would be unthinkable for a payroll.
Each case asks for a proof that reveals nothing except the truth of the statement. That sounds paradoxical: how can I convince you that I know a password without giving you any information about it? In 1985 Goldwasser, Micali and Rackoff showed that it is possible, and made "nothing" precise. This lesson builds that definition, the tools that achieve it, and the trick that turns it into the kind of proof a blockchain can store. Along the way we meet real failures: zero-knowledge proofs are subtle, and production systems have shipped broken ones.
A story: the coffee test
Lucía roasts coffee in Medellín. She says she can tell her washed Caturra from her honey-processed Castillo by taste alone. Her friend Tomás thinks the two taste identical, and he proposes a test. In each round he goes into the kitchen, tosses a coin out of her sight, brews the coffee the coin picks, and brings her the cup. She sips and names it. They play twenty rounds, and she is right every time.
Tomás is convinced. If the coffees really were indistinguishable, Lucía would be guessing, and twenty correct guesses in a row happen with probability , less than one in a million. Notice what Tomás did not learn: not how Lucía tells them apart, not which notes she tastes, nothing he could use to pass the test himself. He learned one fact, that she can.
Now Tomás films the twenty rounds and shows the video to his cousin Wanjiru in Nairobi. She shrugs. "You two could have agreed in advance which cup you would bring each time. Anyone could make that video." She is right: a video of a successful test can be produced by people with no tasting skill at all, simply by choosing the answers before choosing the cups. And that is the heart of the matter. Whatever Tomás saw, he could have staged by himself. The interaction convinced him, because he flipped the coins himself at the moment it mattered; but it gave him nothing he could not have produced on his own, and so it gave him no knowledge beyond the fact itself.
Analogy, not a formal construction
In the formal definition, the video is the verifier's view (everything he saw, including his own coin flips), and the person staging a fake video is the simulator. A protocol is zero-knowledge if fake videos are indistinguishable from real ones.
Simulators, and what zero knowledge means
Take an interactive proof (from the previous lesson) for statements of the form "", where the prover holds a witness (a secret that makes the statement easy to prove, such as a password, a private key or a colouring).
Definition— zero knowledge
The view of a verifier in an interaction with the honest prover is everything sees: , its own random coins, and every message it receives. The proof is zero-knowledge if for every efficient verifier strategy there is an efficient algorithm , the simulator, which given only (and no witness) outputs something indistinguishable from 's view, for every .
It is perfect, statistical or computational zero knowledge according to whether the two distributions are identical, statistically close, or indistinguishable to every efficient algorithm. If the simulator is only required for the honest verifier , the protocol is honest-verifier zero-knowledge (HVZK).
Why does this capture "learning nothing"? Anything could compute from its view after the interaction, it could equally compute from the simulator's output, which it could have produced alone, without ever meeting the prover. So the interaction added nothing to what could compute, except the conviction that . Note what the definition does not say: the simulator may cheat in ways the real prover cannot (Lucía's fake-video maker chose the answers first, a luxury the real test denies her). Simulators typically choose messages out of order, or "rewind" the verifier, which is fine because they are thought experiments run on paper, not participants in the real protocol.
Two more properties will appear constantly.
Definition— proof of knowledge
A protocol is a proof of knowledge if there is an efficient extractor that, given the ability to run (and rewind) any prover that convinces the verifier with good probability, outputs a witness . It formalises "the prover does not just know that ; it knows a witness".
Definition— commitment scheme
A commitment scheme lets a sender fix a value now and reveal it later. uses fresh randomness and outputs ; opening means revealing . It must be hiding ( reveals nothing about ) and binding (no efficient sender can open to two different values). It is the digital version of a locked box placed on the table.
Zero knowledge for every NP statement: graph 3-colouring
Is zero knowledge a curiosity of a few algebraic problems? In 1986 Goldreich, Micali and Wigderson showed it is not: every NP statement has a zero-knowledge proof, assuming commitments exist (which follows from one-way functions). They gave a proof for graph 3-colouring, which is NP-complete, so any NP statement can be translated into it (see hard problems for reductions).
The prover knows a proper 3-colouring of a graph with edge set . One round goes like this:
- The prover picks a random permutation of the three colours and recolours its colouring with it. (A proper colouring stays proper; the colour names now carry no information.)
- It commits to the colour of every vertex separately: one locked box per vertex.
- The verifier picks a random edge .
- The prover opens the boxes of and only. The verifier checks that the two colours are valid and different.
Soundness. If has no proper 3-colouring, then whatever the prover committed to, at least one edge has equal (or invalid) colours at its ends, and the verifier picks it with probability at least . Repeating rounds with fresh permutations and commitments drives the error down to , below after rounds.
Zero knowledge. In each round the verifier sees two different colours chosen uniformly by the random permutation, plus unopened boxes that, by hiding, reveal nothing. A simulator can produce that: guess an edge, commit to two random different colours at its ends and anything at all elsewhere, and if the verifier asks for a different edge, rewind and try again. The real argument needs care about cheating verifiers whose edge choice depends on the commitments, which is where hiding is used.
This protocol is a theorem, not a product: it needs many rounds and a commitment per vertex per round, so nobody proves real statements this way. But it establishes that zero knowledge is available for everything we will want to prove, and later lessons build the efficient versions.
Pedersen commitments
Let be a group of prime order with generators and such that nobody knows (for example, is derived by hashing a public string onto the group). The Pedersen commitment to with randomness is
- Perfectly hiding: for any and any message , there is exactly one with . So when is uniform, is uniform in whatever is; not even an all-powerful observer learns anything.
- Computationally binding: two openings of the same give , hence . Binding is as hard as computing that discrete logarithm.
- Additively homomorphic: . Confidential-transaction schemes use this to check that hidden input amounts equal hidden output amounts.
The program uses a toy group, the squares modulo the safe prime , which have prime order . Group elements are numbers modulo and exponents are numbers modulo (see groups).
import random
# A toy group: the squares modulo the safe prime p = 2q + 1 form a subgroup of prime order q.
# Real systems use groups of order about 2^256 (for example elliptic curves). Learning only!
p, q = 2039, 1019
g, h = 4, 9 # two generators of the order-q subgroup; nobody should know log_g(h)
def commit(m, r):
return pow(g, m % q, p) * pow(h, r % q, p) % p
rng = random.Random(42)
m, r = 25, rng.randrange(q) # commit to the message 25 with fresh randomness
C = commit(m, r)
print("commitment C =", C, " opens to 25:", C == commit(25, r), " to 26 with the same r:", C == commit(26, r))
# Hiding: for this C, EVERY message has exactly one r that opens it, so C reveals nothing about m.
openings = {msg: next(s for s in range(q) if commit(msg, s) == C) for msg in [0, 1, 25, 500]}
print("an opening of C exists for each message:", openings)
# Homomorphism: multiplying commitments adds the messages (and the randomness).
m2, r2 = 17, rng.randrange(q)
print("C(25) * C(17) == C(42):", C * commit(m2, r2) % p == commit(m + m2, r + r2))
# Binding holds only while log_g(h) is unknown. In this tiny group we can just search for it...
t = next(x for x in range(q) if pow(g, x, p) == h)
print("log_g(h) =", t)
# ...and then open C to any message we like: g^m h^r = g^(m + t r), so solve m + t r = m' + t r'.
m_fake = 999
r_fake = (r + (m - m_fake) * pow(t, -1, q)) % q
print("C also opens to 999 with r' =", r_fake, ":", commit(m_fake, r_fake) == C)The last lines are the whole security story in miniature. With , a loop finds instantly and binding is gone. In a group of order about , the best known classical attacks need about operations, which is why real commitments use such groups, and why whoever generates must provably not know its logarithm. (A large quantum computer would break binding, but not hiding: Pedersen commitments made today stay hiding forever.)
Schnorr's protocol: proving you know a discrete logarithm
Signatures and keys introduced Schnorr signatures. Underneath them sits an interactive protocol from 1989, in which a prover convinces a verifier that it knows the secret key behind a public key , without revealing .
Definition— Schnorr identification protocol
Public: a group of prime order with generator , and . The prover knows .
- Commit: the prover picks a fresh random and sends .
- Challenge: the verifier sends a random .
- Response: the prover sends .
The verifier accepts if .
Completeness is one line: . This three-move shape — commitment, challenge, response — is called a Σ-protocol, and it has two properties that make it so useful.
Theorem— Schnorr's protocol is special-sound and HVZK
- Special soundness: from two accepting transcripts and with the same commitment and , one can compute .
- Honest-verifier zero knowledge: choosing and uniformly from and setting produces transcripts with exactly the same distribution as real ones with an honest verifier.
Proof
(1) Dividing by gives , so , and is invertible because is prime.
(2) In a real transcript, is uniform, is uniform and independent of it, so is uniform and independent of ; and is then determined by . The simulator produces and uniform and independent, with determined by the same equation. The distributions are identical.
∎
Special soundness gives the proof-of-knowledge property: an extractor runs a convincing prover, then rewinds it to just after it sent , sends a different challenge, and applies (1). The simulator is the formal version of Wanjiru's objection: by choosing the challenge first it can produce valid-looking transcripts without . Both are checked below; in a group of order 11 we can compare the two distributions exactly by listing every possibility.
import random
from collections import Counter
def schnorr_round(g, p, q, x, c, k):
"""One run of Schnorr identification. Prover knows x with y = g^x.
k: the prover's fresh secret nonce; c: the verifier's random challenge."""
t = pow(g, k, p) # 1. prover commits
s = (k + c * x) % q # 3. prover responds to the challenge c
return t, c, s
def verify(g, p, q, y, t, c, s):
return pow(g, s, p) == t * pow(y, c, p) % p
def simulate(g, p, q, y, c, s):
"""The simulator: choose the challenge and response FIRST, then solve for t. No secret needed."""
t = pow(g, s, p) * pow(y, -c, p) % p
return t, c, s
# --- Exact comparison in a tiny group: squares mod 23, prime order q = 11 (toy only) ----------
p, q, g = 23, 11, 4
x = 7 # the prover's secret
y = pow(g, x, p)
real = Counter(schnorr_round(g, p, q, x, c, k) for c in range(q) for k in range(q))
fake = Counter(simulate(g, p, q, y, c, s) for c in range(q) for s in range(q))
print("real transcripts:", len(real), " simulated:", len(fake), " identical distributions:", real == fake)
print("all simulated transcripts verify:", all(verify(g, p, q, y, *tr) for tr in fake))
# --- Special soundness: two answers to one commitment reveal the secret ------------------------
p, q, g = 2039, 1019, 4
rng = random.Random(3)
x = rng.randrange(1, q)
y = pow(g, x, p)
k = rng.randrange(q) # the prover is "rewound" and answers twice with the same k
t1, c1, s1 = schnorr_round(g, p, q, x, rng.randrange(q), k)
t2, c2, s2 = schnorr_round(g, p, q, x, rng.randrange(q), k)
assert t1 == t2 and c1 != c2 and verify(g, p, q, y, t1, c1, s1) and verify(g, p, q, y, t2, c2, s2)
extracted = (s1 - s2) * pow(c1 - c2, -1, q) % q
print(f"transcripts (t={t1}, c={c1}, s={s1}) and (t={t2}, c={c2}, s={s2})")
print("extracted secret:", extracted, " true secret:", x, " match:", extracted == x)Schnorr's protocol is honest-verifier zero-knowledge; against a verifier that picks cleverly from the commitment, the simple simulator fails (it would have to guess in advance, with probability ). Restricting challenges to a small set and repeating, or the Fiat–Shamir transform below, deal with this. Σ-protocols for many other statements follow the same pattern: knowledge of an opening of a Pedersen commitment, equality of two discrete logarithms (used for verifiable decryption and verifiable random functions), and "I know the secret for one of these keys, without saying which" (the basis of ring signatures).
Fiat–Shamir: removing the verifier, and the weak-hash pitfall
An interactive proof convinces only the verifier who took part; a blockchain needs a proof that anyone can check later. In 1986 Fiat and Shamir proposed replacing the verifier's random challenge by a hash of everything said so far:
The prover computes , then , then , and publishes ; anyone recomputes and checks. The transform works for any public-coin protocol (sumcheck included), and hashing a message in as well turns Schnorr identification into the Schnorr signature of Signatures and keys, where was called and was called . The intuition is that a hash behaves like a fresh random oracle: the prover cannot predict before fixing . That intuition is formalised in the random oracle model, where Fiat–Shamir is proven secure for Σ-protocols (Pointcheval and Stern, 1996).
The fine print is in the brackets. If the hash omits the statement — the public key, the commitments, the public inputs of a circuit — then the prover can fix and first, learn , and only then choose a statement that makes the equations hold. This is the weak Fiat–Shamir transform, analysed by Bernhard, Pereira and Warinschi in 2012 after they found it in the Helios voting system. The program attacks a Chaum–Pedersen proof, which claims that and for the same , and produces an accepting proof for a pair whose logarithms differ.
import hashlib
import random
# Toy group again: squares modulo p = 2q + 1, prime order q. For learning only.
p, q = 2039, 1019
g, h = 4, 9
def H(*items):
"""Hash a list of integers to a challenge in Z_q."""
data = b"|".join(str(i).encode() for i in items)
return int.from_bytes(hashlib.sha256(data).digest(), "big") % q
# Chaum-Pedersen: prove that A = g^x and B = h^x for the SAME secret x (equal discrete logs).
def prove(x, A, B, rng, strong=True):
k = rng.randrange(q)
t1, t2 = pow(g, k, p), pow(h, k, p)
c = H(g, h, A, B, t1, t2) if strong else H(t1, t2) # strong FS hashes the statement too
return t1, t2, (k + c * x) % q
def verify(A, B, proof, strong=True):
t1, t2, s = proof
c = H(g, h, A, B, t1, t2) if strong else H(t1, t2)
return pow(g, s, p) == t1 * pow(A, c, p) % p and pow(h, s, p) == t2 * pow(B, c, p) % p
rng = random.Random(2022)
x = 321
A, B = pow(g, x, p), pow(h, x, p)
print("honest proof, strong FS:", verify(A, B, prove(x, A, B, rng)))
# The attack on WEAK Fiat-Shamir: pick the commitments and the response first, learn c, and only
# then choose a (false!) statement A, B that makes the verification equations hold.
k1, k2, s = rng.randrange(q), rng.randrange(q), rng.randrange(q)
t1, t2 = pow(g, k1, p), pow(h, k2, p)
c = H(t1, t2)
a = (s - k1) * pow(c, -1, q) % q # then g^s = t1 * (g^a)^c
b = (s - k2) * pow(c, -1, q) % q # and h^s = t2 * (h^b)^c
A_bad, B_bad = pow(g, a, p), pow(h, b, p)
forged = (t1, t2, s)
print("forged statement: log_g(A) =", a, " log_h(B) =", b, " equal?", a == b)
print("weak verifier accepts the forgery: ", verify(A_bad, B_bad, forged, strong=False))
print("strong verifier accepts the forgery:", verify(A_bad, B_bad, forged, strong=True))The forged proof "proves" a false statement, and the attacker never broke any hash or discrete logarithm. With the statement inside the hash, changing or changes , and the same trick fails.
This is not a classroom curiosity. In April 2022 Trail of Bits disclosed a family of such bugs, which it called Frozen Heart, in several open-source implementations of Girault's proof of knowledge, of Bulletproofs (traced to an under-specified transcript in the original paper) and of PlonK (public inputs missing from the hash); the affected projects were fixed before publication (disclosure). In June 2025 the Solana Foundation published a post-mortem on its ZK ElGamal Proof program, where components missing from a Fiat–Shamir transcript would have allowed forged proofs for confidential token transfers; it was patched and the program disabled for audit, with no known exploitation. The engineering rule that follows: hash everything — protocol and parameters, the full statement, and every prover message — with domain separation, and prefer transcript libraries that make omissions hard.
Zero knowledge is not succinctness
Two properties are often blurred together, even in product names:
| Property | Question it answers | Example |
|---|---|---|
| Zero knowledge | Does the proof hide the witness? | Schnorr's proof hides ; a ZK proof of age hides the birth date. |
| Succinctness | Is the proof short and fast to verify, compared with the computation? | A sumcheck transcript is tiny compared with the sum it checks. |
They are independent. The 3-colouring proof is zero-knowledge but not succinct: it grows with the graph. The sumcheck protocol of the previous lesson is succinct but not zero-knowledge: its messages leak information about . Many "zk-rollups" use succinct validity proofs with no zero-knowledge property at all, because their transaction data is public anyway; the name stuck for historical reasons. Systems that need both (private payments, private identity) take a succinct proof system and add zero knowledge, usually by masking polynomials with random blinding terms, which costs a little extra. When you read "ZK" in a product description, ask which of the two properties is actually claimed.
Applications: private payments, credentials and age
Private payments. The Zerocash design (2014), deployed as Zcash in 2016, lets a user spend a hidden coin. The prover shows, in zero knowledge, that it knows a coin commitment inside the public Merkle tree of all coins (Hashes and Merkle trees), the secret key that owns it, and a nullifier derived from it that marks it spent without saying which coin it was; and that input and output amounts balance. Observers learn that some valid coin was spent, not which, by whom, to whom, or for how much. Zcash's later Orchard protocol (2022) uses the Halo 2 proof system, which needs no trusted setup (next lesson). Other designs reach different privacy points: Monero hides senders with ring signatures and amounts with Pedersen commitments and Bulletproofs range proofs. Financial privacy is also contested; misuse for laundering stolen funds and the regulatory responses are discussed in Applications, limits and regulation.
Anonymous credentials. David Chaum proposed in 1985 that people should be able to prove things about themselves without being tracked. Modern anonymous credential schemes let an issuer (a university, a state, a bank) sign a set of attributes, and let the holder later prove statements about those attributes to any verifier, revealing only what the statement requires, with each presentation unlinkable to the others. IBM's Idemix and Microsoft's U-Prove were early systems; the BBS signature scheme, designed for exactly this kind of selective disclosure, is in standardisation at the IRTF as of 2026.
Proving age without a birth date. A credential contains a birth date signed by an issuer. To enter an age-restricted website, the holder proves: I hold a credential with a valid issuer signature, bound to a key on my device, whose birth date is at least 18 years before today. The verifier learns one bit, plus the issuer's identity. The "at least 18 years" part is a range proof on a committed number, and the signature check is a computation proved in zero knowledge. In July 2025 Google open-sourced Longfellow ZK, a library that proves such statements about existing ECDSA-signed identity documents (announcement), in connection with European age-assurance and digital-identity-wallet efforts. Deployments like this are early, and questions remain about issuers, revocation, and who controls the wallets — but they are the first large-scale uses of zero knowledge outside blockchains.
Common misconceptions
Misconception
"Zero knowledge means the data is encrypted." Encryption hides data from people without a key; zero knowledge proves a statement about data while revealing nothing beyond its truth. A ZK proof may concern data that is public (the rollup state) or that nobody but the prover will ever see.
Misconception
"Honest-verifier zero knowledge is good enough." Only if verifiers follow the protocol. A verifier who chooses challenges adaptively may learn more, as Tomás with his mystery bag would. Fiat–Shamir sidesteps this because the "verifier" becomes a hash function, which cannot be malicious in the random oracle model, and many protocols are proven fully zero-knowledge directly.
Misconception
"Fiat–Shamir is a mechanical step that cannot go wrong." It is the most common place where implementations of correct protocols become unsound: omitted public inputs, parameters or prover messages; ambiguous encodings of what is hashed; and challenges reduced modulo the wrong number. There are also theoretical limits: there exist (contrived) protocols that are secure interactively and insecure under every concrete hash function, and in 2025 such an attack was made practical against a GKR-based proof system (the frontier lesson returns to this).
Misconception
"A zero-knowledge proof reveals nothing, so the statement can be anything." The statement itself is public, and it can leak. "My balance is exactly 1,234,567" proved in zero knowledge reveals the balance. Designing what to prove is part of the privacy engineering.
Exercises
1. Zero knowledge
Warm-upHumanA protocol has a simulator that, given only the public statement, produces transcripts indistinguishable from real ones. What does this establish?
2. Zero knowledge
CoreHumanRun one round of Schnorr's protocol in the toy group of squares modulo , which has prime order , with generator . The prover's secret is , its nonce is , and the verifier's challenge is . What response (an integer from 0 to 10) does the prover send?
3. Zero knowledge
CoreHumanIn a Schnorr group of prime order , a prover answered the same commitment twice: challenge with response , and challenge with response . Both transcripts verify. What is the secret (from 0 to 10)?
4. Zero knowledge
StretchHumanThe zero-knowledge proof of 3-colouring is run on the five-vertex "house" graph of the lesson's figure, which has edges. If the graph had no proper 3-colouring, a cheating prover would survive each round with probability at most . What is the smallest number of rounds for which ?
5. Zero knowledge
CoreHumanYou implement a non-interactive Chaum–Pedersen proof that and for the same , with prover messages , and response . Which values must go into the hash that computes the challenge ? Select all that apply.
6. Zero knowledge
CoreHumanIn the coffee story, Tomás secretly buys a bag of unknown origin and brings Lucía a cup from it, asking "Caturra or Castillo?". Why does this matter for the definition of zero knowledge?
7. Zero knowledge
CoreComputationalWrite the honest-verifier simulator for Schnorr's protocol. simulate(g, p, q, y, c, s) receives the group (the subgroup of prime order q of the integers modulo p, generated by g), the public key y, and a challenge c and response s that the caller chose at random. Return a transcript (t, c, s) that the verifier accepts, , without knowing the secret .
The tests check that every simulated transcript verifies, and that over a group of order 11 the simulated transcripts have exactly the distribution of real ones.
8. Zero knowledge
StretchComputationalGeneralise Schnorr's protocol to prove knowledge of an opening of a Pedersen commitment , without revealing or , and make it non-interactive with strong Fiat–Shamir.
prove_opening(m, r, C, rng): pick random withrng.randrange(q), set , compute the challenge exactly asc = H(g, h, C, t), and return(t, s1, s2)with and .verify_opening(C, proof): recomputec = H(g, h, C, t)and check .
The toy group, H and commit are provided. The tests also try a forgery built for a verifier that forgot to hash .
Further reading and resources
- Proofs, Arguments, and Zero-Knowledge · Justin ThalerChapters 11 and 12 treat zero knowledge, Σ-protocols and Fiat–Shamir in depth.
- The knowledge complexity of interactive proof-systems · Shafi Goldwasser, Silvio Micali and Charles Rackoff · 1985
- Proofs that yield nothing but their validity, or all languages in NP have zero-knowledge proof systems · Oded Goldreich, Silvio Micali and Avi Wigderson · 1991
- How to prove yourself: practical solutions to identification and signature problems · Amos Fiat and Adi Shamir · 1986
- Efficient signature generation by smart cards · Claus-Peter Schnorr · 1991
- Non-interactive and information-theoretic secure verifiable secret sharing · Torben Pryds Pedersen · 1991The paper that introduced Pedersen commitments.
- How not to prove yourself: pitfalls of the Fiat–Shamir heuristic and applications to Helios · David Bernhard, Olivier Pereira and Bogdan Warinschi · 2012Weak versus strong Fiat–Shamir, with attacks on a real voting system.
- Coordinated disclosure of vulnerabilities affecting Girault, Bulletproofs, and PlonK · Trail of Bits · 2022The "Frozen Heart" disclosures, with follow-up posts on each system.
- Zerocash: decentralized anonymous payments from Bitcoin · Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer and Madars Virza · 2014
- Zcash protocol specification
- Security without identification: transaction systems to make big brother obsolete · David Chaum · 1985The founding vision of anonymous credentials.
- The BBS signature scheme (IRTF CFRG draft)A signature scheme designed for selective disclosure, in standardisation as of 2026.
- Longfellow ZKGoogle's open-source zero-knowledge library for proving facts about identity documents, released in 2025.