Digital Signatures (ECDSA & Schnorr)

Public-key crypto gave each user a secret d and a public point Q = d·G. A digital signature is the bridge between them: a number you can only produce with d, that anyone can check using only Q. It proves two things at once — I authorized this exact transaction, and I did so without showing you my key. This is the primitive that lets strangers accept a spend without trusting the spender.

What a signature must guarantee

A real signature scheme has to nail three properties simultaneously:

Property	What it means	What breaks without it
Authenticity	only the holder of d could have made it	anyone could spend your coins
Integrity	it commits to this message — change a byte, it’s invalid	a relay could redirect your payment
Non-repudiation	verifiable by anyone with Q, no secret needed	nodes couldn’t independently check

Crucially, what gets signed is not the whole transaction but a hash of a carefully chosen subset of it — the sighash — which is why a SIGHASH flag can say “sign only these inputs/outputs.” For now, treat the thing being signed as a single 256-bit number z.

ECDSA: sign and verify

Bitcoin’s original scheme is ECDSA over secp256k1. To sign message-hash z with private key d:

   1. pick a random nonce  k  in [1, n−1]          ← must be unique & secret every time
   2. R = k · G        and    r = R.x  mod n        ← the x-coordinate of a fresh point
   3. s = k⁻¹ · (z + r · d)   mod n
   4. signature = (r, s)

To verify (r, s) against public key Q and hash z — note d and k appear nowhere:

   u1 = z · s⁻¹ mod n     u2 = r · s⁻¹ mod n
   R' = u1 · G + u2 · Q
   valid  ⇔  R'.x mod n == r

The algebra closes because substituting s = k⁻¹(z + rd) makes u1·G + u2·Q collapse back to exactly k·G = R. The verifier reconstructs the same point the signer committed to — using only public values.

The nonce k is not a detail — it’s the whole ballgame

k must be secret (it’s as sensitive as d) and never reused. The signer throws it away after step 4, but it is mathematically welded into s. Leak it, or repeat it, and you hand over d itself. The next section proves that with real numbers.

By the numbers — recovering a private key from a reused nonce

Watch how a single repeated k collapses the whole scheme. We’ll use a tiny order n = 23 so the arithmetic fits on the page; the algebra is identical at 256 bits. Say the secret is d = 7 and the signer (foolishly) signs two different messages with the same nonce k = 3, giving the same r = 9:

   message 1:  z₁ = 5      s₁ = k⁻¹(z₁ + r·d) = 8·(5 + 9·7)  = 8·22 = 15  (mod 23)
   message 2:  z₂ = 11     s₂ = k⁻¹(z₂ + r·d) = 8·(11 + 9·7) = 8·5  = 17  (mod 23)
                                    (k⁻¹ = 3⁻¹ = 8, since 3·8 = 24 ≡ 1 mod 23)

An attacker now sees two signatures sharing the same r — a dead giveaway that k was reused. With that, recovering first k, then d, is pure arithmetic:

   k = (z₁ − z₂) / (s₁ − s₂)  =  (5 − 11)/(15 − 17)  =  (−6)/(−2)  =  3   ✓  (mod 23)

   d = (s₁·k − z₁) / r        =  (15·3 − 5)/9        =  40/9        =  7   ✓  (mod 23)

The key is fully recovered. The signature didn’t have to be broken — the randomness leaked it. This is not theoretical; it’s the most common way real funds have been stolen at the crypto layer.

It actually happened — the 2013 Android wallet thefts (and Sony’s PS3)

In August 2013, a flaw in Android’s SecureRandom caused several Bitcoin wallet apps to generate duplicate k values. Attackers scanned the chain for transactions sharing an r, ran exactly the arithmetic above, and drained the affected addresses. Bitcoin.org issued an emergency advisory and wallets rushed to regenerate keys. The same class of bug had already burned Sony in 2010: the PS3’s firmware-signing code reused a constant k, letting hackers extract the master private key and sign their own code. Different decade, different system, identical mistake. Modern wallets defuse it entirely with deterministic nonces (RFC 6979) — k is derived from H(d, z), so it’s unpredictable to outsiders yet guaranteed never to repeat for different messages.

Under the hood — malleability and the low-s rule

ECDSA has an annoying quirk: if (r, s) is valid, so is (r, n − s). Both verify, but they’re different byte strings — so a third party can flip a signature to its twin in flight, changing the transaction’s txid without invalidating it. That’s signature malleability, and it underlies a famous era of Bitcoin bugs (see Transaction Malleability). The fix is the low-s rule: only the signature with s ≤ n/2 is allowed, killing the second twin. (Bitcoin Core enforces it as a relay/standardness policy; the proposal to elevate it to consensus, BIP 146, was withdrawn and never activated.) Signatures are also serialized in strict DER form so there’s exactly one valid encoding of the same numbers.

Schnorr: the same job, but linear

Taproot (2021) added a second scheme, Schnorr (BIP340), and the difference that matters is one word: linearity. A Schnorr signature is almost embarrassingly simple:

   sign:    R = k·G,   e = H(R ‖ P ‖ z),   s = k + e·d   (mod n)     → signature (R, s)
   verify:  s·G  ==  R + e·P

Because s = k + e·d is a straight-line equation in the secret values, signatures and keys add up. Three signers can combine their keys into one aggregate key and their signatures into one aggregate signature (MuSig2), and the result looks identical to an ordinary single-sig on chain — same 64 bytes, same verification. ECDSA’s k⁻¹ term made that impossible.

	ECDSA	Schnorr (BIP340)
Equation for s	k⁻¹(z + r·d) — nonlinear	k + e·d — linear
Size	~71–72 bytes (DER)	64 bytes, fixed
Malleable?	yes (needs low-s rule)	provably non-malleable
Multisig on chain	looks like multisig	looks like one signature

That last row is the payoff: cheaper, more private multisig and complex spending policies that are indistinguishable from a normal payment. See Taproot, Schnorr & MuSig2 for how it’s wired into spending.

The thread

How does this help untrusting strangers agree on one ledger? A signature is the only thing in Bitcoin that says “this specific value movement was authorized,” and it says it in a way every stranger can check independently and none can forge. No clearing house vouches for the payer — the math does. And because verification needs only public data, a node in another country re-checks your spend with the same certainty as your own wallet. That shared, forgery-proof “yes” is what turns a pile of broadcast bytes into an agreed ledger. Next, Merkle Trees show how thousands of these authorized spends get committed into one block hash.

The architect’s lens

• Why does it exist? To let the holder of a secret d produce a number anyone can check with only the public key Q — proving I authorized this exact transaction without ever revealing d.
• What problem does it solve? Authenticity, integrity, and non-repudiation at once — no clearing house vouches for the payer, the math does, and every stranger re-checks the spend independently from public data alone.
• What are the trade-offs? ECDSA’s nonlinear s = k⁻¹(z + r·d) is fragile: a reused or leaked nonce k hands over d outright (the 2013 Android wallet thefts), signatures are malleable (needing the low-s rule and strict DER), and they run ~71–72 bytes each.
• When would you choose differently? When you want aggregatable or provably non-malleable signatures — exactly why Taproot added Schnorr (BIP340): its linear s = k + e·d lets MuSig2 fold many signers into one 64-byte signature that looks like a single-sig on chain, which ECDSA’s k⁻¹ term makes impossible.
• What breaks if I remove it? Anyone could spend anyone’s coins — there’d be no forgery-proof way to say “this value movement was authorized,” so nodes couldn’t accept a spend and the shared ledger would never form.

Check your understanding

1. A verifier checks a signature using only Q, z, r, and s. Why is it significant that neither d nor k appears in the verification equations?
2. Work the intuition: in the reused-nonce example, what single observable clue tells an attacker the same k was used across two signatures?
3. From two signatures (r, s₁) and (r, s₂) over hashes z₁, z₂ with a shared k, write the formula that recovers k, then the one that recovers d.
4. What is signature malleability, and how does the low-s rule remove it?
5. Schnorr’s s = k + e·d is “linear.” Name one concrete capability that linearity unlocks which ECDSA cannot offer.

Show answers

1. It means verification uses only public values, so anyone — a node anywhere, with no secrets — can independently confirm the spend was authorized, while the signer’s secret d (and the one-time k) never leave their wallet. Public verifiability + secret authority is the whole point.
2. Both signatures carry the same r (the x-coordinate of k·G). Identical r ⇒ identical k, which should never happen for different messages.
3. k = (z₁ − z₂) / (s₁ − s₂) mod n, then d = (s₁·k − z₁) / r mod n. (In the worked example these gave k = 3 and d = 7.)
4. Malleability: (r, s) and (r, n − s) are both valid, so a third party can swap one for the other in transit, changing the txid without invalidating the tx. The low-s rule (a standardness policy in Bitcoin Core) accepts only s ≤ n/2, eliminating the second valid form.
5. Because keys and signatures add, multiple signers can aggregate into a single key and a single signature (MuSig2) that looks exactly like an ordinary single-sig on chain — smaller and more private. ECDSA’s k⁻¹ term blocks this.