& C8 K6 M; S& G( F. B
更有野心的是,交易所可以建立一个未经储户同意无法提取储户资金的系统。我们可以尝试探索「不作恶」有职业素养的 CEX 与「无法作恶」却泄漏隐私的低效链上 DEX 之间的界限。这篇文章将深入探讨让 CEX 更加去信任的历史尝试,与其采用技术的局限性,以及一些依赖 ZK-SNARKs 等先进技术的有力手段。2 d+ C2 t$ m6 ^ z9 L
余额表和 Merkle 树:传统的可偿付证明交易所试图用密码学来证明自己没有欺骗用户的最早尝试可以追溯到很久以前。2011 年,当时最大的比特币交易所 MtGox 通过发送一笔移动 424,242 个 BTC 到预先公布地址的交易来证明他们拥有该笔资金。2013 年,大家开始讨论如何解决该问题的另一面:证明用户存款的总规模。如果你证明用户的存款等于 X (负债证明 proof of liabilities),并证明拥有 X 个代币的私钥(资产证明 proof of assets),那么就提供了可偿付证明(proof of solvency):你证明了交易所有足够的资金偿还给储户。
1 _" k+ T- i6 ?9 x2 c
提供存款证明的最简单方法是公布一个列表。每个用户都可以检查他们在列表中的余额,而且任何人都可以检查完整的列表:(i)每项余额都是非负的;(ii)总额是宣称的金额。
当然,这会破坏隐私,所以我们可以稍微改变一下该方案:发布一个 列表,并私下给用户发送 salt 值。但即使这样也会泄漏余额与其分布。为了保护隐私,我们采用了后续技术:Merkle 树技术。
0 {9 t) Q8 P! e6 b- o
绿色:Charlie 的节点。蓝色:Charlie 收到用于证明的节点。黄色:根节点,向所有人公布
J- N( t( z1 \$ U3 ?
Merkle 树技术会将用户余额表放进 Merkle 总和树。在 Merkle 总和树中,每个节点都是对。底层叶子节点表示各个用户的余额以及用户名的加盐哈希。在每个更高层的节点中,余额是下面两个节点余额的总和,而哈希是下面两个节点的哈希。Merkle 总和证明和 Merkle 证明一样,是一个由叶子节点到根节点路径上所有姐妹节点组成的「分支」。$ o* C3 o3 x& p- a% \
首先,交易所会向每个用户发送一份其余额的 Merkle 总和证明。然后,用户能够确定其余额作为总额的一部分而被正确地包含。可以在这里找到简单的示例代码。
3 I; T5 B% g* ? W
- # The function for computing a parent node given two child nodes" C* O1 R* ~; d2 B2 \1 o+ ~ Z
- def combine_tree_nodes(L, R):* k0 B. R+ e2 l2 g/ f- p# F
- & o6 r8 M2 z7 m3 f, g3 y* q
- L_hash, L_balance = L/ M: b/ m0 z9 U" D% V5 X5 `1 L- g+ ]
- R_hash, R_balance = R
- assert L_balance >= 0 and R_balance >= 0; K+ s* b! H( B! U! W9 }/ ^
- new_node_hash = hash(& T! |. C1 r( j' t7 c4 g+ i7 s5 N5 F
- L_hash + L_balance.to_bytes(32, 'big') +
- R_hash + R_balance.to_bytes(32, 'big')
- 8 x$ e7 ~% V3 e! h8 p% t
- )
- ) Q; R9 S6 Z6 j3 U( b7 n$ E4 _
- return (new_node_hash, L_balance + R_balance)2 x* M$ \! F0 U6 e5 y
- " n: V- x& w- X1 ~+ Y" G `4 K4 N' i
- # Builds a full Merkle tree. Stored in flattened form where7 D' O8 d) X2 h8 n* q
- 6 E3 p# Q9 ]/ }& N5 n
- # node i is the parent of nodes 2i and 2i+14 k- Q( c7 c* Y5 f) g8 Q" h
- % o6 l5 x: J# ]0 R6 }
- def build_merkle_sum_tree(user_table: "List[(username, salt, balance)]"):7 H! n2 ?0 B2 s6 }$ }0 D- _
- / Q. \# ~' J% x; b7 l* x7 t
- tree_size = get_next_power_of_2(len(user_table))% Y% E& O; H: K( @/ Y5 y6 N
- tree = (
- [None] * tree_size +8 k& B, t( Z$ k& C
- [userdata_to_leaf(*user) for user in user_table] +0 ]+ e2 r1 _( |. G3 C. h2 Q
- [EMPTY_LEAF for _ in range(tree_size - len(user_table))]
- 7 f9 S$ y3 J3 d$ G/ I$ v4 ]; \
- )# t' |' s- x4 F4 H `) \. z
- for i in range(tree_size - 1, 0, -1):4 b( Q9 R' K% `9 n6 s- n8 {
- ' u0 K! O' m8 ^4 B! _, F1 q# D3 M7 e
- tree = combine_tree_nodes(tree[i*2], tree[i*2+1])! t. f, o# x& ~2 a
- ) T7 ]3 j V7 Z. u- Y
- return tree+ X4 K7 N$ u1 L3 i$ }; |
- ; e: }2 w# j. Y% P2 W
- # Root of a tree is stored at index 1 in the flattened form
- 5 p% r. u. ^. W! H( g' h$ c
- def get_root(tree):
- return tree[1]
- & M* I. f% l: ^1 z2 Y/ B
- # Gets a proof for a node at a particular index; D% `! K7 `' W, i6 P3 N3 w" |
- def get_proof(tree, index):% y0 Y2 T6 i$ N5 d. K) F- q
- 3 [+ t9 z& L% L6 O
- branch_length = log2(len(tree)) - 1" ^( U6 I% \. w
- / C! _- C% b9 ^0 [) V. Q
- # ^ = bitwise xor, x ^ 1 = sister node of x, S$ E" D. e* o/ a( [7 d
- index_in_tree = index + len(tree) // 2
- return [tree[(index_in_tree // 2**i) ^ 1] for i in range(branch_length)]
- 7 ]7 s6 b5 U( M
- # Verifies a proof (duh). M+ a! H4 u' E9 X. t
- $ t4 ~+ d. G" A" f5 b
- def verify_proof(username, salt, balance, index, user_table_size, root, proof):
- ; H: p7 D& k0 c8 S
- leaf = userdata_to_leaf(username, salt, balance), A( W4 A3 @% B3 t$ P9 `0 E% r
- branch_length = log2(get_next_power_of_2(user_table_size)) - 1
- % A5 ~$ B1 A- q7 y! ^7 d% d
- for i in range(branch_length):, t1 {( `$ D6 A; |) w" W. ~1 I
- 9 L0 T+ m0 \1 ^. ^/ D
- if index & (2**i):
- leaf = combine_tree_nodes(proof, leaf)
- 1 D. s7 x5 J6 X& _7 U7 Y6 I
- else:
- leaf = combine_tree_nodes(leaf, proof)% }* m- w3 D8 ]# D. y, p
- return leaf == root