Merkle Tree
Merkle tree is a generalisation of a hash list or a hash chain. It has “leaf” nodes, each of them have a cryptographic hash of a data black they’re accossiated with. Every node that is not a “leaf” (they’re called branch or inner node) is labelled with the cryptographic hash of its child node’s hash. Merkle tree (or hash tree) allows more secure and efficient verification of large data structures. It was created in 1979 by Ralph Merkle (hence, Merkle tree).
How does it work in Blockchain?
Merkle tree helps us to store hashes of each block. The reason to do that is its difficulty and inefficiency to store the hash of each transaction inside one block. Therefore, we combine them in one hash for every block with the help of Merkle tree.
Let’s look at an example:
We have one block that we need to get the hash of. It stores 12 transactions. Firstly, we get the hash for every individual transactions (12 hashes). Secondly, we combine them in pairs. It would look like this:
After that, we continue to pair them up until we get the final hash containing all the transaction hashes. But, wait, we’ve got into trouble! After pairing them up, we’ve got only 3 nodes, how are we going to pair the block for Txns 9, 10, 11 and 12?
.png)
The solution in that case is to copy the same node that contains the remaining hashes. In the end, we’ve got our Root, the initial hashes are “leafs” and the in between nodes with hashes are branches:
.png)
In the end, merkle root is a digital fingerprint of the entire set of operations (block), allowing the user to verify whether the transaction is included in the block or not.
Why is it beneficial to Blockchain?
There are several advantages of utilizing Merkle tree in Blockchain:
1. Merkle tree is used to effectively verify data’s integrity and ensure that all the transactions in the block are correct. The reason is that we can easily broke the Merkle root down into small pieces of data, i.e. leafs. It leads to verification taking up only a few seconds.
2. In comparison to other data structures, Merkle tree takes up a very little disk space, which is useful for nodes storing the blocks.
Example of Merkle tree usage with Bitcoin
1. As we already said above, Merkle tree takes only a little disk space and can be broken down into small pieces. Withouth the Merkle tree, each node on the Bitcoin network would have to store the complete copy of every transaction ever made. With Merkle tree, each node has to store only the Merkle root and is able to get and verify each individual transaction.
2. Consensus mechanism would require even more computational power and energy to compare all the blocks created and verify which one is correct. Moreover, without the Merkle tree, all the giant data structures would have been transferred between nodes and miners, which would also significantly increase the power required from the miners.
Other examples of Merkle tree usage
Merkle tree is used by a lot more systems than only blockchain. For example, Git uses Merkle tree, which allows us to get all the projects, protocols and programs from any part of the world; Interplanetary File System (IFS), Amazon DynamoDP and Apache Cassandra also use Merkle tree to control discrepancies.
Sources:
