细品以太坊的“四棵树”——Merkle Patricia Trie

可见默克尔树的树根就相当于对所有的数据做了一个哈希可以用来校验数据的完整性。但这有什么好处呢？为什么不直接把所有数据合并直接计算一个哈希呢？既然中间多出了这么多冗余的哈希那自然会有它的用处。实际上这常被用来做 默克尔证明Merkle Proof。一个默克尔证明包含一个数据块、树根、以及经过这个数据块到树根之间的路径的所有哈希。使用默克尔证明可以快速验证一个数据确实存在树中的某个位置。攻击者无法伪造一个默克尔证明因为根哈希依赖于其他所有节点的哈希每一个节点的修改都会导致根哈希不一致。

默克尔证明最初被应用在比特币中区块链中每个区块的交易计算哈希并形成一棵默克尔树并将树根存储在区块头中。

这可以应用在“简单支付校验”simplified payment verification中：“轻客户端”节点无需下载区块的所有交易数据只需要下载区块头当需要获取一个交易的状态时只需要向全节点请求该交易的一个默克尔证明以证明该交易确实存在于一棵默克尔树中并且该树的树根记录在区块头中。

1.2 Trie

Trie 是一种有序的树结构用于存储和检索键值对key-value其中 key 可以映射到有限“字符集”组成的字符串树的每个节点记录了一个字符并且指向了下一个字符每个路径可以组成一个完整的 key这使得节点可以共享相同的前缀。这种数据结构可以高效地存储和检索有相同前缀的 key 集实现简单并且占用内存小常被用于实现路由表以及在路由器等低规格的设备中运行的系统。

“Trie” 一词提取自 “retrieval”数据检索的中间部分根据其特征也叫前缀树Prefix Tree、字典树等。

上图表示了一棵前缀树存储了 key 值 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn"每个 key 对应了一个数字作为 value比如 "A" 对应的值为 15。注意图中的节点标注了完整的单词但这只是为了演示 Trie 的原理实际上完整的 key 并不存储在节点中而是由路径组成的。

在一种具体实现中Trie 的每个节点存储了一个固定长度的数组数组的每个元素除最后一个元素是指向子节点的指针数组的最后一个元素存储了 value若存在表示根节点到本节点的路径组成的 key 对应的 value。

例如一种用来存储英文单词26个字母的树每个节点存储的数组长度为 27下标 0~25 代表 a-z 字符下标 26 代表 value。如下图所示：

Trie 有一个很大的缺点即当某个 key 不与其他 key 共享前缀并且长度很长时会使得树极为不平衡即高度不可控这给攻击者提供了攻击的可能。如下图所示：

为了解决这个问题有新的数据结构被提出。

1.3 Patricia Trie

Patricia 一名取自论文 PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric 的首字母缩写也叫压缩前缀树、基数树Radix Tree是 Trie 的一种改进——当某节点只有一个子节点时子节点与父节点进行合并。这使得压缩前缀树可以更高效地用于存储小数据集特别是 key 长度很长时和相同前缀较长的数据集。

2. Merkle Patricia Trie

在了解了 Merkle tree 和 Patricia Trie 之后我们来看看以太坊中的 MPT 树是如何把这两者结合起来以完美地应用两种数据结构的特点。

2.1 节点类型

首先MPT 树可以看成是压缩前缀树一种实现为了实现压缩前缀树MPT 树定义了如下节点类型：

空白节点 NULL
分支节点 branch [ v0 ... v15, vt ]
叶子节点 leaf [encodedPath, value]
拓展节点 extension [encodedPath, key]

其中分支节点就是最基础的 Trie 节点包含长度为 17 的数组为什么是 17 下文会有解释前 16 个元素表示十六进制字符集最后一个元素存储该分支对应的value如果存在；

而拓展节点就是优化后的压缩前缀树新增的节点其中 encodedPath 表示所有被合并的节点字符组合“部分路径”的编码key 指向下一个节点；

叶子节点是拓展节点的一种特殊情况key 在该节点终止value 为对应的值。

2.2 Key 定义

另外一个值得关注的是 MPT 树的 key我们明确下以太坊中定义的各种 key 的概念：

Origin Key：数据的原始 key为字节数组。
Secure Key：为原始 key 计算哈希 Keccak256(Origin Key) 的结果长度固定为 32 字节用于防止深度攻击。后文我们将看到以太坊的状态树和存储树使用这种 Key 类型。
Hex Key：将 Origin Key 或 Secure Key 进行半字节nibble拆解后的 key为 MPT 树真正存储的 key。每个 nibble 的长度为 4 bit可以表示数字 0~15这一步可以看成是将 key 映射到十六进制字符 0~f 组成的字符串这就是为什么分支节点的数组长度为 1716+1。也就是说在以上条件的限制下MPT 树 key 的长度固定为 64 字符。
HP Key：hex prefix encodingHex 前缀编码当我们使用 nibble 寻找路径时我们可能最后会剩下奇数个的 nibble但是由于数据存储的最小单位是字节所以可能会带来一些二义性比如我们可能无法区分 1 或 01都存储为1字节<01>。因此为了区分奇偶长度叶子节点和拓展节点的 encodedPath 使用一个前缀作为标签另外这个标签也用于区分节点类型。

HP 编码规则：

Hex字符	bits	节点类型	部分路径长度
0	0000	拓展节点	偶数
1	0001	拓展节点	奇数
2	0010	叶子节点	偶数
3	0011	叶子节点	奇数

另外对于偶数路径长度的前缀0或2会使用半字节 0 补齐而奇数路径长度的前缀会直接作为半字节拼接到奇数长度路径中使其成为偶数长度。

例子：

拓展节点：
    > 路径nibble值：[ 0, 1, 2, 3, 4, 5, ...] 路径长度为偶数
    HP编码结果：'00 01 23 45'前缀为'00'
    > [ 1, 2, 3, 4, 5, ...] 路径长度为奇数
    '11 23 45'前缀为'1'
叶子节点：
    > [ 0, f, 1, c, b, 8, 10] 路径长度为偶数注：最后一个10为值
    '20 0f 1c b8'前缀为'20'
    > [ f, 1, c, b, 8, 10] 路径长度为奇数
    '3f 1c b8'前缀为'3'

再以一个简化的以太坊世界状态树作为例子：

右上角为简化的 key-value 定义。我们可以看到图中有 2 个拓展节点2 个分支节点4 个叶子节点。在最下面的两个叶子节点中prefix 3 的右边有个格子有个箭头从 7 指向这个格子表示 3 和 7 两个 nibble 组成一个字节存储与我们上面的编码规则是一致的。

2.3 节点哈希

以上我们讲的都是“压缩前缀树”的特点那 MPT 树的“默克尔”部分体现在哪里呢？

实际上当一个节点被另一个节点在内部指向时比如上图中的分支节点内部指向了叶子节点父节点会存储H(rlp.encode(x))其中 H(y) = keccak256(y) if len(y) >= 32 else y rlp.encode 为 RLP 编码函数。即当子节点内容的 RLP 编码结果小于 32 字节时则直接存储在父节点中否则则存储编码结果的哈希值。对于后者如果需要根据哈希读取出子节点的内容还需要在数据库中存储 keccak256(y) 到 y 的映射；而对于前者子节点的内容直接记录在父节点中所以子节点无需再单独存储这可以减少磁盘 IO 次数。

这个特性使得父节点的哈希值计算依赖了子节点也就让 MPT 树具备了“默克尔”的性质。

3. 以太坊“四棵树”

以太坊执行层中的所有默克尔树都使用了 MPT 数据结构。

网上的大多数文章一般都是说以太坊有“三棵树”这是因为以太坊的区块头中存储了以下三个树根：

transactionsRoot 交易根
receiptsRoot 回执根
stateRoot 状态根

从上图中我们可以看到除了区块头中三个树根对应的三棵树之外还有第四棵树——存储树。

下面我们分别来看这四棵树的构成。

3.1 交易树

每个区块都有一棵独立的交易树对应区块头里的交易根。交易树的 key路径为 rlp(transactionIndex)value 为交易序列化后的值。其中 transactionIndex 表示交易在该区块中的下标。

对于交易序列化的细节可参考 EIP 2718。

3.2 回执树

每个交易对应一个交易回执交易回执记录了交易执行结果包括执行状态、Gas消耗、事件日志等。每个区块也有自己的回执树对应了区块头里的回执根。与交易树类似key 为 rlp(transactionIndex)value 为交易回执序列化后的值。

对于交易回执序列化的细节可参考 EIP 2718。

3.3 状态树

状态树要稍微复杂一些。与交易树和回执树不同的是状态树是全局的、不断更新的。它的 key 为 keccak256(ethereumAddress)value 为 rlp(ethereumAccount)。其中 ethereumAddress 表示以太坊账户地址； ethereumAccount 表示以太坊账户包含四个字段 [nonce,balance,storageRoot,codeHash]。

以太坊有两种账户分别是 EOAExternally-Owned Account外部拥有账户和合约账户对于两种账户的介绍和区别可以参考 Ethereum Accounts。简单来说如果 storageRoot 和 codeHash 不为空则为合约账户其中 codeHash 对应合约代码的哈希storageRoot 对应另一棵树的树根这棵树我们称为存储树。

3.4 存储树

这就是我们说的第四棵树。虽然每棵存储树的树根都存储在状态树中但是存储树跟状态树的 key 和 value 都不同所以它值得有自己的名字。

存储树存储了合约的所有状态数据每个合约有单独的存储树。它的 key 为 keccak256(position) value 为 position 对应值32字节的 rlp 编码。其中 position 为状态变量在合约中存储槽的位置用32字节表示比如以下合约代码定义的第一个 uint256 变量 a存储槽为 0那么key为 keccak256(0x00000000000000000000000000000000) 。

contract StorageTest {
    uint256 a;
    // ......
}

当然对于动态长度数组和 Map 等较复杂类型的变量position 计算会稍微复杂一些具体计算方法可参考 Understanding Ethereum Smart Contract Storage。

一个有意思的事实是由于 MPT 树是确定性的所以如果两棵树存储了完全相同的数据那么这两棵树的节点将完全相同包括根节点。因此如果两个相同的合约存储的数据刚好完全相同那么在状态树中它们的 storageRoot 是相等的即对应了同一棵存储树。通过上面 MPT 树的讨论我们知道节点在硬盘中是以节点哈希节点内容这样的键值对存储的所以当两个合约的存储树相同时实际上他们共享了相同的硬盘数据。那么可能会带来这样的疑惑：这两个节点在读写数据时不会冲突吗？自然是不会的。假设在某一时刻当其中一个合约修改了某个变量的数据使得它与另一个合约的数据不同时会生成一个新的节点并从新节点开始由下往上直到根节点整个路径的节点值都会更新新生成的节点会存储到硬盘但旧的节点不会从硬盘删除。

以上图为例左边是区块 175223 的状态树和存储树其中账户 175 有个变量的值为 27假如在区块 175224 中有一个交易的合约调用将该变量的值改为 45那么该值所在节点的哈希会变化从该节点到存储树根节点整个路径的节点内容和哈希也随着变化账户 175 在状态树中的 storageRoot 也会被更新最终影响到状态根的变化。所有受影响的节点都会作为新节点存储而其他节点仍然维持不变这就形成了上图中不同区块对应的状态树共享一部分数据的情形。这样做的好处是显而易见的所有历史数据都不会删除只要拿到区块头中的状态根就能定位到执行到该区块为止的状态数据。

因此当我们调用以太坊的 eth_getStorageAt 接口读取状态数据时我们需要提供合约地址、存储槽位置position、区块ID。根据区块ID可以定位到区块头的状态根哈希根据状态根哈希从硬盘中读取状态根节点再根据状态根节点中的子节点哈希根据需要依次从硬盘读取其他节点从而获取到了状态树；根据合约地址可以从状态树中定位到合约账户信息从中读取 storageRoot 从而定位到存储树；最后我们根据存储槽位置从存储树中读取出状态数据。

比如我们读取合约地址 0x295a70b2de5e3953354a6a8344e616ed314d7251 的存储槽 0 的最新区块下的状态数据请求和响应如下：

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x0", "latest"], "id": 1}' localhost:8545

{"jsonrpc":"2.0","id":1,"result":"0x00000000000000000000000000000000000000000000000000000000000004d2"}