Merkle Patricia Trie
以太坊采用的 modified Merkle-Patricia Trie
- Trie：字典树/前缀树
- Merkle：Hash 节点，支持 Hash 验证整个树
- Patricia：Practical Algorithm to Retrieve Information Coded in Alphanumeric 缩写，一种压缩 单一子 节点 路径的变种 trie，也叫 紧凑 trie
数据结构
在 State Trie 中，每一个账户作为一个键值对存储：
- 键（key / path）：账户地址的 Keccak-256 哈希（Secure Trie，state trie/storage trie 采用）
- 值（value）：账户（
[nonce, balance, storageRoot, codeHash]的 RLP 编码）
trie 结构中，每一个节点都会存储一个键的 16 进制字符，也就是半字节（nibble / 4 bit）
MPT 中有 4 种节点类型：
- NULL（空字符串）
- branch（分支节点）
- 长度 17 数组：空/子节点hash *16 + 值
- 前 16 位每一个都代表一个前缀 16 进制数
- 例：
[[NULL, NULL, child_hash, NULL, NULL, other_child_hash, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL], value]
- extension（扩展节点）
- 对压缩共享前缀键的优化扩展
- 长度 2 数组：共享前缀(键) + 子节点 hash
- 例：
[shared_prefix, child_hash]
- leaf（叶子节点）
- 长度 2 数组：剩余键 + 值，路径的末端
- 例：
[key-end, value]
*MPT root 根节点可以是任意节点类型，但一般如果数据足够大足够多，根节点一般是分支节点类型
奇偶校验前缀
| 标志 | 节点类型 | 奇偶 |
|---|---|---|
| 0 + 占位符 0 | Extension | 偶 |
| 1 | Extension | 奇 |
| 2 + 占位符 0 | Leaf | 偶 |
| 3 | Leaf | 奇 |
Secure Trie
状态树（State Trie）和存储树（Storage Trie）都会采用安全模式（secure），即键采用 keccak256(address)
主要是出于安全性和性能平衡的考虑：
- 防御 DoS ：地址外部可控，可精心构造一系列具有共同前缀的地址，会导致 MPT 树形成一条极深的路径，增加查找、插入和计算 root 的 CPU 开销 和磁盘 I/O 开销
- 路径均匀分布：通过
keccak256，让原本可能有规律的地址随机分布，确保树结构更加平衡，深度合理
该设计在以太坊黄皮书中有直接的设计和定义，状态树 $\sigma$ ：
验证
和传统标准 Merkle 的差别在于验证顺序，传统 Merkle 证明是从下到上（从叶子到根，leaf to root），而 MPT 证明是上到下（从根到叶子，root to leaf）
以太坊 MPT
每个区块的区块头中包含 3 个 MPT 树根：
- stateRoot：世界状态
- transactionsRoot：该区块中所有交易的
- receiptsRoot：该区块中所有交易事件的
State Trie（状态树 / 世界状态）
键值构成
- path / key：
keccak256(ethereumAddress) - value：
rlp(ethereumAccount)- ethereumAccount：
[nonce, balance, storageRoot, codeHash]
- ethereumAccount：
账户状态
账户状态由 4 部分组成
- nonce：如果账户是外部账户，则该属性代表从账户地址发送的交易数量；如果账户是合约账户，则该属性代表账户创建的合约数量
- balance：该地址账户余额
- storageRoot：该账户的存储数据的 MPT 树根，非智能合约账户默认为空
- codeHash：该账户的 EVM 代码哈希值。对于合约账户，这是经过哈希处理并存储为
codeHash的代码；对于外部账户，codeHash字段是空字符串的哈希值
根据以太坊黄皮书，账户若是一个智能合约账户，则必定包含了 存储树（storageRoot）和代码存储（codeHash）
每个账户都处在树的叶子节点上，树的组织则按照排列顺序进行串联哈希，最终层层哈希得出世界状态。当更改某单一账户时，则会引发它所在分支的上层哈希值的更改，直到影响到根节点的哈希值，根节点的哈希值称为状态树根（stateRoot），这个值将存入区块头部。世界状态随着区块链的前进而不断变化，状态树的值也不断变更。
storage trie（存储树）
存放该账户下的智能合约的存储数据状态
Transaction Trie（交易树）
键值构成
- path / key：
rlp(transactionIndex) - value：
legacyTx ? rlp(tx) : TxType | encode(tx)
每个区块都有一棵独立的交易树，这棵树包含了当前区块打包的所有交易，交易的排列顺序由矿工在打包时唯一确定
若同一个块中含了同一个账户发出的数笔交易，矿工按照发送账户的 nonce 值顺序安排该账户的交易。矿工在排序完成后，调用自身的以太坊虚拟机执行交易指令来变更世界状态中对应的账户的状态，收取相应的交易费
Receipts Trie（收据树）
键值构成
- path/key：
rlp(transactionIndex) - value：
legacyReceipt ? rlp([status, cumulativeGasUsed, logsBloom, logs]) : TxType | ReceiptPayload
每个区块都有一棵独立的收据树，收据树中包含了执行交易期间产生的相应的收据
如果一笔交易是一次智能合约的执行，则在以太坊虚拟机执行的过程中会产生程序自定义的日志，日志是智能合约自定义的格式。日志（Log）包含了日志产生方的地址、日志话题（topics）、日志数据（可选）
