What is the Merkle Tree?
Bitget
2022-11-28 06:49
Dear Global Bitgetters,
Merkle Tree is a data structure, also known as a Hash Tree. Merkle tree stores data in the leaf nodes of the tree structure, and by hashing the data step by step up to the top root node, any changes in the data of the leaf nodes will be passed to the higher level nodes and eventually displayed as changes in the root of the tree.
1. The roles of Merkle tree
- Zero-knowledge proof
- Ensure data immutability
- Ensures data privacy
2. Bitget Limited Merkle Tree Definition
2.1 Node Information
Information stored in every tree node includes:
1. hash value
2. the number of coins contained in the user's asset snapshot (BTC, ETH, USDT for example)
| hash value,{"BTC":"BTC amount","ETH":"ETH amount","USDT":"USDT amount"} 2070b6a5b12f4ea7,{"BTC":1.763,"ETH":362,"USDT":1077200.2274} |
2.2 Hash Rules
Leaf nodes (except padding nodes)
- encryptUid: encrypted UID of the user
- nonce: a unique value assigned to each user
- balances: json string composed of the number of coins in the user's asset snapshot, (note: remove the invalid 0 at the end and keep precision of 8 bits)
- For example: {"BTC":1.763,"ETH":362,"USDT":1077200.2274}
Parent node
- h1: hash of the left child node of the current node,
- h2: hash of the right child node of the current node,
- level: where the parent node lies in
Definition of tree node level: A complete Merkle Tree (full binary tree) requires 2^n leaf node data, leaf node level = n + 1, parent node level = child node level - 1, root node level = 1, leaf node level is the maximum
Padding node rules
A complete Merkle Tree (full binary tree) requires 2^n leaf node data, but the actual number of data may not satisfy and may be odd. In such a case, if a node k has no sibling node, then auto padding generates a sibling node k', and hash(k') = hash(k), and the number of coins of node k' is set to zero.
For example:
|
Hash
|
balances
|
|
hash1
|
{"BTC":1,"ETH": 6,"USDT":10}
|
|
hash2
|
{"BTC":2,"ETH":4,"USDT":8}
|
|
hash3
|
{"BTC":2,"ETH":1,"USDT":12}
|
Then the padding node hash4 = hash3, stored balances are {"BTC": 0, "ETH": 0, "USDT": 0}, as shown in the highlighted node in Figure one.
Figure one
Therefore, hash6 = SHA256 (hash3 + hash3, {BTC: (2+0), ETH:(1+0), USDT:(12+0)}, level)
Verification Principle
1. Verification principle: According to the definition of Bitget Limited Merkle tree, the hash value of the parent node is calculated from the user's own leaf node up to the root node, and the hash value of the root node is compared with the hash value of the Merkle tree in "Verification Step - Step 1", if the two are equal, the verification passes, if not, the verification fails.
2. Example: Combining figure one and the following json text, and based on the user's own leaf node h3 and the information provided by the adjacent node h4, we can calculate out the hash of the parent node h6, and then with the information provided by the adjacent node h5, we can calculate out the hash of the parent node h7, and then compare the hash value with the root node h7 provided in the Merkle tree path data to see if the hash values are equal to complete the validation.
Merkle tree path data json text:
Verification Steps
1. Log in to your Bitget account, click "Asset Overview - Proof of Assets", and go to "Proof of Assets" to directly view the recent audits. The data at the time of your audit will be expanded by default to show.
2. If you want to further manually verify that your assets are included in the Merkle tree, you can do so by following the verification steps. Click the "Download Data" button to get the data needed for manual validation, and a file with the default name: merkel_tree_bg.json will be downloaded
3. Specific operations:
In our example, the file name is merkel_tree_bg.json. The text of the merkle tree path data json is shown below:
4. Download the open source verification tool proof-of-reserves-*.zip provided by Bitget Limited.
5. Unzip proof-of-reserves-*.zip file to the current directory and store the merkel_tree_bg.json file saved in step 3 to the same folder. In our case, the file is stored in Downloads, and the folder name is proof-of-reserves, and the screenshot is as follows:
6. Open the terminal program (Mac system: terminal application. Windows system: cmd application)
7. Enter the command cd ~/Downloads/proof-of-reserves-* in the terminal program, and enter the downloaded package directory
8. Verify your data by entering the following command
Mac/Linux
Windows
Click the start.bat file
Note: If you are using a Mac system and encounter problems with security settings during this step, go to System Preferences -> Security Privacy -> General -> Tap the lock button to make changes -> Allow apps downloaded from: App Store and approved developers -> Give permission to tools.
If the following problem occurs, zsh: permission denied: . /start.sh, execute the following command
9. View results
(1) If your data are correct and the verification passed, then the result is "Consistent with the Merkle tree root hash. The verification succeeds".
(2) If your data are wrong and the verification fails, the result is "Inconsistent with the Merkle tree root hash. The verification fails".
10. You can also refer to the Bitget Limited open source verification tool code and Merkle tree definition (refer to the "What is the Merkle Tree" section) and write your own program to verify the path data obtained in step 2, or check to make sure your assets are included in the Merkle tree generated by this audit.
Bitget Team