Merkle Patricia Tree 梅克尔帕特里夏树(MPT)规范

TryBlockchain   |     |   1025 次阅读

Merkle Patricia Tree [1],梅克尔帕特里夏树,提供了一个基于加密学的,自校验防篡改的数据结构,用来存储键值对关系。后文中将简称为MPT。尽管在本规范范围内,我们限定键值的类型只能是字符串(但仍对所有的类型适用,因为只需提供一个简单的序列化和反序化机制,将要存储的类型与字符串进行转换即可)。

MPT是确定的。确定性是指同样内容的键值,将被保证找到同样的结果,有同样的根哈希。关于效率方面,对树的插入,查找,删除的时间复杂度控制在O(log(n))。相较于红黑树来说,MPT更好理解和编码实现。

1. 前言:基数树(Radix Tree)

在一个标准的基数树里,要存储的数据,按下述所述:

[i0, i1, ... iN, value]

其中的i0iN的表示一般是二进制或十六进制的格式的字母符号。value表示的是树节点中存储的最终值。每一个i0iN槽位的值,要么是NULL,要么是指向另一个节点的指针(在当前这个场景中,存储的是其它节点的哈希值)。这样我们就实现了一个简单的键值对存储。举个例子来说,如果你想在这个基数树中,找到键dog所对应的值。首先需要将dog转换为比如ascii码值(十六进制表示是646f67)。然后按字母序形成一个逐层向下的树。沿着字母组成的路径,在树的底部叶节点上,即找到dog对应的值。具体来说,首先找到存储这个键值对数据的根节点,找到下一层的第6个节点,然后再往下一层,找到节点4,然后一层一层往下找,直到完成了路径 root -> 6 -> 4 -> 6 -> f -> 6 -> 7。这样你将最终找到值的对应节点。

基数树的更新和删除操作比较简单,可以按下面的定义:

def update(node,key,value):
    if key == '':
        curnode = db.get(node) if node else [ NULL ] * 17
        newnode = curnode.copy()
        newnode[-1] = value
    else:
        curnode = db.get(node) if node else [ NULL ] * 17
        newnode = curnode.copy()
        newindex = update(curnode[key[0]],key[1:],value)
        newnode[key[0]] = newindex
    db.put(hash(newnode),newnode)
    return hash(newnode)

def delete(node,key):
    if key == '' or node is NULL:
        return NULL
    else:
        curnode = db.get(node)
        newnode = curnode.copy()
        newindex = delete(curnode[key[0]],key[1:])
        newnode[key[0]] = newindex
        if len(filter(x -> x is not NULL, newnode)) == 0:
            return NULL
        else:
            db.put(hash(newnode),newnode)
            return hash(newnode)

1.1 数据校验问题 - Merkle Tree

基数树的节点关系,一般是使用比如C语言的32位或64位的内存地址指针来串联起来的。但在以太坊中为了实现数据的防篡改及校验,我们引入了Merkle Tree,使用节点的哈希值来建立节点关系。这样,如果一个给定的前缀的根哈希值是已知的,那么任何人都可以根据这个前缀来检查。对于一个攻击者,不可能能证明一个不存在键值对存在,因为根哈希最终依赖所有的下面的哈希值,所以任何的修改都会导致根哈希值的改变。

1.2 效率问题 - Patricia树

基数树另一个主要的缺陷是低效。即使你只想存一个键值对,但其中的键长度有几百字符长,那么每个字符的那个层级你都需要大量的额外空间。每次查找和删除都会有上百个步骤。在这里我们引入Patricia树来解决这个问题。

2. 核心规范

2.1 键数据的编码算法

在介绍完整规范前,我们先介绍一个对键的编码算法,十六进制序列的带可选结束标记的压缩编码。传统的编码十六进制字符串的方式,是将他们转为了十进制。比如0f1248表示的是三个字节的[15,18,72]。然而,这个方式有点小小的问题,如果16进制的字符长度为奇数呢。在这种情况下,就没有办法知道如何将十六进制字符对转为十进制了。额外的,MPT需要一个额外的特性,十六进制字符串,在结束节点上,可以有一个特殊的结束标记(一般用T表示)。结束标记仅在最后出现,且只出现一次。或者说,并不存在一个结束标记,而是存在一个标记位,标记当前节点是否是一个最终结点,存着我们要查找的值。如果不含结束标记,则是表明还需指向下一个节点继续查找。

为了解决上述的这些问题。我们强制使用最终字节流第一个半字节(半个字节,4位,也叫nibble),编码两个标记位。标记是否是结束标记和当前字节流的奇偶性(不算结束标记),分别存储在第一个半字节的低两位。如果数据是偶数长,我们引入一个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

上面的代码可以看出来,如果要表示的是T结尾的字符串,term值取1,否则取0。如果为奇数长,取值1,否则取值0。由于term标记是两个标记中的较高位,所以将term乘2来左移一位。如果不算后面的结束标记的字节流是奇数的,就不补位。如果是偶数数位,就补一个值为零的半字节。

一些实际的转换例子:

> [ 1, 2, 3, 4, 5 ]
'\x11\x23\x45'  ( Here in python, '\x11#E' because of its displaying unicodes. ) 
//不含结束,所以没有结束标记,由于字节流是奇数,标记位取值1,不补位,所以前面只补一个半字节就好。
> [ 0, 1, 2, 3, 4, 5 ]
'\x00\x01\x23\x45'
//不含结束标记的偶数,且由于是偶数第一个nibble是0,由于是偶数位,需要补一个值为零的nibble,所以是00。紧跟后面的值。
> [ 0, 15, 1, 12, 11, 8, T ]
'\x20\x0f\x1c\xb8'
//由于有结束标记,除结束标记的长度为偶数,所以第一个nibblie是2,由于是偶数长补位一个值为0的nibble,所以最后加20。
> [ 15, 1, 12, 11, 8, T ]
'\x3f\x1c\xb8'
//由于有结束标记,且为奇数,第一个值为3,又由于是奇数不需要补位,值是3加后面的值。

2.2 Merkle Patricia Tree

MPT在解决低效的问题时,对当前的数据结构进行了一些改进。MPT的节点类型定义如下。

  • NULL(空字符串)
  • 两个元素的数组[k, v](又名键值对节点)
  • 一个17个元素的数组。[v0 ... v15, vt]。(又名分支结点)

思路是,是当出现一些一个元素的节点,但却有很长路径的情况时,将这种层级关系缩减为一个键值对节点[k, v]。其中键值为层级树的路径元素,使用为上述编码的十六进制串,值为节点的哈希值,就像标准的基数树一样。另外,我们增加了一个概念的优化,关于内部节点不能存值,只有那些没有孩子节点的可以存值。但为了让这个键值对存储方案变得更通用,可以同时存储dogdoge。我们增加了一个结束标记16到字母表,所以不会存在一个值被错误指向到另一个值的情况。

对于一个键值对节点,两个元素的数组[k, v]。v只能是一个值或者节点。

  • 当v是一个值时,k必须是含结束标记的半字节按上述的紧凑的编码串。
  • 当v是指向另一个节点时,k必须是不含结束标记的半字节按上述的紧凑编码串。

对于一个分支结点,一个17个元素的数组[ v0 ... v15, vt]。在v0到v15的每个元素,要么是一个节点,要么是空,而vt则总是一个值,或空。所以如果只是在v0到v15中的其中一个元素中存储值,我们应该使用键值对节点,其中的k是对包含结尾标记的一个空的半字节列表编码结果。

下面是在MPT中获取一个节点的代码:

def get_helper(node,key):
    if key == []: 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 == key[:len(k2)]:
            return get(v2, key[len(k2):])
        else:
            return ''
    elif len(curnode) == 17:
        return get_helper(curnode[key[0]],key[1:])
def get(node,key):
    key2 = []
    for i in range(len(key)):
        key2.push(int(ord(key) / 16))
        key2.push(ord(key) % 16)
    key2.push(16)
    return get_helper(node,key2)

例子,假设我们有一个树有这样一些值('dog', 'puppy'), ('horse', 'stallion'), ('do', 'verb'), ('doge', 'coin')。首先,我们将它们转为十六进制格式:

[ 6, 4, 6, 15, 16 ] : do => 'verb'
//64 6f
[ 6, 4, 6, 15, 6, 7, 16 ] : dog => 'puppy'
//64 6f 67
[ 6, 4, 6, 15, 6, 7, 6, 5, 16 ] : doge => 'coin'
//64 6f 67 65
[ 6, 8, 6, 15, 7, 2, 7, 3, 6, 5, 16 ] : horse => 'stallion'
//68 6f 72 73 65

创建的树,如下图所示:

ROOT: [ '\x16', A ]
A: [ '', '', '', '', B, '', '', '', C, '', '', '', '', '', '', '', '' ]
B: [ '\x00\x6f', D ]
D: [ '', '', '', '', '', '', E, '', '', '', '', '', '', '', '', '', 'verb' ]
E: [ '\x17', F ]
F: [ '', '', '', '', '', '', G, '', '', '', '', '', '', '', '', '', 'puppy' ]
G: [ '\x35', 'coin' ]
C: [ '\x20\x6f\x72\x73\x65', 'stallion' ]

树的构造逻辑是root结点,要构造一个指向下一个结点的kv节点。先对键编码,由于当前节点不是结束结点,存值的键为奇数字符数,所以前导值为1,又由于奇数不补位,最终存键为0x16。它指向的是一个全节点A。下一层级,要编码的是d和h的第二个半字节,4和6。所以在A节点的第五个位置(从零开始)和第七个位置,我们可以看到分别被指向到了B和C两个节点。对于B节点往后do,dog,doge来说。他们紧接着的都是一个编码为6f的o字符。所以这里,B节点被编码为指向D的kv结点,数据是指向D节点的。其中键值存6f,由于是指向另一个节点的kv节点,不包含结束标记,且是偶数,需要补位0,得到00,最终的编码结果是006f。后续节点也以此类推。

当在一个节点中引用另一个节点时,其中包含的是H(rlp.encode(x))。其中哈希算法是H(x) = sha3(x) if len(x) >= 32 else x,这里的rlp.encode,是使用RLP编码函数的方法。需要注意的是当更新一个超过32字节前缀时,你需要保存键值对(sha3(x), x)在一个持久化的只查表中。当小于32字节时,则不需要转存任何东西。因为f(x)始终等于它本身值x。

关于作者

专注基于以太坊(Ethereum)的相关区块链(Blockchain)技术,了解以太坊,Solidity,Truffle,web3.js。

个人博客: http://me.tryblockchain.org
版权所有,转载注明出处

参考资料

[1]: 文章翻译自: https://github.com/ethereum/wiki/wiki/Patricia-Tree

 
0 人喜欢