摘要：是以太坊存储数据的核心数据结构，它是由和结合的一种树形结构，理解有助于我们更好的理解以太坊的数据存储。所以就有了树压缩前缀树，后面会介绍到，也被称为，中文名称默克尔树，主要用于数据集较大时的文件校验。
MPT(Merkle Patricia Tries)是以太坊存储数据的核心数据结构，它是由Merkle Tree和Patricia Tree结合的一种树形结构，理解MPT有助于我们更好的理解以太坊的数据存储。在了解MPT数据结构之前，我们需要先来看看基本的Tree结构和Merkle Tree、Patricia Tree。
Trie字典树Trie树，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。
上图是一棵Trie树，表示了字符串集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} ，从上图中我们可以看出Trie树的特点：
根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符互不相同。
但是从上面的结构也可以看出一个问题：高度不可控，如下图所示。所以就有了Patricia树（压缩前缀树），后面会介绍到
Merkle Tree，也被称为Hash Tree，中文名称：默克尔树，主要用于数据集较大时的文件校验。其主要特点为：
叶节点存储着数据块的Hash（如：文件块、一段数据集）
非叶子节点（包括中间节点和根节点）存储着对应子节点Hash值串联字符串之后的Hash值。
解释：
1、在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应；
2、往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个”子哈希“。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希再往上推，依然是一样的方式，可以得到数目更少的新一级哈希，
3、最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root。
对于这种数据结构，在实际应用中会有哪些应用场景了，举个例子，我们知道现在从网上下载文件，很多都是P2P下载，文件会切分成很多小的数据块，每个数据块从不同的来源上下载，这些机器可以认为是不稳定或不可信的，文件下载完之后我们需要校验文件的完整性，这时我们总不能把文件再次切分然后分别计算它的Hash和下载前的Hash做对比吧，这时就需要用到Merkle Tree。
在下载前，先从可靠的源获得文件的Merkle Tree树根，下载后，在合并文件之前先对比小文件的Hash是否一样，如果一样就认为是可靠的，如果不一样，就判定文件被损坏，从新的来源重新下载，文件合并之后，计算小数据块的Hash并最终计算根Hash，也成为Merkle Root，然后对比根Hash是否一致。这样就避免了对整个文件进行Hash计算，因为当文件太大时，这种计算是很耗时。
Patricia树，或称Patricia trie，或crit bit tree，压缩前缀树，是一种更节省空间的Trie。对于基数树的每个节点，如果该节点是唯一的儿子的话，就和父节点合并。
上面我们介绍了Merkle Tree和Patricia Tree，而MPT（Merkle Patricia Tree），顾名思义就是这两者的结合。MTP树种的节点包含空节点、叶子节点、扩展节点和分支节点。
Nibble：它是key的基本单元，是一个四元组（四个bit位的组合例如二进制表达的0010就是一个四元组）
空节点**：简单的表示空，在代码中是一个空串。
叶子节点（leaf）：只有两个元素，分别为key和value，表示为[key,value]的一个键值对，其中key是key的一种特殊十六进制编码，value是value的RLP编码。
扩展节点（extension）：也是[key，value]的一个键值对，但是这里的value是其他节点的hash值，这个hash可以被用来查询数据库中的节点。也就是说通过hash链接到其他节点。
分支节点（branch）：分支节点有17个元素，回到Nibble，四元组是key的基本单元，四元组最多有16个值。所以前16个必将落入到在其遍历中的键的十六个可能的半字节值中的每一个。第17个是存储那些在当前结点结束了的节点(例如， 有三个key,分别是 (abc ,abd, ab) 第17个字段储存了ab节点的值)
这里还有一些知识点需要了解的，为了将MPT树存储到数据库中，同时还可以把MPT树从数据库中恢复出来，对于Extension和Leaf的节点类型做了特殊的定义：如果是一个扩展节点，那么前缀为0，这个0加在key前面。如果是一个叶子节点，那么前缀就是1。同时对key的长度就奇偶类型也做了设定，如果是奇数长度则标示1，如果是偶数长度则标示0。
以太坊的每一个区块头，并非只包含一棵MPT树，而是包含了三棵MPT树，分别对应了四种对象：
State Trie 区块头中的状态树
key => sha3(以太坊账户地址address)
value => rlp(账号内容信息account)
Transactions Trie 区块头中的交易树
key => rlp(交易的偏移量 transaction index)
每个块都有各自的交易树，且不可更改
Receipts Trie 区块头中的收据树
key = rlp(交易的偏移量 transaction index)
每个块都有各自的交易树，且不可更改
Storage Trie 存储树
存储只能合约状态
每个账号有自己的Storage Trie
MPT树种还有一个重要的概念：特殊的十六进制前缀(hex-prefix, HP)编码来对key编码，我们先来了解一下编码定义规则：
RAW 原始编码，对输入不做任何变更
HEX 十六进制编码
RAW编码输入的每个字符分解为高4位和低4位。比如key=>"bob",b的ASCII十六进制编码为0x62，o的ASCII十六进制编码为0x6f，分解成高四位和第四位，16表示终结 0x10，最终编码结果为[6 2 6 15 6 2 16]，
如果是叶子节点，则在最后加上Hex值0x10表示结束
如果是分支节点不附加任何Hex值
HEX-Prefix 十六进制前缀编码
输入key结尾为0x10，则去掉这个终止符
key之前补一个四元组这个Byte第0位区分奇偶信息，第1位区分节点类型
如果输入key的长度是偶数，则再添加一个四元组0x0在flag四元组后
将原来的key内容压缩，将分离的两个byte以高四位低四位进行合并
十六进制前缀编码相当于一个逆向的过程，比如输入的是[6 2 6 15 6 2 16]，根据第一个规则去掉终止符16。根据第二个规则key前补一个四元组，从右往左第一位为1表示叶子节点，从右往左第0位如果后面key的长度为偶数设置为0，奇数长度设置为1，那么四元组0010就是2。根据第三个规则，添加一个全0的补在后面，那么就是20.根据第三个规则内容压缩合并，那么结果就是[0x20 0x62 0x6f 0x62]
官方有一个详细的结构的示例：
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/24478.html
摘要：是以太坊中存储区块数据的核心数据结构，它和融合一个树形结构，理解结构对之后学习以太坊区块以及智能合约状态存储结构的模块源码很有帮助。 MPT(Merkle Patricia Tries)是以太坊中存储区块数据的核心数据结构，它Merkle Tree和Patricia Tree融合一个树形结构，理解MPT结构对之后学习以太坊区块header以及智能合约状态存储结构的模块源码很有帮助。 首...
摘要：前言以太坊是一个巨大的状态机，在网络中，每一个全节点都保存着以太坊状态机的全部历史，只要愿意，我们可以查询到任何时刻的状态黄皮书中，而账户状态便是其中的状态，这部分功能由主要由代码中的包提供基本概念账户地址在以太坊中，无论是外部账户还是合约 前言 以太坊是一个巨大的状态机，在网络中，每一个全节点都保存着以太坊状态机的全部历史，只要愿意，我们可以查询到任何时刻的状态(黄皮书中World ...
摘要：加密经济网络中的底层公链是比比特币更像比特币的价值存储平台。这一点将会在经济模型设计中讲到，敬请期待在技术实现上，我们也充分对比了比特币模型和以太坊模型的优劣，从中继承了比特币协议对状态为核心的优秀架构。 Nervos 加密经济网络中的底层公链 CKB 是比比特币更像比特币的价值存储平台。（这一点将会在经济模型设计中讲到，敬请期待～）在技术实现上，我们也充分对比了比特币 UTXO 模型...
摘要：以太坊发布加密货币网络年月初文章在上宣布以太坊首次向比特币社群宣布以太坊。销售所得首先用于偿还日益增加的法律债务，回报开发者们数月以来的努力，以及资助以太坊的持续开发。以太坊安全审查开始于年末，持续到年上半年。 以太坊历史最近历史记录，请查看Taylor Gerring博客发帖。 诞生2013年末Vitalik Buterin第一次描述了以太坊，作为他研究比特币社群的成果，不久后，Vi...
摘要：基于以太坊项目，以太坊团队目前运营了一个公开的区块链平台以太坊网络。主要特点以太坊区块链底层也是一个类似比特币网络的网络平台，智能合约运行在网络中的以太坊虚拟机里。以太坊采用交易作为执行操作的最小单位。 以太坊将比特币针对数字交易的功能进一步进行了拓展，面向更为复杂和灵活的应用场景，支持了智能合约这一重要特性。 以太坊项目简介 以太坊：项目最初的目标是打造以个智能合约的平台，该平台支持...
阅读 3569·2023-04-26 02:24
阅读 847·2023-04-25 14:47
阅读 2348·2021-11-24 11:16
阅读 1682·2021-11-24 09:38
阅读 1491·2021-11-18 10:07
阅读 2037·2021-09-22 15:49
阅读 1501·2019-08-30 15:55
阅读 807·2019-08-26 13:38
