The one field that we didn’t investigate much in the Chapter 9 is the Merkle Root field. In order to understand why it’s useful, we have to learn a few things about what Merkle Trees are 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.
For a device that doesn’t have much hard drive space, like your phone, it’s hard to store the entire blockchain. As of this writing, the entire Bitcoin blockchain is around 170GB, which is a lot more than many phones can store. 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:
-
Paying someone
-
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, they’ll give you the good or service you are expecting in return. Once you’ve sent the transaction to the other party, there really isn’t anything for you to do than wait until they give you what you were exchanging the Bitcoins for.
When getting paid Bitcoins, however, we have a dilemma. If we are connected and have the full blockchain, we don’t need to worry as we can observe that the transaction paying us is in a sufficiently buried 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?
It turns out that the answer lies in the Merkle Root field from the block header that we saw in Chapter 9. As we saw in the last chapter, we can download the block headers and verify that they meet the 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, we know that a proof of inclusion in that block means at a minimum, the person creating the block had to expend a good deal of energy to produce it. The rest of this chapter goes into what the proof of inclusion looks like and how to verify it.
A Merkle Tree is a computer science structure designed for efficient proofs of inclusion. The prerequisite is an ordered list of items and a hash function. In our case, transactions and double_sha256 are what we use. To construct the Merkle Tree, we follow this algorithm:
-
Hash all the items of the ordered list with the provided hash function
-
If there is exactly 1 hash, we are done
-
If there is an odd number of hashes, we add a copy of the last hash in the list to the end so that we have an even number.
-
We pair the hashes in order and hash the concatenation to get the parent level. We should have half the number of hashes as before.
-
Go to 2.
The idea is to come to a single hash that represents all of the hashes. The gist of getting the Merkle Tree looks like this:
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.
Given two hashes, we need some way to 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. Tho combination, we call the parent hash. The formula for getting the parent is pretty simple:
H = Hashing function, P = Parent Hash, L = Left Hash, R = Right Hash
P=H(L||R)
Note the || symbol is typically used to denote concatenation.
The actual calculation in Python is relatively straightforward:
>>> from helper import double_sha256
>>> hash1 = bytes.fromhex('c117...')
>>> hash2 = bytes.fromhex('c131...')
>>> parent = double_sha256(hash1 + hash2)
>>> print(parent.hex())
8b30c5ba100f6f2e5ad1e2a742e5020491240f8eb514fe97c713c31718ad7ecdAt this point, it’s important to note that we can show that L is included in the parent, P, by revealing R. That is, if someone wanted to prove to us that L was used to produce P, they would 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. This is the most basic proof-of-inclusion.
Given an ordered list of more than two hashes, we can calculate an entire list of parents, 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 else as we have a lone hash at the end.
The Merkle Tree solution is to simply duplicate the last item. So, for a list like [A, B, C] what we do is add C again to get [A, B, C, C]. At this point, we can calculate the merkle parent of A and B and calculate the merkle parent of C and C to get:
Note that since the Merkle Parent always consists of two hashes, we end up with exactly half the number of hashes before, rounded up. The rounding up is because an odd number of hashes is expanded to be one more.
>>> from helper import merkle_parent
>>> hashes = [...]
>>> if len(hashes) % 2 == 1:
... hashes.append(hashes[-1]) # (1)
...
>>> parent_level = []
>>> for i in range(0, len(hashes), 2): # (2)
... parent = merkle_parent(hashes[i], hashes[i+1])
... parent_level.append(parent)
>>> for item in parent_level:
... print(item.hex())
8b30c5ba100f6f2e5ad1e2a742e5020491240f8eb514fe97c713c31718ad7ecd
7f4e6f9e224e20fda0ae4c44114237f97cd35aca38d83081c9bfd41feb907800
3ecf6115380c77e8aae56660f5634982ee897351ba906a6837d15ebc3a225df0-
This will add the last hash on the list (hashes[-1]) to the end of
hashes. This makes the length ofhasheseven. -
This is how we skip by two in Python.
iwill be 0 the first time through the loop, 2 the second, 4 the third and so on.
This will give us a new list of hashes that correspond to the Merkle Parent Level
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, we combine to get the parent level:
Then we combine to get the parent level again:
We are left with just 2 items, which we combine one more time:
H(H(A||B)||H(C||D))||H(H(E||F)||H(G||G))
The final hash is called the Merkle Root. As each level will halve the number of hashes, this will result in a single item eventually.
>>> from helper import merkle_parent_level
>>> hashes = [...]
>>> current_hashes = hashes
>>> while len(current_hashes) > 1: # (1)
... current_hashes = merkle_parent_level(current_hashes)
...
>>> print(current_hashes[0].hex()) # (2)
acbcab8bcc1af95d8d563b77d24c3d19b18f1486383d75a5085c4e86c86beed6-
We loop until there’s 1 hash left.
-
We’ve exited the loop so there should only be 1 item
The way we calculate the merkle root in Blocks should be pretty straightforward, but due to endian-ness issues, this turns out to be a bit counterintuitive. Specifically, we have to calculate the hash of a transaction and use the little-endian ordering as the leaves for the Merkle Tree. After we calculate the Merkle Root, we have to again interpret that in little-endian in order to compare against the Merkle Root stored in the block.
In practice, this simply means reversing the hash before we start and reversing the hash at the end.
>>> from helper import merkle_root
>>> tx_hashes = [...]
>>> hashes = [h[::-1] for h in tx_hashes] # (1)
>>> print(merkle_root(current_level)[::-1].hex()) # (2)
654d6181e18e4ac4368383fdc5eead11bf138f9b7ac1e15334e4411b3c4797d9-
This reverses each hash before we begin using a list comprehension
-
This reverses the root at the end
To make this calculatable for a Block, we have to adjust the class a bit:
class Block:
def __init__(self, version, prev_block, merkle_root, timestamp, bits, nonce, tx_hashes=None): # (1)
self.version = version
self.prev_block = prev_block
self.merkle_root = merkle_root
self.timestamp = timestamp
self.bits = bits
self.nonce = nonce
self.tx_hashes = tx_hashes-
We now allow the transaction hashes to be set as part of the initialization of the block. The hashes would have to be in order.
As a full node, if we are given all of the transaction hashes, we can now calculate the merkle root and check that the merkle root is what we expect.
Now that we know how a Merkle Tree is constructed, we can now utilize it to get a proof-of-inclusion. For nodes that don’t have the entire blockchain, they can get proofs that certain transactions were included in a block without having to know all the transactions of a block. The essence of how we can do this is the following.
Say that we have two transactions that we are interested in, which would be the hashes marked by green boxes, HK and HN above. A full node can to prove to us that these transactions were a part of the block by sending us all of the hashes marked by blue boxes, HABCDEFGH, HIJ, HL, HM and HOP. We 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 check against the block header whose proof-of-work we’ve already validated.
The full node can send us a limited amount of information about the block and the light node can recalculate the merkle root, which can then be verified against the block header. This does not guarantee that the transaction is in a block, but it does assure the light node that the full node would have had to spend a lot of hashing power and thus energy creating a valid proof-of-work. As long as the reward for creating such aproof-of-work is greater than the amounts in the transactions, the light node can at least know that the full node has no clear economic incentive to lie.
Indeed, since the block header can be requested from multiple nodes, light nodes have an easy 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, it’s not easy to isolate a light node enough to be able to deceive in this way. This, of course, assumes that there are lots of nodes on the network in the first place and that a good number of them are being honest.
In other words, light client security is based on a robust network of nodes and a little bit of game theory based on econmic incentives. For a transaction up to the block reward, (12.5 BTC as of this writing), there’s very little to worry about. For large transactions (say 1000 BTC or 80x the mining award), the full nodes, if they’re controlled by your counterparty, may have economic incentive to deceive you. Transactions that large should generally be done using a full node.
The full node needs to send the information about the tree structure and which hash is at which position in the Merkle Tree. A light node then needs to be able to reconstruct the partial Merkle Tree to actually validate the transaction. The format in which the full node communicates this to the light node is using something called a Merkle Block.
To understand what’s in a Merkle Block, we need to understand a bit about how a Merkle Tree can be traversed. If we look at the diagram above, the nodes can be traversed bredth-first or depth-first. Bredth-first traversal would go level by level like this:
The bredth-first ordering goes wider first and traverses each level before going to the one below.
Depth-first ordering is a bit different and looks like this:
The depth-first ordering goes deeper first and traverses the left side before the right side.
Going back to this diagram, the full node needs to send us the green boxes, HK and HN along with the blue boxes HABCDEFGH, HIJ, HL, HM and HOP. The full node sends us these items by utilizing depth-first ordering, flags and a list of hashes. We go through each step in detail.
The first thing we need to do is create the general structure of the Merkle Tree. Because Merkle Trees built from the leaves upward, the only thing we really need is the number of leaves and we’ll have the structure. The tree above has 16 leaves, which means we can create an empty Merkle Tree:
>>> import math
>>> total = 16
>>> max_depth = math.ceil(math.log(total, 2)) # (1)
>>> merkle_tree = [] # (2)
>>> for depth in range(max_depth + 1): # (3)
... num_items = math.ceil(total / 2**(max_depth - depth)) # (4)
... level_hashes = [None] * num_items # (5)
... merkle_tree.append(level_hashes) # (6)
>>> 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, log2 tells us how many levels there will be to the Merkle Tree. Note we have to round up using
math.ceilas we round up for halving at each level. We could also be clever and uselen(bin(total))-2. -
The merkle tree will hold the root at index 0, the level below at index 1 and so on. In other words, the index is the "depth" from the top.
-
We have to go up to
max_depth + 1asrangegoes to 1 less than the second argument in Python. -
The number of items at any particular level is the number of total leaves divided by the number of times we’ve halved, rounded up.
-
We don’t know what any of the hashes are, so we set them to
None -
Note again that
merkle_treeis a list of lists of hashes.
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 # (1)
self.current_index = 0
def __repr__(self): # (2)
result = ''
for depth, level in enumerate(self.nodes):
for index, h in enumerate(level):
short = '{}...'.format(h.hex()[:8])
if depth == self.current_depth and index == self.current_index:
result += '*{}*, '.format(short[:-2])
else:
result += '{}, '.format(short)
result += '\n'
return 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.
Given the leaves, we can use this structure to fill in the rest of the tree. We might be tempted to do something like this:
>>> from merkleblock import MerkleTree
>>> from helper import merkle_parent_level
>>> hex_hashes = [...]
>>> 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...,Indeed, this would fill the tree and allow us to get the 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 up 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. In order to do this, we need to keep track of some state as to where we are in the tree. We purposefully added the self.current_depth and self.current_index as a way to keep track of where in the tree we are.
We now need methods to navigate the tree. We’ll also include some 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): # (1)
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 will want to know if we are a leaf node
-
In certain situations, we won’t have a right child because we’re the right-most node of a level whose child level has an odd number of items.
We can now traverse the tree using the left, right and up methods. Let’s try populating the tree using depth-first traversal:
>>> from merkleblock import MerkleTree
>>> from helper import merkle_parent
>>> hex_hashes = [...]
>>> tree = MerkleTree(len(hex_hashes))
>>> tree.nodes[4] = [bytes.fromhex(h) for h in hex_hashes]
>>> while tree.root() is None: # (1)
... if tree.is_leaf(): # (2)
... tree.up()
... else:
... left_hash = tree.get_left_node()
... right_hash = tree.get_right_node()
... if left_hash is None: # (3)
... tree.left()
... elif right_hash is None: # (4)
... tree.right()
... else: # (5)
... 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 are looking to calculate the merkle root. As long as we don’t have the root, we continue to loop until we do.
-
If we are in 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 need to calculate that first before we can calculate the current node’s hash.
-
If we don’t have the right hash, we need it before calculating the current node’s hash. Note we should have the left one due to the depth-first traversal.
-
We have both the left and the right hash so we can combine them to get our current node. Once set, we can go upwards.
Note this code will only work when the number of leaves is a power of 2.
To do something a little more robust and allow for the possibility that the parent might be a combination of the left child twice if it’s the rightmost node, we have to change things up a bit:
>>> from merkleblock import MerkleTree
>>> from helper import merkle_parent_level
>>> hex_hashes = [...]
>>> 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: # (1)
... tree.left()
... elif tree.right_exists(): # (2)
... right_hash = tree.get_right_node()
... if right_hash is None: # (3)
... tree.right()
... else: # (4)
... tree.set_current_node(merkle_parent(left_hash, right_hash))
... tree.up()
... else: # (5)
... 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...,-
We start by checking to see if the left hash is defined. If not, we go to the left node since all internal nodes are guaranteed a left child.
-
We check here if this node has a right child. This is true unless this node happens to be the right-most node of the level and the child level has an odd number of nodes.
-
We the see if we have the right hash and if we don’t, we go and get it.
-
If we have both the left and the right hashes, we combine and go up a level.
-
We are in the situation where we have the left hash, but the right child doesn’t exist. That means the left hash is combined twice.
We now have code that can traverse the tree for the number of leaves that aren’t powers of 2.
The node communicating a Merkle Block needs to send us all the hashes we need to verify that the hash is indeed in the Merkle Tree. Indeed, the merkleblock network command does exactly this. We can see what that looks like:
merkleblockThe first 6 fields are exactly the same as the block header from Chapter 9. The other 4 fields are what help us reconstruct the Merkle Root.
The number of transactions is how many leaves this particular Merkle Tree will have. This allows us to get the right tree structure. We can create an empty tree and start filling in the hashes. There are a bunch of hashes that are given to us as well as flags that denote where the actual hashes go. The actual flags have to be interpreted a certain way and the bytes_to_bits_field converts the flag bytes to a list of bits (1’s and 0’s):
def bytes_to_bit_field(some_bytes):
flag_bits = []
# iterate over each byte of flags
for byte in some_bytes:
# iterate over each bit, right-to-left
for _ in range(8):
# add the current bit (byte & 1)
flag_bits.append(byte & 1)
# rightshift the byte 1
byte >>= 1
return flag_bitsThe ordering for the bytes are a bit strange, but meant to be easy to convert into the bits we need.
The flags are a list of bits that tell us about nodes in depth-first order.
The rules for the flags are these:
-
If the node is given to us (blue box in the diagram), the flag is 0 and the next hash is the actual hash value.
-
If the node is an internal node and calculated, that is, calculated from its children (dotted outline in the diagram), the flag is 1.
-
If the node is a leaf node and is a transaction we’re interested in (green box in the diagram), the flag is 1 and the next hash is the actual hash value.
In this particular case, the flags would be 1 for the root node (1), since that hash is calculated and not given to us. The left child, HABCDEFGH (2), is given to us, so the flag would be 0 and we would have to get the next hash from the list of hashes. From here, we don’t need to visit HABCD or HEFGH since we were already given HABCDEFGH. Thus, we skip all of its descendents and go straight to the right child of the root node.
The right child, HIJKLMNOP (3) has a flag bit of 1, so is calculated and not given to us. In order to calculate HIJKLMNOP, we need to calculate HIJKL (4) and HMNOP (9). The next item in depth-first order is the left child, HIJKL (4), which is what we go to next. This is once again an internal node that’s calculated, so the flag bit is 1. From here, we need to visit its children HIJ (5) and HKL (6) to calculate HIJKL. The left child, HIJ (5) is what we go to first and that’s a blue box or the hash is being given, so the flag is 0 and we take the next hash from the list of hashes. HKL (6) is an internal, calculated node so the flag is 1. HK (7) is a leaf node that we’re interested in so the flag is 1, and the next hash tells us its value. HL (8) is a given node so the flag is 0 and the next hash tells us its value. Going next in depth-first order is HMNOP (9), which is another internal node so the flag is 1. The left child, HMN (10) is another internal node that’s calculated, so the flag is 1. HM (11) is given to us, so we look at the next hash and the flag is 0. HN (12) is of interest to us and we get the next hash and the flag is 1. HOP (13) is given to us, so we get the final hash from the list.
Overall, our flags should be:
And we should have been communicated 7 hashes. This is sufficient information to prove that the green boxes, HK and HN are included in the block with the merkle root from the block header.
As you can see in the diagram, the flags apply in depth-first order. Anytime we’re given a hash, as with HABCDEFGH, we don’t need to visit any of its children or descendants and go straight to HIJKLMNOP instead of HABCD. Flags are a clever mechanism to show us which nodes have which hash.
We can now code a way to populate the Merkle Tree and specifically, the root, given appropriate flags and hashes.
class MerkleTree:
...
def populate_tree(self, flag_bits, hashes):
while self.root() is None: # (1)
if self.is_leaf(): # (2)
flag_bits.pop(0) # (3)
self.set_current_node(hashes.pop(0)) # (4)
self.up()
else:
left_hash = self.get_left_node()
if left_hash is None: # (5)
if flag_bits.pop(0) == 0: # (6)
self.set_current_node(hashes.pop(0))
self.up()
else:
self.left() # (7)
elif self.right_exists(): # (8)
right_hash = self.get_right_node()
if right_hash is None: # (9)
self.right()
else: # (10)
self.set_current_node(merkle_parent(left_hash, right_hash))
self.up()
else: # (11)
self.set_current_node(merkle_parent(left_hash, left_hash))
self.up()
if len(hashes) != 0: # (12)
raise RuntimeError('hashes not all consumed {}'.format(len(hashes)))
for flag_bit in flag_bits: # (13)
if flag_bit != 0:
raise RuntimeError('flag bits not all consumed')-
As before, the point of creating this Merkle Tree is to validate the root. Each loop iteration is looking at one node and we go until the root is calculated.
-
For leaf nodes, we are always given the hash.
-
This is a way in python to dequeue the next item of the list of flags. We might want to keep track of which hashes are being proven to us by looking at the flag, but for now, we don’t.
-
This is how we get the next item of the list of hashes. We need to set the current node to that hash.
-
In case we don’t know the left child, we might be either given the hash or have to calculate it.
-
The next flag bit tells us whether we need to calculate this node or not. If the flag is 0, we are given the hash, if the flag is 1, we need to calculate the left (and possibly the right)
-
We are guaranteed that there’s a left child, so calculate that first.
-
We check that the right node exists. For certain nodes, this may not exist.
-
At this point, we have the left hash, but not the right, in which case we need to calculate the right node’s hash.
-
We have both the left and the right hash, so we combine them to calculate the current node.
-
We have the rare situation where we have the left hash, but the right does not exist. In this case, according to Merkle Tree rules, we combine the left twice.
-
All hashes must be consumed or we got bad data.
-
All flag bits must be consumed or we got bad data.
It should be obvious at this point why Simplified Payment Verification is useful. However, SPV is not without some significant downsides. The full details are outside the scope of this book, but note that despite the programming being pretty straightforward, most wallets on phones actually do not use SPV, but simply trust nodes from the wallet vendors. The main drawback of SPV is that nodes you are connecting to know something about the transactions you are intersted in. 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.