Hashcash, b-money and Bit Gold: the Precursors

When people first read the Bitcoin whitepaper, they are often surprised by how little in it is new. Digital signatures, hash functions, timestamp chains, proof of work, peer-to-peer networks: every one of these existed before 2008. What was new was the combination, and a way of making the pieces support each other. To understand the whitepaper, it helps to meet the pieces first.

A stamp for e-mail

The story of proof of work begins with junk mail. In 1992 the computer scientists Cynthia Dwork and Moni Naor proposed a way to make unsolicited bulk e-mail expensive without charging money for it. A sender would have to compute the answer to a moderately hard mathematical puzzle for each message. For an ordinary correspondent, a few seconds of computing per e-mail would be unnoticeable. For someone sending millions, the cost would add up quickly. Crucially, checking the answer would be easy for the recipient.

The idea was that computing effort could act like a postage stamp. It could not be forged, because the only way to produce a valid answer was to do the work. In 1999 the researchers Markus Jakobsson and Ari Juels gave this family of techniques the name by which it is now known: proof of work.

Hashcash

In 1997 the British cryptographer Adam Back announced on the cypherpunks mailing list a simple, practical version of the idea called Hashcash. It used a cryptographic hash function, a function that turns any input into a fixed-length fingerprint in a way that is easy to compute but impossible to reverse or predict.

A Hashcash stamp is a short piece of text, including the recipient’s address and the date, together with a counter. The sender changes the counter again and again until the hash of the whole text happens to begin with a certain number of zero bits. Because the output of a good hash function is unpredictable, there is no shortcut: the sender simply has to try many values. The recipient, on the other hand, can check the stamp with a single hash computation.

Back described the scheme in more detail in a 2002 paper, which is cited in the Bitcoin whitepaper. Hashcash was designed against spam and denial-of-service attacks, not as money. But it produced something money needs: a token that is costly to create and cheap to verify.

b-money

In November 1998 Wei Dai, a computer engineer known for an open-source cryptography library, posted a short proposal called b-money. It opens with an acknowledgement of Tim May’s crypto-anarchy and sets out to describe a system of money and contracts for anonymous participants who are known to each other only by pseudonyms, that is, by public keys.

Dai described two protocols. In the first, every participant keeps a separate copy of a database recording how much money belongs to each pseudonym. New money is created by anyone who broadcasts the solution to a previously unsolved computational problem, with the amount created tied to the cost of the computing effort. Transfers are broadcast to everyone, signed by the payer, and every participant updates their own copy of the database.

Dai acknowledged that the first protocol was impractical, because it required a synchronous, unjammable broadcast channel. His second protocol gave the task of keeping accounts to a subset of participants, who would put up deposits that could be forfeited if they cheated. B-money was never built. But the idea of a ledger kept by every participant, with money created through computing effort, is unmistakable. It is the first reference in the Bitcoin whitepaper.

Bit gold

At around the same time, the computer scientist and legal scholar Nick Szabo was developing a proposal he called bit gold. Szabo was already known for introducing the idea of smart contracts in the mid-1990s. Bit gold drew an analogy with precious metal: something valuable because it is costly to produce and cannot be created cheaply out of nothing.

In Szabo’s design, participants computed proof-of-work strings starting from a challenge. Each new challenge was derived from a previous solution, so the strings formed a chain. Solutions were to be timestamped and their ownership recorded in a distributed registry of property titles maintained by a group of servers. Szabo also recognised a problem: pieces of bit gold produced at different times with different hardware would have different costs, so they would not be interchangeable. He proposed ways of bundling them into standard units.

Szabo described bit gold in a post on his weblog in 2005, though he dated the idea to 1998. Like b-money, it was never implemented as a working currency.

Reusable proofs of work

In 2004 Hal Finney, a cryptographer and veteran of the cypherpunks, actually built something. His system, RPOW, for reusable proofs of work, let a user exchange a Hashcash-style token for a new token that could be passed to someone else, who could exchange it again. To prevent the server from cheating, Finney ran it on secure hardware that could prove to outsiders which software it was running. RPOW still depended on a single server, but it was a working demonstration of transferable tokens backed by computing effort.

The other ingredients

Digital cash research was only one source of the whitepaper’s ideas. Two others came from quite different fields.

Timestamps and hash chains

In 1991 the researchers Stuart Haber and W. Scott Stornetta, working at Bellcore in New Jersey, published a paper on how to timestamp a digital document so that nobody, including the timestamping service itself, could later backdate it. Their solution linked each new timestamp to the previous one through a hash, forming a chain in which changing any earlier entry would break every later link. A later paper, written with Dave Bayer, used Merkle trees to timestamp many documents at once. Three of the eight references in the Bitcoin whitepaper are to their work. Merkle trees themselves, a way of summarising many items in a single hash, had been described by Ralph Merkle in 1979.

Agreement among unreliable parties

The second field was distributed computing. In 1982 Leslie Lamport, Robert Shostak and Marshall Pease published “The Byzantine Generals Problem”, a formal treatment of how a group of computers can reach agreement when some of them may be faulty or actively malicious. A large body of research followed, including practical algorithms in the late 1990s. These algorithms worked well for a known, fixed set of participants. They did not obviously work for an open network where anyone could join under any number of identities.

The problem received a name in 2002, when John Douceur of Microsoft Research published a paper called “The Sybil Attack”, after a well-known case study of a woman with multiple personalities. Douceur showed that in a peer-to-peer system without a central authority to vouch for identities, a single attacker could create many apparent participants and so outvote everyone else. Unless creating an identity had some real cost, he argued, there was no general way to prevent this. Any voting scheme based on counting participants was therefore open to manipulation. For digital cash without a bank, this was a serious obstacle: the system would need to agree on which payments had happened first, and agreement seemed to require counting votes.

Putting the pieces together

By 2008 the ingredients were all on the table. There were signatures for ownership, hash chains for ordering, proof of work for making creation costly, ideas for ledgers kept by every participant, and decades of research on agreement in the presence of faults. What remained unsolved was how to prevent double-spending without a central party in an open network where identities cost nothing.

The whitepaper’s answer, which we read section by section in the next essay, was to use proof of work not only as a cost of creating money but as a way of voting on the order of transactions. Votes would be weighted by computing effort rather than by identities, which can be faked at no cost. It is a simple-sounding move, and it took a generation of earlier work to make it possible.