Polkadot系列|混合共识详解

2020-09-04 09:02 栏目:经验之谈 来源:网络整理 查看()

引言:本文是波尔卡多系列的第二篇文章,详细解释了波尔卡多的混合共识。当谈到波尔卡多的共识时,许多人的第一反应是波尔卡多有许多共识算法和许多新术语。由于波尔卡多的一致性算法数量众多,功能各异,很多人对波尔卡多采用的一致性算法有很多疑问,其中最令人困惑的是不同一致性算法之间如何协作。接下来,本文拟对波尔卡多的共识进行深入分析。

波尔卡多共识有三种主要类型:NPOS、贝比、爷爷

接下来,我们将逐一解释这三个共识

NPOS

什么是NPOS共识

在波尔卡多中,中继链中的验证器需要被分配给每个并行链,以向它们提供区块链验证能力,这是波尔卡多共享安全性的一部分。因此,中继链中的验证器对整个波尔卡多链系统的安全性至关重要。

如何公平、安全地选择中继链中的验证者,成为保证整个系统共享安全不可或缺的第一步。

使用NPOS(指定的利害关系证明)一致性算法来选择验证者集合,可以使系统更加安全和高效。与传统意义上的位置一致性相比,NPOS算法结合了波尔卡多链自身结构的一些特点,并进行相应的优化。

让我们来看看NPOS是如何工作的。

在解释NPOS之前,我们需要回顾一下波尔卡多的两个重要角色。

*验证人

对于中继链的所有节点,中继链将通过验证器池中的随机分组将验证器分配给不同的并行链。验证者将接受来自收集器的打包块并验证它们的有效性,然后通过结合一致算法来确认收集器提交的块。

*提名者

波尔卡多数字现金点的持有者将选择他信任的验证者来保证点,然后分享验证者的利润。

波尔卡多的选举模式就是基于这两个角色。要成为一个验证者,你必须首先成为一个验证者。候选人参与选举过程,这个选举过程中的“投票人”就是被提名人。

在波尔卡多的设计中,理论上提名人数没有上限。如果有更多的被提名者可以参与投票阶段,参与选举的资金数额将会更大,整个系统将会更安全;为了区块链性能,验证器不应该太多(如果所有节点都可以用作验证器,这是比特币采用的模式),验证器的数量是由系统确定的固定值,这与POS共识一致。

选举模式

为了阐明选举问题,波尔卡多将选举验证集问题抽象为一个数学选举问题:

问题:当M名选民反对N名候选人时,最后的T名被选为获胜者

(注意:可以有任意数量的被提名者和有限数量的验证者)

问题的描述很简单,但是有不同的策略来使系统更安全。在波尔卡多的设计哲学中,选举策略需要满足以下“三个原则”:

Balance:验证器在阻塞时具有相同的比例,因此该策略需要在Stake中均匀分布,以确保网络的安全性;

支持:这个策略需要尽可能多的股份基金参与。因为被提名人只负责投票给哪些候选人,但没有决定分配多少和哪些验证者的股份,这是由NPOS算法通过计算确定的。这也是NPOS与普通POS共识的一大区别;

公平代表:由更多被提名者选择的股份验证者更有可能出现在验证者集中。

基于上述问题和要求,问题可以转化为以下数学模型:

输入:给定,其中是提名者集、验证者候选集和边集,表示被提名者投票给候选人。同时,给出一个方向量,指示每个被提名者的堆叠数量,这是所选择的最终验证者集合的大小。

输出:给定的解决方案,最终选择的验证器在哪里,大小是多少,这是被提名者分配给最终验证器的赌注。

*限制:

平衡:给定,可以给一个,使最小

给定支持:可以给一个最大化

公平代表制:比例合理代表制规则

任何一个,都不会有被提名者的子集,导致以下情况:

Polkadot系列|混合共识详解

在一种更流行的语言中,它是不允许出现的:有些被提名者的股份超过了总股份的比例,他们支持的候选人有不止交集,但他们支持的验证者的数量不超过。

上述问题是数学中的一个优化问题。不幸的是,这种选择已经被证明是数学上的NP完全问题,并且最优解不能在多项式时间内给出。

因此,波尔卡多给出了自己的解决方案来绕过这个难题。

NPOS进程

在上面导出的数学模型中,因为它是一个NP完全问题,也就是说,给出最优解的计算时间复杂度不能在多项式时间内确定。

波尔卡多给出了一个相对可行的方案。

在不寻求最优解的情况下,给出NP完全问题的可行解是非常困难的,但是证明了现有的解在多项式时间内是简单和完全的。因此,验证可行解的部分被放在链上。

整个过程如下:

Polkadot系列|混合共识详解

被提名人投票后,每个候选人都可以对上述选举问题给出一个可行的解决方案。

在上述一套可行方案中,根据前面的“三个原则”,利用链中的方案比较方案对这些方案进行比较,选出最佳方案,最终验证选举结果,从而完成一轮选举。

婴儿

贝比的全名是区块链分机的盲分配。BABE是一个用于阻塞的引擎,类似于Ourobros Praos,一个PoS协议。BABE算法基于插槽。

在波尔卡多,每个时隙几乎有6秒长。

BABE将选择一个领导者在每一个投币口打出一个方块。

巴布的领袖选举是通过随机函数实现的(VRF)。在每个时隙阶段,每个节点将通过操作VRF函数获得一个数值。如果这个数值小于网络中预先指定的阈值,节点将认为它是这个时间段中的领导者,因此节点将开始阻塞。

值得注意的是,在上述过程中,由于VRF函数随机生成数字,在某个时隙中可能没有前导,或者多个节点计算出它们的VRF值小于阈值,导致多个前导。我们依次分析两种情况:

当没有领导者时,波尔卡多根据预先确定的顺序来决定谁是领导者。

当有多个领导者时,波尔卡多允许多个节点提交块,最后的块确认由爷爷决定。

爷爷

爷爷用于块确认。在文章的第二部分,我们提到BABE将阻止波尔卡多的事务,所以这些块最终由爷爷决定。

像其他PBFT衍生算法一样,爷爷的时间复杂度是0(n)。然而,波尔卡多采用了爷爷,因为爷爷不仅一次确认一个块,而且每次都确定几个块进行确认。

空闲(24个对等机),最佳: #664257 (0x706c…76b7),最终完成#664253 (0xe4ab…4d2a)

进口#664258 (0xee71…6321)

空闲(24个对等机),最佳: #664258 (0xee71…6321),最终#664256 (0x809a…a5d8)

以上是波尔卡多测试网络的日志,可以看出,一次确认的区块高度为664253-664256,所以爷爷一次确认了三个区块。在这种情况下,与一次只确认一个相比,爷爷算法比其他PBFT导数算法更有效。

下面描述了爷爷的具体过程:

1.主节点在前一轮确认之后广播块高度;

2.在等待网络延迟之后,每个节点广播最高的预投票);他们认为可以被证实;

3.每个节点计算在步骤2中接收的块集,计算它们认为可以确认的最高块,并广播结果(预提交);

4.当一个节点收到足够多的预提交消息来确认一个块时,就会形成一个提交消息,一般认为如果大于2/3就可以确认。

以上是爷爷确认块的主要流程。

我们需要担心的是,在步骤2的预投票过程中,一些邪恶的节点可能会投票支持两个块并广播它们,这可能会导致链分叉。

波尔卡多使用了一种叫做帐户安全的方法来防止这种情况的发生。

如果要分叉的提交消息出现在网络中,波尔卡多的节点将立即采用帐户安全机制。每个节点会询问其他节点他们看到的预投票信息,节点会回复他们收到的信息,因此很容易检查哪些恶意节点投票支持两个块。最后,这些被抓住的邪恶节点将被踢出共识网络,永远不会进入。

让我们回到BABE。通过结合BABE和爷爷,我们可以看到波尔卡多使用BABE来屏蔽。此时,它只需要在节点之间发送一次块信息。在这种情况下,时间复杂度仅为0(n)。封锁之后,爷爷被用于节点之间的封锁确认。此时,由于节点之间的第二次确认,块确认结果的一致性得到保证。时间复杂度为0(n),但是因为在0(n)时间确认多个块,所以将两者结合的混合共识非常有效,并且比普通PBFT共识更有效。

结论

以上三个算法是我们向您介绍的波尔卡多的一致算法。我们可以看到,NPOS主要是选择波尔卡多的共识节点,而贝比和爷爷可以通过混合有效地屏蔽和确认区块链。

这种混合共识比传统的PBFT共识更快,并且安全性不会在更快的速度的基础上丧失。在区块链共识中,将阻塞和确认阻塞这两个阶段分开并使用不同的算法是值得学习的。

通过这三种算法,波尔卡多可以说在一定程度上有效地实现了区块链在波尔卡多上的一致性算法。

参考文献:

[1]大毒蛇:一种自适应安全的半同步股份证明区块链贝尔纳多戴维,彼得加齐,阿杰洛斯基亚伊阿斯2017年11月14日

微信二维码
售前客服二维码

文章均源于网络收集编辑侵删

提示:币友交流QQ/WX群请联系客服加入!

郑重申明:资讯文章为网络收集整理,官方公告以外的资讯内容与本站无关!
虚拟币开发,虚拟币交易平台开发,山寨币交易平台开发 Keywords: 虚拟币开发 虚拟币交易平台开发 山寨币交易平台开发