什么是默克尔树？
默克尔树（Merkle Tree）又叫哈希树（Hash Tree），是一种数据结构，通常是一棵二叉树，它以特定的方式从叶节点逐层向上计算hash值，直到顶部根节点。
欧易默克尔树定义
节点信息
每个树节点存储信息包括: 1. 节点hash值; 2. 用户资产快照覆盖的币种数量（以BTC, ETH, USDT为例）
hash值,{"BTC":"BTC数量","ETH":"ETH数量","USDT":"USDT数量"}be324cf06aee0616b4ec20c3,{"BTC":"1.023","ETH":"0","USDT":"20.2343322"}Hash规则
叶子结点（填充节点除外）
hash=SHA256(nonce+balances)
其中，欧易会给每个用户分配一个唯一的nonce，这个nonce可以在audit页面查询到；balances是用户资产快照覆盖的币种数量组成的json字符串，如：{"BTC":"1.023","ETH":"0","USDT":"20.2343322"}（注意：去除末尾无效0，保留8位精度）
父节点
其中，h1=当前节点的左孩子节点的hash，h2=当前节点的右孩子节点的hash，audit_id=本次审计的ID，height=h1或h2节点的高度
树节点的高度定义：最底部叶子结点高度=1，父节点高度=子节点高度+1，根节点高度最大
填充节点规则
构建一棵完整的Merkle Tree（满二叉树）需要2^n个叶子结点数据，但实际情况数据的数量未必满足且还可能是奇数。在此种情况下，如果一个节点k没有兄弟节点，则自动填充（padding）生成一个兄弟节点k'，该兄弟节点hash(k')=hash(k)，节点k'的币种数量全置零。
例子：
| Hash | balances |
| h1 | {"BTC": 1, "ETH": 1,"USDT": 1} |
| h2 | {"BTC": 1, "ETH": 2,"USDT": 3} |
| h3 | {"BTC": 1, "ETH": 2,"USDT": 4} |
则填充节点h4=h3，存储的blances为{"BTC": 0, "ETH": 0,"USDT": 0}，如图一绿色节点所示：
图一：
父节点的hash = SHA256(h1 + h2+ (h1 BTC数量+h2 BTC数量)+(h1 ETH数量+h2 ETH数量)+(h1 USDT数量+h2 USDT数量)+height)
故：h6 = SHA256(h3 + h4 + (1+0)+(2+0)+(4+0)+height)
如何查看自己的账户资产是否包含在默克尔树中？
验证原理
1. 验证原理：根据欧易默克尔树定义，从用户本身叶子结点开始往上计算父节点hash值，一直到根节点得出hash(root)，对比步骤1中获取到的默克尔树路径中根节点的hash值，如果二者相等则验证通过，不等则验证不通过。
2. 例子：结合图一和下面的json文本，依据用户本身叶子节点h3和提供的相邻节点h4信息可以计算出父节点h6的hash，再和提供的相邻节点h5信息可以计算出父节点h7的hash，然后和默克尔树路径数据中提供的根节点h7信息对比hash值是否相等即可完成验证。
默克尔树路径数据json文本：{ "self": { "balances": { "BTC": "1", "ETH": "1", "USDT": "1" }, "nonce": "aa8442ee975df827dc14e527e3ea01db71fe5a6cfe867d77f6a4148fc492743c", "hash": "ca080cc4b04630c9e667e3177be7b093af743101a300cd737dd2da6dbe801be6", "type": 1, "height": 1 }, "path": [{ "balances": { "BTC": "1", "ETH": "2", "USDT": "3" }, "hash": "7d16e6b5203299b85498aa35b964c83903a933d549f99ff3ca8b20c243c2be3e", "type": 2, "height": 1 }, { "balances": { "BTC": "1", "ETH": "2", "USDT": "4" }, "hash": "4d6376b3a51693be961dd402b620c3f2536cb3f7275629fa23e2d1c6c7b319db", "type": 2, "height": 2 }, { "balances": { "BTC": "3", "ETH": "5", "USDT": "8" }, "hash": "af1787033e8d32d600e2e40dc616c1f8d4271e1c182ed57b6e9585e1ac5aa959", "type": 3, "height": 3 }]}验证步骤：1. 登陆您的欧易账户，点击“资产管理”，进入“审计”可直接查看近期审计，点击“详情”可查看您审计时的数据。
2. 如果您想进一步手动验证您的资产已被包括在默克尔树中，可以参考验证步骤进行操作。点击“复制数据”按钮来获得手动验证需要的数据。
3. 点击“复制数据”后，打开文本编辑器（如：记事本），粘贴数据并保存为一个 json 文件。
具体操作：
Mac : 打开终端程序（终端应用），输入 touch merkle_proof_file.json，创建一个 json 文件。文件默认保存在系统 desk 中，可打开访达搜索 merkle_proof_file.json 找到此文件。打开此 json 文件，粘贴复制的数据，并保存。
Windows: 双击打开文本编辑器（如：记事本），并粘贴复制的数据，保存为 json 文件。
在我们的例子中，文件名称为 merkle_proof_file.json。默克尔树路径数据 json 文本如下图所示：
{ "self": { "balances": { "BTC": "1", "ETH": "1", "USDT": "1" }, "nonce": "aa8442ee975df827dc14e527e3ea01db71fe5a6cfe867d77f6a4148fc492743c", "hash": "ca080cc4b04630c9e667e3177be7b093af743101a300cd737dd2da6dbe801be6", "type": 1, "height": 1 }, "path": [{ "balances": { "BTC": "1", "ETH": "2", "USDT": "3" }, "hash": "7d16e6b5203299b85498aa35b964c83903a933d549f99ff3ca8b20c243c2be3e", "type": 2, "height": 1 }, { "balances": { "BTC": "1", "ETH": "2", "USDT": "4" }, "hash": "4d6376b3a51693be961dd402b620c3f2536cb3f7275629fa23e2d1c6c7b319db", "type": 2, "height": 2 }, { "balances": { "BTC": "3", "ETH": "5", "USDT": "8" }, "hash": "af1787033e8d32d600e2e40dc616c1f8d4271e1c182ed57b6e9585e1ac5aa959", "type": 3, "height": 3 }]}4. 下载欧易提供的开源验证工具（MerkleValidator）
5. 将开源验证工具和步骤 3 中保存的 json 文件存放到同一个文件夹，在我们的例子中，文件储存在Downloads 中，文件夹名称为 proof-of-reserves，截图如下:
6. 打开终端程序（Mac系统：终端应用，Windows系统：cmd应用）
7. 在终端程序中输入 cd ~/Downloads/proof-of-reserves 命令，进入下载的软件包目录
8. 输入以下命令就可以验证您的数据
Mac
./MerkleValidator --merkle_proof_file merkle_proof_file.json
Windows
MerkleValidator.exe --merkle_proof_file merkle_proof_file.json注：如果您使用的是 Mac 系统，在此步骤中遇到安全设定的问题，可到 系统偏好设置 -> 安全性&隐私 -> 通用 ->点按锁按钮以进行更改 -> 允许从以下位置下载的 App：App Store和被认可的开发者 -> 给予工具权限。
9. 查看结果
1）如果您的数据正确，执行结果如下，提示“Merkle tree path validation passed”
2）如果您的数据错误，执行结果如下，提示“Merkle tree path validation failed”
10. 您也可以参考开源验证工具的代码和欧易默克尔树定义（参考“什么是默克尔树”章节），自行写程序验证步骤2获取到的路径数据，确认自己的资产被包含在此次审计生成的默克尔树中。
推荐阅读：
评论