Proof of Work

“I am going to solve the double-spending problem by making computers guess numbers until the room gets uncomfortably warm.” — Satoshi Nakamoto¹ (probably).

Bitcoin Paper

The Sybil Problem

PBFT (Practical Byzantine Fault Tolerance) relies on knowing exactly how many nodes ($N$) exist, so it can calculate that $2/3rds$ threshold. But in a permissionless network (the internet), what stops a malicious actor from booting up 10,000 fake nodes in an AWS server farm to hijack the $2/3rds$ majority?

This is called a Sybil Attack² (essentially showing up to an election with a million fake mustaches and voting a million times). If identity is cheap, the $3f+1$ math immediately collapses.

The Origin: Anti-Spam Roots

Before Bitcoin, PoW was a tool to fight email spam. In 1997, Adam Back proposed Hashcash:

• The Idea: To send an email, your computer must solve a moderately difficult mathematical puzzle.
• The Logic: For a normal user, solving one puzzle takes 1 second (unnoticeable). For a spammer sending 10 million emails, it takes 115 days of CPU time. The “cost” makes the attack unprofitable.

The Nonce Hunt

In the 2008 Bitcoin Whitepaper, Satoshi realized that to prevent Sybil attacks, identity must be tied to a scarce, undeniably physical resource: Computation (Thermodynamic Energy).

To participate in the consensus, a node cannot just say “I vote for this block.” It must prove it expended raw CPU power to earn the right to propose that block. This adapts the Hashcash idea.

The Formal Mechanics

Instead of nodes talking to each other to reach a vote (like PBFT), they race to solve a cryptographic puzzle.

1. The Puzzle: Take the block header (which includes the previous block’s hash, a Merkle Root of current transactions, and a random number called a Nonce). Pass it through the SHA-256 hashing algorithm.
2. The Target: The resulting hash must begin with a specific number of zero bits (e.g., 0000000000000000x...).
3. The Work: Because cryptographic hashes are unpredictable, the only way to find a hash with enough leading zeros is brute-force guessing. The node increments the Nonce (1, 2, 3…) and hashes it again and again.

Once a node finds the lucky Nonce, it broadcasts the block. The network easily verifies it (hashing it once takes microseconds), and accepts it by chaining the next block to its hash.

The Longest Chain Rule

Because work is chained, changing a past block requires redoing the Proof of Work for that block, plus all blocks after it.

Satoshi decreed that the network will always consider the longest chain to be the definitive truth, because it represents the greatest amount of cumulative computational effort. It is the mathematical manifestation of the majority.

The Mathematical Formalization: Gambler’s Ruin

Can an attacker outpace the honest network and rewrite history (a “51% attack” or double-spend)? Satoshi modeled this race between the honest chain and the attacker’s chain as a Binomial Random Walk.

Let:

• $p =$ probability an honest node finds the next block.
• $q =$ probability the attacker finds the next block.
• $z =$ the number of blocks an attacker needs to catch up to the honest chain.

The probability ($q_z$) that the attacker will ever catch up from $z$ blocks behind is a classic Gambler’s Ruin problem:

If the honest nodes control the majority of the CPU power ($p > q$), the attacker’s probability of catching up drops exponentially as the number of confirmed blocks ($z$) increases.

Furthermore, Satoshi calculated the exact probability of an attacker catching up by modeling the attacker’s potential progress as a Poisson distribution (with expected value $\lambda = z(q/p)$). To find the exact likelihood that an attacker could still compromise the transaction, Satoshi multiplied the Poisson density for each amount of progress ($k$) the attacker could have made by the probability they could catch up from that point, yielding the following summation:

This formal calculation is the mathematical origin of the “6-block confirmation” rule. If an attacker controls 10% of the network’s hash power ($q=0.1$) and the merchant waits for $z=6$ blocks, the attacker’s probability of rewriting the chain drops to $0.0002428$ (about $0.02\%$). However, if the attacker controls 30% of the hash power ($q=0.3$), $z=6$ only drops the probability to around $5\%$, and the merchant would technically need to wait $z=24$ blocks to reach a $<0.1\%$ risk threshold. As $z$ grows, the math violently crushes the attacker’s odds of success to vanishingly small fractions of a percent, providing a quantifiable metric for “probabilistic finality.”

Bitcoin

Satoshi didn’t just invent a cool math trick; they solved the Double-Spending problem without a central bank. To make the system self-sustaining, Satoshi merged the consensus algorithm with Game Theory and Economics.

If you rely on volunteers to burn electricity, the network will die. So, Satoshi added an Incentive:

1. Block Rewards: The first transaction in a block is a special one that creates new coins out of thin air and gives them to the winning miner. (Literal money printer go brrr, but mathematically capped at 21 million).
2. Transaction Fees: Users attach small tips to their transactions to incentivize miners to include them in the next block.

This incentive structure is the actual glue of BFT in Bitcoin. If a greedy attacker somehow buys enough hardware to pull off a 51% attack, they face a choice: Use that massive power to defraud people and destroy the network’s trust (crashing the value of the coins), or just play by the rules and legally mine more new coins than everyone else combined. It is economically irrational to attack the network.

The Curse That Turns PC into Space Heaters

Although PoW is an elegant solution filling the gap from PBFT, there are several major drawbacks:

1. The Environmental Cost: Tying security to thermodynamic work means the network literally consumes the electricity of a medium-sized country.
2. Hardware Centralization: The “One-CPU-One-Vote” ideal died with the invention of ASICs (Application-Specific Integrated Circuits). Mining became dominated by massive industrial server farms, ironically re-centralizing the network.
3. Probabilistic Finality: In PoW, a transaction is never 100% mathematically final; it just becomes exponentially harder to reverse as blocks pile up (Gambler’s Ruin). Financial institutions prefer Deterministic Finality (when a transaction is approved, it is mathematically impossible to revert without burning the whole system down).
   The next solution? $\rightarrow$Proof of Stake