What is a Merkle tree.
Merkle tree is a hash tree, named after Ralph Merkle, who patented in 1979.
Most implementations of them are binary, which means two child nodes under each node.
Why the merkle tree is important to the peer-to-peer network?
The main purpose of a merkle tree is to ensure the data we received from a peer-to-peer network are undamaged and unaltered, it’s important as the data were splitted into many blocks and stored in multiple nodes in the network.
It’s also provide a mechanism to check the data without to receive all the data.
How does a merkle tree work.
Let’s check the follow image that download from Wikipedia:
From bottom to top:
- L1,L2,L3,L4: The data are splitted into 4 blocks, and stored as leaf node in the merkle tree.
- Hash 0-0,Hash 0-1,Hash 1-0,Hash 1-1: Each parent of the data blocks stores the hash of each data block, usually by a cryptographic hash function such as SHA-2.
- Hash 0, Hash 1: Hash of their children’s hash.
- Top Hash: Hash of their children’s hash.
As we can see, if any data block is changed, then the root hash or top hash will be changed too. So we can simply compare any two root hash or top hash values to check if the data are changed or not.