The Role of Merkle Tree in Blockchain and Exchanges for Proof of Reserve

What Is a Merkle Tree?

Have you ever wondered what the fuzz about the Merkle tree system is? It has been so huge as most centralized exchanges are implementing it to restore user confidence after the collapse of the second biggest centralized crypto exchange (FTX). A Merkle tree is a particular kind of structure that may be used to quickly check the accuracy of data in a collection Most of the components in this structure are hash functions, which are widely employed in blockchain technology. In other terms, a Merkle tree is a mathematical data structure that represents a summary of all the transactions in a block of data and is made up of hashes of various blocks of data. Additionally, it enables quick and safe content verification across a vast body of data. Additionally, it aids in confirming the accuracy and completeness of the data.

Diagram according to Bitpanda explaining a Merkle tree

The blue boxes at the bottom - “m0”, “m1”, “m2” and “m3” - represent data. This data “m” is not considered a part of the Merkle tree. Now, if the value in such a box - with a lower-case letter “m” - is hashed, you receive a hashed value, indicated in the yellow box above with a capital letter “M”.

Ralph Merkle came up with the idea for the Merkle tree in the 1980s. Because peer-to-peer (P2P) networks require information to be exchanged and independently evaluated, Merkle trees are frequently employed in P2P networks.

Merkle trees allow transactions to be confirmed without needing any data at all, which aids in reducing CPU processing and enables increased security. All transactions are paired together while examining the Merkle tree's structure. A calculated hash for each pair is kept in the parent node and is stored there. Additionally, these nodes are paired together before having their hash stored on the following level. Until the Merkle tree's root is reached, this procedure continues.

TL;DR: A Merkle tree enables quick and safe content verification across a vast body of data. You can track the movement of transaction using the Merkel tree system.

What is a Merkle root?

A Merkle root comprises the sum of all the hashes for each transaction in the block. The block header contains the Merkle root. With this method, it is unnecessary to download the full block chain in order to safely validate that a transaction has been approved by the network (and to determine the number of confirmations). Instead, just the tiny block headers and Merkle tree need to be downloaded. Currently, Bitcoin does not make advantage of this capability, but it will in the future.

In order to better understand the concept of a Merkle tree, it is important to explain cryptographic hash as Merkle tree relies on this to operate.

Any type of arbitrary data, regardless of length, must be translated into an output with a defined size using a hash function. Since it performs a cryptographic function, cryptography makes extensive use of it.

The efficient hash functions are distinguished by their unique characteristic, which prevents them from being reversed. It is a one-way function that can only be used in this manner.

Hashing has multiple uses including

• Password protection
• File integrity checks and verification
• Cryptocurrency

There are multiple hash families out there including Message Direct(MD), Secure Hash Function(SHF), and RIPE Message Direct(RIPEMD).

The key properties of hash functions include:

• Deterministic : This implies that the output will be the same for every given input. To put it another way, if you run the same input through the hash function 100 times, the results will always be the same.
• Pre-Image Resistant: This indicates that the hash result, once created, has no information about the input. This feature is crucial since it provides the most crucial information.
• Computationally Efficient: This indicates that it will swiftly produce the hash output regardless of how lengthy and intricate the input is.
• Cannot be Reversed Engineered: This indicates that it is safe. As is well known, non-reversible functions serve as the foundation for the creation of cryptographic hash functions. The result is produced using a reduced set of mathematical equations and a non-reversible procedure. Technically speaking, the inverse operation is not supported by the hash function.
• Collision Resistant: This formulation allows for an endless number of inputs. The output, which is now a fixed-length, must now be unique each time. The outputs are finite numbers because of the restriction on fixed length, even if finite numbers have enormous value.

The three node types that can be found in a Merkle tree include:

• Leaf node — Consists of hash values for transaction data. Every transaction that's located in a block consists of hashed data. The hash value is then stored in leaf nodes.
• Non-leaf node — Made up of hash values of their children. These are essentially intermediate hash values that are used until the process reaches the tree root.
• Root node — The root of a Merkle tree is stored directly in the block header.

Exploring The Potential of a Merkle Tree in Blockchain

Because they provide rapid and simple verification in a way that is not achievable with other systems, Merkle trees have established themselves as vital for blockchain technology. Developers may use these Merkle trees to compress extraordinarily big data sets by removing any extraneous information and converting the data that is left 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

Application of Merkle Tree in Blockchain

There are already numerous blockchains and cryptocurrency platforms that use Merkle tree and Merkle root structures. These applications include the information below.

Bitcoin

Merkle trees play a key role in Bitcoin, which makes them essential to the whole system. In fact, each Bitcoin block header contains one of these trees. The header contains the hash for each transaction that is present in the block. The Merkle root is critical for both mining and verification in the context of Bitcoin.

Mining

In addition to a long list of transactions, bitcoin blocks often include headers that carry metadata. Typically, this list exceeds the block's header. When verifying a block, miners must hash data to produce an output that meets certain criteria. Before they discover a genuine block, the miners may try trillions of different combinations. Every effort necessitates changing a number in the block's header. A block can include hundreds of distinct transactions, yet each one needs to be hashed.

Miners may greatly increase the efficiency of this procedure by using Merkle roots. All that is required before mining can start is for the transactions to be organized into a Merkle tree, at which point the root hash may be added to the block header. At this stage, the miner just has to hash the block's header rather than the full block.

Verification

Leverage, a component of the Merkle root that is utilized with Bitcoin, is focused on light clients. Users won't be able to download and hash every transaction in a single block when a node is running on a relatively weak hardware with few resources. Instead, a Merkle proof, which provides verification that a transaction is present in a block, can be asked for. Verification may be carried out more efficiently by lowering the quantity of hashes that must be run during the procedure.

Ethereum

The Merkle Patricia tree, on which Ethereum is built, is a slightly modified version of the Merkle tree. On contrast to Bitcoin blocks, which only include one binary tree, each block in the Ethereum blockchain has three Merkle trees. The three roots each have a distinct function.

Every transaction's root is regarded as being the first root. Regarding the second root, it displays the transaction's state. The transaction's receipt is the last root. A user can check a Merkle root to see if a transaction is found on a particular block and to see how much money is in their account.

Hyperledger Fabric

With regard to Hyperledger Fabric particularly, this blockchain technology computes block data as a hash using a Merkle tree. The Merkle tree's width is determined by the hash value. Merkle trees operate similarly on the Hyperledger Fabric platform and the Bitcoin platform.

Implementing Merkle Tree Systems by Central Exchanges

We can now examine how the Merkle tree, based on how it can promote transparency, may be utilized by central exchanges to promote transparency, foster user confidence, and serve as a proof of solvency without violating users' privacy. Exchanges only need to demonstrate the total quantity of deposits and the possession of the private keys to the assets in order to demonstrate their solvency.

The Merkle tree method entails creating a Merkle sum tree from the database of customer balances. Each node in a Merkle sum tree is a (balance, hash) pair. Individual customers' balances and salted username hashes are represented by the leaf nodes in the bottom layer. The balance and hash of each higher-layer node are equal to the total of the two balances and hashes below it.

A Merkle sum proof is a "branch" of the tree, like a Merkle proof, made up of the sister nodes that line the path from a leaf to the root. Each user would receive a Merkle sum verification of their balance from the exchange. The user would then be certain that their balance was appropriately counted toward the final sum. This design offers much less privacy leakage than a fully public list, and it can be made even more secure by randomly rearranging the branches after each root publication.

Merkle Tree development for Dex to improve user confidence as implemented by Loopring.

To achieve the implementation of the Merkle tree transparency process, Protocol 3.0 by Loopring which is still on its Beta test stage uses zero-knowledge proofs to shift nearly all data off-chain and off-chain calculations for all requests (zkSNARKs). Data is stored in a Merkle tree using an account model. A person can only have one account, which is linked to their Ethereum address. The user's full trade history information may be retained in this account, along with any token balances that the exchange chooses to support. The Merkle tree is changed by requests, and on-chain proofs are employed to verify state changes. In order to maximize efficiency, requests are organized into blocks. The number of requests that may be contained in a block is limited; otherwise, proof verification on-chain would become inefficient. Regardless of the number of requests in a block, the cost of confirming a proof is always the same.

The DEX operator has a certain length of time after committing the block to the chain to submit the block's evidence in order to generate proofs. The proof submission and block commit are carried out separately since the proof generating currently takes some time. By allowing the DEX operator to commit the block first without having to wait for the proof to be created, other operators can create additional blocks that expand upon the state of the most recently committed block, enabling simultaneous proof generation. The proof can then be transmitted on-chain by the operator to confirm the state changes made in the block. Operators that don't promptly present reliable proof are punished and the status is quickly restored back to lawful. While executing this acton the only thing saved on-chain is the Merkle tree root. Users can use this to demonstrate (using a Merkle proof) that they own a specific number of tokens listed on the DEX.  

About Pontem

Pontem Network is a product studio building foundational dApps for Aptos. Our products include:

• Pontem Wallet -- the best Aptos wallet
• Liquidswap -- the first DEX (AMM) for Aptos
• Move Playground -- a simple browser Move code editor
• Move IntelliJ IDE plugin for developers
• ByteBabel -- a Solidity-to-Move translator, and the first EVM for Aptos