Arsablog

What is Merkle Tree?

درخت مرکل (Merkle Tree) چیست؟

Since its inception, blockchain technology has created a fundamental transformation in various industries and has caused stunning progress in various sectors. Undoubtedly, we can consider the most important achievement of this technology to secure the Bitcoin network and other similar digital currencies. Meanwhile, what ensures the efficiency of this technology in a wide financial network like Bitcoin, is a set of mathematical structures related to cryptography and hashing (Hashing). One of the basic data structures in blockchain technology is the Merkle Tree, which allows the blockchain to process and store large amounts of data.

Merkel tree has a tree-like data structure and consists of several different hashes that contain transaction information. Merkel tree can be considered as one of the main pillars of ensuring the security and efficiency of blockchain-based networks such as Bitcoin, which deal with huge data structures. Due to the importance of this structure, we have dedicated this article to the analysis of the Merkel tree. Next, after getting familiar with the concept of Merkel tree and its history, we will take a look at how this structure works. Then, we mention the functions of Merkel tree and its importance in blockchain. So stay with us until the end of this article.

Merkel tree (Merkle Tree) What is?

Merkel tree, also called Hash Tree, has a data structure similar to an inverted tree that can process and summarize a large amount of data safely. Merkel tree has many applications in computer science, especially cryptography. Blockchain is also one of the technologies that uses this concept.

Blockchain uses the Merkel tree to process and at the same time reduce the volume of encrypted data in an efficient and secure way. Each block contains many transactions and data. The Merkel tree considers the hash value of each transaction or transaction ID separately and combines them to create a new branch.

To better visualize how a Merkel tree works, think of transaction hashes as the leaves of the tree. Both leaves are paired together and subjected to a hash function (for example, the SHA256 function in the Bitcoin blockchain). The result of this combination is a new hash that footprints It contains the previous two hashes. Next, the tree pairs this new hash with another new hash obtained from the other two transactions to create a newer hash.

Read more: What is a block in the Bitcoin blockchain and what is inside it?

This hashing path continues until we finally get a single hash called the Merkle Root, which is the same The original hash It is blocked. The final hash is a processed summary of all transaction data that contains the fingerprint of each transaction.

A picture of the Merkel tree
A general view of the Merkel tree

The history of the Merkel tree

Merkel tree is older than blockchain technology. This invention was registered in 1989 and was named “Merkle” in honor of Stanford University professor Ralph Merkle. Merkel by publication an article About digital signatures under the title “A Certified Digital Signature” (A Certified Digital Signature) he explained this plan. Decades before the invention of Bitcoin, cryptography was used to secure data in software development. Merkel tree was one of the methods of calculating a huge amount of data and saving memory.

This process is a reliable way to validate hash data in databases that deal with large amounts of information. Merkel’s article in the Bitcoin white paper is presented as one of the main components of this network, and it is interesting to know that Ralph Merkel is also a supporter of digital currencies and a supporter of decentralized autonomous organizations or DAOs.

Read more: What is DAO? Acquaintance with the best projects of the decentralized self-governing organization

Merkel root (Merkle Root) What is?

As we mentioned earlier, the Merkel root is the single and final hash of the entire Merkel tree, which contains a summary of all the block data. The Merkel root is stored as a summary of each block in its header and maintains data integrity.

Actually, the Merkel root is used to measure the correctness of the previous blocks. Each block can have only one Merkel root. With the smallest change in block transactions, the root of Merkel changes. Therefore, if we want to check very quickly and simply whether a transaction is included in a block or not, we just need to refer to its Merkel root.

How does Merkel tree work?Theslow?

In this method, the hash of all related transactions is put under the hash function two by two, so that we finally get to the final hash called the Merkel root. For this purpose, the number of hash entries must be even. If the number of hashes is odd, the last hash is repeated once and then paired with itself.

Suppose you have 200 transactions at the end of the Merkel tree, which are reduced to 50, then to 10, then to 5, and finally to 1 hash under the hash function. The final hash or Merkel root is the representative of all 200 previous hashes of the group; Because any small change in the transactions may change the final outcome of the Merkel root. This makes tampering with transactions virtually impossible.

For example, in the image below you can see four transaction hashes C, B, A and D. By combining these four hashes, we get two hashes AB and CD, finally we are faced with the unit hash ABCD, which is the Merkel root and representative of the previous four hashes. Of course, this picture is quite simplified, and Merkel trees generally process and summarize a much larger volume of data. However, a single hash can be achieved with sequential hashing in larger datasets.

Merkel root

Note that a Merkel tree is not just a list of transactions; Because even without access to all transactions, you can validate each branch of the transaction separately. Thus, if the original version becomes corrupted, smaller portions of the data can be re-examined.

Merkel tree and blockchain

Computer science uses the term “tree” to describe any branching data structure. Merkel trees are inverted trees with lower leaves and a single root at the top. In general, the Merkel tree in blockchain consists of three important parts:

  • Leaf nodes or nodes
  • Nodes or non-leaf nodes
  • Merkel root

In the lowest part of the Merkel tree, we deal with leaf nodes, which are transaction hashes or transaction identifiers (TXID). If you look for a specific transaction in the blockchain browser, you will come across these identifiers. By pairing two leafy nodes, we get a non-leafy node. Non-leaf nodes no longer contain the transaction hash; Rather, it only stores the hash of the lower two-node leaf. These non-leaf nodes are also paired so that the number of hashes is halved again in the next layer. In the end, only two nodes remain, which form the Merkel root.

Read more: How does Bitcoin work and how are its transactions done?

We can use the Merkel root to validate each leaf node or the ID of transactions. If you are familiar with how Bitcoin works, you know that the header of each block contains only a single hash. This hash is the same unit Merkel root which is sometimes called the root hash (Root Hash).

Leafy and non-leafy nodes in Merkel tree

Applications of Merkel tree

A Merkel tree is a method of summarizing data, and thus, it can greatly reduce the memory requirements for storing data in a reliable database such as blockchain. This technology separates data validation from the data itself. This structure can be used for a specific part or for an entire distributed system.

Therefore, Merkel tree is one of the main tools of blockchain users to evaluate the validity and reliability of data. Also, since this technology requires little memory or disk space, it helps larger networks to perform calculations more quickly and easily. With this structure, data transfer is faster throughout the network; Because small amounts of data can contain general network information.

In blockchain technology, it is essential to prove the completeness and consistency of an entry to the thematic ledger. Merkle trees help to record and validate the latest inputs along with all previous data in an orderly and accurate manner.

Also, to prove the validity of the new input, we need to show that all the previous data is correct without modification or manipulation, and that the source of the input is not a forked branch or invalid. Merkel tree helps miners and blockchain users to prove this issue; Because the smallest change in one of the hash values ​​messes up all the equations and the final result of this structure.

By using the Merkel tree, miners receive and calculate hashes of transactions gradually from users. Users can also check individual parts of blocks and validate their desired transactions using the hash of other parts of the tree. In fact, Merkle tree eliminates the need to download a huge amount of information for data validation by separating the data validation process from the data itself.

Merkle tree benefits

Merkel tree adds several advantages to the data processing system, some of which are:

  • Creating an efficient and fast way to prove the authenticity and validity of data
  • Reducing the amount of data needed to validate network information
  • Reducing the memory required to store network data
  • The possibility of validation using the Simple Payment Verification (SPV) method for LiteBitcoin clients (in this method, Lightnodes are satisfied with minimal information checks)
  • Ease of transferring and publishing data throughout the network
  • The possibility of checking individual parts of blocks without needing to have all the information
  • Access individual sections of data without having to load all the data

The importance of the Merkel tree for Bitcoin

We can consider the Merkel tree as one of the main pillars of Bitcoin. To understand the importance of this structure in the Bitcoin network, just imagine Bitcoin without these trees.

Read more: What is the difference between Bitcoin and Blockchain?

Without a Merkel tree, every Bitcoin node would have to keep a complete copy of all data about every transaction ever made on Bitcoin. Regardless of the staggering amount of storage and bandwidth that this amount of data would require, it would also be nearly impossible for nodes to match different versions of the blockchain to ensure their authenticity.

In fact, the Merkel tree helps Bitcoin users to go to the Merkel root and its path when checking a specific transaction, instead of needing to check all the data. Also, clients lightBitcoin users can access block information by just downloading the block header that contains the Merkel root, without needing to download the entire blockchain.

It should be noted that by reducing the volume of data, the Merkel tree greatly reduces the time required to transfer data throughout the network. At the same time, the sensitivity of this structure to the smallest change in data makes this transfer completely safe.

Apart from Bitcoin, many other blockchain networks also use the Merkel tree structure; But some of them have a different way of using this data structure. For example, the Ethereum network’s Merkel tree is called Patricia and produces three different Merkel roots for each block.

TotalTheclassification

Merkel tree is an efficient way to improve processing speed and perform necessary calculations in cryptographic systems. Considering the importance of this concept in the blockchain encrypted system, in this article we tried to take a look at the Merkel tree and its function in the blockchain. In the meantime, we got to know the root of Merkel and its place in blockchain network calculations, and we learned more about its advantages. Finally, we explained why the Bitcoin blockchain cannot survive without the Merkel tree structure.

Merkel tree guarantees the immutability and integrity of blockchain data. In addition, this data structure makes the information as compact and portable as possible. In fact, we can consider the Merkel tree as one of the main pillars of the blockchain, which allows this system to grow bigger and more complex every day, and at the same time, not suffer from a lack of security. Understanding the place of the Merkel tree in the emergence and expansion of the blockchain industry and digital currencies seems essential, and it may be safe to say that without the history-making invention of this data tree, there would be no news of the Bitcoin revolution today.

source

Leave a Reply

Your email address will not be published.