What is a Merkle Tree?

[TL; DR]

- Merkle trees were named after the computer scientist who proposed them.

- They are a form of data structure used in computer science and blockchain.

- Merkle trees or hash trees are for verifying transactions on a blockchain efficiently and securely.

- To confirm the presence of a transaction on a blockchain, one merely has to query it, and the Merkle tree will expedite the verification process.


The word Merkle Tree was named after a computer scientist of the same name. Ralph Merkle, who also developed cryptographic hashing, proposed the idea of Merkle trees in 1987. He wrote a paper titled “A Digital Signature Based on a Conventional Encryption Function."

In general terms of computer science application, A Merkle tree is simply a type of data structure. It was adopted in the world of crypto as a way of encoding blockchain data efficiently and securely. Merkle trees can also be called hash trees because they are hash-based data structures used in computer science and cryptography.


The Composition Of A Merkle Tree

---

A Merkle Tree, as exemplified above, has the structure of a tree. It has a root and branches, each with its function. Unlike real trees, the roots of Merkle trees are at the top, not the bottom. So, the hash at the very top of this tree is the root, followed by the branches and the leaves at the bottom.

In Bitcoin, the root is a part of the block header, making sure of the transactions that are present. The branches are nodes that contain the values of the nodes beneath them, serving as their “parent nodes.” Typically, in Merkle trees, these nodes never contain more than two nodes underneath them which is why they are called binary hash trees.

However, a hash tree can have more than two nodes.

Finally, leaves, as mentioned earlier, are the nodes at the bottom that do not have any more nodes functioning beneath them. Every node in the arrangement of the Merkle tree is a partial representation of the hashed data that is beneath them. On the other hand, the leaves represent the hashes of single transactions.


How Merkle Trees Work

---

The Bitcoin blockchain is perhaps the prominent use case of Merkle trees, and this is how it works. Usually, Merkle trees are used to make data verification faster and more efficient.

Whenever there is a need to verify the correctness of a set of data from the primary set of transactions, Merkle trees ensure that there is no need to get the entire information file.

Essentially, Merkle trees are created by running transactions through the hash function one at a time, then concatenating and hashing each new one to the previous one. The process continues until an entire block has been hashed together into one hash. Merkle Trees summarise all the transactions in a block and produce a virtual fingerprint of the entire set. This enables a user to verify the presence of a particular transaction in a block without downloading all the other unnecessary information within it.

To explain it further, if you want to confirm that a particular transaction, say one of the leaves, is included in the block above it, you can simply ask the network about the specific node. It will give you an answer using three hashes, allowing you to verify the presence of your specific node.





Importance of Merkle Trees

---

Merkle trees are an invaluable tool for data verification in blockchain and computer science at large for the following reasons:

Speed

Imagine you need to verify the presence of particular data on a blockchain. Without Merkle trees, you would have to download a whole blockchain and sift through it. Obviously, that would take a lot more time than is necessary as the amount of data on blockchains is usually massive, running into hundreds of gigabytes. Bitcoin, for example, has up to 389 gigabytes of data as of April this year, according to a report by Statista. With Merkle trees, however, you can easily trace your specific transaction query and get answers within a smaller time frame.

Efficiency

Citing the above Scenario again, it is obviously a cumbersome and unnecessary activity trying to go through all transactions just to verify a single one. Merkle trees significantly narrow the amount of data required to verify transactions. With only four hashed values; one can easily determine what one needs to know about specific transactions.

Trust

Last of all, verifying the integrity of a particular transaction is considerably easier with a hash tree. If you need to confirm values from sources you don’t trust, just reconstruct the part relevant to you and compare it with the root hash from a trusted source. This is invaluable in speeding up the validation process.


As Well as the Recent Eye-catching "100% Proof of Margin"

---

The account asset hash value of each user can be stored in the leaf node of the Merkel tree in the form of the Merkel tree. Everyone can audit the total amount of user assets stored in the Merkel tree leaf node through a third-party institution with audit qualification to verify whether his/her funds are included in the asset Merkel tree.



How Does Gate.io Adopt the User's Encrypted UID and Balance to Build a Merkel Tree?

---

First, export the encrypted UID and the corresponding user balance from the Gate.io database. Each pair of encrypted UIDs and user balances will be hashed separately, and then joined to form underlying data blocks. For each data block, the same hash function is used to generate the leaf node of the Merkel tree. The encrypted data obtained will then be hashed together in pairs to create the parent node of the leaf node. This process continues until a single hash data, namely Merkel root, is obtained. After the Merkel tree is successfully built, the leaf node will be exported as a text file and then released by the auditor together with the Merkel root hash.

When the total assets of the platform audited in the form of a Merkel tree are greater than or equal to 100%, it proves that the platform has kept the user's funds intact, which means that the platform provides 100% of the corresponding assets as margins. You can view more information about the Gate.io 100% Proof of Margin through the Gate.io 100% margin details page or the third-party audit Armanino official website.


Conclusion

---

The invention of Merkle trees and its subsequent usage in blockchain technology is an invaluable asset to the world of tech. With it, people can now easily and efficiently expedite the verification of transactions on a blockchain without needing extra space to download the entire blockchain. Merkle trees also save validators time while making blockchain tech security easier.




Author: M. Olatunji, Gate.io Researcher
* This article represents only the views of the observers and does not constitute any investment suggestions.
*Gate.io reserves all rights to this article. Reposting of the article will be permitted provided Gate.io is referenced. In all other cases, legal action will be taken due to copyright infringement.