Qitmeer 的 MeerDAG 是如何实现快速确认的?

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

原文阅读: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] 中的伪代码:

参考文献

[1] Sompolinsky, Y. (2018). PHANTOM , GHOSTDAG : Two Scalable BlockDAG protocols.

[2] Sompolinsky, Yonatan et al. “SPECTRE: A Fast and Scalable Cryptocurrency Protocol.” IACR Cryptol. ePrint Arch. 2016 (2016): 1159.

[3] https://www.daglabs.com/

1赞