concept merkle tree in category cryptography
This is an excerpt from Manning's book Real-World Cryptography MEAP V09.
One last interesting aspect of Bitcoin that I want to talk about is how it compresses some of the information available. Blocks in Bitcoin actually do not contain any transactions, but rather a digest that authenticates all the transactions that are included in the block. Transactions are actually shared separately, and the digest is the root hash of a merkle tree. What’s a merkle tree? It’s a tree structure where internal nodes are hashes of the concatenation of their children. By publishing the root of the tree, one can authenticate all of the leaves. I illustrate this in figure 12.7.
Figure 12.7. A merkle tree, a data structure that authenticates a number 2n of leaves for n the depth of the tree. In a merkle tree, internal nodes are the hashes of their children.
Merkle trees are very useful structures and you will find them in all types of real world protocols. They can be thought of as cryptographic accumulators, as they compress an unlimited amount of data into a fixed size value (the root of the tree). A merkle tree can provide proofs of membership that are logarithmic in the depth of the tree in size: if you know the root of the merkle tree, and want to know if a leaf is in the tree, I can share with you the neighbor nodes in the path up to the root as a membership proof. What’s left for you is to compute the internal nodes up to the root of the tree by hashing each pair in the path. It’s a bit complicated to explain this in writing so I illustrate this in figure 12.8.
Figure 12.8. To prove that a leaf belongs in a merkle tree, one can simply publish the neighbor nodes in the path from the leaf to the root. A verifier can then use these neighbor nodes to compute the hash of all the nodes in the path to the root, and verify that the last node is indeed the known root hash.
The reason for using merkle trees in a block is to lighten the information that needs to be downloaded in order to perform simple queries on the blockchain. For example, imagine that you want to check that your recent transaction has been included in a block. You could download all the recent blocks with all of their transactions, but you don’t need to. Instead, you can download the block headers (which are lighter) and ask a peer to tell you what block includes your transaction, and to give you a proof of that.