The Schnorr Zero-Knowledge Protocol

Three moves: commit, challenge, response

The Schnorr identification protocol lets a prover convince a verifier that they know a secret number x — a discrete logarithm — without ever transmitting x itself, or anything an eavesdropper could use to compute it. It runs over a cyclic group with a public generator g of large prime order q (the same kind of group used in Diffie-Hellman and DSA), and it is exactly three messages long:

setup:      public key  y = g^x mod p        (x is the prover's secret)

1. commit:   prover picks random r, sends   t = g^r mod p
2. challenge: verifier sends a random        c
3. response:  prover sends                   s = r + c*x mod q

verifier checks:   g^s  ==  t * y^c  (mod p)

live demo · repeated commit / challenge / response rounds● LIVE

The check works because s = r + c*x, so g^s = g^r * g^(c*x) = t * (g^x)^c = t * y^c exactly when the prover really used the x that matches the public key y. Anyone who doesn't know x would have to guess the challenge c in advance to fake a matching t — which they can only do with negligible probability 1/q, since c is chosen after t is already committed.

Why it's genuinely zero-knowledge

A useful proof system needs three properties: completeness (an honest prover who really knows x always convinces the verifier), soundness (a prover who doesn't know x can only fool the verifier with negligible probability, since faking it requires guessing the challenge before committing), and zero-knowledge itself — the transcript reveals nothing about x beyond the bare fact that the prover knows it. The standard argument for the third property is a simulator: given only the public key y, you can generate a fake transcript (t, c, s) that is statistically indistinguishable from a real one, simply by picking s and c first and computing t = g^s / y^c backwards. If a simulator with no access to the secret can produce transcripts indistinguishable from real ones, the real transcript cannot be leaking information about the secret either.

The discrete logarithm problem underneath it all

The whole protocol's security rests on the discrete logarithm problem: given g and y = g^x mod p, finding x is believed to be computationally infeasible for a well-chosen group, even though checking a candidate x is trivial. It is the same hard problem behind Diffie-Hellman key exchange and DSA/ECDSA signatures — Schnorr identification is, in a sense, the cleanest possible demonstration of what that hardness assumption buys you: a way to prove possession of a secret without the secret ever needing to leave the prover's machine, not even encrypted.

From identification to signatures: Fiat-Shamir

An interactive protocol needs a live verifier picking a genuinely random challenge, which is awkward for signing a document that has to be verifiable by anyone, later, without the original prover present. The Fiat-Shamir transform removes the interaction by replacing the verifier's random challenge with a hash of the commitment (and the message being signed): c = H(t, message). Because a cryptographic hash function is unpredictable in the same way a random verifier is, this turns the three-move identification protocol directly into the Schnorr signature scheme — one of the two signature algorithms (alongside ECDSA) standardised for use in Bitcoin and Taproot.

Frequently asked questions

What does zero-knowledge actually mean here?

That the transcript exchanged between prover and verifier proves the prover knows the secret x without revealing anything else about x. Formally, a simulator with no knowledge of x can produce fake transcripts statistically indistinguishable from real ones, which shows the real protocol cannot be leaking extra information — only the bare fact of knowledge is conveyed.

Why can't the verifier learn x from watching many rounds?

Each round uses a fresh random r, so each commitment t and response s is unrelated to previous rounds — the response s = r + c*x mod q is masked by a value the verifier never sees on its own. Without r, recovering x from s and c is exactly as hard as solving the discrete logarithm problem directly.

What is the Fiat-Shamir transform?

A technique that turns the interactive Schnorr identification protocol into a non-interactive signature scheme by replacing the verifier's random challenge with a hash of the commitment and the message: c = H(t, message). Because a hash function behaves unpredictably like a random challenge, the prover can compute the entire proof alone, producing a signature anyone can verify later without interaction.

Try it live

Everything above runs in your browser — open Zero-Knowledge Proof and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Zero-Knowledge Proof simulation

Zero-Knowledge Proof: The Schnorr Identification Protocol