Schnorr signatures and BIP-340

Schnorr's 1989 signature is the one textbooks start from: short, provably secure in the random-oracle model, and linear in the key. Schnorr's patent kept it out of the early standards, and Bitcoin adopted it in 2021 as BIP-340. Its linearity is what makes multi-signatures cheap, and also what makes them easy to get wrong.

Rests on
The ECDLP on secp256k1, in the random-oracle model
Standards
Bitcoin Improvement Proposal 340, activated with Taproot in November 2021
Sizes
32-byte public key (x-coordinate only), 64-byte signature
Checked here
All 19 BIP-340 test vectors: 8 signatures regenerated byte for byte, 9 valid and 10 invalid verifications
Quantum
Broken by Shor's algorithm

The scheme

A private key is a scalar d and the public key is P = dG. To sign a message m:

  1. Choose a secret nonce k and compute R = kG.
  2. Compute the challenge e = H(R ‖ P ‖ m).
  3. Compute s = k + e·d mod n. The signature is (R, s).

The verifier checks sG = R + eP. Compared with ECDSA, there is no inversion, and the signing equation is linear in both the nonce and the key. The security proof is also cleaner: in the random-oracle model, forging a Schnorr signature is as hard as the discrete logarithm, via the forking lemma. ECDSA has no comparable proof for the scheme as standardised.

What BIP-340 adds

BIP-340, by Wuille, Nick and Ruffing, fixes the details that a deployable scheme needs:

  • x-only keys. Public keys and R are 32-byte x-coordinates, and the implied point is always the one with even y. That saves a byte per key and per signature, at the cost of a sign fix-up when signing: if dG has odd y, the signer uses n − d.
  • Tagged hashes. Every hash is SHA-256(SHA-256(tag) ‖ SHA-256(tag) ‖ data) with a distinct tag for the challenge, the nonce and the auxiliary randomness, so a hash computed for one purpose can never be reinterpreted as another.
  • Key-prefixed challenge. The challenge includes the public key, which blocks related-key attacks and makes the scheme safe for key tweaking, as Taproot does.
  • Hedged nonces. The nonce is derived from the key, the message and 32 bytes of auxiliary randomness. That is deterministic enough to survive a bad random number generator and random enough to frustrate fault attacks.

The code that builds this page implements BIP-340 from the specification and runs every test vector the BIP publishes, 19 in all, copied unmodified from the bitcoin/bips repository. Where a vector supplies a secret key, the signature is regenerated and must match byte for byte (8 of them). Every vector's verification result must also match: 9 valid signatures and 10 deliberately invalid ones, covering wrong-parity R, a public key not on the curve, s ≥ n, and similar edge cases.

Linearity and the rogue-key attack

Because signing is linear, signatures and keys add. If Alice and Bob have keys PA and PB, a signature under PA + PB can be produced jointly, each contributing a partial nonce and a partial s. On chain it is one ordinary 64-byte signature under one ordinary key, and nobody can tell that two parties were involved. That is the attraction.

The naive version is broken. Suppose Mallory is to share a 2-of-2 key with Alice, and announces her key after seeing Alice's. She picks a scalar x and announces PM = xG − PA. The aggregate PA + PM is xG, whose discrete logarithm Mallory knows, so she can sign alone. The build does exactly this:

Alice's key     58a38fbb214e67fdb8cfd7a38d2b05fec6fbcafe0ff89cf036549f21f8ef0aee
Mallory's key   407f81438f448cd9d9d0e9de6126ff33cac3e90c08c6034f692d326a2832f1a9
aggregate key   7f27deff60778c4ad4f9315438627ac31eb4c5cba0547d1dcbcef2d301f3111a

signature by Mallory alone on "Spend the 2-of-2 output to Mallory":
64a6401999d5c8395df8e7df1cde270d61d14b20d82bdc91cb3cb86f9db9ee82227fb75f8cd3d8f7e2e81e3ed4878385c510b060a7138611a001441884a06f5f

A rogue-key attack at full size: the signature verifies under the "2-of-2" key

The fix is to stop keys from being chosen as a function of each other. MuSig, by Maxwell, Poelstra, Seurin and Wuille, multiplies each key by a coefficient that hashes all the keys, so no participant can cancel another's. MuSig2, by Nick, Ruffing and Seurin, brings the signing protocol down to two rounds and is specified for Bitcoin as BIP-327. Proofs of possession, where each party signs its own key, are the other standard defence.

Nonce reuse

Linearity also makes nonce reuse even simpler to exploit than in ECDSA. Two signatures with the same k on different messages give s1 − s2 = (e1 − e2)d, one subtraction and one division from the key. The build forces a repeated nonce on "Pay Alice 10 coins" and "Pay Bob 20 coins". Both signatures have the same R, and the formula returns a scalar whose public key matches. BIP-340's hedged nonce derivation exists to make this impossible in practice. In multi-signature protocols, where nonces are exchanged between parties, it is the main thing to get right: a signer who can be made to reuse a nonce across two sessions loses its key.

Where it stands

Against the curve, BIP-340 offers the ECDLP security of secp256k1, about 2127 with the curve's extra automorphisms taken into account; see Pollard's rho. Like every discrete-logarithm scheme it falls to Shor's algorithm. For Bitcoin that is a particular concern, because Taproot outputs expose their public key on chain, and how to migrate coins to post-quantum signatures is an open design question there.

Primary sources

  1. C. P. Schnorr, "Efficient signature generation by smart cards", Journal of Cryptology 4 (1991)
  2. P. Wuille, J. Nick and T. Ruffing, BIP-340: Schnorr Signatures for secp256k1
  3. G. Maxwell, A. Poelstra, Y. Seurin and P. Wuille, "Simple Schnorr multi-signatures with applications to Bitcoin", Designs, Codes and Cryptography 87 (2019)
  4. J. Nick, T. Ruffing and Y. Seurin, "MuSig2: simple two-round Schnorr multi-signatures", CRYPTO 2021
  5. BIP-327: MuSig2 for BIP340-compatible multi-signatures