Merkle Patricia Trie

相关源文件

• core/state/database.go
• core/state/dump.go
• core/state/iterator.go
• core/state/journal.go
• core/state/state_object.go
• core/state/state_test.go
• core/state/statedb.go
• core/state/statedb_fuzz_test.go
• core/state/statedb_test.go
• core/state/stateupdate.go
• core/state/sync.go
• core/state/sync_test.go
• core/vm/interface.go
• eth/downloader/statesync.go
• tests/fuzzers/rangeproof/rangeproof-fuzzer.go
• trie/committer.go
• trie/hasher.go
• trie/iterator.go
• trie/iterator_test.go
• trie/node.go
• trie/proof.go
• trie/proof_test.go
• trie/secure_trie.go
• trie/secure_trie_test.go
• trie/sync.go
• trie/sync_test.go
• trie/trie.go
• trie/trie_test.go

本文档涵盖了 go-ethereum 中 Merkle Patricia Trie 的实现，它为存储以太坊的世界状态提供了一种加密认证的数据结构。该 Trie 结合了 Merkle 树（通过基于哈希的验证实现加密完整性）和 Patricia Trie（空间高效地存储稀疏键值数据）的优点。

有关使用这些 Trie 的更高级别状态管理系统的更多信息，请参阅状态管理。有关数据库级别的存储详细信息，请参阅数据库架构。

架构概述

Merkle Patricia Trie 系统由几个核心组件组成，它们协同工作以提供认证状态存储。

来源： trie/trie.go32-60 trie/secure_trie.go63-69 core/state/statedb.go68-158

StateTrie 提供了围绕基本 Trie 实现的安全包装，通过使用 Keccak256 自动哈希密钥，防止了可能通过故意构造的密钥创建不平衡 Trie 的攻击。

节点类型和结构

该 Trie 使用四种基本节点类型来表示数据。

来源： trie/node.go28-94

• shortNode: 表示路径压缩 - 存储部分键并指向另一个节点
• fullNode: 表示一个分支，最多包含 16 个子节点（用于十六进制数字 0-F）以及一个可选值
• hashNode: 通过其哈希引用另一个节点，支持按需加载和 Merkle 证明
• valueNode: 包含叶子位置的实际数据值

核心 Trie 操作

该 Trie 支持标准的键值操作，并自动计算 Merkle 根。

来源： trie/trie.go142-157 trie/trie.go299-325 trie/trie.go417-431

该 Trie 在内部使用十六进制编码的键，其中每个字节代表一个 4 位 Nibble，从而能够有效地通过 fullNode 条目的 16 路分支结构进行遍历。

状态集成

Trie 系统通过多个层级与以太坊的状态管理集成。

来源： core/state/statedb.go79-158 core/state/state_object.go47-86 core/state/statedb.go778-927

每个以太坊账户都有一个关联的存储 Trie 用于合同存储，而主账户 Trie 将地址映射到账户数据。 StateTrie 包装器确保所有密钥都经过哈希处理，以实现安全性和均匀分布。

Merkle 证明系统

该 Trie 提供加密证明，允许在不下载整个 Trie 的情况下验证数据。

来源： trie/proof.go29-101 trie/proof.go114-141 trie/proof.go143-217

Merkle 证明使轻客户端能够在不下载完整的状态 Trie（可能达到数百 GB）的情况下验证特定的状态值。

Trie 同步

同步系统支持下载和验证远程 Trie 数据。

来源： trie/sync.go257-283 trie/sync.go419-520 trie/sync.go191-256

同步系统使用优先队列来高效下载 Trie 节点，优先下载更接近根的节点，并实现适当的去重，以避免重复下载相同的节点。

性能优化

几项优化措施提高了 Trie 的性能。

按需加载和缓存

• 哈希节点：节点可以存储为哈希引用，并在需要时加载。
• 预取：triePrefetcher 在后台线程中加载预期的节点。
• 节点缓存：经常访问的节点会保留在内存中。

路径压缩

• 短节点：压缩单子节点路径以降低树的深度。
• 十六进制编码：内部键使用 4 位 Nibble，以实现高效的 16 路分支。

批量操作

• 脏跟踪：已修改的节点会被标记为脏节点并进行批量处理。
• 并行哈希：提交期间，多个 goroutine 并发计算哈希。
• 内存批量处理：在写入数据库之前，更改会在内存中进行批量处理。

来源： core/state/statedb.go196-229 trie/trie.go626-661 trie/hasher.go26-50

这些优点的结合使得 Trie 能够处理以太坊的高交易吞吐量，同时保持加密安全保证。