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