Day 18 · Keys and Signatures

Day 17 left a hole big enough to drive a heist through: the UTXO set tracks coins and prevents double-spends, but nothing yet stops you from spending my coins. The validate_tx rules mentioned “the right key” and “a valid signature” without building either. Today we build ownership itself — and it turns out ownership in a chain isn’t a name, a password, or a row in a table. It’s a capability: the ability to produce a particular cryptographic signature. Hold the key and the coins are yours; lose it and they’re gone; nobody — no admin, no support line — can override that.

Public-key cryptography, the one idea you need

A keypair is two numbers, mathematically linked:

• a private key — a secret 256-bit number you keep, and
• a public key — derived from it, which you can share freely.

The magic is a one-way relationship over a specific curve. You can sign a message with the private key, and anyone with the public key can verify the signature is genuine — yet no one can work backwards from the public key (or any number of signatures) to the private key. Bitcoin uses the secp256k1 curve with the ECDSA signature scheme, and so do we, via the k256 crate.

   private key  ──(point multiplication on secp256k1)──▶  public key
        │                                                     │
        │ sign(tx)                                            │ verify(tx, sig)
        ▼                                                     ▼
   signature  ─────────────────────────────────────────▶  true / false
        (only the private key can make one that verifies)

Pure Rust, no C — why k256

secp256k1 has a famous C library (libsecp256k1), and binding to it would drag a C toolchain into your build. k256 is a pure-Rust implementation from the RustCrypto project, so cargo build needs no OpenSSL, no system library, nothing but Rust. That’s not just convenience — it means the memory-safety guarantees the rest of the playbook hammers on extend all the way down into the crypto, instead of stopping at an unsafe extern "C" boundary. We enable just the ecdsa feature.

Keypairs and addresses

In rust/btcmini/src/keys.rs, a keypair wraps k256’s signing key, and the public key and address fall straight out of it:

pub struct Keypair { signing: SigningKey }

impl Keypair {
    pub fn generate() -> Self {                 // OsRng → the OS entropy source
        Keypair { signing: SigningKey::random(&mut OsRng) }
    }
    pub fn public(&self) -> PublicKey { /* the verifying key */ }
    pub fn address(&self) -> Address { self.public().address() }
    pub fn sign(&self, message: &[u8]) -> Sig { /* deterministic ECDSA */ }
}

An address — the thing you hand someone so they can pay you — is the hash of your public key, not the key itself:

pub fn address(&self) -> Address {
    let h = double_sha256(&self.to_bytes());   // double-SHA-256 of the pubkey
    Address(first_20_bytes(h))                 // truncate to 20 bytes
}

Two questions this answers. Why hash the key at all? So you can publish a short, fixed-size identifier without revealing the public key until you actually spend — a small extra layer between the world and your key material. Why 20 bytes? It mirrors Bitcoin’s address length and keeps addresses short while staying collision-resistant. (Real Bitcoin uses RIPEMD160(SHA256(pubkey)); we truncate double-SHA-256 to 20 bytes — same length, same idea, one fewer hash function to pull in.)

Signing a transaction: the sighash

Here’s the subtle part. An input proves its right to spend by carrying a signature — but a signature over what? You can’t sign the finished transaction, because the signature is part of the finished transaction; you’d be trying to sign your own signature. So we sign a sighash: a digest of everything that matters except the signatures themselves. From rust/btcmini/src/tx.rs:

pub fn sighash(&self) -> Hash256 {
    let mut buf = Vec::new();
    for inp in &self.inputs { encode_outpoint(&mut buf, &inp.prev); } // what we spend
    for out in &self.outputs { /* amount + address */ }                // what we create
    double_sha256(&buf)   // commit to both, but NOT to the sigs
}

The sighash commits to what coins you’re spending and where the value is going — so a signature authorizes this transfer and only this one. Change an output address after signing and the sighash changes, so the old signature no longer verifies. Then signing is one method:

pub fn sign_input(&mut self, i: usize, kp: &Keypair) -> Result<()> {
    let sighash = self.sighash();
    self.inputs[i].pubkey = Some(kp.public());
    self.inputs[i].sig = Some(kp.sign(sighash.as_bytes()));
    Ok(())
}

And verification, back in validate_tx (Day 17), closes the loop with two checks that together define ownership:

if pk.address() != utxo.address { return Err(WrongKey); }        // your key locks this coin
if !pk.verify(sighash.as_bytes(), sig) { return Err(BadSignature); } // and you really signed

First: the public key you supplied must hash to the address the coin is locked to — so you can’t spend a coin locked to someone else. Second: the signature must verify against the sighash under that key — so you must actually hold the private key, not just know the address. Pass both and you’ve proven ownership without ever revealing the private key. This is the whole game, and the tests make it concrete: a_different_key_does_not_verify, wrong_key_is_rejected, and (Day 17’s) forged-spend test all fail exactly here.

Under the hood — deterministic signatures, and the nonce that must never repeat

ECDSA needs a fresh random number — a nonce, called k — for every signature. It is the single most dangerous parameter in the scheme: if you ever sign two different messages with the same k, anyone can solve two equations for the one unknown and recover your private key from the two public signatures. Predictable k is just as fatal. This isn’t theoretical; it has cost real keys and real money (see below).

k256 sidesteps the landmine entirely by signing deterministically per RFC 6979: it derives k from the private key and the message hash with HMAC, so k is reproducible, never reuses across different messages, and needs no random number generator at signing time. That’s why Keypair::sign takes no RNG — the only randomness in the whole crate is OsRng when you generate a key. What is Rust protecting you from? Here it’s less the borrow checker and more the ecosystem: a well-designed crate makes the safe thing the default thing, so you can’t accidentally hand-roll the catastrophic version.

By the numbers — the size of a private key, and why a 20-byte address is fine

A secp256k1 private key is a number below the curve order n ≈ 2^256 — about 1.16 × 10^77 possibilities. Guessing one is the same hopeless 2^256 search as forging a hash (Day 16): there isn’t enough energy in the solar system to brute-force it. Truncating the address to 160 bits is still safe because the relevant attack is a collision (two keys with the same address), whose birthday bound is about 2^80 — roughly 10^24 work, still far beyond feasible. So the short address costs you nothing in practice while keeping the key itself behind a 2^256 wall. The asymmetry — trivial to verify, impossible to forge — is the entire foundation of “ownership = a signature.”

It actually happened — the constant nonce that unlocked the PS3

At the 27th Chaos Communication Congress in December 2010, the group fail0verflow revealed that Sony had signed PlayStation 3 software with ECDSA using a constant nonce k — the same value every time. Because reusing k across two signatures leaks the private signing key, they recovered Sony’s master private key and could sign code as if they were Sony. The exact same failure has bitten Bitcoin users: in August 2013, a flaw in Android’s SecureRandom caused some wallet apps to reuse k across transactions, leaking private keys and allowing coins to be stolen — prompting an official advisory and a wave of key rotations. The defense in both cases is precisely what k256 does by default: derive k deterministically (RFC 6979) so it can never repeat or be predicted. The lesson for the playbook’s thread: the most dangerous bugs aren’t always memory bugs — sometimes they’re a single misused random number — and the way you stay safe is to lean on libraries that made the catastrophic option unreachable.

Build it

In rust/btcmini:

1. Read src/keys.rs and run cargo test keys. Confirm sign_then_verify_roundtrips passes and that a_different_key_does_not_verify and a_tampered_message_does_not_verify fail to verify — the two ways a forgery is caught.
2. In a scratch test, sign a transaction, then mutate an output’s amount and re-check the signature against the new sighash. It no longer verifies — proof that the signature is bound to the exact transfer.
3. Run cargo run -- demo and look at the addresses printed for Alice and Bob — each is the 20-byte hash of a freshly generated public key. Generate another keypair and confirm a different key yields a different address.

Where this leaves us

We now have the three of Bitcoin’s four pillars: a tamper-evident chain (Day 16), a UTXO ledger that can’t double-spend (Day 17), and cryptographic ownership (today). A transaction can now prove it’s legitimate. But one enormous question remains: when two valid histories compete — two different next blocks, each perfectly valid — which one is real? With no central server to decide, you need a way to make agreement expensive to disagree with. That’s tomorrow: Proof-of-Work, the mining loop, and the most-work chain rule that finally lets strangers converge on one history.

→ Next: Day 19 · Proof-of-Work · Prev: Day 17 · The UTXO Model · Back to the Project 5 overview

Check your understanding

1. In a UTXO chain, what does it actually mean to “own” a coin? Why can’t an admin reverse a transfer?
2. An address is the hash of a public key, not the key itself. Give two reasons the crate hashes the key, and note how our 20-byte address differs from Bitcoin’s.
3. What is a sighash, and why can’t you simply sign the finished transaction? What two things does the sighash commit to?
4. Spell out the two checks in validate_tx that together define ownership. What does each one rule out on its own?
5. What is the ECDSA nonce k, why is reusing it catastrophic, and how does k256 (and RFC 6979) make that failure unreachable? Name one real incident.

Show answers

1. Owning a coin means being able to produce a valid ECDSA signature under the private key whose public key hashes to the address the coin is locked to — a capability, not an identity or a database row. No admin can reverse a transfer because there is no privileged key or override; the only authority is the ability to sign, which only the holder has.
2. Hashing lets you publish a short, fixed-size identifier and keep the actual public key hidden until you spend (an extra layer between the world and your key material). Our address is the first 20 bytes of double_sha256(pubkey); Bitcoin uses RIPEMD160(SHA256(pubkey)) — same 20-byte length and purpose, one fewer hash function in our build.
3. The sighash is a digest of the transaction excluding the signatures. You can’t sign the finished transaction because the signature is part of it — you’d be signing your own signature. The sighash commits to what you’re spending (the input outpoints) and what you’re creating (the outputs), so a signature authorizes exactly that transfer.
4. (a) pk.address() == utxo.address — the supplied public key must hash to the coin’s locking address, so you can’t spend coins locked to someone else. (b) pk.verify(sighash, sig) — the signature must verify under that key, so you must actually hold the private key, not merely know the address. Each alone is insufficient; together they prove rightful ownership without revealing the secret.
5. k is the per-signature random nonce ECDSA requires. Reusing (or predicting) it across two signatures lets anyone solve for and recover the private key. k256 signs deterministically per RFC 6979, deriving k from the key and message via HMAC so it never repeats and needs no RNG. Real incidents: the PS3 constant-nonce break (fail0verflow, December 2010) and the August 2013 Android SecureRandom flaw that leaked Bitcoin wallet keys.