默克尔帕特里夏字典树

上次修改时间: @DreamInMorning(opens in a new tab), 2024年4月1日

以太坊的状态（全体帐户、余额与智能合约）被编码进一个特殊版本的数据结构中，在计算机科学中，这种数据结构通常称为默克尔树。这种结构可用于许多加密学应用，因为它在树中保存的所有单独数据之间创建了可验证的关系，产生一个可用于证明数据的单独根值。

以太坊的数据结构是一个“修改版默克尔帕特里夏字典树”，之所以这样命名，不仅是因为它引入了 PATRICIA 算法（检索用字母数字编码的信息的实用算法）的一些特性，也由于它旨在实现含有以太坊状态的值的高效数据检索。

默克尔帕特里夏字典树是确定性的并可通过密码学验证：生成状态根的唯一方式是从每个单独的状态进行计算，且两个相同的状态可以通过比较根哈希和父节点哈希（默克尔证明）而轻松证明相同。相反，也无法用同一根哈希创建两个不同的状态，任何用不同值修改状态的尝试都会产生不同的状态根哈希。理论上，这种结构在插入、查找和删除操作上的效率达到了超乎寻常的 O(log(n))。

在不久的将来，以太坊计划迁移到沃克尔树(opens in a new tab)结构，这将为未来的协议改进开创更多新的可能性。

前提条件

为了更好地理解本文，具备以下基础知识将有所帮助：哈希(opens in a new tab)、默克尔树(opens in a new tab)、字典树(opens in a new tab)和序列化(opens in a new tab)。本文从描述基本的基数树(opens in a new tab)开始，并逐步介绍使以太坊数据结构更为优化的必要修改措施。

基数树

在一个基数树中，每个节点如下所示：

1    [i_0, i_1 ... i_n, value]

其中，i_0 ... i_n 代表字母表的符号（通常是二进制或十六进制），value 是节点的终点值，i_0, i_1 ... i_n 插槽的值要么是 NULL，要么是指向其他节点（在本例中，是其他节点的哈希）的指针。这形成了基本的 (key, value) 存储。

假设你想使用基数树数据结构永久保存一组键值对的次序。为了在字典树中找到与键 dog 映射的值，首先需要把 dog 转换成字母表中的字母（给出 64 6f 67），然后沿着该路径向下遍历字典树，直到找到该值。也就是说，为了找到字典树的根节点，你先在平面键/值数据库中查找根哈希。它表示一组指向其他节点的键。你会使用索引 6 的值作为键，并通过在平面键/值数据库中查找该键来获取下一层的节点。然后使用索引 4 查找下一个值，再使用索引 6，以此类推，直到遍历路径 root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7 后，你将找到该节点的值并且返回结果。

从前缀树中查询和从其底层的固定“键/值”数据库中查询存在差异。它们都定义了“键/值”对，但底层数据库能对键执行传统的 1 步查找。而在前缀树中查询一个键对应的值则需要在底层数据库中查询多次才能得到最终结果。我们把后者的查询方式称作 path，以避免描述上的模糊。

基数树的更新和删除操作定义如下：

1    def update(node,path,value):
2        if path == '':
3            curnode = db.get(node) if node else [ NULL ] * 17
4            newnode = curnode.copy()
5            newnode[-1] = value
6        else:
7            curnode = db.get(node) if node else [ NULL ] * 17
8            newnode = curnode.copy()
9            newindex = update(curnode[path[0]],path[1:],value)
10            newnode[path[0]] = newindex
11        db.put(hash(newnode),newnode)
12        return hash(newnode)
13
14    def delete(node,path):
15        if node is NULL:
16            return NULL
17        else:
18            curnode = db.get(node)
19            newnode = curnode.copy()
20            if path == '':
21                newnode[-1] = NULL
22            else:
23                newindex = delete(curnode[path[0]],path[1:])
24                newnode[path[0]] = newindex
25
26            if all(x is NULL for x in newnode):
27                return NULL
28            else:
29                db.put(hash(newnode),newnode)
30                return hash(newnode)
显示全部

“默克尔”基数树是通过使用确定性生成的加密哈希摘要链接节点来构建的。这种（键/值数据库中 key == keccak256(rlp(value))）内容寻址提供了存储数据的加密完整性保障。如果给定字典树的根哈希是公开的，那么任何可以访问底层叶数据的人都可以通过提供将特定值与树根连接的每个节点的哈希，来证明该字典树在特定路径中包含给定值。

对于攻击者来说，他们无法证明 (path, value) 对不存在，因为根哈希从根本上基于它下方的所有哈希。任何底层的修改都会改变根哈希。可以将哈希看作是数据结构信息的一种压缩表示，并由哈希函数的预映射保护所保障。

我们把基数树的原子单位（例如单个十六进制字符或 4 位二进制数）称为“半字节”。如上文所述，以半字节为单位遍历路径时，节点最多可指向 16 个子节点，不过还包含一个 value 元素。因此，我们把它们表示为具有长度 17 的数组。我们把这些有 17 个元素的数组称为“分支节点”。

默克尔帕特里夏树

基数树有一个主要限制：效率低下。如果你想将一个 (path, value) 对存储在路径长度为 64 个字符（bytes32 中的半字节数）的位置（如以太坊中），我们需要超过一千字节的额外空间将每个字符存储一个层级，并且每次查询或删除都需要执行完整的 64 个步骤。下文介绍的帕特里夏字典树可以解决这个问题。

优化

默克尔帕特里夏树的节点可以是以下任意一种：

NULL（表示为空字符串）
branch，一个 17 元素节点 [ v0 ... v15, vt ]
leaf，一个双元素节点 [ encodedPath, value ]
extension，一个双元素节点 [ encodedPath, key ]

在 64 个字符的路径中，遍历前缀树的前几层后，一定会到达这样的节点：至少部分下游再无分支路径。为了避免在路径中创建多达 15 个稀疏 NULL 节点，我们通过设置一个形式为 [ encodedPath, key ] 的 extension 节点来精简向下遍历，其中 encodedPath 包含要跳过的“部分路径”（使用下面描述的压缩编码），key 用于下一次数据库查询。

对于 leaf 节点，可以使用 encodedPath 的第一个半字节中的标志来标记，其路径编码了所有先前节点的路径片段，并且我们可以直接查询 value。

然而，上述优化造成了模棱两可。

当以半字节遍历路径时，最后我们可能需要遍历奇数个半字节，但是所有数据都需要以 bytes 格式存储。两者之间是无法区分的，例如，半字节 1 和半字节 01（两者都必须存储为 <01>）。要指定奇数个半字节的长度，这部分路径要使用标记位作为前缀。

规范：带有可选终止符的十六进制序列的压缩编码

如上文所述，剩余部分路径长度为奇数 vs 偶数和叶节点 vs 扩展节点的标记位位于任意双元素节点中部分路径的第一个半字节。从而产生以下结果：

1hex char    bits    |    node type partial     path length
2----------------------------------------------------------
3   0        0000    |       extension              even
4   1        0001    |       extension              odd
5   2        0010    |   terminating (leaf)         even
6   3        0011    |   terminating (leaf)         odd

对于剩余路径长度为偶数的情况（0 或 2），一定会附加一个 0“占位”半字节。

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term: hexarray = hexarray[:-1]
4        oddlen = len(hexarray) % 2
5        flags = 2 * term + oddlen
6        if oddlen:
7            hexarray = [flags] + hexarray
8        else:
9            hexarray = [flags] + [0] + hexarray
10        // hexarray now has an even length whose first nibble is the flags.
11        o = ''
12        for i in range(0,len(hexarray),2):
13            o += chr(16 * hexarray[i] + hexarray[i+1])
14        return o
显示全部

示例：

1    > [ 1, 2, 3, 4, 5, ...]
2    '11 23 45'
3    > [ 0, 1, 2, 3, 4, 5, ...]
4    '00 01 23 45'
5    > [ 0, f, 1, c, b, 8, 10]
6    '20 0f 1c b8'
7    > [ f, 1, c, b, 8, 10]
8    '3f 1c b8'

以下为获取默克尔帕特里夏树中节点的扩展代码：

1    def get_helper(node,path):
2        if path == []: return node
3        if node = '': return ''
4        curnode = rlp.decode(node if len(node) < 32 else db.get(node))
5        if len(curnode) == 2:
6            (k2, v2) = curnode
7            k2 = compact_decode(k2)
8            if k2 == path[:len(k2)]:
9                return get(v2, path[len(k2):])
10            else:
11                return ''
12        elif len(curnode) == 17:
13            return get_helper(curnode[path[0]],path[1:])
14
15    def get(node,path):
16        path2 = []
17        for i in range(len(path)):
18            path2.push(int(ord(path[i]) / 16))
19            path2.push(ord(path[i]) % 16)
20        path2.push(16)
21        return get_helper(node,path2)
显示全部

前缀树示例

假定我们想要包含四个路径/值对 ('do', 'verb')、('dog', 'puppy')、('doge', 'coin')、('horse', 'stallion') 的前缀树。

首先，我们将路径和值都转换为 bytes。在下方代码中，路径的实际字节代表用 <> 表示。而值仍然显示为字符串，用 '' 表示，以便于理解（值也应为 bytes）：

1    <64 6f> : 'verb'
2    <64 6f 67> : 'puppy'
3    <64 6f 67 65> : 'coin'
4    <68 6f 72 73 65> : 'stallion'

现在，我们使用底层数据库中的以下键/值对构建了这样一棵前缀树：

1    rootHash: [ <16>, hashA ]
2    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
3    hashB:    [ <00 6f>, hashD ]
4    hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
5    hashE:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coin' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

当一个节点在另一个节点内部引用时，包含的是 H(rlp.encode(x))，其中 H(x) = keccak256(x) if len(x) > > = 32 else x 和 rlp.encode 是递归长度前缀编码函数。

请注意，更新前缀树时，如果新创建节点的长度 >= 32，则需要将键/值对 (keccak256(x), x) 存储在一个持久的查询表中。然而，如果节点比这短，则不需要存储任何数据，因为函数 f(x) = x 是可逆的。

以太坊中的前缀树

以太坊执行层中的所有默克尔树均使用默克尔帕特里夏树。

在区块头，有来自 3 棵前缀树的 3 个根。

stateRoot
transactionsRoot
receiptsRoot

状态树

有一个全局状态字典树，每次客户端处理一个区块时它都会更新。其中，path 始终为：keccak256(ethereumAddress)，value 始终为：rlp(ethereumAccount)。更具体地说，一个以太坊 account 是包含 4 个元素的数组：[nonce,balance,storageRoot,codeHash]。关于这一点值得注意的是，storageRoot 是另一个帕特里夏字典树的根：

存储树

存储树是所有合同数据存放之处。每个帐户都有一棵单独的存储树。要用给定地址在特定的存储位置检索值，需要存储地址、存储器中存储数据的整数位置，以及区块 ID。之后，这些数据可以作为参数传入 JSON-RPC 应用程序接口中定义的 eth_getStorageAt，例如用于检索地址 0x295a70b2de5e3953354a6a8344e616ed314d7251 的存储插槽 0 中的数据：

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

更多的是检索存储器中的其他元素，因为必须首先计算存储树中的位置。该位置作为地址和存储位置的 keccak256 哈希值进行计算，两者都从左侧开始用零填充 32 个字节的长度。例如，地址 0x391694e7e0b0cce554cb130d723a9d27458f9298 的数据在存储时隙 1 中的位置是：

1keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))

在 Geth 控制台中，可以按以下方式计算：

1> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
2undefined
3> web3.sha3(key, {"encoding": "hex"})
4"0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9"

因此，path 是 keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>)。与以前相同，此地址现在可用于从存储树检索数据：

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

注意：如果不是合约帐户，以太坊帐户的 storageRoot 默认为空。

交易树

每个区块都有一个独立的交易字典树，也用于存储 (key, value) 对。路径为：rlp(transactionIndex)，代表了对应一个值的键，值由以下决定：

1if legacyTx:
2  value = rlp(tx)
3else:
4  value = TxType | encode(tx)

关于这个问题的更多信息可以在 EIP 2718(opens in a new tab) 文档中找到。

收据树

每个区块都有自己的收据树。此处的 path 是：rlp(transactionIndex)。 transactionIndex 是它在挖矿区块中的索引。收据字典树从不更新。与交易字典树类似，它也有当前和以前的收据。为了在收据字典树中查询特定的收据，需要提供区块中交易的索引、收据有效载荷以及交易类型。返回的收据可以是 Receipt 类型，定义为 TransactionType 和 ReceiptPayload 的串联；也可以是 LegacyReceipt 类型，定义为rlp([status, cumulativeGasUsed, logsBloom, logs])。