Grokking Bitcoin

Step 1 of the process (Figure 3) is when Alice asks the network to move 1 bitcoin to Bob. She does this by sending a Bitcoin transaction to the Bitcoin network. This transaction contains instructions on how to move the money and a digital signature that proves it’s really Alice requesting that the money be moved.

The Bitcoin transaction is a piece of data specifying

The digital signature is created from the transaction and a huge secret number, called a private key, that only Alice has access to. The result is a digital signature that only the private key’s owner could have created.

Alice’s mobile wallet app is connected to one or more nodes in the Bitcoin network and sends the transaction to those nodes.

Alice has sent a transaction to one or more Bitcoin nodes. In step 2 of the process (Figure 4), each such node checks that the transaction is valid and passes it on to its peers. It does this by consulting its local copy of the blockchain and verifying that

If all checks pass, a node forwards the transaction to its peers in the Bitcoin network. This is known as relaying. Alice’s transaction will shortly have traveled the entire network while each node verifies it along the way. The blockchain hasn’t been updated yet; that’s the next step.

In step 3, nodes update their local copies of the Bitcoin blockchain with Alice’s transaction. The blockchain contains historic information about all previous transactions; new transactions, such as Alice’s, are appended to it every now and then.

Updating the blockchain with Alice’s transaction isn’t as straightforward as it might seem. Alice’s transaction isn’t the only one going on in the Bitcoin network. Potentially thousands of transactions can be in flight at the same time. If all nodes updated their copy of the blockchain as they received transactions, the copies wouldn’t remain copies for long because transactions can come in different orders on different nodes, as Figure 5 shows.

To coordinate the ordering of transactions, one node takes the lead, saying “I want to add these two transactions to the blockchain in the order Y, X!” This message, known as a block, is sent out on the network by that leader (Figure 6), in the same way that Alice sent the transaction.

As nodes see this block, they update their copy of the blockchain according to the message and pass the block on to their peers. Alice’s transaction was one of the transactions in the block and is now part of the blockchain.

Why would a node want to take the lead? The node that takes the lead is rewarded with newly minted bitcoins and transaction fees paid by the transactions it includes in the block.

But wouldn’t every node constantly take the lead to collect the rewards? No, because to take the lead, a node must solve a hard problem. This requires the node to consume considerable time and electricity, which ensures that leaders don’t pop up often. The problem is so hard that most nodes in the network don’t even try. Nodes that do try are called miners because they mine new coins, similar to a gold miner digging for gold. We’ll discuss this process further in Chapter 7.

Bob and Alice are Bitcoin network users, and they both need a computer program to interact with the network. Such a program is called a Bitcoin wallet. Several types of Bitcoin wallets are available for different devices, such as mobile phones and desktop computers, and there are even specialized hardware wallet devices.

Before step 4 of the payment process, the nodes in the network update their local copy of the blockchain. Now, the network needs to notify Alice and Bob that the transaction went through, as Figure 7 shows.

Bob’s wallet is connected to some of the nodes in the Bitcoin network. When a transaction concerning Bob is added to the blockchain, the nodes that Bob’s wallet is connected to will notify Bob’s wallet. The wallet will then display a message to Bob that he received 1 bitcoin. Alice also uses a wallet. Her wallet will be notified of her own transaction.

Besides sending and receiving transactions, Bob’s and Alice’s wallets also manage their private keys for them. As described earlier, a private key is used to create digital signatures, as well as to generate a Bitcoin address. Alice created her digital signature with one of her private keys. When Bob later wants to spend the money he received at his Bitcoin address, which he generated from his private key, he needs to create a transaction and digitally sign it with that private key.

People with bank accounts and access to banking services such as online payments or loans are privileged. According to the World Bank, about 38% of the world’s population doesn’t have a bank account (see Web resource 6). The numbers are slowly improving, but many people are still stuck in a cash-only environment.

Without a bank account and basic banking services, such as online payments, people can’t expand their businesses outside their local communities. A merchant won’t be able to offer goods or services on the internet to increase its customer base. A person living in a rural area might have to travel half a day to pay a utility bill or top up their prepaid mobile phone.

This segregation between banked people and unbanked people is driven by several factors:

When it comes to electronic payments such as credit cards or bank transfers, traditional money poses several privacy problems. States can easily

You might say, “I have nothing to hide, and the government needs these tools to fight crime.” The problem is, you don’t know what your government will look like in five years and how that government defines crime. New laws are just an election away. After the next election, your government could pass a law that allows it to freeze the funds of people with your political view. In some parts of the world, this is already happening.

We’ve seen lots of examples in which these powers are abused to disable someone’s ability to transact. For example, the nonprofit organization WikiLeaks was put under a blockade in 2010 in which all donations through traditional channels were blocked after pressure from the US government on the major payment networks, such as Visa and Mastercard (see Web resource 7). We’ve also seen how Cyprus seized 47.5% of all bank deposits exceeding 100,000 € as part of a financial rescue program in 2013 (Web resource 8).

Note that bank notes and coins usually aren’t affected. As long as there is cash, people can trade freely and privately. In some parts of the world—for example, Sweden—cash is being phased out, which means soon you won’t be able to buy chewing gum without someone recording your transaction.

Inflation means the purchasing power of a currency decreases (Figure 8).

Most currencies are subject to inflation, some more than others. For example, the Zimbabwean dollar inflated nearly 10²³% from 2007–2008, peaking at 80 billion percent per month during a few months in 2008. That’s an average daily inflation rate of nearly 100%. Prices roughly doubled every day.

Extreme cases of inflation like this are called hyperinflation, and are usually driven by a rapid increase in the money supply. Governments sometimes increase the money supply as a tool to extract value from the population and pay for expenses such as the national debt, warfare, or welfare. If this tool is overused, the risk of hyperinflation is apparent.

A rapid increase in the money supply will most likely lead to a depreciation of a country’s currency. This, in turn, pushes people to exchange their local currency for goods or alternative currencies that better hold value, which further drives down the value of the local currency. This can spiral to extremes, as in Zimbabwe. The result is devastating for people as they see their life savings diminish to virtually nothing. Table 1 shows examples of recent hyperinflations.

Zimbabwe is one of the most extreme cases of inflation throughout history, but even today, some countries suffer from very high inflation. One is Venezuela, where its currency, the bolívar, experienced an 254% inflation rate during 2016 and suffered from about a 1,088% inflation rate in 2017. A staggering 1,370,000% inflation rate is forecast for 2018.

Moving value across national borders using national, or fiat, currency is hard, expensive, and sometimes even forbidden. If you want to send 1,000 Swedish crowns (SEK) from Sweden to a person in the Philippines, you can use a service like Western Union for the transfer. At the time I investigated this, 1,000 SEK was worth 5,374 Philippine pesos (PHP) or 109 US dollars. See Table 2.

If the recipient has a bank account that can receive an international money transfer, you can get away with a 4.9% fee. But a typical remittance recipient will be able to receive only cash, which doubles or triples the cost to 10.5% or 16.3%, depending on how quickly or conveniently they want it.

In contrast with international transfers, moving fiat currency within a nation state’s borders is usually convenient. For example, you can hand over cash directly to the recipient or transfer money using some mobile app made specifically for the currency. As long as you stay within one country and one currency, fiat currencies usually do a good job.

Instead of a central organization such as the US Federal Reserve controlling the currency, control of Bitcoin is distributed among thousands of computers, or nodes. No single node or group of nodes has more privileges or obligations than any other. This equality between nodes makes Bitcoin decentralized, as opposed to centralized systems, such as banks or the Google search engine (Figure 9).

In a centralized system, the service is controlled by a single entity, such as a bank. This single entity can decide who gets to use the service and what the user is allowed to do. For example, an online video service can choose to provide a video only to people in a certain geographical location.

With a decentralized system such as Bitcoin, which has several thousands of nodes spread around the globe, it’s extremely hard to control who uses the system and how. No matter where or who they are, or to whom they’re sending money, the Bitcoin system will treat all users equally. The Bitcoin system has no central point that can be exploited to censor payments, deny users service, or seize funds.

Changing the rules of Bitcoin is nearly impossible without broad consensus. If a node doesn’t obey the rules, the rest of the nodes will ignore it. For example, one rule is that Bitcoin’s money supply is limited to 21 million bitcoins. This limit is nearly impossible to change because of decentralization; there’s no one you can threaten or bribe to change these rules.

Because Bitcoin’s money supply won’t exceed 21 million bitcoins, people can be sure that if they own 1 bitcoin, they will always own at least one 21-millionth of the total supply of bitcoins. This feature isn’t found in any fiat currency, where decisions on supply are made every so often by a company or state. Bitcoin is resistant to high inflation because you can’t increase the money supply at will.

Bitcoin’s money supply isn’t fixed today. It’s increasing, at a diminishing rate, according to a predetermined schedule and will eventually stop increasing around the year 2140. See Figure 10.

Because Bitcoin is a system run by ordinary computers connected to the internet, it’s as global as the internet. This means anyone with an internet connection can send money to other people across the world, as Figure 11 illustrates.

There is no difference between sending a bitcoin to someone in the same room or sending it to someone on another continent. The experience is the same: money is sent directly to the recipient, who sees the payment nearly instantaneously. Within about 60 minutes, this recipient can be sure the money is theirs. Once settled, the transfer can’t be reversed without the recipient’s consent.

One interesting Bitcoin feature is that you keep your money safe by storing a set of private keys: the secret pieces of information you’ll need when you want to spend your money. You choose how those private keys are stored. You can write them on paper, or you can store them electronically with a mobile app to have easy access to them. You can also memorize your private keys. These keys are all anyone needs to spend your money. Keep them safe.

Savings is an attractive use case for Bitcoin. A simple way to save is to create a private key and write it down on a piece of paper that you store in a safe. This piece of paper is now your savings account, your savings wallet. You can then send bitcoins to your wallet. As long as your private key is kept safe, your money is safe. You can choose from a lot of different saving schemes to find the right balance between security and convenience. For example, you can keep your keys unencrypted in your mobile phone for easy access or store them encrypted on paper in a vault with armed guards.

As noted, moving money from one country to another is expensive (say, 15%), especially if you move money to a poor country, and the recipient doesn’t have a bank account. It’s becoming increasingly popular to use Bitcoin to circumvent this expensive and slow legacy system. It’s usually cheaper to exchange Swedish crowns for bitcoins in Sweden and transfer the bitcoins to your friend in the Philippines. Your friend will then exchange the bitcoins locally for Philippine pesos.

Some companies offer services so that you pay Swedish crowns to the company and the company pays out Philippine pesos to your friend (Figure 12). You won’t even know that Bitcoin is used under the hood. Such companies typically charge a few percent for the service, but it will still be cheaper than traditional remittance services.

Of course, if recipients can make good use of Bitcoin where they live, there’s no need for a middleman that takes a cut of the money. You can send bitcoins directly to your friend. This is what Bitcoin is all about. Exchanges and other such service companies are just bridges between the old legacy world and the new Bitcoin world.

The most obvious use case for Bitcoin is shopping. Bitcoin’s borderlessness and security make it ideal for online payments for goods and services.

In traditional online payments, you send your debit card details to the merchant and hope the merchant will withdraw as much as you agreed on. You also hope the merchant handles your debit card details with great care. They probably store the details in a database. Think about that: for every debit card purchase you make, your card details will be stored in that merchant’s database. It’s likely that one of the databases will be hacked and your card details stolen. The more merchants store your details, the higher the risk.

With Bitcoin, you don’t have that problem because you don’t send any sensitive information to the merchant, or anyone else. You transfer the amount of money you agreed on and nothing more.

The world is full of people wanting to get rich quick. Bitcoin can be alluring to them because of its price volatility, or tendency to change. Looking at the history of bitcoin’s price, as shown in Figure 13, it’s tempting to try to buy when it’s low and sell when it’s high.

Sometimes a government or big corporation makes a negative statement about Bitcoin that creates fear in the market, but those events tend to have a limited effect on bitcoin’s value.

Bitcoin’s price volatility seems contradictory to the claims of it having a non-inflationary property; a 50% drop in market value appears pretty inflationary. Bitcoin is still relatively new, and lots of short-term speculation causes this volatility. But as Bitcoin grows and more people and institutions start using it to store their wealth, it will probably stabilize in the long run, and its deflationary property will emerge over time.

Bitcoin is digital cash, but this form of cash can be used for things beyond money. This section covers two common uses, but there are others, including those not yet invented.

As you read in the Section 1.5.4, a bitcoin’s price can fluctuate dramatically. But where does this price come from? Several Bitcoin exchanges exist, most of them internet-based. They resemble stock markets, where users wanting to sell bitcoins are matched with users wanting to buy bitcoins.

Different markets can have different market prices depending on the supply and demand in that market. For example, in countries such as Venezuela, where the government tries to hinder the Bitcoin market, the supply is low. But the demand is high because people want to escape their hyperinflating currency. These factors drive the Bitcoin price up in that market compared to, for example, the US and European markets, where people can trade more freely.

Bitcoin is nice and all, but it’s not suitable for all financial activity. At least, not yet.

Cryptographic hash functions can be used as an integrity check to detect changes in data. Suppose you want to store your favorite cat picture on your laptop’s hard drive, but you suspect the stored picture might become corrupted. This could happen, for example, due to disk errors or hackers. How can you make sure you detect corruption?

First, you calculate a cryptographic hash of the cat picture on your hard drive and write it down on a piece of paper (Figure 22).

Later, when you want to look at the picture, you can check if it’s changed since you wrote the hash on that paper. Calculate the cryptographic hash of the cat picture again, and compare it to the original hash on your paper (Figure 23).

If the new hash matches the one on paper, you can be sure the picture hasn’t changed. On the other hand, if the hashes don’t match, the cat picture has definitely changed.

Bitcoin uses cryptographic hash functions a lot to verify that data hasn’t changed. For example, every now and then—on average, every 10 minutes—a new hash of the entire payment history is created. If someone tries to change the data, anyone verifying the hash of the modified data will notice.

The real answer is complex, so I won’t go into exact detail. But to help you understand the operation of a cryptographic hash function, we’ll create a very simplistic one. Well, it isn’t really cryptographic, as I’ll explain later. Let’s just call it a hash function for now.

Suppose you want to hash a file containing the six bytes a1 02 12 6b c6 7d. You want the hash to be a 1-byte number (8 bits). You can construct a hash function using addition modulo 256, which means to wrap around to 0 when the result of an addition reaches 256 (Figure 24).

The result is the decimal number 99. What does 99 say about the original input a1 02 12 6b c6 7d? Not much—99 looks just as random as any other single-byte number.

If you change the input, the hash will change, although a chance exists that the hash will remain 99. After all, this simple hash function has just 256 different possible outputs. With real cryptographic hash functions, like the one we used to hash the cat picture, this chance is unimaginably small. You’ll soon get a glimpse of this probability.

A cryptographic hash function takes any digital input data, called a pre-image, and produces a fixed-length output, called a hash. In the example with the cat picture on your hard drive, the pre-image is the cat picture of 1.21 MB, and the hash is a 256-bit number. The function will output the exact same hash each time the same pre-image is used. But it will, with extremely high probability, output a totally different hash when even the slightest variation of that pre-image is used. The hash is also commonly referred to as a digest.

Let’s look at what properties you can expect from a cryptographic hash function. I’ll illustrate using SHA256 because it’s the one Bitcoin uses most. Several cryptographic hash functions are available, but they all provide the same basic properties:

Figure 25 illustrates the first three properties. The fourth property of a cryptographic hash function is what makes it a cryptographic hash function, and this needs a bit more elaboration. There are some variations to the fourth property, all of which are desirable for cryptographic hash functions (Figure 26):

The term hard in this context means astronomically hard. It’s silly to even try. We’ll look at second-pre-image resistance as an example of what hard means, but a similar example can be made for any of the three variants.

Suppose you want to find an input to SHA256 that results in the same hash as “Hello!”:

You can’t change the input “Hello!” just a little so the function “won’t notice.” It will notice and will output a totally different hash. The only way to find an input other than “Hello!” that gives the hash 334d016f…​d42c87b7 is to try different inputs one by one and check whether one produces the desired hash.

Let’s try, using Table 7.

As you can see, we aren’t very successful. Think about how much time it would take for a typical desktop computer to find such an input. It can calculate about 60 million hashes per second, and the expected number of tries needed to find a solution is 2²⁵⁵. The result is 2²⁵⁵ / (60 × 10⁶) s ≈ 10⁶⁸ s ≈ 3 × 10⁶¹ years, or about 30,000,000,000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000,​000 years.

I think we can stop trying, don’t you? I don’t think buying a faster computer will help, either. Even if we had 1 trillion computers and ran them concurrently, it would take about 3 × 10⁴⁹ years.

Pre-image resistance, second-pre-image resistance, and collision resistance are extremely important in Bitcoin. Most of its security relies on these properties.

Table 8 shows several different cryptographic hash functions. Some aren’t considered cryptographically secure.

Generally, when a single collision has been found in a cryptographic hash function, most cryptographers will consider the function insecure.

A cryptographic hash function is a computer program that takes any data as input and computes a big number—a cryptographic hash—based on that input.

It’s astronomically hard to find an input that will result in a specific output. This is why we call it a one-way function. You have to repeatedly guess different inputs.

We’ll discuss important topics throughout this book. When you’ve learned about a specific topic, like cryptographic hash functions, you can put a new tool into your toolbox for later use. Your first tool is the cryptographic hash function, which is represented here by a paper shredder; the cryptographic hash is represented by a pile of paper strips.

From now on, we’ll use these tool icons to represent cryptographic hash functions and cryptographic hashes, with some exceptions.

Suppose you want to send your favorite cat picture to your friend Fred via email, but you suspect the picture might be, maliciously or accidentally, corrupted during transfer. How would you and Fred make sure the picture Fred receives is exactly the same as the one you send?

You can include a digital signature of the cat picture in the email. Fred can then verify this digital signature to make sure the cat picture is authentic. You do this in three different phases, as Figure 27 shows.

Step 1 is preparation. You create a huge random number: the private key. You can use this to create digital signatures. You then create the public key, which is used to verify the signatures the private key creates. The public key is calculated from the private key. You hand the public key to Fred in person so Fred is sure it belongs to you.

Step 2 is signing. You write an email to Fred and attach the cat picture. You also use your private key and the cat picture to digitally sign the cat picture. The result is a digital signature that you include in your email message. You then send the email to Fred.

Step 3 is verifying. Fred receives your email, but he’s concerned the cat picture might be corrupt, so he wants to verify the signature. He uses the public key he got from you in step 1, the digital signature in the email, and the attached cat picture. If the signature or the cat picture has changed since you created the signature, the verification will fail.

It’s time to return to our cookie token spreadsheet. The company is growing, and Lisa has a hard time recognizing everyone. She notices that some people aren’t honest. For example, Mallory says she is Anne, to trick Lisa into moving cookie tokens from Anne to the cafe, instead of from Mallory to the cafe. Lisa thinks of requiring everybody to digitally sign their cookie token transfers by writing a message and a digital signature in an email, as Figure 28 shows.

Suppose John is the new guy at the office. The company gave him some cookie tokens as a welcome gift when he started. Now, John wants to buy a cookie in the cafe for 10 CT. He needs to digitally sign a cookie token transfer. Figure 29 shows what he has to do.

Just as with the email to Fred in the previous section, there are three phases in this process (please compare with the steps in Figure 27 to see the similarities):

The signing and verification processes are based on a key pair. John needs a private key to sign payments, and Lisa will need John’s public key to verify John’s signatures. John needs to prepare for this by creating a key pair. He does this by first generating a private key and then calculating the public key from that private key, as Figure 30 shows.

John will use a random number generator to generate a huge, 256-bit random number. A random number generator is available on almost all operating systems. The random number is now John’s private key. The private key is then transformed into a public key using a public-key derivation function.

The public key is 33 bytes (66 hex digits) long. This is longer than the private key, which is 32 bytes (64 hex digits) long. The reason for the “extra” byte and how the public-key derivation function works is a hard topic, covered in Chapter 4. Luckily, you don’t have to be a cryptography expert to understand how signatures work from a user’s perspective.

Let’s summarize what you’ve learned about public and private keys. You create a key pair by first creating a private key. The private key is a huge, secret random number. The public key is then calculated from the private key.

You can use the private key to encrypt a message that can be decrypted only using the public key.

The encryption and decryption in this figure are the foundation for digital signatures. This process is not suitable for sending secret messages because the public key is usually widely known.

The reverse process is also common, in which the public key is used to encrypt and the private key is used to decrypt. This process is used to send secret messages. Bitcoin doesn’t use it.

Let’s have a close look at how the signing really happens (Figure 33).

The message John wants to sign is, “Lisa, please move 10CT to Cafe. /John”. The signing function will hash this message with SHA256, whose output is a 256-bit number. This hash value is then encrypted with John’s private key. The result is a digital signature that looks like this:

For example, using the input message “Lisa, please move 10CT to Mallory. /John” would generate this signature:

This isn’t remotely similar to the previous signature. This is good for John, because he knows his signature can’t be used for messages other than his specific message.

John has now composed an email to Lisa. This email contains a message and a signature of that message. John finishes by sending the email to Lisa.

Lisa looks at the email and sees it claims to be from John, so she looks up John in her table of public keys (Figure 34).

Lisa’s actions in this figure aim to determine that the cookie token transfer was signed by the private key it claims to be signed with. The message says it’s from John. She received John’s public key the other day and put that public key in her table of public keys. The things she has at hand are

Lisa takes the signature (B) and decrypts it with the public key (C) she looked up in her table of public keys. The decryption outputs a big number. If this number is equal to the hash of the message (A), it proves John’s private key was used to sign the message. Lisa takes the message (A), exactly as written, and hashes that message just like John did when he created the signature. This message hash is then compared with the decrypted signature. The message hash and the decrypted signature match, which means the signature is valid.

Note that this process works only if John and Lisa use the exact same digital signature scheme. This must be agreed on beforehand, but it’s usually standardized. In Bitcoin, everyone knows exactly what digital signature scheme to use.

Lisa can now be sure no one is trying to fool her. She updates the spreadsheet with John’s transfer, as shown in Figure 35.

John is in control of his cookie tokens because he owns the private key. No one but John can use John’s cookie tokens because he’s the only one with access to his private key. If his private key is stolen, he can lose any and all of his cookie tokens.

The morning after John’s transfer, he comes to the office, takes his laptop from his desk, and goes straight to the cafe to buy two morning cookies. He opens his laptop to write an email to Lisa:

He sends this email containing the message and a signature to Lisa. But the cafe doesn’t hand him any cookies. The guy behind the desk says he hasn’t seen an incoming payment of 20 CT yet. Lisa usually verifies and executes transfers quickly.

John opens the spreadsheet—he has read-only access, remember—and searches for “John.” Figure 36 shows what he sees.

John steps into Lisa’s office, asking for an explanation. She answers that she got a message signed with John’s private key, asking her to send money to a new coworker, Melissa. Lisa even shows him the message and signature. Of course, there is no Melissa at the office, even though several new employees have started at the company. Lisa doesn’t care about names anymore, only public keys and signatures. But she needs the name to look up the correct public key in the table.

The explanation to all this is that Mallory has

Lisa verified the transfer in step 3, concluded it was valid, and executed the transfer. John asks Lisa to revert the—according to him—fraudulent transfer. But Lisa refuses to do so. She thinks the transfer is perfectly valid. If John let someone see his private key, that’s his problem, not Lisa’s. That’s part of why she’s so trusted in the company—she keeps her promises.

John creates a new key pair and asks Lisa to add his new public key under the name John2. How can John secure his new private key and still have it readily available when he wants a cookie? John is pretty sure he won’t have more than 1,000 cookie tokens on that key.

The security of the spreadsheet has shifted from a system in which Lisa knows everyone’s face to one in which she knows everyone’s public key. In a sense, the security could be worse now, because it might be easier for Mallory to steal John’s private key than it is for her to trick Lisa into thinking Mallory is John. This depends on how John protects his private key. An important thing to note is that the security of John’s private key is totally up to him. No one will be able to restore John’s private key if he loses it. And Lisa sure isn’t going to reverse “fraudulent” transfers just because John is sloppy with security.

If John stores his private key in cleartext in a shared folder on the company’s intranet, anyone can easily copy it and use it to steal his cookie tokens. But if John stores the private key in an encrypted file, protected by a strong password, on his own laptop’s hard drive, getting a copy of his key is a lot harder. An attacker would have to

If John never has more than 50 CT on his private key, he might not be that concerned with security. But the cafe, which manages about 10,000 CT daily, might be concerned. John and the cafe probably need different strategies for storing their private keys.

A trade-off exists between security and convenience. You can, for example, keep your private key encrypted on an offline laptop in a bank safe-deposit box. When you want to buy a cookie, you’ll need to go to the bank, take the laptop out of your safe-deposit box, decrypt the private key with your password, and use it to digitally sign a message to Lisa that you save to a USB stick. Then, you’ll have to put the laptop back into the safe-deposit box, bring the USB stick back to the office, and send the email to Lisa. The private key never leaves
the laptop in the safe-deposit box. Very secure, and very inconvenient.

On the other hand, you can store your private key in cleartext on your mobile phone. You’ll have the key at your fingertips and can sign a message within seconds of when the urge for a cookie starts to nudge you. Very insecure, and very convenient.

Some of the different trade-offs, as illustrated in Figure 37, are as follows:

You can use any combination of these methods to store your keys. But as a rule of thumb, the greater the security against attackers, the greater the risk of you accidentally losing access to your key. For example, if you store the private key encrypted on your hard drive, you risk losing your key due to both computer failure and forgetting your password. In this sense, the more securely you store your key, the less secure it is.

Suppose a new coworker just started at the company. Her name is Faiza. The company wants to send her 100 CT as a welcome gift. How can the company send 100 CT to Faiza?

First, the company needs the recipient’s—Faiza’s—public key. Faiza hasn’t used cookie tokens yet, so she needs to create a key pair and give the public key to the sender—the company—as Figure 42 shows.

Faiza creates a private and a public key, following the same process described in Section 2.3.2, but she doesn’t give her public key to Lisa. Now that Lisa doesn’t have the table of names and public keys, there’s no longer any point in giving her the public key. She doesn’t need it. Instead, Faiza gives the public key to the entity that wants to pay her cookie tokens—the company.

The company creates a message asking Lisa to move 100 CT from 037e944a…36de9496 to 029a726c…ad8f436d. It then digitally signs the message and sends it to Lisa. Lisa uses

to verify that the message is signed with the private key belonging to the sender’s public key. She also verifies that the sender’s public key has enough funds in the spreadsheet. She does this the same way she did when the spreadsheet contained names—she searches for the sender’s public key and calculates the balance.

Lisa has never seen the recipient’s public key before, but she doesn’t care. She cares only that the sender has the money to spend and that the message is correctly signed. She’ll write into the spreadsheet’s recipient column whatever the message asks her to write.

Faiza sees the new row with her public key in the To column. It gives her a warm, fuzzy feeling. She can now spend her cookie tokens as she pleases. Faiza didn’t have to bother Lisa with her public key, saving Lisa a lot of work.

Let’s summarize what’s happened so far:

These changes have improved privacy and simplified Lisa’s work. At the end of this chapter, we’ll discuss more about how to further improve privacy.

The email to Lisa in this example probably reveals, to Lisa, who the sender is (the company, in this case) because of the From field of the email. For now, we can assume Lisa doesn’t reveal or use this personal information in any way. We use email in this example in place of Bitcoin’s peer-to-peer network. The Bitcoin network, discussed in detail in Chapter 8, doesn’t use any personal information.

Please take a moment to think about what Acme Insurances can now figure out from the spreadsheet. What information can it get if it figures out the name of the sender or recipient of one payment? It will be able to identify all payments that person has made.

Among the coworkers, some developers think they can replace 33-byte public keys with something shorter while still preserving enough security. They suggest replacing each public key in the cookie token spreadsheet with a cryptographic hash of the public key. This shortens senders and recipients in the spreadsheet but also protects users’ money in the event of a flaw in the public key derivation function, as we’ll see later. The hashing isn’t made with a single cryptographic hash function but with two different cryptographic hash functions, as Figure 43 illustrates. We’ll discuss the reason for using two hash functions in the next section.

The public key is first hashed with SHA256, which you should be familiar with from the previous chapter. The output of this cryptographic hash function is then hashed with RIPEMD160, a cryptographic hash function that outputs a 160-bit (20-byte) number. We call this final hash the public key hash (PKH). All public keys in the spreadsheet are replaced with their respective PKHs.

The payment process now differs from when Faiza received her 100 CT from the company. Suppose John wants to buy a cookie (Figure 44).

First, the message to Lisa is changed a bit. John must use the cafe’s PKH—which was previously a public key—as the recipient. The sender is still a public key in the message because that public key is needed to verify the signature. Lisa doesn’t keep people’s public keys around anymore.

Second, because the spreadsheet now contains PKHs, Lisa must calculate the PKH from the sender’s public key to check the sender’s balance and be able to enter the payment into the spreadsheet.

Using RIPEMD160 as the last cryptographic hash function is a deliberate choice to make the PKHs shorter. Compare the output from SHA256 with the output from RIPEMD160:

It’s a well-balanced trade-off between security and size.

But why have two different cryptographic hash functions? We don’t really know why this scheme was chosen for Bitcoin because its inventor, Satoshi Nakamoto, has stopped corresponding with the Bitcoin community. We can only speculate. Instead, let’s discuss some of the scheme’s properties.

If either hash function isn’t pre-image-resistant, the other still is. This means if you can calculate an input to RIPEMD160 that gives a certain PKH output, you still need to pre-image attack SHA256 (with about 2²⁵⁵ guesses) to find the public key. Likewise, if you can calculate an input to SHA256 that gives a certain output, you first need to pre-image attack RIPEMD160 before you can use that pre-image to calculate the public key.

On the other hand, if it turns out that the output set of either cryptographic hash function is smaller than anticipated, then the security of the combined hash-function chain suffers. To make this clearer, pretend SHA256 has only 100 possible output values. You can steal money from anyone by trying different random private keys and calculating the corresponding PKHs. If a PKH matches your target, you’ve found a private key you can steal the money with. On average, you’d only have to test 50 different private keys to steal from one PKH. This property gives the worst of both worlds: if either of the two functions is weak, then the whole chain is weak. The probability that any function has this flaw is small. If any such flaw exists, the reduction in the output set likely isn’t significant enough to endanger security in practice. Remember, we’ve yet to find one single collision in any of these cryptographic hash functions.

Another thing to note is that different organizations developed the two cryptographic hash functions. RIPEMD160 was developed at a European university in open collaboration with a broad community of cryptographers. SHA256 was developed by the US National Security Agency (NSA). Both are considered secure, and both have been subject to scrutiny from a large number of people.

Now that we’ve strengthened the security of the cookie token spreadsheet, let’s think about privacy again. Has this improved privacy? Is it harder for Acme Insurances to figure out information about who’s paying whom now compared to when we used public keys in the spreadsheet?

The answer is no. There is practically a one-to-one correspondence between the public keys and the PKHs. Using PKHs doesn’t hide personal information any more than using plain public keys.

Among the coworkers, the security-oriented people discuss the problem with typos and come up with the idea of cookie token addresses. A cookie token address is a PKH encoded to detect typing errors. The PKH can be converted back and forth between this encoding and plain byte format.

Suppose Faiza feels sorry for John and wants to give him 20 CT from her 100 CT to ease his pain. She doesn’t want to make the same mistake John did, so she asks him for his cookie token address. John creates this by encoding his PKH with a function called base58check (Figure 47).

The result is John’s cookie token address: 19g6oo8f…gCenRBPD. John hands this address to Faiza, who then makes a payment following the process in Figure 48.

The payment process changes for the payer, but nothing changes for Lisa. Faiza will base58check decode John’s address into a PKH. This decoding ensures that no typing errors were made in the address.

As mentioned previously, a PKH can be converted to an address and back to a PKH. It is not a one-way function. It’s just different ways to represent the PKH, either as a series of bytes or as an address (Figure 49).

The email to Lisa is exactly the same as before. Only users employ the cookie token address. It isn’t part of Lisa’s validation process or the spreadsheet in any way.

The concept table (Table 11) isn’t updated in this chapter. Cookie token addresses are exactly what Bitcoin uses, so we haven’t introduced any concepts that differ from Bitcoin.

Thanks to PKH and cookie token addresses, Lisa can ditch her table of public keys. You can add PKH and addresses to your toolbox for later use, and we release version 3.0 of the cookie token system (Table 12).

A password’s strength is measured in entropy. The higher the entropy, the harder it is to guess the password. The word entropy, as used in information security, comes from thermodynamics and means disorder or uncertainty. Suppose you construct a password of 8 characters from among the following 64 characters:

Each character in the password would then represent 6 bits of entropy because there are 64 = 2⁶ possible characters. If you select the 8 characters randomly (no cherry-picking, please!), say E3NrkbA7, the eight-character password will have 6 × 8 = 48 bits of entropy. This is equivalent in strength to 48 coin flips.

Suppose instead that you select random words from a dictionary of 2¹¹= 2,048 words. How many words do you need to use to beat the 48-bit entropy of your eight-character password? Four words wouldn’t be enough because 4 × 11 = 44 bits of entropy. But five words corresponds to 55 bits of entropy, which beats the password’s entropy.

A password’s real entropy also depends on what an attacker knows about the password. For example, suppose an attacker, Mallory, steals John’s encrypted backup file and tries to perform a brute-force attack on it. A brute-force attack means the attacker makes repeated password guesses, over and over, until they find the correct password. If Mallory knows the password’s length is exactly 8 and the characters are chosen from the 64 characters mentioned, the entropy is 48 bits. If she happens to know that the second character is 3, the entropy drops to 6 × 7 = 42 bits. On the other hand, if Mallory doesn’t know how many characters the password has, it will be harder for her, meaning the entropy will be higher.

This is true only if password selection is truly random. If John uses cherry-picking to select the password j0Hn4321, the entropy decreases dramatically. Typical password brute-force attack programs first try a lot of known words and names in different variations before trying more “random-looking” passwords. John is a well-known name, so an attacker will try a lot of different variations of that name as well as many other names and words. For example:

Bingo! Suppose there are 1,000,000 common words and names, and each word can come in 100,000 variations, on average. That’s 100 billion different passwords to test, which corresponds to about 37 bits of entropy; 100 billion tries will take a high-end desktop computer a few days to perform. Let’s say, for simplicity, that it takes one day. If John uses a truly random password, the entropy for the attacker is around 48 bits. It would take around 2,000 days, or about 5.5 years, to crack the password.

The process for password-encrypted backups works pretty well, but it also introduces new problems:

It seems you haven’t yet come up with a good way of dealing with backups. Let’s not settle for this half-bad solution—there are better approaches.

Let’s look deeper into how to generate the master xprv (Figure 63).

To create the master private key, the seed is hashed using HMAC-SHA512 (HMAC is short for Hash Based Message Authentication Code), which produces a 512-bit hash value. HMAC-SHA512 is a special cryptographic hash function that, besides the normal single input, also takes a key. From a user’s perspective, you can regard HMAC-SHA512 as a normal cryptographic hash function but with multiple inputs. The hash value is split into the left 256 bits and the right 256 bits. The left 256 bits become the master private key, which is a normal private key; it’s called the master private key because all other private keys are derived from this single private key (and the chain code). The right 256 bits become the chain code, used in the next step to derive children from the master xprv.

You just created Rita’s master xprv. It’s time to derive the child xprv that groups together her three savings keys. The direct children of an xprv can be derived in any order. Let’s derive the savings account key, m/1, first. The process for deriving a child xprv from a parent xprv is as follows (Figure 64):

This same process is used for all children and grandchildren of the master xprv until you have all the keys Rita wanted in her wallet.

You might be wondering why you need the addition—why not use the left 256 bits as the child private key? The 512-bit hash is calculated from the public key and the chain code—collectively called the extended public key (xpub)—and an index. You’ll see later how to use the xpub in less secure environments, such as a web server, to generate a corresponding tree of public keys. You need to add the parent private key to the left 256 bits to make it impossible for someone with the xpub to generate child private keys.

Recall that the seed is a sequence of bits. For example, Rita’s seed is 128 bits long. What if you could encode those bits in a more human-friendly way? You can!

Rita’s wallet used to create a seed using a random number generator, in the most straight-forward way possible. But if it had done it in a slightly different way, it could display her seed as a sequence of 12 English words, called a mnemonic sentence:

This is a three-step process as shown in Figure 66.

First, a random number is generated. Second, the mnemonic sentence, that can be used for backup, is generated from the random number. In the last and third step, you generate a seed from the mnemonic sentence. The last two steps are discussed more in detail in the next two subsections.

The encoding starts with the random number, as shown in Figure 67. The random number is hashed with SHA256, and the first 4 bits of the hash—in this case, 0111—are appended to the random number. Those 4 bits act as a checksum. You then arrange the bits into 12 groups of 11 bits, where each group encodes a number in the range 0 to 2047. Eleven bits can encode 2¹¹ = 2,048 different values, remember?

The 12 numbers are looked up in a standardized word list of 2,048 words numbered from 0 to 2047. You can find this list in BIP39 from Web resource 9; it contains commonly used English words. After looking up all 12 numbers, the result is the mnemonic sentence.

The sentence doesn’t mean anything in particular. It’s 12 random words, just like the hex-encoded seed is 32 random hex digits.

Rita’s wallet shows the mnemonic sentence to her, and she writes the 12 words down on a piece of paper. She puts the paper in a safe place and gets on with her life.

Rita’s wallet doesn’t stop there. It has yet to generate a seed that it can use to generate addresses for Rita. The wallet will generate the seed in many steps (Figure 68).

The mnemonic sentence is used as the main input for each of the 2048 HMAC-SHA512 functions. This is the same function as we used in Section 4.3.1 to generate a master xprv from the seed. The other input, which is called the key, is mnemonic1 in the first, leftmost, function. For subsequent functions the key input is the output of the previous function.

The output from each function is added using bitwise XOR (exclusive or) to form the final result, which is our 512 bit seed. In bitwise XOR, two numbers are compared bit by bit, and if the bits are equal the resulting bit is 0, otherwise 1. This seed is then used to generate a master xprv as described in Section 4.3.1.

You’re probably wondering why the seed generation uses 2048 steps of HMAC-SHA512. This process is called PBKDF2 (Password-Based Key Derivation Function 2), which is a standardized way to achieve so-called key stretching. Key stretching makes brute-force attacking the mnemonic sentence harder because each try becomes slower due to the many steps involved.

The next day, Rita drops her phone into the ocean, and it disappears into the deep. She lost her wallet! But Rita isn’t very concerned. She buys a new phone and installs the wallet app. She instructs her app to restore from a backup. The wallet asks her for her mnemonic sentence. She writes

into the wallet app. The app uses the 4-bit checksum discussed in the previous section to make sure it’s correct. It does that by running the mnemonic sentence generation backwards as Figure 69 illustrates.

If Rita accidentally writes the last word as deposit instead of depend, the checksum check will probably fail because she wrote the wrong word at the end. If she types depends instead of depend, the decoding will definitely fail because there’s no word depends in the word list.

The checksum is pretty weak—4 bits make only 16 possible checksums. A wrongly written mnemonic sentence, in which all words exist in the word list, would have a 1/16 probability of not being detected. This seems bad. But the probability that you’d write such a sentence is small, because your misspelled words have to exist in the word list. This reduces the risk of an invalid mnemonic sentence being restored.

After the checksum has been verified, the app regenerates the seed as shown in Figure 68 and all of Rita’s private keys can be restored from that seed.

Think back to when you derived a public key from a private key in Chapter 2. I didn’t really tell you how the public key was derived. I’ll make an attempt here instead.

A public key in Bitcoin is a whole-number solution to this equation:

Many such solutions exist, about \(2^{256}\) of them, so let’s simplify by using the solutions to \(y^2 = x^3 + 7 \mod{11}\) instead (Figure 78).

The previous equations are examples of a class of equations called elliptic curves, and a solution is often referred to as a point on the curve. You can now calculate a public key, which is a point on the curve, from a private key. To do this, start at a special point, \(G=(6,5)\), on the curve. \(G\) is somewhat arbitrarily chosen, but it’s widely known by everybody to be the starting point for public key derivation. The public key is the private key multiplied by \(G\).

Suppose your private key is \(5\). Then your public key is \(5G\).

To calculate this multiplication, you need two basic public key operations: addition and doubling, where doubling can be seen as adding a point to itself.

To add two points (Figure 79), you draw a straight line that “wraps around” the edges of the diagram and that intersects your two points and one third point. This third point is the negative result of the addition. To get the final result of the addition, take the symmetric point at the same \(x\) value.

The result of \((6, 5) + (2, 2)\) is \((7, 8)\). The straight line between the two points crosses the point \((7, 3)\). The complement point to \((7, 3)\) is \((7, 8)\), which is the result of the addition.

To double a point (Figure 80) is to add it to itself, but there’s no slope to be calculated from a single point. In this special case, you calculate the slope from the single point \(P=(6,5)\) as \(3*x^2*(2y)^{-1} \mod{11} = 2\). The process is almost the same as adding two different points, but you calculate the slope of the line differently.

Using these two basic operations, adding and doubling, you can derive the multiplication of \(5\) and \(G\). In binary form, \(5\) is

Your public key is then

Start in \(G\) and calculate the resulting public key point by taking terms from right to left:

In short, multiplication is performed by a sequence of adding and doubling operations.

The multiplication process is pretty easy to complete; it takes about 256 steps for a 256-bit private key. But to reverse this process is a totally different story. No known way exists to get the private key by point “division” (for example, point \((6,6)\) “divided by” \(G\)). The only known way is to try different private keys and see if the public key is what you’re looking for. This is what makes public-key derivation a one-way function.

You’ve seen how an ordinary public key is derived from a private key through public-key multiplication. But how can adding the parent public key with the public key derived from the left 256 bits make the child public key? See Figure 81.

You can convince yourself that it works by looking at both normal public-key derivation and child public-key derivation in the same picture: see Figure 82.

The nice thing with elliptic curves is that the special public key “add” operation works a bit like normal add. The same goes for the special public key “multiplication.” You can thus solve some equations:

The result, \(C=Gc\), is exactly how to derive the public key \(C\) from the private key \(c\).

Do you remember how John’s public key looked like a big number?

That doesn’t look like a pair of coordinates, does it? The public key is encoded in a certain way. Because of the symmetry, exactly two points exist for every value of \(x\), one with an even \(y\) value and one with an odd \(y\) value (Figure 83).

You don’t need to store \(y\) values, only whether the \(y\) value is even or odd. You do this by prefixing the \(x\) value with 02 (even) or 03 (odd). In John’s case, the \(y\) value happens to be odd, so the prefix is 03.

This is why public keys are 33 bytes and not 32 bytes. It’s a 256-bit number—the \(x\)-coordinate—prefixed by a byte specifying the odd/even property.

The curve in the figure has a single point \(x=5, y=0\). This doesn’t look symmetric, but it’s a so-called double-root to the curve—it’s two points with the same \(y\) value 0. They’re symmetric because they’re at equal distance 5.5 from the symmetry line. In this special case, both these points will use 02 because 0 is even.

Our concept table (Table 13) isn’t updated in this chapter. The wallets described in this chapter work basically as they do in Bitcoin, but they send an email to Lisa instead of sending a transaction across the global Bitcoin network. We’ll get to that in the next chapter.

Let’s have a release party! Cookie tokens 4.0, fresh from the lab!

Exercises 4.7 and 4.8 assume that you read Section 4.7. If you skipped that section, you can skip these exercises, too.

If you didn’t read Section 4.7, you can skip exercise 4.11.

Let’s dive in and look closer at how John’s transaction is created.

John’s wallet has created a new transaction (Figure 87). It has two inputs and two outputs. Inputs specify which outputs of previous transactions to spend. Outputs specify where the money goes.

The transaction is ready to be sent to Lisa. John’s wallet sends it as an attachment in an email. Lisa picks up the transaction and verifies that:

Lisa doesn’t have to calculate the PKH balance anymore, but she needs to check that the spent output exists and isn’t already spent.

How does she check that an output of a transaction is unspent? Doesn’t she have to search the spreadsheet to look for transactions that spend this output? Yes, she does. This seems about as cumbersome as searching through the spreadsheet to calculate balances. Don’t worry: Lisa has a plan.

Now that John’s transaction is stored in the spreadsheet exactly as he created it, anyone with read access can verify it. Anyone can create a private UTXO set, work through all the transactions, and end up with the exact same UTXO set as Lisa.

In Bitcoin, these verifiers are called full nodes. Lisa is also a full node (a verifier), but she does more than a full node—she updates the spreadsheet. A full node is also called a verifying node or, more casually, a node in Bitcoin.

Lisa can no longer steal someone else’s money, because doing so would make the spreadsheet invalid. For example, suppose she tried to change the output recipient of John’s transaction from PKH_C to PKH_L. She effectively tries to steal 10 CT from the cafe (Figure 92).

Because Lisa has changed the contents of John’s transaction, that transaction’s signatures will no longer be valid. Anyone with access to the spreadsheet can notice this because everything is super-transparent.

Let’s reflect on the changes we’ve made. We’ve moved from an account-based system to a value-based system.

An account-based system keeps track of how much money each account has. This is the type of system we had before this chapter. Lisa had to calculate the balance of a PKH before deciding whether to allow a payment.

A value-based system keeps track of “coins” instead. In this chapter, Lisa needs to verify that the specific coins (UTXOs) exist before deciding whether to allow the payment. She doesn’t have to verify the balance of any PKH. Bitcoin is also a value-based system.

In the example I just presented, the only acceptable signature script is a valid signature followed by the public key corresponding to the PKH in the pubkey script.

Using a programming language, Script, in the transactions makes them very flexible. You’ll see several different types of Script programs throughout this book. If the transactions didn’t use a programming language, all use cases would have to be invented up front. The Script language lets people come up with new use cases as they please.

I’ve already mentioned that “pay to PKH” isn’t the only way to pay. You can write any program in the pubkey script. For example, you can write a pubkey script that ends with OK only if the signature script provides two numbers whose sum is 10. Or, you can write a program that ends with OK only if the signature script contains the SHA256 pre-image of a hash. Consider this example:

This will allow anyone who knows an input to SHA256 that results in the hash 334d016f…d42c87b7 to spend the output. You happen to know from Chapter 2 that the text “Hello!” will give this specific output. Suppose your signature script is

Run the program to convince yourself that it works and that all signature scripts that don’t contain a correct pre-image fail.

You might wonder why we call the output script part pubkey script when it usually doesn’t contain a public key. Likewise, the input script is called signature script, but it doesn’t only contain a signature.

The pubkey script in Bitcoin transactions used to contain an actual public key, and the signature script used to contain the signature only. It was more straightforward then. A typical pubkey script looked like this

and the signature script like this:

Things have changed since then, but the names signature script and pubkey script remain. Most developers today look at this more abstractly: the pubkey script can be regarded as a public key, and the signature script can be regarded as a signature, but not necessarily ordinary public keys and signatures. In a normal payment today, the “public key” is the script that needs to be satisfied by the “signature,” the signature script. Of course, the “public key” here contains some operators and a PKH, but we can still view it as a public key on a conceptual level. The same goes for the signature script, which we can view as a signature on a conceptual level.

In p2pkh, the recipient generates a cookie token address that’s handed over to the sender. The sender then makes a payment to that address.

But what if the recipient would like their money secured by something other than a single private key? Suppose Faiza, Ellen, and John want to raise money for charity from their coworkers.

They could use a normal p2pkh address that their supporters donate cookie tokens to. They could let, say, Faiza have control over the private key, so only she could spend the funds. This approach has a few problems:

A lot of risks seem to be inherent in this setup, but what if Faiza gives the private key to her two charity partners? Then, all partners can spend the money. This will solve problems 1 and 2, but problems 3 and 4 would be worse because now any of the three partners might be sloppy with private-key security or run away with the money.

This organization consists of three people. It would be better if these three people could share the responsibility and the power over the money somehow. Thanks to the Script programming language, they can accomplish this.

They can create one private key each and demand that two of the three keys must sign the transaction to spend the charity funds. (Figure 101).

This brings some good properties to the charity fundraising account:

Figure 102 shows a script program that enforces the two-of-three rule.

The OP_CHECKMULTISIG operator instructs Lisa to verify that the two signatures in the signature script are made with the keys in the pubkey script. Lisa runs the program in Figure 103.

The top eight data items in the program are put on the stack. Then the only operator, OP_CHECKMULTISIG, runs, as illustrated in Figure 104. OP_CHECKMULTISIG takes a number, 3 in this case, from the stack and then expects that number of public keys from the stack followed by another number. This second number dictates how many signatures are needed to spend the money. In this case, the number is 2. Then, the operator takes the expected number of signatures from the stack, followed by the dummy mentioned earlier. You don’t use the dummy item.

OP_CHECKMULTISIG uses all this information and the transaction to determine whether enough signatures are made and verifies those signatures. If everything is OK, it puts OK back on the stack. This is where the program ends. Because the top item on the stack is OK, the output spending is authorized.

A coworker who wants to donate cookie tokens to the charity needs to get their wallet to write the pubkey script in Figure 102 into the donation transaction’s output. This presents a few problems:

You can fix all this with a small change to how the programs are run. Some developers among your coworkers invent something called pay-to-script-hash (p2sh).

We’ve discussed how p2pkh hides the public key from the sender, who gets a hash of the public key to pay to instead of the public key itself.

p2sh takes this idea even further—it hides the script program. Instead of giving a big, complicated pubkey script to the sender, you give them just the hash of the script. The sender then makes a payment to that hash and leaves it up to the recipient to provide the script later, when the recipient wants to spend the money.

Suppose again that Faiza, Ellen, and John want to raise money for charity, and they want a multisignature setup to protect their money (Figure 105).

To verify this transaction in full, you need new software. We’ll talk about how this new software verifies this transaction in a moment. First, let’s see how the old software would handle this transaction.

Faiza, Ellen, and John have created their two-of-three multisignature redeem script:

They now want people to pay to the redeem script’s SHA256+RIPEMD160 hash:

How do Faiza, Ellen, and John ask people to pay them? What do they print on the flyers so coworkers can pay to their script hash? Let’s look at a couple of their options:

In both cases, if the donor erroneously makes a p2pkh payment using the printed hash or address, no one can spend the money because no private key corresponds to this false PKH.

These two options seem neither safe nor practical. Instead, let’s introduce a new address format for p2sh, the p2sh address (Figure 109). This format is similar to normal p2pkh addresses. It uses the base58check encoding scheme, just as normal addresses did.

This process is almost the same as for p2pkh addresses. The only difference is that the version is 05 instead of 00. This will cause the address to begin with a 3 instead of a 1.

Because of this change and how base58 works—using integer division by 58 successively—the last remainder will always be 2. If you’re interested, Figure 110 provides the base58 encoding of the versioned and checksummed script hash of Faiza’s, Ellen’s, and John’s redeem script.

This last remainder 2 will translate to 3 in base58’s character-lookup table. This 3 character will become the first character when the base58 process performs the reversing step. This causes all p2sh addresses to start with a 3. This is how users identify them as p2sh addresses and not, for example, p2pkh addresses.

Faiza, Ellen, and John can now print 328qTX…wrB2ag on their flyer. When a coworker scans this flyer’s QR code, their wallet will recognize the address as a p2sh address because it starts with a 3. The wallet will base58check-decode the address and create a proper p2sh output:

This concludes our discussion of programmable transactions. You’ve learned that transactions can express a lot of different rules for how to spend money. Note that you can’t constrain where spent money goes, only what’s needed in the input to spend the money. The pubkey script makes the rules for what’s required in the signature script. Later in the book, we’ll revisit transactions to talk about more fancy stuff you can do with them, such as make spending impossible until a certain future date.

You might be wondering how the coworkers updated from the old spreadsheet—as it was in release 4.0—to the one that contains transactions. What happened to the already-existing cookie tokens in the spreadsheet?

They all agreed on a time slot when the upgrade would take place. During this time slot, Lisa created a single, huge transaction with one output per PKH in the spreadsheet. This transaction looks like a coinbase transaction but with a lot of outputs. Anyone can keep a version of the old spreadsheet and verify that this new transaction contains the exact same outputs as the old UTXO set. New verifiers can’t be sure it went well, though—they’ll have to trust Lisa with that.

Note that this isn’t at all how it happened in Bitcoin, which was designed for transactions from the beginning. The “initial state” in Bitcoin was an empty UTXO set. No one had any bitcoins.

Transactions and txid have been added to your toolbox. The concept-mapping table (Table 15) shrinks by two rows: emails to Lisa and rows in the spreadsheet are replaced by transactions. Note that you still use email to send the transaction to Lisa, but the transaction has the same format as in Bitcoin. This is why we can remove the row.

The next chapter will take care of replacing the spreadsheet, which now contains transactions, with a blockchain.

Let’s release version 5.0 of the cookie token system (Table 16).

Lisa creates a new block roughly every 10 minutes, containing unconfirmed transactions. She writes this block into a new file in a shared folder. Everyone has permission to create new files in the shared folder, but no one has permission to delete or change files. When Lisa writes a block to a file in the shared folder, she confirms the transactions in that block.

Suppose Lisa is about to create a new block at height 20. She’ll do the following:

Suppose Lisa wants to eat a cookie without paying for it. She creates a transaction and puts it in the block she’s currently working on, block height 21. She creates the block header, signs it, and writes the block to a new file (block_21.dat) in the shared folder (Figure 122).

The cafe watches the shared folder for incoming blocks. When Lisa writes the block file into the shared folder, the cafe downloads the block and verifies it. Verifying a block involves verifying the following:

Lisa has paid for a cookie, and the cafe has downloaded the block that contains Lisa’s transaction and verified it. The cafe gives Lisa the cookie, and she eats it.

Can Lisa undo this payment without being proven a fraud? Her only option is to make another, changed version of block 21 that doesn’t include her transaction and to write this new block to the shared folder as block_21b.dat (Figure 123).

The new version is like the old version but without Lisa’s transaction. Because she tampers with the transactions in the block, she has to update the merkle root in the header with a merkle root that matches the new set of transactions in the block. When she changes the header, the signature is no longer valid, and the header needs to be re-signed. To make the changed block available to verifiers, she needs to put the block on the shared folder, for example using filename block_21b.dat.

The cafe has already downloaded the first version of block 21. When Lisa adds the new block file, the cafe will discover that there’s another version of the block in the shared folder (Figure 124).

Now the cafe sees two different blocks at height 21, one that contains the 10 CT payment to the cafe and one that doesn’t. Both blocks are equally valid, and neither block is more accurate than the other from a verification perspective. But the good thing is that the cafe can prove Lisa is playing dirty tricks because she’s created two different signed versions of the block. The signatures prove Lisa cheated, and you no longer have a word-against-word situation. Lisa will be fired or at least removed from her powerful position as a transaction processor.

What if there were other blocks after block 21 when Lisa cheated? Suppose blocks 22 and 23 were already created when Lisa decided she wanted to delete her transaction (Figure 125).

Now she needs to make three alternative blocks: 21, 22, and 23. They must all be replaced by valid blocks.

The blockchain is a complicated way to sign a bunch of transactions. Wouldn’t it be much simpler if Lisa just signed all transactions ever made in one big chunk every 10 minutes? This would accomplish the same goal. But this approach has several problems:

By using the blockchain, Lisa has to sign only the most recent block of transactions while still, indirectly via the previous block ID pointer, signing all historic transactions, as Figure 126 shows.

Each block’s signature reinforces the previous blocks’ signatures. This will become important when we replace the signatures with proof of work in the next chapter.

The verifiers can also easily see what’s new since the last block and update their UTXO sets accordingly. The new transactions are right there in the block.

The blockchain also provides some nice extra features that we’ll discuss later, such as the merkle tree.

John’s wallet contains two addresses, @_a and @_b, but John doesn’t want to reveal to anyone that @_a and @_b belong to the same wallet. He has reason to be wary because he’s heard rumors that Acme Insurances pays good money for such information, to “adjust” premiums based on people’s cookie-eating habits.

It’s time to reveal how Lisa created the merkle root. Suppose Lisa is about to create the block header shown in Figure 134. She needs to calculate the combined hash of all transactions, called the merkle root (Figure 135). You calculate the merkle root by creating a hierarchy of cryptographic hashes, a merkle tree.

The transactions are ordered the same way they are in the block. If the number of items is odd, the last item is duplicated and added last. This extra item isn’t added to the block; it’s only duplicated temporarily for the merkle tree calculation.

Each item (transaction, in this case) is hashed with double SHA256. This results in four hash values of 256 bits each.

The hash values are pairwise concatenated, meaning two hashes are merged by appending the second hash after the first hash. For example, abc concatenated with def becomes abcdef.

The four hash values have now become two concatenated values. Because two is an even number, you don’t add an extra item at the end. The two concatenated values are each hashed separately, resulting in two 256-bit hashes.

These two hash values are concatenated into a single 512-bit value. This value is hashed, resulting in the 256-bit merkle root. This merkle root is written into the block header. If any transaction is added, deleted, or changed, the merkle root must be recalculated (Figure 136).

This is nice, because when Lisa signs the block header, you know that if someone tampers with the transactions in it, the signature becomes invalid.

The full node wants to send Tx₂ and Tx₃ to John’s wallet because it thinks those transactions might be interesting to John’s wallet. The full node wants to prove to the wallet that both Tx₂ and Tx₃ are included in the block. But let’s begin with proving only a single transaction, Tx₂. We’ll look at a bigger, more complex example later in this chapter.

How can the full node provide proof to the wallet that Tx₂ is included in the block? It can provide a partial merkle tree that connects Tx₂ to the merkle root in the block header. The general idea is to send the bare minimum to the lightweight wallet—just enough to verify that Tx₂ is in the block. In this example, the node will send the stuff in Figure 137 to the lightweight wallet.

The lightweight wallet will then use this information to verify that Tx₂ is in the block by calculating the intermediary hashes toward the root, and verify that the hash of Tx₂ is among the hashes provided by the full node (Figure 138).

The hash functions have been removed from the diagram to make it easier to read. The wallet can now be certain Tx₂ is in the block.

We’ve introduced the blockchain, which replaces the spreadsheet on Lisa’s computer (Table 18). This chapter also introduced a new concept specifically for the cookie token system: the shared folder. This folder will be replaced by a peer-to-peer network of full nodes in Chapter 8.

This blockchain is close to how Bitcoin’s blockchain works but with an important difference: Lisa signs the blocks using digital signatures, whereas in Bitcoin, they’re signed using proof of work.

It’s time again to release a new version of the cookie token system. Just look at the fancy new features in Table 19!

Suppose the current block height is 100. Tom and Qi have just published their block-signing public keys on the billboard and on the company’s intranet. All wallets start sending transactions to all three block producers, or miners. Figure 147 illustrates what happens.

If they all just do what Lisa did, they’ll produce a block every 10 minutes, resulting in three different blocks with roughly the same transactions. The major differences between the three conflicting blocks are the coinbase transaction and the signatures. The coinbase of Tom’s blocks would pay the block reward to Tom’s cookie token address, whereas the coinbase of Lisa’s blocks would pay the block reward to Lisa’s cookie token address.

To avoid this problem, the miners must somehow decide which one produces the next block. They could take turns, but this would be complicated because Lisa’s computer might be broken, or Tom might refuse to create a block for some reason. In such a scenario, the system would halt.

Let’s try another naive approach (Figure 148). Every second, each miner draws a random number between 0 and 999,999. If a miner happens to draw a number in the range 0 to 555, it will immediately sign and publish a block. The probability of drawing a lucky number on a single try is low—556/1,000,000, or roughly 1 in 1,800 tries. The miners draw one number per second, so each miner is expected to draw a lucky number every 30 minutes (1,800 seconds) on average. The three miners together will then produce on average 1 block every 10 minutes.

When a miner draws a lucky number, chances are low that either of the other two miners also drew a lucky number at the same time. This means, usually, only a single miner will produce the next block.

The miners save their blocks as <_last-8-hexdigits-of-blockid_>.dat in the shared folder, so multiple blocks at the same height don’t have to worry about file naming. An example of a filename is 9ce35c25.dat.

The system ticks on quite well, but once in a while, two miners draw a lucky number at the same time. They aren’t aware that another miner also drew a lucky number, so they’ll both produce a block at the same height. This situation is known as a blockchain split because the chain splits in two. Both branches are equally valid, so which one is “correct”? Which miner will “win” the block and collect the block reward of 50 CT?

You don’t know the winner yet. It’s up to the miners to decide which branch they want to extend with their next blocks. In Figure 148, both Tom and Qi have created a block at height 106. The different miners would likely think as follows:

When the miners have picked a block at height 106 to extend, they build a new block at height 107 and start drawing numbers again. Several outcomes are possible from this situation, assuming everyone is honest: an immediate resolution, a delayed resolution, or a split of a split.

Eventually, one branch of a split will win. The likelihood that two branches of length X happen next diminishes rapidly for increasing X:

A split of branch length 1 is quite likely to happen, but a branch of length 2 probably won’t happen during Lisa’s lifetime (she’s 45). No matter how long the splits are, eventually they’ll resolve with a winner. This seems like a nice scheme. But it has its issues:

Clearly, this system won’t be able to increase the number of miners beyond a controlled group of highly trusted participants. You’ll get a flood of blocks as miners start cheating, but you can’t prove they’re cheating. It’s possible they’re just really, really lucky.

To create a new block, a miner must produce a valid proof of work for the block before it’s considered valid. To make a valid proof of work, the miner must create a block-header hash that’s less than or equal to the target in the block header.

A block ID is a double SHA256 of the block header. As you learned in Chapter 2, the only way to find a pre-image to a cryptographic hash function is to try different inputs over and over until you find one. The same goes here; the miner must try different block headers until it finds one that hashes to a value less than or equal to the target.

Let’s go back in time and look at how Qi created her block. She creates a block, sets the target to 00000000926e…, and sets the nonce to 0. She then tests whether the proof of work is valid (Figure 156).

She calculates the block ID by hashing her block header with double SHA256. In this case, the block ID is aa9c614e7f50…. This number is bigger than the target:

The rule is that the block ID must be less than or equal to the target for the proof of work to be valid. Qi fails miserably.

This is where the nonce comes in. A nonce is just a silly number that doesn’t mean anything. It can be set to any value. Qi initially set the nonce to 0, but she could just as well have set it to 123 or 92178237. The nonce helps make a change in the block that will affect the block ID without changing any real data, like transactions or the previous block ID.

Qi will now try again to make a valid proof of work. She increases the nonce from 0 to 1 and tests the validity again (Figure 157).

When Qi changes the block header by increasing the nonce, the block ID changes—any tiny change in the header will result in a completely different block ID. This is the same property displayed in Section 2.2 in Chapter 2, when we changed the cat picture (Figure 158).

The new block ID is 863c9bea5fd8… This is also bigger than the target. Qi fails again. I’m sorry, but there’s no way around it—Qi must try once more. She increases the nonce from 1 to 2 and tests again (Figure 159).

The result is the same: miserable failure. The block ID was 005ce22db5aa… this time, which is still bigger than the target.

She repeats this over and over. For example, Figure 160 shows her 227,299,125th try. It was close, but close doesn’t help. She has to keep trying (Figure 161). And finally she gets the result shown in Figure 162.

The nonce 492781982 results in a block ID 000000003c77…. She compares this to the target:

Wow—this block ID is less than the target! Qi has performed a great deal of work to find a nonce that results in a block ID less than the target. She’s created a block with a valid proof of work. Great, now she’ll publish the block to the shared folder.

It’s important to realize that all miners build their own unique blocks. For example, Tom is working on his own block concurrently with Qi (and Lisa), but his set of transactions is different than Qi’s because his coinbase transaction pays the block reward to himself, whereas Qi’s coinbase transaction pays the block reward to Qi. This difference will cause the merkle roots in their respective block headers to differ. If Tom sets Qi’s winning nonce, 492781982, on his own block, he likely won’t meet the target. Other things that probably differ between their blocks could be the timestamp or the selected list of transactions.

Anyone can pick up the block from the shared folder and verify that the rule is met—the block ID is less than or equal to the agreed-on target. Block verification is now slightly different than before (Figure 163).

The difference from verifying a digitally signed block is that the full node verifies the block producer has provided a valid proof of work instead of a valid digital signature.

The blockchain will grow the same way as before, but the drawing of lucky numbers is replaced by hashing the block header (Figure 164). Table 20 compares the two systems.

Instead of drawing a random number each second, the miners draw a number about every 0.02 microseconds through cryptographic hashing. At the same time, the lucky number limit, or target, is set to the 256-bit number 00000000926e…=926eb9*2²⁰⁰ instead of just 555.

subtle but important difference is that with proof of work, it’s the chain with the most accumulated proof of work that’s considered the best branch to follow. In the lucky numbers case, nodes followed the longest chain. The accumulated proof of work for a blockchain is the sum of the difficulty of each individual block in the chain.

The difficulty of a block is a measurement of how many times harder it is to find a valid proof of work for that block compared to finding it for the genesis block.

More exactly, the difficulty of block B is calculated like this:

The target of the genesis block is divided by the target of B, which makes the difficulty of the genesis block exactly 1.

The gist of this is that the higher the target of a block, the lower the difficulty of that block, and the lower the target, the higher the difficulty. So, we sum all blocks’ difficulties in the blockchain to get the chain’s accumulated proof of work.

From now on, I’ll refer to the branch with the most accumulated work as the strongest branch or strongest chain. Another commonly used term is best chain. The distinction between the longest and the strongest chain will become important in Section 7.5.2 when I’ve introduced difficulty adjustments.

The nonce is a 32-bit number. This is pretty small. If a miner has tried all 4,294,967,296 possible numbers without success, they must do something else to change the block header. Otherwise, they’ll redo the exact same tries they’ve already made. Several options exist for making a change (Figure 165):

Changing the timestamp is straightforward—just add a second to the timestamp, and the header will be different. If you use one of the other two options, you’ll have to recalculate the merkle root because the transaction data has changed. When the merkle root is updated, the header changes.

Once you make any of these changes to the block, the header will change so the nonce can be reset to 0, and the miner can begin hashing again.

An interesting aspect of this system is that anyone can become a miner without asking for permission. They can just set up a computer at home and start building blocks. Blocks are no longer tied to a person but to an amount of computing work:

After Lisa’s and Rashid’s added hashrate, the total hashrate in the cookie token system has increased significantly:

Look: we’re producing more blocks per day than we designed for! The goal is 144 blocks per day, and 264 is significantly more than this. The block rate is too high, almost double the desired rate.

A higher block rate might seem beneficial because the confirmation time of transactions will decrease, but it comes with some problems.

We’ve fixed the hard problem of forcing “honest lucky numbers” in an interesting way. Let’s see what issues from Section 7.1.3 remain:

There’s only one problem left in the list. We’ll fix it in the next section.