【科讯】AERGO发布StateTrie：为高性能互操作性而构建的哈希树

改进稀疏的merkle树，以实现更快、更高效的状态认证。 请参加我们的discord。

互操作性是多个区块链初创企业、研究者和开发者正在搜索的主题。 旨在连接孤立的区块链互联网，实现价值和数据的链间传输。 他还认为互操作性是aergo多层体系结构设计的核心。 这个设计结合了公共和私有区块链技术，聚集了领域的精华，使公司能够在不牺牲中心化和数据完整性等重要因素的情况下灵活地设计dapp。

如果我们将来的顾客要跨越区块链传输价值和数据，就必须在这些互联网之间进行安全的通信。 区块链之间通信的过程称为资产桥。 资源桥接必须通过比较高效的机制验证不同的链的状态。 实现此目标的一种方法是通过智能合同验证其他区块链状态的merkle说明(在这种情况下为资产转移请求)。 这些说明的验证必须轻量且高效以达到智能合同的消费效率。

以太网坊使用编辑的merkle patricia树验证状态数据。 但是，以太网的patricia树是十六进制的，每个节点包含16个子节点。 这比二叉树效率低，很难解决。 实现区块链业务所需的速度和性能要求状态认证尽可能高效，促使研究稀疏的merkle树。

我们的设计迭代首先实现了标准稀疏的merkle树。 标准稀疏的merkle树是一个散列树，可以在一定时间内更新。 但是我发现还太晚了，不能为aergo平台提供必要的吞吐量。 标准稀疏merkle树限制速度的主要原因是其值存储在树的0 (高度)中，因此更新密钥需要256次散列运算。

因此，为了提高aergo链的吞吐量，开发者pierre-alain ouvrard相应地改善了稀疏的merkle树，并通过开源方法提高了吞吐量。

aergo statetrie概述

aergo statetrie提供了快速有效的状态验证。 本副本概括介绍了什么是aergo statetrie、它的功能以及如何采用它。

aergo statetrie是一个改进的稀疏merkle树。 值存储在只包含一个密钥的顶层子树中。 由此实现的好处是，平均来说，在包含n个随机密钥的树中，更新树中的密钥只需要log(n )次散列运算。

aergo改进的稀疏merkle树包含以下特征:

高效的merkle说明验证(二叉树结构)

使用节点批处理解决方案读取和保存高效的数据库。

减少数据存储(子树的叶节点包含一个密钥)

减少散列计算(子树的叶节点包含一个密钥)

采用goroutine，更新多个密钥

限制:不包含的merkle说明与标准smt不同。 表示位于不包含叶节点的关键点的路径上，或默认位于高度0处。

稀疏的merkle树

稀疏的merkle树是包含用于加密散列函数的各可输出叶子的树。

图1 .稀疏merkle树的高度示例= 4(4位密钥)。 3位密钥显示为红色和蓝色。 默认节点显示为绿色。 非默认节点显示为紫色。

值(默认键)存储在高度为0的树叶中。 如果默认值为d0，则位于高度1处的每个默认节点的值为d1 =散列( d0，d0 )。 空树根是高4的默认散列。 当密钥插入树中时，叶节点的值从默认值( d0 )更改为指定值，仅重新计算树的编辑部分。

例如，要向包含蓝色密钥的树添加红色值，只需计算h1、h2、h3和根并检索树的新根。 由于此h3没有更改，因此将在树的左侧添加红色值。

对于输出256位的散列函数，该树包括256级。 换句话说，有两个可能的钥匙，无法表达。

之所以把树称为稀疏树，是因为在树中只包含随机密钥(稀疏分布)的情况下，其中包含的很多节点都有基于节点高度的决策默认值。 因此，可以先保存默认节点一次，然后再保存其他非默认节点，以模拟树。

有关smt及其merkle帮助的详细信息，请参阅此副本。

创建稀疏的merkle树

为了减少更新树密钥所需的散列运算次数，制作了叶节点。 叶节点存储在只有一个非默认密钥的顶层子树中。 因此，树的哈希从叶节点的高度开始，不是从高度0开始。 如果树包含n个随机关键点，平均会在高度= log(n )周围创建一些叶节点。

图2. h3是只包含一个密钥的顶层子树:红色子树。 因此，在写入后稀疏的merkle树中占有一个位置。

蓝色的钥匙并不稀少。 因为只在最后一位发散，所以在树下的位置不会改变。 这表明在稀疏的merkle树中采用随机密钥的重要性。

merkle帮助

采用二叉树为我们提供了非常简单易用的merkle说明。 与patricia树不同，merkle说明由一个关键路径中的所有节点组成。 因为patricia树中的每个节点都有16个子节点，所以此数据量很大，不能像二进制数据那样直接验证。

在上面的示例中，红色键的merkle说明由红色节点组成: [h3]。 请注意，此说明远远短于上一个示例( [d0，d1，d2，h3] )。 这是因为值没有存储在高度0处。 说明的验证者计算散列(叶节点，h3 )，检查根是否符合预期。

压缩的merkle说明:与标准稀疏的merkle树一样，也可以压缩merkle的说明。 由于merkle说明的大部分节点是默认节点，因此可以使用位图为说明的每个非默认索引设置一个。 树中包含蓝色叶节点的证据是【叶节点2、d1、d2、叶节点】。 这个说明可以缩小到1001【叶节点2，叶节点】。 压缩的merkle描述的验证者应该知道使用d1计算h2，因为位图的第二个索引是0，d2用于计算第三个元素。

不包含的说明:编辑的稀疏merkle树的限制是不包含的说明不确定。 说明键不在树中的证据是，不包含叶节点的键的路径上或值默认处于高度0。 例如，树中不包含密钥= 0000的证据是叶节点位于密钥路径上，也是树中的证据。 密钥= 1111是树中不包含的证据，也是值默认处于高度0 (与标准稀疏的merkle树相同)的证据。

从树中删除

从树上删除叶子时，update ( )函数特别观察到叶子节点保持在只包含一个密钥的顶层子树中。 否则，如果节点位于树中的不同位置，则生成的trie根将不同，即使键和值相同。

因此，删除密钥时，update ( )会检查其兄弟是否也是叶节点，并向上移动，直到顶层子代的根包含默认以外的密钥。

图3 .修改其中一个蓝色节点时树的外观示例

节点批处理解决

如果将每个节点保存为具有两个子节点的根，则保存的节点数将非常快地增加。 此外，由于多个线程从内存加载节点，因此会出现瓶颈。 十六进制merkle树可以处理这个问题。 因为每个密钥有16个子节点，高度很低( 64(256/4 ) )。 如上所述，需要二进制树。 但是，通过使用节点批处理解决，可以实现与十六进制树相同的功能。

我们不是为一个节点存储两个子节点，而是为该节点存储高度为4的子树。 高4的树高0有16个叶子(十六进制数等)。 因此，节点的值是包含4位树的所有节点的数组.树中索引为I的节点的子节点位于索引为2 * i + 1和2 * i + 2的位置。

节点代码如下。

{根: [叶节点的字节(0/1) ]，30，31，20，21，22，3，1，1，2，3，13，14，15，16，1，7，0，1

例如，为了得到数组内索引id = 1的节点3-0的子节点，访问索引(2 * id + 1) =索引3的左边的子节点2-0，访问索引( *id+2) =索引4的右边的子节点2-1

对各节点附加用于识别叶节点的字节标签。 由于无法预先知道根的性质，因此此字节标签存储在节点数组的第一个索引中。

图4 .节点批处理解决的可视化表现:第一批是蓝色的，一批所有16片叶子是其他批(绿色)的根。 批处理包括30个节点。

节点批处理解决有两个好处。

减少数据库的读取次数。

无需锁定即可更新高度4子树。

使用goroutines同步更新多个密钥

您可以使用更新调用功能更新任意数量的密钥，而不是一次更新一个密钥，从而更新树的不同部分。 键必须按数组排序。 对应的值必须在另一个数组中的同一索引中(请参见用法)。

要从树中删除密钥，只需将其值设置为高度0(d0 )的默认值。

用法

如果要创建空树，请将根设置为零。 零根表示等于高度的默认值。 如果要发送多个节点，请使用自定义散列函数或在实用程序中使用散列计算机指定数据库。

返回指定高度的默认节点

39433550800

“键[ ] [ ]字节”是规则的键数组，“值[ ] [ ]字节”包含每个键的匹配值。

00

“键[ ] [ ]字节”是规则的键数组，“值[ ] [ ]字节”包含每个键的匹配值。

更新递归地沿着树下行，根据私钥所属的树的一侧分割密钥和值:可以更新树的多个部分。

如果在提交前多次调用更新，则仅提交最后的状态。

atomicupdate与update一样，用排序的键和值更新树。 但是，与update不同，如果在提交前多次调用atomicupdate，则会记录atomicupdate调用的所有中间状态。 这在验证各个块的状态时很有用，但不能立即提交到数据库。

获取树中存储的密钥值。 如果密钥是缺省值，即没有存储键值，则返回零。

将更新的节点提交到数据库。 调用更新时，新节点存储在smt.db.updatednodes中。 然后使用commit保存到磁盘。

可以使用stash函数恢复更新，而无需提交，例如块验证无效时

调用恢复时，要回滚的树(当前树和tooldroot之间)将从数据库中删除。

merkleproof创建了merkle包含/不包含密钥的证据。 merkle说明是散列数组。

如果不包含密钥，merkleproof将返回错误和密钥路径的说明叶。

merkleproofcompressed可以创建与merkleproof相同的merkle说明，但使用位图进行压缩

确保键值对包含在当前根树中。

验证中不包括的说明。 确保叶( proofkey，proofvalue )位于不包含关键帧的路径上，或者路径ap支持高度为0的默认值。

确保键值对包含在当前根树中。 长度是要验证的叶键值的高度。

验证不包含的压缩说明。 检查叶( proofkey，proofvalue )是否位于不包含关键帧的路径上，或路径ap是否支持高度为0的默认值以外的值。

结论

不同区块链系统之间的通信是分布式互联网和企业区块链未来需要的功能。 为了促进公司将链或数据链从链转移到链，需要比较有效的状态验证手段。 标准稀疏的merkle树完全不符合我们心中想的性能标准。 因为我们编辑了它，用开源实现了。 aergo statetrie用于aergo平台，是根据资产桥的过程和钱包和轻客户端等安全状态进行验证的其他应用程序，用于迅速有效地验证状态。

如果您知道其他感兴趣的实施，或者想与我们交流aergo的技术方面，请与我们联系。