How Are Merkle Trees Used On Bitcoin?

Merkle trees are a fundamental element of blockchain technology. They are used by most protocols, starting with Bitcoin, which relies on the Proof-of-Work consensus mechanism. However, they are utilized by most protocols to ensure the security and integrity of data on the network. If you are interested in the queen of cryptocurrencies, you have probably heard of it, but without really grasping how it works. In this article, we will explain in a precise and detailed manner what Merkle trees are and their utility for the Bitcoin network. You will also discover the limits and perspectives of this technology.

What is a Merkle tree?

A Merkle tree – also called a Merkle Tree or hash tree – is a logical structure that organizes data in a distributed system while ensuring their integrity and consistency. This tree-like architecture is widely used in blockchain protocols, including Bitcoin, to ensure that data cannot be altered or deleted.

Merkle trees were introduced in 1979 by Ralph Merkle. They use cryptographic hash functions to create a link between the nodes of the tree. Indeed, Merkle trees are composed of several nodes, notably:

• the leaves: these are the input data for the Merkle Tree. In the case of the Bitcoin blockchain, these are the transactions made on the network and contained in each block. Each leaf represents a specific transaction;
• the sub-branches: the leaves are first hashed individually to produce unique hash values for each transaction. Then, these hashes are combined two by two, from left to right, to form pairs of sub-branches. Each pair is then hashed again to create a new unique hash that will become an input for the next step of the process. If the total number of leaves is odd, the last leaf is duplicated to form a pair with itself;
• the branches: these are the parent nodes of the sub-branches. They result from hashing couples of sub-branches at the same hierarchical level. Each hierarchical level generates the creation of a number of branches reduced by half compared to the previous level, until only one node remains, the root of the tree;
• the root: called the Merkle root, it is the top of the Merkle tree. It is generated by combining the two top branches of the tree and hashing them together. The root is then used to represent the entire dataset included in the Merkle tree.

In general, when the number of transactions is odd, the system duplicates the last transaction to form a pair. Another alternative is to pair the solo transaction with a Coinbase transaction from the block.

How does Bitcoin leverage Merkle trees?

Merkle trees allow the Bitcoin network to achieve several objectives.

Storage Optimization

Bitcoin was the first blockchain to integrate Merkle trees. In fact, Satoshi Nakamoto explicitly mentioned this mechanism in the Bitcoin white paper. At that time, he spoke of it as a means to optimize storage space.

Indeed, the tree structure of the Merkle tree allows for the reduction of the size of data to be stored in the blockchain. This optimization enables full nodes to synchronize more quickly to the network and improves the scalability of Bitcoin.

Fraud Prevention

Each block in the Bitcoin network consists of a header and a list of transactions. When a new block is added to the chain, its Merkle root is included in the header of the following block.

The purpose of this maneuver is to maintain a historical record of events to ensure data authenticity. This is because if any modification is made to a transaction, the Merkle root of the block will change. As a result, one can notice an inconsistency with the value that was previously mentioned in the header of the next block.

Simplification of the Synchronization and Verification Process

Hash trees allow for verifying transaction validity without downloading the entire blockchain. Each tree summarizes all transactions in the block. This enables miners to easily traverse up the branches to determine if a transaction is fraudulent.

This is an efficient method that Bitcoin utilizes in the context of simplified payment verification, which is widely used by crypto wallets.

What are the limitations of using Merkle trees in the Bitcoin blockchain?

Despite their importance and utility in the operation of Bitcoin, Merkle Trees have certain limitations.

• Increase in Block Size: With the addition of each new transaction to a block, the size of the corresponding Merkle tree increases. This can lead to a significant increase in the overall block size. This can make it more difficult for miners and network nodes to store, synchronize, and validate the entire blockchain. This limitation has led to debates in the Bitcoin community regarding the scalability of the network;
• Increased Computational Costs: Constructing Merkle trees requires significant computational resources, as each level of the tree depends on the lower levels. The increase in the number of transactions in a block leads to an increase in the computations required to generate the Merkle root. This can result in higher costs for miners and potentially delays in block validation;
• Data Integrity in Case of Forks: When a fork occurs in the Bitcoin network, there may be variations in the transactions included in each branch of the fork. Consequently, the Merkle trees of the different branches will not be identical. This could create issues when merging forks or resolving conflicts;
• Pre-computation of Merkle Trees: Merkle trees are generally constructed before the addition of a new block to the chain. This means that miners must know all transactions included in a block before they can calculate the Merkle root and include it in the header of the block. This potentially limits the effectiveness of certain privacy or scalability mechanisms that might require dynamic construction of Merkle trees;

• Support for Offline Transactions: In certain circumstances, Bitcoin transactions can be performed offline. However, to include these transactions in a block, they must be added to the Merkle tree, which can be a complex and less convenient process.

Merkelized Abstract Syntax Trees (MAST)

Traditional Merkle trees can become very large when used to manage complex smart contracts. This issue has led to the development of palliative solutions, one of the most promising being Merkelized Abstract Syntax Trees (MAST).

MAST are an improvement proposal aimed at enhancing the flexibility and efficiency of Merkle trees in managing smart contracts and complex scripts. They allow breaking scripts into digestible pieces and selectively incorporating them into transactions.

MAST aims to reduce the size of data associated with contracts by only including the specific branches of the Merkle Tree necessary to validate a transaction. This helps save storage space on the blockchain and improves the privacy of contracts by obscuring unutilized branches.

However, although MAST offer significant advantages, their implementation also raises challenges. Compatibility, security, and governance issues need to be addressed to ensure harmonious adoption by the Bitcoin community. Furthermore, the implications of using MAST on verification and block size must be carefully studied to avoid any degradation of network performance.

Conclusion

The role of Merkle trees in the Bitcoin blockchain is multidimensional. They ensure data integrity, optimize storage, prevent fraud, and enhance the scalability of the network. In connection with the PoW mechanism and the hashrate of the network, they contribute to forging a secure and trustworthy ecosystem, making BTC the reference in cryptocurrency. As they evolve, they will continue to facilitate the construction of a decentralized and reliable financial system for generations to come.

La Rédaction C.

L'équipe éditoriale de Cointribune unit ses voix pour s’exprimer sur des thématiques propres aux cryptomonnaies, à l'investissement, au métaverse et aux NFT, tout en s’efforçant de répondre au mieux à vos interrogations.