Merkle Patricia Trie（翻译）

区块链  ·  2019年9月24日

原文：https://github.com/ethereum/wiki/wiki/Patricia-Tree

改良的 Merkle Patricia Trie 规范（又称为 Merkle Patricia Tree）

Merkle Patricia Trie（下简称 MPT 树，Trie 又称前缀树或字典树）尝试提供一种加密认证的数据结构，其可用于存储任意类型的的键值对。本文仅讨论键值对为字符串的情况（对于其他类型，只需要使用某种序列化方式将其转换为字符串即可）。这些键值对是完全确定的，这意味着两颗具有相同键值对的 Patricia 前缀树，它们的数据是保证完全一致的，因此也拥有相同的根哈希（root hash）。MPT 树提供优秀的 O(log(n)) 时间复杂度的插入，查询和删除性能。此外 MPT 树也比一些基于比较的替代方案（如红黑前缀树）更好理解和实现。

主要技术指标：Merkle Patricia Trie

但是，radix 树有一个较大的缺点：存储效率很低。举个例子，如果你只存储一个路径/值对，而这个路径长64个字符（32 字节的半字节（Hex）表示，正如以太坊的状态树一样），你将需要近 1K 的额外空间，一层一个字符地存储这个路径，并在需要删除它的时候花上整整 64 步。本文的 Patricia 树正是用来解决这个问题的。

改进

MPT 树通过提高原本的数据结构的复杂度，来尝试解决效率问题。MPT 树的节点可分为 4 种类型：

1. NULL 空节点，用于表示空字符串
2. branch 分支节点，具有 17 个项 [v0 ... v15, vt]
3. leaf 叶子节点，具有 2 个项 [ encodedPath, value ]
4. extension 扩展节点，具有 2 个项 [ encodedPath, key ]

在使用长为 64 个字符的路径的情况下，在遍历前缀树的前面几层的节点之后，后面层的节点很大可能都不再是发散的路径，而是一条单一路径。如果此时还按照前面的节点一样配置 index（Hex 字符集，共 16 个），则除了其中 1 个 index 不为空之外（即目标路径的下一个字符），剩余 15 个 index都是空的。这样做显然是不明智的。所以我们使用扩展节点 [ encodedPath, key ] 来快速处理这种单一路径。其中，encodePath 包含要跳过的"局部路径"（partial path，使用了下面提到的紧凑编码），key 用于下一次的数据库查询。

对于用 encodePath 第一个半字节就可以确定的叶子节点，上面提到的情况同样存在，且跳过的"局部路径"即完整路径的剩余部分。此时 value 即目标值。

当遍历半字节路径时，我们可能最终得到一个奇数个半字节的遍历路径。但因为所有的数据是以 bytes 格式存储的，因此不可能区分下面这种情况：半字节 1，和半字节 01 （两者都应该存储为 <01>）。所以如果要指定奇数长度，则在局部路径加上前缀标记。

规范：带可选终结符的十六进制序列的紧凑编码

上面提到，局部路径的首位半字节用于标记一个 2 项节点的属性：奇数剩余路径长度/偶数奇数剩余路径长度 和 叶子节点/扩展节点 。定义如下：

 HEX 值     位值     |     节点局部路径类型           路径长度
----------------------------------------------------------
   0        0000    |        扩展节点                偶数        
   1        0001    |        扩展节点                奇数         
   2        0010    |    终止节点 （叶子节点）         偶数        
   3        0011    |    终止节点 （叶子节点）         奇数         

对于偶数剩余路径长度（0 或 2），将始终跟随另一个“填充”的半字节 0。

def compact_encode(hexarray):
    term = 1 if hexarray[-1] == 16 else 0 
    if term: hexarray = hexarray[:-1]
    oddlen = len(hexarray) % 2
    flags = 2 * term + oddlen
    if oddlen:
        hexarray = [flags] + hexarray
    else:
        hexarray = [flags] + [0] + hexarray
    // hexarray now has an even length whose first nibble is the flags.
    o = ''
    for i in range(0,len(hexarray),2):
        o += chr(16 * hexarray[i] + hexarray[i+1])
    return o

示例：

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

以下是在 MPT 树中获取节点的扩展代码：

def get_helper(node,path):
    if path == []: return node
    if node = '': return ''
    curnode = rlp.decode(node if len(node) < 32 else db.get(node))
    if len(curnode) == 2:
        (k2, v2) = curnode
        k2 = compact_decode(k2)
        if k2 == path[:len(k2)]:
            return get_helper(v2, path[len(k2):])
        else:
            return ''
    elif len(curnode) == 17:
        return get_helper(curnode[path[0]],path[1:])

def get(node,path):
    path2 = []
    for i in range(len(path)):
        path2.push(int(ord(path[i]) / 16))
        path2.push(ord(path[i]) % 16)
    path2.push(16)
    return get_helper(node,path2)

#ETH #MPT #前缀树 #字典树