Chapter 3 · Digital Signatures - Bitcoin from Scratch

Part I · Bricks: the cryptographic floor This chapter closes the loop. You will assemble the previous two chapters into real ECDSA, then count how many times priv appears inside verify.

3.0 First, why signatures need to exist at all¶

You have two things now: a hash (chapter 1) and a key pair (chapter 2).

Before going further, ask the obvious question — almost everyone asks it at this point:

A hash is also easy-forwards and hard-backwards. Why can’t we just use that as a key pair?

It is an excellent question, because thinking it all the way through derives the entire reason signatures exist.

Try it: a hash as an identity¶

Pick a secret number x. Call it the private key. Compute hash(x), publish it, call it the public key.

Nobody can recover x from the hash. When you need to prove “I am the person behind this public key,” you reveal x, everyone hashes it, it matches — that’s you.

This works. In fact you already wrote it: this is chapter 1’s commitment, used as an ID card.

And here it dies¶

The trouble:

To prove anything, you must produce x itself. Produce it once, and x is burned.

Next time, the whole world already knows x. Anyone can impersonate you.

Stop here, because this is one of the most important contrasts in the book:

	Hash-as-identity	An actual private key
To prove	You must hand over the secret (reveal)	The secret never appears
Usable how many times	Once, then dead	Unlimited

And be precise about where the difference is. At the public-key layer, both are public — a published hash and a published curve point are equally exposed. That is not the difference. The difference is entirely at the proving layer: the hash approach must expose the secret, while the key pair only exposes a value computed from the secret.

That is the watershed. Which turns the question into:

Is there a way to prove I know a secret without saying what it is?

That question is the entire reason digital signatures exist. This chapter is the answer.

3.1 While we’re here: what is a signature actually for?¶

We sign contracts constantly. But a handwritten signature is not very good, and it has exactly two holes. Seeing them tells you precisely what a digital signature is buying you.

Hole one: it can be forged. Practise someone’s handwriting and you can get close enough that the person checking cannot tell.

Hole two: it can be peeled off and moved. Your signature on a contract and your signature on an IOU look identical — because the signature has nothing to do with the content. So someone can detach the page you signed and staple it to a different document. “I signed version A, how did you end up with version B?” Good luck proving it.

Remember those two words: forgeable and transplantable. A digital signature kills one each.

Killing hole one: the seal stays home¶

A medieval king had one unique signet ring. Pressed into wax it left a mark the whole country recognized. Everyone knew what the mark looked like — but the ring itself never left the king’s hand, and nobody could manufacture a second one.

The elegant part: the person checking the seal does not need to own the ring.

In this book’s vocabulary: you hold a unique seal (private key); everyone else holds a lamp that reveals whether a seal is genuine (public key). Stamping requires the seal, which only you have. Checking requires the lamp, and the lamp is safe to hand out to the entire world because a lamp can only inspect, never stamp.

Handwriting can be imitated; a seal cannot be duplicated. Hole one closed.

Killing hole two: the signature moves with the content¶

A digital signature is not stamped onto a document from outside. It is computed from your private key together with every character of that document.

Change one character and the whole signature changes. So a digital signature is welded to this document, this version. Peel it off, staple it to version B, and it fails on inspection.

Hole two closed.

That is the complete reason a digital signature beats a handwritten one. Not more, not less.

3.2 Bring in the bricks¶

A signature is not new magic. It is a composition of old parts. Set them up first.

This chapter uses a smaller curve: $y^2 = x^3 + x + 4 \pmod{23}$ , with $G=(1,12)$ .

Why change? Because signature mathematics needs one extra property: the order of G must be prime. On this curve G has order 29, which is prime; on chapter 2’s curve G had order 50, which is not. (A composite order breaks the modular inverses the signature equation relies on. Real Bitcoin’s curve satisfies the same requirement.)

import hashlib

p, a, b = 23, 1, 4      # curve: y^2 = x^3 + a x + b (mod p)
G = (1, 12)             # generator
n = 29                  # the order of G -- prime

def inv(x, m):
    '''Modular inverse (Fermat).'''
    return pow(x % m, m - 2, m)

def point_add(P, Q):
    '''Chapter 2's point addition, verbatim.'''
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P; x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return None
    if P == Q:
        s = (3*x1*x1 + a) * inv(2*y1, p) % p
    else:
        s = (y2 - y1) * inv(x2 - x1, p) % p
    x3 = (s*s - x1 - x2) % p
    y3 = (s*(x1 - x3) - y1) % p
    return (x3, y3)

def scalar_mul(k, P):
    '''Chapter 2's scalar_mul.'''
    R = None; k %= n
    for _ in range(k):
        R = point_add(R, P)
    return R

print("bricks ready. G =", G, " n =", n)

bricks ready. G = (1, 12)  n = 29

There is not one new line in that cell. inv, point_add, scalar_mul are all yours from chapter 2, unchanged except for the curve constants.

Worth noticing: the “magic” that follows is built entirely from parts you already understand.

Make a key pair¶

priv = 7                       # private key: keep it
pub  = scalar_mul(priv, G)     # public key: publish it
print("private key =", priv, "  (hidden)")
print("public key  =", pub, "  (published)")

private key = 7   (hidden)
public key  = (0, 21)   (published)

private key = 7, public key = (0, 21). Same two shapes as chapter 2 — one integer, one tuple.

Squeeze the message into a number¶

A signature does not sign raw text. First the message is hashed into a number z:

def hash_to_int(msg: str) -> int:
    '''SHA-256 the message, reduce mod n to get a number.'''
    digest = hashlib.sha256(msg.encode()).digest()   # chapter 1's sha256
    return int.from_bytes(digest, "big") % n

print("z(pay 0.5 to Alice) =", hash_to_int("pay 0.5 to Alice"))
print("z(pay 5 to Bob)     =", hash_to_int("pay 5 to Bob"))

z(pay 0.5 to Alice) = 4
z(pay 5 to Bob)     = 7

hash_to_int is chapter 1’s sha256 plus one line: turn the 32-byte fingerprint into a single integer between 0 and 28.

(Real Bitcoin’s n is a 256-bit number, so almost nothing is lost. Here n=29 compresses brutally, purely so you can follow the arithmetic by hand.)

And section 3.1’s “the signature moves with the content” originates in exactly this line: change one character and z changes, and every subsequent computation changes with it.

3.3 `sign` — requires the private key¶

def sign(priv, msg, k):
    '''Sign msg with priv, return (r, s).'''
    z = hash_to_int(msg)               # the message as a number
    R = scalar_mul(k, G)               # hop k times to get a point
    r = R[0] % n                       # take its x coordinate
    if r == 0:
        return None                    # bad k: real ECDSA picks a new one
    s = (inv(k, n) * (z + r * priv)) % n   # the key step: priv and z mixed in
    if s == 0:
        return None
    return (r, s)

sig = sign(priv, "pay 0.5 to Alice", k=11)
print("signature (r, s) =", sig)

signature (r, s) = (18, 25)

Output: signature (r, s) = (18, 25).

Be clear what a signature is: a tuple of two integers.

sig = (18, 25)

Not a hash, not a blob of ciphertext. Two numbers. That is the first layer of “a signature is not a hash”: a hash returns one value, a signature returns two.

Now look at the function’s inputs. Three parameters, and one of them is priv — signing requires the private key, and there is no way around that.

About k: it is a one-time nonce, and it must be fresh every single time. Passing it in by hand here exists only so your output matches the book’s. In a real system k must be a secret random value — and section 3.6 explains what happens when it isn’t, using events that actually occurred.

3.4 `verify` — the pivot of the whole book¶

Here is the verification function. Before you read it, know that you are about to count something.

def verify(pub, msg, sig):
    '''Verify using only the public key.'''
    if sig is None:
        return False
    r, s = sig
    if not (1 <= r < n and 1 <= s < n):
        return False
    z = hash_to_int(msg)               # hash the message the same way
    w  = inv(s, n)
    u1 = (z * w) % n
    u2 = (r * w) % n
    # The key line: X is computed from G and pub only -- no priv anywhere.
    X = point_add(scalar_mul(u1, G), scalar_mul(u2, pub))
    if X is None:
        return False
    return (X[0] % n) == r             # lamp on = True

print("verify:", verify(pub, "pay 0.5 to Alice", sig))

verify: True

It prints True.

Now count¶

How many times does priv appear in the body of verify?

Zero.

Its three parameters — pub, msg, sig — are all public. Everything it touches inside — inv, z, point_add, scalar_mul, G, pub — is public.

Anyone can run this function. Every full node on the Bitcoin network verifies thousands of transactions a day using a function of exactly this shape. None of them knows your private key, and all of them can confirm you authorized the payment.

That is the answer to the question in 3.0:

Prove you know the secret, without saying what it is.

sign contains priv. verify does not. The rest of this book stands on that asymmetry.

The second difference from hashing¶

Chapter 1’s hash is a machine with one input: content goes in, a fingerprint comes out, and anybody can turn the crank.

Signing is a machine with two inputs: content and the private key go in, a signature comes out, and only the key holder can operate it.

Verification takes three: content, signature, and public key. Note that the lamp contains no private key and does not regenerate the signature — it is a gate that outputs True or False and nothing else.

3.5 Three attacks, three failures¶

# Attack 1: tamper -- change Alice to Bob, reuse the old signature.
print("tampered content :", verify(pub, "pay 5 to Bob", sig))

# Attack 2: impersonate -- the attacker has a different key.
fake_pub = scalar_mul(13, G)
print("wrong identity   :", verify(fake_pub, "pay 0.5 to Alice", sig))

# Attack 3: forge -- guess (r, s) with no private key.
print("guessed signature:", verify(pub, "pay 0.5 to Alice", (5, 9)))

tampered content : False
wrong identity   : False
guessed signature: False

Three Falses. And they fail for three different reasons, which is worth reading carefully:

Attack	Why it fails	Which hole it closes
Tampering	The message changed, so `z` went from 4 to 7, so the computed `X` no longer matches `r`	3.1’s hole two (transplanting)
Impersonation	`verify` uses `pub` to compute `X`; a different key gives a different `X`	Identity binding
Forgery	Without `priv` you cannot produce an `(r, s)` satisfying the equation	3.1’s hole one (forgery)

Unforgeable, unimpersonatable, untamperable. And all three fall out of one equation.

YOUR TURN¶

# YOUR TURN:
# 1) Change k (try 5), re-sign, re-verify.
#    The signature (r,s) changes but verify is still True -- why?
sig2 = sign(priv, "pay 0.5 to Alice", k=5)
print("new signature:", sig2, " still valid?:", verify(pub, "pay 0.5 to Alice", sig2))

# 2) Find a k that makes sign return None. Hint: try 7 and 22.
# print(sign(priv, "hello", k=7))

# 3) Without priv, brute-force every (r,s) and count how many pass.
msg = "I am the boss, pay me"
count = 0
for r in range(1, n):
    for s in range(1, n):
        if verify(pub, msg, (r, s)):
            count += 1
print("valid (r,s) pairs found by brute force:", count, "/", (n-1)*(n-1))

new signature: (4, 18)  still valid?: True
valid (r,s) pairs found by brute force: 26 / 784

Question 1 prints (4, 18) — completely different from (18, 25) — and still verifies. So one message has many valid signatures. A signature is not a fingerprint of the message; it is evidence that you hold the key, and evidence can be produced in unlimited forms.

Question 2: both k=7 and k=22 return None. Not a bug — a genuine ECDSA detail. A few unlucky nonces drive r or s to zero, and real implementations simply pick another.

Question 3 prints 26 / 784.

That number is more interesting than it looks. 26/784 ≈ 3.3%, and 1/n = 1/29 ≈ 3.4%. They are nearly equal, and that is not a coincidence:

The probability that a randomly guessed (r, s) verifies is about 1/n.

On this curve n = 29, so roughly one guess in thirty works — on a toy curve, forgery is entirely practical.

Real Bitcoin has n ≈ 2²⁵⁶. Same formula, so the probability is 1/2²⁵⁶. A billion guesses a second until the heat death of the universe and your odds still round to zero.

Chapter 2’s sentence again: security is not the algorithm, it is the scale.

3.6 A real lesson: never reuse `k`¶

We passed k in as a parameter for reproducibility. In a real system k must be a fresh random value every time.

What happens if the same k signs two different messages?

Look at that line in sign:

s = (inv(k, n) * (z + r * priv)) % n

Same k → same r (since r depends only on k). So an observer has two equations, two known z values, two known s values, and only two unknowns: k and priv.

Two equations, two unknowns. High-school algebra recovers the private key.

This is not a theoretical concern. In the early 2010s, Android’s Bitcoin wallets reused k because of a flaw in the system random number generator, and real funds were stolen. Sony’s PlayStation 3 code-signing key leaked the same way — they had hardcoded k as a constant.

A signature’s security depends on the mathematics and on how you use it. This is the first time that shows up in this book, and it will not be the last — chapters 11, 13 and 18 all contain a mathematically flawless design ruined by an engineering detail.

(Real Bitcoin now generally uses RFC 6979: derive k deterministically from the private key and the message, so it depends on no random number generator at all. Reproducible and never repeated.)

3.7 A thirty-year gap¶

Part I ends here. You have three bricks: hashing, key pairs, signatures.

Worth knowing: all three existed thirty years before Bitcoin.

Digital signatures were invented in 1976–77. The moment they existed, people began chasing one goal: digital cash.

Year	Who	What they built	Where it stalled
1982	David Chaum	Blind signatures → DigiCash / eCash, the first serious attempt	Needed a central bank to stop double-spends
1997	Adam Back	Hashcash proof-of-work	Not money — postage
1998	Wei Dai	b-money: a group keeping a ledger together	Stayed a proposal
1998	Nick Szabo	Bitgold: proof-of-work plus a chained structure	Stayed a paper

Every one of them assumed signatures as the foundation, and every one of them stalled on the same thing.

A signature proves “I authorized this payment.” It cannot tell you whether I already spent that same coin somewhere else.

Because a signature is local: it can establish the validity of the transaction in front of you, and it has no way of knowing whether another equally valid transaction exists somewhere spending the same coin. Detecting that requires a ledger everyone agrees on.

And “how do mutually distrustful strangers maintain a shared ledger” — that is not a cryptography question.

That is what chapter 4 begins. From here on, the cryptography in your code thins out and systems, consensus, game theory and economics take over.
The prologue’s claim starts being cashed on the next page.

3.8 The ledger¶

What you wrote	Field
`hash_to_int()` — message to number	Cryptography (reusing chapter 1)
`sign(priv, msg, k)` — signing with the private key	Cryptography
`verify(pub, msg, sig)` — verifying, with no priv	Cryptography
“Never reuse `k`”	Engineering safety — not mathematics

Three conclusions:

A signature is not a hash. A hash: one input, one output, anyone can compute it. A signature: two inputs, two outputs, only the key holder can produce it.
Verification never touches the private key. Public verification, private key permanently hidden — and this is also the root of why an entire chain can be independently checked by anyone.
Composition. A signature = a hash + an elliptic curve + one equation. This chapter invented no new primitive. It only put chapters 1 and 2 next to each other.

You have now walked all of Part I:

bytes → hash → commitment → finite field → curve → public key → sign & verify

Next¶

The hash time-stamp chain.

You will take chapter 1’s hash and do something Haber and Stornetta did in 1991: link data head-to-tail, then edit one item in the middle and watch everything after it collapse.

That chapter contains no new cryptography at all. It is the first piece of systems design in this book.

It is also where the “chain” in blockchain actually comes from.

Chapter 3 · Digital Signatures