Polkadot系列（二）——混合共识详解

本文作者

夏立伟，陶勇星 

来自趣链科技数据网格实验室BitXHub团队，主要负责区块链账本互操作技术相关研究工作。

导读：此文是Polkadot系列文章第2篇，Polkadot的混合共识详解。当说到Polkadot的共识时，很多人的第一反应是Polkadot有很多的共识算法，有很多新鲜的名词，由于Polkadot共识算法的数量较多、功能各异，很多人对Polkadot采用的共识算法有很多疑问，其中最容易混淆的是多种不同的共识算法之间如何协作的问题，本文接下来拟针对Polkadot的共识进行深度剖析。

Polkadot共识主要有三种

NPOS, BABE, GRANDPA

接下来我们对这三种共识进行逐一的解释

NPOS

什么是NPOS共识

在Polkadot 中，中继链上的验证者需要分配到各个平行链，为它们提供区块链验证能力，是 Polkadot 共享安全性的一部分，因此中继链的验证者对于整个Polkadot多链系统的安全性至关重要。

如何公平安全地选举出中继链上的验证者也就成了保障整个系统共享安全性的第一步，是不可或缺的一步。

NPOS( Nominated Proof of Stake)共识算法就是用来选举出能让系统更安全，更高效的验证者集合的。和传统意义上的POS共识相比，NPOS算法结合了Polkadot链自身架构的一些特点，进行相应的优化。

下面看看NPOS是如何进行工作的。

在说明NPOS之前，我们需要先回顾一下Polkadot中重要的两种角色。

▲ 验证人

中继链的全节点，中继链会在验证人池中通过随机分组把验证人指定给不同的平行链。验证人会接受来自收集人打包的区块并进行有效性验证，然后结合共识算法对收集人提交的区块进行确认。

▲ 提名人

Polkadot中数字货币DOT的持有人，它会选择自己所信任的验证人进行DOT质押，然后分享验证人的收益。

Polkadot的选举模型是建立在这两种角色基础上的。要成为验证人，必须先成为验证人候选人参加选举的过程，而这个选举过程中的“选民”就是提名人。

在Polkadot的设计中，提名人数量在理论是可以不设置上限的，如果能够让更多的提名者参与到投票阶段，那么参与到选举的资金量也就越大，整个系统就更加的安全；而对于验证者来说，为了区块链的性能，不能太多（所有节点都能作为验证者的话，那就是比特币采用的模式了），验证者的数量由系统确定的固定值，这一点来说和POS共识是一致的。

选举模型

为了明确选举问题，Polkadot中将选举验证者集合的问题抽象为一个数学的选举问题：

▲ 问题：m 个选民对 n 个候选者的情况下，选出最终的 t 为当选者

（注：提名人可以有任意个，验证者是有限个）

问题的描述很简单，但是如何做到让系统更安全，会有不同的策略。Polkadot的设计哲学中，认为选举策略需要满足下面的“三大原则”：

Balance: 验证者在出块时候的比重相同，因此该策略在Stake分配需要尽量平均，保证网络的安全；

Support: 该策略需要让尽可能多的 Stake 资金参与进来。因为提名者只负责选投哪些候选者，但是对于的 Stake具体分配给多少到哪个验证者是没有决定权的，这部分是NPOS算法通过计算来决定的。这也是NPOS和普通的POS共识中很大的不同之处；

Fair representation: Stake 多的提名者选投的验证人更可能出现在验证者集合中。

• 输入：给定，其中是Nominator集合，是Validator候选者集合，是边的集合，表示提名者投了候选者一票。同时给定向量 ,表示各个提名者各自的Stake数量，是选出的最终验证者集合的大小。
•  输出：给定解，其中是最终选定的Validator，大小为， 是提名者分配多少 Stake 到最终的Validator。
• 限制条件：
• Balance: 给定，能够给出一个 ，使得最小
• Support: 给定，能够给出一个 ，使得最大

Fair representation: proportional justified representation(PJR)规则

•  任意一个 ,都不会存在一个提名者的子集，导致出现下面的情况：

用较为通俗的话来说就是不允许出现：存在某些中的提名者的stake 超过了总的staking的的比重，并且他们支持的人选有交集的超过个，但是他们支持的Validator的数量入选却没有超过个。

上述的问题在数学上就是一个最优化问题，很可惜这个选举在数学上已经被证明是 NP完全问题，并不能在多项式时间内给出最优解。

所以Polkadot给出了自己的一套解决方案，来绕过这个难解问题。

NPOS流程

上述推导的数学模型中，由于是NP完全问题，也就是说给出最优解的计算时间复杂度是无法确定在多项式时间内的。

Polkadot给出了一个相对来说可行的方案。

不追求最优解，达到相对最优即可NP完全问题中给出可行解是很困难的，但是验证已有解是简单的，能在多项式时间内完全。所以验证可行解的部分放在链上进行。

▲ 完整的流程如下：

在提名者给出自己的投票之后，每一个候选者都可以给出自己对于上述选举问题的一个可行解。

在上述这些可行解的集合中，利用链上的方案比较方案，按照之前的“三大原则”来比较这些方案，选取其中最优的方案最为最后验证人选举结果，这样就完成了一轮选举。

BABE

BABE的全称是Blind Assignment for Blockchain Extension，BABE是一个用来出块的引擎，类似于Ourobros Praos，一种PoS的协议。BABE算法是基于slots的。

在Polkadot中每一个slot差不多6秒长的时间。

每个slot时间段中BABE会选出一个leader来出块。

BABE中leader的选举是通过一个随机函数（VRF）来实现的，在每个slot阶段，每一个节点会通过运算VRF函数来获得一个数值，如果这个数值小于网络中预先规定好的阈值，那么节点就会认为自己就是这个时间段的leader，于是节点就开始出块了。

值得注意的是在上述的过程中，由于VRF函数是随机生成数字的，所以可能造成在某一slot中没有leader或者有多个节点算出自己的VRF值小于阈值进而产生多个leader的情况。我们依次分析两种情况：

当没有leader产生时，Polkadot就规定按照顺序来决定谁是leader，这个顺序是预先确定好的。

当出现多个leader的时候，Polkadot允许多个节点都提交区块，而最终区块的确认则由GRANDPA来决定。

GRANDPA

GRANDPA则是用来做区块确认的，在文章的第二部分我们有提到BABE将会对Polkadot的交易进行出块，那么这些出块最终就是由GRANDPA来确定的。

像其他PBFT的衍生算法一样，GRANDPA的时间复杂度也是O(n²)。但是Polkadot之所以采用GRANDPA是因为GRANDPA并不是每次只确认一个区块，它每一次都会确定好几个区块来做确认

Idle(24peers),best:#664257(0x706c…76b7),finalized#664253

(0xe4ab…4d2a)

Imported#664258(0xee71…6321)

Idle(24peers),best:#664258(0xee71…6321),finalized#664256

(0x809a…a5d8)

上面是Polkadot测试网络的一段日志，可以看到一次确认区块高度从664253到了664256，所以GRANDPA一次性确认了三个区块。这样的话跟一次性只确认一个相比，GRANDPA的效率要比其他PBFT的衍生算法要高出很多。

▲ 下面介绍一下GRANDPA的具体流程：

1. 一个主节点广播之前一轮确认后的区块高度；

2. 等待网络延迟以后，每个节点都广播他们认为的可以被确认的最高的区块（pre-vote）；

3. 每个节点对步骤2接受到的区块集进行计算，算出他们认为的能够被确认的最高区块，并且将结果广播出去(pre-commit)；

4. 当节点接收到足够的pre-commit的消息能够确认区块后就会形成commit的消息，一般认为大于2/3就可以被确认了。

上述就是GRANDPA确认区块的主要流程。

我们需要担心的是在步骤2的pre-vote过程中可能会有作恶的节点投票了两个区块并且广播出去，这样的话就有可能产生链的分叉行为。

Polkadot为了防止这种情况的发生使用了一个叫做Account Safety的方式。

如果当网络中出现了要分叉的commit信息时，Polkadot的节点会马上采取Account Safety的机制。每个节点都会询问其他节点他们所看到的pre-vote的情况，节点都会回复他们收到的信息，这样就很容易检查到有哪些恶意节点投了两个区块。最后这些被抓到的作恶节点将会被踢出共识网络，永远不能进入。

让我们回到BABE，通过结合BABE和GRANDPA我们可以看到在出块的时候Polkadot采用BABE出块，此时节点之间只要发送一次块信息即可，这样的话时间复杂度仅仅是O(n)，在出块之后节点之间再采用GRANDPA进行块确认，此时由于确认阶段节点之间要通过二次确认来保证确认块结果的一致性，时间复杂度是O(n²)，不过由于是多个块一次性进行确认，所以两者结合的混合共识是非常高效的，比普通的PBFT共识要高效很多。

结语

上面三种就是我们向大家介绍的Polkadot的共识算法，可以看到NPOS主要是为了选取Polkadot的共识节点，BABE和GRANDPA通过混合来高效的进行区块链的出块和确认。

这样的混合共识比传统的PBFT共识速度更快，并且在速度更快的基础上并没有丢失掉安全性。将出块和确认区块两个阶段分开并且使用不同的算法是在区块链共识中值得学习的地方。

通过这三种算法，Polkadot可以说在一定程度上高效的实现了Polkadot上区块链的共识算法。

参考文献：

[1] Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain Bernardo David , Peter Gaˇzi , Aggelos Kiayias November 14, 2017