Ethereum World State
Table of Contents
1. World State 简介
可以把区块链看做是一个分布式的状态机：所有节点从第一个区块中的创世状态开始，依次执行每个区块内的交易，这些交易会对状态进行操作（增加、删除、修改），由于所有节点执行的交易完全相同，执行顺序也相同，从而这个状态在所有节点也是完全一致，我们把这个状态称之为“世界状态”（World State）。
“世界状态”是区块链的核心，其它数据都是围绕“世界状态”而来。本文将从“世界状态”开始介绍 Ethereum 的数据存储结构。
2. State Trie（保存世界状态）
在 Ethereum Yellow Paper 的第 4.3 节介绍了区块头的结构定义，区块头一共包含了 15 个字段，这 15 个字段中 transactionsRoot/receiptsRoot/stateRoot 这 3 个字段分别记录着 3 个 Trie 的根，其中 stateRoot 就是世界状态对应 Trie 的根，一旦某区块被节点确认，则区块头所有信息（当然包括 stateRoot）也就无法被改变了，如图 1（摘自 https://medium.com/cybermiles/diving-into-ethereums-world-state-c893102030ed ） 所示。
Figure 1: 其中 stateRoot 是“世界状态”对应 trie 的根
State Trie 保存着 Ethereum 中每个帐户的信息，即很多 key-value 数据，具体为：
- key 是帐户的地址的哈希，即 Keccak256(address) 。
- value 记录着帐户的下面 4 个信息的 RLP 编码数据：
- nonce
- balance
- storageRoot（仅合约帐户才有，记录合约 Storage trie 的根，后面会介绍）
- codeHash
- nonce
当链发生 Reorganization 时，需要 Revert Block，这需要回到 State Trie 的某个历史状态，相关信息可参考：State Tree Pruning, by Vitalik Buterin
2.1. Modified Merkle Patricia Trie
图 2 一个简化版本的 State Trie 的示意图（摘自 https://ethereum.stackexchange.com/questions/268/ethereum-block-architecture ）。它演示的是下面 4 个 key-value 对是如何保存在 State Trie 中的：
# key value a711355 45.0 a77d337 1.00 a7f9365 1.1 a77d397 0.12
这个简化版本中，key 仅占 35 个比特位，而 value 也仅编码了 balance 信息（完整版本中 value 编码了 nonce/balance/storageRoot/codeHash 这 4 个信息）。
Figure 2: 简化版本的 State Trie
Ethereum 中，State Trie 是一种 Modified Merkle Patricia Trie（简称 MPT）。MPT 有三种节点类型：
- Leaf Node，一个节点如果没有子节点，则称为 Leaf Node。Leaf Node 保存 2 个信息：[encodedPath, value]，encodedPath 用于保存 key 中的部分 path，而 value 用于保存键值对的 value，例如在图 2 中最左边那个 Leaf Node 的 encodedPath 为 1355，而 value 为 45.0ETH。
- Branch Node，一个节点如果存在子节点，则是 Branch Node（也可能是 Extension Node，后面会介绍），Branch Node 保存 17 个信息：[v0 ... v15, vt ]，由于 key 都是 16 进制，前 16 个 item 恰好足够保存 path 中的一项了，而最后一个 vt 用于保存键值对的 value，例如在图 2 中，如果要有一个 key 为 a7 键值对需要保存，则图中第 1 个 Branch Node 的 value 就会用到了。
- Extension Node， 如果连续几个 Branch Node 仅有一个子节点，则可以优化（压缩）为一个 Extension Node。 Extension Node 保存 2 个信息：[encodedPath, next-node]，encodedPath 用于保存 key 中的部分 path，而 next-node 用于指向下一个节点。例如在图 2 中的第 1 个 Extension Node 可以看作是图 3 中两个连续 Branch Node 的优化。
Figure 3: 如果连续几个 Branch Node 仅有一个子节点，则可以优化（压缩）为一个 Extension Node
2.2. Storage Trie（保存合约数据）
合约中的所有数据，都是以 key-value 形式存储在 Storage Trie 中。 每个合约都对应一个 Storage Trie， 一个 Storage Trie 的根称为 storageRoot，它和 State Trie 的关系如图 4（改编自 https://medium.com/cybermiles/diving-into-ethereums-world-state-c893102030ed ）所示。
Figure 4: Storage trie
Storage Trie 中的 key 和 value 分别是什么呢？合约中的数据可以看作是一个“大数组”，所有数据都保存在数组的某个 slot 中。
contract Storage {
uint pos0; // 对于固定大小的状态变量，从编号 0 开始，所以 pos0 的 slot 就是 0
// ......
}
Storage Trie 中的 key 是状态变量 slot 的哈希，即 Keccak256(slot)；而 value 就是对应的状态变量的值。 使用 getStorageAt 可以查询合约中保存的数据。
3. Transactions Trie（保存交易数据）
每个区块都有一个 Transactions Trie，记录着区块中每个 Transaction 的下面信息（参考 Yellow Paper 的第 4.2 节）：
nonce gasPrice gasLimit to value v,r,s
Transactions Trie 中的 key 是 RLP(transactionIndex)，这里 transactionIndex 是交易在当前区块中的索引。
4. Receipts Trie（保存交易执行结果）
每个区块都有一个 Receipts Trie，记录着区块中每个 Transaction 的执行结果 （参考 Yellow Paper 的第 4.3.1 节）：
status // 交易的最终状态 cumulativeGasUsed // 执行交易时，当前区块内的累计 gas 使用 bloom // Bloom filter composed from information in those logs logs // 交易执行时，合约产生的 event
Receipts Trie 中的 key 是 RLP(transactionIndex)，这里 transactionIndex 是交易在当前区块中的索引。
注：Transactions Trie 和 Receipts Trie 和当前世界状态无直接关系，但它们记录着改变世界状态的交易的相关信息。