Proof of Work & Mining

So far our blocks link together with prev-hash pointers, but nothing costs anything to make one. Anyone could rewrite history by re-hashing a few blocks on a laptop. Proof of Work fixes that: it makes a valid block expensive to produce but trivial to check. That asymmetry is the whole trick behind how untrusting strangers agree on one ledger without a referee.

In this chapter we’ll write the rule that decides whether a hash is “good enough,” and the loop that hunts for a hash that passes. It’s only about thirty lines of Rust, but it’s the beating heart of mining.

Why this matters

Mining is a brute-force lottery. There’s no clever shortcut — you just keep trying until you get lucky. But anyone who receives your block can verify your luck in a single hash. That gap between hard to do and easy to check is what makes the chain tamper-evident. For the full economic and game-theoretic picture, see Proof of Work in Depth.

The difficulty rule: leading zero bits

Real Bitcoin compares a block’s hash, interpreted as a giant 256-bit number, against a target: the hash must be numerically less than or equal to that target. The smaller the target, the rarer a qualifying hash, the more work required. The target is packed into a compact field called bits, and the network retargets it every 2016 blocks to keep blocks roughly ten minutes apart.

We’re going to simplify that to something you can read at a glance: a hash is valid if it begins with at least bits leading zero bits. This is equivalent in spirit — requiring more leading zeros is exactly like shrinking the target — and it keeps the code honest and short.

Same idea, simpler dial

Our bits means “how many zero bits the hash must start with.” Bitcoin’s bits is a compressed encoding of a 256-bit threshold. Same direction (more = harder), different units. The deep version lives in Target, bits & Difficulty.

Here is the entire pow module — copied verbatim from src/pow.rs:

//! Proof of Work.
//!
//! Real Bitcoin compares the block hash against a 256-bit target. We use a
//! simpler, equivalent-in-spirit rule that's easy to read: a hash is valid if it
//! begins with at least `bits` leading zero **bits**. More required zeros =
//! exponentially more work.

use crate::hashing::Hash;

/// Count the leading zero bits of a hash (big-endian, most-significant first).
pub fn leading_zero_bits(hash: &Hash) -> u32 {
    let mut count = 0;
    for &byte in hash {
        if byte == 0 {
            count += 8;
        } else {
            count += byte.leading_zeros();
            break;
        }
    }
    count
}

/// Does this hash satisfy the difficulty `bits`?
pub fn meets_target(hash: &Hash, bits: u32) -> bool {
    leading_zero_bits(hash) >= bits
}

Two small functions. Let’s read them slowly, because every line teaches a piece of Rust.

Counting zeros, bit by bit

A Hash is 32 bytes — an array of 32 u8 values. (u8 is an unsigned 8-bit integer: it holds a whole number from 0 to 255, exactly one byte.) We want to count how many bits at the front are zero, reading the most-significant byte first.

let mut count = 0;
for &byte in hash {

let mut count = 0; declares a mutable variable. By default Rust variables are immutable — you can’t reassign them — so we add mut because we’re going to keep adding to count.

The for &byte in hash loop walks the array one byte at a time. The & in &byte is a pattern that destructures the reference: iterating over hash hands us &u8 references, and &byte peels off the reference so byte is a plain u8 we can compare and add. (It’s the mirror image of taking a reference — here we’re removing one in the pattern.)

    if byte == 0 {
        count += 8;
    } else {
        count += byte.leading_zeros();
        break;
    }

Now the logic. We scan from the front:

• If a byte is entirely zero (byte == 0), all 8 of its bits are zero, so we add 8 and keep going to the next byte.
• The moment we hit a non-zero byte, the run of leading zeros ends inside that byte. We ask the byte how many zero bits it starts with using byte.leading_zeros() — a method the standard library gives every integer type — add that, and break out of the loop. There’s no point looking further; the streak is over.

break immediately stops the for loop. Without it, we’d keep scanning bytes after the streak ended and get a nonsense count. After the loop we just return count.

leading_zeros() is a built-in

leading_zeros() is not something we wrote — it’s a method on Rust’s integer types (u8, u32, …) that counts the zero bits before the first 1, most-significant first. For a u8, 0b0001_1010 returns 3. It usually compiles down to a single CPU instruction, so it’s fast. We lean on it instead of hand-rolling bit math.

A worked example. Suppose a hash starts with the bytes 00 00 0F …:

• byte 0x00 → all zero → count = 8
• byte 0x00 → all zero → count = 16
• byte 0x0F is 0b0000_1111 → leading_zeros() is 4 → count = 20, then break

So this hash has 20 leading zero bits. If our difficulty bits were 16, it passes; if it were 24, it fails.

The pass/fail check

pub fn meets_target(hash: &Hash, bits: u32) -> bool {
    leading_zero_bits(hash) >= bits
}

meets_target is the one-line verdict: count the leading zeros, and return whether there are at least as many as required. It returns a bool. Note there’s no semicolon on that last line — in Rust, the final expression of a function is its return value. This is the function the rest of the chain calls to ask, “is this block hash valid Proof of Work?”

And here’s the asymmetry made literal: verifying a block calls meets_target exactly once — one hash, one comparison, microseconds. Producing a block, as we’ll see next, may call it billions of times.

The nonce loop: Block::mine()

Now the lottery itself. Recall from The Block & the Header that the header contains a field called nonce (a u64 — an unsigned 64-bit integer). The nonce exists for exactly one reason: it’s the dial the miner spins. Changing it changes the header, which changes the header’s hash, which gives us a fresh ticket in the lottery.

Here is mine() from src/block.rs, copied verbatim:

    /// Brute-force the nonce until the header hash meets the difficulty target.
    /// (Real miners also roll the timestamp and a coinbase extra-nonce; one
    /// counter is enough to demonstrate the idea.)
    pub fn mine(&mut self) {
        self.header.nonce = 0;
        loop {
            if meets_target(&self.header.hash(), self.header.bits) {
                break;
            }
            self.header.nonce = self.header.nonce.wrapping_add(1);
        }
    }

Let’s walk through it.

pub fn mine(&mut self) takes &mut self — a mutable reference to the block — because mining changes the block in place by writing into self.header.nonce. A plain &self would only let us read.

self.header.nonce = 0;

We start the counter at zero. (This also resets it if the block was mined before and we’re re-mining.)

loop {
    if meets_target(&self.header.hash(), self.header.bits) {
        break;
    }
    self.header.nonce = self.header.nonce.wrapping_add(1);
}

loop { … } is Rust’s infinite loop — it runs forever until something inside breaks out. Each iteration:

1. Computes the header hash with self.header.hash() (double-SHA-256 of the encoded header).
2. Asks meets_target whether that hash has enough leading zeros. If yes, break — we found a winning nonce, and we’re done.
3. If not, bump the nonce by one and try again.

That step 3 uses wrapping_add(1) instead of plain + 1. Here’s why it matters. A u64 maxes out at 18_446_744_073_709_551_615. In debug builds, + 1 past the maximum would panic (crash) on overflow; in release builds it would silently wrap, which is inconsistent. wrapping_add makes the intent explicit and identical everywhere: when the counter hits the top, it wraps cleanly back to 0 instead of crashing. We never want our miner to die just because it tried a lot of nonces.

loop vs while

We used loop because we don’t have a counting condition up front — we spin until we get lucky and break. If instead we wanted “try at most N nonces,” a while self.header.nonce < n { … } would fit: while checks a condition before each pass and stops when it’s false. loop is the right tool when the only exit is an event inside the body.

Why it’s a lottery (and why that’s the point)

SHA-256 output is effectively random and unpredictable — flip one bit of input and the whole hash scrambles. So there is no way to compute the right nonce directly. You can’t reason your way to a hash with 20 leading zeros; you can only try nonces and check. On average, getting k leading zero bits takes about 2^k attempts. Each extra required zero doubles the expected work. That’s the “exponentially more work” the module comment promises.

This is exactly why rewriting history is so costly. To change a transaction in block 100, an attacker would have to re-mine block 100 and every block after it (each block commits to the previous block’s hash), racing the honest network the whole time. Doing one block is a lottery; redoing a hundred while everyone else extends the real chain is a losing bet.

And the payoff for honesty: a node that receives your freshly mined block doesn’t trust you — it just runs meets_target on your header once. Cheap to check, expensive to fake. That single line is how strangers agree.

Try it

Run the demo and watch every block hash come out starting with 0000:

cd rust/blockchain-from-scratch
cargo run -- demo

Each mined block … line prints a block hash like 0000cd8509b9b185b342c1eff4a73cfed4320208bb487f6a1cbbe93122cb0bd0. Those four leading hex zeros are 16 zero bits — proof that mine() spun the nonce until meets_target returned true. The first non-zero nibble after them is where leading_zeros() stopped counting.

By the numbers — our 16 bits vs Bitcoin’s ~78

Our demo requires 16 leading zero bits, so a block takes about 2^16 ≈ 65,000 hash attempts — a blink on a laptop. Real Bitcoin is on another planet:

our demo:             16 zero bits → ~2^16 ≈ 6.5 × 10^4   hashes/block
mainnet (mid-2020s): ~78 zero bits → ~2^78 ≈ 3 × 10^23   hashes/block

That’s roughly 2^62 times more work per block, which is why the entire planet’s mining hardware — hundreds of exahashes (10^18 hashes) every second — still needs about ten minutes to find one. Same meets_target check; the only thing that changed is the number of required zeros. Each extra zero bit doubles the cost, so the gap between “fun on a laptop” and “secures a trillion-dollar ledger” is just ~62 turns of that one dial. (Figures drift; treat the mainnet numbers as approximate, as of the mid-2020s.)

Check your understanding

1. Why does leading_zero_bits call break the instant it sees a non-zero byte instead of continuing through the rest of the hash?
2. What would go wrong if mine() used self.header.nonce + 1 instead of wrapping_add(1), and the loop happened to run an enormous number of times?
3. Our bits field means “required leading zero bits.” How does that relate to Bitcoin’s real 256-bit target, and which direction makes mining harder for each? (See Target, bits & Difficulty.)
4. Verifying a block calls meets_target once; mining may call it billions of times. Why is that asymmetry the whole point of Proof of Work?
5. Roughly how much more work does requiring 20 leading zero bits take than requiring 16?

Show answers

1. Because the run of leading zeros ends inside the first non-zero byte — once a 1 bit appears, no later byte can add to the leading-zero count. It uses byte.leading_zeros() to count the zeros before that 1 and breaks; scanning further would wrongly inflate the count.
2. With plain + 1, when the u64 nonce reaches its maximum it would panic (crash) on overflow in debug builds (and silently wrap in release) — so a miner that tried that many nonces could die. wrapping_add(1) makes the behavior explicit and identical everywhere: it wraps cleanly back to 0 instead of crashing.
3. Both are a difficulty dial pointing the same direction — more = harder. Our bits is the required count of leading zero bits; Bitcoin’s bits is a compressed encoding of a 256-bit target the hash must be ≤. More required zeros is equivalent to a smaller target, and both make qualifying hashes rarer.
4. Because verifying runs meets_target exactly once (one hash, microseconds) while producing a valid block may run it billions of times — that “hard to do, trivial to check” gap is what makes the chain tamper-evident: cheap for honest nodes to verify your work, expensive for anyone to fake or rewrite.
5. About 16× more — each extra required zero bit roughly doubles the expected attempts (≈ 2^k for k zeros), so 4 more bits is 2^4 = 16 times the work.