Day 16 · Blocks and Hashing

The Project 5 overview framed the whole phase around one question: how do strangers agree on a ledger with no bank? Before any of the cryptography or mining, we need the thing they agree on — an ordered history that cannot be quietly rewritten. Today you build that spine: a hash function strong enough to act as a fingerprint, and a chain of blocks where each one commits to the one before it, so a single altered byte anywhere in the past shatters every hash that follows.

First, the bug we’re designing against

A coin is data. Data copies for free. So the attack we must make impossible is the double-spend: pay Alice with a coin, then pay Bob with the same coin, hoping the two never compare notes. A bank prevents this trivially — it keeps one ledger and subtracts your balance the instant you spend. Take the bank away and you have to rebuild that single, agreed-upon, append-only history out of cryptography. Step one is making the history tamper-evident: if anyone edits a past transaction to un-spend a coin, every honest participant must be able to tell at a glance.

That is a job for a cryptographic hash.

A hash is a fingerprint

A cryptographic hash function takes any bytes and returns a fixed-size digest (256 bits, here) with three properties that matter to us:

• Deterministic — the same input always gives the same digest, so two people can independently check they’re looking at the same data.
• Avalanche — flip one bit of the input and about half the output bits flip, unpredictably. There’s no “close”; a tiny edit gives a totally different fingerprint.
• Preimage- and collision-resistant — given a digest you can’t find an input that produces it, and you can’t find two different inputs that collide. So a digest binds to its data: you can’t swap the data out and keep the fingerprint.

Bitcoin uses double-SHA-256 — SHA-256 applied twice, SHA256(SHA256(bytes)) — for block and transaction ids. The second pass is cheap insurance against a class of length-extension attacks that plain SHA-256 is theoretically open to. In rust/btcmini/src/hash.rs it’s four lines:

pub fn double_sha256(data: &[u8]) -> Hash256 {
    let first = Sha256::digest(data);
    let second = Sha256::digest(first);
    let mut out = [0u8; 32];
    out.copy_from_slice(&second);
    Hash256(out)
}

Under the hood — why wrap it in a Hash256 newtype

The digest is just [u8; 32]. So is a truncated pubkey, a raw nonce buffer, half of a signature. If every 32-byte thing has the same type, nothing stops you from passing a public key where a block hash is expected — the code compiles and silently does the wrong thing. So the crate wraps the bytes in a newtype:

pub struct Hash256(pub [u8; 32]);

Now a block id and a pubkey are different types, and mixing them is a compile error, not a runtime mystery. This is the playbook’s recurring thread in miniature: what is the compiler protecting you from? Here it’s a whole category of “right size, wrong meaning” bugs — the kind that are invisible in C and in dynamically-typed chains. The newtype costs nothing at runtime (it’s the same 32 bytes) and buys you a type system that knows a fingerprint from a key.

By the numbers — why you can’t forge a fingerprint

SHA-256 outputs one of 2^256 values — about 1.16 × 10^77. For scale, the observable universe holds roughly 10^80 atoms. To find a second input with the same digest as a given block, an attacker tries inputs at random; by the design of the function there’s no shortcut, so the expected number of attempts is on the order of 2^256. Even at the entire Bitcoin network’s hash rate (as of ~2024, on the order of hundreds of exahashes — 10^20 — per second) that search would outlast the universe by a preposterous margin. That is why a hash can stand in for “this exact data, unaltered”: forging a match is not hard, it’s effectively impossible.

A block, and the chain

A block is a small header plus the transactions it seals. Only the header is hashed and (next day) mined; it holds just enough to commit to everything else. From rust/btcmini/src/block.rs:

pub struct BlockHeader {
    pub prev_hash: Hash256,     // the previous block's header hash — the "chain"
    pub merkle_root: Hash256,   // one hash summarizing every transaction
    pub timestamp: u64,
    pub bits: u32,              // the difficulty target (Day 19)
    pub nonce: u64,            // the number a miner searches over (Day 19)
}

pub struct Block {
    pub header: BlockHeader,
    pub txs: Vec<Transaction>,
}

Two fields do the tamper-evidence. The merkle_root is a single hash computed from all the transactions, so the tiny header commits to the whole (possibly huge) body — change any transaction and the root changes. The prev_hash is the previous block’s header hash, and it’s what makes a chain:

   block N-1            block N              block N+1
   ┌─────────┐  prev    ┌─────────┐  prev    ┌─────────┐
   │ header  │◀─────────│ header  │◀─────────│ header  │
   │  hash=H │   =H     │ root,⋯  │          │ ⋯       │
   └─────────┘          └─────────┘          └─────────┘
     tamper here  ─────▶ breaks every prev_hash to the right

Edit a transaction in block N-1. Its merkle root changes, so block N-1’s header hash H changes. But block N still stores the old H in its prev_hash, so block N no longer points at the real N-1 — the link is visibly broken. To repair it you’d have to recompute N’s hash, which changes N+1’s expected prev_hash, and so on to the tip. One edit forces you to redo every block after it. Today that’s “merely” a lot of hashing; on Day 19, Proof-of-Work makes each of those recomputations cost real, measurable work — which is what turns “tamper-evident” into “tamper-resistant.”

The merkle root, briefly

You don’t need to hold all transactions to check the header — you need their merkle root. Pair up the txids, hash each pair, repeat until one hash remains (an odd one out is paired with itself):

   txid0  txid1   txid2  txid3
     └──┬──┘        └──┬──┘
      h01            h23
        └──────┬──────┘
            merkle root        ← goes in the header

rust/btcmini/src/block.rs builds this in merkle_root(). The payoff (which real Bitcoin uses for lightweight wallets) is that you can prove one transaction is in a block with just the handful of sibling hashes along its path, not the whole block — but even at our toy scale, it’s what lets the small header stand in for the full body.

Build it

In rust/btcmini:

1. Read src/hash.rs and run cargo test hash. Note how Hash256 serializes as hex and how double_sha256 is the only hash in the crate — ids, the merkle tree, and (Day 18) addresses all route through it.
2. Read src/block.rs. Hand a block to mine (Day 19’s job, but it works today), then recompute its hash after flipping one byte of a transaction and watch the id change completely — the avalanche property, live.
3. Run the merkle_root tests: confirm the root is order-sensitive (swapping two txids changes it) and that it handles an odd number of transactions.

It actually happened — the day SHA-1 died

Bitcoin chose SHA-256, not the older SHA-1, and 2017 showed why it had to. On 23 February 2017, researchers at Google and CWI Amsterdam announced SHAttered — the first practical collision in SHA-1: two different PDF files with the same SHA-1 digest, found with about 2^63 computations rather than the 2^80 a perfect 160-bit hash should require. A hash you can collide is a fingerprint you can forge: swap the data, keep the digest, break the binding a chain depends on. SHA-1 had been theoretically wounded since 2005; SHAttered made it dead in practice, and systems still relying on it (including some version-control and certificate uses) scrambled to migrate. The lesson the chain bakes in: a ledger is only as tamper-evident as its hash, so you pick one with a wide margin — SHA-256’s 2^256 space — and you don’t get cute.

Where this leaves us

You now have an append-only structure that screams if anyone edits the past. What it does not yet have: any notion of coins, ownership, or who is allowed to spend what. A chain of hashes proves the history wasn’t altered; it says nothing about whether the transactions in it were ever legitimate. That’s tomorrow: the UTXO model, where a coin is an unspent output, spending it removes it, and a double-spend becomes something the ledger structurally cannot represent.

→ Next: Day 17 · The UTXO Model · Back to the Project 5 overview

Check your understanding

1. State the double-spend problem in one sentence, and the traditional (pre-Bitcoin) fix. What is this project trying to do instead?
2. Name the three properties of a cryptographic hash that the chapter relies on, and say what each one buys the chain.
3. What is double-SHA-256, and why does the crate wrap a digest in a Hash256 newtype instead of using a bare [u8; 32]?
4. Walk through what happens to the hashes when someone edits a transaction in an old block. Why does it “break every hash to the right”?
5. Why did Bitcoin choose SHA-256 over SHA-1, and what real 2017 event made that choice look prescient?

Show answers

1. The double-spend problem: because a coin is just data and data copies for free, nothing inherently stops you from spending the same coin twice (paying two people with identical bytes). The traditional fix is a trusted third party — a bank with one authoritative ledger. This project rebuilds a single agreed-upon, append-only ledger without any trusted party, using cryptography and (later) Proof-of-Work.
2. Deterministic (same input → same digest, so independent parties can confirm they hold identical data); avalanche (one flipped input bit changes ~half the output unpredictably, so there’s no “close” forgery); collision/preimage resistance (you can’t find data matching a given digest, nor two inputs that collide, so a digest binds to its data and can’t be swapped out).
3. Double-SHA-256 is SHA-256 applied twice, SHA256(SHA256(bytes)); the second pass guards against length-extension attacks. The Hash256 newtype makes a block id a distinct type from other 32-byte values (pubkeys, buffers), so the compiler rejects “right size, wrong meaning” mix-ups at zero runtime cost.
4. Editing a transaction changes its block’s merkle root, which changes that block’s header hash. The next block still stores the old hash in its prev_hash, so the link no longer matches — visibly broken. Repairing it means recomputing that block’s hash, which changes the next block’s expected prev_hash, cascading all the way to the tip. So one edit forces recomputing every following block.
5. SHA-256 has a far wider security margin (2^256 output space) than SHA-1’s 160 bits. On 23 February 2017, Google and CWI’s SHAttered result produced the first practical SHA-1 collision (two distinct PDFs, same digest), proving SHA-1’s fingerprints could be forged — exactly the failure a tamper-evident chain cannot tolerate.