中心化交易所如何用Merkle Tree实现资产储备证明
最近，在cz几条推特的轰炸之下，全球第二大交易所FTX因为挪用用户资产，被挤兑后迅速宣告破产，由此导致了用户对CEX资产储备不透明的强烈不信任感。而cz提出CEX要做Merkle Tree的资产证明，并计划几周内发布，其他交易所纷纷表示跟进。
那么，什么是Merkle Tree，中心化交易所应如何通过Merkle Tree实现自身资产储备≥用户资产？本文将从技术角度讨论并给出完整的证明方案与代码实现。
我们以ETH为例，当我们要实现资产证明时，我们要证明的是链上资产ETH总额≥交易所用户ETH资产总额。因此，证明分为链上与链下两部分。
链上证明
链上证明比较简单，因为交易所通常会将所有用户充值汇总到几个地址，列出这几个地址在链上自查即可。为证明这些地址是交易所拥有，可用私钥签名一条简单的消息即可，签名只需要发布一次。
链下证明
链下证明就比较复杂，需要用到Merkle Tree。
Merkle Tree（默克尔树）是一种二叉树，其最底层叶子节点存储数据以及数据的哈希，而每上一层节点则存储两个子节点的哈希，最后由根节点的哈希保证这个Merkle Tree的任何节点数据的完整性。 因为修改任何一个叶子节点的数据都会导致根节点的哈希变化，因此，使用Merkle Tree可以保证，只要发布了Root，树的所有子节点均不可修改：
┌─┐
└─┘
┌───────┴───────┐
┌─┐ ┌─┐
└─┘ └─┘
┌───┴───┐ ┌───┴───┐
┌─┐ ┌─┐ ┌─┐ ┌─┐
└─┘ └─┘ └─┘ └─┘
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
└─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘ └─┘
假设交易所全部5个用户持有若干不等的ETH，按用户ID可表示如下：
User ID, Balance
12345, 12.34
23456, 23.45
34567, 34.56
45678, 45.67
56789, 567.89
可将用户ID视为索引，构造Merkle Tree并计算Merkle Root：
root
▲
┌──┴──┐
...............................................
▲ ▲ ▲ ▲ ▲
┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌──────┐
... │12.34│...│23.45│.......│34.56│ │45.67│.......│567.89│...
└─────┘ └─────┘ └─────┘ └─────┘ └──────┘
index: 12345 23456 34567 45678 56789
交易所发布Merkle Root后，可确保所有子节点——即用户ID对应的子节点余额均完全确定下来，每个用户均可根据自己的用户ID查询余额是否相符，只要有任何一个用户发现自己的余额在指定索引的位置不符，即可判断交易所造假。
为了证明交易所的用户资产储备总额，交易所也不得不公开所有子节点的索引与余额，这样任何第三方才能计算出用户资产总额，并根据交易所公布的Merkle Root确认这些子节点数据没有被篡改。
然而，这样一来，每个用户的持币余额就完全公开了，可以很容易地对持币大户进行跟踪。因此，我们需要一种机制将一个用户的余额拆成若干份，并存储在多个不同的索引地址。为了确保索引不会冲突，可使用Sparse Merkle Tree，用以太坊地址作为索引。对Sparse Merkle Tree不熟悉的同学可以参考针对以太坊实现的一种Sparse Merkle Tree。
例如，对于用户45678持有的45.67余额，我们可以分为3份：
- 14.72783542
- 7.83947710
- 23.10268748
然后，根据ID计算出确定的若干地址索引：
- 6f1cc8a44919eb1c6576d6819b37ac9ab288ecb5
- 9759bf1d54e5f25f135d7674dea3bef0d24fb153
- 46daefba020f7e5bfa957b13aeaa4b72034a90fd
这样我们就可以把这个用户的余额分别存放在3个子节点上。把所有用户都处理一遍，假设结果如下：
add user asset: 12345 = 12.34
set 8038ee8dc0ee24097883f69a2ffe7946264fa377: 5.24622934
set cbd2331a281f6cba5f044f96f9f54633e6e8fdfe: 3.38555784
set b78f6fbb6226f453e5b4f43e22f2a653a2c5af43: 3.70821282
add user asset: 23456 = 23.45
set 4aa9352b9fe9df0554a139182dcefe09e543ea7e: 7.71339164
set c6c0132de4dfe36b44b07d6c3f3c8310f05c2147: 4.75253454
set bb17f54d8e86cd9cb8b22e4f28ccd8e9570d7717: 10.98407382
add user asset: 34567 = 34.56
set d57a42e1fd79bf0e77437140878cd0579caf8c8d: 15.26664377
set 9cffd3be18b70ddb743b5a1f5dc35967a206a6b6: 8.78207399
set f4fe734bd736144ec5b1bfcabe456431e4cd0eae: 10.51128224
add user asset: 45678 = 45.67
set 6f1cc8a44919eb1c6576d6819b37ac9ab288ecb5: 14.72783542
set 9759bf1d54e5f25f135d7674dea3bef0d24fb153: 7.83947710
set 46daefba020f7e5bfa957b13aeaa4b72034a90fd: 23.10268748
add user asset: 56789 = 567.89
set 7fe3990369fa0d3cf8dc7abb2cf817ddbf548b11: 226.26887015
set 790d84b35986cec20c006ef487e708900220c641: 93.97072264
set 549e751887e4e9ce2a490a5dc1995a7a1e89e205: 110.57987563
set 15844c96b44bd87dbd6f0ab275ddd815d51e62eb: 40.99473402
set 48e1a485f5e939cbe051128028c7bf38e9a630c3: 33.07176793
set b4d6711f896aeac3675827f3f51c11837341e23a: 63.00402963
我们就可以得到一个地址索引=余额的列表。对地址进行排序，以便让同一个用户的多个地址不再连续列出，得到地址/余额的CSV如下：
address, balance
15844c96b44bd87dbd6f0ab275ddd815d51e62eb, 40.99473402
46daefba020f7e5bfa957b13aeaa4b72034a90fd, 23.10268748
48e1a485f5e939cbe051128028c7bf38e9a630c3, 33.07176793
4aa9352b9fe9df0554a139182dcefe09e543ea7e, 7.71339164
549e751887e4e9ce2a490a5dc1995a7a1e89e205, 110.57987563
6f1cc8a44919eb1c6576d6819b37ac9ab288ecb5, 14.72783542
790d84b35986cec20c006ef487e708900220c641, 93.97072264
7fe3990369fa0d3cf8dc7abb2cf817ddbf548b11, 226.26887015
8038ee8dc0ee24097883f69a2ffe7946264fa377, 5.24622934
9759bf1d54e5f25f135d7674dea3bef0d24fb153, 7.83947710
9cffd3be18b70ddb743b5a1f5dc35967a206a6b6, 8.78207399
b4d6711f896aeac3675827f3f51c11837341e23a, 63.00402963
b78f6fbb6226f453e5b4f43e22f2a653a2c5af43, 3.70821282
bb17f54d8e86cd9cb8b22e4f28ccd8e9570d7717, 10.98407382
c6c0132de4dfe36b44b07d6c3f3c8310f05c2147, 4.75253454
cbd2331a281f6cba5f044f96f9f54633e6e8fdfe, 3.38555784
d57a42e1fd79bf0e77437140878cd0579caf8c8d, 15.26664377
f4fe734bd736144ec5b1bfcabe456431e4cd0eae, 10.51128224
交易所计算总额683.91以及Merkle Root值0x61cdf659...c41c40fe，公开CSV文件及Merkle Root后，任何第三方可校验树的有效性，并获得用户资产总额，再与链上对比。对于每一个用户来说，需要根据自己的ID，快照时产生的余额，以及交易所给出的用于生成确定性地址的随机数，可自行验证对应的若干节点余额总和与自己的资产额度完全相等。
这种方式既能保证每个用户可验证自己的资产，又能保证其他人无法推算某个用户的资产，其缺点是计算较为繁琐，需要相应的第三方工具帮助用户校验。
小结
本文给出了一种交易所用户资产的额度证明，并保证不泄漏任何用户的额度。详细代码可参考GitHub源码。