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.
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 500 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 ^^^^^^^^ 8 leading hex zeros (32 leading binary zeros)
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.
Theorem 14.2 (Adjustment Bounds)
The difficulty adjustment is clamped to prevent extreme changes:
0.25 ≤ adjustment_factor ≤ 4.0
Difficulty can at most quadruple or quarter in a single adjustment period.
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.
Theorem 14.3 (Heaviest Chain Rule)
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.
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)
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.0002% Expected daily blocks = 144 × 0.000002 = 0.000288 Daily revenue (at 6.25 BTC subsidy, $40,000/BTC): = 0.000288 × 6.25 × $40,000 = $72 Daily profit = $72 - $3.60 = $68.40
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's longer
Theorem 14.4 (Attack Success Probability)
An attacker with fraction q of total hash power attempting to reverse a transaction with z confirmations has success probability:
P(success) = 1 − Σₖ₌₀^z [λᵏe^(-λ)/k! × (1 − (q/p)^(z-k))]
where λ = z(q/p) and p = 1 − q.
| Attacker Hash % | 1 conf | 3 conf | 6 conf |
|---|---|---|---|
| 10% | 20.4% | 1.3% | 0.02% |
| 25% | 43.7% | 12.9% | 2.4% |
| 33% | 55.6% | 25.7% | 9.1% |
| 45% | 73.3% | 51.0% | 33.5% |
14.8.2 The 51% Attack
Theorem 14.5 (Majority Attack)
An attacker controlling more than 50% of hash power can:
- 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 don't own
- Change consensus rules (nodes still validate)
14.8.3 Selfish Mining
Remark 14.1 (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.2 (Energy Consumption)
Bitcoin's energy consumption is a feature, not a bug. The energy spent mining represents a real-world cost that attackers must also pay. Security is proportional to energy expenditure.
As of 2024, Bitcoin's estimated annual energy consumption is comparable to a small country (~100-150 TWh/year).
Theorem 14.6 (Security Budget)
The cost to attack Bitcoin is bounded below by the mining revenue:
attack_cost ≥ mining_revenue × attack_duration / block_time
This creates a "security budget" paid by inflation (subsidy) and fees.
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 are roughly 10 billion times more efficient 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?
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?