How do I verify assets in the OKX Merkle tree? (Merkle Tree V2)

Applicable to audit period after March, 2023

What's a Merkle Tree?

A Merkle Tree (or Hash Tree) is a data structure, which is normally a binary tree. It uses predefined functions to calculate hash value of a node from bottom up, to the top root node of the tree.

Node Information

Every tree node stores such information:

• Hash value of the node
• Crypto currency amount of a user captured by the audit snapshot (take BTC, ETH, USDT as an example)

  hash value,{"BTC":"BTC amount","ETH":"ETH amount","USDT":"USDT amount"} be324cf06aee0616b4ec20c3,{"BTC":"1.023","ETH":"0","USDT":"20.2343322"}

Hash Rule

• Leaf Nodes (except padding nodes)

  hash=SHA256(nonce+balances)

  OKX will assign one unique __nonce__ for each user, which can be found on the user's audit page; __balances__ is a json String composed of users' assets and amounts that were captured by the audit snapshot, for example: {"BTC":"1.023","ETH":"0","USDT":"20.2343322"} (NOTE: need to get rid of the trailing zeroes, and keep 8 decimals of precision)

Parent Nodes

__h1__=Hash of the current node's left child node, __h2__=Hash of the current node's right child node, __audit_id__=ID of the current audit, __height__=the height of node h1 (or h2) Definition of height: height of the bottom leaf node=1, height of a parent node=height of its child node + 1, root node has the maximum height

Splitting Node Rule

To protect the privacy of customers, OKX will randomly split user assets into two nodes, with the random range between 0 and 1. For example, if a user's assets are: {"BTC": "10.2", "ETH": "4", "USDT": "5"} and the random number is 0.6, the user's assets will be split into 60% and 40%.

During the subsequent generation of the Merkle tree, the split leaf nodes will be randomly scrambled to distribute them to different positions in the tree.

Padding Nodes Rule

To construct a full Merkle tree (a full binary tree), it requires 2^n leaf nodes, but the actual data might not meet such requirement and there could also be an odd number of data. In such circumstances, if node k doesn't have sibling nodes, one sibling node k' will be automatically generated as a padding node, such that hash(k')=hash(k), and the asset amounts will be set to 0 for all currencies.
e.g.

In this example, padding node h4=h3, and balances stored in the node is {"BTC": 0, "ETH": 0,"USDT": 0} as shown in Picture 1 (green node): *Picture 1* So: h6 = SHA256(h3 + h4 + (1+0)+(2+0)+(4+0)+height)

How do I verify if my assets are included in the OKX Merkle tree？

Verification theory

According to the definition of the OKX Merkle tree, you can compute the hash value of a parent node by working your way up from the bottom, using the hash values of its left and right child nodes. Eventually, you will obtain the hash value of the root node. You can then compare this calculated hash value of the root node with the one obtained from the Merkle tree path root node. If they match, the verification is successful; otherwise, it fails.
Example: refer to Picture 1 and below text, based on user's self node h3 and provided its sibling node h4, the hash of their parent node h6 can be calculated, and provided h6's sibling node h5, the hash of their parent node h7 can be calculated, then compare h7's hash value with the one collected in the merkle tree path root node and see whether they are identical to complete the verification process.
Merkle tree path data text:

Note: OKX has introduced net asset snapshot when generating the Merkle tree. A debt (e.g. negative equity) will be recorded in the snapshot if the user has borrowed assets. You may refer to here for more details.

Verification steps

1. Login to your OKX account, go to Asset > Audits to view recent audits, select Details to view your audit data.
   Select Assets and View details for better data audit understanding

2. You can also manually verify your assets in the Merkle tree by selecting Copy data
   Select Copy data for the manual verification process

3. Open the text editor (e.g. notebook) , paste and save the json String as a json file.

Operational steps

Mac: Open the terminal, enter command touch merkle_proof_file.json, and then a json file will be created. The file is saved in the system desk by default. You can open Finder and search for merkle_proof_file.json to find this file. Open this json file, paste the copied data, and save it.
Windows: Double-click to open a text editor (e.g: notebook), paste the data and save it as a json file.
In our case, we name the file "merkle_proof_file.json". Merkle tree path data json text is shown as below：
{
"hash": "7e5a588806ff1de23f81e3a092860de43367fb4ea5503a53d95a5bc36d77e0c2",
"nodes": [
{ "balances": { "BTC": "0.49997703", "ETH": "0", "USDT": "16.62437479" },
"hash": "4087972e6b4bd3897c19f76b94b27db8eaf19f0d27d1b73e18297c18c850c3c1"
},
{ "balances": { "BTC": "0.40002297", "ETH": "0", "USDT": "12.18752303" },
"hash": "da14bd34c8d933781b8ec20a7e16109d0d650306b049da52c755437c4f7ec5e5" }
],
"nonce": "b6f6ea7584742839791ab923f4f1980d7ca3ff7c5d3f3fd9cc2a18c598503553",
"totalBalances": { "BTC": "0.9", "ETH": "0", "USDT": "28.81189782" }
}

4. Download the "Full Merkle Tree" files under Liability report and unzip the downloaded file to get a "Full Merkle Tree file".
   Select download to get the report

5. Download the OKX open-source verification tool (MerkleValidator)

6. Save OKX open-source verification tool (MerkleValidator) and the two data files (merkle_proof_file.json, full-liabilities-merkle-tree.txt) in the same folder. In our case: we put the tool as well as the data file under folder Downloads, named proof-of-reserves, as shown below:
   

7. Run the command and locate the directory of the downloaded folder. In our case, enter the command: cd ~/Downloads/proof-of-reserve

8. Type the command below and enter to start the verification:
   Mac
   ./MerkleValidator --merkle_file full-liabilities-merkle-tree.txt --user_info_file merkle_proof_file.json
   Windows
   MerkleValidator.exe --merkle_file full-liabilities-merkle-tree.txt --user_info_file merkle_proof_file.json
   Note: If you are using Mac and encounter "cannot open the tools because the developer cannot be verified", please go to System preferences > Security&Privacy > General > Click the lock to make changes > Allow apps downloaded from App Store and identified developers

9. Check the result
   If the verification passes, the result Merkle tree path validation passed will be shown below:
   

If the verification fails, the result Merkle tree path validation failed will be shown below:

10. You can also refer to the code of the OKX open-source verification tool (MerkleValidator) and OKX merkle tree definition, write a program yourself to verify that your assets are captured by the merkle tree built from the audit snapshot, using the merkle tree path data collected in step 2.