Merkle Patrcia Tree原理

Merkle Patrcia Tree 是结合了Merkle Tree和Patricia Tree两种数据类型的优点的数据结构，所以我们接下来将分别讨论这几种树。

一 Merkle Tree

1  Merkle Tree

Merkle Tree（梅克尔树）可以是二叉树，也可以是多叉树；最下面的叶子节点包含基数数据，非叶子节点存储的是其子节点的hash。

以下是一个典型的Merkle Tree，他拥有四个交易，其结构如下：

比特币区块链的每个区块都有一个Merkle Tree，区块头中的Merkle Root（也称为Merkle树的根哈希值）是由区块体中所有交易的哈希值生成的。

2  Merkle Tree特性

每个数据集对应一个唯一合法的根散列值。

很容易更新、添加、删除树节点，以及生成新的根散列值。

数据的修改必然会影响根的hash值，比特币区块链中可以根据Merkle Root信息验证这棵树的正确性。

可以只提供一个到特定节点的分支，并通过密码学方法证明拥有对应内容的节点确实在树里。

3  Merkle Root

1)   数字摘要

Merkle中任何数据的修改，都会影响其对应的Hash值，并逐步传导到上层，直到Root节点，这意味着树根节点是底层所有数据的数字摘要。

如图所示，当一个数据被篡改后，N3、N6、Root的hash值都将改变。在区块链中，任何一个用户试图通过一个虚假的交易，替换Merkle底部的交易时，这个改变都将会导致根部hash值的改变。

2)   零知识证明

基于这个图我们再考虑另外一个问题，如何确认Dx是否是{D1, D2, D3, D4}这个集合中的一部分呢？

举一个实际中的场景：BTC的持有者为了进行交易，需要将BTC寄存在交易所，理论上交易所可以将用户寄存的账户余额挪作它用，那么用户如何知道交易所没有将自己的账户余额挪用，交易所如何自证清白。这就意味着需要在不公布每个用户的余额（会泄露用户的隐私）的情况下，让每个用户都认可自己的余额被包含在了总的准备金中，那如何才能做到这一点呢？

假设{A1, A2, A3, A4, ...}是用户的账户，交易所如何在不告诉任何其他用户账户余额的情况下向A3证明，本交易所没有动过你寄存的BTC？

首先构建一颗Merkle Tree,末端代表用户的账户余额，交易所只需要向用户提供相邻节点的hash值，以及父节点的兄弟节点的hash值即可，用户可以通过追溯父节点的方式，确保自己的余额被包含在父节点中，进而确认被包含在root节点中。如下图所示。

4  应用场景

1)   快速比较大量数据

相同数据的默克尔树根是相同的。对需要比较的每组数据构建默克尔树，当两个默克尔树根不同，则说明这两组数据必然存在差异，如果两个默克尔树根相同，意味着两组数据相同（hash碰撞概率极小，如果有顾虑，可以在逐个对比）。

2)   快速定位修改

因为默克尔树的任何数据修改，都会传导到根节点，所以当根节点数据变化以后，通过二叉树的快速查找特性，定位到修改的节点。例如当D1修改以后，通过Root->N4->N1即可找到D1发生修改，时间复杂度为O( lgN )。

3)   零知识证明

如果想证明某组数据（D1、D2、D3、…、DN）中拥有某数据Dx，可以构建出默克尔树，然后判断Dx的拥有者的默克尔树根和此组数据的默克尔树根是否相同即可。

具体证明过程，参考上面的示例。

5  应用-简单支付验证（SPV）

在比特币系统中，很多时候用户只关心与自己相关的交易。例如：当用户收到他人发来的比特币时，只希望知道交易是否合法，区块是否是共识区块，而不需要自己做完整校验，典型场景是比特币钱包客户端。

中本聪曾在比特币白皮书里提到，“不运行全节点也可以验证支付，用户只需要保存所有的区块头（Block Header）就可以了。用户虽然不能自己验证交易，但如果能够从区块链的某处找到相符的交易，他就可以知道网络已经认可了这笔交易，而且得到了网络的多个确认。”这就是SPV，即简单支付验证。因为每个区块头仅80字节，每10分钟左右产生一个区块，所以一年下来也就4M左右的数据，即便是将目前所有区块头信息保存下来，也就几十M的数据量。

下面以比特币钱包的客户端为例来讨论，如何通过SPV验证某一笔交易的合法性。当收到一个转账交易时，假设要验证此交易对应的输入是合法的，那么就需要验证此交易输入对应的区块（假设名为Block A）是存在的，并且是得到网络共识的区块。SPV的验证过程如下：

 - 钱包客户端节点从区块链网络上获取并存储最长链的所有区块头至本地。

 - 根据交易输入中的hash值定位到区块（Block A），并判断此区块的header是否在本地保存的区块头中，如果不存在则说明非法。

 - 从区块（Block A）中获取构建Merkle Tree值，计算出Merkle Tree Root的hash值，将此计算出的hash值与区块（Block A）头中的Merkle root值进行比较，相同则认为交易是真实的。

 - 根据区块（Block A）头在区块链上的位置，确认此区块是否是共识的区块。

二 Trie Tree

Patricia Tree是一种压缩前缀树，在了解Patricia Tree之前，我们先了解一下前缀树（Trie Tree）。

1  Trie Tree

Trie Tree（前缀树或字典树）也成为Radix Tree，是一种有序树。在Tire Tree中，key一般为字符串，代表的是从树根到对应value的一条真实路径；即从根节点开始，key中的每个字符（从前到后）都代表着从根节点出发寻找对应value所要经过的子节点；value存储在叶子节点中，是每条路径的最终节点。

2  Trie Tree特性

根节点不包含字符，除根节点外每一个节点都只包含一个字符。

从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的key。

每个节点的所有子节点包含的字符都不相同。

3  Trie Tree优缺点

优点：如果有两个value，他们key相同前缀的长度占自身比例越大，意味着这两个value在树中的位置越靠近，并且Trie树中不会有想散列表一样的冲突，也就是说key永远只对应一个value。

缺点：存储不平衡问题，即给定一个长度较长的key，在树中没有其他key与它有相同的前缀，那么遍历或者存储key所代表的value时，将会遍历或存储相当多的节点，这颗树就越不平衡。

4  Trie Tree示例

假设有以下数据需要通过Trie Tree存储：

那么存储后的结构如下所示：

三 Patricia Tree

Patricia Tree（也称Patricia trie，或crit bit tree），是一种压缩前缀树，可以认为是一种更节省空间的Trie Tree。对于基数树的每个节点，如果该节点是唯一的儿子的话，就和父节点合并。

假设有以下数据需要通过Patrica Tree存储：

那么存储后的结构如下所示：

四 Merkle Patrcia Tree

1  Merkle Patrcia Tree

Merkle Patrcia（MPT）树是一种加密认证的数据结构，它结合了Merkle树和Patricia树（压缩前缀树）两种数据类型的优点。

下图就是一个典型的MPT树，它由2个扩展节点，2个分支节点，4个叶子节点构成。（此图从网上截取）

2  节点类型

MPT树有四种类型的节点：空节点、叶子节点（B、D、F、G）、扩展节点（C）和分支节点（A、E）。

1)   空节点（Empty Node）

简单的表示空，在代码中是一个空串。

2)   叶子节点（Leaf Node）

是一个键值对[key,value]，其中key是key的一种特殊十六进制编码，value是value的RLP编码。

图中有四个叶子节点，他们的key、value分别如下：

3)   扩展节点（Extension Node）

叶子节点、扩展节点的结构定义是共享的。一个键值对[key，value]，只不过value是其他节点的hash值，通过hash链接到其他节点，即可以通过这个hash查询数据库中的节点。

这种设计的目的是：

²   当整棵树被持久化到数据库中时，保持节点间的关联关系；

²   从数据库中读取节点时，尽量避免不必要的IO开销；

在内存中，父节点与子节点之间关联关系可以通过引用、指针等编程手段实现，但是当树节点持久化到数据库时，父节点中会存储一个子节点在数据库中的索引值，以此保持关联关系。同样，从数据库中读取节点时，本着最小IO开销的原则，仅需要读取那些需要用到的节点数据即可，因此若目前该节点已经包含所需要查找的信息时，便无须将其子节点再读取出来；反之，则根据子节点的哈希索引递归读取子节点，直至读取到所需要的信息。

4)   分支节点（Branch Node）

分支节点是一个长度为17的列表，MPT树中的key被编码成一种特殊的16进制的表示，所以前16个元素对应着key中的16个可能的十六进制字符，再加上最后的value，组成一个长度为17的列表。如果有一个[key,value]在这个分支节点终止，最后一个元素存储的就是这个value，由此可见分支节点既可以搜索路径的终止也可以是路径的中间节点。

3  key编码

说明：因为key编码规则是固定的，所以此节的内容大部分上都来自网上，未做过多改动。

在以太坊中对MPT树的key值提供了三种不同的编码方式，以满足不同场景，编码方式如下：

 - Raw编码（原生的字符）；

 - Hex编码（扩展的16进制编码）；

 - Hex-Prefix编码（16进制前缀编码）；

1)  Raw编码

Raw编码就是原生的key值，不做任何改变。这是MPT对外提供接口的默认编码方式。

例如一条key为“cat”，value为“dog”的数据项，其Raw编码就是['c', 'a', 't']，换成ASCII表示方式就是[63, 61, 74]

2)   Hex编码

为了减少分支节点孩子的个数，需要将key的编码进行转换，将原key的高低四位分拆成两个字节进行存储。这种转换后的key的编码方式，就是Hex编码。Hex编码用于对内存中MPT树节点key进行编码。

从Raw编码向Hex编码的转换规则是：

 - 将Raw编码的每个字符，根据高4位低4位拆成两个字节；

 - 若该Key对应的节点存储的是真实的数据项内容（即该节点是叶子节点），则在末位添加一个ASCII值为16的字符作为终止标志符；

 - 若该key对应的节点存储的是另外一个节点的哈希索引（即该节点是扩展节点），则不加任何字符；

key为“cat”, value为“dog”的数据项，其Hex编码为[3, 15, 3, 13, 4, 10, 16]

3)   HP编码

叶子节点、扩展节点这两种节点定义是共享的，所以需要通过一种额外的机制来区分节点的类型。

以太坊通过HP编码对存储在数据库中的叶子节点、扩展节点的key进行编码区分。持久化到数据库之前，首先从Hex编码转换成HP编码。HP编码的规则如下：

 - 若原key的末尾字节的值为16（即该节点是叶子节点），去掉该字节；

 - 在key之前增加一个半字节，其中最低位用来编码原本key长度的奇偶信息，key长度为奇数，则该位为1；低2位中编码一个特殊的终止标记符，若该节点为叶子节点，则该位为1；

 - 若原本key的长度为奇数，则在key之前再增加一个值为0x0的半字节；

 - 将原本key的内容作压缩，即将两个字符以高4位低4位进行划分，存储在一个字节中（Hex扩展的逆过程）；

key为“cat”, value为“dog”的数据项，Hex编码为[3, 15, 3, 13, 4, 10, 16]，HP编码的值为[32, 63, 61, 74]

4)   编码转换关系

Raw编码：原生的key编码，是MPT对外提供接口中使用的编码方式，当数据项被插入到树中时，Raw编码被转换成Hex编码；

Hex编码：16进制扩展编码，用于对内存中树节点key进行编码，当树节点被持久化到数据库时，Hex编码被转换成HP编码；

HP编码：16进制前缀编码，用于对数据库中树节点key进行编码，当树节点被加载到内存时，HP编码被转换成Hex编码；

4  安全性

1)   问题

MPT树可以用来存储内容为任何长度的key-value数据项。倘若数据项的key长度没有限制时，当树中维护的数据量较大时，仍然会造成整棵树的深度变得越来越深，会造成以下影响：

 - 查询一个节点可能会需要许多次IO读取，效率低下；

 - 系统易遭受Dos攻击，攻击者可以通过在合约中存储特定的数据，“构造”一棵拥有一条很长路径的树，然后不断地调用SLOAD指令读取该树节点的内容，造成系统执行效率极度下降；

 - 所有的key其实是一种明文的形式进行存储；

2)   改进

为了解决以上问题，在以太坊中对MPT再进行了一次封装，对数据项的key进行了一次哈希计算，因此最终作为参数传入到MPT接口的数据项其实是(sha3(key), value)

3)   优劣

优势：传入MPT接口的key是固定长度的（32字节），可以避免出现树中出现长度很长的路径；

劣势：每次树操作需要增加一次哈希计算；需要在数据库中存储额外的sha3(key)与key之间的对应关系；

5  基本操作

MPT的基本操作包括Get、Insert、Delete、Update、Commit，类似于DB的增删改查和提交操作。详细内容可以参考《MPT的基本操作》

五 参考文档

1  书籍

《以太坊技术详解与实战》

2  博客

BlockChain 与Ethereum 介绍

Merkle Tree- 哈希树证明的简单概念/原理/用途分析

干货| Merkle Patricia Tree 详解

MPT的基本操作