共识算法的解释:广义的纳库姆托共识幻影

介绍

比特币十多年来一直是安全的，但由于其安全模——“最长的链式法则”——比特币的吞吐率非常低。最长链规则要求所有可靠的节点快速接收新创建的块，以便在下一个块通过所有节点之前无法创建下一个块，并确保创建很少的“孤立块”

从这个角度来看，必须在吞吐量和安全性之间进行权衡，而比特币协议的最长链规则限制了这种权衡。有没有更好的思考方法?

答案是两者都要做。以色列的团队,在2020年“幻影和GHOSTDAG Nakamoto共识的一个可伸缩的概括)(https://eprint.iacr.org/2018/104.pdf),提出了使用有向无环图(DAG,使用一个参数k(后面详细介绍k)的起源来定义网络安全宽容同时,并保证并行块(因为新块,所有DAG叶节点作为父块被引用时,而不是丢弃速度不足以到达主链的网络，然后首先对块进行排序。例如，在下面的图中，B,C,D, E也可以是block, V是一个新的block，它需要引用J,M,L。

视觉上，这是什么意思?

比特币的情况下,网络被定义为D的延迟,所以为了确保没有叉子,然后D不再生成块,这意味着它的每秒钟非常慢,我们可以认为一定小于k块。具体地说，如果网络延迟为1秒，那么最多在1秒内生成1/600个块(在10分钟内生成一个块)。

因此，为了扩展这个概念，DAG图中的一个块需要保证在一个块输出期间生成最多k个块(在本例中，没有明显的来回引用)。

这就是PHANTOM协议的概念出现的地方，它确保最多(k+1)个块出现在同一个块阶段。为了确保这一点，它首先定义了反锥函数:对于一个块B，查找它所属的DAG中没有直接或间接引用(即在DAG中不可访问)的块的数量。例如，在下面的图中，block G在整个DAG中没有访问B, F, I, H, K，所以anticone(B)=B, F, I, H, K. |anticone(B)|被定义为总块数，即5。

图2

然后需要求解**k -簇的DAG图，记为MCSk:

**这是一个简单的问题**:

*输入:DAG
*输出:一个知名的子DAG图S’S‘在SAMPLrsquo的任一块B中的反锥;块的数量不超过k。

以图2中知名的3-cluster为例，由蓝色块组成的DAG图就是最终找到的MCS3很容易验证任何蓝色块是否满足|反锥(B)。3.反锥(E)=(B, C, D, F, G, I)有六个块。可以看出，当k=3时，实际上在每个块区间内最多可以生成3+1个块(因为不同的阶段可以直接通过引用关系来确定)。换句话说，k决定了在每个block interal **内最多可以生成k+1个block。

但事实上,这个问题是np难的,所以作者使用一个简单的构建MCSk贪婪的方法,即首先创建DAG图满足MCSk条件之前,然后找到满足的块MCSk状况,判断是否满足MCSk条件,并将其添加到MCSk。

一旦找到MCSk，就可以确定块的全局顺序。

整个DAG块的顺序确定如下:

1. 确定MCSk，然后将其标记为蓝色，其他块标记为红色
。2. 排序MCSk拓扑(即。，从DAG图中的创建块开始，根据边的关系，将访问后的边放在后面)，从而确定主干;然后对于那些不在主链上的蓝色方块，把它们一个一个加到序列中;**，我将按照拓扑顺序添加红色方块。

作为一个简单的例子，如果k=3，让我们构建如下图所示的全局顺序。

1. 从M开始(因为它包含了过去的块上)，然后选择K(因为F过去的块只有三个)，以选择H, D, genesis，从而构建主链
2。然后迭代构建MCSk
3第一次访问D，创世纪作为过去，所以创建块被添加到蓝色块
4。访问H，然后确定C、D、E |反锥|小于或等于3，发现均满足，故加C、D、E
5。访问K，然后添加M 排序。根据任何拓扑排序算法确定蓝色集合的顺序，如Genesis,D,E,C,I,H,K,M 创世纪，D, E, C, I, H, K, M, B, F, L, J
6。**，根据交易区块内的顺序排序，可以确定交易顺序

如果你感兴趣，正式算法如下:

!(图片)(https://uploader.shimo.im/f/MXx12G3Y9onyo.png !缩略图)

事实上，我们发现，如果k设置为0，那么这就是中本共识**。

可扩展性怎么样?

在这里，我们将协议的可扩展性定义为它可以在不牺牲安全阈值(恶意节点控制的最小算力的比例)的情况下提高块生成的速度。* *

证明了PHANTOM可以保证安全阈值的下限为1/2 AMPL MIDdot;(1)AMPL -;和δ,)而与三角洲;由K控制，K和delta更大;越小。

**增加块生成速度和lambda;**:安全阈值不跟随λ增大，但同时受到节点带宽的限制。例如，如果带宽为1M，一个块大小为1M，那么λ每秒最多一个数据块。

**提高安全性**:为了增加安全阈值，k需要增加，但是确认时间会增加

**生存活动(确认时间)**:随着block继续被取出，block被篡改的风险呈指数级下降。假设网络时延为7秒，可以安全设置k=16，攻击者计算力为αAMPL勒;0.25的概率被篡改ϵ= 0.1%,交易确认时间只有45秒。并确认时间，对网络延时不敏感增加。

结论

PHANTOM概括了DAG数据结构的区块链上的Nakamoto共识。它不需要预先设置诸如块间距之类的限制，因此它面临着Nakamoto共识在“广泛安全性”方面的权衡。贪心算法也易于实现，安全性得到了严格的证明。

但是具体的实验数据还没有得到，还需要进一步的验证……