IOTA开发明星Hans Moog:一种新的“共识”:多界Tangle[第二部分]

在本系列博文的第一部分中,我描述了这种新方法背后的基本思想和概念,但是所有的描述都很哲学化,而且描述相当模糊。现在我想使用额外的部分来讨论实际的算法和机制,它们是这种方法生效的必要条件。

PS:我决定把剩下的内容也分成几个部分,否则就太长了。

基于“平行世界”的账本状态

第一个大的构件是一种不同的账本状态的记录形式,它试图通过承认“Tangle中隐藏的Tangle”原则来建立账本状态的模型,而不是试图使账本状态直接表示Tangle状态。

1. UTXO方案的采用

我们没有使用基于帐户余额的账本方案,它只记录地址和它们的余额,而选择了记录了与负责创建这些余额的交易散列相关的地址的“子余额”的账本方案,即UTXO方案。

在这种UTXO方案中,移动资金的每一笔交易都会产生一个输出,然后可以将其作为下一笔交易的输入加以引用。输出包含余额,并由地址和交易散列的组合标识。因此,交易自动引用负责创建移动资金的交易。

这些额外的引用(在分支和主干旁边)可以用来验证资金的来源,而不必遍历整个Tangle,也不用对过去的交易进行昂贵的“二分查找”。

2. 作为过去椎体的一部分的附加引用

这些附加的输入引用(在分支和主干旁边)将被认为是交易的过去锥的一部分,并且交易是固化的 ,如果它满足:

  • 所有引用的输入都是固化的。
  • 分支和主干也是固化的。

通过这种方式,一笔固化的交易就包含了它想要花费在过去椎体的资金,而不管交易所涉及的资金是如何附加在Tangle当中的。因此,这些附加的引用让我们可以在并行的子Tangle中“相邻地”进行资金和支出交易,这将使选择小费变得更加容易(见图):​

支出不用通过主干和分支去引用收入。

因为交易直接引用他们想要花费的资金,所以不可能有试图无中生有地花费资金的交易(因为它们永远不会被固化)。

3. 汇总的账本状态(用于非冲突交易)

因为大多数交易的“健康的”Tangle并不互相冲突(或者只是数据交易),他们最终会收敛到一个全局共享的状态,节点将达成一致,我们甚至不需要考虑维护“单独”的账本状态或者被告知这些诚实的交易的存在。

因此,所有可靠的交易最初都将“入账”到一个汇总的账本状态,这将只是一个交易输出列表—“主世界”。(Hans 使用的是master reality,笔者觉得把它翻译成(世)界可能更贴切一些。因为在后面你会看到节点会在不同的世界做选择。)

4. 双花检测

每当一个交易消耗一个输出时,我们都会得到一个交易散列,它通过将输出与数据库中的输出一起存储在消费者列表中来消耗输出(我们将其标记为spent)。当一个交易消耗一个已经被另一个交易消耗的输出时,双花就出现了,这时候就需要针对性的去处理它。

5. 使用平行“世界”(多版本的账本状态)处理冲突

每一笔双花都会对账本产生一个独特的感知,这种印记不会像之前讨论的诚实交易那样自动趋同二消失。所有直接或间接参与到双花的资金的交易都有带有这种独特的感知。

为了能够正确地反映这一点,我们为每笔双花创建一份账本状态的副本。然后,我们浏览了双花的消费者,并将所有与这种观点相同的余额变化“登记”到这个新版本的账本中。如果余额变化之前已经在另一个“世界”(即主世界,而交易没有冲突)中被记录,那么我们将已记录的余额移到我们刚刚创建的相应的“世界”中。

注意:我们不是创建一个账本状态的“实际”副本,而是以一种分层的方式组织这些"世界",每个"世界"都有一个父"世界",递归地从父"世界"继承所有的余额。这是一个优化,允许我们创建"世界",而不必复制所有现有的传输输出。"世界"变得非常轻量级,它只是一个标识符,用于逻辑上“分组”交易输出。由于交易输出只被存储一次,然后只被“预订”到这个逻辑上的群组,所以"世界"的“成本”几乎为零。

让我们从一开始就看看这个例子,看看冲突的交易是如何“创造”新的"世界"的:

各个世界"”独立地追踪账本状态的不同“版本”

6. 冲突集

如果交易使用相同的输入,那么它们相应的“世界”将形成一个冲突集(由使用的输入标识)。如果一个交易花费多个输入,那么它的“世界”可能同时是多个冲突集的一部分。

注意:节点只能"喜欢"(认可)冲突集中的一个“世界”。

7. 子世界的递归

如果一个"世界"包含额外的双花,那么它将递归地形成次"世界",就像从主"世界"形成"子世界"一样,通过创建一个新的"世界",让他的父"世界"指向包含在第二个花费到达之前的资金的"世界"。

8. 世界的聚合

通过使用来自这些“世界”的输出,交易也可以组合多个“世界”(如果它们不是同一冲突集的一部分)。这将创建一个具有多个父“世界”(即合并的“世界”)的“聚合世界”。这允许我们将每个交易与一个世界关联起来。

无论何时接收到新交易,我们都将交易关联到的“世界”存储在交易元数据中。新附加的交易可以简单地通过以下方式“继承”父交易的"世界":

我们迭代被引用的"世界",并删除所有被其他世界“降权”的"世界",只保留“最深的”"世界"(拥有通往主要"世界"的最长路径)。

  • 如果只剩下一个"世界",那么我们将这个"世界"与新的交易关联起来。
  • 如果还剩下一个以上的"世界",那么我们将它们组合成一个聚合的"世界",并将聚合的"世界"分配给新的交易。

聚合"世界"的标识符是通过散列它“包含”的"世界"id的排序列表来计算的。

9. 冲突的解决和清理

一旦一个冲突被裁定了(即通过虚拟投票过程最终确定一个决定),我们就可以删除冲突集及其所有相关的"世界"(从账本状态中删除交易——它们将被简单地丢弃)。获胜的"世界"得到了“提升”,这意味着我们将把它的所有内容复制到它的父"世界"中,并将它的子"世界"重新连接到现在指向底层的父"世界"。

关于未被裁定的子"世界"的附加决策将以同样的方式得到解决,方法是在做出裁定时将它们与它们的父"世界"合并回去。

让我们再来看看之前的例子,假设投票结果是REALITY2被接受:

获胜的"世界"得到提升并成为主"世界"的一部分。

注意:我们只在账本状态中丢弃被拒绝的"世界"。那些负责创造这些"世界"的交易以及所有与之相关的事物依然还在Tangle里面,并不受这个决策过程的影响。

结论

这种跟踪账本的方法允许我们立即决定一个交易是否有效,而不必在Tangle中摸索。我们只需要检索引用的交易输出并检查它们是否已经有了使用者。

更复杂的冲突处理在必要的时候才会引入,而不是反复在Tangle中搜寻来确定余额,但我们创建“世界”是,只需要简单的查询一下消费者(这是所有交易的一个很小的子集)。

与此同时,我们不再需要确保我们正确地参考了过去在一个花费锥中的资金交易,这将使tip的选择也独立于Tangle的行走。

这整个机制的工作原理有点像“git”,您可以为Tangle的冲突部分创建分支,一旦做出了决定,这些冲突部分就会与主分支合并。

任何对账本状态代码感兴趣的人都可以在这里查看:

https://github.com/iotaledger/goshimmer/tree/ledger_state/packages/ledgerstate

注意:整个账本状态完全独立于“Tangle的结构”,只依赖于Tangle中的隐藏的DAG结构。最坏的情况(每个tip都与其他tip相冲突)本质上“退化”为我们今天计算账本状态的方式(每个交易都有其自身的"世界",然后只能通过“遍历”该交易的父"世界"来解决)

原文来源

https://medium.com/@hans_94488/a-new-consensus-the-tangle-multiverse-part-2-b4c971235c59​​​​

大熊

专栏作者:大熊

个人简介:我共发表了 43 篇文章,总计被阅读了15,438 次,共获得了 489 个赞。

作者邮箱 作者主页 Ta的文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注