以太坊的状态树 Merkle Patricia Tree

Merkle Patricia 树 Merkle 树

Merkle Tree，俗称哈希树，顾名思义，是一种存储哈希值的树。 Merkle 树的叶子是数据块（例如，文件或文件集合）的哈希值。 非叶节点是其相应子节点的串联字符串的散列。 Merkle Tree的主要作用就是当我得到Top Hash的时候，这个hash值代表了整棵树的信息汇总。 当树中的任何数据发生变化时，Top Hash 的值都会发生变化。 Top Hash 的值将存储在区块链的区块头中，区块头必须通过工作量证明。 也就是说以太坊状态树，只要拿到区块头，就可以验证区块信息。

Merkle 树的特点

MT是一种树，大部分是二叉树或多叉树，不管是多少叉树，都具备树结构的所有特征；

Merkle Tree的叶子节点的值是数据集的单位数据或单位数据HASH。

一个非叶子节点的值是根据它下面所有叶子节点的值，根据Hash算法计算出来的。

特里树

Trie以太坊状态树，常被称为前缀树、字典树，也是一种key-value存储结构。 比如下面的词需要整理成trie数据结构，gennral,genesis,god,go,good。

[外链图片传输失败，源站可能有防盗链机制，建议保存图片直接上传(img-wFH2pnoU-1643700433444)("trie01.drawio.png")]

Trie树的特点可以概括为：

trie的每个节点的分支数取决于key中元素的取值范围

trie的查找效率取决于key的长度

trie 不会有哈希冲突

输入不变，最终的trie树是唯一的

更新操作是本地的

帕特里夏尝试

Patricia Tries 是一种路径压缩特里树。 直观上，树的高度明显变小了，访问内存的次数减少了，效率提高了。 以太坊中账户地址的分布非常稀疏。

[外链图片传输失败，源站可能有防盗链机制，建议保存图片直接上传(img-8t2iujMs-1643700433445)("PatriciaTries.drawio.png")]

以太坊的 MPT

[外链图片传输失败，源站可能有防盗链机制，建议保存图片直接上传(img-QxxPxO5m-1643700433445)("worldstatetrie.png")]

课程视频笔记 以太坊状态数据结构推测

以太坊是一个基于账户的账本，需要完成账户地址到账户状态的映射，address=>state。 address是一个160bits的地址，state包括balance, nonce, code等。首先想到的是用哈希表。

哈希表

第一个想到的是使用哈希表。 更新、插入和查询都在这个哈希表中。 一个地址键对应一个状态值。 每个全节点在本地维护一个哈希表，在打包交易时构建默克尔树，并将根哈希放在区块头中。

如果需要提供默克尔证明，如何提供？ 发起交易时如何查询账户余额是否正确？ 一种方法是使用这个哈希表构建一个merkle树，将根哈希存储在区块头中，并发布。 只要根哈希是正确的，数据就不会被篡改。 这有什么问题？ 当一个新的区块发布时，当有新的交易时，哈希表的内容在执行后必然会发生变化，需要重新构建一个从账户地址到账户状态的merkle树。 但是，以太坊账户数量级巨大，再建一棵merkle树的成本太高。 除了证明账户的余额，merkle proof还有一个很重要的作用，就是保持所有节点之间状态的一致性。

那么我们考虑第二种方法，不用哈希表，直接构建merkle树

默克尔树

直接建一个merkle树，把所有的账户都放在merkle树里面，需要修改的时候直接使用merkle树。 只需要修改一小部分账户信息，只需要修改一小部分merkle树。 这种结构的问题是默克尔树没有提供快速高效的查找和更新方式。 另外一个问题是，这个默克尔树需要排序吗？ 如果不排序，这些账户组成的merkle树的叶子节点就是账户信息，不指定叶子节点在merkle树中出现的顺序。 每个全节点构建的默克尔树不唯一，计算出的根哈希也不唯一，无法达成共识。 所以每隔 10 秒左右，发布一个新块将构建一个不同的 merkle 树。 但是大部分账户的状态是不变的，而且账户的数量级非常大，所以每次出块都去建立一个新的merkle树是不现实的。

那么，排序后的默克尔树能行吗？

排序默克尔树

如果有一个新帐户怎么办？ 账户地址是随机的，很可能在merkle树中间插入了一个叶子节点，后面的树需要重构merkle树。 回到上面的同一个问题。 将帐户插入已排序的 merkle 树的成本太高。