Exercise 2

Write the merkle_parent_level function.

Exercise 3

Write the merkle_root function.

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 Figure 11-5 has 16 leaves. A light client can create the empty Merkle tree like so:

>>> import math
>>> total = 16
>>> max_depth = math.ceil(math.log(total, 2))  
>>> merkle_tree = []  
>>> for depth in range(max_depth + 1):  
...     num_items = math.ceil(total / 2**(max_depth - depth))  
...     level_hashes = [None] * num_items  
...     merkle_tree.append(level_hashes)  
>>> for level in merkle_tree:
...     print(level)
[None]
[None, None]
[None, None, None, None]
[None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None, None, None, None,\
 None, None, None]

Since we halve at every level, log₂ 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.

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.

There are levels 0 to max_depth in this Merkle tree.

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

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

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

Exercise 5

Create an empty Merkle Tree with 27 items and print each level.

Coding a Merkle Tree

We can now create a MerkleTree class:

class MerkleTree:

    def __init__(self, total):
        self.total = total
        self.max_depth = math.ceil(math.log(self.total, 2))
        self.nodes = []
        for depth in range(self.max_depth + 1):
            num_items = math.ceil(self.total / 2**(self.max_depth - depth))
            level_hashes = [None] * num_items
            self.nodes.append(level_hashes)
        self.current_depth = 0  
        self.current_index = 0

    def __repr__(self):  
        result = []
        for depth, level in enumerate(self.nodes):
            items = []
            for index, h in enumerate(level):
                if h is None:
                    short = 'None'
                else:
                    short = '{}...'.format(h.hex()[:8])
                if depth == self.current_depth and index == self.current_index:
                    items.append('*{}*'.format(short[:-2]))
                else:
                    items.append('{}'.format(short))
            result.append(', '.join(items))
        return '\n'.join(result)

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

We print a representation of the tree.

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

>>> from merkleblock import MerkleTree
>>> from helper import merkle_parent_level
>>> hex_hashes = [
...     "9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
...     "5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
...     "82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
...     "507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308",
...     "a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330",
...     "bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add",
...     "ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836",
...     "457743861de496c429912558a106b810b0507975a49773228aa788df40730d41",
...     "7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a",
...     "b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9",
...     "9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab",
...     "b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638",
...     "b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263",
...     "c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800",
...     "c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2",
...     "f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e",
... ]
>>> tree = MerkleTree(len(hex_hashes))
>>> tree.nodes[4] = [bytes.fromhex(h) for h in hex_hashes]
>>> tree.nodes[3] = merkle_parent_level(tree.nodes[4])
>>> tree.nodes[2] = merkle_parent_level(tree.nodes[3])
>>> tree.nodes[1] = merkle_parent_level(tree.nodes[2])
>>> tree.nodes[0] = merkle_parent_level(tree.nodes[1])
>>> print(tree)
*597c4baf.*
6382df3f..., 87cf8fa3...
3ba6c080..., 8e894862..., 7ab01bb6..., 3df760ac...
272945ec..., 9a38d037..., 4a64abd9..., ec7c95e1..., 3b67006c..., 850683df..., \
d40d268b..., 8636b7a3...
9745f717..., 5573c8ed..., 82a02ecb..., 507ccae5..., a7a4aec2..., bb626766..., \
ea6d7ac1..., 45774386..., 76880292..., b1ae7f15..., 9b74f89f..., b3a92b5b..., \
b5c0b915..., c9d52c5c..., c555bc5f..., f9dbfafc...

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 cleverer 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 exactly 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:
...
    def up(self):
        self.current_depth -= 1
        self.current_index //= 2

    def left(self):
        self.current_depth += 1
        self.current_index *= 2

    def right(self):
        self.current_depth += 1
        self.current_index = self.current_index * 2 + 1

    def root(self):
        return self.nodes[0][0]

    def set_current_node(self, value):  
        self.nodes[self.current_depth][self.current_index] = value

    def get_current_node(self):
        return self.nodes[self.current_depth][self.current_index]

    def get_left_node(self):
        return self.nodes[self.current_depth + 1][self.current_index * 2]

    def get_right_node(self):
        return self.nodes[self.current_depth + 1][self.current_index * 2 + 1]

    def is_leaf(self):  
        return self.current_depth == self.max_depth

    def right_exists(self):  
        return len(self.nodes[self.current_depth + 1]) > \
            self.current_index * 2 + 1

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

We want to know if we are a leaf node.

In certain situations, we won’t have a right child because we may be at the furthest-right 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:

>>> from merkleblock import MerkleTree
>>> from helper import merkle_parent
>>> hex_hashes = [
...     "9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
...     "5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
...     "82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
...     "507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308",
...     "a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330",
...     "bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add",
...     "ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836",
...     "457743861de496c429912558a106b810b0507975a49773228aa788df40730d41",
...     "7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a",
...     "b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9",
...     "9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab",
...     "b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638",
...     "b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263",
...     "c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800",
...     "c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2",
...     "f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e",
... ]
>>> tree = MerkleTree(len(hex_hashes))
>>> tree.nodes[4] = [bytes.fromhex(h) for h in hex_hashes]
>>> while tree.root() is None:  
...     if tree.is_leaf():  
...         tree.up()
...     else:
...         left_hash = tree.get_left_node()
...         right_hash = tree.get_right_node()
...         if left_hash is None:  
...             tree.left()
...         elif right_hash is None:  
...             tree.right()
...         else:  
...             tree.set_current_node(merkle_parent(left_hash, right_hash))
...             tree.up()
>>> print(tree)
597c4baf...
6382df3f..., 87cf8fa3...
3ba6c080..., 8e894862..., 7ab01bb6..., 3df760ac...
272945ec..., 9a38d037..., 4a64abd9..., ec7c95e1..., 3b67006c..., 850683df..., \
d40d268b..., 8636b7a3...
9745f717..., 5573c8ed..., 82a02ecb..., 507ccae5..., a7a4aec2..., bb626766..., \
ea6d7ac1..., 45774386..., 76880292..., b1ae7f15..., 9b74f89f..., b3a92b5b..., \
b5c0b915..., c9d52c5c..., c555bc5f..., f9dbfafc...

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

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

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

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

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 two, as edge cases where there are 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:

>>> from merkleblock import MerkleTree
>>> from helper import merkle_parent
>>> hex_hashes = [
...     "9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
...     "5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
...     "82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
...     "507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308",
...     "a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330",
...     "bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add",
...     "ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836",
...     "457743861de496c429912558a106b810b0507975a49773228aa788df40730d41",
...     "7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a",
...     "b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9",
...     "9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab",
...     "b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638",
...     "b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263",
...     "c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800",
...     "c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2",
...     "f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e",
...     "38faf8c811988dff0a7e6080b1771c97bcc0801c64d9068cffb85e6e7aacaf51",
... ]
>>> tree = MerkleTree(len(hex_hashes))
>>> tree.nodes[5] = [bytes.fromhex(h) for h in hex_hashes]
>>> while tree.root() is None:
...     if tree.is_leaf():
...         tree.up()
...     else:
...         left_hash = tree.get_left_node()
...         if left_hash is None:  
...             tree.left()
...         elif tree.right_exists():  
...             right_hash = tree.get_right_node()
...             if right_hash is None:  
...                 tree.right()
...             else:  
...                 tree.set_current_node(merkle_parent(left_hash, right_hash))
...                 tree.up()
...         else:  
...             tree.set_current_node(merkle_parent(left_hash, left_hash))
...             tree.up()
>>> print(tree)
0a313864...
597c4baf..., 6f8a8190...
6382df3f..., 87cf8fa3..., 5647f416...
3ba6c080..., 8e894862..., 7ab01bb6..., 3df760ac..., 28e93b98...
272945ec..., 9a38d037..., 4a64abd9..., ec7c95e1..., 3b67006c..., 850683df..., \
d40d268b..., 8636b7a3..., ce26d40b...
9745f717..., 5573c8ed..., 82a02ecb..., 507ccae5..., a7a4aec2..., bb626766..., \
ea6d7ac1..., 45774386..., 76880292..., b1ae7f15..., 9b74f89f..., b3a92b5b..., \
b5c0b915..., c9d52c5c..., c555bc5f..., f9dbfafc..., 38faf8c8...

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

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

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

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

We have the left node’s value, but the right child doesn’t exist. This is the rightmost 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 two.

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; it looks like Figure 11-6.

Figure 11-6. Parsed merkleblock

The first six fields are exactly the same as the block header from Chapter 9. The last four fields are the proof of inclusion.

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

def bytes_to_bit_field(some_bytes):
    flag_bits = []
    for byte in some_bytes:
        for _ in range(8):
            flag_bits.append(byte & 1)
            byte >>= 1
    return flag_bits

The ordering for the bytes is a bit strange, but it’s meant to be easy to convert into the flag bits needed to reconstruct the Merkle root.

Exercise 6

Write the parse method for MerkleBlock.

Using Flag Bits and Hashes

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

1. If the node’s value is given in the hashes field (blue box in Figure 11-7), the flag bit is 0.

2. If the node is an internal node and the value is to be calculated by the light client (dotted outline in Figure 11-7), the flag bit is 1.

3. If the node is a leaf node and is a transaction of interest (green box in Figure 11-7), the flag is 1 and the node’s value is also given in the hashes field. These are the items proven to be included in the Merkle tree.

Figure 11-7. Processing a Merkle block

Given the tree from Figure 11-7:

• The flag bit is 1 for the root node (1), since that hash is calculated by the light client.

• The left child, H_ABCDEFGH (2), is included in the hashes field, so the flag is 0.

• From here, we traverse to H_IJKLMNOP (3) instead of H_ABCD or H_EFGH since H_ABCDEFGH represents both those nodes and we don’t need them.

• The right child, H_IJKLMNOP, is also calculated, so it has a flag bit of 1.

• To calculate H_IJKLMNOP, we need the values for H_IJKL and H_MNOP (9). The next node in depth-first order is the left child, H_IJKL (4), which is where we traverse to next.

• H_IJKL is an internal node that’s calculated, so the flag bit is 1.

• From here, we traverse to its left child, H_IJ (5). We will be traversing to H_KL (6) when we come back to this node.

• H_IJ is next in depth-first ordering; its hash is included in the hashes list and the flag is 0.

• H_KL is an internal, calculated node, so the flag is 1.

• H_K (7) is a leaf node whose presence in the block is being proved, so the flag is 1.

• H_L (8) is a node whose value is included in the hashes field, so the flag is 0.

• We traverse up to H_KL, whose value can now be calculated since H_K and H_L are known.

• We traverse up to H_IJKL, whose value can now be calculated since H_IJ and H_KL are known.

• We traverse up to H_IJKLMNOP, whose value we can’t calculate yet since we haven’t been to H_MNOP.

• We traverse to H_MNOP, which is another internal node, so the flag is 1.

• H_MN (10) is another internal node that’s calculated, so the flag is 1.

• H_M (11) is a node whose value is included in the hashes field, so the flag is 0.

• H_N (12) is of interest, so the flag is 1 and its value is in the hashes field.

• We traverse up to H_MN, whose value can now be calculated.

• We traverse up again to H_MNOP, whose value cannot be calculated because we haven’t been to H_OP yet.

• H_OP (13) is given, so the flag is 1 and its hash is the final hash in the hashes field.

• We traverse to H_MNOP, which can now be calculated.

• We traverse to H_IJKLMNOP, which can now be calculated.

• Finally, we traverse to H_{ABCDEFGHIJKLMNOP}, which is the Merkle root, and calculate it!

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

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

There should be seven hashes in the hashes field, in this order:

• H_ABCDEFGH

• H_IJ

• H_K

• H_L

• H_M

• H_N

• H_OP

Notice that every letter is represented in the hashes, A to P. This information is sufficient to prove that H_K and H_N (the green boxes in Figure 11-7) are included in the block.

As you can see from Figure 11-7, the flag bits are given in depth-first order. Anytime we’re given a hash, as with H_ABCDEFGH, we skip its children and continue. In the case of H_ABCDEFGH, we traverse to H_IJKLMNOP instead of H_ABCD. 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 the appropriate flag bits and hashes:

class MerkleTree:
...
    def populate_tree(self, flag_bits, hashes):
        while self.root() is None:  
            if self.is_leaf():  
                flag_bits.pop(0)  
                self.set_current_node(hashes.pop(0))  
                self.up()
            else:
                left_hash = self.get_left_node()
                if left_hash is None:  
                    if flag_bits.pop(0) == 0:  
                        self.set_current_node(hashes.pop(0))
                        self.up()
                    else:
                        self.left()  
                elif self.right_exists():  
                    right_hash = self.get_right_node()
                    if right_hash is None:  
                        self.right()
                    else:  
                        self.set_current_node(merkle_parent(left_hash,
                        right_hash))
                        self.up()
                else:  
                    self.set_current_node(merkle_parent(left_hash, left_hash))
                    self.up()
        if len(hashes) != 0:  
            raise RuntimeError('hashes not all consumed {}'.format(len(hashes)))
        for flag_bit in flag_bits:  
            if flag_bit != 0:
                raise RuntimeError('flag bits not all consumed')

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

For leaf nodes, we are always given the hash.

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 do this.

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

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

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) node’s value.

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

We check that the right node exists.

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

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

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.

All hashes must be consumed or we got bad data.

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