8.1 Merkle Tree Algorithm
A Merkle tree is a tree data structure, where the leaf nodes contain the hash of a block of data and the non-leaf nodes contain the hash of its children nodes. In a Merkle tree, any change to the underlying data causes the hash of the node referring to the data to change. Since each parent node hash depends on the data of its children, any change to the data of a child node causes the parent hash to change. This happens to each parent node up to the root node. Therefore, any change to the data at the leaf nodes causes the root node hash to change.
From this, we can derive two important properties:
We don't need to compare all the data across the leaf nodes to know if they have the same data. We can just compare the root node hash.
If we want to prove that specific data is part of the tree, we can use a technique called Merkle proofs. We won't dive into details here but it is an easy and effective way to prove that a piece of data is in the Merkle tree.
The first property is important because it makes it possible to store only a hash of the root node to represent the data at that point in time. This means we only need to store the root hash of the tree representing the block on the blockchain (as opposed to storing all the data in the blockchain) and still keep the data immutable.
