Proof-of-Work

There is a lot of misinformation about Proof-of-Work and the role it plays in Bitcoin. It is variously described as a form of encryption, as the thing that keeps your coins safe, or as a waste of electricity that serves no purpose. None of these descriptions are quite right, and in this section we will look at what Proof-of-Work actually does.

It is my belief that the clearest way to understand Proof-of-Work is to stop thinking about it as cryptography, and to start thinking about Bitcoin as what it is: a distributed system. Once we do that, Proof-of-Work turns out to be the answer to a rather old question in distributed computing.

Bitcoin as a distributed system

Recall from Grokking Bitcoin that we replaced our Trusted Issuer with a network of independent timestamp nodes, each of which keeps its own copy of the ledger. These nodes are spread across the world, they are run by different parties, and they talk to each other over an unreliable network. Messages are delayed, nodes go offline, and from time to time parts of the network can’t reach each other at all.

Any system built this way is subject to the CAP theorem. The theorem tells us that a distributed data store can’t guarantee all three of the following at the same time:

• Consistency (C): every node sees the same data at the same time.
• Availability (A): every request to a node that is working receives a response.
• Partition tolerance (P): the system keeps working when the network between the nodes fails.

The CAP theorem was put forward by Eric Brewer in 2000, and proven by Seth Gilbert and Nancy Lynch in 2002 in Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services.

A network that spans the globe will suffer partitions whether we like it or not, so partition tolerance is not optional. The real choice is between consistency and availability, and Bitcoin chooses availability. Any node will accept a valid Transaction and any miner will try to build a block, without first waiting for the rest of the network to agree.

The price of that choice is that, at any given moment, the nodes don’t all hold the same ledger. Two miners can each find a valid block at nearly the same time, and for a little while part of the network builds on one block and part of it builds on the other. What Bitcoin offers instead of strict consistency is eventual consistency: given a little time, all the nodes converge on the same history.

Resolving the “C”

This leaves us with the question that matters. When two nodes hold different versions of the ledger, how do they decide which one wins?

In a system with a known, fixed set of participants, they could simply vote. Bitcoin has no such set. Anyone can run a node, and anyone can run a thousand nodes, so counting nodes or identities would hand the decision to whoever could create the most of them. Whatever method we use to resolve the disagreement has to be fair: no participant should be able to win more often than the resources they put in would justify, and every participant must be able to check the outcome for themselves.

This is exactly what Proof-of-Work provides. Each block carries a solution to a hash puzzle that is expensive to find and cheap to check. The whitepaper puts it this way in section 4:

“Proof-of-work is essentially one-CPU-one-vote. The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it.”

When the nodes disagree, they follow the chain with the most accumulated work and abandon the others. Proof-of-Work is the signal that resolves the “C” in the CAP theorem. It is fair, because one’s chance of finding the next block is proportional to the work one puts in. And it needs no trust, because any node, or any SPV wallet holding only the block headers, can check the work for itself.

Referring to Figure 1, we notice a few interesting things:

1. Two miners find a valid block at height 812,401 at nearly the same time. For a little while the network is inconsistent: some nodes hold block A, others hold block B.
2. The next block, at height 812,402, happens to be found on top of block A. The chain through A now holds more work.
3. The nodes that held block B switch to the chain through A. Block B is orphaned, and the network is consistent once more.

Figure 1: Two competing blocks, resolved by the work built on top of them

Do note that “longest chain” means the chain with the most accumulated work, not the chain with the most blocks. The two are almost always the same, but it is the work that counts.

It should be noted that this consistency is probabilistic. A block that was found a few seconds ago may yet be replaced. A block with six blocks on top of it is very unlikely to be, and each block added on top makes it less likely still. Section 11 of the whitepaper works through the numbers. This is why we speak of a Transaction having a number of confirmations, and it is the reorganisation we deal with in Simplified Payment Verification.

What the work is

The hash puzzle itself is rather straightforward. A miner assembles an 80-byte Block Header, which holds:

• the version of the block,
• the hash of the previous Block Header, which binds the blocks into a chain,
• the merkle root of the block’s Transactions,
• a timestamp,
• the target, in a compact form known as bits,
• a nonce.

The miner hashes the header twice with SHA-256. If the result, read as a number, is below the target, the block is valid. If it isn’t, the miner changes the nonce (or another field it is free to change) and tries again. There is no shortcut. The only way to find a valid header is to try a very large number of them, and the only way to try more of them is to spend more on hardware and electricity.

Every node adjusts the target over time, so that blocks keep arriving at about one every ten minutes however much work the network as a whole puts in.

Because the previous block’s hash is part of each header, the work in a block also covers every block before it. Changing a Transaction in an old block changes its merkle root, which changes its header hash, which invalidates every header after it. To rewrite history one has to redo the work of every block since.

Security is economic, not cryptographic

With this picture in hand, we can see what Proof-of-Work does not do. It does not encrypt anything, and it does not protect anyone’s coins. SHA-256 is a cryptographic hash function, but in Proof-of-Work it serves as a fair lottery, not as a means of keeping secrets.

The cryptography in Bitcoin lives elsewhere, and it is the wallet’s job. A coin can only be spent by someone who can produce a valid Signature for its Locking Script, and that depends on the Private Key being kept safe. No amount of hashing power lets a miner forge a Signature. You can read more about this in Signature Schemes.

What a miner with a great deal of hashing power can do is choose which version of history the network converges on. They could, for example, pay someone, and then build a competing chain in which that payment never happened. This is a double-spend, and the only thing standing in the way of it is cost. The attacker has to out-work the rest of the network, for as many blocks as they want to rewrite, and they forgo the block rewards and fees they could have earned by mining honestly. The whitepaper describes the choice in section 6:

“If a greedy attacker is able to assemble more CPU power than all the honest nodes, he would have to choose between using it to defraud people by stealing back his payments, or using it to generate new coins. He ought to find it more profitable to play by the rules, such rules that favour him with more new coins than everyone else combined, than to undermine the system and the validity of his own wealth.”

The short of it, is that Bitcoin’s security is economic. The network stays consistent because behaving honestly pays better than attacking it, and because the cost of an attack grows with every block that is added on top of the one being attacked. Cryptography protects each individual coin, in the user’s wallet. Proof-of-Work protects the agreed history of all of them, through the incentives of the people doing the work.

Proof-of-Work is not a security mechanism for your keys. It is the means by which a distributed system with no fixed membership reaches eventual consistency, fairly, and at a cost that makes cheating unprofitable.