Skip to content

Latest commit

 

History

History
486 lines (370 loc) · 24.4 KB

ch11.asciidoc

File metadata and controls

486 lines (370 loc) · 24.4 KB

Simplified Payment Verification

The one block header field that we didn’t investigate much in [chapter_blocks] is the Merkle Root. In order to understand what makes the Merkle Root useful, we first have to learn about Merkle Trees and what properties they have. In this chapter, we’re going to learn exactly what a Merkle Root is. This will be motivated by something called a Proof of Inclusion.

Motivation

For a device that doesn’t have much disk space, bandwidth or computing power like your phone, it’s expensive to store, receive and validate the entire blockchain. As of this writing, the entire Bitcoin blockchain is around 200GB, which is more than many phones can store, can be very difficult to download efficiently and will certainly tax the CPU. If the entire blockchain cannot be put on the phone, what else can we do? Is it possible to create a Bitcoin wallet on a phone without having all the data?

For any wallet, there are two scenarios that we’re concerned with:

  1. Paying someone

  2. Getting paid by someone

If you are paying someone with your Bitcoin wallet, it is up to the person receiving your Bitcoins to verify that they’ve been paid. Once they’ve verified that the transaction has been included in a block sufficiently deep, the other side of the trade, or the good or service will be given to you. Once you’ve sent the transaction to the other party, there really isn’t anything for you to do than wait until you receive whatever it is you’re exchanging the Bitcoins for.

When getting paid Bitcoins, however, we have a dilemma. If we are connected and have the full blockchain, we can easily see when the transaction is in a sufficiently deep block at which point we’d give them our goods or services. If we don’t have the full blockchain, as with a phone, what can we do?

The answer lies in the Merkle Root field from the Block header that we saw in [chapter_blocks]. As we saw in the last chapter, we can download the Block headers and verify that they meet the Bitcoin consensus rules. In this chapter we’re going to work towards getting proof that a particular transaction is in a block that we know about. Since the block header is secured by proof-of-work, a transaction with a Proof of Inclusion in that block means at a minimum, there was a good deal of energy spent to produce that block. This means that the cost to deceive you would be at least the cost of the proof-of-work for the block. The rest of this chapter goes into what the Proof of Inclusion is and how to verify it.

Merkle Tree

A Merkle Tree is a computer science structure designed for efficient proofs of inclusion. The prerequisites are an ordered list of items and a cryptographic hash function. In our case, the ordered list of items are transactions in a block and the hash function, hash256. To construct the Merkle Tree, we follow this algorithm:

  1. Hash all the items of the ordered list with the provided hash function

  2. If there is exactly 1 hash, we are done

  3. If there is an odd number of hashes, we duplicate the last hash in the list and add it to the end so that we have an even number of hashes.

  4. We pair the hashes in order and hash the concatenation to get the parent level which should have half the number of hashes.

  5. Go to 2.

The idea is to come to a single hash that "represents" the entire ordered list. Visually, a Merkle Tree looks like Merkle Tree:

Merkle Tree
Figure 1. Merkle Tree

The bottom row is what we call the leaves of the tree. All other nodes besides the leaves are called internal nodes. The leaves get combined to produce its parent level (HAB and HCD) and when we calculate the parent level of that, we get the Merkle Root.

We’ll go through each part of this process below.

Warning
Be Careful With Merkle Trees!

There was a vulnerability in Bitcoin 0.4-0.6 which is detailed in CVE-2012-2459. There was a Denial of Service vector due to the duplication of the last item in Merkle Trees, which caused some nodes to invalidate blocks even if they were valid.

Merkle Parent

Given two hashes, we produce another hash that represents both of them. As they are ordered, we will call the two hashes the left hash and the right hash. The hash of the left and right hashes is what we call the parent hash. To clarify, here’s the formula for the parent hash:

H = Hashing function, P = Parent Hash, L = Left Hash, R = Right Hash

P=H(L||R)

Note the || symbol denotes concatenation.

Here’s how we can code this process in Python:

link:code-ch11/examples.py[role=include]

The reason why we hash the concatenation to get the parent is because we can provide a Proof of Inclusion. Specifically, we can show that L is represented in the parent, P, by revealing R. That is, if we want proof L is represented in P, the producer of P can show us R and let us know that L is the left child of P. We can then combine L and R to produce P and have proof that L was used to produce P. If L is not represented in P, being able to provide R would be the equivalent to providing a hash pre-image, which we know is very difficult. This is what we mean by a Proof of Inclusion.

Merkle Parent Level

Given an ordered list of more than two hashes, we can calculate the parents of each pair, or what we call the Merkle Parent Level. If we have an even number of hashes, this is straightforward, as we can simply pair them up in order. If we have an odd number of hashes, then we need to do something as we have a lone hash at the end. We can solve this by duplicating the last item.

For a list like [A, B, C] what we add C again to get [A, B, C, C]. Now we can calculate the Merkle Parent of A and B and calculate the Merkle Parent of C and C to get:

[H(A||B), H(C||C)]

Since the Merkle Parent always consists of two hashes, the Merkle Parent Level always has exactly half the number of hashes, rounded up.

link:code-ch11/examples.py[role=include]

  1. We add the last hash on the list, hashes[-1], to the end of hashes to makes the length of hashes even.

  2. This is how we skip by two in Python. i will be 0 the first time through the loop, 2 the second, 4 the third and so on.

This code results in a new list of hashes that correspond to the Merkle Parent Level

Merkle Root

The process of getting the Merkle Root is to calculate successive Merkle Parent Levels until we get a single hash. If, for example, we have items A through G (7 items), we calculate the Merkle Parent Level:

[H(A||B), H(C||D), H(E||F), H(G||G)]

Then we calculate the Merkle Parent Level again:

[H(H(A||B)||H(C||D)), H(H(E||F)||H(G||G))]

We are left with just 2 items, where we calculate the Merkle Parent Level one more time:

H(H(H(A||B)||H(C||D))||H(H(E||F)||H(G||G)))

Since we are left with exactly one hash, we are done. The final single hash is called the Merkle Root. Each level will halve the number of hashes, so doing this process over and over will eventually result in a single item or the Merkle Root.

link:code-ch11/examples.py[role=include]

  1. We loop until there’s 1 hash left.

  2. We’ve exited the loop so there should only be 1 item

Merkle Root in Blocks

The Merkle Root in Blocks should be pretty straightforward, but due to Endian-ness issues, this turns out to be tricky. Specifically, we use Little-Endian ordering for the leaves for the Merkle Tree. After we calculate the Merkle Root, we use Little-Endian ordering again.

In practice, this means reversing the leaves before we start and reversing the root at the end.

link:code-ch11/examples.py[role=include]

  1. We reverse each hash before we begin using a Python list comprehension

  2. We reverse the root at the end.

We want to calculate Merkle Roots for a Block, so we add a tx_hashes parameter.

link:code-ch11/block.py[role=include]

  1. We now allow the transaction hashes to be set as part of the initialization of the block. The transaction hashes have to be ordered.

As a full node, if we are given all of the transactions, we can calculate the Merkle Root and check that the Merkle Root is what we expect.

Using a Merkle Tree

Now that we know how a Merkle Tree is constructed, we can create and verify Proofs of Inclusion. Light nodes can get proofs that transactions of interest were included in a block without having to know all the transactions of a block (Merkle Proof).

Merkle Proof
Figure 2. Merkle Proof

Say that a light client has two transactions that are of interest, which would be the hashes represented by the green boxes, HK and HN above. A full node can construct a Proof of Inclusion by sending us all of the hashes marked by blue boxes, HABCDEFGH, HIJ, HL, HM and HOP. The light client would then perform these calculations:

  • HKL = merkle_parent(HK, HL)

  • HMN = merkle_parent(HM, HN)

  • HIJKL = merkle_parent(HIJ, HKL)

  • HMNOP = merkle_parent(HMN, HOP)

  • HIJKLMNOP = merkle_parent(HIJKL, HMNOP)

  • HABCDEFGHIJKLMNOP = merkle_parent(HABCDEFGH, HIJKLMNOP)

The Merkle Root is HABCDEFGHIJKLMNOP, which we can then be checked against the block header whose proof-of-work has been validated.

Note
How secure is an SPV proof?

The full node can send a limited amount of information about the block and the light client can recalculate the Merkle Root, which can then be verified against the Merkle Root in the block header. This does not guarantee that the transaction is in the longest blockchain, but it does assure the light client that the full node would have had to spend a lot of hashing power or energy creating a valid proof-of-work. As long as the reward for creating such a proof-of-work is greater than the amounts in the transactions, the light client can at least know that the full node has no clear economic incentive to lie.

Since block headers can be requested from multiple nodes, light clients have a way to verify if one node is trying to show them block headers that are not the longest. It only takes a single honest node to invalidate 100 dishonest ones since proof-of-work is objective. Therefore, isolation of a light client (that is, control of who the light client is connected to) is required to deceive in this way. The security of SPV requires that there be lots of honest nodes on the network.

In other words, light client security is based on a robust network of nodes and the economic cost of producing proof-of-work. For small transactions relative to the block subsidy (currently 12.5 BTC), there’s probably little to worry about. For large transactions (say 100 BTC), the full nodes may have economic incentive to deceive you. Transactions that large should generally be validated using a full node.

Merkle Block

When a full node sends a Proof of Inclusion, there are two pieces of information that need to be included. First, the light client needs the Merkle Tree structure and second, the light client needs to know which hash is at which position in the Merkle Tree. Once both pieces of information are given, the light client can reconstruct the partial Merkle Tree to reconstruct the Merkle Root and validate the Proof of Inclusion. A full node communicates these two pieces of information to a light client using a Merkle Block.

To understand what’s in a Merkle Block, we need to understand a bit about how a Merkle Tree or more generally, Binary Trees, can be traversed. In a binary tree, nodes can be traversed breadth-first or depth-first. Breadth-first traversal would go level by level like Breadth-First Ordering:

Breadth First
Figure 3. Breadth-First Ordering

The breadth-first ordering starts at the root and goes from root to leaves, level by level, left to right.

Depth-first ordering is a bit different and looks like Depth-First Ordering:

Depth First
Figure 4. Depth-First Ordering

The depth-first ordering starts at the root, traverses the left side at each node before the right side.

Merkle Proof
Figure 5. Merkle Proof

In a Proof of Inclusion (see Merkle Proof), the full node sends the green boxes, HK and HN along with the blue boxes HABCDEFGH, HIJ, HL, HM and HOP. The location of each hash is reconstructed using depth-first ordering from some flags. The process of reconstructing the tree is what we describe next.

Merkle Tree Structure

The first thing a light client does is create the general structure of the Merkle Tree. Because Merkle Trees are built from the leaves upward, the only thing a light client needs is the number of leaves that exist to know the structure. The tree from Merkle Proof has 16 leaves. A light client can create the empty Merkle Tree like so:

link:code-ch11/examples.py[role=include]

  1. Since we halve at every level, log2 of the number of leaves is how many levels there are in the Merkle Tree. Note we round up using math.ceil as we round up for halving at each level. We could also be clever and use len(bin(total))-2.

  2. The Merkle Tree will hold the root level at index 0, the level below at index 1 and so on. In other words, the index is the "depth" from the top.

  3. There are levels 0 to max_depth in this Merkle Tree.

  4. At any particular level, the number of nodes is the number of total leaves divided by 2 for every level above the leaf level.

  5. We don’t know yet what any of the hashes are, so we set them to None

  6. Note merkle_tree is a list of lists of hashes, or a 2-dimensional array.

Coding a Merkle Tree

We create a MerkleTree class:

link:code-ch11/merkleblock.py[role=include]

  1. We keep a pointer to a particular node in the tree, which will come in handy later.

  2. We print a representation of the tree.

Now that we have an empty tree, we can go about fill it to calculate the Merkle Root. If we had every leaf hash, getting the Merkle Root would look like this:

link:code-ch11/examples.py[role=include]

This fills the tree and gets us the Merkle Root. However, the message from the network may not be giving us all of the leaves. The message might contain some internal nodes as well. We need a more clever way to fill the tree.

Tree traversal is going to be the way we do this. We can do a depth-first traversal and only fill in the nodes that we can calculate. To traverse, we need to keep track of where in the tree we are. The properties self.current_depth and self.current_index do this.

We need methods to traverse the Merkle Tree. We’ll also include other useful methods.

class MerkleTree:
...
link:code-ch11/merkleblock.py[role=include]

  1. We want the ability to set the current node in the tree to some value.

  2. We will want to know if we are a leaf node.

  3. In certain situations, we won’t have a right child because we may be at the right-most node of a level whose child level has an odd number of items.

We have Merkle Tree traversal methods left, right and up. Let’s use these methods to populate the tree via depth-first traversal:

link:code-ch11/examples.py[role=include]

  1. We traverse until we calculate the Merkle Root. Each time through the loop, we are at a particular node.

  2. If we are at a leaf node, we already have that hash, so we don’t need to do anything but go back up.

  3. If we don’t have the left hash, then we calculate the value first before calculating the current node’s hash.

  4. If we don’t have the right hash, we calculate the value first calculating the current node’s hash. Note we already have the left one due to the depth-first traversal.

  5. We have both the left and the right hash so we calculate the Merkle Parent value and set that to the current node. Once set, we can go back up.

This code will only work when the number of leaves is a power of 2 as edge cases where there’s an odd number of nodes on a level are not handled.

We handle the case where the parent is the parent of the rightmost node on a level with an odd number of nodes:

link:code-ch11/examples.py[role=include]

  1. If we don’t have left node’s value, we traverse to the left node since all internal nodes are guaranteed a left child.

  2. We check first if this node has a right child. This is true unless this node happens to be the right-most node and the child level has an odd number of nodes.

  3. If we don’t have the right node value, we traverse to that node.

  4. If we have both the left and the right node values, we calculate the current node value using merkle_parent.

  5. We have the left node value, but the right child doesn’t exist. This is the right-most node of this level so we combine the left value twice.

We can now traverse the tree for the number of leaves that aren’t powers of 2.

Merkle Block Command

The full node communicating a Merkle Block sends all the information needed to verify that the interesting transaction is in the Merkle Tree. The merkleblock network command is what communicates this information and looks like Parsed merkleblock:

merkleblock command
Figure 6. Parsed merkleblock

The first 6 fields are exactly the same as the block header from [chapter_blocks]. The last 4 fields are the Proof of Inclusion.

The number of transactions field is how many leaves this particular Merkle Tree will have. This allows a light client to construct an empty Merkle Tree. The hashes field are the blue and green boxes from Merkle Proof. Since the number of hashes in the hashes field is not fixed, it’s prefixed with how many there are. Lastly, the flags field give information about where the hashes go within the Merkle Tree. The flags are parsed using bytes_to_bits_field to convert to a list of bits (1’s and 0’s):

link:code-ch11/helper.py[role=include]

The ordering for the bytes are a bit strange, but meant to be easy to convert into the flag bits needed to reconstruct the Merkle Root.

Using Flag bits and Hashes

The flag bits inform where the hashes go using depth-first ordering.

The rules for the flag bits are:

  1. If the node’s value is given in the hashes field (blue box in the Processing a Merkle Block), the flag bit is 0.

  2. If the node’s value is an internal node and the value is to be calculated by the light client (dotted outline in the Processing a Merkle Block), the flag bit is 1.

  3. If the node is a leaf node and is a transaction of interest (green box in the Processing a Merkle Block), the flag is 1 and also given in the hashes field. These are the items in the Merkle Tree being proven to be included.

Merkle Blocks and Hashes
Figure 7. Processing a Merkle Block

Given a tree from Processing a Merkle Block, the flag bit is 1 for the root node (1), since that hash is calculated by the light node. The left child, HABCDEFGH (2), is included in the hashes field, so the flag is 0. From here, we traverse to HIJKLMNOP instead of HABCD or HEFGH since HABCDEFGH represents both those nodes and we don’t need them. We don’t need to traverse any of the descendants of HABCDEFGH and go straight to HIJKLMNOP instead.

The right child, HIJKLMNOP (3) is also calculated so has a flag bit of 1. To calculate HIJKLMNOP, we need the values for HIJKL (4) and HMNOP (9). The next node in depth-first order is the left child, HIJKL (4), which is where we traverse to next. HIJKL is an internal node that’s calculated, so the flag bit is 1. From here, we traverse to its left child HIJ (5). We will be traversing to HKL (6) when we come back to this node. HIJ (5) is next in depth-first ordering and that’s hash is included in the hashes list and the flag is 0. HKL (6) is an internal, calculated node so the flag is 1. HK (7) is a leaf node whose presence in the block is being proved so the flag is 1. HL (8) is a node whose value is included in the hashes field so the flag is 0. We traverse up to HKL whose value can now be calculated since HK and HL are known. We traverse up to HIJKL whose value can now be calculated since HIJ and HKL are known. We traverse up to HIJKLMNOP whose value we can’t calculate yet since we haven’t been to HMNOP. We traverse to HMNOP (9), which is another internal node so the flag is 1. HMN (10) is another internal node that’s calculated, so the flag is 1. HM (11) is a node whose value is included in the hashes field, so the flag is 0. HN (12) is of interest, so the flag is 1 and its value is in the hashes field. We traverse up to HMN whose value can now be calculated. We traverse up again to HMNOP, whose value can not be calculated because we haven’t been to HOP yet. HOP (13) is given, so the flag is 1 and its hash is the final hash in the hashes field. We traverse to HMNOP which can now be calculated. We traverse to HIJKLMNOP which can now be calculated. Finally, we traverse to HABCDEFGHIJKLMNOP which is the Merkle Root and calculate it!

The flag bits for nodes (1) - (13) are:

1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0

There should be 7 hashes in the hashes field in this order:

  • HABCDEFGH

  • HIJ

  • HK

  • HL

  • HM

  • HN

  • HOP

Notice that every letter is represented in the hashes above, A-P. This information is sufficient to prove that HK and HN (green boxes in Processing a Merkle Block) are included in the block.

As you can see from Processing a Merkle Block, the flag bits are given in depth-first order. Anytime we’re given a hash, as with HABCDEFGH, we skip its children and continue. In the case of HABCDEFGH, we traverse to HIJKLMNOP instead of HABCD. Flag bits are a clever mechanism to encode which nodes have which hash value.

We can now populate the Merkle Tree and calculate the root, given appropriate flag bits and hashes.

class MerkleTree:
...
link:code-ch11/merkleblock.py[role=include]

  1. The point of populating this Merkle Tree is to calculate the root. Each loop iteration processes one node until the root is calculated.

  2. For leaf nodes, we are always given the hash.

  3. flag_bits.pop(0) is a way in Python to dequeue the next flag bit. We may want to keep track of which hashes are of interest to us by looking at the flag bit, but for now, we don’t.

  4. hashes.pop(0) is how we get the next hash from the hashes field. We need to set the current node to that hash.

  5. If we don’t have the left child value, there are two possibilities. This node’s value may be in the hashes field or this node’s value might need calculation.

  6. The next flag bit tells us whether we need to calculate this node or not. If the flag bit is 0, the next hash in the hashes field is this node’s value. If the flag bit is 1, we need to calculate the left (and possibly the right)

  7. We are guaranteed that there’s a left child, so traverse to that node and get its value.

  8. We check that the right node exists.

  9. We have the left hash, but not the right. We traverse to the right node to get its value.

  10. We have both the left and the right node values, so we calculate their Merkle Parent to get the current node’s value.

  11. We have the left node’s value, but the right does not exist. In this case, according to Merkle Tree rules, we calculate the Merkle Parent of the left node twice.

  12. All hashes must be consumed or we got bad data.

  13. All flag bits must be consumed or we got bad data.

Conclusion

Simplified Payment Verification is useful but not without some significant downsides. The full details are outside the scope of this book, but despite the programming being pretty straightforward, most light wallets do not use SPV and trust data from the wallet vendor servers. The main drawback of SPV is that the nodes you are connecting to know something about the transactions you are interested in. That is, you lose some privacy by using SPV. This will be covered more in detail in the next chapter as we make Bloom Filters to tell nodes what transactions we are interested in.