波尔卡多“三个共识”的详细阐释

波卡共识有三种：非营利组织、宝贝和爷爷

接下来，我们将逐一解释这三种共识

非营利组织

非营利组织的共识是什么

在Polkadot中，中继链上的验证器需要被分配到每个并行链上，以提供块链验证能力，这是Polkadot共享安全的一部分。因此，中继链的验证器对整个Polkadot多链系统的安全性至关重要。

如何公平、安全地选择中继链上的验证器，成为保证整个系统共享安全的第一步，是必不可少的一步。

采用NPOs一致性算法来选择一组验证器，使系统更加安全高效。与传统的POS一致性算法相比，NPOs算法结合了Polkadot链的一些特点，对其进行了相应的优化。

让我们来看看非营利组织是如何运作的。

在描述非营利组织之前，我们需要回顾一下Polkadot中的两个重要角色。

验证者

在中继链的整个节点中，通过随机分组的方式将验证器分配到不同的并行链上。验证器将接受收集器打包的块并验证其有效性，然后根据一致性算法对收集器提交的块进行确认。

提名人

在Polkadot中，数字货币dot的持有者将选择其信任的验证器对dot进行质押，然后分享验证器的收益。

波卡的选举模式就是基于这两个角色。要成为一名核查员，你必须首先成为一名核查员候选人才能参与选举过程，而选举过程中的“选民”就是提名者。

在波卡的设计中，理论上对提名人数没有上限。如果更多的被提名者能够参与投票阶段，那么选举涉及的资金量就越大，整个系统也将更加安全。对于验证器，对于区块链的性能来说，不能太多（如果所有节点都可以充当验证器，即比特币），验证器的数量是系统确定的一个固定值，这与POS共识一致。

选举模式

为了阐明选举问题，波卡将选举验证器集问题抽象为一个数学选举问题

问题：在M个选民对n个候选人的情况下，最后一个t被选为赢家

（注：提名者可以有任意数量，验证者数量有限）

这个问题的描述非常简单，但是对于如何使系统更安全有不同的策略。在波卡的设计理念中，选举策略需要满足以下“三个原则”：

平衡：块输出时校验器的比例相同。因此，在堆栈分配时策略应尽可能平均，以保证网络安全；

支持：这项策略需要尽可能多地动用资金。因为提名者只负责选择要投票给哪些候选人，但是它没有决定分配给堆栈的验证器数量。该部分由NPOs算法通过计算确定。这也是非营利组织与普通POS共识的一大区别；

公平表示：由拥有更多堆栈的被提名者铸造的验证器更有可能出现在验证器中心化。

基于上述的问题和要求，可以将该问题转化为下面的数学模：输入：给定，其中是Nominator集合，是Validator候选者集合，是边的集合，表示提名者投了候选者一票。同时给定向量 ,表示各个提名者各自的Stake数量，是选出的最终验证者集合的大小。输出：给定解，其中是最终选定的Validator，大小为，是提名者分配多少 Stake 到最终的Validator。限制条件：

平衡：给定，可以给出一个最小值

支持：给予，可以给予最大限度的支持

Fair representation: proportional justified representation(PJR)规则任意一个 ,都不会存在一个提名者的子集，导致出现下面的情况：

但他们支持的人数并不比被提名者多，而且支持的人也不多。上述问题是数学中的一个最优化问题。不幸的是，这种选择在数学上被证明是一个NP完全问题，不能在多项式时间内给出最优解。因此，波卡想出了一个自己的解决方案来规避这个棘手的问题。在上述NPOs过程的数学模中，由于它是一个NP完全问题，即最优解的计算时间复杂度不能在多项式时间内确定。波卡给出了一个相对可行的方案。在NP完全问题中，不寻求最优解很难得到可行解，但证明了现有的解是简单的，可以在多项式时间内完成。因此，验证可行解的部分被放在链上。整个过程如下：

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

在上述可行解集合中，利用链上的方案比较方案，按照前面的“三原则”对这些方案进行比较，选出最佳方案作为最终的验证者选举结果，从而完成一轮选举。

宝贝

babe的全称是区块链扩展的盲分配。Babe是一个用于生成块的引擎，类似于POS协议ourobos praos。Babe算法是基于时隙的。

在波卡语中，每个时隙大约6秒长。

在每一个空档期，宝贝都会选择一个头球来阻挡。

babe中领导者的选择是通过一个随机函数（VRF）来实现的。在每个时隙级，每个节点将通过计算VRF函数来获得一个值。如果该值小于网络中预定的阈值，则该节点将认为它是该时间段的前导，并且该节点将开始阻塞。

值得注意的是，在上述过程中，由于VRF函数随机生成数字，因此可能在一个时隙中没有引线，或者多个节点计算其VRF值小于阈值，然后生成多个引线。我们依次分析了两个案例

当没有生成leader时，Polkadot规定按照预先确定的顺序来确定leader。

当有多个前导时，Polkadot允许多个节点提交块，最后的块确认由grando决定。

爷爷

爷爷被用来确认区块。在本文的第二部分，我们提到babe将阻止Polkadot的事务。然后这些街区最终由爷爷决定。

与其他基于pbft的算法一样，grandian的时间复杂度是O（n？）。然而，波卡收养了爷爷，因为爷爷不仅一次确认一个区块，而且每次都会确定几个区块进行确认。

空闲（24个对等端），最佳：#664257（0x706c…76b7），已定案#664253（0xe4ab…4d2a）导入的#664258（0xee71…6321）空闲（24个对等），最佳：#664258（0xee71…6321），已定案#664256（0x809a…a5d8）

以上是Polkadot测试网络的日志。可以看出，一个确认块的高度是从664253到664256，所以爷爷一次确认三块。这样，grandian算法的效率远高于其他pbft求导算法，而一次只能进行一次确认。

下面介绍爷爷的具体过程：

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

2等待网络延迟后，每个节点广播他们认为可以确认的最高预投票；

3每个节点计算步骤2中接收到的块集，计算他们认为可以确认的最高块，并广播结果（预提交）；

4当节点接收到足够的预提交消息来确认块时，它将形成一个提交消息，一般认为该消息大于2/3。

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

我们需要担心的是，在步骤2的预投票过程中，一些恶意节点可能会投票两个块并广播它们。这样，可能会发生链分岔行为。Polkadot使用一种叫做账户安全的方法来防止这种情况。

如果要分叉的提交信息出现在网络中，Polkadot节点将立即采用帐户安全机制。每个节点都会询问其他节点他们看到的预投票情况，这些节点会回复他们收到的信息，这样就很容易检测到哪些恶意节点投了两个块。最后，这些被抓住的邪恶节点将被踢出共识网络，永远无法进入。

让我们回到宝贝身边。通过组合babe和grando，我们可以看到，当block用完时，polkado使用babe发送块。在这种情况下，时间复杂度仅为O（n），然后在块被释放后，使用grandog来确认节点之间的块。此时，由于节点间的二次确认处于确认阶段，需要确认块的一致性时间复杂度为O（n？2） 一。然而，由于一次确认了多个块，因此二者的混合一致性非常有效，比普通的pbft一致性效率高很多。

后记

以上三个是我们介绍给您的Polkadot一致性算法。可见，非营利组织主要是选择波卡的共识节点。Babe和grandover混合起来有效地阻止和确认区块链。

这种混合共识比传统的pbft共识更快，并且不会因为更快的速度而失去安全性。在区块链共识中，将分块和分块确认两个阶段分开，使用不同的算法，值得学习。

通过这三种算法，Polkadot可以在一定程度上有效地实现区块链的一致性算法。

参考文献：

[1] Ouroboros Praos：自适应安全、半同步股权证明区块链Bernardo David，Peter Gaˇzi，Aggelos Kiayias 2017年11月14日