内容简介：账户和合约存储数据的方式是影响以太坊的众多问题之一。以太坊协议选用了 Merkle Patricia Tree（MPT，默克尔帕特里夏树）来组织账户及合约数据。尽管这种数据结构在理论上效果很好，但在实际应用中，它带来的问题却比它能够解决的问题多。核心开发者们已经讨论多年，想要把这种数据结构换为二叉树，我将在这篇文章中阐述我对这个问题的看法以及我所提议的处理方法包括一段时间的过渡期，在这段时间内，网络要同时维护两种树结构。这样做的好处是，转换树结构的过程不会影响链的运行，并且可以确保所有的账户都被转换成了二进
账户和合约存储数据的方式是影响以太坊的众多问题之一。以太坊协议选用了 Merkle Patricia Tree（MPT，默克尔帕特里夏树）来组织账户及合约数据。尽管这种数据结构在理论上效果很好，但在实际应用中，它带来的问题却比它能够解决的问题多。核心开发者们已经讨论多年，想要把这种数据结构换为二叉树，我将在这篇文章中阐述我对这个问题的看法以及 如何实现这种转变 。
我所提议的处理方法包括一段时间的过渡期，在这段时间内，网络要同时维护两种树结构。这样做的好处是，转换树结构的过程不会影响链的运行，并且可以确保所有的账户都被转换成了二进制格式。
背景
目前，以太坊的状态树是十六叉制的。十六叉制表示每个节点有 16 个孩子节点。理论上讲，这种方式挺好的，因为孩子节点多意味着只需要更少的 “层” （即树高）便可存储所有数据。
例如，下图是用十六叉树表示的键值对 (170, v) 。十六进制中， 170 记作 0xaa ，因此你只需要两层：第一层记录第一个 a ，第二层记录第二个 a 。
170 在二叉树中被表示为
10101010
。
从图中可见，二叉树要深得多，也窄得多。
以太坊中，每个区块包含一个 stateRoot 字段，这是该块处理完成后表示以太坊全局状态的 MPT 的树根哈希值。总的来说，这个哈希值是对根节点的 16 个孩子节点的哈希值所组成的列表作哈希运算得到的。这些孩子节点的哈希值又是孩子的 16 个孩子节点的哈希值所组成的列表做哈希运算得到的，以此类推。
每次打包交易生成新区块时，矿工都会更新账户树，重新计算根哈希。根哈希存储在新区块的 stateRoot 字段，然后新区块被共识。
） 。虽然后者（矿工从数据库检索兄弟哈希值）花费的时间没有前者（矿工从数据库库得到所有的叶子节点并做哈希）那么多，这个操作还是很耗时。因为每个哈希都必须从数据库中取出。
在十六叉树中，通常每一层你都需要取出 15 个兄弟哈希值。在上面那个我构造的例子（图 1）中，（重计算根哈希）就需要 30 个哈希值。
尽管二叉树层次更深一点，但在每一层只需要一个兄弟哈希值。在上述例子（图 2）中，仅仅需要 8 个哈希值！这就是为什么在实际中二叉树更优。
覆盖层转变方法
不幸的是，转换为二叉树并不简单。需要转换的数据 太多了 ，执行转换花费的时间将多于 15 秒的区块生成时间 。
除此以外，设想你要翻译一本 5000 页的书，作者还在不停地告诉你他们对故事做了些修改，并且这些修改会影响你已经翻译过的页 …… 那这个过程就没完没了。转换状态树的格式也是一样的问题：可能你刚完成某个地址的格式转换，用户就使用了该地址（因此更新了该地址的状态），那你又得从头转换一遍（因为一个地址的状态更新也会影响到整棵状态树）。
解决这个问题的办法是增加一个过渡期，过渡期间，在十六叉树基层上建立一棵 覆盖树（overlay tree） 。这棵覆盖树是二叉树格式的，它的作用是保存状态上发生的所有变化，直到基十六叉树完全转换为二叉树。转换分为 3 步进行。
第 1 步 —— 转换
在这种方法下，区块高度为 H1 时肯定会有 两个 状态根：一个是 “基层” 十六叉树状态根，一个是 “覆盖层” 二叉树状态根。
十六叉树被设置为只读，因此对状态的任何更新都将在覆盖树上进行。
当一笔交易读取或者更新一个账户时，系统首先会搜索覆盖树。如果在覆盖树中找不到账户，接着将会在旧的十六叉树中搜索值。
与此同时，十六叉树在后台进行转换。此时不需要担心值插入的问题，因为所有的改变都会存储在上层的覆盖树中。
第 2 步 —— 基层树切换
当后台转换过程完成，矿工对外宣告，他们已经准备好用转换结果（只读二叉树根）来替换只读的十六进制基层树根。对状态的读写与步骤 1 阶段是一样的。（译者注：此时的只读二叉基层树是根据原本的十六进制状态树得到的）
当足够多的一系列区块对转换所得的二叉基层树根给出了相同的值，意味着大多数矿工都完成了转换，并且认可转换后的树。合并过程则开始。（译者注：此时的合并是针对只读二叉基层树和可读写二叉覆盖树）
第 3 步 —— 合并两棵树
合并过程不断推进：每产生一个新的区块，就从覆盖树上删除 n 个键，把它们重新插入二叉基层树。此过程一直持续，直到所有的键都从覆盖树上移除。到达这步时，区块头就不再保留覆盖状态树的树根。
整个步骤的核心只有一个：如果交易执行时要写的键存在于覆盖树上，这个键就会从覆盖树上删除，写操作直接在二叉基层树上进行。
下一步
为了估计完成转换所需要的时间，我已经做了一个 低转换率的原型系统 。我们确信，整个过程花费的时间不会太离谱，也就是说几天时间就够了。我们会随着算法的改进而公布更多细节。
致谢
此提议得益于 Alexey Akhunov、Vitalik Buterin、Anna George、Sina Mahmoodi、Tomasz Stanczak 以及 Martin H. Swende 的宝贵意见。
（完）
原文链接: https://medium.com/@gballet/ethereum-state-tree-format-change-using-an-overlay-e0862d1bf201
作者:Guillaume Ballet
翻译&校对:裴奇 & 阿剑
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
