What is Merkle Tree ?

If not redirected, please click here https://www.thesecuritybuddy.com/encryption/what-is-a-merkle-tree/

When data is distributed across multiple hosts over a network and they are transferred, there should be some way to verify the integrity of the data stored in multiple nodes. For example, in BitTorrent, if we are not sure about the integrity of data stored in different nodes, the file sharing will fall apart. Merkle Tree is a data structure that solves the purpose.

What is Merkle Tree ?

In cryptography and computer science, a Merkle Tree is a hash tree in which every leaf node stores some data and every non-leaf node is labelled with the hash of the data of its children nodes. This Merkle Tree is used to verify data stored, handled and transferred in and between computers. It is used to make sure, the data blocks received from other peers in a peer-to-peer network are unaltered and undamaged.


In this tree, every parent node contains the hash of its children nodes and the root node is the top hash, which verifies the data blocks stored in the whole tree is undamaged and unmodified.

In a peer-to-peer network, when we download the whole file, this hash tree gives a significant advantages.



How does Merkle Tree work ?


Here is the algorithmic overview of a Merkle Tree :

1. Take a file or binary stream of data.
2. Split the file into chunk of data blocks. Usually the chunks are of same size.
3. For an odd number of chunks, use all-zero values to complete the binary tree. Every non-leaf nodes should have two children nodes each.
4. Arrange the chunks in the same order as the content of the file.
5. Take a pair of leaf nodes, and hash them using a well-known cryptographic hash function like SHA-1. Put the hash value in the parent node of the pair of leaf nodes.
6. Repeat the process and calculate the hash of a pair of sibling nodes and put the hash value in their parent node.
7. Repeat the process and calculate the hash value of the root node.
8. The top hash will verify the data chunks stored in the whole tree.

This Merkle Tree is significantly used in peer-to-peer network like BitTorrent. Before downloading a file on a peer-to-peer network, the top hash is first acquired from a trusted source. When the top hash is available, the whole tree can be received from any source and verified.


This Merkle Tree is also used heavily while mining bitcoin, as we discussed earlier.




Read More

What is Blockchain ?

What is Bitcoin ?

What is mining of Bitcoin ?

How does mining of Bitcoin work ?

What are the pros and cons of using DSA and RSA ?

What is PGP or Pretty Good Privacy ?