以太坊MPT数据结构

末蓝、 2022-03-25 07:24 375阅读 0赞

# Trie树 #

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

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

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

常见的用来存英文单词的trie每个节点是一个长度为27的指针数组，index0-25代表a-z字符，26为标志域。如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 1]

## 传统trie的局限 ##

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

# Patricia树 #

Patricia树，或称Patricia trie，或crit bit tree，压缩前缀树，是一种更节省空间的Trie。对于基数树的每个节点，如果该节点是唯一的儿子的话，就和父节点合并。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 3]

# 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列表校验数据块。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 4]  
Merkle Tree可以看做Hash List的泛化（Hash List可以看作一种特殊的Merkle Tree，即树高为2的多叉Merkle Tree。

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

官方数据结构如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 6]  
上图存储的key-value如下：

![在这里插入图片描述][20190119135058500.png]  
从前面结构图可以看出，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既可表示  
![在这里插入图片描述][20190119135150728.png]  
接着插入a77d337,由于和a711355共享前缀’a7’,因而可以创建’a7’扩展节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 7]  
接着插入a7f9365,也是共享’a7’,只需新增一个leaf node.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 8]  
最后插入a77d397,这个key和a77d337共享’a7’+’d3’,因而再需要创建一个’d3’扩展节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 9]  
MPT节点有个flag字段,flag.hash会保存该节点采用merkle tree类似算法生成的hash,同时会将hash和源数据以<hash, node.rlprawdata>方式保存在leveldb数据库中。这样后面通过hash就可以反推出节点数据。具体结构如下(蓝色的hash部分就是flag.hash字段)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 10]  
这样一个结构的核心思想是：hash可以还原出节点上的数据，这样只需要保存一个root(hash)，即可还原出完整的树结构，同时还可以按需展开节点数据，比如如果只需要访问<a771355, 45>这个数据，只需展开h00, h10, h20, h30这四个hash对应的节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 11]

# 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 编码的基本逻辑如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 12]  
很简单，就是将 keybytes 中的 1byte 信息，将高 4bit 和低 4bit 分别放到两个 byte 里，最后在尾部加 1byte 标记当前属于 Hex 格式。这样新产生的 key 虽然形式还是 \[\]byte，但是每个 byte 大小已经被限制在 4bit 以内，代码中把这种新数据的每一位称为 nibble。这样经过编码之后，带有\[\]nibble 格式的 key 的数据就可以顺利的进入 fullNode.Children\[\] 数组了。  
之所以会被拆分为高低4为，是因为数组只有16位，最多可以存储16进制的f，24=16。但是一个字节是8位，是28=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。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 13]  
如上图所示，

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

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

## 为什么要进行编码 ##

先看Hex prefix 编码的以太坊白皮书  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 14]  
![在这里插入图片描述][20190119135507345.png]  
其中各符合的定义：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其实是针对叶子节点

![在这里插入图片描述][20190119135548962.png]

参考资料

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70]: /images/20220325/aa5c34da9d9c4676b72aa66920e3f200.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 1]: /images/20220325/97d13537d198452f88e21b6d0c72c223.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 2]: /images/20220325/e719f934f4814ae789d3a59136678ab2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 3]: /images/20220325/9b7943bb25e744ea818a5bed8155756d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 4]: /images/20220325/334bfc77c9a94333a6fe8f74899df2bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 5]: /images/20220325/fece0ac6e0494ba697ed3e7517cc5bd6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 6]: /images/20220325/1a97d73aa0e04beea8b76228b92e2b7c.png
[20190119135058500.png]: /images/20220325/58687a6889e244abbabe29d3ac1cf1dc.png
[20190119135150728.png]: /images/20220325/eb570312631f4f8caa14268f953c8044.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 7]: /images/20220325/cb4ffec2fd6a45c1a9012533e7b5024e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 8]: /images/20220325/89cdf08dc2a24a05a1883ebfcebe8646.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 9]: /images/20220325/e6253bb2f5dd41578e4854cf6db0e635.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 10]: /images/20220325/09095c1e26b44ba1aecb61f28ddd27b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 11]: /images/20220325/746fff963eca4e98aa7fac187904737b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 12]: /images/20220325/6284b56f1db14369ab789dc419e9618d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 13]: /images/20220325/436826748fa54d73bbc24c8dabac87ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70 14]: /images/20220325/eb169cd119c749da9c65ac0682da8419.png
[20190119135507345.png]: /images/20220325/a96f9a9ae95742798fbee127331971c6.png
[20190119135548962.png]: /images/20220325/3c236343db884e0e8c0a7c6c50c268da.png
[Merkle-Patricia Trie_MPT]: https://www.jianshu.com/p/1e7455d00065
[Link 1]: https://blog.csdn.net/zxkr777/article/details/82146064
[MPT_Merkle Patricia Tree]: https://blog.csdn.net/qq_33935254/article/details/55505472
[Merkle Patricia Tree _MPT_ _merkle]: https://blog.csdn.net/zslomo/article/details/53434883
[MPT]: https://blog.csdn.net/itleaks/article/details/79992072