Proof of work using Hashcash

Posted by David Harding, Saïvann Carignan, Balaji Srinivasan

Tutorial

What you’ll learn

By the end of this tutorial you’ll understand how, years before Bitcoin, the program Hashcash used Proof of Work to deter spam, and why Proof of Work is an essential part of Bitcoin.

Install 21

Hashcash: The key to Nakamoto consensus

Each bitcoin can be thought of as a digital good. Because digital goods can be perfectly copied, it's possible for evil Mallory to give the same bitcoin to Bob that he previously gave to Alice. This is called the double spend problem.

The Bitcoin system provides a solution to the double spend problem: each transaction on the Bitcoin blockchain (global ledger) is placed in order. If Mallory first gives his bitcoins to Alice—and that is recorded on the blockchain—he can't give those same bitcoins to Bob at a later time.

Because Bitcoin is a decentralized system, we need a way for Bitcoin peers to trustlessly come to agreement (called consensus) about the order of transactions on the blockchain. The method used for that is called Proof Of Work (POW), and it was pioneered by a program called Hashcash.

Hashcash is a system that predates Bitcoin by about a decade—it was initially designed to reduce email spam by requiring senders to attach the equivalent of a penny worth of CPU time (electricity) to their emails in the form of POW. This was cheap for legitimate senders who sent a few dozen emails a day at most, but expensive for spammers who sent millions of emails per day. Unfortunately Hashcash never became widely used—probably as result of it being invented during a time when email infrastructure was centralizing (e.g. webmail), and the centralized providers finding cheaper ways to authenticate data between themselves (e.g. DKIM).

In 2004, Hashcash was used by cryptographer Hal Finney to build Reusable Proof of Work (RPOW), a pre-Bitcoin cryptocurrency that likely heavily influenced Satoshi Nakamoto.

Hashcash works by repeatedly hashing the same data over and over with tiny variations until a hash is found with a certain number of leading zero bits. Let’s use hashcash to repeatedly hash some data until it finds a hash that has a sufficient number of leading zero bits—just like we do in Bitcoin.

## If Hashcash is not already pre-installed on your Linux machine
sudo apt-get install -y hashcash
## If Hashcash is not already pre-installed on your Mac
sudo brew install hashcash

## Use Hashcash to mine a token containing the string “test”
time hashcash -m -r test > mined.txt

Hashcash will start mining and, when it finishes, return control to your prompt and print three time fields. The user time field gives you an idea of how much CPU time hashcash used; we know the average time on your 21 Bitcoin Computer will be about 2 seconds, but for about 10% of you it will have taken less than 1/10th of a second, and for a different 10%, it will have taken more than 4 seconds—that’s because mining to find a hash with a sufficient number of leading zero bits is a random search. By producing this hash with a specific number of leading zeros, you have proven (on average) that you've expended a certain amount of computational resources.

alt text

Now look at the output hashcash created. Notice that the string “test” that we provided is contained there, and that it’s surrounded by a bunch of other data.

## Display the data created by hashcash
cat mined.txt

That data should look similar to, but not identical to:

1:20:151001:test::xYzc5A1pnts9FhC3:00000000000002OQc

Most of the other data is irrelevant to us—it’s part of the anti-spam protection that Hashcash was designed to provide—but the last field is interesting; it’s the Number used Once (nonce). Bitcoin block headers also contain a nonce for the same reason: so that mining code can iterate through nonces in an attempt to produce a block header hash with the correct number of leading zeroes.

## Show the SHA1 (not SHA256) hash of the mined data
cat mined.txt | tr -d "\n" | shasum

This shows the hash of the data Hashcash created. Note that it starts with five zeros. This is Proof Of Work (POW)—it’s proof that hashcash checked (on average) about 2^20 hashes (1,048,576 hashes). Now let’s try generating a hash with even more proof of work:

## Run hashcash again but at a higher “difficulty” (default = 20)
time hashcash -b 25 -m -r test2 > mined2.txt

For most of you, the command will take more than 22 seconds to run, so now is a good time for a short break.

Note: There’s a 2% chance that hashcash won’t have finished running after five minutes. If that’s the case and you need to proceed to the next section, press Ctrl-c to stop it and don’t run the echo command below.

After hashcash finishes mining, display the hash the same way you did before:

## Show the hash of the mined data
echo -n $( cat mined2.txt ) | shasum

Note there is now an additional leading zero. By increasing the proof of work difficulty, the amount of time it took to run the command noticeably increased. For each additional bit of proof of work security, the average amount of CPU time doubles.

Now that you know about Proof Of Work (POW), you may want to explore Bitcoin's first block into which Bitcoin creator Satoshi Nakamoto put both a special message and an unusual amount of POW.

Questions

Hashcash and Proof Of Work questions

For each additional bit of Proof Of Work (POW) security that you create, how much longer do you have to work on average?

Correct

Incorrect

Correct

Incorrect

Correct

Incorrect

Correct

Incorrect

Correct

Incorrect

What does Bitcoin use Hashcash-style proof of work for?

Correct

Incorrect

Correct

Incorrect

Correct

Incorrect

Correct

Incorrect

Correct

Incorrect

What does Hashcash-style proof of work prove?

Correct

Incorrect

Correct

Incorrect

Correct

Incorrect

Correct

Incorrect

As of September 2015, new blocks on the Bitcoin block chain had 67 bits of proof of work. If creating a hash demonstrating 25 bits of proof of work security takes on average 77 seconds on a typical CPU without a hardware mining chip, how long would it take on average for it to generate a hash with 67 bits of security using a typical CPU? (Python is installed on the 21 Bitcoin Computer if you want to invoke its REPL to perform a calculation; otherwise, feel free to use a calculator installed on your laptop.)

Correct

Incorrect

Correct

Incorrect

Correct

Incorrect

Correct

Incorrect

Correct

Incorrect