『数据库』以太坊核心开发者：MPT十六叉树将被替换 |国创上头条|

写在前面：想象一下，你正在翻译一本5000页的书籍，作者一直打电话告诉你他对故事做了调整，这会影响到你已经翻译过的页面……而这可能会一直持续下去，这就是以太坊从当前使用的MPT十六叉树转变为二叉树结构中遇到的一个类似困境。对此，以太坊核心开发者Guillaume Ballet提出了一种方案，可以在大约几天的时间内，通过3个步骤完成这一转换手术。

本文插图
(图片来自：tuchong.com)
对于该提案，以太坊联合创始人vitalik评论称：
“来自Ballet的重要研究基础，它会使以太坊无状态变得友好，同时创造了一个机会，以大大简化该协议。期待在未来的几个月中，来自以太坊1.x开发人员更加出色的工作及成果。 ”

本文插图
以下是译文：
影响以太坊的众多问题之一是账户和合约数据的存储方式，以太坊目前选择的结构称为默克尔帕特里夏树(Merkle Patricia Tree ，或简称MPT）。尽管从理论上讲，它是很有意义的，但在实践中，它带来的问题要比其解决的问题要更多。多年来，核心开发人员一直在讨论向二叉树（binary tree）的转换，在本文中，我将阐明我对这一问题的看法，然后给出一个解决它的方法。
提议的过程引入了一个过渡期，在此期间，两种树结构都会存在。这样做的好处是，在转换树结构时，主链可以保持运行，并且还可以确保将所有帐户转换为二叉树格式。
背景目前，以太坊的账户是被存储到一棵十六叉树当中的。所谓十六叉，就表示一个节点有16个子节点，理论上这是很好的，因为这意味着你需要更少的"阶段"来存储你所有的数据。
例如，这就是以十六叉树的形式表示键与值对（170 ， v）的过程。在十六进制中， 170表示为0xaa ，因此你只需要两层：其中之一用于第一个a ，另一层则用于第二个a 。
图1: 这是一棵十六叉trie树示例，显示了值“v”如何存储在键0xaa处。此树只有2字节长的键，并且只沿0xaa键的子树被展开。为了简洁起见，不相关的子树被替换为“…” 。
注意，这棵树很浅，也很宽。然后将其与以下相同键与值对的二叉树表示法进行比较。在二进制中， 170表示为10101010 。

本文插图
图2: 和图1中相同的键值对，以二叉树形式进行存储。为了简洁起见，不相关的子树被表示为“…” 。
你可以看到，这棵树要深得多，也窄得多。
在以太坊中，每个区块都包含一个stateRoot字段，它是MPT根的哈希值。总而言之，这个哈希，是通过对根的16个子项的哈希列表进行哈希运算而获得的。这些子哈希列中的每一个，又依次是其子哈希列表的哈希，依此类推。
每次生成一个新区块时，矿工都会更新帐户树并重新计算其根哈希值。哈希存储在新区块的stateRoot字段中，然后新区块被密封。

本文插图
图3 区块头的state root字段指向十六叉树的根。问题就出现在这里了：通过对所有节点进行哈希运算来重新计算哈希根花费的时间太长，因此，为了计算根节点，矿工将从数据库中检索同级哈希（sibling hash）。尽管从数据库中获取所有子叶并对整棵树进行哈希运算所需的时间不多，但此操作仍然需要大量时间。这是因为必须要从数据库中获取每个哈希。