Schnorr Signatures

Introduction

Schnorr signatures, proposed by Claus-Peter Schnorr in 1989 and patented until 2008, are often described as what DSA could have been without a patent forcing NIST to design around it. Built on the exact same discrete logarithm hardness assumption, Schnorr signatures are simpler to describe, come with a clean mathematical security proof, and support elegant extensions (like signature aggregation) that DSA doesn’t. Once Schnorr’s patent expired, the algorithm found its way into some of the most consequential cryptographic infrastructure in the world — most notably Bitcoin’s 2021 Taproot upgrade.

Table of Contents

• Domain Parameters and Keys
• Signing a Message
• Verifying a Signature
• A Worked Example
• Why Schnorr Over DSA?
• Schnorr and Bitcoin’s Taproot
• FAQ
• References

Domain Parameters and Keys

Schnorr signatures use the same kind of setup as DSA: a large prime p, a prime q dividing p − 1, and a generator g of the order-q subgroup mod p (in modern deployments, an elliptic curve group is used instead, but the underlying logic is identical). A private key x is a random integer, 0 < x < q, and the public key is y = gˣ mod p.

Signing a Message

1. Choose a random, secret k, where 0 < k < q.
2. Compute r = gᵏ mod p — the “commitment.”
3. Compute e = H(r, m) — a hash combining the commitment and the message itself (mod q). This single step is where Schnorr’s simplicity shines: unlike DSA, the hash directly incorporates r as a full value, not derived through r mod q first.
4. Compute s = (k + x·e) mod q.
5. The signature is the pair (e, s) — note this is subtly different from DSA’s (r, s) pair; Schnorr publishes the hash e rather than r itself, and the verifier recomputes r during verification.

Verifying a Signature

Given a message m, signature (e, s), and public key y:

1. Recompute the commitment: r’ = (gˢ · y⁻ᵉ) mod p.
2. Recompute the hash: e’ = H(r’, m).
3. The signature is valid if and only if e’ = e.

This works because of a small piece of algebra: gˢ = g^(k+xe) = gᵏ · gˣᵉ = r · yᵉ, so gˢ · y⁻ᵉ = r · yᵉ · y⁻ᵉ = r exactly — the verifier reconstructs the same commitment the signer started with, without ever needing to know k or x.

Interactive Visualizer

The visualizer above runs this exact sign-and-verify math with small demonstration numbers. Try tampering with the message after signing — because the hash step covers the message directly, even a one-character change causes verification to correctly fail.

A Worked Example

Using the same small domain parameters as the DSA guide, for direct comparison:

• Domain parameters: p = 23, q = 11, g = 4
• Private key: x = 7 → Public key: y = 8
• Signing “HELLO” with k = 1 produces signature (e = 1, s = 8), which verifies successfully
• Tampering the message to “HELLO!” changes the hash entirely, so the same signature no longer verifies

Why Schnorr Over DSA?

• Provable security: Schnorr signatures have a clean security reduction to the discrete logarithm problem in the random oracle model — a mathematically tighter guarantee than DSA’s.
• Simplicity: fewer moving parts, a more direct hash-and-verify structure, and no equivalent to DSA’s easy-to-misuse “if r or s is 0, retry” edge case.
• Linearity enables aggregation: because Schnorr’s signing equation (s = k + xe) is linear in the private key, multiple parties’ signatures can be mathematically combined into a single, compact aggregate signature — a property DSA’s construction doesn’t share, and one that’s become extremely valuable for blockchain systems handling many signatures per transaction.
• The historical catch: Schnorr’s 1989 patent kept it out of most standards for two decades, which is a major reason NIST designed DSA using a different (patent-avoiding) construction in the first place, despite the extra complexity.

Schnorr and Bitcoin’s Taproot

Bitcoin’s November 2021 Taproot upgrade replaced its original ECDSA-based signatures with Schnorr signatures (specifically, the BIP 340 elliptic-curve variant) for several concrete benefits: smaller, more consistent transaction sizes, and — most significantly — native support for signature aggregation. Multiple participants in a multi-signature transaction can now produce a single combined Schnorr signature indistinguishable on the blockchain from an ordinary single-signer transaction, improving both privacy (multi-sig transactions no longer stand out) and efficiency (less blockchain space consumed per signature).

FAQ

Are Schnorr signatures more secure than DSA?

Both rest on the same underlying discrete logarithm hardness assumption and are considered secure with proper parameters. Schnorr’s advantage is a cleaner, more direct security proof and useful mathematical properties (like aggregation) rather than a fundamentally different security level.

Why did it take so long for Schnorr signatures to be widely adopted?

Claus-Peter Schnorr’s patent, filed in 1989 and expiring in 2008, kept the algorithm out of most royalty-free standards for two decades — directly influencing NIST’s choice of the differently-structured DSA for the U.S. Digital Signature Standard.

What does “signature aggregation” actually mean?

It means multiple separate signatures — potentially from multiple different signers over multiple different messages, depending on the specific aggregation scheme — can be mathematically combined into a single, compact signature that’s faster to verify and takes up less space than storing each signature individually.

Does Bitcoin only use Schnorr signatures now?

No — Taproot added Schnorr as an available signature scheme (used by modern wallet software and Taproot-aware addresses), but Bitcoin’s original ECDSA-based signatures remain valid and widely used for compatibility with older addresses and software.

What’s the relationship between Schnorr signatures and ECDSA?

Both are digital signature schemes built on discrete-log-hard groups (Schnorr can run over ordinary modular arithmetic or elliptic curves; ECDSA is always elliptic-curve-based). They differ in their exact mathematical construction — Schnorr’s is generally considered simpler and more elegant, which is exactly why Bitcoin migrated to it despite ECDSA’s decade-plus head start in production use.

References

1. Schnorr, C. P. “Efficient Identification and Signatures for Smart Cards.” CRYPTO 1989 — the original paper.

2. Bitcoin Improvement Proposal 340 (BIP 340). “Schnorr Signatures for secp256k1.” Available at: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki

3. Wikipedia. “Schnorr signature.” Available at: https://en.wikipedia.org/wiki/Schnorr_signature

4. Wuille, P., Nick, J., and Ruffing, T. “Taproot: SegWit version 1 spending rules.” Bitcoin Core, 2021.