以色列研究团队提出新共识算法 PHANTOM，借助于有向无环图 DAG 实现并行的同时保障安全性。

原文标题：《共识算法解读 : 泛化的中本聪共识 PHANTOM》
撰文：Johnathan

比特币运行了十几年都非常的安全，但是饱守诟病的问题就是它的吞吐量太低了，这也是由它的安全模型即最长链规则决定的。最长链规则要求所有的诚实节点能迅速接收到新创建的区块，因此，必须要等到一个区块完全传递到所有节点才能创建下一个块，并且保证了创建的「孤块」(orphan blocks) 非常的少。

那么从这个角度上来讲，就是吞吐量和安全之间必须进行权衡，而比特币协议的最长链规则限制了这个权衡规则，有没有更好的思路呢？

答案就是，在并行的同时保障安全。以色列的研究团队，在 2020 年的《PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus[1]》一文中，提出了在借助于有向无环图 DAG，使用一个参数 k(后面具体介绍 k 的来历）来限定网络的安全容忍度的同时，且保障了并行出块（因为新区块，会引用所有 DAG 的叶子节点作为父块，而不是直接丢弃网络中没有到主链上的快，然后先出块再排序）。比如下图，B,C,D,E 可以并且出块，且 V 是新出的块，它需要引用 J,M,L。

直观上来看，具体的思路是怎样的呢？

类比比特币，定义网络的延迟是 D，那么为了保证没有分叉，那么 D 这个时间段内就不能再产生块了，也就是每秒出块速度得很慢，我们可以认为是肯定小于 k 个块。具体而言就是网络时延 1 秒的话，1 秒内最多产生 1/600 个块（10 分钟出一个块）。

那么把这个概念拓展一下就是，在 DAG 图中的块，需要保证在一个出块的周期内（此处指的是没有明显的前后引用关系），最多出 k 个块。

PHANTOM 协议的思路也就由此而来，它需要保证在同一个出块阶段内，最多出（k+1）个块。为了保证这点，它先定义了 anticone 函数：对于一个块 B，查找它所在的 DAG 图中与他没有直接或间接引用关系（也就是在 DAG 图中不能访问到的）的块的数目。比如说下图中区块 G，在整个 DAG 图中它不能访问到 B，F，I，H，K 所以 anticone(B)=B，F，I，H，K。并定义 |anticone(B)| 为总共块的数目，也即 5.

图 2

然后就需要求解一个最大 k-cluster 子 DAG 图的问题，记为 MCSk：

简单来说就是这样一个问题：

• 输入：DAG
• 输出：一个最大子 DAG 图 S’，S‘中任一区块 B 的 anticone 在 S’的块的数目不超过 k。

举图 2 中最大 3-cluster 的例子，蓝色的块构成的 DAG 图就是最终找到的 MCS3。很容易验证任何一个蓝色的块都满足 |anticone(B)|≤3, 比如 anticone(G)=B，I，F。而 anticone(E)=(B, C, D, F, G, I)，有 6 个块，不满足。并且可以看出 k=3 时，实际上保证了每一个出块间隔内最多产生 3+1 个块（因为不同阶段的明显可以通过引用关系直接确定），也就是说 k 决定了每个出块间隔最多出 k+1 个块。

但是实际上，这个问题是个 NP-hard 问题，所以作者采用简单的贪心法来构建 MCSk，也就是先把之前满足 MCSk 条件的 DAG 图创建好，然后新创建的区块再去找到满足它的条件的块，判断是否满足 MCSk 条件，并加入到 MCSk 中。

找到 MCSk 之后，就可以进行确定区块的全局序了。

整个 DAG 区块的序按照如下方式确定

1. 确定好 MCSk，然后把它标记为蓝色的，其他的块标记为红色的
2. 对 MCSk 按照拓扑排序（也就是 DAG 图中从创世区块开始，根据边的关系，后面被访问到的就排后面），这样就确定了一个主链；然后再对蓝色块中，没有在主链上的逐个加入到序列中；最后把红色的区块，按照拓扑排序加入进来。

听起来是不是头晕了，还是举个简单的例子吧，假设 k=3，我们来按照下图构建全局的序 (V 为虚拟区块便于理解）：

从 M 开始（因为它包含的过去的区块最多），再选 K （因为 F 的过去的区块只有 3 个），依次选取 H,D,genesis，从而构建出主链，然后再迭代地构建 MCSk。

1. 首先访问 D，过去的只有 Genesis，所以添加创世区块到蓝色块中
2. 访问 H，然后判断 C,D,E 的 |anticone| 是否小于等于
3. 发现都满足，所以添加 C,D,E3. 访问 K，同理添加 H，I
4. 访问 M，添加 K，因为 |anticone(F)|=4，所以不能添加 F
5. 然后添加 M

排序

1. 根据任意的拓扑排序算法确定蓝色集合的序，比如 Genesis,D,E,C,I,H,K,M
2. 将红色区块进行拓扑排序并加在后面，逐个加上 B,F,L,J

因此总体的序为：Genesis,D,E,C,I,H,K,M,B,F,L,J5. 最后按照交易在区块内部的出现的顺序进行排序，就可以确定交易的序了

感兴趣的可以看下，形式化的算法如下：

实际上，我们发现如果把 k 设为 0，那么这就是中本聪共识。

拓展性又如何呢？

在此，我们定义协议的拓展性指的是，在不牺牲安全门限（恶意节点控制的最小算力比例) 的同时，还能提高区块的生成速度。

作者证明了 PHANTOM 可以保证安全门限的下限是 1 /2 · (1 ? δ), 而δ由 k 来控制，k 越大δ越小。

增加区块产生速度λ：安全门限不会随着λ增大而增大，但是同时受到节点带宽的限制，比如带宽 1M 的话，一个区块大小是 1M，那么λ最多可以提升到每秒出一个块。

提升安全性：提升安全门限，需要提升 k，但是会增大确认时间

存活性 (确认时间): 区块被篡改的风险，随着不断出块，指数级下降。假设网络延迟 7 秒，可以安全地设置 k=16，在攻击者算力为α ≤ 0.25，被篡改的概率为? = 0.1% 时，交易确认时间仅为 45 秒。并且确认时间，对网络延迟增大不敏感。

总结

PHANTOM 在 DAG 数据结构的区块链上，将中本聪共识进行了泛化，它不需要事先设定出块间隔等限制，因此也接触了中本聪共识对拓展性-安全性的权衡。采用贪心算法，也便于实现，并且安全性也被严格证明了。

但是具体的实验数据，目前还是没有，需要进一步的验证 ...