AI中国网 https://www.cnaiplus.com
改进稀疏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证明验证（二叉树结构）
通过节点批处理实现高效的数据库读取和存储
减少数据存储（子树的叶子节点包含1个密钥）
减少哈希计算（子树的叶子节点包含1个密钥）
使用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级；或换句话说，具有2²⁵个可能密钥，这使其无法表示。
树之所以被称为稀疏树是因为如果树只包含随机密钥（稀疏分布），那么其包含的大多数节点都有基于节点高度决定的默认值。因此，我们可以通过仅存储一次默认节点，然后再存储其余的非默认节点来对树进行模拟。
有关SMT及其Merkle证明的详细概述，请参阅此文章。
稀疏Merkle树的修改
为了减少更新树中密钥所需的哈希运算次数，我们创建了叶子节点。叶子节点存储在仅包含1个非默认密钥的最高子树中。因此，树的哈希从叶子节点的高度开始而不是从高度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()函数会特别注意将叶子节点保持在仅包含1个密钥的最高子树中。否则，如果节点在树中具有不同位置，则即使密钥和值相同，生成的trie根也会不同。
因此，当删除某个密钥时，Update()会检查它的同级是否也是一个叶子节点并将其向上移动，直到最高子树根包含该非默认密钥为止。
图3.修改了其中一个蓝色节点后，树的外观示例
节点批处理
当将每个节点存储为具有2个子节点的根时，存储的节点数量增长非常快。并且，由于多个线程从内存加载节点，因而产生瓶颈。十六进制Merkle树可以解决这个问题。因为每个密钥有16个子节点，高度较低（为64（256/4））。尽管如前所述，我们需要二进制的树。但是，我们可以通过使用节点批处理来实现与十六进制树相同的功能。
我们不是为一个节点存储2个子节点，而是为该节点存储高度为4的子树。高度为4的树在高度0处有16个叶子（如十六进制）。因此，节点的值是包含4位树的所有节点的数组。可以在索引2 * i + 1和2 * i + 2处找到树中索引i处的节点的子节点。
节点编码如下：
{根：[ [标记叶子节点的字节(0/1)], 3–0, 3–1, 2–0, 2–1, 2–2, 2–3, 1–0, 1–1, 1–2, 1–3, 1–4, 1–5, 1–6, 1–7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f ] }
例如，为了获得数组中索引id = 1处的节点3-0的子节点，我们可以在索引（2 * id + 1）=索引3处访问左子节点2-0，并且在索引（2 * 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的任何技术方面进行互动，请联系我们。
AI中国网 https://www.cnaiplus.com
本文网址：
