1. What is a Merkle tree?

In order for users to be sure that HTX has the genuine and complete account data of each user, we have built and implemented Merkle Tree as a form of Proof of Reserves (PoR). Using the Merkle tree, all our users can independently and conclusively verify that their assets are held intact on HTX without revealing any information about other users. Users do not need the intervention of a third-party organization. They only need to download their unique recorded ID hash, along with the Merkle root and the proof path, to prove that their assets are held by HTX in a 1:1 ratio.

The Merkle tree, named after its inventor Ralph Merkle in 1979, is a data structure commonly used in cryptocurrencies such as Bitcoin and Ethereum. Through a Merkle tree, multiple data can be combined into one data, allowing for the storage of aggregated data on a larger scale. At the same time, it can prove that the corresponding data is compressed in the aggregated result through cryptographic means. By verifying the integrity of the Merkle Tree root data, one can prove the integrity of all the data that makes up the Merkle tree. The leaves of a Merkle tree are composed of the hash values of all the data in the dataset. Specifically, the leaf structure connects two adjacent hash pairs, groups them together, and then hashes them again to generate a parent hash value. The repeated grouping and hashing process eventually produces the top-level root hash, which is the Merkle root. The hash value of the Merkle root contains the hash value of all the data of the entire Merkle tree. Tampering or changing the data of any node will cause the hash value of the Merkle root to change, which, in turn, guarantees the integrity of the Merkle tree data.

To put it simply, the Merkel tree, named after its inventor Ralph Merkel, is a data structure extensively used in cryptography. It enables the verification of data integrity on a large scale without revealing additional information. It represents various data forms as irreversible hash values. Each user can get their own user proof, which includes the proof path and Merkle root in the Merkle proof, as well as their user hash. Users can use these attributes of the Merkle tree to verify whether their personal information and assets are included in HTX's asset information. At the same time, based on the reserve certificate formed by Merkle-related circuit constraints in the zero-asset certificate, users can verify that HTX's assets (i.e., all user asset data) are calculated exactly from each user's data. This way, users can be sure that HTX holds their assets and has a reserve fund corresponding to each user in a 1:1 ratio. Simply put, users can ensure that all their asset information is accurate through the Merkle tree.

 

2. Merkle tree upgrade:

We have adopted the Merkle tree v2.0 mechanism as a verification proof of 100% reserve.

Before this upgrade, our main verification process was as follows:

1. An anonymous snapshot of the balance of all users was taken to generate a Merkle tree, which contains the encrypted data of assets held by all users of the exchange.

2. The Merkle root was obtained from the last node of the Merkle tree. From the Merkle root, a single hash value (the hash value of all transactions combined) and the total balance of assets at the time of the snapshot were obtained.

3. The digital signature of the wallet address on the HTX Chain was verified to prove the ownership of the address and obtain the total balance of assets that can be publicly verified.

4. Finally, by comparing whether the total balance in the wallet address on the chain is greater than the total assets displayed by the Merkle tree, it is proven that the user assets are supported by 100% reserve funds, demonstrating HTX's ability to redeem user assets.

 

• Upgrade:

We upgraded the original Merkle tree to a sparse Merkle tree. Its huge tree composition and multiple empty hash roots have stronger fault tolerance. In addition, a larger tree can accommodate more users. We have increased five types of currencies in the original version to 200 types of currencies. In addition, we have added the total positive assets and total liabilities of users for simultaneous hashing. The sparse Merkle tree constructed according to this rule can guarantee the uniqueness of each node of the user and completely cover all assets related to the user. The details of the sparse Merkle tree are as follows.

 

How to perform a Merkle proof for a single user:

From the interactive terminal, users can verify their user IDs and download their unique userproof files. By reading their userproof files into the verification terminal, users can perform a Merkle proof to verify that all their asset information is indeed owned by HTX.

What's in the userproof file?

A userproof file contains the user's index position in the sparse Merkle tree, the encrypted ID hash of the UID, all currency property information, root hash, and the proof path specific to that user. Using the asset information and ID hash to recalculate the leaf node hash and combining it with the verification path hash, users can calculate and compare the final root, completing the Merkle proof. (Illustrated in charts)

 

3. Sparse Merkle tree

Compared to the previous version, we upgraded our Merkle tree to the v2.0 version, known as the sparse Merkle tree.

Figure 1

The size of the sparse Merkle tree is predefined, and empty nodes are not stored when each leaf node is stored in the sparse Merkle tree. This means that we only need to store the user nodes that have been set, as shown in Figure 1.

Its advantages include:

1. Strong scalability: As the amount of data increases, the height of the traditional Merkle tree may increase, resulting in an increase in the amount of calculation required for verification. Sparse Merkle trees can reduce the height of the tree by merging empty branches, which improves the efficiency and scalability of verification to some extent.
2. Dynamic updates: For a regular Merkle tree, if the data needs to be updated, the hash value of the entire tree needs to be recalculated. Sparse Merkle trees can support the insertion and deletion of dynamic data more efficiently. Only the hash values of leaf nodes and a small part of intermediate nodes need to be updated, without rebuilding the entire tree.
3. Fast verification: The structure of the sparse Merkle tree makes it possible to verify data integrity more quickly in some cases, because there is no need to traverse the entire tree layer by layer.

To add a user to the sparse Merkle tree, we use the leaf hash we calculated in the previous step and determine the index position where we want to add the leaf node. Based on the user's index position, we can get the user's proof path, which is used to verify whether the user is actually in the tree structure and save your asset data.

 

4. How are leaf nodes formed?

• What is Hash256 calculation?

For a message of any length, SHA256 will generate a 256-bit hash value, equivalent to an array with a length of 32 bytes, usually represented by a hexadecimal string with a length of 64. Specifically, 1 byte = 8 bits, and the length of a hexadecimal character is 4 bits.

For example, for the message:

BlockChain

Through Hash256, you can get a hexadecimal value with a length of 64:

3a6fed5fc11392b3ee9f81caf017b48640d7458766a8eb0382899a605b41f2b9

 

This hash value can guarantee one-way (the unknown original message cannot reversely calculate the hash value) and avoid collision (it is difficult for different messages to have duplicate hash values).

 

• Composition of leaf nodes

We start by encrypting the UID to obtain the hash value corresponding to each user ID:

Figure 2

By using hashID, the unique identifier, we can access each user's unique asset and personal information. Additionally, Hash256 does not have the possibility of linear time inverse calculation, which means that it is impossible for others to violently calculate your hashID - unless they knows your UID.

 

Furthermore, the hash value of the user's leaf node is calculated by hashID and all currency information asset commitments, in addition to the user's total assets and total liabilities. This ensures that the unique hash itself contains all of the user's account information.

 

You can understand this calculation process from the diagram:

Figure 3

• Why don't hashes repeat?

Since each user has a unique UID, their hashID is necessarily unique. In most cases, it is unlikely for all asset-related account information between different users to be exactly the same. Therefore, the probability of their hash values being identical is extremely low. Moreover, the uniqueness guaranteed by hashID makes it highly improbable for two account IDs to be the same.

• Why can't other users get your hash?

One of the core security properties of SHA256 is collision resistance, meaning it is very difficult to find two different inputs that produce the same hash. Deriving the original input from the hash value involves finding all possible inputs that satisfy the hash value. This is called "reverse mapping" or "reverse hashing." However, in the current computing environment, achieving reverse calculation of SHA256 is extremely difficult because hash functions are designed to prevent reverse calculation. Therefore, only when others fully grasp your account attributes and UID can they obtain your hash value.