以太坊MPT构建详解<\/h1>

1. MPT概述<\/h2>

MPT (Merkle Patricia Tree) 是以太坊中用于存储账户状态和交易信息的核心数据结构。它结合了Merkle Tree和Patricia Tree的优点，具有以下特性：<\/p>

高效存储：通过路径压缩减少存储空间<\/li>
快速验证：通过Merkle证明可以快速验证数据完整性<\/li>

确定性：相同的数据集总是生成相同的树结构<\/li> <\/ul>

2. MPT核心组件<\/h2>

2.1 节点类型<\/h3>

MPT包含四种节点类型：<\/p>

空节点<\/strong>：表示空树<\/li>
叶子节点(shortNode)<\/strong>：存储键值对，键是16进制编码<\/li>
分支节点(fullNode)<\/strong>：有17个元素的数组，前16个对应16进制字符，第17个存储值<\/li>

哈希节点(hashNode)<\/strong>：指向其他节点的哈希引用<\/li> <\/ol>
2.2 辅助结构<\/h3>
2.2.1 hasher结构<\/h4>
type<\/span> hasher<\/span> struct<\/span> { <\/span><\/span> sha<\/span> crypto<\/span>.Keccak256<\/span> <\/span><\/span> tmp<\/span> []byte<\/span> <\/span><\/span> parallel<\/span> bool<\/span> \/\/ 是否并行处理 <\/span><\/span><\/span><\/span>} <\/span><\/span><\/code><\/pre>2.2.2 committer结构<\/h4> type<\/span> committer<\/span> struct<\/span> { <\/span><\/span> onleaf<\/span> LeafCallback<\/span> <\/span><\/span> leafCh<\/span> chan<\/span> *<\/span>leaf<\/span> <\/span><\/span> \/\/ ...其他字段 <\/span><\/span><\/span><\/span>} <\/span><\/span><\/code><\/pre>3. MPT构建过程<\/h2> 3.1 树的提交(Commit)<\/h3> 树的提交通过Commit<\/code>函数实现，主要流程：<\/p> 检查Trie的DB和Root是否存在<\/li> 计算Root的Hash值<\/li> 检查是否需要提交变更<\/li> 将节点折叠为哈希节点并插入数据库<\/li> <\/ol> func<\/span> (t<\/span> *<\/span>Trie<\/span>) Commit<\/span>(onleaf<\/span> LeafCallback<\/span>) (root<\/span> common<\/span>.Hash<\/span>, err<\/span> error<\/span>) { <\/span><\/span> if<\/span> t<\/span>.db<\/span> ==<\/span> nil<\/span> { <\/span><\/span> panic("commit called on trie with nil database"<\/span>) <\/span><\/span> } <\/span><\/span> if<\/span> t<\/span>.root<\/span> ==<\/span> nil<\/span> { <\/span><\/span> return<\/span> emptyRoot<\/span>, nil<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> rootHash<\/span> :=<\/span> t<\/span>.Hash<\/span>() <\/span><\/span> h<\/span> :=<\/span> newCommitter<\/span>() <\/span><\/span> defer<\/span> returnCommitterToPool<\/span>(h<\/span>) <\/span><\/span> <\/span><\/span> if<\/span> _<\/span>, dirty<\/span> :=<\/span> t<\/span>.root<\/span>.cache<\/span>(); !dirty<\/span> { <\/span><\/span> return<\/span> rootHash<\/span>, nil<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> var<\/span> wg<\/span> sync<\/span>.WaitGroup<\/span> <\/span><\/span> if<\/span> onleaf<\/span> !=<\/span> nil<\/span> { <\/span><\/span> h<\/span>.onleaf<\/span> = onleaf<\/span> <\/span><\/span> h<\/span>.leafCh<\/span> = make(chan<\/span> *<\/span>leaf<\/span>, leafChanSize<\/span>) <\/span><\/span> wg<\/span>.Add<\/span>(1<\/span>) <\/span><\/span> go<\/span> func<\/span>() { <\/span><\/span> defer<\/span> wg<\/span>.Done<\/span>() <\/span><\/span> h<\/span>.commitLoop<\/span>(t<\/span>.db<\/span>) <\/span><\/span> }() <\/span><\/span> } <\/span><\/span> <\/span><\/span> var<\/span> newRoot<\/span> hashNode<\/span> <\/span><\/span> newRoot<\/span>, err<\/span> = h<\/span>.Commit<\/span>(t<\/span>.root<\/span>, t<\/span>.db<\/span>) <\/span><\/span> <\/span><\/span> if<\/span> onleaf<\/span> !=<\/span> nil<\/span> { <\/span><\/span> close(h<\/span>.leafCh<\/span>) <\/span><\/span> wg<\/span>.Wait<\/span>() <\/span><\/span> } <\/span><\/span> <\/span><\/span> if<\/span> err<\/span> !=<\/span> nil<\/span> { <\/span><\/span> return<\/span> common<\/span>.Hash<\/span>{}, err<\/span> <\/span><\/span> } <\/span><\/span> t<\/span>.root<\/span> = newRoot<\/span> <\/span><\/span> return<\/span> rootHash<\/span>, nil<\/span> <\/span><\/span>} <\/span><\/span><\/code><\/pre>3.2 Hash计算<\/h3> Hash<\/code>方法计算树的根哈希：<\/p> func<\/span> (t<\/span> *<\/span>Trie<\/span>) Hash<\/span>() common<\/span>.Hash<\/span> { <\/span><\/span> hash<\/span>, cached<\/span>, _<\/span> :=<\/span> t<\/span>.hashRoot<\/span>() <\/span><\/span> t<\/span>.root<\/span> = cached<\/span> <\/span><\/span> return<\/span> common<\/span>.BytesToHash<\/span>(hash<\/span>.(hashNode<\/span>)) <\/span><\/span>} <\/span><\/span><\/code><\/pre>hashRoot<\/code>方法实现：<\/p> func<\/span> (t<\/span> *<\/span>Trie<\/span>) hashRoot<\/span>() (node<\/span>, node<\/span>, error<\/span>) { <\/span><\/span> if<\/span> t<\/span>.root<\/span> ==<\/span> nil<\/span> { <\/span><\/span> return<\/span> hashNode<\/span>(emptyRoot<\/span>.Bytes<\/span>()), nil<\/span>, nil<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> h<\/span> :=<\/span> newHasher<\/span>(t<\/span>.unhashed<\/span> >=<\/span> 100<\/span>) <\/span><\/span> defer<\/span> returnHasherToPool<\/span>(h<\/span>) <\/span><\/span> <\/span><\/span> hashed<\/span>, cached<\/span> :=<\/span> h<\/span>.hash<\/span>(t<\/span>.root<\/span>, true<\/span>) <\/span><\/span> t<\/span>.unhashed<\/span> = 0<\/span> <\/span><\/span> return<\/span> hashed<\/span>, cached<\/span>, nil<\/span> <\/span><\/span>} <\/span><\/span><\/code><\/pre>3.3 节点哈希处理<\/h3> hash<\/code>方法将节点折叠为哈希节点：<\/p> func<\/span> (h<\/span> *<\/span>hasher<\/span>) hash<\/span>(n<\/span> node<\/span>, force<\/span> bool<\/span>) (hashed<\/span> node<\/span>, cached<\/span> node<\/span>) { <\/span><\/span> if<\/span> hash<\/span>, _<\/span> :=<\/span> n<\/span>.cache<\/span>(); hash<\/span> !=<\/span> nil<\/span> { <\/span><\/span> return<\/span> hash<\/span>, n<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> switch<\/span> n<\/span> :=<\/span> n<\/span>.(type<\/span>) { <\/span><\/span> case<\/span> *<\/span>shortNode<\/span>: <\/span><\/span> collapsed<\/span>, cached<\/span> :=<\/span> h<\/span>.hashShortNodeChildren<\/span>(n<\/span>) <\/span><\/span> hashed<\/span> :=<\/span> h<\/span>.shortnodeToHash<\/span>(collapsed<\/span>, force<\/span>) <\/span><\/span> if<\/span> hn<\/span>, ok<\/span> :=<\/span> hashed<\/span>.(hashNode<\/span>); ok<\/span> { <\/span><\/span> cached<\/span>.flags<\/span>.hash<\/span> = hn<\/span> <\/span><\/span> } else<\/span> { <\/span><\/span> cached<\/span>.flags<\/span>.hash<\/span> = nil<\/span> <\/span><\/span> } <\/span><\/span> return<\/span> hashed<\/span>, cached<\/span> <\/span><\/span> <\/span><\/span> case<\/span> *<\/span>fullNode<\/span>: <\/span><\/span> collapsed<\/span>, cached<\/span> :=<\/span> h<\/span>.hashFullNodeChildren<\/span>(n<\/span>) <\/span><\/span> hashed<\/span> = h<\/span>.fullnodeToHash<\/span>(collapsed<\/span>, force<\/span>) <\/span><\/span> if<\/span> hn<\/span>, ok<\/span> :=<\/span> hashed<\/span>.(hashNode<\/span>); ok<\/span> { <\/span><\/span> cached<\/span>.flags<\/span>.hash<\/span> = hn<\/span> <\/span><\/span> } else<\/span> { <\/span><\/span> cached<\/span>.flags<\/span>.hash<\/span> = nil<\/span> <\/span><\/span> } <\/span><\/span> return<\/span> hashed<\/span>, cached<\/span> <\/span><\/span> <\/span><\/span> default<\/span>: <\/span><\/span> return<\/span> n<\/span>, n<\/span> <\/span><\/span> } <\/span><\/span>} <\/span><\/span><\/code><\/pre>3.3.1 扩展节点处理<\/h4> hashShortNodeChildren<\/code>处理扩展节点：<\/p> func<\/span> (h<\/span> *<\/span>hasher<\/span>) hashShortNodeChildren<\/span>(n<\/span> *<\/span>shortNode<\/span>) (collapsed<\/span>, cached<\/span> *<\/span>shortNode<\/span>) { <\/span><\/span> collapsed<\/span>, cached<\/span> = n<\/span>.copy(), n<\/span>.copy() <\/span><\/span> collapsed<\/span>.Key<\/span> = hexToCompact<\/span>(n<\/span>.Key<\/span>) <\/span><\/span> <\/span><\/span> switch<\/span> n<\/span>.Val<\/span>.(type<\/span>) { <\/span><\/span> case<\/span> *<\/span>fullNode<\/span>, *<\/span>shortNode<\/span>: <\/span><\/span> collapsed<\/span>.Val<\/span>, cached<\/span>.Val<\/span> = h<\/span>.hash<\/span>(n<\/span>.Val<\/span>, false<\/span>) <\/span><\/span> } <\/span><\/span> return<\/span> collapsed<\/span>, cached<\/span> <\/span><\/span>} <\/span><\/span><\/code><\/pre>shortnodeToHash<\/code>创建哈希节点：<\/p> func<\/span> (h<\/span> *<\/span>hasher<\/span>) shortnodeToHash<\/span>(n<\/span> *<\/span>shortNode<\/span>, force<\/span> bool<\/span>) node<\/span> { <\/span><\/span> h<\/span>.tmp<\/span>.Reset<\/span>() <\/span><\/span> if<\/span> err<\/span> :=<\/span> rlp<\/span>.Encode<\/span>(&<\/span>h<\/span>.tmp<\/span>, n<\/span>); err<\/span> !=<\/span> nil<\/span> { <\/span><\/span> panic("encode error: "<\/span> +<\/span> err<\/span>.Error<\/span>()) <\/span><\/span> } <\/span><\/span> <\/span><\/span> if<\/span> len(h<\/span>.tmp<\/span>) < 32<\/span> &&<\/span> !force<\/span> { <\/span><\/span> return<\/span> n<\/span> <\/span><\/span> } <\/span><\/span> return<\/span> h<\/span>.hashData<\/span>(h<\/span>.tmp<\/span>) <\/span><\/span>} <\/span><\/span><\/code><\/pre>3.3.2 分支节点处理<\/h4> hashFullNodeChildren<\/code>处理分支节点：<\/p> func<\/span> (h<\/span> *<\/span>hasher<\/span>) hashFullNodeChildren<\/span>(n<\/span> *<\/span>fullNode<\/span>) (collapsed<\/span> *<\/span>fullNode<\/span>, cached<\/span> *<\/span>fullNode<\/span>) { <\/span><\/span> cached<\/span> = n<\/span>.copy() <\/span><\/span> collapsed<\/span> = n<\/span>.copy() <\/span><\/span> <\/span><\/span> if<\/span> h<\/span>.parallel<\/span> { <\/span><\/span> var<\/span> wg<\/span> sync<\/span>.WaitGroup<\/span> <\/span><\/span> wg<\/span>.Add<\/span>(16<\/span>) <\/span><\/span> for<\/span> i<\/span> :=<\/span> 0<\/span>; i<\/span> < 16<\/span>; i<\/span>++<\/span> { <\/span><\/span> go<\/span> func<\/span>(i<\/span> int<\/span>) { <\/span><\/span> hasher<\/span> :=<\/span> newHasher<\/span>(false<\/span>) <\/span><\/span> if<\/span> child<\/span> :=<\/span> n<\/span>.Children<\/span>[i<\/span>]; child<\/span> !=<\/span> nil<\/span> { <\/span><\/span> collapsed<\/span>.Children<\/span>[i<\/span>], cached<\/span>.Children<\/span>[i<\/span>] = hasher<\/span>.hash<\/span>(child<\/span>, false<\/span>) <\/span><\/span> } else<\/span> { <\/span><\/span> collapsed<\/span>.Children<\/span>[i<\/span>] = nilValueNode<\/span> <\/span><\/span> } <\/span><\/span> returnHasherToPool<\/span>(hasher<\/span>) <\/span><\/span> wg<\/span>.Done<\/span>() <\/span><\/span> }(i<\/span>) <\/span><\/span> } <\/span><\/span> wg<\/span>.Wait<\/span>() <\/span><\/span> } else<\/span> { <\/span><\/span> for<\/span> i<\/span> :=<\/span> 0<\/span>; i<\/span> < 16<\/span>; i<\/span>++<\/span> { <\/span><\/span> if<\/span> child<\/span> :=<\/span> n<\/span>.Children<\/span>[i<\/span>]; child<\/span> !=<\/span> nil<\/span> { <\/span><\/span> collapsed<\/span>.Children<\/span>[i<\/span>], cached<\/span>.Children<\/span>[i<\/span>] = h<\/span>.hash<\/span>(child<\/span>, false<\/span>) <\/span><\/span> } else<\/span> { <\/span><\/span> collapsed<\/span>.Children<\/span>[i<\/span>] = nilValueNode<\/span> <\/span><\/span> } <\/span><\/span> } <\/span><\/span> } <\/span><\/span> return<\/span> collapsed<\/span>, cached<\/span> <\/span><\/span>} <\/span><\/span><\/code><\/pre>fullnodeToHash<\/code>创建哈希节点：<\/p> func<\/span> (h<\/span> *<\/span>hasher<\/span>) fullnodeToHash<\/span>(n<\/span> *<\/span>fullNode<\/span>, force<\/span> bool<\/span>) node<\/span> { <\/span><\/span> h<\/span>.tmp<\/span>.Reset<\/span>() <\/span><\/span> if<\/span> err<\/span> :=<\/span> n<\/span>.EncodeRLP<\/span>(&<\/span>h<\/span>.tmp<\/span>); err<\/span> !=<\/span> nil<\/span> { <\/span><\/span> panic("encode error: "<\/span> +<\/span> err<\/span>.Error<\/span>()) <\/span><\/span> } <\/span><\/span> <\/span><\/span> if<\/span> len(h<\/span>.tmp<\/span>) < 32<\/span> &&<\/span> !force<\/span> { <\/span><\/span> return<\/span> n<\/span> <\/span><\/span> } <\/span><\/span> return<\/span> h<\/span>.hashData<\/span>(h<\/span>.tmp<\/span>) <\/span><\/span>} <\/span><\/span><\/code><\/pre>4. 树的证明<\/h2> 4.1 Prove方法<\/h3> Prove<\/code>方法获取指定Key的proof证明：<\/p> func<\/span> (t<\/span> *<\/span>Trie<\/span>) Prove<\/span>(key<\/span> []byte<\/span>, fromLevel<\/span> uint<\/span>, proofDb<\/span> ethdb<\/span>.KeyValueWriter<\/span>) error<\/span> { <\/span><\/span> key<\/span> = keybytesToHex<\/span>(key<\/span>) <\/span><\/span> var<\/span> nodes<\/span> []node<\/span> <\/span><\/span> tn<\/span> :=<\/span> t<\/span>.root<\/span> <\/span><\/span> <\/span><\/span> for<\/span> len(key<\/span>) > 0<\/span> &&<\/span> tn<\/span> !=<\/span> nil<\/span> { <\/span><\/span> switch<\/span> n<\/span> :=<\/span> tn<\/span>.(type<\/span>) { <\/span><\/span> case<\/span> *<\/span>shortNode<\/span>: <\/span><\/span> if<\/span> len(key<\/span>) < len(n<\/span>.Key<\/span>) ||<\/span> !bytes<\/span>.Equal<\/span>(n<\/span>.Key<\/span>, key<\/span>[:len(n<\/span>.Key<\/span>)]) { <\/span><\/span> tn<\/span> = nil<\/span> <\/span><\/span> } else<\/span> { <\/span><\/span> tn<\/span> = n<\/span>.Val<\/span> <\/span><\/span> key<\/span> = key<\/span>[len(n<\/span>.Key<\/span>):] <\/span><\/span> } <\/span><\/span> nodes<\/span> = append(nodes<\/span>, n<\/span>) <\/span><\/span> <\/span><\/span> case<\/span> *<\/span>fullNode<\/span>: <\/span><\/span> tn<\/span> = n<\/span>.Children<\/span>[key<\/span>[0<\/span>]] <\/span><\/span> key<\/span> = key<\/span>[1<\/span>:] <\/span><\/span> nodes<\/span> = append(nodes<\/span>, n<\/span>) <\/span><\/span> <\/span><\/span> case<\/span> hashNode<\/span>: <\/span><\/span> var<\/span> err<\/span> error<\/span> <\/span><\/span> tn<\/span>, err<\/span> = t<\/span>.resolveHash<\/span>(n<\/span>, nil<\/span>) <\/span><\/span> if<\/span> err<\/span> !=<\/span> nil<\/span> { <\/span><\/span> log<\/span>.Error<\/span>(fmt<\/span>.Sprintf<\/span>("Unhandled trie error: %v"<\/span>, err<\/span>)) <\/span><\/span> return<\/span> err<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> default<\/span>: <\/span><\/span> panic(fmt<\/span>.Sprintf<\/span>("%T: invalid node: %v"<\/span>, tn<\/span>, tn<\/span>)) <\/span><\/span> } <\/span><\/span> } <\/span><\/span> <\/span><\/span> hasher<\/span> :=<\/span> newHasher<\/span>(false<\/span>) <\/span><\/span> defer<\/span> returnHasherToPool<\/span>(hasher<\/span>) <\/span><\/span> <\/span><\/span> for<\/span> i<\/span>, n<\/span> :=<\/span> range<\/span> nodes<\/span> { <\/span><\/span> if<\/span> fromLevel<\/span> > 0<\/span> { <\/span><\/span> fromLevel<\/span>--<\/span> <\/span><\/span> continue<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> var<\/span> hn<\/span> node<\/span> <\/span><\/span> n<\/span>, hn<\/span> = hasher<\/span>.proofHash<\/span>(n<\/span>) <\/span><\/span> if<\/span> hash<\/span>, ok<\/span> :=<\/span> hn<\/span>.(hashNode<\/span>); ok<\/span> ||<\/span> i<\/span> ==<\/span> 0<\/span> { <\/span><\/span> enc<\/span>, _<\/span> :=<\/span> rlp<\/span>.EncodeToBytes<\/span>(n<\/span>) <\/span><\/span> if<\/span> !ok<\/span> { <\/span><\/span> hash<\/span> = hasher<\/span>.hashData<\/span>(enc<\/span>) <\/span><\/span> } <\/span><\/span> proofDb<\/span>.Put<\/span>(hash<\/span>, enc<\/span>) <\/span><\/span> } <\/span><\/span> } <\/span><\/span> return<\/span> nil<\/span> <\/span><\/span>} <\/span><\/span><\/code><\/pre>4.2 VerifyProof方法<\/h3> 验证Merkle证明：<\/p> func<\/span> VerifyProof<\/span>(rootHash<\/span> common<\/span>.Hash<\/span>, key<\/span> []byte<\/span>, proofDb<\/span> ethdb<\/span>.KeyValueReader<\/span>) (value<\/span> []byte<\/span>, err<\/span> error<\/span>) { <\/span><\/span> key<\/span> = keybytesToHex<\/span>(key<\/span>) <\/span><\/span> wantHash<\/span> :=<\/span> rootHash<\/span> <\/span><\/span> <\/span><\/span> for<\/span> i<\/span> :=<\/span> 0<\/span>; ; i<\/span>++<\/span> { <\/span><\/span> buf<\/span>, _<\/span> :=<\/span> proofDb<\/span>.Get<\/span>(wantHash<\/span>[:]) <\/span><\/span> if<\/span> buf<\/span> ==<\/span> nil<\/span> { <\/span><\/span> return<\/span> nil<\/span>, fmt<\/span>.Errorf<\/span>("proof node %d (hash %064x) missing"<\/span>, i<\/span>, wantHash<\/span>) <\/span><\/span> } <\/span><\/span> <\/span><\/span> n<\/span>, err<\/span> :=<\/span> decodeNode<\/span>(wantHash<\/span>[:], buf<\/span>) <\/span><\/span> if<\/span> err<\/span> !=<\/span> nil<\/span> { <\/span><\/span> return<\/span> nil<\/span>, fmt<\/span>.Errorf<\/span>("bad proof node %d: %v"<\/span>, i<\/span>, err<\/span>) <\/span><\/span> } <\/span><\/span> <\/span><\/span> keyrest<\/span>, cld<\/span> :=<\/span> get<\/span>(n<\/span>, key<\/span>, true<\/span>) <\/span><\/span> switch<\/span> cld<\/span> :=<\/span> cld<\/span>.(type<\/span>) { <\/span><\/span> case<\/span> nil<\/span>: <\/span><\/span> return<\/span> nil<\/span>, nil<\/span> <\/span><\/span> case<\/span> hashNode<\/span>: <\/span><\/span> key<\/span> = keyrest<\/span> <\/span><\/span> copy(wantHash<\/span>[:], cld<\/span>) <\/span><\/span> case<\/span> valueNode<\/span>: <\/span><\/span> return<\/span> cld<\/span>, nil<\/span> <\/span><\/span> } <\/span><\/span> } <\/span><\/span>} <\/span><\/span><\/code><\/pre>4.3 VerifyRangeProof方法<\/h3> 验证范围证明：<\/p> func<\/span> VerifyRangeProof<\/span>(rootHash<\/span> common<\/span>.Hash<\/span>, firstKey<\/span> []byte<\/span>, lastKey<\/span> []byte<\/span>, <\/span><\/span> keys<\/span> [][]byte<\/span>, values<\/span> [][]byte<\/span>, proof<\/span> ethdb<\/span>.KeyValueReader<\/span>) (ethdb<\/span>.KeyValueStore<\/span>, *<\/span>Trie<\/span>, *<\/span>KeyValueNotary<\/span>, bool<\/span>, error<\/span>) { <\/span><\/span> <\/span><\/span> \/\/ 验证输入数据一致性 <\/span><\/span><\/span><\/span> if<\/span> len(keys<\/span>) !=<\/span> len(values<\/span>) { <\/span><\/span> return<\/span> nil<\/span>, nil<\/span>, nil<\/span>, false<\/span>, fmt<\/span>.Errorf<\/span>("inconsistent proof data, keys: %d, values: %d"<\/span>, len(keys<\/span>), len(values<\/span>)) <\/span><\/span> } <\/span><\/span> <\/span><\/span> \/\/ 确保键是单调递增的 <\/span><\/span><\/span><\/span> for<\/span> i<\/span> :=<\/span> 0<\/span>; i<\/span> < len(keys<\/span>)-<\/span>1<\/span>; i<\/span>++<\/span> { <\/span><\/span> if<\/span> bytes<\/span>.Compare<\/span>(keys<\/span>[i<\/span>], keys<\/span>[i<\/span>+<\/span>1<\/span>]) >=<\/span> 0<\/span> { <\/span><\/span> return<\/span> nil<\/span>, nil<\/span>, nil<\/span>, false<\/span>, errors<\/span>.New<\/span>("range is not monotonically increasing"<\/span>) <\/span><\/span> } <\/span><\/span> } <\/span><\/span> <\/span><\/span> \/\/ 创建证明跟踪器 <\/span><\/span><\/span><\/span> notary<\/span> :=<\/span> NewKeyValueNotary<\/span>(proof<\/span>) <\/span><\/span> <\/span><\/span> \/\/ 处理特殊情况 <\/span><\/span><\/span><\/span> if<\/span> proof<\/span> ==<\/span> nil<\/span> { <\/span><\/span> \/\/ 处理无证明的特殊情况 <\/span><\/span><\/span><\/span> \/\/ ... <\/span><\/span><\/span><\/span> } <\/span><\/span> <\/span><\/span> if<\/span> len(keys<\/span>) ==<\/span> 0<\/span> { <\/span><\/span> \/\/ 处理零元素证明 <\/span><\/span><\/span><\/span> \/\/ ... <\/span><\/span><\/span><\/span> } <\/span><\/span> <\/span><\/span> if<\/span> len(keys<\/span>) ==<\/span> 1<\/span> &&<\/span> bytes<\/span>.Equal<\/span>(firstKey<\/span>, lastKey<\/span>) { <\/span><\/span> \/\/ 处理单元素证明 <\/span><\/span><\/span><\/span> \/\/ ... <\/span><\/span><\/span><\/span> } <\/span><\/span> <\/span><\/span> \/\/ 验证边缘键有效性 <\/span><\/span><\/span><\/span> if<\/span> bytes<\/span>.Compare<\/span>(firstKey<\/span>, lastKey<\/span>) >=<\/span> 0<\/span> { <\/span><\/span> return<\/span> nil<\/span>, nil<\/span>, nil<\/span>, false<\/span>, errors<\/span>.New<\/span>("invalid edge keys"<\/span>) <\/span><\/span> } <\/span><\/span> <\/span><\/span> if<\/span> len(firstKey<\/span>) !=<\/span> len(lastKey<\/span>) { <\/span><\/span> return<\/span> nil<\/span>, nil<\/span>, nil<\/span>, false<\/span>, errors<\/span>.New<\/span>("inconsistent edge keys"<\/span>) <\/span><\/span> } <\/span><\/span> <\/span><\/span> \/\/ 将边缘证明转换为路径 <\/span><\/span><\/span><\/span> root<\/span>, _<\/span>, err<\/span> :=<\/span> proofToPath<\/span>(rootHash<\/span>, nil<\/span>, firstKey<\/span>, notary<\/span>, true<\/span>) <\/span><\/span> if<\/span> err<\/span> !=<\/span> nil<\/span> { <\/span><\/span> return<\/span> nil<\/span>, nil<\/span>, nil<\/span>, false<\/span>, err<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> root<\/span>, _<\/span>, err<\/span> = proofToPath<\/span>(rootHash<\/span>, root<\/span>, lastKey<\/span>, notary<\/span>, true<\/span>) <\/span><\/span> if<\/span> err<\/span> !=<\/span> nil<\/span> { <\/span><\/span> return<\/span> nil<\/span>, nil<\/span>, nil<\/span>, false<\/span>, err<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> \/\/ 移除内部引用 <\/span><\/span><\/span><\/span> empty<\/span>, err<\/span> :=<\/span> unsetInternal<\/span>(root<\/span>, firstKey<\/span>, lastKey<\/span>) <\/span><\/span> if<\/span> err<\/span> !=<\/span> nil<\/span> { <\/span><\/span> return<\/span> nil<\/span>, nil<\/span>, nil<\/span>, false<\/span>, err<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> \/\/ 重建Trie <\/span><\/span><\/span><\/span> diskdb<\/span> :=<\/span> memorydb<\/span>.New<\/span>() <\/span><\/span> triedb<\/span> :=<\/span> NewDatabase<\/span>(diskdb<\/span>) <\/span><\/span> tr<\/span> :=<\/span> &<\/span>Trie<\/span>{root<\/span>: root<\/span>, db<\/span>: triedb<\/span>} <\/span><\/span> <\/span><\/span> if<\/span> empty<\/span> { <\/span><\/span> tr<\/span>.root<\/span> = nil<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> for<\/span> index<\/span>, key<\/span> :=<\/span> range<\/span> keys<\/span> { <\/span><\/span> tr<\/span>.TryUpdate<\/span>(key<\/span>, values<\/span>[index<\/span>]) <\/span><\/span> } <\/span><\/span> <\/span><\/span> if<\/span> tr<\/span>.Hash<\/span>() !=<\/span> rootHash<\/span> { <\/span><\/span> return<\/span> nil<\/span>, nil<\/span>, nil<\/span>, false<\/span>, fmt<\/span>.Errorf<\/span>("invalid proof, want hash %x, got %x"<\/span>, rootHash<\/span>, tr<\/span>.Hash<\/span>()) <\/span><\/span> } <\/span><\/span> <\/span><\/span> \/\/ 提交更改 <\/span><\/span><\/span><\/span> if<\/span> _<\/span>, err<\/span> :=<\/span> tr<\/span>.Commit<\/span>(nil<\/span>); err<\/span> !=<\/span> nil<\/span> { <\/span><\/span> return<\/span> nil<\/span>, nil<\/span>, nil<\/span>, false<\/span>, err<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> if<\/span> err<\/span> :=<\/span> triedb<\/span>.Commit<\/span>(rootHash<\/span>, false<\/span>, nil<\/span>); err<\/span> !=<\/span> nil<\/span> { <\/span><\/span> return<\/span> nil<\/span>, nil<\/span>, nil<\/span>, false<\/span>, err<\/span> <\/span><\/span> } <\/span><\/span> <\/span><\/span> return<\/span> diskdb<\/span>, tr<\/span>, notary<\/span>, hasRightElement<\/span>(root<\/span>, keys<\/span>[len(keys<\/span>)-<\/span>1<\/span>]), nil<\/span> <\/span><\/span>} <\/span><\/span><\/code><\/pre>5. 安全考虑<\/h2> 5.1 哈希碰撞(Hash Collision)<\/h3> 攻击者可能通过构造不同的数据集产生相同的哈希值，从而绕过验证。在MPT中需要注意：<\/p> 哈希计算顺序<\/strong>：交换非叶子节点的子树顺序可能产生相同的Merkle根<\/li> 防御措施<\/strong>：使用足够强的哈希函数(如Keccak-256)<\/li> 在验证时检查完整路径而不仅仅是哈希值<\/li> <\/ul> <\/li> <\/ol> 5.2 其他安全考虑<\/h3> 空节点处理<\/strong>：确保空节点有明确的表示方式<\/li> 序列化验证<\/strong>：验证RLP编码的正确性<\/li> 并行处理安全<\/strong>：确保并发哈希计算时的线程安全<\/li> <\/ol> 6. 关键常量<\/h2> var<\/span> ( <\/span><\/span> \/\/ 空树的已知根哈希 <\/span><\/span><\/span><\/span> emptyRoot<\/span> = common<\/span>.HexToHash<\/span>("56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421"<\/span>) <\/span><\/span> <\/span><\/span> \/\/ 空状态条目的已知哈希 <\/span><\/span><\/span><\/span> emptyState<\/span> = crypto<\/span>.Keccak256Hash<\/span>(nil<\/span>) <\/span><\/span>) <\/span><\/span><\/code><\/pre>7. 总结<\/h2> MPT是以太坊存储层的核心数据结构，理解其构建和验证过程对于：<\/p> 开发以太坊客户端<\/li> 实现轻客户端验证<\/li> 设计状态通道和侧链<\/li> 进行安全审计<\/li> <\/ul> 都非常重要。本文详细介绍了MPT的构建过程、证明生成和验证机制，以及相关的安全考虑，为开发者深入理解以太坊底层提供了全面的参考。<\/p>