Zero-knowledge is one of those phrases that arrives wearing stage fog.

It is not secrecy by vibes. It is not a promise that “nothing is visible.” The verifier sees messages. The verifier checks equations. The verifier is convinced of something.

The claim is sharper:

whatever the verifier sees could have been simulated without the witness

That is the sentence to hold onto.

Goldwasser, Micali, and Rackoff introduced zero-knowledge through the idea of knowledge complexity: how much additional knowledge does a proof reveal beyond the truth of the statement?1 The simulator is the formal pressure test. If a transcript can be generated without the secret, then the transcript itself is not evidence from which the secret was learned.

The smallest useful microscope for this idea is Schnorr’s identification protocol.2 It proves knowledge of a discrete logarithm. In modern language, it is a Sigma protocol: commit, challenge, respond.

Three messages. Three properties. A surprising amount of cryptography packed into something you can still do on a napkin.

Claim on the Table

Work in a cyclic group of prime order \(q\) with generator \(g\). The prover knows a secret

\[x \in \mathbb{Z}_q\]

and publishes

\[y = g^x.\]

The statement is:

I know x such that y = g^x.

The prover should convince the verifier of this statement without sending \(x\).

Schnorr’s interactive protocol is:

  1. The prover samples a nonce \(r\) and sends \(t=g^r\).
  2. The verifier samples a random challenge \(c\).
  3. The prover sends \(z=r+cx \pmod q\).
  4. The verifier checks
\[g^z \stackrel{?}{=} t y^c.\]

Completeness is the easy part:

\[g^z = g^{r+cx} = g^r(g^x)^c = t y^c.\]

An honest prover passes.

But zero-knowledge is not the same as passing.

The Fake Transcript Is the Point

Here is the strange move. Suppose someone wants a transcript for a chosen challenge \(c\) but does not know \(x\).

They can choose a random response \(z\) first, then define

\[t = g^z y^{-c}.\]

Now the verifier’s equation holds:

\[t y^c = g^z y^{-c} y^c = g^z.\]

This fake transcript passes the verifier’s check. More importantly, under an honest verifier that chooses \(c\) uniformly, it has the same distribution as a real transcript conditioned on that challenge. In a real run, \(r\) is uniform, so \(z=r+cx\) is also uniform. The commitment is then forced by the same equation.

That is honest-verifier zero knowledge. The transcript is not a confession. It is something a simulator could have made after being told the challenge.

Sigma-protocol terminology packages this neatly:

  • completeness: honest transcripts verify;
  • special honest-verifier zero knowledge: accepting transcripts can be simulated for a given challenge;
  • special soundness: two accepting transcripts with the same commitment and different challenges reveal a witness.

Damgard’s notes on Sigma protocols make this simulator/extractor viewpoint especially clean.3

The next section is a toy lab for those three bullets.

Put Schnorr on the Stand

The lab uses a very small prime-order subgroup:

p = 1019, q = 509, g = 4

That is intentionally insecure. It is small enough that the numbers fit on the screen and large enough to show the algebra. Do not use this code, group, hash, or randomness for real cryptography.

The panels show four things:

  1. an honest Schnorr transcript;
  2. a simulated transcript that verifies without using the witness;
  3. a fork extractor that recovers \(x\) from two accepting answers to the same commitment;
  4. the soundness curve as the challenge space and repetition count change.
Prover values Verifier challenges Simulator Extractor

Educational toy only. The group is tiny, the hash is not cryptographic, and the challenge space is deliberately small so the probabilities are visible.

In the default run, the toy group has p = 1019, q = 509, and g = 4; I checked that g has order 509. With x = 137, the public key is y = 465. The honest transcript uses t = 504, c = 5, and z = 299, and it accepts. The simulator, without using x, builds an accepting transcript with t = 929 and z = 376. The fork panel changes the challenge to 7, gets z = 64, and extracts 137 back out.

The default cheating experiment reports a one-round success rate of 12.13% against the 12.50% theory for an eight-value challenge space. I also swept 576 parameter combinations across secrets, nonces, challenge sizes, challenges, and repetition counts; every honest transcript, simulated transcript, forked transcript, and extracted witness checked out.

Try these moves.

First, change Secret x. The public key changes. The honest transcript still accepts, the simulator still accepts, and the extractor still recovers the new witness.

Second, change Nonce r. The commitment changes. If the same nonce is reused under two challenges, the fork panel recovers \(x\). This is not a fake danger. Nonce reuse is exactly the kind of arithmetic mistake that breaks Schnorr-like signature systems.

Third, increase Challenge bits and Repetitions. A prover who does not know \(x\) can prepare a commitment for one challenge. If the verifier samples from \(|\mathcal C|\) possibilities, one round succeeds with probability \(1/|\mathcal C|\). Independent repetitions multiply the pain.

Fourth, move Challenge c beyond the current challenge space. The lab reduces it into range. This is mundane UI plumbing, but it echoes a real implementation requirement: challenge domains must be specified exactly.

Two Futures Break Open the Secret

The simulator explains why the transcript does not leak the witness.

The extractor explains why the proof is still meaningful.

Suppose the same commitment \(t\) has two accepting responses:

\[g^{z_1}=t y^{c_1}\]

and

\[g^{z_2}=t y^{c_2},\]

with \(c_1 \ne c_2\). Divide the equations:

\[g^{z_1-z_2}=y^{c_1-c_2}.\]

Because \(y=g^x\),

\[g^{z_1-z_2}=g^{x(c_1-c_2)}.\]

In a prime-order group, this gives

\[x = (z_1-z_2)(c_1-c_2)^{-1} \pmod q.\]

That is special soundness. If a prover can answer two different challenges for the same commitment, the witness is hiding in the fork.

This is also why the simulator is not a cheating prover. The simulator can create a transcript for a challenge it already knows. In the live protocol, the prover sends \(t\) before seeing \(c\). The order of messages matters.

The proof is a little trapdoor in time: harmless when you see one future, revealing when you see two.

The Challenge Becomes a Hash

Interactive identification is useful, but signatures and many proof systems need a non-interactive transcript. Fiat and Shamir’s classic heuristic replaces the verifier’s random challenge with a hash of the public statement, the commitment, and the message.4

In cartoon form:

\[c = H(y, t, m).\]

Then the prover publishes \((t,z)\), and the verifier recomputes \(c\) from the same public data. The transcript is now tied to the message.

The word “heuristic” matters. Security arguments usually model the hash as a random oracle, and real-world schemes need careful domain separation, group validation, nonce generation, and exact serialization. The lab’s toy hash is not even trying to be cryptographic. It is there only to show the dependency: change the message, and the challenge should change, invalidating the response unless a collision happens inside the tiny toy challenge space.

Fiat-Shamir did not remove the challenge. It made the challenge reproducible.

What the Word Does Not Promise

Zero-knowledge does not say:

no equations are checked
no information is exchanged
no assumptions are needed

It says that the verifier’s view can be reproduced without the witness, under the conditions in the definition.

For the basic Schnorr protocol, the clean simulator above is honest-verifier zero knowledge. A malicious verifier is a harder object; broader zero-knowledge definitions quantify over verifier strategies, and many real protocols use additional transformations or assumptions to get the exact security property they need.

The proof-of-knowledge side has its own conditions. The extractor argument assumes a forking ability: get two accepting answers to the same commitment under different challenges. This is not something an ordinary verifier sees in one live conversation. It is an analysis tool for explaining why a successful prover must, in a precise sense, contain the witness.

That is the lovely tension:

one transcript can be simulated
two forked transcripts can extract

A transcript is harmless enough to fake. A prover that can survive the wrong future is carrying something real.

Why This Toy Still Has Teeth

Modern zero-knowledge systems can look nothing like this little three-message exchange. They involve polynomial commitments, arithmetization, low-degree tests, elliptic curves, hash-based commitments, recursion, virtual machines, and too many acronyms to fit comfortably in a paragraph.

Still, the simulator/extractor pair keeps showing up.

The simulator says what privacy means. The extractor says what knowledge means. Fiat-Shamir says how a public challenge can be made non-interactive. Soundness amplification says why tiny challenge games become serious after enough bits.

The lab is small because the idea is small enough to hold:

the verifier checks an equation
the simulator can fake one view
the extractor breaks two views open

That is zero-knowledge with the fog removed.

  1. Shafi Goldwasser, Silvio Micali, and Charles Rackoff, “The Knowledge Complexity of Interactive Proof Systems”, SIAM Journal on Computing, 1989. ↩

  2. Claus-Peter Schnorr, “Efficient Identification and Signatures for Smart Cards”, CRYPTO 1989; related Journal of Cryptology version: “Efficient signature generation by smart cards”, 1991. ↩

  3. Ivan Damgard, “On Sigma-Protocols”, lecture notes, 2010. ↩

  4. Amos Fiat and Adi Shamir, “How To Prove Yourself: Practical Solutions to Identification and Signature Problems”, CRYPTO 1986. ↩