叶节点(leaf)存储数据或其哈希值,中间节点(non leaf)是它的两个孩子节点内容的哈希值。只要叶节点有任何变动,都会传递到其父节点,一直到 root。
图片来源:https://en.wikipedia.org/wiki/Merkle_tree
图片来源:https://medium.com/crypto-0-nite/merkle-proofs-explained-6dd429623dc5
K 的 proof 包含了上图中蓝色的部分,即 H(L), H(IJ), H(MNOP) 和 H(ABCDEFGH) ,通过 proof 和 K 可以计算出 root,与真正的 root 比对,如果一致,则说明 K 存在。
这样不需要发送所有的数据便可发现不一致的数据块。
叶节点存储交易哈希,区块头只需存储 Merkle 根,节省了存储空间。Merkle Tree 可支持 SPV(Simple Payment Verification),在不运行完整区块链网络节点的情况下,也能够对交易数据进行检验。
图片来源:https://www.cnblogs.com/bonelee/p/13154709.html
Sparse Merkle Tree (SMT) 可以做不存在证明。
SMT 根据 key-value map 构建。每个叶节点都有一个 key 和 value 以及一个哈希属性,该哈希属性是通过将 key 和 value 哈希在一起获得的。叶节点可通过定长 key 来定位。对于给定的数据,树中只有一个位置可以放置该数据。如果该位置为空,则数据不存在。
为此,SMT 大小固定,有 256 级,key 的长度为 256,叶节点数为 2^256。因为 SMT 中大多数数据都不存在,也不需要存储,所以是 Sparse 的。例如,如果子树只有一个非空节点(绿色),可被该非空节点替代。如果子树的节点都为空(白色),可被空节点代替。
图片来源:https://lisk.com/blog/posts/sparse-merkle-trees-and-new-state-model
SMT 还支持 multiproof,即一次性证明多个节点是否存在,可节省 proof 空间。如下图所示,需要构建节点 A、B、C、D (红色边框)的 multiproof。节点 B、C 存在于树中,而节点 A、D 不存在于树中。multiproof 包含了图中用红色填充的块。
图片来源:https://lisk.com/blog/posts/sparse-merkle-trees-and-new-state-model
https://github.com/felicityin/start-smt
CKB 是一个采用 PoW 共识算法的区块链。
RFC: Compact UDT Lock 中提到了一个例子(应该还没有实现),Tom 将钱 deposit 到 Alice。交易如下所示(只展示 data 部分):
Inputs:
<vec> Compact UDT Cell
Data: <1000 UDT> <old SMT root hash>
<vec> Tom's UDT Cell
Data: <2000 UDT>
<...>
Outputs:
<vec> Compact UDT Cell
Data: <1200 UDT> <new SMT root hash>
<vec> Tom's UDT Cell
Data: <1799 UDT>
<...>
Witnesses:
WitnessArgs structure:
Lock:
deposits:
<vec> Deposit Entry
source: Tom
target: Alice
amount: 200 UDT
fee: 1 UDT
transfers: []
kv_state:
<vec> Alice's SMT Entry
k: Alice
v: 1000 UDT | nonce 5
kv_proof: <valid proof>
<...>
该交易结束后,SMT 中会新增如下数据:
Alice’s SMT Entry
k: Alice
v: 1200 UDT | nonce 5
合约的验证逻辑:
区块链技术架构分析(3)-默克尔树(merkle tree)
Understanding Trie Databases in Ethereum
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。