以太坊MPT原理

「爱情、让人受尽委屈。」 2022-05-20 03:05 257阅读 0赞

MPT的全称是Merkle Patricia Tree, 从这里可以看出MPT是Merkle Tree + Patricia Tree。接下来就就来讲讲这两种树:

## Merkle Tree ##

区块链P2P网络中，如果需要传输的数据很大，就需要同时从多个机器上下载数据，而且很可能有些机器是不稳定(可能下载速度很慢)或者不可信的(需要重新下载)。为了快速下载大块数据并验证，更好的办法是把大文件分割成小的数据块（例如把大文件分割成4K为单位的小数据块）。这样的好处是如果小块数据在传输过程中损坏了或者是错误的数据，那么只要重新下载这一块数据就行了，不用重新下载整个文件。

由于只有大文件内容的hash, 当其中一块小数据错误时，我们是能检出由小块数据拼凑出来的大数据是错误的，但是我们不知道哪块小数据是错误的，就没法通过重传错误的小数据来纠正。哪怎么处理呢？为每个小块生成hash, 节点先把小块数据的hash都下载下来，然后就可以验证一个一个验证小块数据是否正确了。那问题又来了，小块数据的hash的正确性谁来保证呢？信任节点，比如BT论坛上的bt种子文件，这个种子文件就记录了原始文件的小块数据的hash. 验证问题解决了，但是多出来了小块数据hash，当块数据很大时，这个数据量也不小。因而Merkle Tree出来了，它就是用来解决这个问题的。

小块数据的hash两两组合再次生成新的hash,然后新生成的hash又两两合并生成更新的hash,直至最后两个hash生成一个hash root,这个叫merkle root(默克尔根)。可见merkle tree和传统bt分片技术只是对小块数据hash的组织方式不一样。

![SouthEast][]

看到上面的图，你可能会说，merkle tree不是生成更多hash数据了啊，怎么能降低数据传输量。确实，对于数据发送方来说，相比传统分片技术，它是需要保存完整merkle tree, 会多占用一点空间。但是对于接受方来说，它在验证某一块数据不需要下载全部hash,只需一段merkle 路径即可，比如下图

![SouthEast 1][]

如果要验证slice2数据的正确性，只需要拿到hash1, h12, h02这3个hash再加上本地存储的root hash,就可以验证了。需要传输的hash数据量从n变为log2n.

总结，Merkle root(包含在区块头里)是从可信渠道下载的(主链或者可信节点)，接收到数据及这个数据对应的Merkle验证路径即可验证该数据的正确性。

## Patricia Tree ##

patricia tree 前缀树，是一种编码方式,它是传统trie的改进。

### Trie树 ###

Trie，又称前缀树或字典树，是一种有序树状的数据结构，其中的键通常是字符串，常用语存储Key-value数据结构。

Trie与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，节点对应的key是根节点到该节点路径上的所有节点key值前后拼接而成，节点的value值就是该key对应的值。根节点对应空字符串key。

如果key是英文单词，trie的每个节点就是一个长度为27的指针数组，index0-25代表a-z字符，26为标志域。

![Center][]

上面的存储的数据如下：

\[‘a'\] = V1, \[‘ab’\] = V3, \[‘b’\] = V2, \[‘ba’\] = V4,  \[‘baa’\] = V5, \[‘zaaba\] = V6

从上面可以看出zaaba这个key,没有和任何其他key共享字段，但是却产生了6层，这种无用的深度增加有什么方法减呢？Patricia Tree就可以解决这个问题

### Merkle Patricia Tree对trie的改进 ###

上面tries出现的问题的根本原因是每个前置节点只能表示一个字母，key有多长，树的深度就会多长，不管这个key有没有和其他key共享部分key。因而允许一个节点表示变长的key就可以解决这个深度，具体以官方的下图为例：

![SouthEast 2][]

上图存储的key-value如下：

![20180418161636280][]

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

*  叶子节点（leaf），表示为\[key,value\]的一个键值对。和前面的英文字母key不一样，这里的key都是16编码出来的字符串，每个字符只有0-f 16种，value是RLP编码的数据
 *  扩展节点（extension），也是\[key，value\]的一个键值对，但是这里的value是其他节点的hash值，通过hash链接到其他节点
 *   分支节点（branch），因为MPT树中的key被编码成一种特殊的16进制的表示，再加上最后的value，所以分支节点是一个长度为17的list，前16个元素对应着key中的16个可能的十六进制字符，如果有一个\[key,value\]对在这个分支节点终止，最后一个元素代表一个值，即分支节点既可以搜索路径的终止也可以是路径的中间节点。分支节点的父亲必然是extension node
 *  空节点，代码中用null表示

### 原理解释 ###

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

![Center 1][]

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

![Center 2][]

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

![Center 3][]

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

![Center 4][]

## MPT中的Merkle Tree哪去了 ##

前面为了和官方图一致，将叶子节点和最后的short node合并到一个节点了，事实上源码实现需要再深一层，最后一层的叶子节点只有数据

![Center 5][]

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

![Center 6][]

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

![Center 7][]

原文:https://blog.csdn.net/itleaks/article/details/79992072

[SouthEast]: /images/20220520/fca2415ca90a4bc19616da2019e538bf.png
[SouthEast 1]: /images/20220520/bdb0fd7785da4ab0aad317a45c62162b.png
[Center]: /images/20220520/7604fd903da34b6bab9821761afecfb3.png
[SouthEast 2]: /images/20220520/a80b41c2c09a4cd98ccaad9d458e48aa.png
[20180418161636280]: /images/20220520/ff399761b6a04f23a431aca75ad24937.png
[Center 1]: /images/20220520/cc527dea5074421182b70f75b2743728.png
[Center 2]: /images/20220520/a908a7977b28475d880517b8f276754b.png
[Center 3]: /images/20220520/100f09c24dfe493b95ebcb762c4187b5.png
[Center 4]: /images/20220520/8d906700bc394db89e7d62aaeb516895.png
[Center 5]: /images/20220520/0178312ce61349f68a5c5714b0456be9.png
[Center 6]: /images/20220520/cc7f3cdcddad422990d86ecb6ad9afd7.png
[Center 7]: /images/20220520/c5b31c28cb06432397ab0b97a5250292.png