Bitcoin and other cryptocurrencies use a ‘proof of work’ (PoW) protocol to build consensus on the network and prevent double-spending. But what does this mean? And what is proof of work?

The double-spending problem

Before Bitcoin was invented, cryptographers had been working on a cryptographically secure digital currency for several years. Many of these cryptographers believed that public/private key cryptography could be used to create digital ‘coins’ and that these coins could not be spent without first being received from someone else. However, while it was clear how this form of cryptography could stop someone from spending coins he didn’t receive, it was not clear how this form of cryptography could stop a person from spending the same coins twice.

This problem was known as the double-spending problem. It was this problem that the Bitcoin PoW protocol was designed to overcome.

Hashcash and Proof of Work

HashCash was the first application to popularize PoW among cryptographers. Adam Back developed this application in 1997 in order to stop email spam without preventing legitimate messages from getting through. HashCash allowed email servers to require tokens from users in order to send emails. These tokens could only be generated if the user solved an extremely difficult mathematical problem. Because solving the mathematical problem required electricity, users had to pay a real-world cost to send emails. In theory, this would prevent email servers from having to charge real-world money for their use but would also have made sending emails costly for spammers.

In order to create a HashCash token, the user had to produce a string of text whose hash had a certain number of zeros at the beginning. This problem could only be solved through trial-and-error. The more zeros needed, the more difficult the problem was. Broadcasting a string that hashed to a number with a certain number of zeros at the beginning was called submitting ‘proof of work’ because it proved that the user had spent electricity, a real-world cost, to obtain the result.

A piece of HashCash could only be spent once; it was not reusable. Hence this version of the PoW protocol did not solve the double-spending problem. However, it provided the foundation that would later be used to solve this problem in Bitcoin.

Reusable Proof of Work

While HashCash never quite caught on as a way to stop email spam, it did catch the attention of Hal Finney, who was trying to solve the double-spending problem. Finney’s solution was to create a system called ‘Reusable Proof of Work’ (RPOW). Under the RPOW system that was released in 2004, a user would create a piece of HashCash and send it to a trusted server. This server was hosted by Finney, although he hoped others would create similar servers in the future. Once the HashCash was sent, the server would verify that it had a certain value and would then issue an RPOW token in exchange for it. When the user received the RPOW token, he/she could send it to a recipient in exchange for a good or service. The recipient would then send the token back to the central server, and the server would mint a new RPOW token which could again be sent to a new recipient.

The RPOW ‘trusted server’ problem and solution

The most obvious problem with RPOW was that it required a trusted central server, much like a bank. However, Finney sought to mitigate this problem by using a processor that could securely transmit information to the Internet about what software it was running. In Finney’s view, this could be used to prove to network participants that the owner of the server wasn’t using tricks to create tokens out of thin air or otherwise cheat.

RPOW used PoW to create tokens, but it didn’t use the protocol to solve the double-spending problem. Instead, it used a central server to make sure that a user hadn’t spent the same coin twice. Just four years later, Bitcoin would use PoW to eliminate the central server entirely.

Proof of Work in Bitcoin

The Bitcoin system was released as a white paper in late 2008 and as software in January 2009. In Bitcoin, transactions are gathered together by a node into a group called a ‘block’. This block is then timestamped, hashed and broadcast to the entire network. Because the block has a timestamp, this proves that the transactions within it existed at the time the block was created. Each block also contains a hash of the previous block, which contains a timestamp of when that block was created. Because each block refers to the one before it, the entire history of transactions in the Bitcoin system can be known. This history of transactions is called the ‘blockchain’.

Adding a block to the blockchain

To add a block to the blockchain, a node must take the hash of the previous block, add the hash of the new transactions and timestamp and add a random number called the ‘nonce’. If the resulting hash has the correct number of zeros at the beginning, the block is added to the blockchain. The node who produced this hash is rewarded with newly minted bitcoins. If the hash does not have the correct number of zeros, the node produces a new random number and checks again to see if the hash has the correct number of zeros at the beginning. This process continues until either the node produces the correct hash or some other node does. If another node solves the problem, the current node throws away its current transactions, gathers new ones and starts over, using the new block that has just been added by the other node as the new ‘previous block’. Because each node must perform a proof of work calculation to add a block to the blockchain, it is extremely difficult to undo a previous block. For this reason, double-spending is nearly impossible as long as the recipient waits for multiple blocks to be confirmed before sending merchandise.

How PoW Prevents Double-Spending

To illustrate how PoW solves the double-spending, let’s take a look at the following example. Let’s say that Joe wants to send 10 bitcoins to Amy in order to purchase a television from her. However, he also wants to spend the same bitcoins to buy a surround sound system from Bill. In order to pull off this scam, he needs to first broadcast to the network that he intends to send Amy the bitcoins and then wait for this transaction to be confirmed. Once the block is confirmed, he hopes that Amy will go ahead and give him the television. At this point, he will begin to produce a parallel blockchain in which the transaction never took place. However, to get this fraudulent blockchain accepted as the new one, he will need to confirm blocks faster than the entire network of honest nodes. Yet, he is already behind by at least one block as the rest of the network had moved on to confirm new blocks.

If Amy releases the television just after the transaction is confirmed, it’s possible that Joe could get lucky and solve two blocks on his parallel chain in rapid succession, erasing the transaction with Amy. However, this is very unlikely. If Amy is worried about this possibility though, she can simply wait to release the television until two or three blocks are confirmed. The longer time passes and the more blocks are confirmed, the more exponentially difficult it gets for Joe to ‘catch up’ and erase the previous transaction.

Just as HashCash sought to eliminate spam by using PoW to make it costly, Bitcoin uses PoW to make double-spending costly.

Proof of Work after Bitcoin

Since the invention of Bitcoin, many other cryptocurrencies have used Proof of Work to secure their networks, including Bitcoin Cash, Litecoin, Ethereum, Monero, Zcash and others. Although new consensus protocols like Proof of Stake, Proof of Useful Work, Proof of Storage and others have provided alternatives to it, PoW is still used in many cryptocurrencies and blockchain applications.