Schnorr Signatures: The Linear Math Behind Taproot and MuSig

What It Is and the Problem It Solves

A digital signature must prove that whoever produced it knew a secret key, while revealing nothing about that key. Schnorr's scheme does this with a proof of knowledge of a discrete logarithm. Given a public key P = x·G on an elliptic-curve group of prime order n with generator G, a signer proves knowledge of x without disclosing it.

The problem it solves that ECDSA does not is linearity. ECDSA's verification equation involves a modular inverse of a per-signature value, which entangles the components non-linearly; you cannot add two ECDSA signatures and get a valid signature for the sum of the keys. Schnorr's verification is the affine relation s·G = R + e·P. Because it is linear in both the secret x and the nonce k, independent signers' partial signatures add into a single joint signature, and independent public keys add into a single aggregate key.

• One signature verifies one, two, or a thousand cooperating signers.
• The scheme is non-malleable: only one valid s exists per (R, message).
• It carries a tight security reduction to ECDLP in the random-oracle model — historically the reason it was patented, which delayed adoption until the patent expired in 2008.

How It Works, Step by Step

Fix a curve of prime order n, generator G, and a hash H modeled as a random oracle. The secret is x; the public key is P = x·G. To sign a message m:

SIGN(x, m):
  k  = random scalar in [1, n-1]      # the nonce — must be unique & secret
  R  = k · G                          # commitment point
  e  = H(R ‖ P ‖ m)  mod n            # challenge (Fiat–Shamir: hash replaces verifier)
  s  = (k + e · x)  mod n             # response
  return (R, s)                       # 32 bytes R.x + 32 bytes s = 64 bytes

VERIFY(P, m, (R, s)):
  e = H(R ‖ P ‖ m) mod n
  return  s · G  ==  R + e · P        # the linear check

The verification holds because s·G = (k + e·x)·G = k·G + e·(x·G) = R + e·P. The interactive origin is a three-move Sigma protocol: commit R, receive challenge e, respond s. The Fiat–Shamir heuristic makes it non-interactive by computing e as a hash of the commitment and message instead of getting it from a live verifier. BIP-340 fixes details: x-only (32-byte) public keys, an even-y convention, and a deterministic nonce derived by hashing the key and message so a broken RNG cannot leak the key.

Complexity and a Worked Step-Trace

Let a scalar multiplication on the curve cost one M (roughly O(log n) point additions, ~256 doublings for secp256k1). Then:

• Signing: 1 scalar mult (k·G) + hashing ⇒ 1 M. With a fixed-base precomputed table, effectively O(1) mults.
• Verifying: the check s·G − e·P = R is a 2-scalar multi-exponentiation, done with Shamir's trick in ~1.16 M rather than 2 M.
• Batch verification: n signatures verify with random-linear-combination weights in one big multi-exp, ≈ O(n / log n) effective cost — a real speedup Schnorr enables and ECDSA does not.
• Size: 64 bytes signature, 32-byte key. Space is O(1).

Worked micro-example over the tiny group Z*-style prime-order group with G, n=11, secret x=3, so P=3·G. Suppose the RNG picks k=6, giving R=6·G. Let the hash return e=4. Then s = (6 + 4·3) mod 11 = 18 mod 11 = 7. Signature is (R=6·G, s=7). Verify: s·G = 7·G; and R + e·P = 6·G + 4·(3·G) = 6·G + 12·G = 18·G = 7·G (since 18 mod 11 = 7). They match, so the signature is valid.

Where It's Used in Real Systems

Schnorr is now infrastructure, not theory:

• Bitcoin Taproot (BIP-340/341/342, activated Nov 2021): replaced ECDSA for the new Taproot output type. A single Schnorr key can commit, via a tweak, to an entire tree of alternative spending scripts (a Merkle tree of Tapscripts), so a complex smart contract and a plain payment are indistinguishable on-chain until spent.
• MuSig / MuSig2: an n-of-n multisignature protocol that aggregates all cosigners into one 32-byte key and one 64-byte signature. MuSig2 needs only two communication rounds and is secure under concurrent sessions — the flagship application of Schnorr's linearity.
• FROST: flexible round-optimized t-of-n threshold Schnorr signing, used for distributed custody.
• Ed25519 (EdDSA): the Schnorr construction over the Edwards curve Curve25519, deterministic nonces baked in. It signs SSH keys, TLS certificates, Signal, and Linux kernel module signatures.
• Cardano, Polkadot, and Lightning: use Schnorr/EdDSA-family signatures; adaptor signatures enable payment channels and atomic swaps.

Comparison to ECDSA and RSA — the Tradeoff

Versus ECDSA (which secp256k1 Bitcoin used from day one): both rest on the same elliptic-curve discrete-log problem and the same 256-bit curve, so raw security is comparable. Schnorr wins on four counts — smaller fixed 64-byte signatures, provable non-malleability, native key/signature aggregation, and efficient batch verification. ECDSA's one historical edge was that it was not patented when Bitcoin launched in 2009; Schnorr's patent expired in 2008 but tooling lagged. ECDSA's cost: a modular inverse per signature and no aggregation.

Versus RSA: RSA signatures are 256 bytes at the 112-bit security level and rely on integer factoring. Schnorr at 256-bit curves gives ~128-bit security in 64 bytes — 4× smaller and faster to sign, though RSA verification (small public exponent) is very fast.

Versus BLS signatures: BLS also aggregates and even supports non-interactive aggregation across different messages, but requires pairing-friendly curves and pairings that are slower to verify and lack a random-oracle-free proof of the same tightness. Schnorr's tradeoff: aggregation needs interaction (MuSig rounds), but verification is plain and fast.

Pitfalls, Failure Modes, and Significance

Schnorr's elegance is unforgiving of one mistake — the nonce k:

• Nonce reuse is catastrophic. Sign two messages with the same k: s₁ = k + e₁x, s₂ = k + e₂x. Subtract: x = (s₁ − s₂)/(e₁ − e₂) mod n. The secret key falls out with one division. This is the same class of bug that leaked the Sony PS3 ECDSA key. BIP-340 mandates deterministic, message-dependent nonces to eliminate it.
• Biased or low-entropy nonces leak the key over many signatures via lattice (hidden-number-problem) attacks — even a few known bits per nonce suffice.
• Naive multisig is broken by the rogue-key attack: a malicious cosigner can choose P₂ = P_forged − P₁ so the aggregate is a key it fully controls. MuSig defeats this by weighting each key with a hash of all keys before summing, and by requiring nonce commitments up front.
• Wagner's generalized birthday attack breaks insecure interactive multi-round nonce schemes; MuSig2's design specifically resists it.

The significance is architectural: by restoring linearity that ECDSA discarded, Schnorr turned signatures into a composable algebraic object. Aggregation, thresholds, blind signatures, and adaptor signatures for off-chain contracts all become one-line consequences of s·G = R + e·P.

Schnorr vs. ECDSA vs. RSA — signature schemes compared

Property	Schnorr (BIP-340)	ECDSA (secp256k1)	RSA-2048 PKCS#1
Signature size	64 bytes	70–72 bytes (DER)	256 bytes
Public key size	32 bytes (x-only)	33 bytes (compressed)	256+ bytes
Verify equation	Linear: s·G = R + e·P	Non-linear (modular inverse)	Modular exponentiation
Key aggregation / multisig	Native (MuSig2, n→1 key)	Not possible on-chain	Not possible
Security proof	Tight reduction to ECDLP (ROM)	Only under stronger assumptions	RSA / factoring
Provable non-malleability	Yes	No (s and −s both valid)	Scheme-dependent