Trie树

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

• 每个节点数据所携带的 key 不会存储在 Trie 的节点中，而是通过该节点在整个树形结构里位置来体现(下图中标注出完整的单词，只是为了演示Trie的原理)；
• 同一个父节点的子节点，共享该父节点的 key 作为它们各自 key 的前缀，因此根节点 key 为空；
• 待存储的数据只存于叶子节点和部分内部节点中，非叶子节点帮助形成叶子节点 key 的前缀。下图展示了一个简单的 Trie 结构

上图是一个简略视图，实际上trie每个节点是一个确定长度的数组，数组中每个节点的值是一个指向子节点的指针，最后有个标志域，标识这个位置为止是否是一个完整的字符串，并且有几个这样的字符串

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

传统trie的局限

高度不可控

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

Patricia树

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

Merkle树

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

MPT（Merkle Patricia Tree）树

官方数据结构如下：

上图存储的key-value如下：

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

• 叶子节点（leaf），表示为[key,value]的一个键值对。和前面的英文字母key不一样，数据库中的key是节点的RLP编码的sha3哈希，value是节点的RLP编码
• 扩展节点（extension），也是[key，value]的一个键值对，但是这里的value是其他节点的hash值，通过hash链接到其他节点
• 分支节点（branch），因为MPT树中的key被编码成一种特殊的16进制的表示，再加上最后的value，所以分支节点是一个长度为17的list，前16个元素对应着key中的16个可能的十六进制字符，如果有一个[key,value]对在这个分支节点终止，最后一个元素代表一个值，即分支节点既可以搜索路径的终止也可以是路径的中间节点。分支节点的父亲必然是extension node。扩展节点合并相同的前缀，扩展节点下面是分支节点。由于分支节点是16长度数组，故该节点减少了层高和存储空间
• 空节点，代码中用null表示

该MPT树的演变过程

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

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

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

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

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

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

MPT 中对 key 的编码

MPT中涉及到了三种编码，分别为keybytes编码、Hex编码和Compact编码

keybytes 编码这种编码格式就是原生的key字节数组，大部分的Trie的API都是使用这边编码格式

hex prefix编码: 当 [k,v] 数据插入 MPT 时，它们的 k(key)都必须经过编码。这时对 key 的编码，要保证原本是 []byte 类型的 key 能够以 16 进制形式按位进入 fullNode.Children[]，因为 Children[] 数组最多只能容纳 16 个子节点。相应的，Ethereum 代码中在这里定义了一种编码方式叫 Hex，将 1byte 的字符大小限制在 4bit(16 进制)以内。

先来看 Hex 编码的实现，Hex 编码的基本逻辑如下图：

很简单，就是将 keybytes 中的 1byte 信息，将高 4bit 和低 4bit 分别放到两个 byte 里，最后在尾部加 1byte 标记当前属于 Hex 格式。这样新产生的 key 虽然形式还是 []byte，但是每个 byte 大小已经被限制在 4bit 以内，代码中把这种新数据的每一位称为 nibble。这样经过编码之后，带有[]nibble 格式的 key 的数据就可以顺利的进入 fullNode.Children[] 数组了。
之所以会被拆分为高低4为，是因为数组只有16位，最多可以存储16进制的f，2^{4=16。但是一个字节是8位，是2}8=256。显然无法存下那么大的数据。故将其拆分为高低4位，这样就可以使用长度16的数据结构存储了。

问题：为什么不将扩展节点的长度设置为256？都是数组，时间复杂度并没有提升啊。而且这样可以简化读写操作。

节点被加载到内存里面的时候key使用的是这种编码，因为它的方便访问。

Hex 编码虽然解决了 key 是 keybytes 形式的数据插入 MPT 的问题，但代价也很大，就是数据冗余。典型的如 shortNode，目前 Hex 格式下的 Key，长度会变成是原来 keybytes 格式下的两倍。这一点对于节点的哈希计算，比如计算 hashNode，影响很大。所以 Ethereum 又定义了另一种编码格式叫 Compact，用来对 Hex 格式进行优化。

Compact 编码:又叫 hex prefix 编码，它的主要意图是将 Hex 格式的字符串恢复到 keybytes 的格式，同时要加入当前 Compact 格式的标记位，还要考虑在奇偶不同长度 Hex 格式字符串下，避免引入多余的 byte。

如上图所示，

• Compact 编码首先将 Hex 尾部标记 byte 去掉，然后将原本每 2 nibble 的数据合并到 1byte；
• 增添 1byte 在输出数据头部以放置 Compact 格式标记位00100000；
• 如果输入 Hex 格式字符串有效长度为奇数，还可以将 Hex 字符串的第一个 nibble 放置在标记位 byte 里的低 4bit,并增加奇数位标志 0011xxxx。
  节点放入数据库时候的key用到的就是Compact编码，可以节约磁盘空间。

源码中的CommData.cpp是上述几种格式编码互相转换的实现。

为什么要进行编码

先看Hex prefix 编码的以太坊白皮书


其中各符合的定义：x是一个nibble（半字节，在计算机中，通常将8位二进制数称为字节，而把4位二进制数称为半字节）数组，t是标志位，用以标志节点类型。

在以太坊协议中，不管是地址还是hash，都是一个16进制串，如"0x5b3edbcf7d0a97e95e57a4554a29ea66601b71ad"，数据最小的表示单位为一位16进制，2^4=16,用4bit可以表示十六进制所有数字，如1、a等，但在编程实现中，数据的最小表示单位往往是byte（8bit，2位16进制数），这样在用byte来表示一串奇数长度的16进制串时会出现问题，如"5b3"和"5b30"，直接转成byte都是5b30（紧凑编码，每个16进制字符按4位存，可以看到需要两个字节，但是第13-16位都是0）。还有一种简单直观的转换方式，“5b3”->“050b03”（每个16进制都占用8位存储空间），这种方式虽然简单，但是数据量会翻倍，不利于大量hash的计算，同时也会增加tree的大小，降低同步性能。Hex-Prefix Encoding能解决这些问题。

下面举个具体例子说明编码过程：

对"0x5b3ed"编码（奇数位）

“0x5b3ed” = “0005 1011 0003 1110 1101”

t=0 时, “0001”+“0005 1011 0003 1110 1101”->“00010005 10110003 11101101”->“0x15b3ed”

t !=0时 “0011”+“0005 1011 0003 1110 1101”->“00110005 10110003 11101101”->“0x35b3ed”

对"0x5b3e"编码（偶数位）

“0x5b3e” = “0005 1011 0003 1110”

t=0 时, “0000”+“0005 1011 0003 1110 1101”->“00000005 10110003 11101101”->“0x005b3e”

t !=0时 “0010”+“0005 1011 0003 1110 1101”->“00100005 10110003 11101101”->“0x205b3e”

t=0与t!=0实际用处， t=0是其实是针对拓展节点，t!=0其实是针对叶子节点

参考资料

以太坊源码（一）Merkle-Patricia Trie(MPT)的实现
以太坊存储分析（整合）
深入浅出以太坊MPT（Merkle Patricia Tree）
Merkle Patricia Tree (MPT) 以太坊merkle技术分析
以太坊MPT原理，你最值得看的一篇