The Schnorr Protocol
If you have ever used a password, a cryptocurrency wallet, or logged in with a modern authentication system, you have relied on ideas closely related to the Schnorr protocol. Introduced by Claus-Peter Schnorr in 1989, it is the standard way to prove — in zero knowledge — that you know a secret number without revealing that number to anyone.
Where the Ali Baba Cave uses a physical metaphor and graph coloring uses puzzle structure, Schnorr works directly with the mathematics of modular exponentiation: the same operations that power Diffie–Hellman key exchange, ElGamal encryption, and digital signatures. It is short (three messages), efficient, and easy to implement — which is why variants of it appear in Bitcoin Taproot, EdDSA, and countless other systems today.
By the end of this page you will understand exactly what Peggy sends, what Victor checks, and why the transcript reveals nothing about Peggy's secret — even though every message is computed from it.
The Problem
Start with a simple idea from everyday arithmetic. Pick a prime $p$ and a number $g$. Repeatedly multiply $g$ by itself, but always keep the result mod $p$:
$$g,\; g^2,\; g^3,\; g^4,\; \ldots \pmod p$$Each value in this sequence lives in the multiplicative group of units $U(p)$: the set $\{1, 2, \ldots, p-1\}$ with operation multiplication mod $p$. When $p$ is prime, every nonzero residue has a multiplicative inverse, so $U(p)$ is a group. (This is not the additive group $\mathbb{Z}/p\mathbb{Z}$ — that group uses addition mod $p$ and includes $0$.)
The discrete logarithm problem asks the reverse question: if someone shows you $y = g^x \bmod p$ with $y \in U(p)$, can you figure out the exponent $x$?
For small numbers you can guess and check. For the large primes used in real cryptography (hundreds of digits long), no efficient algorithm is known. That one-way direction — easy to compute $g^x$, hard to recover $x$ — is exactly what makes public-key cryptography work.
The Setup
Two parties, same names as in our other protocols:
- Peggy (Prover) — knows the secret exponent $x$ where $y \equiv g^x \bmod p$ and $y \in U(p)$. Think of $x$ as her private key.
- Victor (Verifier) — knows the public parameters $(p, g, y)$ and wants convincing evidence that Peggy knows $x$, without learning $x$ itself.
Everyone agrees on $p$ and $g$ ahead of time. Peggy (or anyone) can compute $y = g^x \bmod p$ from her secret $x$ and publish $y$. From that point on, $y$ is public — but $x$ stays hidden. The Schnorr protocol lets Peggy prove knowledge of $x$ without revealing $x$.
The Protocol
Each round has four steps and three messages from Peggy (one commitment, one response). Victor sends a single challenge in the middle. The entire proof fits on a napkin:
- Peggy commits to a random value $t = g^r \bmod p$.
- Victor sends a random challenge $c$.
- Peggy responds with $s = r + cx \bmod q$.
- Victor checks that $g^s \equiv t \cdot y^c \bmod p$ in $U(p)$.
The magic is in step 4: the check ties together Peggy's commitment $t$, her response $s$, and the public value $y$ — but the algebra never exposes $x$ on the wire.
Public Parameters
Before the protocol begins, everyone agrees on:
- A large prime $p$.
- The multiplicative unit group $U(p) = \{1, 2, \ldots, p-1\}$ under multiplication mod $p$. All group elements $g$, $y$, and $t$ live here.
- A generator $g \in U(p)$ — an element whose repeated powers cycle through a subgroup $\langle g \rangle = \{g, g^2, g^3, \ldots\} \subseteq U(p)$.
- The subgroup order $q = |\langle g \rangle|$ — how many distinct powers of $g$ appear before the cycle repeats. If $g$ generates all of $U(p)$, then $q = p - 1$.
- Peggy's public value $y = g^x \bmod p \in U(p)$, computed from her secret exponent $x$.
Exponents such as $x$, $r$, $c$, and $s$ are ordinary integers taken mod $q$ — they belong to the additive group $\mathbb{Z}_q$, not to $U(p)$. The protocol multiplies group elements in $U(p)$ and adds exponents in $\mathbb{Z}_q$.
In real systems $p$ and $q$ are hundreds of bits long. Our demo uses $p = 23$ so you can follow every calculation by hand.
Step 1 — Commit
Peggy picks a fresh random number $r$ (called a nonce, for "number used once") and computes:
$$t = g^{r} \bmod p$$She sends $t$ to Victor. This is her commitment — a sealed envelope that hides $r$ but binds her to a specific value before Victor asks any questions.
Why randomness matters: if Peggy always used the same $r$, Victor could eventually learn information about $x$ by comparing transcripts across rounds. A fresh $r$ every round is essential for zero-knowledge.
Victor sees $t$ but cannot work backwards to find $r$ — that would require solving a discrete logarithm, which is assumed to be hard.
Step 2 — Challenge
Victor picks a random challenge $c \in \mathbb{Z}_q$ (equivalently, $c \in \{0, 1, \ldots, q-1\}$) and sends it to Peggy.
The order of operations is critical. Victor's challenge must come after Peggy's commitment. If Peggy could see $c$ before choosing $r$, a cheater without knowledge of $x$ could simply pick $r$ and $s$ first, then set $t = g^s \cdot y^{-c} \bmod p$ to pass the check — without ever knowing $x$. Committing first removes that cheat.
Step 3 — Response
Peggy computes and sends:
$$s = r + c \cdot x \bmod q$$Read this as: "take the nonce $r$, add $c$ copies of the secret $x$, and reduce mod $q$." The response $s$ looks like random noise to Victor — it mixes the secret $x$ with the fresh random $r$, and Victor does not know either one individually.
Notice that $x$ never appears on its own in any message. Only this masked combination $r + cx$ is ever transmitted.
Step 4 — Verify
Victor accepts the proof if and only if:
$$g^{s} \;\stackrel{?}{=}\; t \cdot y^{c} \bmod p$$Why does this work? Expand both sides using Peggy's honest values:
$$g^{s} = g^{r + cx} = g^{r} \cdot g^{cx} = \underbrace{g^{r}}_{= t} \cdot \underbrace{(g^{x})^{c}}_{= y^{c}} = t \cdot y^{c}$$Every step is ordinary exponent algebra. If Peggy is honest and knows $x$, the check always passes. If she is cheating and does not know $x$, she cannot produce a valid $s$ for a random $c$ she did not anticipate — except with probability at most $1/q$ per round.
Try It Yourself
The demo below walks through a complete Schnorr round with numbers small enough to verify by hand. You play both roles: set Peggy's secret parameters, commit a nonce, choose Victor's challenge, and run the verification yourself.
- Setup — pick $p$, $g$, and Peggy's secret $x$; watch $y = g^x \bmod p$ update live.
- Commit — choose or randomize the nonce $r$; preview $t = g^r \bmod p$ before sending.
- Challenge — pick Victor's challenge $c$ from the quick buttons or type your own.
- Verify — see whether $g^s \equiv t \cdot y^c \bmod p$ holds in $U(p)$.
Try setting $x$ to a wrong value and watch verification fail — that is soundness in action. Then reset, use the correct $x$, and confirm the check passes without Victor ever learning $x$.
Edit the parameters below, then click Begin Round.
We show x to you (the reader) so you can follow the math. Victor only sees y. Try a wrong x to watch verification fail.
Figure 4. Interactive simulation of the Schnorr protocol. Edit parameters, step through each phase, and inspect the modular arithmetic at every stage. Peggy's secret $x$ is visible to the reader but never transmitted to Victor. Protocol by Claus-Peter Schnorr, 1989.
Why Is This Zero-Knowledge?
A valid zero-knowledge proof must satisfy three properties. Schnorr is one of the cleanest examples because each property maps directly to a step in the protocol.
Completeness — Honest Provers Always Succeed
If Peggy truly knows $x$, the verification equation always holds. We showed above that $g^{s} = t \cdot y^{c}$ follows directly from the definition of $s$. There is no random chance involved on Peggy's side — an honest prover with the correct secret convinces an honest verifier every single time.
This is the easy direction. Completeness says the protocol is useful: people who actually know the secret can prove it.
Soundness — Cheaters Get Caught
Now suppose Peggy does not know $x$. She picks some commitment $t$ and waits for Victor's challenge $c$. To pass verification she needs:
$$g^{s} = t \cdot y^{c} \bmod p$$Without knowing $x$, she cannot solve for a valid $s$ after seeing a random $c$ — unless she got lucky and guessed $c$ correctly before committing. Since $c$ is chosen uniformly from $\mathbb{Z}_q$, the probability of guessing correctly is at most $1/q$ per round.
Repeating the protocol shrinks the cheater's survival probability exponentially. After $k$ independent rounds:
$$P(\text{cheater not caught after } k \text{ rounds}) \;\leq\; \left(\frac{q-1}{q}\right)^{\!k}$$In our demo with $q = 22$, you need many rounds to reach high confidence — which is why the confidence bar climbs slowly. In production, $q$ is roughly $2^{256}$, so a single round already makes cheating impossible in practice.
Zero-Knowledge — Victor Learns Nothing
This is the subtle and important property. After a successful round, Victor holds the transcript $(t, c, s)$. Does this tell him anything about $x$?
No. Here is the standard argument. A simulator — a program with no access to Peggy's secret — can produce a fake transcript that looks identical to a real one:
- Pick random $c$ and $s$.
- Compute $t = g^{s} \cdot y^{-c} \bmod p$.
- Output $(t, c, s)$.
This simulated transcript passes Victor's check by construction, and its distribution is identical to a real interaction. Because Victor could have generated the same-looking evidence himself — without ever talking to Peggy — the real conversation conveys zero information about $x$ beyond the fact that Peggy likely knows it.
Intuitively: the random nonce $r$ acts like a one-time pad masking $x$ inside the response $s = r + cx$. Each round uses a fresh mask, so no amount of transcript data adds up to reveal the secret.
| Protocol | What is proved | Per-round soundness error |
|---|---|---|
| Ali Baba Cave | Knowledge of a password | $1/2$ |
| Graph Coloring | Valid 3-colouring exists | $(m-1)/m$ |
| Sudoku ZKP | Valid Sudoku solution | $26/27$ |
| Schnorr | Knowledge of discrete log | $(q-1)/q \approx 1$ for small $q$ |
From Interactive Proof to Digital Signature
The Schnorr protocol requires back-and-forth: Peggy commits, Victor challenges, Peggy responds. Real systems often need a non-interactive proof — a single message that anyone can verify offline, without Victor present.
The Fiat–Shamir transform achieves this by replacing Victor's random challenge with a hash of the commitment (and whatever message is being signed):
$$c = H(t \,\|\, \text{message})$$The hash function $H$ acts as a virtual Victor — it produces a challenge that Peggy cannot predict before committing to $t$, as long as $H$ behaves like a random oracle. Peggy publishes $(s, c)$ as a Schnorr signature. Anyone who knows the public key $y$ can verify it with the same check $g^{s} \stackrel{?}{=} t \cdot y^{c}$.
This construction is the basis of Schnorr signatures in Bitcoin Taproot, Ed25519 (EdDSA), and many other modern schemes. The proof of knowledge becomes a proof of identity: "whoever signed this message knows the private key $x$."
How Many Rounds?
In the interactive protocol, Victor repeats the proof until his confidence is high enough. With challenge space $\mathbb{Z}_q$, each round independently catches a cheater with probability $1/q$. The table below uses $q = 22$ (matching our demo with $p = 23$):
| Rounds ($k$) | Soundness error $\left(\tfrac{q-1}{q}\right)^k$ | Verifier confidence |
|---|---|---|
| 1 | 95.5% | 4.5% |
| 10 | 63.0% | 37.0% |
| 50 | 10.0% | 90.0% |
| 100 | 1.0% | 99.0% |
| 200 | 0.01% | 99.99% |
Notice how slowly confidence grows with small $q$ — try it in the demo above. This is exactly why production systems use enormous challenge spaces: with $q \approx 2^{256}$, a single Fiat–Shamir signature round provides more security than billions of interactive rounds with $q = 22$.