The Double Spend Problem

One major issue of decentralized digital currencies that was solved by the invention of Bitcoin and the blockchain, is the double spend problem. It is worth taking a step back to understand why we need blockchains in the first place, and why they are constructed in the way they are.

To illustrate this, consider the following short tale. Alice is the owner of one bitcoin. We use public key cryptography to determine ownership, so that Alice is in possession of the private key for the bitcoin address. This means that she is able to prove ownership by digitally signing messages. Using the associated public key, anyone is able to verify the signatures and confirm that they have indeed been authorised by Alice.

First, Alice visits Bob, who has an item for sale. For the sake of the story, he is selling a car. He also agrees that one bitcoin is a fair price, so agrees to sell it to Alice. For her part, Alice creates a transaction transferring her bitcoin to Bob’s address and signs it. Bob now has a transaction giving him the bitcoin, and can prove to anyone that it has been authorised by Alice. So, he gives her the car and she drives away.

Next, Alice visits Carol, who is selling some jewellery. She agrees that one bitcoin is a fair price. So Alice again creates a transaction, paying the very same bitcoin to Carol’s address, and signs it. As happened with Bob, Carol knows that she can prove to anyone that the transaction has been authorised by Alice, so hands over the items. Alice drives off in her new car wearing her new designer jewellery.

Something has gone badly wrong here. Somehow, Alice has managed to spend the same bitcoin twice. Either, she has created new coins out of thin air, or at least one of Bob and Carol are going to lose possession their coins once the double spend is noticed. Either way, this approach would be very bad for the use of bitcoin as a medium of exchange.

How can the situation above be avoided? There is no way that Bob can know for sure that Alice will never sign any other transactions spending the coin that she has supposedly given him. As long as she remembers the private key, she can sign as many transactions with it as she likes. Similarly, Carol can never be sure what transactions Alice may have signed previously in private transactions with other parties.

To solve this problem, the initial transaction between Alice and Bob cannot be entirely private. The information has to be passed on to some other party or parties so that, later, Carol will be able to check with them to see if Alice does indeed still own the bitcoin.

For the centralized solution, this role could be played by Alice’s bank, who she must inform in order for Bob to accept the transaction. Later, Carol will only accept that her transaction is valid when Alice’s bank approves it. Of course, they will not do this, since Alice has already spent the bitcoin. This solution removes the freedom from Alice to double spend her coins by, instead, placing the trust in her bank that they would not authorise such a thing.

With a decentralized asset such as Bitcoin, we do not want to place trust to record all transactions with a single party. Instead, the transaction between Alice and Bob must be publicly announced to the network. Bob will only procede with the transaction after sufficient network nodes accept it as valid. Then, when Carol transmits her transaction, the network will not accept it, since it has already been recorded that Alice has spent her bitcoin.

This is not an easy thing to pull off in a decentralized network. All nodes must come to a consensus as to the precise state, and ownership of all bitcoin in existence. Alice could submit both transactions simultaneously to different nodes. When contradictory data is submitted, the network needs to agree which is correct and which will be rejected. Furthermore, the recorded information should be immutable, so that once a transaction is confirmed, then it can never be undone. We cannot assume that all nodes are good actors either. Alice, and her accomplices, could be actively participating in the network to spread false information in order to replace her original transaction with Bob by the later one with Carol. This behaviour of the system, where it continues to perform correctly even when individual components are unreliable, is known as Byzantine fault tolerance.

Blockchains are the solution employed by cryptocurrencies. As new transactions are submitted, additional blocks recording these are appended to the chain. The proof of work (or alternative) protocol is used to allow all nodes to come to consensus and ensure immutability of the blockchain. Individual actors are not easily able to change the state of already-confirmed transactions. To do such a thing would require the bad actors to all work together, and to gain an overall majority of the hashpower of the network. It should be noted that, very occasionally, double spends do occur. However, this only usually happens for transactions in blocks very near the top of the chain. Transactions which have been ‘confirmed’, by having several blocks added on top of them in the chain, are rarely if ever undone.