Qitmeer课堂：MeerDAG是如何实现快速确认的？

原创

1315 天前

1741

我们知道，Qitmeer 的 MeerDAG 协议是一个结合了 GhostDAG 和 Spectre 协议的 BlockDAG 协议，即解决了 Spectre 协议无法支持交易线性排序的问题，同时也具备了实现基于状态的智能合约的能力，拥有着快速确认交易的能力。为了理解 MeerDAG 的快速确认交易的能力，我们分享一篇由资深 DAG 研究员 Tony Outlier 发表的文章《 Fast Confirmation of GhostDAG with SPECTRE》

以下为原文译文：

来自DAGlabs [3] 的GhostDAG [1] 协议是对SPECTRE [2] 协议的升级，解决了SPECTRE 无法线性排序的问题，这是链上智能合约的基础。这样升级的代价是，GhostDAG的确认时间会比SPECTER的确认时间更长。GhostDAG一直在探索如何既保持GhostDAG交易的线性排序能力，同时还具有SPECTER的快速确认能力。GhostDAG [1]的最新论文提供了参考实现，我们可以一起来了解一下。

GhostDAG 的确认速度之所以比SPECTRE 慢，是因为其不得不预估最大网络延迟，也就是区块传遍整个网络需要的最长时间。显而易见，为了保证绝大多数节点能在该延迟内传遍整个网络，该延迟时间需要尽可能地大。而确认时间的计算是以延迟时间为基础的，所以会造成确认时间也相应增加。而SPECTRE的确认速度只依赖于节点自身的传播延迟，可以尽可能地逼近确认速度的极限值。

根据BlockDAG框架的定义，对于任何块B，整个分类帐G都由过去集，未来集和反锥（anticone）集组成。过去集和未来集形成一个锥体集，代表具有确定顺序的区块B集。只有反锥集中的顺序是待定的，由于SPECTRE的排序方法≺G 可以确定任意两个区块之间的关系，所以其中必然存在先于B的部分以及后于B的部分，其中我们比较关注先于B的部分的个数，因为这个数字可以指导我们要追赶的数量，我们定义为差距（gap）。

如果它是一个诚实的区块，差距（gap）应该相对较小。具体来说，它小于GhostDAG的k值，k值也就是当一个节点在一个区块中生成时，整个网络生成的区块数。我们可以把它理解为并发的程度。

上图反映了过去集和未来集对区块 b的投票；反锥集是除了过去集和未来集之外的区块；差距（gap）是在反锥体集中 SPECTRE 排序在b之前的区块。

为了量化这一差距（gap），GhostDAG提出了一个抽出指数（Pumping index）；直观上可以理解为延长区块B，就像从B区块抽出来一样，直到B区块延长到B的顺序先于反锥体（Anticone）中所有其他区块。这里补充下，为什么延长B会提高B的顺序，是因为延长的部分都是属于B的将来集且只属于B的将来集。有一点需要提及的是，根据 SPECTRE 的规则，某区块将来集会投票给该区块，而因为延长的部分只属于该区块的将来集，所以该部分的票数不会影响到其他区块的顺序，因此可以作为量化差距（gap）标准。

上图为抽出指数示意图

形式上说，假设在区块b之后拉长了j个区块，则 b₁为b的唯一子区块，而原来b的子节点则全部连接到bⱼ，将改造后的账本定义为<b, G, j>，我们定义抽出指数如下：

该定义源自GhostDAG

现在我们可以基于抽出指数得出蓝色集合。关于 SPECTRE 有一个 Condorcet 悖论，即会发生a≺ b，b≺ c，c≺ a的情况，然而，由于 SPECTRE 只影响蓝色集的生成，即使这个悖论发生，在SPECTRE 中存在a≺ b，b≺ c，c≺ a的情况，GhostDAG也能得到蓝色集中交易的线性顺排序，在蓝色集中仍然可以唯一确定 a, b, c之间的顺序。此外，由于蓝色集的生成完全是 SPECTRE 生成，而 SPECTRE的计算不需要考虑网络最大延迟，所以确认速度会很快。

附上 GhostDAG[1] 中的伪代码：