Grokking Bitcoin

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 8).

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 9).

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 10).

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 11 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 12):

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 3.

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 4 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 13 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 14 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 15 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 13 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 16 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 [ch04]. 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 19).

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 20).

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 21.

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 22 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 23, 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.