What is a Merkle Tree?
Merkle Tree is a type of structure that is often used to quickly verify data integrity, mostly in a dataset. It is also known as a hash tree, which has, in most cases, binary implementations, with each node usually having two “child nodes.” In the cryptocurrency world, this structure is used to encrypt blockchain data more efficiently and securely, but we will explore that in more details later.
Merkle Tree is a way for quick and secure content verification across big data sets. It also helps to verify consistency and content of the data. Merkle Tree is a mathematical data structure made up of hashes of various blocks. These hashes summarise all the transactions in the given block thanks to which Merkle Trees are often used in cryptography.
Merkle Tree has three types of nodes that can be found within it. These are as follow:
-
Root node: this is stored directly in the header and is also known as Merkle root.
-
Leaf node: consists of hash values for transaction data. Each transaction in the block has its data hashed, leading to a creation of transaction ID, which is then stored in leaf nodes.
-
Non-leaf node: lastly, the Merkle Tree also has a non-leaf node, which contains hash values of “their children.” Known as intermediate nodes, they are essentially hash values used until the process reaches the tree root.
The essence of Merkle Tree is such that it allows transactions to be verified without using much data at all. This then helps with lowering the CPI processing, while maintaining enhanced security, both of which are necessary.
The Merkle Tree has all transactions grouped in pairs, so that each pair has a computed hash that is stored directly in the parent node above the given pair. This applies to the nodes above them and above them and so on, until the Merkle root is reached.
Example of Merkle Tree with Merkle root, non-leaf node and leaf node, Source: geeksforgeeks.org
Let’s look at an easy example. In the chart below, we have 4 different transactions, labeled A, B, C, D. Each transaction is first hashed, leaving it in a form of Hash A, Hash B etc. Four hashes are thus created and paired to a leaf node, leading to a creation of non-leaf nodes. In this case, these are hash AB and hash CD, which are the results of children hash A and hash B, for the hash AB and hash C and hash D, for the hash CD.
These two new hashes, which are parent hashes to the original four transactions, are then hashed again. This leads them to reach a hash ABCD and a root of the Merkle Tree. The Merkle root is then responsible for a summary of data that the initial transactions held. This information is stored in a block header.
Benefits of Merkle Tree
Merkle Tree as a structure provides several benefits that are then exploited also in the cryptocurrency and blockchain technology. Before we look at how these benefits are used, let’s first see what they are.
-
No delays: when Merkle trees are used, the transfer of data through the network can be done without any delays. Without the use of Merkle Tree, this is not possible as all the data needs to be transferred all over the network for verification, causing delays.
-
Efficient verification process: very little memory needs to be used during the verification process thanks to how the data is structured. This means that the transaction validity and integrity can be verified in almost no time. Also, thanks to this, only a small amount of data needs to be sent compared to the size of the dataset.
-
Little disk space: hand in hand with the above-mentioned benefit is also the size of the disk space that the Merkle Tree takes up, which is considerably small compared to other data structures. This leads to verification of transactions with viable bandwidth and computational power.
-
Detection of tampering: every transaction is stored within the Merkle Tree. This means that any attempt of a transaction being changed leads to reaching Merkle root and contains the information in the block header. Thus, it is easy to compare the present data with the tampered version and quickly detect any attempt of fraud.
Merkle Trees and cryptocurrencies
While not many non-technical people are paying attention to Merkle Trees in the cryptocurrency community, the cypherpunks or technically advanced supporters of cryptocurrencies know the value of Merkle Trees in this sphere. Merkle Trees are essential for blockchain technology, since they facilitate quick and easy verification. In fact, this type of verification would not be possible with any other technique or structure.
Merkle Tree gives the power over huge data sets to developers, who can compress them effectively by getting rid of all unnecessary data, just to later turn it into hashes. In the cryptocurrency world, the benefits of this can be manifested, for example, through fuel efficiency, effective scalability, basic payment authentication, verification of transaction or lightweight structure.
Merkle Tree breaking the data into tiny parts of information, Source: simplilearn.com
Merkle Trees in crypto – Bitcoin and Ethereum
With briefly looking at what Merkle Trees are or how they are used in the cryptocurrency space, let’s now dive into more concrete examples of their use cases.
Bitcoin
Many of you have probably guessed it, but Bitcoin uses Merkle Trees in many instances. The most obvious one is the use of it in the Bitcoin block header, since the hash of every transaction that is available within the block is placed in it.
However, that is not all. Merkle Tree structure is also used in mining or verification. For miners, Merkle root is crucial in improving efficiency of all the processes. Thanks to this structure and its inherent characteristics, once the miner checks the blocks header once they have been made into the Merkle Tree. Checking the Merkle root thus means a much more effective approach, then checking the entire block itself.
This structure is also used in verification, more specifically in cases when a node is operated from a relatively weak device. If the device has limited resources, instead of downloading every hash and block, it will use Merkle proof, which contains the confirmation that a transaction is present in a block. This then reduces the number of hashes and allows verification to occur without needing as much energy resources.
Ethereum
The second biggest cryptocurrency, Ethereum, is based on Merkle Patricia Tree, a modified version of Merkle Tree. This means that every block in this blockchain consists not of one, but three Merkle Trees, with each of the roots having its own purpose.
The first one is the root for every transaction. The second shows the state of the transaction. And the last root is the receipt of the whole transaction. Anyone can thus look at the Merkle root and see whether the transaction is found in a specific block, whether it was already approved and sent and what the balance of the transaction was, thanks to the Merkle Trees.
Conclusion
Merkle Tree structure has become ever more important in the cryptography movement once the cryptocurrencies were invented. With the first one, Bitcoin, using Merkle Trees in many aspects, this type of structure spread also to other cryptocurrencies thanks to the benefits it provides to the underlying projects.
BTCEX team
2023-05-11