Merkle trees are used in computer science applications as a data structure for data verification and synchronization. Merkle trees are also used to more securely and efficiently encrypt blockchain data in Bitcoin and other cryptocurrencies. 

With cryptocurrencies, a Merkle tree database is used to securely split the block's data and ensure that it is not lost, damaged, or altered. This method of data management makes it possible to validate specific transactions without downloading the entire, terabyte-sized blockchain. It is a reliable, secure, and cryptographic method of running the blockchain.

As a result of the fall of the Centralized Exchange (CEX) giant, FTX, many CEXs have built and implemented Merkle Tree as a form of Proof of Reserves (PoR) to assure users that their funds are safe. In this article, we will be discussing what are Merkle trees, their role in blockchain and how a user can validate their funds using the Merkle tree.

Who is the Founder of Merkle Tree?

Ralph Merkle, a computer scientist renowned for his work on public-key cryptography, proposed Merkle trees in the 1987 paper "A Digital Signature Based on a Conventional Encryption Function". Cryptographic hashing was also invented by Merkle.

What Is a Merkle Tree?

Merkle tree is a hash-based mathematical data structure that compiles the summaries of all the transactions in a block. It is a method for quickly checking the accuracy of data in a decentralization manner. As a result of its functionalities, Merkle trees are utilized more effectively and securely to encrypt blockchain data. 

Merkle trees are often used with peer-to-peer (P2P) networks because of the need to have information shared and independently validated. Let’s understand more about Merkle trees and how they work.

Merkle Tree Structure

The Merkle tree, also known as a hash tree, has a binary tree structure, with the hashes of the transactional data on the bottom row being referred to as "Leaf Nodes," the intermediate hashes being referred to as "Non-Leaf Nodes," and the hash at the top being referred to as the "Root." Even though the majority of hash tree implementations are binary (each node has two child nodes), they can also have a lot more child nodes.

When looking at the structure of a Merkle tree, all transactions are grouped in pairs. Each pair has a computed hash that's stored directly in the parent node. These nodes are also grouped into pairs, after which their hash is stored on the next level up. This process continues until reaching the root of the Merkle tree.

Let’s take a look at each of the nodes:

Leaf Nodes

These are the hashes of each cryptocurrency transaction in a block, also referred to as transaction IDs (TXIDs). You view the transaction hash when you search for a transaction on a block explorer.

Non-Leaf Nodes

Then, to create a layer of non-leaf nodes above the leaf nodes, these leaf nodes are hashed together in pairs. They are known as non-leaf nodes because, in contrast to leaf nodes, they merely store the hash of the two leaf nodes that it represents and don't contain transaction IDs (or hashes). As a result, there will be half as many hashes (or nodes) in the non-leaf node layer above the leaf nodes as there are in the leaf node layer. As the tree narrows as it ascends, these non-leaf node layers continue to be hashed together in pairs, resulting in half as many nodes per layer. Two nodes will be present in the final non-leaf node layer. This creates the Merkle root and is the location of the last hashing in a Merkle tree.

Merkle Root

With Bitcoin, the hashes of all transactions are combined into a single hash and stored in the block header. The Merkle root, also known as the root hash, is this particular hash. The leaf nodes (transaction IDs/hashes) at the base of the Merkle tree can be verified using this Merkle root. When used for cryptocurrencies, the Merkle root makes sure that data blocks are unaltered, undamaged and whole.

A Merkle tree is binary, which means that the total number of different leaf nodes must be even for the tree to be properly constructed. When an odd number of leaf nodes exists, the previous hash will be duplicated to provide an even number of nodes.

How Does a Merkle Tree Work?

A Merkle tree is essentially designed to break large pieces of data into considerably smaller chunks, which ensures that all the transactions can be verified promptly. The tree summarizes every transaction by creating a small fingerprint of a specific set of transactions, which makes it easier for users to verify the availability of transactions in a block. 

Merkle trees are formed by hashing different pairs of nodes until just one hash remains, which is referred to as the Merkle root. These trees are built from the bottom up, with each transaction consisting of hashes. Every leaf node is a singular hash of data. As for non-leaf nodes, these are hashes of previous hashes.

Let's say that a Merkle tree consists of four transactions which are labeled D0, D1, D2 and D3. Each transaction is hashed before the hash is stored directly on the leaf node. When this occurs, hash N0, N1, N2 and N3 are created. Any consecutive pair of leaf nodes will then be summarized in a parent node via the hashing of hash N0 and hash N1, which results in hash N4. If hash N2 and hash N3 are hashed together, hash N5 is created. Both of these hashes, N4 and N5, are hashed once more in order to create the Merkle root.

This process can be used with extensive data sets. The Merkle root is responsible for summarizing the data that's present in specific transactions, all of which are stored directly in the block header. This technique results in data integrity being properly maintained. In the event that one detail within the transaction is changed at some point, the Merkle root will automatically change alongside it.

Benefits of a Merkle Tree

There are many benefits for blockchain technology and cryptocurrency platforms when using a Merkle tree to verify transactions, which include everything from efficient verification to easy tampering detection.

Efficient Data Verification Process

It's easy for transaction integrity to be verified in practically no time at all. Because of how the data is structured, very little memory needs to be used during the verification process and the computing power required is significantly reduced. 

Because blockchains typically consist of hundreds of thousands of blocks, each of which can contain up to several thousand transactions, validating the data poses two major challenges: memory space and computing power. Every node on the network would have been required to maintain a complete copy of every transaction that has ever taken place on the blockchain if Merkle trees were not a concept in the blockchain. A node would have had to compare each entry line by line when verifying a transaction to ensure that its records exactly match the network records. The network's security could be jeopardized if there was any discrepancy between the records. As a result, to compare the records to make sure there had been no changes, the computer used to validate the data would have needed much more processing power. 

Merkle trees, on the other hand, offer a solution to this issue by drastically reducing the amount of data that must be kept on hand for verification needs. They hash every entry in the ledger, effectively separating the data itself from the evidence supporting it. Without knowing every single TXID in a block, you can check a TXID using the Merkle root with a Merkle tree. A Merkle tree is essentially a great way to demonstrate that something is present in a dataset without having to download the entire set. Consequently, less computing power is needed to validate the transactions.

Faster Processing Speed

As a result of the distribution of the transactions on the block among the validators, each validator is working on a different transaction at the same time. Compared to a method where each transaction is sequentially validated after another, this is much more effective.

Usage of Crypto Wallet

Simple Payment Verification (SPV), which enables you to confirm a transaction without downloading an entire block or blockchain, is made possible by the Merkle tree. This enables the use of a light-client node, more formally known as a crypto wallet, to send and receive transactions.

Detection of Any Tampering

The hash structure makes it easy for miners to identify if tampering has occurred with transactions. 

A distinct hash value is generated for each block using the Merkle root. The block links one block to another in the blockchain by including the hash of the preceding block. The hash of any transaction changes whenever that transaction is modified. The block becomes invalid as a result of this change because it cascades up to the Merkle Root and alters its value. This then causes a change in the hash of the following block, rendering the remainder of the Blockchain invalid. As a result, the Merkle tree creates an immutable record of the block's transactions.

Double spending can also be prevented as a result. If an individual tries to double-spend his digital currency, a hash will be generated for that transaction. If that hash matches the existing records present on the Blockchain, that transaction is rejected.

Why Are Merkle Trees Important in Blockchains?

Merkle trees have proven to be essential for blockchain technology because they facilitate quick and easy verification in a manner that's not possible with other techniques. These Merkle trees provide developers with the ability to compress exceedingly large sets of data by getting rid of all unnecessary data, and turning the data that remains into hashes. The various features provided by Merkle trees include:

• Very lightweight structure
• Effective scalability
• Fuel efficiency
• Verification that transactions are included in a specific block
• Basic payment authentication

Merkle Tree Proof-of-Reserves (PoR)

As mentioned in the beginning, following the downfall of FTX, users have been concerned as to whether their funds are actually kept safe in CEXs. As a result, multiple CEXs have come forth to develop a Merkle Tree Proof-of-Reserve mechanism. In this section, we will be looking into Merkle proofs and how our users can validate their funds.

Merkle Proofs

A Merkle tree proof is a cut from a Merkle tree, not the actual tree. And be represented as an array or sequence (shown by the orange portion in the diagram below).

All of the leaf nodes and the balance information for a particular single user of our company are represented by the figure's last level nodes. Assuming that the pink people in the figure represent the intended recipients of the proofs, we extract the orange portions of the figure level by level and present the proof documents to the users in order of height. It's significant to remember that the Merkle proof has two main components

1. The direct parent nodes (i.e., B and D) of this user are not extracted.
2. Provide the root node, i.e. Merkle root.

Taking the volume of 10 million users as an example, the height of the tree can be calculated as Log2(10,000,000) = 23.2534966642 based on the mathematical formula, which gives the height of the tree as 24 levels. Therefore, the nodes in the graph that are intentionally not provided to users will be 24 - 2 = 22.

Merkle tree is a complete binary tree, which allows us to calculate all of the information about its parent node by simply knowing the left and right nodes. Two parts make up this complete information: the balance data and the hash data.

1. Balance Data: The parent node data can and can only be split to its lower left and right nodes.
2. Hash Data: Only balance data, tree hierarchy data, and child node hash data will be present for each node (each node keeps summary data of the left and right nodes below it).

The validation of the Merkle tree is computed by deriving the B and D and verifying that

1. the balance is in accordance with the splitting principle; and
2. the hash is legal.

By utilizing a hash summary function, the Merkle tree enables users to determine whether they are a part of the entire tree without having to be aware of every purple node in the graph. The Merkle proof is exclusive to that user. For instance, a 24-level Merkle tree requires an array of 23 elements to verify the user's balance information, and this array can only confirm that the user's balance proof is accurate.

The user cannot reconstruct the entire tree based on his or her fragmented information as long as they do not obtain more than half of the total number of users. As a result, the Merkle tree protects both user privacy and the company's ability to prevent the leak of information about the company's overall assets.

Validating Your Bybit Account

There are 2 methods available for you to validate your Bybit account and to check the validity of funds.

Platform Validation Tool

This method is the first and only one in the entire network, and it will show the node derivation process of Merkle Tree validation in an intuitive graphical manner on the company's platform.

Self Validation Tool

The company's Merkle tree generation source code and validation code are openly available on github to assist users in programming their own validation. The Merkle tree calculation process involves a huge amount of user calculations, which are usually implemented by big data and Java. 

*An open Java code means that it is open to users without holding back any information.

Bybit has open-sourced the following code for professional users to validate their own Merkle Tree proof file by copying it from their proof of reserves page to their own "sticky" version of the system via the Copy Data button and storing it as a file named myProof.json to local disk.

Applications of Merkle Trees in Blockchain

Merkle tree and Merkle root structures have already been widely adopted across many different blockchains and cryptocurrency platforms. The following details three such applications.

Bitcoin

Bitcoin uses Merkle trees in several ways, which makes these trees integral to the entire Bitcoin platform. In fact, these trees are present in every Bitcoin block header. The hash for every transaction that's available within the block is placed in the header. When it comes to Bitcoin, the Merkle root is important for mining as well as verification.

Mining

Bitcoin blocks consist of headers that contain metadata as well as an extensive list of transactions. This list is usually larger than the block's header. Miners hash data to create an output that adheres to specific conditions, which is necessary when validating a block. The miners can make trillions of separate attempts before they find a valid block. Every attempt requires a number in the header of the block to be changed. Even though thousands of separate transactions can exist in a block, each one must be hashed.

Merkle roots allow miners to make this process much more efficient. When the mining process begins, all that's necessary is for the transactions to be made into a Merkle tree, after which the root hash can be placed within the block header. At this point, the miner is only required to hash the header of the block, as opposed to the entire block.

Verification

Another aspect of the Merkle root that's used with Bitcoin involves leverage, which focuses on light clients. When a node is being operated on a relatively weak device that has limited resources, users won't be able to download and hash every transaction in a single block. Instead, a Merkle proof can be requested, which is confirmation that a transaction is present in a block. By reducing the number of hashes that need to be performed during the verification process, verification can occur without using as many computing resources.

Ethereum

Ethereum is based on a somewhat modified version of the Merkle tree, which is why it's referred to as the Merkle Patricia tree. Every block within the Ethereum blockchain consists of three Merkle trees, as opposed to one binary tree — which is what happens in Bitcoin blocks. Each of the three roots has its own purpose.

The initial root is considered to be the root of every transaction. As for the second root, it shows the state of the transaction. The final root is the receipt of the transaction. A user can look at a Merkle root to determine if a transaction is found on a specific block, as well as determine what their account balance is.

Hyperledger Fabric

When looking specifically at Hyperledger Fabric, this blockchain platform uses a Merkle tree to compute block data as a hash. The hash value identifies the width of the Merkle tree. Merkle trees on the Hyperledger Fabric platform work just like the ones on the Bitcoin platform.

The Bottom Line

Merkle trees have proven to be highly useful for cryptocurrency platforms that want to make sure their transaction verification process is as easy and efficient as possible. Without this structure in place, verification would be a time-consuming process because the data would need to be transferred throughout the entire network for verification. The platforms that use Merkle trees benefit from less bandwidth and computational power requirements.

Source: What Is a Merkle Tree & What Is Its Role in Blockchain? | Bybit Learn