跳转至主要内容

默克尔帕特里夏字典树

上次编辑: , Invalid DateTime

默克尔帕特里字典树夏树提供了一种经过加密认证的数据结构,可用于存储所有 (key, value) 对。

默克尔帕特里夏树是完全确定性的,这意味着有相同 (key, value) 对的字典树肯定是完全相同的,就连最后一个字节也相同。 这代表它们有着相同的根哈希,让插入、查找和删除操作具有难以企及的 O(log(n)) 效率。 此外,相较于更复杂的基于比较的其他字典树(如红黑树),默克尔帕特里夏树更易于理解和编码。

前提条件

为了更好地理解本文,具备以下基础知识将有所帮助:哈希(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]
2

其中,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)
31
显示全部

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

对于攻击者来说,他们无法证明 (path, value) 对不存在,因为根哈希从根本上基于它下方的所有哈希。 任何底层的修改都会改变根哈希。

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

默克尔帕特里夏树

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

优化

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

  1. NULL(表示为空字符串)
  2. branch,一个 17 元素节点 [ v0 ... v15, vt ]
  3. leaf,一个双元素节点 [ encodedPath, value ]
  4. 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
7

对于剩余路径长度为偶数的情况(02),一定会附加一个 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
15
显示全部

示例:

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'
9

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

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)
22
显示全部

前缀树示例

假定我们想要包含四个路径/值对 ('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'
5

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

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' ] ]
6

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

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

以太坊中的前缀树

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

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

  1. stateRoot
  2. transactionsRoot
  3. 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
5

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

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

在 Geth 控制台中,可以按以下方式计算:

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

因此,pathkeccak256(<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"}
4

交易树

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

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

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

收据树

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

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

延伸阅读

本文对您有帮助吗?