Schnorr Signatures and Σ-Protocols: The Simplest Zero-Knowledge Proof

This article has three layers:

1. The intuition: a three-step conversation that is convincing yet reveals nothing
2. Real-world use: Bitcoin Taproot, MuSig2, Ed25519
3. The mathematics: the protocol, soundness (the extractor), zero knowledge (the simulator), Fiat–Shamir and a worked example

Layer 1: The Intuition

1.1 Proving you know a password without saying it

You want to prove to a guard that you know the combination to the company safe, without telling him the combination. The Schnorr protocol offers a three-step conversation:

• Why it is convincing: the prover must fix $R$ before seeing the challenge. Without knowing $x$, they could only try to guess the challenge, and the challenge space is so huge that a correct guess is almost impossible.
• Why it reveals nothing: in the response $s = k + cx$, $x$ is "covered" by a random number $k$, so $s$ looks like a uniformly random number.

1.2 From conversation to signature

The conversation needs a verifier online to set the question. Fiat and Shamir's idea: let a hash function set the question, with $c = \mathrm{Hash}(R, \text{message})$. A hash's output can't be predicted, so the effect is the same as an honest verifier. The prover can now generate $(R, s)$ alone, and anyone can check it afterwards. This is a digital signature.

Layer 2: Real-World Use

• Bitcoin Taproot (BIP 340, activated in 2021): introduced Schnorr signatures on secp256k1.
• MuSig2: the Schnorr signatures of several people can merge into one ordinary signature, which looks on-chain exactly like a single-person transaction, saving space and improving privacy. It works because Schnorr's response $s$ is linear in the private key: $s_1 + s_2 = (k_1 + k_2) + c(x_1 + x_2)$.
• FROST: a threshold signature protocol for Schnorr, using Shamir's secret sharing to achieve "any 3 of 5 people can sign".
• Ed25519 (EdDSA): used by SSH, Signal, Tor and many blockchains. It is a variant of Schnorr in which the random $k$ is instead generated deterministically from the private key and message hash.

Layer 3: The Mathematics

3.1 The protocol

Let $G = \langle g \rangle$ be a cyclic group of prime order $q$ (a subgroup of $\mathbb{Z}_p^\times$ or an elliptic curve group), with private key $x \in \mathbb{Z}_q$ and public key $y = g^x$.

1. Commit: pick a random $k \in \mathbb{Z}_q$ and send $R = g^k$;
2. Challenge: the verifier sends a random $c \in \mathbb{Z}_q$;
3. Respond: send $s = k + cx \bmod q$;
4. Verify: $g^s \stackrel{?}{=} R \cdot y^c$.

Correctness: $g^s = g^{k + cx} = g^k (g^x)^c = R\, y^c$.

3.2 Soundness: if you can answer two questions, you must know $x$

Suppose a prover can answer two different challenges $c \neq c'$ for the same $R$, giving $s, s'$. Then

$$g^{s} = R\,y^{c},\quad g^{s'} = R\,y^{c'} \ \Rightarrow\ g^{s - s'} = y^{c - c'} \ \Rightarrow\ x = \frac{s - s'}{c - c'} \bmod q.$$

So anyone who "can fool the verifier" can in fact compute $x$. This is called special soundness, and the procedure that computes $x$ is called the extractor. It uses the fact that $q$ is prime, so $c - c'$ is invertible in $\mathbb{Z}_q$.

3.3 Zero knowledge: an identical conversation without knowing $x$

The simulator works backwards: first pick random $s$ and $c$, then let $R = g^s y^{-c}$. These three numbers satisfy the verification equation, and their distribution is exactly the same as a real conversation ($s$ and $c$ are uniformly random, and $R$ is determined by them).

Since someone who doesn't know $x$ can produce transcripts with the same distribution, a real conversation can't reveal anything about $x$. This is how zero knowledge is defined. (Strictly speaking, the Schnorr protocol is "honest-verifier zero knowledge".)

3.4 The Fiat–Shamir transform: becoming a signature

Replace the challenge with $c = H(R \,\|\, y \,\|\, m)$:

• Signature: $(R, s)$ or $(c, s)$, where $s = k + cx$;
• Verification: recompute $c$ and check $g^s = R\,y^c$.

In the random oracle model, forging a signature is equivalent to solving the discrete logarithm.

3.5 A worked example

Summary