以太坊哈希值打头字母 Merkle Patricia Tree Merkle Patricia Tree（MPT）详细介绍

Merkle Patricia Tree[1]，Merkle Patricia Tree以太坊哈希值打头字母，提供了一种基于密码学、自我验证和防篡改的数据结构，用于存储键值对。 以下简称为MPT。 虽然在本规范的范围内，我们将键值的类型限制为只能是字符串（但它仍然适用于所有类型，因为只提供了简单的序列化和反序列化机制，将要存储的类型进行比较与要转换的字符串）。

MPT 没问题。 确定性意味着具有相同内容的密钥将保证找到相同的结果并具有相同的根哈希。 在效率上，树的插入、查找、删除的时间复杂度控制在O(log(n))。 与红黑树相比，MPT更好理解和编码。

一、前言：首乌

在一个标准的基数树中，要存储的数据如下：

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

i0 到 iN 的表示一般是二进制或十六进制格式的字母符号。 value 表示存储在树节点中的最终值。 每个 i0 到 iN 槽的值要么是 NULL，要么是指向另一个节点的指针（在当前场景中，存储的是另一个节点的哈希值）。 这样我们就实现了一个简单的键值存储。 比如你想在这棵基数树中找到key 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

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

1.2 效率问题——帕特里夏树

基数树的另一个主要缺点是效率低下。 即使你只想存储一个键值对，但是键的长度有几百个字符那么长，那么你需要为每个字符的那个级别额外留出很多空间。 每次查找和删除都会有数百个步骤。 这里我们引入帕特里夏树来解决这个问题。

2. 核心规范 2.1 关键数据编码算法

在介绍完整规范之前，我们介绍了一种密钥编码算法，一种带有可选结束标记的十六进制序列的压缩编码。 编码十六进制字符串的传统方法是将它们转换为十进制。 例如0f1248代表三个字节[15,18,72]。 不过这个方法有一个小问题，如果十六进制字符的长度是奇数怎么办。 在这种情况下，无法知道如何将十六进制字符对转换为十进制。 此外，MPT还需要一个额外的特性，即十六进制字符串，在结束节点上，可以有一个特殊的结束标记（一般用T表示）。 结束标签只出现在末尾，而且只出现一次。 也就是说，这里没有结束标志，而是标志位，标志当前节点是否为最终节点，存放的是我们要找的值。 如果不包含结束标签，说明需要指向下一个节点继续查找。

为了解决上述问题。 我们强制使用最终字节流的第一个半字节（nibble，4位，也叫半字节），编码两个标记位。 该标记是否为结束标记和当前字节流的奇偶校验（不包括结束标记）分别存储在第一个半字节的低两位。 如果数据是偶数长度，我们引入一个0值的半字节来保证最终的偶数长度，这样就可以用bytes来表示整个字节流。 编码方式可以参考：

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 flag 是两个flag 中的高位，所以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树

MPT 在解决效率低下的问题的同时，对现有的数据结构进行了一些改进。 MPT的节点类型定义如下。

想法是当有一些节点只有一个元素但路径很长时，将这种层次关系减少到键值对节点[k，v]。 键值是层次树的路径元素，使用上面编码的十六进制字符串，值是节点的哈希值，就像标准的基数树。 另外，我们增加了一个概念上的优化，内部节点不能存值，只有没有子节点的才可以存值。 但是为了让这个键值对存储方案更通用，可以同时存储dog和doge。 我们在字母表中添加了一个结束标记 16，因此一个值不会被错误地指向另一个值。

对于键值节点，二元数组 [k, v]。 v 只能是一个值或一个节点。

对于分支节点，数组 [ v0 ... v15, vt ] 包含 17 个元素。 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' ]

树的构造逻辑是根节点，必须构造一个指向下一个节点的kv节点。 首先对密钥进行编码。 由于当前节点不是尾节点，所以存储的key是奇数个字符，所以leading值为1，由于奇数没有填充，所以最终存储的key是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))。 hash算法为H(x) = sha3(x) if len(x) >= 32 else x，这里的rlp.encode是使用RLP编码函数的方法。 请注意，当更新大于 32 字节的前缀时，您需要将键值对 (sha3(x), x) 存储在持久的仅查找表中。 当小于 32 字节时，不需要转储任何东西。 因为 f(x) 总是等于它自己的值 x。

参考

[1]：文章翻译自：