The keys are organized as a tree, but it’s a tree turned upside down because that’s how computer geeks typically draw their trees. Anyway, the root key of the tree (at the top) is called the master private key. It’s the key from which all the rest of the keys are derived. The master private key has two child keys: one that represents the shopping account (left, in Figure 60) and one that represents the savings account (right). Each of these children has, in turn, its own children. The shopping account key has five children, and the savings account key has three children. These eight children have no children of their own, which is why they’re called leaves of the tree. The leaves are the private keys Rita uses to store cookie tokens, so an address is generated from each of these eight private keys.
Note how the keys in the tree are numbered. Each set of children is
numbered from 0 and upwards. This is used to give each key a unique
identifier. For example the first, index 0, savings key is denoted
m/1/0
. m
is special and refers to the master private key.
How is a tree structure like this accomplished? Let’s look closer at the creation of some parts of the tree.
Three important processes are performed to create the tree, as Figure 61 shows:
-
A random seed of 128 bits is generated. This seed is what the whole tree grows up (um, down) from.
-
The master extended private key is derived from the seed.
-
The descendant extended private keys of the master extended private key are derived.
An extended private key (xprv) contains two items: a private key and a chain code (Figure 62).
The private key is indistinguishable from an old-type private key generated directly from a random number generator. You can use it to derive a public key and a cookie token address. You usually make addresses only out of leaves, but you could use internal keys as well. The other part of the xprv is the chain code. A chain code is the rightmost 256 bits of a 512-bit hash, hence the right-half hash icon in the figure. You’ll see soon how that hash is created. The chain code’s purpose is to provide entropy when generating a child xprv. The master xprv doesn’t differ from other xprvs, but we give it a special name because it’s the ancestor of all keys in the tree. It is, however, created differently.
In step 1, the random seed is created in the same way as when you created private keys in Chapter 2. In this example, you generate 128 bits of random data, but it could just as well be 256 bits depending on the level of security you want—128 bits are enough for most users. You’ll see later how the choice of seed size will affect the backup process; a longer seed means more writing on a piece of paper during backup. We’ll get back to this in Section 4.5.
Steps 2 and 3 deserve their own subsections.
4.3.1. Deriving a master extended private key
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.
4.3.2.  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):
-
The desired index is appended to the parent public key.
-
The public key and index become the input to HMAC-SHA512. The parent chain code acts as a source of entropy to the hash function. To simplify, think of it as three pieces of data are hashed together.
-
The 512-bit hash value is split in half:
-
The left 256 bits are added, with normal addition (modulo 2256), to the parent private key. The sum becomes the child private key.
-
The right 256 bits become the child chain code.
-
-
The child private key and the child chain code together form the child xprv.
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.
4.4. Where were we?
Let’s recall why you’re here: to create a wallet app that makes life easier for end users (Figure 65).
The main duties of a wallet are to
-
Manage private keys
-
Create new addresses
-
Transfer payment details from payee to payer
-
Make a payment
-
Keep track of funds
-
Back up private keys
We’ve covered the first five items, but we aren’t quite finished with backups. We just looked at xprv derivation, which is the groundwork for better backups.
4.5. Back to backup
You want a safe, easy way to back up private keys. You’ve created an HD wallet to generate any number of private keys from a single seed. What’s the minimum Rita needs to back up to restore all keys in her wallet, should she lose it? Right: the seed (and the tree structure, see margin). As long as her seed is safe, she can always re-create all her keys.
Suppose Rita’s 128-bit (16-byte) seed is
16432a207785ec5c4e5a226e3bde819d
It’s a lot easier to write these 32-hex digits on a piece of paper than it would be to write her eight private keys. But the biggest win is that Rita can write this down once and lock it in a safe. As long as that paper is safe, her wallet is safe from accidental loss. She can even create new keys from the same seed without having to make another backup.
But it’s still difficult to write this down without any typos. What if Rita makes a typo and then loses her wallet? She won’t be able to restore any of her keys! You need something even simpler that’s more compatible with how humans work.
4.5.1. Mnemonic sentences
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:
bind bone marine upper gain comfort defense dust hotel ten parrot depend
This mnemonic sentence presents the seed in a human-readable way. It’s much more approachable to write down 12 words than it is to write down cryptic hex code. If Rita loses her wallet, she can install the wallet app on another phone and restore the seed from those 12 words. Rita can regenerate all her private keys from that seed.
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.
4.5.2. Generating a mnemonic sentence
| We’re going to explore how the mnemonic sentence and seed generation works. It’s really fun, but if you think this section goes too deep, you can accept the previous section and skip to Section 4.6. |
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 211 = 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.
4.5.3. Generating a seed from a mnemonic sentence
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
bind bone marine upper gain comfort defense dust hotel ten parrot depend
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.
4.6. Extended public keys
Rita created her wallet from a random 128-bit seed, which she backed up with a 12-word mnemonic sentence. Her wallet can create any number of private keys from that seed. She can organize them into different “accounts” as she pleases. Very nice. But HD wallets have another feature: you can create a tree of public keys and chain codes without knowing any of the private keys.
Suppose the cafe uses an HD wallet. It wants to start selling cookies on its website and delivering those cookies to coworkers’ cubicles.
For privacy reasons, the web server needs to be able to present a new cookie token address for every sale, but where does it get the addresses? The cafe could create an xprv for an online sales account in its HD wallet and put that xprv on the web server, as Figure 70 shows.
The web server can now create new addresses as the orders pour in. Great! But what if Mallory, the gangster, gains access to the web server’s hard drive? She can steal all the money in any of the addresses in the online sales account. She can’t steal from any other addresses in the tree. For example, she can’t calculate any key in the counter sales account because she doesn’t have access to the master xprv, which is needed to calculate the counter sales account key and all its children.
Typical web servers are prone to hacking attempts because they’re usually accessible from anywhere in the world. Storing money on the web server would probably attract a lot of hacking attempts. Sooner or later, someone would succeed in getting access to the web server’s hard drive, and steal the xprv.
For this reason, the cafe wants to avoid having any private keys on the web server. Thanks to the HD wallet, this is possible by using xpubs (Figure 71).
An xpub is similar to an xprv, but the xpub contains a public key and a chain code, whereas the xprv contains a private key and a chain code. An xprv shares the chain code with the xpub. You can create an xpub from an xprv, but you can’t create the xprv from the xpub. This is because public key derivation is a one-way function; a public key can be derived from a private key, but a private key can’t be derived from a public key.
The cafe puts the xpub M/1
on the web server. By convention, we use
M
to denote an xpub path and m
to denote an xprv path. M/1
and
m/1
have the same chain code, but M/1
doesn’t have the private key,
only the public key. You can create the whole xpub tree from the master
xpub (Figure 72), which means you can generate any and all addresses
without any private key. You can create addresses, but not spend money
from those addresses.
This looks exactly like when you generated the tree of xprvs. The difference is that you have no private keys. As Figure 73 shows, the xpubs are generated differently than the xprvs. Please compare this to the xprv derivation.
This resembles xprv derivation. The difference is what you do with the left 256 bits of the 512-bit hash. To calculate the child public key, you treat the left 256 bits as if they were a private key and derive a public key from them. This public key is then added to the parent public key using the special public key addition operation. The result is the child public key. Let’s compare the child public key derivation to the child private key derivation (Figure 74) from the point after generating the left 256 bits of the HMAC-SHA512 hash.
Normal addition is used for the private key. You add a 256-bit number to the parent private key to get the child private key. But to keep the result within 256-bit numbers, you use addition modulo 2256.
The addition used to derive the child public key isn’t exactly what most people (including me) are used to. For now, let’s just say this addition works. We’ll dig deeper into that in Section 4.8.
4.7. Deriving hardened private keys
| This section is challenging. If you had a hard time understanding xprv derivation and xpub derivation, I suggest skipping this section and jumping to Section 4.8. You don’t need this section to understand the rest of this book. |
This section will explain how to prevent a potential security issue with normal xprv derivation.
The cafe’s online business works well. People are ordering cookies like crazy! The online sales account grows, with a new public key for every order. The xpub for the online sales account sits on the web server, and the xprv is present only in the cafe’s wallet (and in a locked-away mnemonic sentence).
Suppose Mallory somehow steals the private key m/1/1
, which contains
only 10 CT. This might seem harmless because that private key has so
little money in it. But it could be worse than that. If Mallory has
also managed to get the xpub for the online sales account from the web
server, she can calculate the online sales xprv, as Figure 75
shows.
m/1/1
from the cafe and the parent xpub from the web server. She can now steal all the money in the online sales account.Remember how the xprv derivation function used normal addition to calculate a child private key from a parent private key?
You can write this just as well as
Mallory has everything she needs to calculate the left-half hash for any
child index of M/1
she pleases, but she doesn’t know which index her
stolen private key has, so she starts testing with index 0:
She derives the public key from this private key and notices that it
doesn’t match M/1
, so 0
wasn’t the correct index. She then tries
index 1
:
This private key derives to the public key M/1
. Bingo! She has
calculated the private key m/1
for the online sales account. The xprv
shares the chain code with the xpub, so she also has the xprv for m/1
,
and she can calculate the private key tree for the account. Mallory
steals all the money from the online sales account. Not good.
Now think about what would happen if Mallory had the master xpub. She
could use the same technique to derive the master xprv from the master
xpub and m/1/1
. Mallory can re-create all the private keys of all
accounts in the entire wallet. Can you do something to prevent such a
catastrophic scenario? Yes, with yet another key-derivation
function! This new key-derivation function is called hardened xprv
derivation.
Suppose the cafe wants to prevent Mallory from accessing the master xprv, even if she got the master xpub and a private key in the online sales account. The cafe can generate the xprv for the online sales account using hardened xprv derivation, as Figure 76 shows.
The apostrophe in m/1'
isn’t a typo: it’s used to denote hardened
key derivation. The difference is that with hardened key derivation,
you hash the private key instead of the public key. An attacker
can’t do the “minus” trick anymore because the hash is derived from
the parent private key. Mallory can’t calculate the left-half hash to
subtract from the child private key because she doesn’t have the
parent private key. Figure 77 illustrates the result.
m/0'
and m/1'
are hardened keys.This also means you can’t derive a hardened child xpub from a parent
xpub. You must have the parent xprv to generate any children, public
or private. The children of m/1'
can’t be derived as hardened
private keys because that would require the cafe to put the private
key m/1'
on the online sales web server, which would be
insecure. Using nonhardened leaf keys in the online sales account
makes the cafe vulnerable to an attacker stealing m/1'/1
and
M/1'
. If that happens, all funds in the account will be stolen. With
hardened xprv, you solve the case of a stolen M
and m/1'/1
but not
the case with a stolen M/1'
and m/1'/1
.
4.8. Public key math
This section digs deeper into the math behind public keys. We’ll start by looking at how a public key is derived from a private key using public key multiplication. Later subsections will show why child xpub derivation, using public key addition, works, and how public keys are encoded in Bitcoin.
4.8.1. Public key multiplication
| I’ll try to explain this topic in simple terms, but if you think it’s too much, you can skip this section and jump to Section 4.9. |
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:
-
Calculate \(2^0*G = 1*G = G\). Easy. Now remember this point.
-
Calculate \(2^1*G = 2*G\). This is a point doubling of the previously remembered point G from step 1. Remember the point.
-
Calculate \(2^2*G = 2*2*G\), which is a doubling of the previously remembered point \(2*G\). Because there is a 1 in front of the \(2^2*G\) term, you add this result to the result of step 1.
In short, multiplication is performed by a sequence of adding and doubling operations.
4.8.2. Why is this secure?
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.
4.8.3. Xpub derivation
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\).
4.8.4. Public key encoding
Do you remember how John’s public key looked like a big number?
035541a13851a3742489fdddeef21be13c1abb85e053222c0dbf3703ba218dc1f3
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.
4.9. Recap
Let’s look back at what you’ve learned in this chapter. An HD wallet generates a tree of keys from a random seed. It can use key hardening to isolate different branches of the tree from each other.
Users back up their keys by writing the random seed in the form of 12 to 24 English words on a piece of paper and lock it up safely.
The cafe accepts cookie tokens in its online shop. It only puts the
xpub for the online sales account, M/1'
, on the web server, which
can now create as many addresses as needed without using any private
keys. The private keys are kept in the cafe’s wallet and never touch
the web server.
4.9.1. System changes
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.
| Cookie Tokens | Bitcoin | Covered in |
|---|---|---|
1 cookie token |
1 bitcoin |
|
The spreadsheet |
The blockchain |
|
Email to Lisa |
A transaction |
|
A row in the spreadsheet |
A transaction |
|
Lisa |
A miner |
Let’s have a release party! Cookie tokens 4.0, fresh from the lab!
| Version | Feature | How |
|---|---|---|
4.0 |
Easy to make payments and create new addresses |
Mobile app “wallet” |
Simplified backups |
HD wallets are generated from a seed. Only the seed, 12 to 24 English words, needs to be backed up. |
|
Creating addresses in insecure environments |
HD wallets can generate public key trees without ever seeing any of the private keys. |
|
3.0 |
Safe from expensive typing errors |
Cookie token addresses |
Privacy improvements |
A PKH is stored in the spreadsheet instead of a personal name. |
|
2.0 |
Secure payments |
Digital signatures solve the problem with imposters. |
4.10. Exercises
4.10.1. Warm up
-
Suppose you use a bitcoin wallet app and want to receive 50 BTC from your friend to your Bitcoin address
155gWNamPrwKwu5D6JZdaLVKvxbpoKsp5S
. Construct a payment URI to give to your friend. Hint: in Bitcoin, the URI starts withbitcoin:
instead ofct:
. Otherwise, they’re the same. -
How many coin flips does a random password of 10 characters correspond to? The password is selected from a 64-character alphabet.
-
Name a few problems with password-protected backups. There are at least four.
-
What three major steps are involved when a seed is created in an HD wallet that uses mnemonic sentences? You only need to answer this on a high level.
-
What does an xprv consist of?
-
What does an xpub consist of?
Exercises 4.7 and 4.8 assume that you read Section 4.7. If you skipped that section, you can skip these exercises, too.
-
Suppose you want to make a hardened xprv with index
7
fromm/2/1
. What information do you need to createm/2/1/7'
? -
Can you derive xpub
M/2/1/7'
fromM/2/1
? If not, how would you deriveM/2/1/7'
?
4.10.2. Dig in
-
Suppose you’re a bad guy and have the master xpub of a clueless victim. You’ve also stolen the private key
m/4/1
that contains 1 BTC. Assume you also know this private key has this specific path. Describe how you’d go about calculating the master xprv. Use these hints: -
Suppose instead that your clueless victim had 0 bitcoins on the private key
m/4/1
, but plenty of money on other addresses under the same xprv. Would you be able to steal any money?
If you didn’t read Section 4.7, you can skip exercise 4.11.
-
Suggest a better approach your victim could have used to prevent you from stealing all the money.
-
Say the cafe owner wants employees to have access to the counter sales account because they must be able to create a new address for each sale. But they must not have access to the private keys because the owner doesn’t trust the employees to handle them securely. Suggest how to achieve this. Hint: a wallet can import an xpub.
-
Suppose you work at the cafe and have loaded an xpub into your wallet. Your colleague Anita has loaded the same xpub into her wallet. You can both request payments from customers that go into the same account. How would you notice when Anita has received money into a previously empty key? Hint: you can create keys ahead of time.
4.11. Summary
-
You usually use a mobile app, called a wallet, to send and receive money—cookie tokens or bitcoins.
-
The wallet creates and stores keys, scans or shows payment details, sends payments, shows your balance, and backs up keys.
-
Backups are hard to do right. Password-protected backups suffer from problems with forgotten passwords, technology improvements, and humans being lousy random number generators.
-
With HD wallets, you back up your random seed and store that seed in a safe place. Do it only once.
-
The seed can be encoded using a mnemonic sentence, which makes it easier to write down the seed.
-
HD wallets generate multiple private keys from a seed and organize them in a tree structure to improve privacy.
-
The tree of public keys—or any of its branches—can be generated from an xpub. This is useful for insecure environments such as web servers.
-
Hardened private key derivation keeps “accounts” compartmentalized. It confines an attacker to a single account.
5. Transactions
This chapter covers
-
Bitcoin, or cookie token, transactions
-
Creating, confirming, and verifying transactions
-
Programming money
The cookie token payments you and your coworkers have been making so far have some serious problems. The worst is that Lisa can steal, which worries some new people. They’re hesitant to use the system if they know Lisa can steal from them.
This chapter will focus mainly on transactions (Figure 84): pieces of data that formalize how users send payments to Lisa. Transactions replace the old email to Lisa. They’ll be stored as is in the spreadsheet instead of using the current To, From, and CT scheme. This will make it impossible for Lisa to steal other people’s money because anyone can now verify all payments in the spreadsheet.
In this chapter, we’ll go deep on transactions and explore how they’re programmable, meaning they’re flexible as far as what you can do with them. For example, multisignature transactions can require two signatures out of three possible signatures, to spend money shared among three people.
After this chapter, the system will have changed a lot—in how wallets create payments, how Lisa verifies payments, and how payments are stored. Most important, everyone will be able to verify payments in the spreadsheet.
5.1. Problems with the old system
Lisa is performing valuable work. She makes sure no one cheats by verifying digital signatures and checking public key hash (PKH) balances before confirming a payment. She confirms payments by adding them to the cookie token spreadsheet.
But this old approach presents several problems:
-
Lisa is getting tired of calculating the balance before approving a payment. The ledger is growing, and each check becomes more time-consuming as new payments are added.
-
If you have two addresses with 5 CT each, you must make two separate payments to pay 10 CT for a cookie. This lays an unnecessary burden on the sender as well as Lisa. It also bloats the spreadsheet with excessive rows.
-
Because the company has grown and some people don’t know Lisa well, trust in her begins to fade. Some people fear Lisa will steal cookie tokens from them in the spreadsheet. Only Lisa can verify signatures because only she sees the emails sent to her. So she could increase the CT column of a payment to her or add a row with a false payment from, say, John to Lisa (Figure 85). No one could prove Lisa committed fraud. It doesn’t matter that she’s the most trustworthy human on earth. If people don’t know that, they’re going to assume Lisa is as greedy as everyone else.
Note that Lisa can’t create any new money, other than the 7,200 CT per day as agreed. Also if she tries to steal more than what’s available on a PKH, someone verifying the spreadsheet will notice the total amount of money is becoming too big. Lisa will get busted.
Lisa hates that people distrust her. She knows there’s not much she can do to change her coworkers’ level of trust. An interesting alternative is to minimize the trust needed. She concludes that the best way to do this is to make the process super-transparent so everyone can verify payments. At the same time, she’ll improve how she verifies that people don’t spend money they don’t have and how to spend from multiple addresses at the same time. She invents the cookie token transaction to solve the three problems outlined previously.
5.2. Paying using a transaction
Transactions will replace both how a user’s wallet sends a payment to Lisa and what’s stored in the spreadsheet. They won’t change how wallets behave from a user’s perspective—the wallet app will look exactly the same.
Suppose John wants to buy a cookie in the cafe. He won’t email Lisa the way he’s done so many times before. The wallet software now uses transactions, so his wallet will create a transaction instead, as Figure 86 shows. The transaction’s purpose is to pay 10 CT to the cafe’s cookie token address.
John scans the cafe’s payment URI, and his wallet creates a transaction and asks him to accept it. He clicks OK, and the wallet signs the transaction. John’s wallet then sends the signed transaction as an attachment in an otherwise empty email to Lisa.
The transaction contains information about where to send money. But it also contains information about what money to spend by referencing specific “coins” called unspent transaction outputs (UTXOs) that John received in previous transactions.
Lisa verifies that the coins spent in the transaction exist and aren’t already spent. She also verifies that the signatures—there might be several in a transaction—are valid. If all checks pass, Lisa confirms the transaction by appending it, exactly as she received it, to the end of the spreadsheet.
Once the transaction hits the spreadsheet, anyone can make the same verification of that transaction that Lisa did. They can do this to verify Lisa doesn’t steal money from someone else or otherwise mess with other people’s money.
In the next three subsections, we’ll dig deeper into the three phases: create, confirm, and verify.
5.2.1. Creating the transaction
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.
Inputs
The inputs specify which transaction outputs to spend. John has two UTXOs, one with 8 CT and one with 5 CT. The unspent outputs belong to two previous transactions, transaction 1 and transaction 2, that paid money to John. Now, John wants to spend these UTXOs.
A transaction input references a previous transaction using the previous transaction’s transaction ID (txid). The transaction’s txid is its double SHA256 hash. It’s called a transaction ID because this hash is often used to refer to the transaction, as in the case with inputs in Figure 87.
| The rationale for using double SHA256 here isn’t entirely clear, but doing so prevents something called a length-extension attack. Bitcoin’s creator probably used double SHA256 as a security measure in order to not have to think about these kinds of attacks. For details, see Web resource 12. |
John’s first input, with index 0, contains
-
The txid of transaction 1
-
The index, 1, of the output in transaction 1 to spend
-
An empty placeholder for a signature
His second input, with index 1, contains
-
The txid of transaction 2
-
The index, 0, of the output in transaction 2 to spend
-
An empty placeholder for a signature
John will fill in the signatures last, after the transaction is otherwise complete.
Outputs
A transaction output contains an amount and a PKH. John’s transaction has two outputs. The output at index 0 pays 10 CT to PKHC, the cafe, for the cookie. The output at index 1 pays 3 CT back to one of John’s own keys, PKH3. We call this change because it resembles traditional change, in which you pay $75 with a $100 bill and get $25 back: John pays with 13 CT and gets 3 CT back to his change address, PKH3. Change is needed because you can’t partly spend a transaction output.
The outputs and inputs are a bit more advanced than just specifying a PKH in an output and a signature in the input. In reality, the output contains a computer program that will verify the signature in the spending input. We’ll talk more about this later.
For a transaction to be valid, the sum of the input amounts must be greater than or equal to the sum of the output amounts. The difference, if any, is called a transaction fee, which we’ll discuss in Chapter 7. For now, John pays no transaction fee, so his output sum matches the input sum exactly.
The transaction is now created, but it isn’t yet signed. Anyone could have created this transaction because it’s based completely on public information. The inputs just refer to transactions in the spreadsheet and indexes within those transactions. But only John will be able to sign this transaction, because only he has the private keys corresponding to PKH1 and PKH2.
Signing the transaction
John clicks OK in his wallet to approve signing the transaction. The wallet now needs to make two signatures, one for PKH1 and one for PKH2. This is because John must prove he has both the private key for PKH1 and the private key for PKH2. See Figure 88.
Each input needs to be signed individually. The private key corresponding to PKH1 must be used to sign the input at index 0 because that input spends money addressed to PKH1. Similarly, the private key corresponding to PKH2 must be used for the signature of the input at index 1 because it spends money addressed to PKH2.
Each signature will commit to the entire transaction, which means the signing algorithm will hash the entire transaction, excluding signatures. If anything changes in the transaction, any signature made for this transaction will become invalid.
To make verification easier, you sign a cleaned version of the transaction, which means there are no signatures in any of the inputs. You can’t put a signature in input 0 and then sign input 1. Verification would be difficult if the person verifying didn’t know in what order the signatures were made. If you make all signatures from a cleaned transaction and then add all signatures to it, it doesn’t matter in what order the signatures were made.
When the wallet has made all signatures, it adds them to the transaction. But one piece is still missing. How can someone verifying the transaction—for example, the cafe—know which public key to use to verify a signature? The cafe can see only the PKH in the spent output and the signature in the spending input. It can’t get the public key from the PKH because cryptographic hashes are one-way functions, remember? John’s wallet must explicitly add the corresponding public key to the input. The signature in input 0 that spends money from PKH1 needs to be verified with the public key from which PKH1 was generated. Similarly, input 1 gets the public key corresponding to PKH2.
5.2.2. Lisa confirms the transaction
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:
-
The transaction spends outputs of transactions that actually exist in the spreadsheet and that they aren’t already spent by some other transaction in the spreadsheet.
-
The total value of the transaction outputs doesn’t exceed the total value of the transaction inputs. Otherwise, the transaction would create new money out of thin air.
-
The signatures are correct.
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.
Unspent transaction output set
To make the unspent checks easier, she creates a new, private database that she calls the UTXO set (Figure 89). It’s a set of all UTXOs.
An entry in the UTXO set consists of a txid, an index (idx), and the actual transaction output. Lisa keeps her UTXO set updated while verifying transactions.
Before Lisa adds John’s transaction to the spreadsheet, she makes sure all outputs that the transaction spends are in the UTXO set. If not, then John is trying to spend money that either never existed in the spreadsheet or is already spent (usually referred to as a double-spend attempt).
For each input in John’s transaction, Lisa uses her UTXO set to look up the txid and the output index. If all spent outputs are present in the UTXO set, no double-spend attempt or spending of nonexistent coins is detected. In this case, Lisa finds both outputs in her UTXO set and starts verifying signatures. Lisa needs to verify the signatures of both of John’s transaction inputs.
She grabs the PKH from the output spent by the first input and verifies that it matches the hash of the public key in the input (Figure 90). She verifies the signature in the input using the public key, the signature, and the transaction, and then verifies the second input’s signature the same way. Both are good.
Lisa then adds the confirmed transaction to the spreadsheet. She must remove the newly spent outputs from the UTXO set and add the outputs of John’s transaction to it (Figure 91). This is how she keeps the UTXO set updated to reflect the transaction spreadsheet’s contents.
Lisa keeps the UTXO set up to date by updating it as Figure 91 illustrates for every incoming transaction. If she loses the UTXO set, she can re-create it from the spreadsheet by starting with an empty UTXO set and reapplying all transactions in the spreadsheet to it, one by one.
It isn’t only Lisa who can create a UTXO set. Anyone with access to the spreadsheet can now do the same. This is important in later chapters, when we replace Lisa with multiple people doing her job. It’s also important for people who just want to verify the spreadsheet to convince themselves the information in it is correct.
5.2.3. Anyone verifies the transaction
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.
This means anyone can make the same checks that Lisa does. They can verify that Lisa is doing her job. These verifiers are important to the system because they make sure updates to the spreadsheet obey the agreed-on rules.
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 PKHC to PKHL. 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.
Security consequences of public signatures
The good thing about public signatures is that anyone can verify all transactions. But there’s a slight drawback.
Remember in Chapter 3, when we introduced PKHs? When you used PKHs, the public key wasn’t revealed in the spreadsheet. This protected money with two security layers: the public-key derivation function and a cryptographic hash function (SHA256 + RIPEMD160). If the public key was revealed somehow, the private key would still be protected by the public-key derivation function. It was like a belt and suspenders type of thing.
But using transactions, the public key is revealed in the spending transaction’s input when an output is spent. Look at John’s transaction again in Figure 93.
The input contains the public key. But it only reveals the public key once the output is spent. This brings up an important point: don’t reuse addresses! If John has other unspent outputs to PKH1, those outputs are now less secure because they’re no longer protected by the cryptographic hash function—only by the public-key derivation function.
Not only does address reuse degrade the security of your private keys, it also degrades your privacy, as discussed in Chapter 3. Suppose again that John has other outputs to PKH1. If Acme Insurances forces the cafe to reveal that it was John who bought the cookie, Acme would also know that all outputs to PKH1 belong to John. This goes for change outputs, too.
Luckily, the wallets will automate key creation for you, so you usually don’t have to worry about key reuse. Most Bitcoin wallets on the market today use unique addresses for all incoming payments.
5.2.4. Account-based and value-based systems
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.
5.3. Script
I haven’t been totally honest about what a transaction contains. A transaction’s output doesn’t contain a PKH, but part of a small computer program that contains a PKH. This part of the program is called a pubkey script. The input that spends the output contains the other part of this program. This other part, the signature and the public key in John’s transaction, is called a signature script (Figure 94).
OK
, then the payment is authorized to spend the output.This tiny program, written in a programming language called Script,
contains the instructions to Lisa on how to verify that the spending
transaction is authentic. If Lisa performs all the instructions in the
program without errors, and the end result is OK
, then the
transaction is authentic.
The ability to write a computer program inside a transaction is useful for various use cases. We’ll cover several use cases of customized programs throughout this book.
Suppose Lisa wants to verify input 0 of John’s transaction. She’ll run this program from top to bottom. A stack is used to keep track of intermediate calculation results. This stack is like a pile of stuff. You can add stuff on top of the stack, and you can take stuff off the top.
Let’s start: look at Figure 95. The first (top) item in the program is a signature, which is just data. When you encounter ordinary data, you’ll put it on the stack. Lisa puts the signature on the previously empty stack. Then she encounters a public key, which is also just data. She puts that on the stack as well. The stack now contains a signature and a public key, with the public key on top.
The next item in the program is OP_DUP
(Figure 96). This isn’t just
data—this is an operator. An operator makes calculations based on items
on the stack and, in some cases, the transaction being verified. This
specific operator is simple: it means “Copy the top item on the stack
(but keep it on the stack), and put the copy on top.” Lisa follows
orders and copies the public key on the stack. You now have two public
keys and a signature on the stack.
The next item is also an operator, OP_HASH160
(also shown in
Figure 96). This means “Take the top item off the stack and hash it
using SHA256+RIPEMD160, and put the result on the stack.”
Cool. Lisa takes the top public key from the stack, hashes it, and puts the resulting PKH on top of the stack. This happens to be John’s PKH1 because it was John’s public key that Lisa hashed.
The next item is just data (Figure 97): it’s PKH1, which is the rightful recipient of the 8 CT. Lisa puts PKH1 on the stack.
Next up is another operator, OP_EQUALVERIFY
. This means “Take the top
two items from the stack and compare them. If they’re equal, continue to
the next program instruction; otherwise, quit the program with an
error.” Lisa takes the two PKH items from the top of the stack and
verifies that they’re equal. They are equal, which means the public
key John has provided in his transaction’s signature script matches the
PKH that was set as the recipient in the output.
The last operator, OP_CHECKSIG
(Figure 98), means “Verify that the
top public key on the stack and the signature that’s next on the stack
correctly sign the transaction. Put true
or false
on top of the
stack depending on the verification outcome.” Lisa takes John’s
transaction and cleans out all the signature script from all inputs. She
uses the top two items from the stack, which are John’s public key and
his signature, to verify that the signature signs the cleaned
transaction. When John signed this transaction, he did so without any
signature data in the inputs. This is why Lisa must first clean out the
signature script data from the transaction before verifying the
signature. The signature was good, so Lisa puts true
, meaning
OK
, back on the stack.
Look, the program is empty! Nothing is left to do. After running a
program, the top item on the stack reveals whether the spending of the
output is authentic. If true
—OK
—then the spending is authorized. If
false
—not OK
—then the transaction must be declined. Lisa looks at
the top item on the stack, and there’s an OK
. Lisa now knows that
John’s input with index 0 is good (Figure 99).
Lisa does the same checks for the other input, with index 1, of John’s
transaction. If this program also ends with OK
, then the entire
transaction is valid, and she can add the transaction to the
spreadsheet.
5.3.1. Why use a program?
The pubkey script part of the program stipulates exactly what the spending transaction needs to provide to spend the output. The only way to spend an output is to provide a signature script that makes the program finish with an OK on top of the stack.
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:
OP_SHA256 334d016f755cd6dc58c53a86e183882f8ec14f52fb05345887c8a5edd42c87b7 OP_EQUAL
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
Hello!
Run the program to convince yourself that it works and that all signature scripts that don’t contain a correct pre-image fail.
5.3.2. Why signature script and pubkey script?
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
<public key> OP_CHECKSIG
and the signature script like this:
<signature>
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.
5.4. Where were we?
This chapter covers most aspects of transactions. Figure 100 is a reminder from Chapter 1 of how a typical transaction is sent.
We’ve gone through the anatomy of the transaction and are now discussing different ways to authenticate, or “sign,” transactions.
5.5. Fancy payment types
John’s transaction just spent two pay-to-public-key-hash (p2pkh) outputs. But as noted earlier, other payment types are possible—for example, pay-to-hash, where you pay to a SHA256 hash. To spend this output, you need to provide the hash’s pre-image in the spending input’s signature script. We’ll explore some more interesting and useful ways to authenticate transactions.
5.5.1. Multiple signatures
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:
-
If Faiza dies, the money might be lost forever. Ellen and John won’t be able to recover the funds.
-
If Faiza is sloppy with backup, the money might get lost. Again, no one will be able to recover the funds.
-
If Faiza is sloppy with her private key security, the money might get stolen.
-
Faiza might run away with the money.
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:
-
If one of the three keys is stolen, the thief can’t steal the money.
-
If one of the three keys is lost due to sloppy backups or death, then the other two keys are enough to spend the money.
-
Out of the three partners, no single person can singlehandedly run away with the money.
Figure 102 shows a script program that enforces the two-of-three rule.
OP_CHECKMULTISIG
.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
operator, which results in OK this timeOP_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:
-
The coworker’s wallet knows how to make only p2pkh outputs. The wallet must be modified to understand multisignature outputs and include a user interface to make this kind of output understandable to users.
-
A sender usually doesn’t need to know how the recipient’s money is protected. The sender doesn’t care if it’s multisignature, p2pkh, or anything else. They just want to pay.
-
Transactions usually need to pay a fee to be processed (more on this in Chapter 7). This fee generally depends on how big the transaction is, in bytes. A big pubkey script causes the sender to pay a higher fee. This isn’t fair because it’s the recipient who wants to use this fancy, expensive feature. The recipient, not the sender, should pay for this luxury.
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).
5.5.2. Pay-to-script-hash
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.
Old software
What if the person verifying the transaction hasn’t upgraded their software to the bleeding-edge version that supports verifying p2sh payments? The developers made this forward-compatible, meaning old software won’t reject these new transactions.
Let’s pretend the cafe runs old software to verify this transaction in the spreadsheet (Figure 106). Old software will do what it’s always been doing—push the stuff in the signature script and then run the pubkey script.
When the program is finished, the top item on the stack is true
, or
OK
. This means the payment is valid according to this old software.
You might recognize the pubkey script from the earlier example, when you could pay money to a pre-image of a hash. That’s what happened here, too, but with a different cryptographic hash function.
The old software interprets this program as a payment to a hash. Whoever can show a pre-image of this hash gets the money. The actual multisignature program contained in the redeem script never runs.
New software
Suppose the cafe just upgraded its software and wants to verify this transaction again. Let’s see how that happens.
The new software looks at the pubkey script to determine if this transaction is spending a p2sh output. It looks for this pattern:
OP_HASH160 20 byte hash OP_EQUAL
If the pubkey script has this exact pattern—the p2sh pattern—the
software will treat the program differently. First, it will perform the
same seven steps as the old software, shown in Figure 106, but it will
save the stack after step 2. Let’s call this the saved stack. If the
first seven steps result in OK
, then the stack is replaced by the
saved stack; and the top item, redeemScript
, is taken off the stack
(Figure 107).
redeemScript
is taken off the stack.redeemScript
is a data item that contains a program, as previously
described. This program is now entered into the program area and begins
to execute. It executes from now on as if it was an old-style payment
(Figure 108).
It’s important for Lisa that she runs the latest software. If Lisa ran old software, she would verify only that the redeem script hash matches the script hash in the pubkey script. Anyone who happened to know the redeem script—for example, Faiza—would be able to take the money in the spreadsheet. Lisa would gladly confirm that transaction. This would cause problems if any verifying nodes ran new software. Those nodes wouldn’t accept the transaction in the spreadsheet because it’s invalid according to the new rules. The entire spreadsheet would then be invalid and unacceptable for new nodes from that point forward. We’ll discuss this situation more in Chapter 11.
5.5.3. Pay-to-script-hash addresses
Faiza, Ellen, and John have created their two-of-three multisignature redeem script:
2 022f52f2868dfc7ba9f17d2ee3ea2669f1fea7aea3df6d0cb7e31ea1df284bdaec 023d01ba1b7a1a2b84fc0f45a8a3a36cc7440500f99c797f084f966444db7baeee 02b0c907f0876485798fc1a8e15e9ddabae0858b49236ab3b1330f2cbadf854ee8 3 OP_CHECKMULTISIG
They now want people to pay to the redeem script’s SHA256+RIPEMD160 hash:
04e214163b3b927c3d2058171dd66ff6780f8708
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:
-
Print the script hash as is, and inform coworkers that this is a hash of a redeem script. This would expose the coworkers to the unnecessary risk of typing errors, just as with payments to raw PKHs, as discussed in Chapter 3.
-
Base58check-encode the script hash just as in Chapter 3, which would generate an address like
1SpXyW…RMmEMZ
. If this address was printed on the flyers, they would also need to inform users that they must create a p2sh output instead of a normal p2pkh.
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.
05
for p2sh addresses instead of 00
.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.
3
.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:
OP_HASH160 04e214163b3b927c3d2058171dd66ff6780f8708 OP_EQUAL
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.
5.6. More stuff in transactions
We still haven’t covered all the contents of a transaction. A few more pieces of information belong in transactions, including version, lock time, and sequence numbers:
- Version
-
Each transaction has a version. As of this writing, there are two versions: 1 and 2.
- Sequence number
-
A 4-byte number on each input. For most transactions, this is set to its maximum value
ffffffff
. This is an old, disabled feature that’s being repurposed for new functionality. - Lock time
-
A point in time before which the transaction can’t be added to the spreadsheet. If the lock time is 0, the transaction is always allowed to be added to the spreadsheet.
I include this sparse information here for completeness. We’ll discuss these features more in Chapter 9, when you know more about Bitcoin’s fundamentals.
5.7. Rewards and coin creation
You might be wondering where all the cookie tokens come from in the first place. Remember in Chapter 2, when I described how Lisa gets rewarded with 7,200 CT daily? She would insert a new row in the spreadsheet every day, paying 7,200 new CT to herself.
Now she still rewards herself with 7,200 CT per day, but in a slightly different way. Every day she adds a special transaction to the spreadsheet called a coinbase transaction (Figure 111).
The coinbase transaction’s input is called the coinbase. The only way to create new coins is to add a coinbase transaction to the spreadsheet. New coins are created as rewards to Lisa for performing her valuable work.
All transactions can be traced back to one or more coinbase transactions by following the txid references in transaction inputs. The transactions form a transaction graph (Figure 112). They’re interconnected through the txids.
John’s transaction stems from four different coinbase transactions. To verify John’s transaction, you must follow all txids from John’s transaction and verify all the transactions along the way until you’ve reached the four coinbase transactions. This is what the UTXO set helps verifiers with. It keeps track of all already-verified UTXOs. The verifiers only have to follow the txids (usually only one step) until it reaches an output that’s in the UTXO set.
The coinbase transactions must also be verified so there is exactly one coinbase per 24 hours, and each coinbase creates exactly 7,200 new cookie tokens.
5.7.1. Transition from version 4.0
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.
5.8. Trust in Lisa
In this chapter, we’ve formalized the payment process—for example, the transaction from the wallet must be sent as an attachment in an email to Lisa. Lisa can take advantage of this formal process to automate all her work. She writes a computer program that reads transactions from her email inbox and automatically verifies them, maintains the UTXO set, and adds transactions to the spreadsheet. Lisa can relax and just watch her computer program do the job for her. Nice.
But now you may wonder if she’s still worth the 7,200 CT per day in rewards. She doesn’t work actively with verification anymore; she’s just sitting there, twiddling her thumbs. Let’s take a moment to reflect on what we’re rewarding her for. She’s rewarded not to perform boring manual work but to perform correct, honest confirmations of transactions and not censor them. That’s what gives you and your coworkers value. If Lisa writes a computer program to do the heavy lifting, it doesn’t make the payment processing less correct or honest.
Transactions solve the problem with Lisa arbitrarily changing stuff in the spreadsheet. The only things you have to trust Lisa with now are to
- Not censor transactions
-
She must add to the spreadsheet any valid transactions that she receives over email.
- Not revert transactions
-
To revert a transaction is to remove it from the spreadsheet.
If Lisa decides she doesn’t like Faiza, and she also happens to know some of Faiza’s UTXOs, she can refuse to process Faiza’s transactions that try to spend those UTXOs. This means Faiza can’t spend her money. Lisa is censoring Faiza’s transactions.
If Lisa removes a transaction, whose outputs are all unspent, from the spreadsheet, it might be noticed by already-running verifiers. But verifiers that started after the reverting won’t notice because the spreadsheet is still valid according to the rules.
Suppose Lisa reverts John’s transaction from Section 5.2. Lisa removes John’s transaction from the spreadsheet. No one has spent any of the outputs of John’s transaction yet, so the spreadsheet doesn’t contain any transactions that become invalid when John’s transaction is deleted.
An already-running verifier—for example, the cafe—won’t notice because it just watches the spreadsheet for added transactions at the end. It has already verified John’s transaction and updated its private UTXO set. The cafe trusts Lisa to not delete transactions, so it never re-verifies the spreadsheet
Furthermore, suppose a new coworker, Vera, starts to build her own UTXO set from the spreadsheet, which now lacks John’s transaction. This UTXO set will differ from the cafe’s UTXO set. From Vera’s viewpoint, John still has the money and hasn’t paid 10 CT to the cafe. The outputs that John spent in his transaction appear unspent to Vera because they’re in Vera’s UTXO set.
We now have Vera, who thinks John still has the money; Lisa, who deleted the transaction; and the cafe, which thinks it got 10 CT from John. So far, no one has noticed Lisa’s crime. It will remain unnoticed as long as nobody tries to spend an output from John’s transaction. This could be the cafe spending its 10 CT or John spending his 3 CT change.
Let’s say the cafe wants to pay its rent to the company. It needs to spend, among other outputs, the output of John’s transaction. The cafe creates a transaction that spends the output, signs it, and sends it to Lisa. Lisa knows she’s deleted John’s transaction and her crime will now be noticed. If Lisa decides to confirm the cafe’s transaction, then she’ll make the entire spreadsheet invalid, and Vera and all other verifiers will reject the spreadsheet as a whole. Not good. If Lisa decides to reject the transaction, which is the more sensible thing for her to do, the cafe will notice because its transaction never confirms.
When the cafe notices, it can’t prove that John’s transaction was ever in the spreadsheet. Lisa can’t prove that John’s transaction was never in the spreadsheet. It’s word against word. We’ll solve this problem in Chapter 6.
It isn’t obvious why Lisa would delete John’s transaction. Maybe John pays Lisa to do it. It would probably make more sense for Lisa to cheat with her own money instead. Let’s say she buys a cookie in the cafe, and when the cafe has seen the transaction from Lisa to the cafe in the spreadsheet, it gives a cookie to Lisa. Yummy. Then Lisa walks back to her desk and removes her transaction. Now she’s got a cookie and she gets to keep the money. This will, of course, be noticed when the cafe tries to spend the output from the removed transaction or the next time Lisa tries to double-spend the outputs spent by the removed transaction. But as with John’s transaction, it’s word against word. Lisa can claim the transaction was never in the spreadsheet, and the cafe can claim it was. No one can prove anything.
5.9. Recap
Transactions make it impossible for Lisa to steal cookie tokens from others. They solve the problem by making all signatures public in the spreadsheet. Users’ wallets create and sign transactions that Lisa verifies and appends to the spreadsheet.
Transactions have inputs and outputs. An output of a transaction contains the last part of a Script program. When the output is spent, the input that’s spending the output must provide the first part of the program.
Lisa runs the program. If the program ends with OK
, then the
spending of that output is authorized. If the programs of all inputs
in a transaction end with OK
, the entire transaction is valid, and
Lisa adds the transaction to the spreadsheet.
Once the transaction is in the spreadsheet, anyone can make the exact same checks as Lisa did, because she added the transaction to the spreadsheet exactly as she received it. If Lisa makes changes to it, people will notice that the spreadsheet is no longer valid because it contains an invalid transaction. The only things you can’t verify are if transactions are being censored (not added to the spreadsheet) or deleted from the spreadsheet. You have to trust Lisa with these two things for now.
5.9.1. System changes
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.
| Cookie tokens | Bitcoin | Covered in |
|---|---|---|
1 cookie token |
1 bitcoin |
|
The spreadsheet |
The blockchain |
|
Email to Lisa |
A transaction |
|
A row in the spreadsheet |
A transaction |
|
Lisa |
A miner |
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).
| Version | Feature | How |
|---|---|---|
5.0 |
Spend multiple “coins” in one payment |
Multiple inputs in transactions |
Anyone can verify the spreadsheet |
Make the signatures publicly available in the transactions |
|
Sender decides on criteria for spending the money |
Script programs inside transactions |
|
4.0 |
Easy to make payments and create new addresses |
Mobile app “wallet” |
Simplified backups |
HD wallets are generated from a seed. Only the seed, 12 to 24 English words, needs to be backed up. |
|
Creating addresses in insecure environments |
HD wallets can generate public key trees without ever seeing any of the private keys |
|
3.0 |
Safe from expensive typing errors |
Cookie token addresses |
Privacy improvements |
A PKH is stored in the spreadsheet instead of a personal name. |
5.10. Exercises
5.10.1. Warm up
-
Suppose all your money is spread over three UTXOs: one with 4 CT, one with 7 CT, and one with 2 CT. Which of these outputs would you spend if you wanted to buy a cookie for 10 CT? What outputs would your transaction have, and what would their CT values be?
-
What are txids used for in a transaction?
-
Why do you usually need to add a change output in your transaction?
-
Where are the signatures located in a transaction?
-
Why is the public key needed in the input of a transaction if it spends a p2pkh output?
-
Why are the signature scripts of a transaction cleaned when your wallet signs the transaction?
-
Where are the pubkey scripts located in a transaction, and what do they contain?
-
What’s required from a Script program (signature script + pubkey script) for an input to be considered authentic?
-
How can you recognize a p2sh address?
5.10.2. Dig in
-
Suppose you have 100 CT in a single output at index 7 of a transaction. You want to pay 10 CT to the cafe’s p2pkh address @C and 40 CT to Faiza, Ellen, and John’s charity’s p2sh address @FEJ. Construct a single transaction that does this. Please cheat by looking up the exact operators and program templates from this chapter. You don’t have to sign any inputs.
-
The UTXO set contains all UTXOs. Suppose it contains 10,000 UTXOs, and you send a transaction to Lisa that has two inputs and five outputs. How many UTXOs will the UTXO set contain after the transaction has been confirmed?
-
Create a really simple pubkey script that allows anyone to spend the output. What would the signature script of the spending input contain?
-
Create a pubkey script that requires the spender to provide two numbers in the signature script whose sum is 10 in order to spend the money. An operator called
OP_ADD
takes the top two items from the stack and puts back the sum of those items. -
Suppose you run a full node and receive money from Faiza in a confirmed transaction. Can you trust that the money from Faiza is real?
-
A public key is visible in the input that spends a p2pkh output. What’s the drawback of this if you have multiple UTXOs for the same PKH? What can you do to avoid this drawback?
5.11. Summary
-
Transactions have inputs and outputs, so you can spend multiple “coins” and pay multiple recipients in a single transaction.
-
The outputs of transactions are “programmable.” The sender wallet decides what program to put in the output. This dictates what’s needed to spend the money.
-
Anyone can verify the entire spreadsheet because all signatures are public. This greatly reduces the required trust in Lisa.
-
Scripts can be used to enable multisignature capabilities—for example, three-of-seven capabilities. This is great for companies and charities.
-
A new address type, a p2sh address beginning with
3
, is used to simplify the payment process for a lot of fancy payment types, such as multisignatures. -
All transactions descend from one or more coinbase transactions. Coinbase transactions are the only way to create money.
-
Money creation is verified by any coworker to make sure Lisa creates exactly as much as agreed: 7,200 CT per day and halving every four years.
-
Lisa can censor and revert transactions. You still have to trust her with that.
6. The blockchain
This chapter covers
-
Improving spreadsheet security
-
Lightweight (SPV) wallets
-
Reducing wallet bandwidth requirements
In Chapter 5, we discussed transactions that let anyone verify all transactions in the spreadsheet. But there are still things verifiers can’t verify—that Lisa doesn’t remove or censor transactions. We’ll handle censorship resistance in chapters 7 and 8. This chapter examines how to make it impossible for Lisa to remove or replace transactions without also making it obvious that she’s tampered with the transaction history.
Lisa does this by replacing the spreadsheet with a blockchain (Figure 113). The blockchain contains transactions that are secured from tampering through hashing and signing the set of transactions in a clever way. This technique makes it easy to provide cryptographic proof of fraud if Lisa deletes or replaces transactions. All verifiers keep their own copies of the blockchain, and they can fully verify it to ensure that Lisa doesn’t remove already-confirmed transactions.
This chapter also introduces a lightweight wallet, or simplified payment verification (SPV) wallet, that will defer blockchain verification to someone else—a full node—to save bandwidth and storage space. This is possible thanks to the blockchain, but it comes at a cost.
6.1. Lisa can delete transactions
As noted several times before, Lisa can delete transactions. For example, Lisa could buy a cookie from the cafe, eat it, and delete the transaction. Of course, she wouldn’t do this because she’s the most trustworthy person on earth, but not all her coworkers know or believe this. Suppose she does indeed delete a transaction, as Figure 114 shows.
Later, when the cafe notices that the transaction has disappeared, it can’t prove that Lisa’s transaction was ever in the spreadsheet. And Lisa can’t prove it wasn’t there. This situation is troublesome. If it’s word against word, you’re in for a long and costly dispute, possibly involving lawyers, police, Acme Insurances, and private detectives.
How can you prove whether a transaction was confirmed? Lisa needs a way to publish transactions and their ordering such that she can’t tamper with them.
6.2. Building the blockchain
Lisa can delete transactions because no one can prove that the list of all transactions has changed. What if we could change the system to make it provable that she’s fiddled with history?
Among your coworkers, some developers suggest getting rid of the cookie token spreadsheet and replacing it with a blockchain (Figure 115).
In the blockchain, each block references the previous block and has an implicit height that says how far it is from the first block. The first block has height 0, the second block has height 1, and so on. In Figure 115, the chain tip, or last block, of this blockchain is at height 7, meaning the blockchain is 8 blocks long. Every 10 minutes, Lisa puts recent unconfirmed transactions into a new block and makes it available to everybody who’s interested.
The blockchain stores transactions just like the spreadsheet did. But each block also contains a block header to protect the integrity of the contained transactions and the blockchain before it. Let’s say the blockchain in Figure 115 has grown to contain 20 blocks, so the chain tip is at height 19. Figure 116 zooms in on the last few blocks of the blockchain.
Each block contains one or more transactions and a block header. The block header consists of
-
The double SHA256 hash of the previous block’s header
-
The combined hash of the transactions in the block, the merkle root
-
A timestamp of the block’s creation time
-
Lisa’s signature of the block header
The hash of a block header is an identifier for the block, just as a transaction hash, or transaction ID (txid), is an identifier for a transaction. I’ll sometimes refer to the block header hash as the block ID.
The leftmost part of the block header is the block ID of the previous block in the blockchain. This is why it’s called a block_chain_. The previous block-header hashes form a chain of block headers.
The second part from the left is the combined hash of the transactions. This is the merkle root of a merkle tree. We’ll talk about this in later sections of this chapter, but for now, let’s just say that the transactions in the block are hashed together into a single hash value that’s written into the block header. You can’t change any transactions in the block without also changing the merkle root.
The third part from the left is the block’s creation time. This time isn’t exact and doesn’t even always increase from block to block. But it’s roughly accurate.
The fourth part is Lisa’s block signature, which is a stamp of approval from Lisa that anyone can verify. Lisa’s signature proves that she once approved the block, which can be held against her if she tries to cheat. You’ll see how this works shortly. The digital signature in the block header introduces some problems, which we’ll fix in Chapter 7 by replacing these digital signatures with something called proof of work.
6.2.1. Lisa builds a block
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:
-
Create a block template.
-
Sign the block template to make it complete.
-
Publish the block.
Block templates
Lisa starts by creating the block template, a block without a signature (Figure 117).
She collects several transactions to put in the block. She then creates the block header. She creates the previous block ID by hashing the previous block header and putting the result in the new block header. The merkle root is built using the transactions in the block template, and the time is set to the current time.
The first transaction in her block is a coinbase transaction. Blocks’ coinbase transactions create 50 CT per block instead of 7,200 CT as was the case in Chapter 5. The idea is that Lisa produces a new block every 10 minutes, which means her daily 7,200 CT reward is spread out over 144 blocks: there are 144 blocks in 24 hours, and 144*50 CT = 7,200 CT. We’ll talk more about block rewards and the coinbase in Chapter 7.
Signing the block
Before Lisa is finished with the block, she must sign it using a private key only she knows, as shown in Figure 118.
Lisa uses her private block-signing key to sign the block header. This digital signature commits to
-
The previous block ID, which means Lisa’s signature commits to the entire blockchain before this new block
-
The merkle root, which means the signature commits to all transactions in this new block
-
The timestamp
If anything in the blockchain before the new block or in the transactions in this block changes, the block header’s contents will have to change, too; consequently, the signature will become invalid.
The public key corresponding to Lisa’s block-signing key must be made publicly available to all verifiers. The company can publish the public key on its intranet and on a bulletin board at the main entrance. The signature is required because only Lisa should be able to add blocks to the blockchain (for now). For example, John, can create a block and write it to the shared folder. But he won’t be able to sign it correctly because he doesn’t have Lisa’s private key, so no one will accept John’s block.
Using private keys to sign blocks can be a bad idea for two reasons:
-
Lisa’s private key can be stolen. If this happens, the thief can create valid blocks and write them to the shared folder. These blocks’ coinbase transactions will of course pay the block rewards to the thief’s PKH, and not to Lisa’s.
-
The sources containing Lisa’s public key—for example, the bulletin board and the intranet—might be compromised and the public keys replaced by some bad guy’s public key. If this happens, some verifiers will be tricked into accepting blocks signed by a key other than Lisa’s block-signing key. The bad guy can fool some portion of the verifiers. A coworker shouldn’t trust just the note on the bulletin board, because it’s easy for someone to replace the note with a false public key. Coworkers need to get the public key from different sources, such as the bulletin board, the intranet, and by asking fellow workers. A single source is too easily manipulated by bad guys.
The way blocks are signed will change in Chapter 7, from digital signatures to proof of work.
Publishing the block
Once the block is signed, Lisa needs to make it available to verifiers. She uses the shared folder for this, creating a new file, block_20.dat, in which to save her new block (Figure 119).
The block is now published. Anyone interested can read this block from the shared folder. Remember that no one can delete or alter this file due to restrictive permissions on the shared folder. Not even Lisa can change it. There is, however, a system administrator who has full permission to do anything with the shared folder. We’ll get rid of the system administrator in Chapter 8, when I introduce the peer-to-peer network.
Transaction selection
When Lisa builds her block, she picks transactions to include. She can select anything from zero transactions to all unconfirmed transactions. The transaction order isn’t important as long as all transactions spend outputs already present in the blockchain or in the block being built. For example, the block in Figure 120 is perfectly fine.
All transactions in this block spend transactions already in the blockchain, meaning they all reference transactions to the left of themselves. But the block in Figure 121 is invalid.
It’s invalid because a transaction spends an output that’s placed after—to the right of—the spending transaction.
6.2.2. How does this protect us from deletes?
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:
-
The block-header signature is valid. The signature is verified using Lisa’s public key obtained from the bulletin board or intranet.
-
The previous block ID exists. It’s block 20 in this case.
-
All transactions in the block are valid. This uses the same verification approach as in Chapter 5, using a private unspent transaction output (UTXO) set.
-
The combined hash of all transactions matches the merkle root in the block header.
-
The timestamp is within reasonable limits.
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.
Changing anything in a block makes that block and all subsequent blocks invalid. This is because each block header contains a pointer to the previous block—the previous block ID—which will become invalid if the previous block changes.
6.2.3. Why use a blockchain?
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:
-
As the number of transactions grows, the time it takes for Lisa to sign the entire set will increase.
-
The same goes for verifiers—the time it takes to verify a signature increases with the total number of transactions.
-
It’s hard for verifiers to know what’s new since the last signature. This information is valuable when maintaining the UTXO set.
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.
6.3. Lightweight wallets
Coworkers who want to verify the blockchain to make sure they have valid financial information use software that downloads the entire blockchain and keeps a UTXO set up to date at all times. This software needs to run nearly all the time to stay up to date with newly produced blocks. We call this running software a full node. A full node knows about all transactions since block 0, the genesis block. The company and the cafe are typical full-node users. They don’t have to trust someone else with providing them with financial information: they get their information directly from the blockchain. Anyone is free to run this software as they please.
In Chapter 4, I introduced a mobile app that coworkers can use to manage their private keys, as well as send and receive money. This wallet app has now been adapted to the new blockchain system.
Because most wallet users are on a mobile data plan, they don’t want to waste bandwidth on downloading all—for them, uninteresting—block data. The overwhelming majority of the blocks won’t contain any transactions concerning them, so downloading all that data would only make their phones run out of data traffic without providing useful information.
The full-node developers and the wallet developers cooperate to let wallets connect to full nodes over the internet and get relevant block data from those nodes in a way that doesn’t require huge amounts of data traffic. Wallets are allowed to connect to any full node and ask for the data they need.
Suppose John’s wallet contains two addresses, @a and @b, and he wants to receive notifications from a full node about transactions concerning his wallet. He can make a network connection to any of the full nodes—for example, the cafe’s. The wallet and the full node then start talking, as Figure 127 shows.
We’ll examine how this connection is made and how the wallet and node send information between each other more thoroughly in Chapter 8. I only provide a high-level glimpse here, as follows:
-
John’s wallet asks the full node for all block headers since the wallet’s last known block header and all transactions concerning John’s addresses.
-
The cafe’s full node sends all requested block headers to the wallet and at least all transactions concerning John’s addresses.
In step 1, the wallet doesn’t send the exact list of addresses in John’s wallet. This would harm John’s privacy because the cafe would then know that all John’s addresses belong together and could sell that information to Acme Insurances. Not nice. John’s wallet instead sends a filter to the full node. This filter is called a bloom filter. The full node uses it to determine whether to send a transaction to the wallet. The filter tells the full node to send all transactions concerning @a and @b, but it also tells the full node to send transactions that aren’t relevant to John’s wallet, to obfuscate what addresses actually belong to the wallet. Although bloom filters don’t have much to do with the blockchain, I still dedicate a subsection to them here because lightweight wallets use them extensively.
In step 2, transactions and block headers are sent to John’s wallet, but the complete blocks aren’t sent (to save network traffic). John’s wallet can’t use just a transaction and the header to verify that the transaction is in the block. Something more is required: a partial merkle tree that proves that one or more transactions are included in the block.
The two steps are performed as a synchronizing phase just after the wallet connects to the cafe’s full node. After this, as Lisa creates new blocks and the cafe’s full node picks them up, the corresponding block headers are sent to the wallet together with all transactions concerning John’s addresses in roughly the same way as described earlier.
We’ll next discuss bloom filters. Merkle trees are explained in Section 6.5.
6.3.1. Bloom filters obfuscate addresses
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.
Creating the bloom filter
To obfuscate what addresses belong together, John’s wallet creates a bloom filter to send to the full node (Figure 128).
The bloom filter is a sequence of bits, which, as mentioned in Chapter 2, can have the value 0 or the value 1. John’s bloom filter happens to be 8 bits long. Figure 129 illustrates how it was created.
The wallet creates the sequence of bits (the bloom filter) and initializes them with zeroes all over. It then adds all John’s public key hashes (PKHs) to the bloom filter, starting with PKHa, the PKH for @a.
It runs PKHa through the first of the three hash functions. This
hash function results in the value 2
. This value is the index of a
bit in the bloom filter. The bit at index 2 (the third from the left)
is then set to 1
. Then PKHa is run through the second hash
function, which outputs 0
, and the corresponding bit (the first
from the left in the figure) is set to 1
. Finally, the third hash
function outputs 6
, and the bit at index 6 (seventh from the left)
is set to 1
.
Next up is PKHb, which is handled the exact same way. The three hash
functions output 5
, 0
, and 3
. These three bits are all set to
1
. Note that bit 0 was already set by PKHa, so this bit isn’t
modified.
The bloom filter is finished and ready to be sent to the full node.
Use the bloom filter
The full node receives the bloom filter from the wallet and wants to use it to filter transactions to send to the wallet.
Suppose Lisa just published a new block to the shared folder, and the full node has verified the block. The full node now wants to send the new block’s header and all relevant transactions in it to the wallet. How does the full node use the bloom filter to determine what transactions to send?
The block contains three transactions: Tx1, Tx2, and Tx3 (Figure 130).
Tx1 and Tx3 have nothing to do with John’s addresses, but Tx2 is a payment to John’s address @b. Let’s look at how the full node uses the bloom filter (Figure 131).
For each output in a transaction, the node tests whether any PKH
matches the filter. It starts with Tx1, which has a single output to
PKHL. To test whether PKHL matches the filter, it runs PKHL
through the same three hash functions as John’s wallet did when the
filter was created. The hash functions output the indexes 5
, 1
,
and 0
. The bits at index 5
and 0
are both 1
, but the bit at
index 1
is 0
. A 0 bit means PKHL definitely isn’t interesting
to John’s wallet. If John’s wallet was interested in PKHL, the
wallet would have added it to the filter, thus setting bit 1
to
1
. Because PKHL was the only PKH in Tx1, John’s wallet isn’t
interested in this transaction.
The next transaction is Tx2. It contains two PKHs: PKHb and
PKHX. It begins with PKHb. Running this PKH through the hash
functions gives the indexes 5
, 0
, and 3
. All three bits have the
value 1
. This means the node can’t say for sure if the transaction
is interesting to the wallet, but it can’t say that it’s definitely
not interesting. Testing any further PKHs in this transaction is
pointless because the node has already determined that Tx2 should be
sent to the wallet.
The last transaction has two outputs to PKHY and PKHZ. It starts
with PKHY, which happens to point at 2
, 7
, and 4
. Both bits 4
and 7
are 0
, which means PKHY definitely isn’t interesting to the
wallet. Let’s continue with PKHZ, which results in bits 2
, 3
, and
0
. All three bits have the value 1
. This, again, means Tx3 might
be interesting to the wallet, so the node will send this transaction,
too. John’s wallet doesn’t actually contain PKHZ, but the bloom
filter aims to match more than needed to preserve some degree of
privacy. We call this a false positive match.
The result of the bloom filtering is that the node will send Tx2 and Tx3 to the wallet. How the transactions are sent is a totally different story, described in Section 6.5.
| The following is challenging. Feel free to skip this part and jump to Section 6.4. |
The previous description is a simplification of what really happens. You tested only PKHs of the transaction outputs described, which would capture all transactions that pay cookie tokens to any of John’s addresses. But what about transactions that are spending from John’s addresses? We could argue that the full node doesn’t need to send those transactions to the wallet because the wallet already knows about them, given that it created them in the first place. Unfortunately, you do need to send those transactions, for two reasons.
First, it might not be this wallet app that created the transaction. John can have multiple wallet apps that generate addresses from the same seed. For example, do you remember in Chapter 4 how a wallet can be restored from a mnemonic sentence? This sentence can be used by multiple wallet apps at the same time. John might want to make a payment from one of the wallet apps and be notified of the payment in the other wallet app so he can monitor the total balance in that app.
Second, John wants to be notified when the transaction is confirmed. The wallet app might already have the transaction, but it’s still marked as unconfirmed in the app. John wants to know when the transaction has been included in a block, so he needs the node to send him this transaction when it’s in a block.
What the node really tests are the following items (Figure 132):
-
The txid of the transaction
-
All transaction output (TXO) references in the inputs
-
All data items in signature scripts
-
All data items of the outputs
For John’s wallet to be notified of spends, it needs to add either all its public keys to the bloom filter or all its UTXO references.
Throttling privacy and data traffic
The purpose of the bloom filter is to enhance user privacy. The level of privacy can be controlled by tuning the ratio between the number of 1s in the bloom filter and the bloom filter’s size. The more 1s in the bloom filter in relation to the bloom filter’s size, the more false positives. More false positives means the full node will send more unrelated transactions to the wallet. More unrelated transactions means more wasted data traffic but also improved privacy.
Let’s do some back-of-the-envelope calculations. The bloom filter in the earlier example has 8 bits, of which five are 1s. A single hash function’s output has a 5/8 probability of hitting a 1. For a single test, the probability that all three hash functions hit a 1 is then (5/8)3. The probability that a single test is negative—at least one of the three hash functions points to a 0—is then 1 – (5/8)3. The full node will perform several tests on each transaction, typically nine for a transaction with two inputs and two outputs. Let’s check this against the list of tests the full node performs:
-
The txid of the transaction (1)
-
All TXO references in the inputs (2)
-
All data items in signature scripts (public key and signature × 2 = 4)
-
All data items of the outputs (2)
The probability that all nine tests are negative is (1 – (5/8)3)9 ≈ 0.08. So, almost all—92/100—transactions will be sent to the wallet. This shows that having only three 0s of 8 bits in the bloom filter won’t help reduce the data much, but it protects your privacy better.
To get fewer false positives, John’s wallet must use a larger bloom filter so the ratio (number of ones/bloom filter size) decreases.
Let’s define some symbols:
t = Number of tests performed on a transaction (9) p = Probability of a transaction being deemed uninteresting r = Ratio of the number of 1s/bloom filter size
We can generalize our calculation as follows:
Let’s say you only want to get 1/10 of all transactions (given that all transactions are like the previous transaction, with two inputs and two outputs). How big do you have to make the bloom filter?
This calculation means the bloom filter should be about 6/0.23 ≈ 26 bits to get only 1/10 of all transactions. The bloom filter size must be a multiple of 8 bits, so 26 bits isn’t allowed. We can round upward to 32 bits.
Remember that these are rough calculations based on somewhat false assumptions regarding transaction characteristics. We also aren’t considering that the number of 1s in the example isn’t strictly six but can be anywhere from three to six, given that both John’s addresses could have generated the same set of indexes. But this process should help you get an idea of how big a bloom filter must be.
Problems with bloom filters
Bloom filters have been broadly used by many lightweight wallets, but they have issues:
- Privacy
-
A node that receives bloom filters from a lightweight client can, with high precision, determine what addresses belong to a wallet. The more bloom filters collected, the higher the accuracy. See Web resource 14 for details.
- Performance
-
When a full node first receives a bloom filter from a lightweight client, the node needs to scan the entire blockchain for matching transactions. This scanning is processing and disk intensive and can take several minutes, depending on the full node’s hardware. This fact can be used maliciously to attack full nodes so they become unresponsive, in a denial-of-service (DoS) attack.
New Bitcoin Improvement Proposals (BIPs), BIP157 and BIP158, have been proposed that aim to solve these issues, but they haven’t been widely implemented and tested yet. The general idea is to reverse the process so a full node sends a filter to the lightweight wallet for each block. This filter contains information about what addresses the block affects. The lightweight client checks whether its addresses match the filter and, if so, downloads the entire block. The block can be downloaded from any source, not just the full node that sent the filter.
6.4. Where were we?
For the sake of orientation, Figure 133 shows part of what I sketched out in Figure 7 in Chapter 1, where Bob’s wallet was notified of Alice’s payment to Bob.
In the example in this chapter, John has sent a bloom filter to the cafe’s full node to receive only information concerning him. The full node has received a block that contains two transactions that are interesting to John, at least according to John’s bloom filter.
The next thing that happens is that the new block’s header and the potentially interesting transactions are sent to John’s wallet.
6.5. Merkle trees
Now that the full node has determined which transactions to send to the wallet, it needs to send the new block header and all transactions John’s wallet might be interested in.
The full node has determined that transactions Tx2 and Tx3 need to be sent to the wallet. If the node sends only the header and the two transactions, then John’s wallet won’t be able to verify that the transactions belong to the block. The merkle root depends on three transactions, Tx1, Tx2, and Tx3, but the wallet only gets Tx2 and Tx3 from the full node. The wallet can’t re-create the merkle root in the block header. It needs more information to verify that the transactions are included in the block. Remember that you want to save data traffic, so sending all transactions in the block isn’t good enough.
6.5.1. Creating the merkle root
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.
6.5.2. Proving that a transaction is in a block
The full node wants to send Tx2 and Tx3 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 Tx2 and Tx3 are included in the block. But let’s begin with proving only a single transaction, Tx2. We’ll look at a bigger, more complex example later in this chapter.
How can the full node provide proof to the wallet that Tx2 is included in the block? It can provide a partial merkle tree that connects Tx2 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 Tx2 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 Tx2 is in the block by calculating the intermediary hashes toward the root, and verify that the hash of Tx2 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 Tx2 is in the block.
6.5.3. How it really works
| The following describes in detail how to create and verify a partial merkle tree. If you want, you can skip this part and jump to Section 6.6. |
Creating the partial merkle tree
The partial merkle tree is a pruned version of the full merkle tree, containing only the parts needed to prove Tx2 is part of the tree. The full node sends three things to the wallet:
-
The block header
-
The partial merkle tree
-
Tx2
Let’s construct the partial merkle tree. The full node knows the number of transactions in the block, so it knows the merkle tree’s shape. To construct the partial merkle tree, the full node examines the hashes in the merkle tree, starting at the merkle root and moving downward in the tree, left branch first (Figure 139).
The partial merkle tree consists of
-
A number indicating the total number of transactions in the block
-
A list of flags
-
A list of hashes
At each step, you do two things with the current hash, as outlined in the following table:
-
Add the flag to the list of flags. ✘ means there’s nothing interesting in this hash’s branch; ✔ means this branch contains an interesting transaction.
-
If the flag is ✘, or if this hash is an interesting txid, add the hash to the list of hashes.
| Step | Commits to interesting txid? | List of flags | Is flag ✘, or is the hash an interesting txid? | List of hashes |
|---|---|---|---|---|
1 |
yes |
✔ |
no |
- |
2 |
yes |
✔✔ |
no |
- |
3 |
no |
✔✔✘ |
yes |
3 |
4 |
yes |
✔✔✘✔ |
yes |
3 4 |
5 |
no |
✔✔✘✔✘ |
yes |
3 4 5 |
This ordering of the steps is called depth first, meaning you always move downward in the tree as far as you can before moving sideways. But you won’t go down in tree branches that don’t contain any interesting transactions. This is noted in the list of flags as ✘.
Now that the full node has created this partial merkle tree, the node will send the block header and the partial merkle tree to the wallet, and then send the actual transaction Tx2. The block header together with the partial merkle tree are often referred to as a merkle proof.
Verifying the partial merkle tree
The wallet has received a block header, a partial merkle tree, and the transaction Tx2 from the full node. That’s all the wallet needs to verify that Tx2 is indeed included in the block. The goal is to verify that there’s a way to “connect” Tx2 to the merkle root in the block header. It starts with verifying the partial merkle tree (Figure 140).
Use the number of transactions (three) received from the full node to build the merkle tree’s structure. The wallet knows how a merkle tree with three transactions looks.
Use the list of flags and the list of hashes to attach hashes to the merkle tree in depth-first order, as follows.
| Step | Next flag from list | Remaining list of flags | Is flag ✘, or are you at the lowest level? | Attach hash | List of hashes |
|---|---|---|---|---|---|
1 |
✔ |
✔✘✔✘ |
no |
- |
3 4 5 |
2 |
✔ |
✘✔✘ |
no |
- |
3 4 5 |
3 |
✘ |
✔✘ |
yes |
3 |
4 5 |
4 |
✔ |
✘ |
yes |
4 |
5 |
5 |
✘ |
yes |
5 |
The wallet has now attached enough hashes (3, 4, and 5) to the merkle tree to fill in the blanks upward toward the partial merkle tree root. First, the hash of step 2 is calculated from 3 and 4; then the root is calculated from 2 and 5.
Compare the calculated merkle root with the merkle root in the block header—the actual merkle root—and verify that they’re the same. Also, check that the hash of Tx2 is among the list of hashes received from the full node (Figure 141).
If the transaction turns out to match one of the hashes in the partial merkle tree, and if the partial merkle tree root matches the merkle root in the block header, the full node has proven that Tx2 is part of the block.
But the full node wanted to send two transactions from this block. How would the merkle proof look with two transactions? Do you send multiple merkle proofs? No—we’ll leave this as an exercise at the end of this chapter.
Handling thousands of transactions in a block
The block in the previous example contained only three transactions. You didn’t save much space sending the header, the partial merkle tree, and Tx2. You could just as well send all three txids instead of the partial merkle tree—that would be much simpler. But the gains with merkle proofs become more apparent when the number of transactions in a block increases.
Suppose the full node just verified a block containing 12 transactions. It has determined, by testing all transactions against the wallet’s bloom filter, that two of the transactions are potentially interesting to the wallet. Figure 142 shows how this would look.
The full node has to send only the block header, the number 12, 14 flags, and seven hashes. This sums to about 240 bytes, far less data than sending the block header and all 12 txids (about 464 bytes).
Let’s check some rough numbers to see how the merkle proof compares in size to the full block and the simplistic approach of sending all txids as the number of transactions grows (Table 17).
| Number of transactions in block | Block size (bytes) | Size of simple proof (bytes) | Size of merkle proof (bytes) | Length of list of hashes |
|---|---|---|---|---|
1 |
330 |
112 |
112 |
1 |
10 |
2,580 |
400 |
240 |
5 |
100 |
25,080 |
3,280 |
336 |
8 |
1,000 |
250,080 |
32,080 |
432 |
11 |
10,000 |
2,500,080 |
320,080 |
560 |
15 |
100,000 |
25,000,080 |
3,200,080 |
656 |
18 |
Table 17 assumes that all transactions are 250 bytes and that you only want to prove a single transaction. The block size is calculated as the 80-byte block header plus the number of transactions times 250. The simple proof is calculated as the 80-byte block header plus the number of transactions times 32. The merkle proof is calculated as the 80-byte block header plus the length of the list of hashes times 32. Ignore the flags and number of transactions, because they’re negligible.
The merkle proofs don’t grow as fast as the simple proofs, because merkle proofs grow logarithmically with the number of transactions, whereas simple proofs grow linearly with the number of transactions. When the block doubles in size, the merkle proof size roughly increases by a constant term of 32 bytes, whereas the simple proof doubles in size.
6.6. Security of lightweight wallets
Lightweight wallets seem like a nice touch for the cookie token system. They certainly are, but users should be aware of what they’re missing out on compared to full nodes.
Full nodes verify the blockchain’s complete history and know for sure that the money a transaction spends exists and that the signatures are valid.
A lightweight wallet knows the entire chain of block headers. It will verify that Lisa has correctly signed each block header. When the wallet receives a transaction and a merkle proof, it can check that the transaction is contained in the block and that Lisa signed that block. But it can’t verify a lot of other things. For example:
-
That the script programs in the transaction all return “OK,” which usually means verifying the signatures of all inputs
-
That the spent outputs aren’t already spent
-
That it receives all relevant transactions
The lightweight wallet also doesn’t know what rules the full node is following. The full node might have adopted a rule that pays double the reward to Lisa. A typical full node would consider any block that pays too much to Lisa as invalid because that isn’t a rule it signed up for, and would drop the block.
The lightweight wallet needs to trust the full node to verify those things on its behalf and that the full node is following the rules the wallet expects it to follow.
The full node can hide relevant transactions to the wallet. This means the wallet won’t be notified about some incoming or outgoing transactions.
A lightweight wallet gives verification responsibility to the full node it’s connected to. Suppose Lisa produces an invalid block—for example, a block that contains a transaction that spends an output that doesn’t exist. When the full node receives this block, it should verify the block and drop it because it’s invalid. But there might be occasions when the full node, deliberately or accidentally, doesn’t detect the error. Perhaps the cafe is in cahoots with Lisa to fool John—who knows? The cafe and Lisa can, at least temporarily, make John believe he’s received money that he didn’t receive.
John can take at least two measures to reduce the risk of being fooled by a full node:
- Connect to multiple full nodes simultaneously
-
Most lightweight wallets in Bitcoin do this automatically. All full nodes that John’s wallet is connected to must take active part in the conspiracy in order to fool John (Figure 143).
- Connect to a trusted node
-
A trusted node is a full node that John runs himself on a computer he controls (Figure 144). This way, John can use a lightweight wallet on his mobile phone to save data traffic while still being sure he receives correct information from his full node.
The last option is useful if John is concerned some full nodes might adopt rule changes he doesn’t agree with. The only way to be absolutely sure you follow the rules you want is to run your own full node.
6.7. Recap
This chapter has described the blockchain and how it enables full nodes to prove if Lisa has tried to delete or change transactions. The blockchain is a sequence of blocks that are connected through cryptographic hashes.
The merkle root in the block header is the combined hash of all contained transactions. This hash is created by hashing the transactions in a merkle tree structure. Hashes are concatenated pairwise, and the result is hashed to get one level closer to the root.
A full node can prove to a lightweight wallet that a transaction is in a block by sending a merkle proof to the wallet. The merkle proof consists of the block header and a partial merkle tree. The merkle proof grows logarithmically with the number of transactions in the block.
For privacy reasons, wallets don’t want just the transactions they’re actually interested in. To obfuscate what addresses belong to it, the wallet uses bloom filters to subscribe to more transactions than those that are actually interesting. It creates a bloom filter and sends it to the full node.
The full node tests various stuff from the transactions—for example,
PKHs in outputs—using the three hash functions. If any such item hashes
to indexes all containing 1
, then the node will send the transaction.
If not, it won’t send the transaction.
This chapter has solved the issue with deleted or changed transactions. Lisa can’t change the contents of the blockchain without being proven a fraud.
Lisa can still censor transactions. She can refuse to confirm transactions being sent to her. She has ultimate power over what goes into the blockchain and what doesn’t. In Chapter 7, we’ll make it much harder for a single actor like Lisa to make such decisions.
6.7.1. System changes
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.
| Cookie tokens | Bitcoin | Covered in |
|---|---|---|
1 cookie token |
1 bitcoin |
|
The spreadsheet |
The blockchain |
|
Lisa |
A miner |
|
Block signature |
Proof of work |
|
The shared folder |
The Bitcoin network |
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!
| Version | Feature | How |
|---|---|---|
6.0 |
Prevent Lisa from deleting transactions |
Signed blocks in a blockchain |
Fully validating nodes |
Download and verify the entire blockchain. |
|
Lightweight wallet saves data traffic |
Bloom filters and merkle proofs |
|
5.0 |
Spend multiple “coins” in one payment |
Multiple inputs in transactions |
Anyone can verify the spreadsheet |
Make the signatures publicly available in the transactions |
|
Sender decides on criteria for spending the money |
Script programs inside transactions |
6.8. Exercises
6.8.1. Warm up
-
How does a block in the blockchain refer to the previous block?
-
What information does the merkle root commit to?
-
What information does Lisa’s block signature commit to?
-
How are new cookie tokens (or bitcoins) created?
-
What transactions would match a bloom filter containing only 1s (
1
)? -
What stuff from a transaction does the full node test when determining whether to send a transaction to the lightweight wallet? Skip this exercise if you didn’t read the challenging parts on bloom filters.
-
The hash functions used to create the bloom filter aren’t cryptographic hash functions. Why not?
6.8.2. Dig in
-
Draw the structure of a merkle tree of a block with five transactions.
-
Lisa signs all blocks with her block-signing private key. The public key is made public through several sources, such as the intranet and the bulletin board. Name at least one security risk with this scheme. There are mainly two such risks.
-
There are two places where a single person can censor transactions or blocks. Which two places?
-
Suppose Lisa creates a block in the shared folder at the same height as another block. The new block contains the same transactions as the other block except that one transaction is replaced by another transaction spending the same money. She tries to pull off a double spend. Would this be detected by a full node that
-
Hasn’t downloaded the original block yet?
-
Has already downloaded the original block?
-
| Exercises 12–15 require you to have read the hard parts I warned you about earlier in the chapter. |
-
Make a bloom filter of 8 bits of the two addresses @1 and @2, where @1 hashes to the indexes
6
,1
, and7
, and @2hashes to1
,5
, and7
. Then suppose a full node wants to use your bloom filter to decide whether to send the following transaction to the wallet:This image shows the hash function results for different parts of the transaction. Would the full node send this transaction to the lightweight wallet?
-
When we constructed the merkle proof in Section 6.5.2, we only created the proof for a single transaction, Tx2. In this exercise, construct a partial merkle tree for both transactions Tx2 and Tx3. The number of transactions in the block is three.
-
In Section <IP_ADDRESS>, we constructed a partial merkle tree from a block with 12 transactions. What txids does the full node consider interesting?
-
Suppose that you’ve calculated the root of a partial merkle tree, as in the previous exercise. What else do you need to do to verify that a certain transaction is included in this block?
6.9. Summary
-
Transactions are placed in blocks that Lisa signs to hold her accountable if she tries to delete transactions.
-
Each block signature commits to the transactions in that block and all previous blocks so history can’t be tampered with without re-signing the fraudulent block and all subsequent blocks.
-
The transactions in a block are collectively hashed in a merkle tree structure to create a merkle root that’s written in the block header. This makes it possible to create a lightweight wallet.
-
Lightweight wallets save bandwidth but at the cost of reduced security.
-
Lightweight wallet security is reduced because such wallets can’t fully verify a transaction and because a full node can hide transactions from them.
-
The only way to be absolutely sure the block rules are followed is to run your own full node.
-