In 2021, the Bitcoin network activated Taproot, the most significant upgrade since SegWit. At its cryptographic heart lies the Schnorr signature scheme—a elegant algorithm that predates ECDSA yet offers superior properties.
Schnorr signatures were invented by Claus-Peter Schnorr in the 1980s, but a patent prevented their widespread adoption. The patent expired in 2008, and Bitcoin's BIP-340 brought Schnorr to the world's most valuable blockchain.
In this chapter, we present Schnorr signatures as specified in BIP-340, explaining both the mathematics and the design decisions that make this scheme particularly suited for Bitcoin.
8.1 Why Schnorr?
Before diving into the mathematics, let us understand why Bitcoin adopted Schnorr signatures alongside ECDSA rather than replacing it entirely.
Advantages of Schnorr over ECDSA
- Provable security: Schnorr has a formal security proof in the random oracle model, reducing to the ECDLP. ECDSA's security proof is more complex and less tight.
- Linearity: Schnorr signatures are linear, enabling key aggregation and multi-signatures. Multiple parties can combine their public keys and signatures into single values indistinguishable from ordinary ones.
- Non-malleability: Unlike ECDSA, Schnorr signatures are inherently non-malleable.
- Efficiency: Fixed 64-byte signatures (vs. variable ~71-73 bytes for DER-encoded ECDSA). Batch verification is also possible.
- Simplicity: The algorithm is conceptually simpler, with fewer edge cases.
8.2 The Core Idea: A Zero-Knowledge Proof of Knowledge
At its heart, a Schnorr signature is a non-interactive zero-knowledge proof that the signer knows the discrete logarithm of their public key. The signer proves they know d (where Q = dG) without revealing d itself.
Definition 8.1 (Interactive Schnorr Protocol)
The interactive version (for understanding) works as follows:
- Commitment: Prover chooses random k, sends R = kG
- Challenge: Verifier sends random e
- Response: Prover sends s = k + ed
- Verify: Verifier checks sG = R + eQ
Why verification works
sG = (k + ed)G = kG + edG = R + e(dG) = R + eQ
8.3 The Fiat-Shamir Transform
Digital signatures require non-interactivity: the signer produces the signature alone, without a verifier providing a challenge. The Fiat-Shamir transform achieves this by deriving the challenge from a hash.
Definition 8.2 (Fiat-Shamir Heuristic)
To convert an interactive protocol to a signature scheme, replace the random challenge e with a hash:
e = H(R || message)
The hash acts as a "virtual verifier" providing an unpredictable challenge derived from the commitment and the message being signed.
Binding to the Message.
Including the message in the challenge hash binds the signature to that specific message. Any attempt to use the same signature for a different message would produce a different e, invalidating the verification equation.
8.4 BIP-340: Schnorr for Bitcoin
BIP-340 specifies Schnorr signatures for Bitcoin, making several design decisions that optimize for this use case.
Definition 8.3 (BIP-340 Key Format)
Public keys in BIP-340 are 32 bytes: just the x-coordinate. The y-coordinate is implicitly chosen to be even.
If the full point (x, y) has odd y, we instead use the negation (x, p-y) which has even y.
Why x-only Public Keys?
Using only the x-coordinate saves 1 byte per public key (32 vs. 33 bytes for compressed keys). More importantly, it simplifies key aggregation protocols since there's no need to track y-coordinate parity through aggregation.
Definition 8.4 (BIP-340 Tagged Hash)
To prevent hash collisions between different contexts, BIP-340 uses tagged hashes:
H_{tag}(x) = SHA256(SHA256(tag) || SHA256(tag) || x)
The tag is prepended twice (64 bytes total) to align with SHA256's block size, enabling precomputation optimizations.
8.5 The BIP-340 Signing Algorithm
Algorithm 8.1 (BIP-340 Schnorr Signing)
Sign(d, m):
// Ensure private key produces even-y public key
1. Compute P = dG
2. If y(P) is odd, set d = n - d // Negate if needed
3. Let p = x(P) // x-coordinate (public key)
// Generate deterministic nonce
4. Let a = bytes(d) // 32 bytes
5. Let t = a XOR H_aux(aux_rand) // Optional auxiliary randomness
6. Let rand = H_nonce(t || p || m)
7. Let k' = int(rand) mod n
8. If k' = 0, fail
// Compute R and ensure even y
9. Let R = k'G
10. If y(R) is odd, set k = n - k', else k = k'
11. Let r = x(R) // x-coordinate of R
// Compute challenge and signature
12. Let e = int(H_challenge(r || p || m)) mod n
13. Let s = (k + ed) mod n
// Return 64-byte signature
14. Return bytes(r) || bytes(s)
Even Y-Coordinates.
BIP-340 requires that both the public key P and the nonce point R have even y-coordinates. This is achieved by negating the corresponding scalar when necessary. The benefit is that signatures only need to encode x-coordinates, saving space and simplifying arithmetic.
8.6 The BIP-340 Verification Algorithm
Algorithm 8.2 (BIP-340 Schnorr Verification)
Verify(p, m, sig):
// Parse inputs
1. Let P = lift_x(p) // Recover point with even y
If P is invalid, return false
2. Let r = int(sig[0:32])
3. Let s = int(sig[32:64])
4. If r ≥ p or s ≥ n, return false
// Compute challenge
5. Let e = int(H_challenge(bytes(r) || p || m)) mod n
// Verify equation: sG = R + eP
6. Let R = sG - eP
7. If R is the point at infinity, return false
8. If y(R) is odd, return false
9. If x(R) ≠ r, return false
10. Return true
Theorem 8.1 (Schnorr Correctness)
If (r, s) is a valid BIP-340 signature on m with key d, then verification with p = x(dG) returns true.
From signing: s = k + ed mod n, where R = kG and e = H(r||p||m).
Verification computes sG - eP:
sG - eP = (k + ed)G - e(dG) = kG + edG - edG = kG = R
Since r = x(R) and R has even y by construction, verification succeeds.
8.7 The Linearity Property
The defining feature that makes Schnorr signatures powerful is linearity: signatures and public keys can be added together algebraically.
Theorem 8.2 (Signature Linearity)
Given two Schnorr signatures (R₁, s₁) and (R₂, s₂) for the same message with keys P₁ = d₁G and P₂ = d₂G, we have:
(s₁ + s₂)G = (R₁ + R₂) + e(P₁ + P₂)
where e is the appropriate challenge for the aggregated key.
This linearity enables several powerful constructions:
8.8 MuSig: Secure Multi-Signatures
While naive key and signature aggregation is possible, it's vulnerable to rogue key attacks. The MuSig protocol provides secure multi-signatures.
Definition 8.5 (Rogue Key Attack)
In naive aggregation, a malicious party can choose their "public key" as P_{rogue} = P' - P_{honest} where P' is a key they control. The aggregated key becomes just P', which the attacker can sign alone.
Definition 8.6 (MuSig Key Aggregation)
MuSig prevents rogue key attacks by "tweaking" each public key before aggregation:
L = H(P₁ || P₂ || ... || Pₙ)
aᵢ = H(L || Pᵢ) (coefficient for party i)
P = a₁P₁ + a₂P₂ + ... + aₙPₙ
Each party must prove knowledge of their discrete log before their key affects the aggregate.
MuSig2: The Production Protocol.
MuSig2 is the current recommended protocol, requiring only two rounds of communication (compared to three in original MuSig). It achieves this by having each party commit to multiple nonces upfront, enabling non-interactive signing once nonces are exchanged.
8.9 Batch Verification
Schnorr's linearity also enables efficient batch verification: checking many signatures faster than verifying each individually.
Theorem 8.3 (Batch Verification)
Given n signatures (rᵢ, sᵢ) on messages mᵢ with public keys Pᵢ, we can verify all simultaneously:
- Generate random weights cᵢ
- Check: (Σ cᵢsᵢ)G = Σ cᵢRᵢ + Σ cᵢeᵢPᵢ
This requires only one expensive multi-scalar multiplication instead of n separate verifications, yielding approximately 2× speedup for large batches.
Block Validation.
Bitcoin nodes can batch-verify all Schnorr signatures in a block, significantly speeding up initial block download and validation of new blocks.
8.10 Schnorr in Taproot
Schnorr signatures are the foundation of Bitcoin's Taproot upgrade (BIP-341). Taproot combines Schnorr signatures with Merkleized Abstract Syntax Trees (MAST) to enable sophisticated spending conditions that remain private until executed.
Definition 8.7 (Taproot Output)
A Taproot output commits to a public key Q that encodes:
Q = P + H(P || merkle_root) · G
where P is an internal key (possibly aggregated via MuSig) and merkle_root commits to alternative spending scripts.
The beauty of Taproot is that the most common case (all parties agree to spend) produces a single Schnorr signature indistinguishable from any other. Only when the fallback script is needed does the spending condition become public.