Part 2: The Crafty Design of Bitcoin

This article is part of a GIST series on Bitcoin. In part 1, we described the mathematics that underpins digital currencies like Bitcoin, as well as the security of the web itself. In this part we will begin to uncover the intricacies of how protocols like Bitcoin work. In particular, it is very important for Bitcoin to ensure that users own the currency that they spend, and this has a surprising number of complications when moved from paper to binary.

Computer users will do what computer users do

Imagine the simplest form of digital currency. Owners of this currency could, just like a paper bank note’s serial number, have a string of unique characters to represent their currency. They could send this string of characters to a supplier in order to purchase goods (see Figure 1). The supplier would then own this money, and would be able to use it themselves by sending the string of unique characters to someone else. Perfect, right? Of course not. You may have spotted a problem with this approach immediately: in the digital world, it would be trivial to copy someone else’s string of unique characters (analogous to bank note forgery) and use their currency, just like freedom-loving music fans have been doing with MP3s ever since the first acne-spotted teenager learned to copy and paste. With this system there is no way to verify that a transaction has already taken place with this money – to know whether or not the sender actually owns the currency – and so it is open to being abused.

Image Credit: Sean Leavey
Figure 1: A simple transaction with Bitcoin. The buyer sends some coins with a unique transaction ID to Seller A. If the buyer really owned the currency, then the Bitcoin network would agree that Seller A now owns the bitcoins with ID 537704.

Verifying transactions

A way to overcome the problem of verifying the validity of a transaction is to digitally sign details of the transaction with the public key encryption method discussed in the last part. Then to send digital money to someone, you would simply encrypt a message containing the currency (or, in the case of Bitcoin, some sort of ‘serial number’ representing the money), along with a message saying something like “I am User X, and I sent this money to User Y”, where User X is the buyer and User Y is the seller. This message would be encrypted with the buyer’s private key, and then published somewhere on the web, where everyone in the world would be able to see it. With the message being encrypted with the private key, you would be able to check that the currency was owned by the buyer by decrypting the message with the sender’s public key (see Figure 2).

Image Credit: Sean Leavey
Figure 2: Verifying transactions. The buyer signs the transaction with their private key. The seller then checks that the buyer really owned the coins by using the seller’s public key to verify the transaction, before accepting the transaction. This method helps to ensure buyers actually own the currency they send to sellers.

Verifying that a user still owns the currency they send

The next problem to solve is the fact that a user who once owned some currency represented by a unique serial number would be able to send this same piece of currency over and over to different sellers after having spent it the first time. How can we remove ‘ownership’ of a piece of digital currency from a user once they’ve spent it? With traditional currency we exchange the metal and paper that represents the currency, whereas with digital currencies it is possible to retain the bytes that represent them after having spent them. It’s not practical to somehow delete from the owner’s computer the serial number of the currency – there will always be easy ways to prevent this removal. Instead, it is more practical for the seller to know whether a piece of digital currency has already been used by the buyer, and so be able to block the transaction should someone try to reuse it. Somewhere, there must be a ledger of transactions, against which bitcoins are checked to make sure they are only being used by their rightful owners.

This is where banks come in handy for traditional currency. Banks issue notes with unique serial numbers, and the bank knows that a specific serial number matches up to a specific amount of currency. Bank accounts can be thought of as collections of serial numbers representing real banknotes, so banks are ultimately the entities that can verify who owns what currency. The way in which a transaction can be made with bank notes is for the seller to verify with the bank upon receiving the encrypted message from the buyer that the serial number of the currency sent to the buyer was actually owned by the buyer in the first place. In practice we don’t really do this, instead relying on trust and intuition, but the option is always there. The bank acts as the centralised record of the owners of all of the currency in circulation.

With digital currencies, however, we want to avoid relying on a central authority that can be hacked, intimidated or otherwise corrupted to manipulate the money in circulation. It is also somewhat easier in the Internet Age to take digital systems offline or manipulate them, such is the collective and possibly destructive power of millions of web-connected devices around the world. Banks have also recently reminded the world how reckless they can be with our money, so a solution that cuts them out is definitely of value to some web citizens. As such, Bitcoin avoids the use of a centralised authority to keep a record of the transactions being made. How can Bitcoin, therefore, verify that a piece of currency is really owned by a user?

The bank of Bitcoin

With Bitcoin, everyone takes part in acting as the bank. Since with this digital currency, everyone announces to the world the details of their transactions, in theory everyone in the world can also keep a record of the history of transactions among other users. This would allow a seller to check the records to make sure that a buyer really does own the currency that they are trying to use to buy something. If the transaction was a legitimate one, then the seller could then also announce to the world that they had accepted the currency. Everyone, including those not involved in the transaction, would then update their own records to make note that the seller now owns the currency sent by the buyer.

As with every new piece of the jigsaw, there is a problem with this approach. There exists the possibility that whilst the buyer is spending their currency by buying something from a seller, they could at the same time buy something from a second seller with the same coins (see Figure 4). If it were to be carried out sufficiently quickly, both sellers would be unable to verify that the currency had already been spent by the buyer, since their transaction records would not have been updated to reflect the new transaction.

Image Credit: Sean Leavey
Figure 3: Double spending bitcoins. While sending some coins to Seller A, the buyer could simultaneously make a copy of the transaction and send it to Seller B, making both sellers think they have received the coins. Moreover, since this can be done quickly, both sellers would check their own records and see that the buyer still owns the coins, and so they will both think the transactions they each received were valid and accept them. The Bitcoin network prevents this from happening by packaging unique transactions into ‘blocks’.

Preventing double spending

The way in which Bitcoin prevents double spending is by making not only the seller verify the transaction, but many third parties. Upon receiving the currency, the seller would then ask third parties not directly involved in the transaction to check their own records to make sure that the buyer truly owns the currency. There is a high chance that at least one third party would have knowledge of both transactions and be able to spot the double spending. Only after receiving confirmation from these external sources, would the seller then broadcast their own message that they have accepted the money.

Yet again, there is a flaw with this system. If the buyer controlled a large fraction of the third parties, they would be able to send fake messages to both of the sellers to say that they have verified the validity of both transactions (this is an interesting occurrence of the Byzantine Generals’ Problem ¹). This could be the case if the buyer had created a network of computers that they had control over – a ‘botnet’.

The way that Bitcoin avoids this flaw is to make it difficult to verify a transaction. This may seem counterintuitive; surely we want to make it easy for the seller to check that the money they receive is legitimate? However, part of the security of Bitcoin is involved in making it difficult, yet rewarding for third parties to verify transactions. This mechanism is called the ‘proof of work’, and it is where the well-known aspect of Bitcoin mining comes into play.

The proof of work

By computing a proof of work for a set of pending transactions, a user can help to verify those transactions. A proof of work is simply a hash, like those discussed in Part 1, with specific characteristics. By finding a hash with the correct characteristics, a user can prove that they have performed the work in verifying the transactions. The hash itself is created by a user from their list of transactions that they have yet to verify. The user takes their list of pending transactions announced by others (making sure that they only select one transaction in the event of a double spend), appends to it an additional set of arbitrarily chosen characters, and then applies a hashing function to the resulting string. In order for a proof of work to be accepted by the worldwide network of Bitcoin users, the resulting hash must contain a series of 0s at its beginning. The number of 0s required determines the difficulty of the proof of work. For instance, an easy proof of work may only require a few 0s, whereas a difficult proof might require a dozen or more (at the time of writing, the current target is 15 0s*). The user must keep choosing a different set of arbitrary characters to append to their list of pending transactions until they find a set that produces the number of prefixed 0s required. Note that a suitable hashing function will produce what is essentially a random string of characters, so finding a hash with specific properties is simply a case of hard work (for the user’s computer).

After enough attempts, the user will be able to find a set of characters that, when linked with their pending transactions, produces a hash with a set of 0s of the right length. They can then broadcast this work to the world, and other users can easily verify that the set of characters works by computing a single hash with this list of transactions and counting the number of 0s. The ‘proof of work’ is simply the string of characters, proving that the user has found the appropriate combination that produces a hash with the correct properties.

By broadcasting the proof of work, the user validates their list of pending transactions with the community. The list of transactions with the proof of work is packaged into what is called a ‘block’, and this block contains the proof of work of the last successfully calculated block. Together they form a ‘blockchain’, with each new block pointing to the previous one (see Figure 5). Each user keeps a copy of the blockchain so as to be able to track who owns what. This system also means that when a user wants to send some money, they can simply refer to the block in which they received that money as their currency’s ‘serial number’.

Image Credit: Sean Leavey
Figure 4: An example of a blockchain in the Bitcoin network. Each transaction is packaged into a block, and each block points to the previous one. A transaction where the buyer sends currency to Seller A is packaged into a block, and only once enough blocks have followed this one will the seller accept the transaction. Each block is accompanied by a proof of work calculated from the contents of that block, so a seller can be sure that if a transaction is part of a completed block, then eventually the network will accept that they now own the currency used in the transaction.

With enough proofs of work performed after a transaction has been proposed, a seller can be confident that the currency used by the buyer to purchase something has not yet been spent — remember that third parties perform this check — and can therefore deliver the goods or services on offer, safe in the knowledge that they have been paid (see Figure 6). The Bitcoin protocol specifies that a transaction is accepted when it is part of a block followed by five newer blocks.

Image Credit: Sean Leavey
Figure 5: Resolution of a double spend. When a buyer attempts to reuse currency twice, only one of the transactions will be packaged into a block that becomes part of the blockchain. During the transaction, the sellers only need to wait until they see the transaction become part of a block that is followed by sufficient further blocks before accepting the payment. This will only happen to one of the simultaneous transactions, because the Bitcoin protocol works so the money will only be spent once.

After a transaction has been verified, users around the world update their own blockchains, giving them knowledge of who now owns the coins. This allows for the whole process to be repeated when the coins are next spent by their new owner.

Why does the proof of work need to be so difficult to compute? This is a safety mechanism. Since proofs of work are easy to verify but hard to compute, this helps to avoid the situation where a botnet can be used to flood the network with false proofs of work, thereby allowing coins to be spent more than once at the same time. The Bitcoin protocol also makes sure that the whole worldwide network learns about the transaction, meaning that a fraudster must control a huge proportion of the network to have any influence. The security of Bitcoin relies in part on its ubiquity, with every new independent user enhancing the safety mechanism provided by the proof of work.

Mining

Why would a third party bother to verify other transactions, especially when computing the proof of work requires such substantial computational exertion? Proofs of work are now so difficult that the amount of electricity required to power a device to compute the hashes means that there has to be a monetary reward for users to bother to do it. This is where the Bitcoin protocol implements its most famous aspect: mining. Mining is actually just another term for the process of computing proofs of work, but it is also the way in which new Bitcoins are minted. Since there is no centralised bank in Bitcoin, the traditional way by which new currency is issued doesn’t exist. Instead, new Bitcoins are rewarded by the network to the user who successfully verifies a set of particular transactions first. Users compete with each other to verify transactions, and by profiting from the rewards they can justify the expense they have gone to to carry out the verification. The more computational power that a user brings to the table, the more chance they have of winning a reward.

The minting of new Bitcoins is a feature that resembles a conventional currency. In general, inflation within an economy produces new wealth, in part due to the mining of precious metals which we value from the Earth, and also due to the work exerted by humans in the form of services and goods exchanged for payment. For these reasons, central banks often print new money and issue it into circulation to try to keep the value of existing currency in circulation somewhat constant. Bitcoin also allows for this to happen by providing the means for Bitcoins to continue to be produced, albeit with some caveats. The process by which Bitcoin tries to stabilise itself with changes to the computing power on the network will be described in the next article.

Go to Part 3

1. Excellent Wikipedia article on the subject.