Day 19 · Proof-of-Work

Day 18 gave every transaction a way to prove it’s legitimate. But legitimacy isn’t agreement. Picture two honest miners on opposite sides of the planet, each assembling a perfectly valid next block at the same instant. Both are valid. Both point at the current tip. Which one is the real next block? With no central server to break the tie, you need a rule that’s objective, that nobody can game by simply asserting it, and that makes rewriting history expensive. That rule is Proof-of-Work, and building it is the moment the whole chain finally answers its founding question: how do strangers converge on one history?

The idea: make blocks costly to produce

Proof-of-Work attaches a price tag to every block — not in money, but in computation. To publish a block you must find a nonce (a throwaway number in the header) such that the block’s hash, read as a 256-bit number, lands below a target. Because double-SHA-256 is effectively random and unpredictable (Day 16), there is no clever way to find such a nonce — you can only guess, hash, check, repeat. Finding one is proof you did, on average, a known amount of work. Verifying it is a single hash. That asymmetry — hard to produce, trivial to check — is the entire trick.

   target for bits = 16  (the top 16 bits must be zero):
   0000_0000 0000_0000 1111_1111 … 1111_1111   (2^240 − 1)
   └──── must be 0 ────┘└─ anything below the line passes ─┘

   mining: keep changing the nonce, re-hash, until  hash ≤ target.

Target and difficulty

The target is a 256-bit threshold; difficulty is how low you set it. The lower the target, the more leading zeros a passing hash needs, the more guesses it takes. In rust/btcmini/src/pow.rs we keep this as plain as possible — bits is literally the number of required leading zero bits:

pub fn target_from_bits(bits: u32) -> Hash256 {
    // the largest 256-bit value with `bits` leading zeros, all lower bits set
}

pub fn meets_target(hash: &Hash256, target: &Hash256) -> bool {
    hash.0 <= target.0   // big-endian: a [u8; 32]'s natural Ord IS numeric comparison
}

That last line is a small, satisfying piece of Rust: because the bytes are stored big-endian (most significant first), the array’s built-in lexicographic Ord is exactly numeric comparison of the 256-bit values, so “does this hash meet the target?” is just hash ≤ target. No big-integer library, no hand-rolled comparison.

A simplification, stated honestly

Real Bitcoin packs the target into a compact mantissa/exponent field — also confusingly called bits, e.g. 0x1d00ffff — and adjusts difficulty automatically every 2016 blocks (about two weeks) to keep the average block interval near 10 minutes as total hash power rises and falls. Our bits is the simpler “count of leading zero bits,” and difficulty is fixed. We trade Bitcoin’s self-tuning machinery for something you can read straight out of a hash with your own eyes; the mechanism — hash below a target — is identical.

The mining loop

Mining is the least glamorous loop in the crate, and that’s the point — its security comes from how many times it runs, not from cleverness. From rust/btcmini/src/block.rs:

pub fn mine(header: &mut BlockHeader) -> u64 {
    let target = target_from_bits(header.bits);
    let mut attempts = 0;
    loop {
        attempts += 1;
        if meets_target(&header.hash(), &target) {
            return attempts;          // found a winning nonce
        }
        header.nonce = header.nonce.wrapping_add(1);
    }
}

Increment the nonce, hash the header, check against the target, repeat until it passes. The attempts count is the literal work done. The most_nonces_fail_the_target test in block.rs shows the flip side: scan thousands of nonces at difficulty 16 and the overwhelming majority fail — which is precisely why finding one that passes is evidence of effort.

By the numbers — what “difficulty” costs

A target of bits leading zero bits means each random hash passes with probability 2^-bits, so finding a passing nonce takes about 2^bits attempts on average:

   bits = 8   →  ~256 hashes        (instant; used in tests)
   bits = 16  →  ~65,536 hashes     (our default; a visible blink)
   bits = 24  →  ~16.7 million      (now you wait a moment)

Each extra bit doubles the expected work — difficulty is exponential in bits. Bitcoin sets its target so that the entire network finds a block every ~10 minutes on average; as of ~2024 the network computed on the order of hundreds of exahashes (10^20) per second, meaning a single block represents something like 10^23 hash attempts across all miners. That staggering, real expenditure is what stands between an attacker and a rewritten history — to redo a past block you must out-hash everyone, racing forward, from that block to the tip.

The most-work chain rule

Now the payoff. When honest nodes see two competing valid blocks, they don’t vote, negotiate, or ask an authority. Each node simply keeps building on the chain it saw first, and the network resolves the tie the moment one branch gets the next block — because every node then prefers the branch carrying the most cumulative Proof-of-Work. Our Blockchain measures and compares exactly that, in rust/btcmini/src/chain.rs:

pub fn total_work(&self) -> u128 {
    self.blocks.iter().map(|b| block_work(b.header.bits)).sum()
}

A node adopts a competing chain only if it’s valid and has strictly more work than its own (the maybe_adopt logic you’ll wire up on Day 20). This is why a fork is temporary: branches race, one pulls ahead in accumulated work, and everyone converges on it; the transactions in the abandoned branch fall back to the mempool to be mined again.

                ┌── block A4 ──╴ (orphaned: less total work)
   …─ A3 ───────┤
                └── block B4 ── B5 ──╴ (adopted: most work wins)

Under the hood — why “longest” really means “most work”

You’ll often hear “the longest chain wins,” but that’s a shortcut. The rule is most accumulated work, because difficulty changes over time: a short chain of very-hard blocks can embody more total work than a longer chain of easy ones, and the hard one is the legitimate winner. In our toy, difficulty is fixed, so more blocks does mean more work and “longest” and “most-work” coincide — but the code sums work, not block count, on purpose, so the rule stays correct the day difficulty varies. The security assumption underneath all of it: an honest majority of hash power. If one party controls more than half, it can consistently out-work everyone and rewrite recent history — the “51% attack.” Proof-of-Work doesn’t make attacks impossible; it makes them as expensive as outspending the rest of the world combined.

This is the same bargain as the playbook’s thread, viewed from the chain side. What does building this force you to understand? That Bitcoin doesn’t replace trust with magic — it replaces “trust this person” with “trust that no one will burn more electricity than everyone else to lie to you.” Rust strikes the parallel bargain: it doesn’t trust the programmer, it makes the unsafe program fail to compile. Both buy safety by making the bad outcome costly-to-impossible rather than merely forbidden.

It actually happened — the March 2013 accidental fork

On 11–12 March 2013, Bitcoin split into two chains at block 225430. A new release (v0.8, using LevelDB) accepted a large block that the older v0.7 (limited by a BerkeleyDB lock) rejected as invalid — so the two versions disagreed about validity and built different histories. For several hours there were two competing chains, and the most-work rule alone couldn’t fix it, because the two sides didn’t even agree on which blocks were valid. It was resolved by miners on v0.8 voluntarily downgrading to v0.7 to abandon the branch the whole network could accept — sacrificing real work to reconverge — and documented afterward in BIP 50. The episode is the perfect teacher for this chapter: consensus is “the most-work valid chain,” and valid is defined by the rules every node enforces (the same rules our connect checks). Get those rules subtly out of sync between implementations and even Proof-of-Work can’t save you — which is why a chain’s validation code is the most safety-critical code it has.

Build it

In rust/btcmini:

1. Read src/pow.rs and src/block.rs. Run cargo test -- pow block and watch mining_finds_a_nonce_that_meets_the_target and most_nonces_fail_the_target.
2. Run cargo run -- demo at its bits = 12, then bump it to 20 in demo() and feel mining take measurably longer — difficulty is exponential, live.
3. In chain.rs, read connect: note the order of checks — links to the tip, then PoW meets the target, then merkle root, then the transactions and coinbase amount. Then read total_work and the most_work_chain_beats_a_shorter_one test.

Where this leaves us

The four pillars now stand: a tamper-evident chain, a UTXO ledger, cryptographic ownership, and Proof-of-Work with the most-work rule. But there’s one last gap between “a chain in one program” and “a network.” Mining and the most-work rule only converge strangers if those strangers can actually exchange blocks and transactions. Tomorrow we put the chain on the wire: a std::net TCP node with a mempool, where one node mines a block, broadcasts it, and a second node — running in a different process — adopts it and ends up on the exact same chain. The theory becomes two computers agreeing.

→ Next: Day 20 · A P2P Node · Prev: Day 18 · Keys and Signatures · Back to the Project 5 overview

Check your understanding

1. What asymmetry makes Proof-of-Work useful, and how does the mining loop exploit it? What is the nonce for?
2. What is the relationship between the target and difficulty? In our crate, what does bits literally mean, and how does that differ from real Bitcoin?
3. Why is meets_target just hash.0 <= target.0? What property of the byte layout makes that correct?
4. Explain the most-work chain rule. Why does the code sum work rather than count blocks, and what is the honest-majority assumption it rests on?
5. What did the March 2013 fork reveal about the phrase “the longest chain wins”? Why couldn’t Proof-of-Work alone resolve it?

Show answers

1. Proof-of-Work is hard to produce, trivial to verify: finding a nonce whose block hash is below the target takes on average 2^bits random guesses (no shortcut, because the hash is unpredictable), but checking it is a single hash. The mining loop just increments the nonce, re-hashes the header, and tests hash ≤ target until it passes; the nonce is the throwaway number it varies to search.
2. The target is a 256-bit threshold and difficulty is how low you set it — a lower target needs more leading zeros, hence more guesses. In our crate bits is literally the count of required leading zero bits; real Bitcoin uses a compact mantissa/exponent target and auto-adjusts difficulty every 2016 blocks to hold ~10-minute blocks.
3. Because the hash bytes are stored big-endian (most-significant byte first), a [u8; 32]’s built-in lexicographic ordering is identical to numeric comparison of the 256-bit value — so hash ≤ target as arrays is hash ≤ target as numbers, no big-integer math needed.
4. A node adopts another chain only if it is valid and has strictly more cumulative Proof-of-Work. The code sums work (not block count) because difficulty can vary, and a short chain of hard blocks can outweigh a long chain of easy ones — summing work keeps the rule correct in that case. It assumes an honest majority of hash power; a party with over 50% can out-work everyone and rewrite recent history (the 51% attack).
5. It revealed that the rule is really “the most-work valid chain,” and that validity is defined by the rules each node enforces. In March 2013, v0.8 and v0.7 disagreed about whether a block was valid, so they built different histories; Proof-of-Work couldn’t choose between them because the two sides didn’t agree on the validity rules in the first place. It was fixed socially, by miners downgrading to reconverge (BIP 50).