以太坊的Patricia Tree

本文翻译自：https://github.com/ethereum/wiki/wiki/Patricia-Tree#state-trie

目录：

• 什么是MPTree
• 序言：基本 Radix Tries
• 主要说明：MP Trie
• 优化
• 说明：有可选终止符的16进制序列的压缩编码
• 示例
• 以太坊里的Tries
  State Trie
  Storage Trie
  Transactions Trie
  Receipts Trie

一、MPTree

MP tries提供了一种加密认证数据结构，可用来保存所有的（key value)对，本文我们所使用的key和value都是字符串类型（你也可以使用其他数据类型的序列化格式）。这种数据结构非常明确，只要是同样的（key,value）对就会是完全一样，从而保证有同样的根hash，在这种结构中，增加、查找、删除的时间复杂度是 O(log(n))，相对于其他基于比较的算法（如红黑Tries)，这种结构非常易于理解和编码实现，

导读：基本的基数尝试(Radix Tries)

在一个基础的radix trie, 每个节点如下所示

[i0, i1 ... in, value]

这里的 i0 ... in 代表着字母表的符号（通常是二进制或十六进制）， value就是节点最终的值。i0 ... in 上的值可以是空，或者是指向其他节点的指针（在本例中，就是其他节点的hash值）。这组成一个基本的(key,value)存储。比如，如果你想知道key是dog的value值是多少，首先你需要将dog转化为字母表里字母（比如64 6f 67），然后沿着trie找到完整路径上字母连起来是dog的值。也就是说，你先在普通的key/value数据库中找到trie的根结点（通常是指向其他节点key的数组），使用索引6作为key来找下一层的节点，再选择索引4来找下一个节点，再选择索引6，以此类推，如果你沿着 根结点 -> 6 -> 4 -> 6 -> 15 -> 6 -> 7的路径，就能找到节点的值并返回结果。

需要注意的是，trie和潜在的扁平key/value“DB”是有差别的。尽管他们都是key/value对，不过在潜在的DB中是可以象传统数据库查找那样，一步就找到Key值，但在trie中，则需要花上更多步来查找如上所述的key，为避免混淆，在trie中会使用路径来表示。

在radix tries里的更新、删除操作是非常简单的，大体可用如下代码表示：

def update(node_hash, path, value):

 if path == '':

 curnode = db.get(node_hash) if node else [ NULL ] * 17

 newnode = curnode.copy()

 newnode[-1] = value

 else:

 curnode = db.get(node_hash) if node else [ NULL ] * 17

 newnode = curnode.copy()

 newindex = update(curnode[path[0]], path[1:], value)

 newnode[path[0]] = newindex

 db.put(hash(newnode), newnode)

 return hash(newnode)

def delete(node_hash, path):

 if node_hash is NULL:

 return NULL

 else:

 curnode = db.get(node_hash)

 newnode = curnode.copy()

 if path == '':

 newnode[-1] = NULL

 else: 

 newindex = delete(curnode[path[0]],path[1:])

 newnode[path[0]] = newindex

 if len(filter(x -> x is not NULL, newnode)) == 0:

 return NULL

 else:

 db.put(hash(newnode), newnode)

 return hash(newnode)

在radix trie中的Merkle部分，是因为指向节点的是该节点的加密哈希指针，每次在数据库中查找key/value， key == sha(rlp(value))，这和用C语言来实现的传统trie不同。这种方式给数据结构做了加密认证，如果一个给定的trie根hash是公开的，所有人都能够证明，这个trie有一个特定的值，the trie has a given value at a specific path by providing the nodes going up each step of the way.

攻击者用错误的(path,value)是不可能通过的，因为根hash最xgtu是基于其下所有的hash值的，下面结点的变更都会引起根hash值的变化。

每次沿着路径，如上一次一个nibble,大多数的节点是一个有17位元素的数组， 1 index for each possible value held by the next hex character (nibble) in the path, 还有一位在路径结束时，用来标注最终的目标值。这些17位的元素数组节点被称作分支结点。

二、Main specification: Merkle Patricia Trie

然而，radix tries有一个主要的问题：效率太低，如果你需要保存64位长的（nibble数量，byte32)，光是每层一个字母，你需要的存储空间就是上千字节，每次查找和删除也需要64步。所以引入了The Patricia trie 来进行优化。

优化

MP tries给数据结构增加了点复杂度，从来解决操作上的低效。MP tries上的节点有以下四种：
1、NULL（代表字符空串）
2、分支节点：一个17位的节点[ v0 ... v15, vt ]
3、叶子节点 一个2位的节点[ encodedPath, value ]
4、拓展节点：一个2位节点[ encodedPath, key ]

64字母路径会不可避免地遇到这种情况：在经过前面几层后会遇到一个节点，部分路径不会有分叉，这时如果设置一个每个索引都是空的，只有目标索引才有值（指向下一个nibble)是完全没必要的。相应的，我们会建立一个拓展节点来表示，这个拓展节点的结构是[ encodedPath, key ]，encodedPath包含有部分路径，用来向下跳进（ 使用如下所示的压缩编码方式)，key则为下一个db查找。

如果是叶子结点，在它的encodedPath中的第一个nibble会有标识位来说明，当上述情况发生时，也可以设置为部分路径来结束剩下的路径，在这种节点中，value就是它自己的目标值了。

不过，上述的优化又带来了新的问题：

当查找路径时，可能是奇数个nibble，不过由于所有的数据是字节形式，它们之间可能会没有区别。比如，nibble1,和nibble01是一样的（都表示为<01>),为了表示长度是奇数，这些部分路径会有个前缀标识位。

三、Specification: Compact encoding of hex sequence with optional terminator

用来表示部分路径的奇数位和偶数位差别，还有叶子节点和拓展节点的类型标识位，就在部分路径第一个nibble上，如下表所示：

hex char bits | node type partial path length

---

0 0000 | extension even

1 0001 | extension odd

2 0010 | terminating (leaf) even

3 0011 | terminating (leaf) odd

对余下路径长度的偶数（标识位是0或2），另一个0补丁nibble通常如下所示：

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'

这里拓展编码，如何得到MP trie中的一个节点：

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)

示例Trie
假设我们需要一个Trie，包括四个path/value对，('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion').

首先，我们需要把path和value都转换为字节，如下所示。路径实际的字符表示会外打<>，value仍然用字符串‘’显示，for easier comprehension (they, too, would actually be bytes):

<64 6f> : 'verb'

<64 6f 67> : 'puppy'

<64 6f 67 65> : 'coin'

<68 6f 72 73 65> : 'stallion'

现在，我们用下面的key/value对构建了一个Trie

rootHash: [ <16>, hashA ]

hashA: [ <>, <>, <>, <>, hashB, <>, <>, <>, hashC, <>, <>, <>, <>, <>, <>, <>, <> ]

hashC: [ <20 6f 72 73 65>, 'stallion' ]

hashB: [ <00 6f>, hashD ]

hashD: [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]

hashE: [ <17>, hashF ]

hashF: [ <>, <>, <>, <>, <>, <>, hashG, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ]

hashG: [ <35>, 'coin' ]

示例中的根hash = <59 91 bb 8c 65 14 14 8a 29 db 67 6a 14 ac 50 6c d2 cd 57 75 ac e6 3c 30 a4 fe 45 77 15 e9 ac 84>.

When one node is referenced inside another node, what is included is H(rlp.encode(x)), where H(x) = sha3(x) if len(x) >= 32 else x and rlp.encode is the RLP encoding function.

需要注意，当更新trie时，需要存储key/value对(sha3(x), x),保存在一个持续的查找表，如果新创始的节点长度>=32。不过如此这个节点32短，就什么都不用管，因为function f(x) = x是可逆的

四、以太坊里的Tries

以太坊里的merket tries结构使用的都是MP Trie

先看区块头，可以发现有三个根哈希指向三个tries:

• stateRoot
• transactionRoot
• receiptsRoot

State Trie

• 以太坊里有一个全局状态Trie,随时都在更新。这其中，路径的值是sha3(ethereumAddress)，value值则是rlp(ethereumAccount)。一个以太坊 account 是一个4元数组[nonce,balance,storageRoot,codeHash]。需要指出的是这里的storageRoot是另一个patricia tree的根。

Storage Trie

这里所有有效的合约数据。每个帐户都有单独的storage trie。在这个表里，path还是有些复杂的

Transactions Trie

每个区块都有一个单独的事件trie. Path是rlp(transactionIndex)。transactionIndexj 是它自己挖出来序列位。顺序大多数情况下是由矿工来决定的，因此没挖出声来，这些交易的序号是没人知道。当区块挖出来后，这个交易trie就不会再变了。

Receipts Trie

每个区块都有自己的Receipts trie. 这里的path是rlp(transactionIndex). transactionIndex是被挖出来自己挖出来的的索值。从不更新。