DAG共识之PHANTOM协议

PHANTOM协议主要分为两个内容：

1. 通过投票判定诚实区块和恶意区块

2. 对区块做线性排序

下面将逐一对这两点进行说明。这里重申一下账本共识有效的大前提：网络中大多数节点都是诚实的。我们不考虑集中超过51%算力的这种恶意攻击，因为无论用什么账本共识这样的攻击都会奏效。

1 PHANTOM的投票原则

从《从区块链到DAG（三）--DAG共识之SPECTRE协议》里的描述可以看出：“双花”攻击时，攻击区块在发布以前几乎不会与诚实节点产生的区块相关联，因为在这个阶段诚实区块不知道这些攻击区块的存在，所以自然不会引用它们。在censorship攻击中，攻击节点产生的区块也有类似的倾向：不与诚实节点所产生的包含“冲突交易”的区块相关联。综和来看这些恶意攻击都有一个显著特点：恶意节点产生的区块与诚实节点产生的区块之间的连通度比较低，反之诚实节点产生的区块之间的连通度会比较高。

PHANTOM的投票原则正是基于这个原理，通过判断不同区块间的连通度进行投票。为了描述清楚这个投票过程，我们先介绍几个有关的概念，见图片1。

图片1 一个典型的DAG图例

来源：Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar，PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus

以区块H作为例：

past(H)={Genesis, C, D, E}--在H创建之前直接或间接指向H的过去区块。

future(H)={J,K,M}--在H创建之后直接或间接指向H的未来区块。

anticone(H)={B, F, I, L}--除开past(H)，future(H)之外的区块，这些区块与H并没有直接或间接的指向关系。如何对这些区块的排序是DAG共识的主要难点。

tips(G)={J, L, M}--树叶区块，或者末端区块；这些区块会成为新区块的块头引用。

接下来再引入一个在《从区块链到DAG（二）--DAG的基本结构》里提到过的概念：分叉系数k，直观上看这是一个描述网络允许分叉的个数。严格来说k被定义为传播系数（propagation parameter)，用来描述网络延迟（propagation delay）这个现象。在《从区块链到DAG（一）--区块链的账本结构和共识机制》中我们讲到过，在实际过程中网络延迟的现象无法避免，二这种延迟会导致分叉。如果要避免分叉，就要保证在网络延迟的时间段Δt内不产生新的区块，即k=0。k值的定义非常重要，如果k值太大会使分叉过多，降低网络的安全性；如果太小又会限制网络性能，使TPS较低，比如区块链就是一种k=0的网络。在DAG中，为了平衡性能和安全一般把k定为3。

连通度的高低是通过k值来判定的，区块的连通度要满足最大k-cluster的子集要求，如图片2。

图片2 k-cluster子集要满足的条件

来源：Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar，PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus

如何判断一个区块是诚实节点产生的呢？先找到这个区块的anticone的集合，这个集合和DAG的k-cluster的子集S的交集数目如果小于等于k，则这个区块是诚实节点产生的，会被加入到子集S，反之则是攻击节点产生的区块不会加入集合。当迭代整个过程把全部区块滤过一遍以后，所有被判断为诚实的区块都会加入这个子集S，这时候的S被称为最大的k-cluster子集，写做MSCk，集合里的所有区块会被计入账本。

图片3 一个最大子集为3-cluster的DAG图例，k=3

来源：Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar，PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus

如图3所示，诚实节点产生的区块标记为蓝色，攻击节点产生的区块标记为红色。所有满足图片2要求的集合都属于3-cluster的最大子集，也就是所有的蓝色区块都属于MSC3。我们来验证一下是否这样的区块划分能符合上述要求。

蓝色区块以G为例：

anticone(G)={B, F, I, E, H, K};

anticone(G)与蓝色区块的交集是B, F, I一共3个，满足小于等于k值的要求（该DAG的k值为3），故G是诚实节点产生的区块，可以被计入账本。所有的蓝色区块都满足这一要求。

红色区块以E为例:

anticone(E)={B, C, D, F, G, I};

anticone(E)与蓝色区块的交集是B, C, D, F, G, I一共有6个，大于这里的k值3，所以E被认为是攻击节点产生的区块，不会被计入账本。所有的红色区块也都符合这一原则。

依照这个规律依次滤过所有区块就可以判断和排除攻击区块。这背后的原理很简单：区块X的anticone(X)是指与X无关的区块的集合，若anticone(X)与诚实节点产生的区块交集越多则代表X与诚实区块的连通度越低，这里通过给连通度加上一个极限值k作为判断标准。若anticone(X)与诚实区块交集数高于k值，代表X区块与诚实区块的连通度低，X会被判断为攻击区块；反之则代表X与诚实区块的连通度高，X被认为是诚实区块。

2 线性排序

在找到MSCk子集以后，下一步就是对集合里的进行线性排序，排序的原则和拓扑排序一样，如图片4。

图片4 拓扑排序

来源：拓扑排序--百度百科,

https://baike.baidu.com/item/%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F/5223807

拓扑排序是指把DAG上的顶点排列成一个线性序列，由集合上的一个偏序得到该集合的一个全序的过程。排序的原则：优先选取没有箭头输入的顶点为起点，每排完一个序列就把这个顶点从图中移除，再从移除后的图中选取没有输入的顶点作为下一个序列，如此循坏直到最后一个顶点被输出。需要注意，拓扑排序的顺序并不是唯一的，可能存在多种选择方案，比如图片4也可以在(c)步骤选择输出f, 最终顺序为acfbde。根据这个原则，图片3中的DAG最终的输出结果之一是：A->D->C->G->B->F->I->E->J->H->K。这个结果可以是任意的拓扑排序，但是蓝色区块会优先排列，红色区块由于连通度低会自然的排在蓝色区块后面。

3 PHANTOM协议的应用举例

从上文可知，PHANTOM协议的第一步判断诚实区块是最关键最复杂的一步。怎么高效的确定MSCk将直接影响全网的性能，这里引入贪心算法GHOSTDAG来解决这个问题。先根据每个区块的连通度（区块past()集合里的元素个数）来打分，选出总分最大的区块组成主链，这些区块会组成最初的子集S，剩下的区块将依照主链的顺序依次投票选出。原理是入选主链区块都有着较高的连通度，可以优先加入S集合。这样整个网络会按照连通度从高到低的趋势去投票，用最快的方式找到最大的k-cluster子集MSCk。下面我们通过一个例子来完成复盘一下PHANTOM协议的运作过程：

图片5 PHANTOM协议在一个k=3的DAG图中的应用示例（第一步）

来源：Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar，PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus

图中蓝色小圆圈中的数字代表每个区块X的连通度打分，分数和每个区块past(X)里的区块数目相等。根据贪心算法的规则，我需要选出一条总分最高的路径，先选出分值最高的区块M, 然后依次向前滤过M的所有过去区块past(M)，如果遇到两个区块分值相等则随机选择一条路径，最后选出的主链路径如图片5中蓝色区块所示：Gensis->D->H>K->M，最初的S={Genesis, D, H, K, M}。接下来验证：D区块past(D)只有创世区块，anticone(Genesis)是个空集，与S的交集个数为0≤3，所以创世区块满足3-cluster的子集要求，用蓝色边框标注。

图片6 PHANTOM协议在一个k=3的DAG图中的应用示例（第二步）

来源：Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar，PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus

第二步来到区块H，past(H)除了创世区块以外还有C, D, E, 分别找到这三个区块的anticone集合并判断它们与S之间的交集个数是否小于等于k值，这里k值为3。

anticone(C)={B, D, E, I, L}; 与S的交集是{D}，交集个数为1≤3。

anticone(D)={B, C, F, E, I, L}; 与S的交集个数为0≤3。

anticone(E)={B, C, D, F}; 与S的交集交集是{D}，交集个数为1≤3。

因此这三个区块都加入到3-cluster的子集中，这一步结束时子集更新为S={Genesis, D, H, K, M, C, E}，在图片6中用蓝色边框标注。

图片7 PHANTOM协议在一个k=3的DAG图中的应用示例（第三步）

来源：Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar，PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus

第三步访问区块K，past(K)中需要判断H, I, B是否要加入子集S。

anticone(H)={B, F, I, L}; 与S的交集个数为0≤3。

anticone(I)={B, C, D, H, F, J};与S的交集为{C, D, H}，交集个数为3≤3。

所以在这一步结束时H和I也要加入S，在图片7中用蓝色边框标注。

anticone(B)={C, D, E, H, I, L}；与S的交集为{C, D, E, H}，交集个数为4>3。所以B不满足3-cluster的子集条件，不会被加入到子集中，B被判定为恶意节点产生的区块。第三步结束时，子集更新为S={Genesis, D, H, K, M, C, E, I}。

图片8 PHANTOM协议在一个k=3的DAG图中的应用示例（第四步）

来源：Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar，PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus

第四步访问区块M，past(M)中需要判断F, K是否要加入子集S。

anticone(K)={F, J, L}; 与S的交集个数为0≤3。

anticone(F)={D, H, K, E, I, L}；与S的交集为{D, H, K, E, I}，交集个数为5>3。

所以区块K被加入到子集，而F不被加入。这里更新子集S={Genesis, D, H, K, M, C, E, I}。

图片9 PHANTOM协议在一个k=3的DAG图中的应用示例（第五步）

来源：Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar，PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus

最后一步，访问到一个还没正式产生的虚拟区块V，V引用的区块是tips(G)，这意味着past(V)是整个现有所有区块，在图片9中用虚线表示。继续判断J, M, L是否加入子集。

anticone(M)={J, L}; 与S的交集个数为0≤3。

anticone(L)={B, C, F, J, M, H, K}；与S的交集为{C, M, H, K}，交集个数为4>3, L不属于3-cluster的子集。

anticone(J)={M, K, I, L}; 与S的交集为{M, K, I}，交集个数为3≤3；按理说J应该加入子集，但是这会导致anticone(I)最终与最大子集MSC3的交集变为{C, D, H, J}，交集个数4>3，I不能被加入到子集集合中。这会得到一个与前面步骤相矛盾的结果，所以这里不能把J加入子集。最终这个DAG图的最大3-cluster的子集MSC3={Genesis, D, H, K, M, C, E, I}。（注意：图片9中的L不属于MSC3所以不应该被标注为蓝色边框，这里为图示错误）

接下来我们开始排序：

先对MSC3中的蓝色区块做拓扑排序 Genesis->D->E->C->I->H->K->M。

再对不在MSC3中的黑色边框区块排序然后添加到蓝色区块的排列之后，最终排序为 Genesis->D->E->C->I->H->K->M->B->F->L->J。

交易在每个区块内部会自动按照它们的出现顺序排序，至此整个网络的线性排序就完成了。

4 总结

当k=0时，PHANTOM的规则就表现为比特币的最长链共识，和SPECTRE协议一样，PHANTOM协议是最长链共识的拓展。与SPECTRE的不同之处在于PHANTOM这种可以严格排序的账本共识也适用于有智能合约要求的网络。目前还没有哪个DAG项目采用这两种协议中的任意一种，也许是在代码层面的实现还有一些难度，但是这两个协议的安全性已经在数学理论上得到了验证，我们期待未来会有更进一步的发展。下一篇我们简单介绍一些已经落地的DAG项目。

参考资料：

[1] GHOST, DAG, SPECTRE, PHANTOM和CONFLUX技术原理，https://www.jianshu.com/p/8734e06d558f

[2] Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar，PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus

[3] 共识算法解读:泛化的中本聪共识PHANTOM

，https://www.tuoluocaijing.cn/article/detail-10009964.html

[4] DAG的妙用（三）——比特币协议的扩展,

https://mp.weixin.qq.com/s/KeQDVQMJLQlyXQcywfE8sQ

[4] 拓扑排序--百度百科,

https://baike.baidu.com/item/%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F/5223807