A puzzle against spam
In 1997 the British cryptographer Adam Back came up with Hashcash, a way to fight spam. Before sending an email, the sender’s computer had to spend a few seconds solving a pointless mathematical puzzle and attach the solution. For an ordinary person a few seconds per email cost nothing, but for a spammer sending millions of emails the work would require a whole farm of computers. The recipient could check the solution instantly. That is how proof of work appeared (chapter “The Spectre of Crypto Anarchy”).
You can try Back’s puzzle right in the browser, in the experiment “A Hashcash stamp”. The browser runs through a counter until the email’s hash starts with the right number of zeros, which takes time, while checking the finished stamp takes a single hash.
From Hashcash to bitcoin
The cypherpunks laid the remaining parts on the table one by one. In 1998 Wei Dai described b-money, money kept by all participants at once, with new coins going to whoever solved a computational puzzle. Almost at the same time Nick Szabo came up with Bit Gold, where a solved puzzle itself became a valuable, like gold dug out of the ground, and each next solution was chained to the previous one. In 2004 Hal Finney built Back’s idea into RPOW, a server where proofs of work could be passed from hand to hand, except that the server belonged to Finney himself (same chapter).
None of these schemes took off. B-money had no answer to how participants would agree on who was right if their records diverged, and Bit Gold remained a description (same chapter).
How it works in bitcoin
Satoshi Nakamoto took Back’s puzzle and made it much harder. All participants keep the same book of payments, new payments are gathered into a block, and to attach the block to the book a solution has to be found. The puzzle is tuned so that a solution turns up about once every ten minutes across the whole network, and whoever finds it first gets new coins as a reward. It amounts to a lottery where tickets are bought with electricity. Each block refers to the previous one, and the network goes with the chain that has the most work spent on it (chapter “The Idle God”).
That is where the protection comes from. To rewrite history and spend a coin twice, you would have to recompute every block after your payment faster than the rest of the network (same chapter). More on that in the answer on double spending. In summer 2010 I switched on generation in the wallet on my MacBook myself, and the processor ran through numbers looking for the one that would fit the next block.
What the people of Yap knew
On the island of Yap people paid with stone wheels quarried on Palau and brought across the ocean by canoe. In the 1870s Captain David O’Keefe began carrying islanders on his ship and giving them iron tools, and the number of stones grew. The islanders valued them in their own way. A small stone cut with the old tools was worth more than a huge wheel from the hold of a foreign ship, because a stone’s price was set by the people who drowned bringing it, the storms it survived and the years it took (chapter “A Stone at the Bottom of the Sea”).
A hundred and thirty years before Satoshi, the people of Yap discovered what programmers would later call proof of work. A record is worth as much as it costs to forge, and when extraction gets cheaper, the money gets cheaper too. Bitcoin handles this automatically, raising the mining difficulty every two weeks so that new iron tools simply cannot exist (same chapter). You can hand a stone to another family and paint German marks on the stones in the experiment “The stones of Yap”.
