This is a read note of Programming Bitcoin Ch11: Simplified Payment Verification.

1 Merkle Tree

A Merkle tree is a computer science structure designed for efficient proofs of inclusion. The construction of a Merkle tree from an ordered list of transactions are as follows:

  1. Hash all the items of the ordered list with the hash256 function.
  2. If there is exactly 1 hash, we are done.
  3. Otherwise, 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.

2 Proof of Inclusion

A parent P is the hash value of concatenated left child L and right child R. Giving P and R, we can tell if a value X is included in P or not. This is so-called proof 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. At each level of a Merkle tree, it only needs one hash value of the other half except at the root level to verify the inclusion. For a Merkle tree with N levels, only N-1 hashes are requird to verfy the inclusion. This is the simplified payment verification (SPV).

The SPV proof 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. Large transaction should be valided using a full node.

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.

In a proof of inclusion, the location of each hash is reconstructed using depth-first ordering from some flags.