以太坊的MPT树，以及编码，leveldb存储

声明：此为使用网上多处资料整理而成，由于很多地方内容相同，已经分不清哪里是原创

一.MPT树

1. Trie树

Trie，又称为字典树或者前缀树 (prefix tree)，属于查找树的一种。它与平衡二叉树的主要不同点包括：

• 每个节点数据所携带的 key 不会存储在 Trie 的节点中，而是通过该节点在整个树形结构里位置来体现(下图中标注出完整的单词，只是为了演示Trie的原理)；
• 同一个父节点的子节点，共享该父节点的 key 作为它们各自 key 的前缀，因此根节点 key 为空；
• 待存储的数据只存于叶子节点和部分内部节点中，非叶子节点帮助形成叶子节点 key 的前缀。下图展示了一个简单的 Trie 结构
  
  上图是一个简略视图，实际上trie每个节点是一个确定长度的数组，数组中每个节点的值是一个指向子节点的指针，最后有个标志域，标识这个位置为止是否是一个完整的字符串，并且有几个这样的字符串

常见的用来存英文单词的trie每个节点是一个长度为27的指针数组，index0-25代表a-z字符，26为标志域。如图：

2. 传统trie的局限

1）高度不可控
如上图所示，如果有一个字符串很长，且跟其他字符串没有公共前缀，就会形成这样的一棵极其不平衡的树，整棵树的性能会被少量的这样的字符串拖慢，并且给攻击者提供了可能
2） 安全系数不高
传统的trie是由内存指针来连接节点，并且字符串的值就相当于存储在这棵树中，两者完全暴露在外，毫无安全性可言

3. Patricia树

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

4. Merkle树

Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash

要了解Merkle Tree就要先从Hash List说起：

在点对点网络中作数据传输的时候，会同时从多个机器上下载数据，而且很多机器可以认为是不稳定或者不可信的。为了校验数据的完整性，更好的办法是把大的文件分割成小的数据块（例如，把分割成2K为单位的数据块）。这样的好处是，如果小块数据在传输过程中损坏了，那么只要重新下载这一快数据就行了，不用重新下载整个文件。

怎么确定小的数据块没有损坏哪？只需要为每个数据块做Hash。BT下载的时候，在下载到真正数据之前，我们会先下载一个Hash列表。那么问题又来了，怎么确定这个Hash列表本身是正确的哪？答案是把每个小块数据的Hash值拼到一起，然后对这个长字符串在作一次Hash运算，这样就得到Hash列表的根Hash(Top Hash or Root Hash)。下载数据的时候，首先从可信的数据源得到正确的根Hash，就可以用它来校验Hash列表了，然后通过校验后的Hash列表校验数据块。

Merkle Tree可以看做Hash List的泛化（Hash List可以看作一种特殊的Merkle Tree，即树高为2的多叉Merkle Tree。

在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应。但是往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个”子哈希“。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希。于是往上推，依然是一样的方式，可以得到数目更少的新一级哈希，最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root。

在p2p网络下载网络之前，先从可信的源获得文件的Merkle Tree树根。一旦获得了树根，就可以从其他从不可信的源获取Merkle tree。通过可信的树根来检查接受到的MerkleTree。如果Merkle Tree是损坏的或者虚假的，就从其他源获得另一个Merkle Tree，直到获得一个与可信树根匹配的MerkleTree。

Merkle Tree和HashList的主要区别是，可以直接下载并立即验证Merkle Tree的一个分支。因为可以将文件切分成小的数据块，这样如果有一块数据损坏，仅仅重新下载这个数据块就行了。如果文件非常大，那么Merkle tree和Hash list都很慢，但是Merkle tree可以一次下载一个分支，然后立即验证这个分支，如果分支验证通过，就可以下载数据了。而Hash list只有下载整个hash list才能验证。

4. Merkle树的应用场景

1） 快速比较大量数据 叶子节点数据的细微改动，都会导致根节点发生变化，可以用根节点是否变化来判定叶子数据是否改动过
2）快速定位数据块的修改 如果上图中L2的数据发生变化，那么就会影响Hash0-1，Hash0，Top Hash，根据树的特性，从根节点到叶子节点，只需要通过O(logn)便能定位到实际发生改变的数据是L2
3）零知识证明 为了证明某个论断是否正确，通常我们需要将数据发送给验证者。Merkle树提供了一种方法，可以证明某方拥有某数据，而不需要将原始数据发送给对方。如上图所示，我们只需要将L1，Hash0-1，Hash1，Root对外公布，任何拥有L1数据的用户，经过计算可以获得同样的Root值，说明该公开用户拥有数据，L2，L3，L4

二.以太坊中的MPT

1. 官方数据结构

上图中存储的值(只有叶子节点会存储值）

从前面结构图可以看出，Merkle Patricia Tree有4种类型的节点：

• 叶子节点（leaf），存储的是真实的数据，
• 扩展节点（extension），扩展节点合并相同的前缀，扩展节点下面是分支节点，上图中共享"d3"
• 分支节点（branch），因为在以太坊协议中，不管是地址还是hash，都是一个16进制串，所以是数字，16进制一共16个数字表示0～9，还有a,b,c,d,e,f;不会出现其他字母，MPT树中的key被编码成一种特殊的16进制的表示，再加上最后的value，所以分支节点是一个长度为17的list，前16个元素对应着key中的16个可能的十六进制字符，如果有一个[key,value]对在这个分支节点终止，最后一个元素代表一个值，即分支节点既可以搜索路径的终止也可以是路径的中间节点。分支节点的父亲必然是extension node。由于分支节点是16长度数组，故该节点减少了层高和存储空间
• 空节点，代码中用null表示

每个节点都有一个前缀，表明此节点是哪种类型

	节点类型	奇偶数
0	扩展节点	偶数
1	扩展节点	奇数
2	叶子节点	偶数
3	叶子节点	奇数

扩展节点下面一定是分支节点，所以没有前缀

奇数和偶数编码的意义主要是用在下面要介绍HP编码的时候，可以看下面的详细介绍。

2.该MPT树的演变过程

插入第一个<a711355, 45>，由于只有一个key,直接用leaf node既可表示

接着插入a77d337,由于和a711355共享前缀’a7’,因而可以创建’a7’扩展节点。

接着插入a7f9365,也是共享’a7’,只需新增一个leaf node.

最后插入a77d397,这个key和a77d337共享’a7’+’d3’,因而再需要创建一个’d3’扩展节点

3.MPT树的存储

MPT节点有个flag字段,flag.hash会保存该节点采用merkle tree类似算法生成的hash,同时会将hash和源数据以<hash, node.rlprawdata>方式保存在leveldb数据库中。这样后面通过hash就可以反推出节点数据。具体结构如下(蓝色的hash部分就是flag.hash字段)

levelDB的存储结构有点像这样：

key	value
h00(roothash)	hash(0+a7+h10)
h10	hash(h20+h21+h22)
h20	hash(0+1355+h30)
h21	hash(0+d3+h31)
h22	hash(0+9365+h32)
h30	45
h31	hash(h40+h41)
h32	1.1
h40	hash(0+7+h50)
h41	hash(0+7+h51)
h50	1.0
h51	0.12

这样一个结构的核心思想是：hash可以还原出节点上的数据，这样只需要保存一个roothash(h00)，即可还原出完整的树结构，同时还可以按需展开节点数据，比如如果只需要访问<a771355, 45>这个数据，只需展开h00, h10, h20, h30这四个hash对应的节点

以太坊的编码方式

以太坊采用LevelDB做数据库，如何将MPT树的节点映射成键值对存储到LevelDB呢？

以太坊的MPT树提供了三种不同的编码方式来满足不同场景的不同需求，三种编码方式为；

• Raw编码（原生字符）
• Hex编码（扩展16进制编码）
• Hex-Prefix编码（16进制前缀编码）
  三者的关系如下图所示，分别解决的是MPT对外提供接口的编码，在内存中的编码，和持久化到数据库中的编码。
  

1. Raw编码

MPT对外提供的API采用的就是Raw编码方式，这种编码方式不会对key进行修改，如果key是“foo”, value是”bar”，编码后的key就是[“f”, “o”, “o”]。

假设我们要把a作为key放入MPT树，key可以直接用a的ASCII表示97就可以了。

2. Hex编码

1）为什么要进行Hex编码

在以太坊协议中，不管是地址还是hash，都是一个16进制串，所以是数字，16进制一共16个数字表示0～9，还有a,b,c,d,e,f;不会出现其他字母,这和比特币的地址不一致。如"0x5b3edbcf7d0a97e95e57a4554a29ea66601b71ad"，数据最小的表示单位为一位16进制，2^4=16,用4bit可以表示十六进制所有数字，如1、a等，但在编程实现中，数据的最小表示单位往往是byte（8bit，2位16进制数），这样在用byte来表示一串奇数长度的16进制串时会出现问题，如"5b3"和"5b30"，直接转成byte都是5b30（每个16进制字符按4位存，需要两个字节，但是第13-16位都是0，即101101100110000）。还有一种简单直观的转换方式，“5b3”->“050b03”（每个16进制都占用8位存储空间，这样就不需要补位），这就是Hex编码

思考：可以不生成奇数字符串吗？可以直接使用字符串存储吗？会有什么问题

2）Hex编码如何解决这个问题

以太坊先定义了一个新单位nibble，一个nibble表示4个bit，0.5个byte。然后按照如下规则编码；

将Raw输入的每个字符（1byte）拆分成2个nibble，前4位和后4位各一个nibble；

1101 拆分为 00001101;0110拆分为00000110

将每个nibble扩展为1个byte（8个bit）；
然后分别将Raw编码后的十六进制结果的每个b进行如下操作
b / 16；
b % 16；
有疑惑的话看一下这个例子就懂了

a的ASCII编码为99（十进制），转换十六进制为63
采用Hex编码
[0] = 61 / 16 = 3
[1] = 61 % 16 = 13
编码后的结果 [3, 13]
在举个例子
输入"cat"，Raw编码后 [63, 61, 74]
63 / 16  = 3
63 % 16 = 15
61 / 16 = 3
61 % 16 = 13
74 / 16 = 4
74 % 16 = 10
编码后的结果 [3，15，3，13，4，10]
树的最后一位value是一个标识符，如果存储的是真实的数据项，即该节点是叶子节点，则在末尾添加一个ASCII值为16的字符作为终止标识符。添加后的结果是[3，15，3，13，4，10, 16]

3. HP编码（Hex-Prefix Encoding，16进制前缀编码）

前面介绍的Hex编码后的数据是在内存中的，如果要对Hex编码后的数据进行持久化，就会发现一个问题，我们对原数据进行了扩展，本来1个byte的数据被我们变成了2个byte，显然这对于存储来说是不可接受的，于是就又有了HP编码。

HP编码的过程如下；

• Compact 编码首先将 Hex 尾部标记 byte 去掉，然后将原本每 2 nibble 的数据合并到 1byte，即Raw编码；
• 增添 1byte 在输出数据头部以放置 Compact 格式标记位00100000（偶数）；
• 如果输入 Hex 格式字符串有效长度为奇数，将 Hex 字符串的第一个 nibble 放置在标记位 byte 里的低 4bit,并增加奇数位标志 0011xxxx，这样后面的数据就是偶数了，可以存储到byte里面

举个例子：

"cat"经过HP编码后的结果 [3，15，3，13，4，10, 16]
再用HP编码

1. 去掉16，同时表明这个是叶子节点。
2. 叶子节点，nibble数量是奇数个，这两个条件得出需要填充的值为 0010 0000
3. 将HP编码后的结果用二进制表示 [0010, 0000，0011, 1111, 0011, 1101, 0100, 1010]
4. 将HP编码后的结果合并成byte，为[00100000, 00111111, 00111101, 01001010]转换为十进制是[32, 63, 61, 74]
   相较与cat的Raw编码，经过上面的Hex编码和HP编码，既可以能在内存中构建出MPT树，又可以尽可能减小存储所占用的空间，不得不说以太坊设计的巧妙。