月度归档:2019年09月

Merkle Patricia Trie(翻译)

Published / by sickworm / Leave a Comment

原文: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    |    终止节点 (叶子节点)         奇数         

对于偶数剩余路径长度(02),将始终跟随另一个“填充”的半字节 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)