Merkle Patricia Trie是完全确定性的，这意味着具有相同（键，值）绑定的Patricia trie具有相同的根hash，具有O(log(n) )插入查找和删除的效率，而且比基于比较的查找方法如红黑树更容易理解和编码。

1 基本的radix trie

基本的radix trie像下面这样(节点类型只有一种：分支节点):

[i0, i1 ... in, value]  //前面存放索引， 后面存放value（可选）

比如key='dog', 转换为16进制是64 6f 67。
在底层key/value数据库中,先找到根节点hash, 根节点就是一个其他节点hash的list, 然后在list的索引=6取出i5,是下一级节点的hash值, 在底层数据库中根据该hash值找到该节点的list, 这样一级一级往下找,最后找到对应的value.

root → 6 → 4 → 6 → 15 → 6 → 7

这个和底层扁平数据库查询不一样, 扁平数据库对key查找一次就行,在trie中要在底层数据库中查找多次才能找到value, 为了消除歧义，让我们将后者称为 **路径** 。

代码实现大致如下:

# node: 节点数据
# path/value 数据对
def update(node,path,value): #插入一个空path, 表示新建一个trie树
 if path == '': 
    #新建扩展节点或者使用传入的节点数据
   curnode = db.get(node) if node else [ NULL ] * 17 
   newnode = curnode.copy()
   newnode[-1] = value #保存该path的value
 else: # path非空
    #新建扩展节点或者使用传入的节点数据
   curnode = db.get(node) 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,path):
 if node is NULL:
   return NULL
 else:
   curnode = db.get(node)
   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)

可见上述代码没有考虑数据存储空间和查找性能, Patricia Trie是压缩trie树, 更适合工程上使用.

2 radix trie结合merkle

merkle出现在: 指向下一级节点的指针是使用 节点的确定性加密hash ** ** （对于key/value型数据库,每次查询 key == sha3(rlp(value)) ， 而不是传统意义上下一级节点地址的指针(C语言实现)。
这为数据结构提供了一种密码认证;
如果给定的trie的根哈希是公开的，则任何人都可以 通过给出给定path上的所有节点, 来证明在给定path上存在一个给定值 ，对于攻击者,不可能提供一个不存在的（path，value）对的证明, 因为根哈希最终基于它下面的所有哈希，所以任何修改都会改变根哈希。

在如上所述一次遍历一个半字节的path中，大多数节点是包含17个元素的数组。 前16个索引代表path中的下一个十六进制字符（半字节）所保持的每个可能值，以及在路径已经完全遍历的情况下保存的最终目标值。 这17个元素的数组节点被称为 分支节点 ** ** 。

3 Merkle Trie 结合Patricia

radix tries 从查找性能和空间占用方面效率都比较低, Patricia 树通过扩展节点解决该问题.

扩展节点的形式是 [ encodedPath, key ] , encodepath是压缩路径编码, 通过第一个半字节标识和叶子结点进行区分.

当以半字节遍历路径时，我们可能会以 奇数 个半字节来遍历，但是因为所有的数据都是以 字节格式 存储的，所以不可能区分例如 半字节1和半字节01 （都是 必须保存为<01>）。 要指定奇数长度，部分路径前面加上一个 标志 。如下:

image

odd是奇数长度, 不需要附加一个0, even是偶数长度,需要附加一个0

def compact_encode(hexarray):
  term = 1 if hexarray[-1] == 16 else 0 # 16表示结束符
  if term: hexarray = hexarray[:-1] # 将结束符去掉
     oddlen = len(hexarray) % 2 # 计算是否是奇数长度
     flags = 2 * term + oddlen # 奇数长度带16=>3 不带16=>1 偶数长度带16=>2 不带16=>0
  if oddlen: # 奇数长度 
     hexarray = [flags] + hexarray
  else: #偶数长度需要补0
     hexarray = [flags] + [0] + hexarray
 # hexarray 现在有一个奇数长度, 第一个 nibble 是 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, 16]
'20 0f 1c b8'
> [ f, 1, c, b, 8, 16]
'3f 1c b8'

Merkle Patricia trie中获取节点的代码(待验证):

# path格式是半字节的list
# node是节点数据的hash值
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) #将半子节数据组装为字节,并加上flag,去掉16
  if k2 == path[:len(k2)]: # curnode是扩展节点
     return get(v2, path[len(k2):]) # 去掉部分路径
   else:
     return ''
   elif len(curnode) == 17: # 表示是分支节点
 return get_helper(curnode[path[0]],path[1:])

# path是正常key的字符串
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) # 再压入结束符16, 表示是叶子节点
 return get_helper(node,path2) # 格式如: [ f, 1, c, b, 8, 16]

4 例子

4个path/value pairs :

('do', 'verb'), 
('dog', 'puppy'),
('doge', 'coin'),
('horse', 'stallion') .

将path和value转换为bytes类型,<>表示bytes, value实际上还是也是,方便理解还是写成字符串:

<64 6f> : 'verb' <64 6f 67> : 'puppy' <64 6f 67 65> : 'coin' <68 6f 72 73 65> : 'stallion'

在底层数据库中存储的key/value对: 一个trie树

image

一个节点被另一个节点引用时, 引用方式是H(rlp.encode(x)), 其中 H(n) = sha3(n) if len(n) ≥ 32 else n ; rlp.encode表示rlp编码

上述:

1. 根节点中<16>: 1表示扩展奇数节点, 6表示公共的key
2. hashA是分支节点: hashB和hashC的位置表示key=4, key=8
3. hashC中: 20表示叶子偶数节点,6f 72 73 65表示剩余的key
4. hashD是分支节点: 'verb'表示上一级扩展节点的value

6 以太坊block中的默克尔-帕特里夏树

有3种类型的树:

1. 状态树 stateRoot

是全局的树

path = sha3(ethereumAddress) 以太坊账户地址

value = rlp([nonce,balance,storageRoot,codeHash]) 交易次数, 账户余额,存储树,合约代码hash

其中storageRoot是另一个trie树,存储合约的所有数据,每个账户都有各自的树独立存储

1. 交易树 transactionsRoot

每个block都有一个交易树

path = rlp(transactionIndex) 该交易在block中的索引, 顺序由矿工决定

value = 交易记录

该树生成后永远不会被修改

1. 凭证树 receiptsRoot

同上