How can a decentralized network agree on a single history without a central authority? Bitcoin's answer is proof of work: a computational puzzle that is hard to solve but easy to verify. By requiring significant work to create blocks, Bitcoin makes rewriting history economically prohibitive.
Proof of work transforms electricity into security. Understanding this mechanism is essential for reasoning about Bitcoin's security model and the economics of mining.
14.1 The Concept of Proof of Work
Proof of work was invented independently multiple times, notably by Cynthia Dwork and Moni Naor (1992) for combating email spam, and by Adam Back (1997) in the Hashcash system.
Definition 14.1 (Proof of Work)
A proof of work system requires a prover to demonstrate that they have expended computational effort. The proof must be:
- Hard to produce: Requires significant computation
- Easy to verify: Can be checked with minimal effort
- Adjustable difficulty: Can scale with available compute power
14.2 Bitcoin's Hash Puzzle
Bitcoin uses a hash-based proof of work: find an input that produces a hash below a target value.
Definition 14.2 (Bitcoin Proof of Work)
A block satisfies the proof of work requirement if:
SHA256(SHA256(header)) < target
where header is the 80-byte block header and target is a 256-bit threshold determined by the difficulty.
Because cryptographic hash functions behave as random oracles, the only way to find a valid hash is exhaustive search—trying different nonces until one works.
Probability Background
Two facts from elementary probability are used repeatedly in this volume. First, if an experiment succeeds with probability p on each independent trial, the number of trials until the first success follows the geometric distribution, whose expected value (long-run average) is 1/p. Second, the number of successes in a long stretch of such trials is well approximated by the Poisson distribution: the count equals m with probability λᵐe^(−λ)/m!, where λ is the expected count. Both facts can be taken on faith or found in any introductory probability text.
Theorem 14.1 (Expected Attempts)
If the target is T and hashes are uniformly distributed over [0, 2²⁵⁶), the expected number of attempts to find a valid hash is:
E[attempts] = 2²⁵⁶ / T
Proof.
Each hash has probability p = T / 2²⁵⁶ of being below the target. The number of attempts follows a geometric distribution with parameter p, giving expected value 1/p = 2²⁵⁶/T. □
14.3 Difficulty and Target
The target is encoded in the block header's bits field and determines
how hard it is to mine a block.
Definition 14.3 (Difficulty)
The difficulty is the ratio of the maximum target to the current target:
difficulty = target_max / target_current
where target_max is the easiest possible target
(0x1d00ffff in compact form).
Example 14.1 (Difficulty Interpretation)
If difficulty = 50,000,000,000,000 (50 trillion):
- Finding a valid block is 50 trillion times harder than at difficulty 1
- Expected hashes: ~50 trillion × (genesis difficulty hashes)
- At ~360 EH/s network hashrate: ~10 minutes per block
14.3.1 Leading Zeros
A lower target means more leading zeros are required in the hash.
Example 14.2 (Leading Zeros)
Genesis block hash (2009, difficulty 1):
000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f ^^^^^^^^^^ 10 leading hex zeros (43 leading binary zeros)
The difficulty-1 target only requires about 32 leading zero bits; the genesis hash overshot it considerably.
A modern block (difficulty ~50T):
0000000000000000000234abc... ^^^^^^^^^^^^^^^^^^^ 19+ leading hex zeros (76+ leading binary zeros)
14.4 The Difficulty Adjustment Algorithm
Bitcoin automatically adjusts difficulty to maintain approximately 10-minute block intervals regardless of total network hash power.
Definition 14.4 (Difficulty Adjustment)
Every 2016 blocks (approximately 2 weeks), the difficulty is recalculated:
new_target = old_target × (actual_time / expected_time)
where expected_time = 2016 × 10 minutes = 1,209,600 seconds. The ratio actual_time / expected_time is clamped to the interval [0.25, 4]: difficulty can at most quadruple or quarter in a single adjustment period.
Remark 14.1 (Off-by-One Error)
Bitcoin Core's implementation measures actual_time = timestamp(block[h]) − timestamp(block[h − 2015]), the first and last blocks of the same 2016-block window, which spans only 2015 inter-block intervals rather than 2016. This makes difficulty systematically ~0.05% too low. The bug has been preserved for consensus compatibility.
Example 14.3 (Difficulty Adjustment)
If the last 2016 blocks took 12 days instead of 14:
actual_time = 12 days = 1,036,800 seconds
expected_time = 14 days = 1,209,600 seconds
adjustment = 1,036,800 / 1,209,600 = 0.857
new_difficulty = old_difficulty / 0.857
≈ old_difficulty × 1.167 (16.7% increase)
The network was mining too fast, so difficulty increases.
14.5 The Mining Process
Mining is the iterative process of searching for a valid proof of work.
Algorithm 14.1 (Mining)
- Construct a candidate block:
- Select transactions from mempool
- Create coinbase transaction
- Compute Merkle root
- Fill in header fields
- Set nonce = 0
- Compute hash = SHA256(SHA256(header))
- If hash < target, broadcast block (success!)
- Increment nonce
- If nonce overflows, modify extra nonce (in coinbase) and recompute Merkle root
- If new block received, restart with step 1
- Go to step 3
14.6 Hash Rate and Work
Definition 14.5 (Hash Rate)
Hash rate measures mining speed in hashes per second (H/s). Common units:
- KH/s = 10³ H/s (kilohash)
- MH/s = 10⁶ H/s (megahash)
- GH/s = 10⁹ H/s (gigahash)
- TH/s = 10¹² H/s (terahash)
- PH/s = 10¹⁵ H/s (petahash)
- EH/s = 10¹⁸ H/s (exahash)
Definition 14.6 (Chain Work)
The chain work (or cumulative work) of a blockchain is the sum of work in all blocks:
chainwork = Σᵢ (2²⁵⁶ / targetᵢ)
This represents the expected number of hashes to produce the entire chain.
Remark 14.2 (Protocol Rule: Heaviest-Chain Selection)
Bitcoin nodes follow the chain with the most cumulative work, not necessarily the longest chain. In practice, these usually coincide, but work is the correct metric. This is a protocol rule that every node implements rather than a theorem: it is stated formally as the Nakamoto fork choice rule in Definition 26.10, and its security consequences under an honest majority are analyzed in Section 14.8.
14.7 Mining Economics
Mining is economically rational only when revenue exceeds costs.
Definition 14.7 (Mining Revenue)
A miner's expected revenue per block is:
revenue = (subsidy + fees) × (miner_hashrate / network_hashrate)
(The block subsidy schedule is defined in Definition 15.2.)
Definition 14.8 (Mining Cost)
The primary costs of mining are:
- Electricity: Power consumption × electricity price
- Hardware: Amortized cost of ASICs
- Operations: Cooling, facility, maintenance
Example 14.4 (Mining Profitability)
An ASIC miner with:
- Hash rate: 100 TH/s
- Power: 3000 W
- Electricity: $0.05/kWh
Daily electricity cost = 3 kW × 24h × $0.05 = $3.60 If network hashrate = 500 EH/s: Share of blocks = 100 TH / 500 EH = 0.00002% Expected daily blocks = 144 × 0.0000002 = 0.0000288 Daily revenue (at 3.125 BTC subsidy, $40,000/BTC): = 0.0000288 × 3.125 × $40,000 = $3.60 Daily profit = $3.60 - $3.60 = $0.00
Remark 14.3 (Issuance Without an Issuer)
Proof of work plays a second role beside securing the chain: it is the mechanism by which every new coin enters circulation, and it is the only known mechanism that does so without an issuer. The subsidy (Definition 15.2) is paid to whoever finds a valid block, and finding one requires only the expenditure of resources that anyone, anywhere, may purchase. The protocol thus sells new coins at posted terms, so much expected work per coin, to an open market, holding no inventory and favoring no buyer. The difficulty of achieving this any other way is structural: a system whose validators are selected by stake presupposes that the stake already exists and is distributed, and a protocol cannot create its own initial distribution; it must be allocated by someone, on terms that someone chooses. Proof of work is what allows the question "who decided the initial distribution?" to have the answer: no one—only the rules, and whoever participated. Remark 15.4 records the history.
14.8 Security Analysis
Proof of work provides security through economic cost.
14.8.1 Double-Spend Attacks
Definition 14.9 (Double-Spend Attack)
A double-spend attack attempts to spend the same UTXO twice by:
- Making a payment that gets confirmed
- Mining a secret chain that spends the same UTXO differently
- Revealing the secret chain once it is longer
Theorem 14.2 (Attack Success Probability)
An attacker with fraction q of total hash power, where q < p = 1 − q, attempting to reverse a transaction with z confirmations has success probability:
P(success) ≈ 1 − Σₖ₌₀ᶻ [λᵏe^(−λ)/k! × (1 − (q/p)^(z−k))]
where λ = z(q/p). For q ≥ p, the attack succeeds with probability 1.
The formula is Nakamoto's (2008, whitepaper section 11), with the attacker's progress approximated as Poisson; the exact distribution is negative binomial, but the difference is small. We state it here without proof and derive it in Chapter 26 (Theorem 26.3) by a gambler's-ruin argument.
The following table evaluates the formula at representative attacker shares and confirmation depths. It is referenced throughout the book (Chapters 17, 26, and 36).
| Attacker Hash % | 1 conf | 3 conf | 6 conf | 12 conf |
|---|---|---|---|---|
| 10% | 20.5% | 1.3% | 0.02% | ~0% |
| 25% | 52.2% | 19.6% | 5.0% | 0.4% |
| 33% | 69.0% | 41.7% | 21.3% | 6.0% |
| 40% | 82.9% | 66.4% | 50.4% | 30.6% |
| 45% | 92.0% | 84.4% | 76.6% | 65.1% |
14.8.2 The 51% Attack
Remark 14.4 (Capabilities of a Majority Attacker)
An attacker controlling more than 50% of hash power can (the q ≥ p case of Theorem 14.2):
- Reverse any past transaction (given enough time)
- Prevent specific transactions from confirming
- Double-spend with certainty
However, they cannot:
- Create coins out of nothing
- Spend coins they do not own
- Change consensus rules (nodes still validate; Definition 13.18)
14.8.3 Selfish Mining
Remark 14.5 (Selfish Mining)
Eyal and Sirer (2014) showed that miners with >33% hash power can gain disproportionate rewards by strategically withholding blocks. This reduces the security threshold below 51%, though practical impact remains debated.
14.9 Energy and Thermodynamics
Proof of work converts electricity into security through an irreversible thermodynamic process.
Remark 14.6 (Energy Consumption)
Bitcoin's energy consumption is integral to its security model, not an inefficiency of it: the energy spent mining represents a real-world cost that an attacker must also pay, and the cost of attack scales with the honest network's expenditure. Whether the security purchased is worth the energy consumed is a separate, normative question (Remark 25.13).
As of 2024, Bitcoin's estimated annual energy consumption is comparable to a small country (~100–150 TWh/year).
Remark 14.7 (Security Budget)
As a first-order heuristic, the cost to attack Bitcoin scales with mining revenue:
attack_cost ≈ mining_revenue × attack_duration / block_time
This holds under zero-margin mining (free entry drives cost toward revenue) with rented hashrate and no recapture of block rewards by the attacker; real attacks also face a duration-independent hardware floor. This revenue stream is the "security budget" paid by inflation (subsidy) and fees (see Remark 25.11 for the demand-side condition).
14.10 Mining Hardware Evolution
Mining hardware has evolved through several generations.
| Era | Hardware | Efficiency | Period |
|---|---|---|---|
| CPU | Intel/AMD processors | ~1 MH/s | 2009-2010 |
| GPU | Graphics cards | ~100 MH/s | 2010-2013 |
| FPGA | Field-programmable arrays | ~1 GH/s | 2011-2013 |
| ASIC | Application-specific chips | ~100+ TH/s | 2013-present |
Modern ASICs hash roughly 100 million times faster than the CPUs Satoshi used in 2009.
Exercises
Exercise 14.1
If the target requires hashes to start with 72 zero bits, what is the expected number of hashes to find a valid block? Express your answer as a power of 2.
Exercise 14.2
The last 2016 blocks took 8 days. What is the adjustment factor? What is the new difficulty relative to the old?
Exercise 14.3
A miner has 1% of network hash power. What is their expected number of blocks per day? What is the standard deviation? (Hint: block counts are approximately Poisson, and a Poisson distribution's variance equals its mean.)
Exercise 14.4
Explain why the 4× maximum adjustment factor is important. What could go wrong if difficulty could adjust without bounds?
Exercise 14.5
An attacker with 30% hash power wants to double-spend a transaction with 6 confirmations. Using the formula or table, estimate their success probability. How long would they expect to wait for success?