作者：资讯 / 来源：PlatON

PlatON 的 Giskard 共识协议由概率性权益证明 PPoS( PlatON proof of stake ) 和 Giskard 拜占庭容错协议-Giskard BFT( Giskard Byzantine Fault Tolerance ) 组成。PPoS 使用质押、委托、随机选取的形式选出参与共识的验证节点，Giskard BFT 使用类 BFT 算法实现区块的生产和验证。

本文我们将简单介绍 PPoS 共识和 BFT 理论，并分析 PBFT 算法特性及 PBFT 存在的问题，其后重点分析 Giskard BFT 借鉴 PBFT、Tendermint、Hotstuff 等共识协议的演进之路。

区块链技术本质脱离不开传统分布式系统。分布式一致性算法是传统分布式系统的一大难题，经过长期的研究和应用，诞生了如 paxos、raft、zab 等成熟安全的算法。

相比于传统的分布式系统，公共区块链中没有中心化的假设，任何节点都可以加入并自由访问所有的数据，因此公链中不可避免会存在恶意节点。所以，区块链系统中的共识机制不仅需要支持 CFT( Crash fault tolerance ) 还需要支持 BFT(Byzantine Fault Tolerance) 。BFT 是一个已经被研究得比较透彻的理论，PBFT 是其中最为著名的实现算法，目前广泛应用于各大区块链系统中。

PlatON 的 Giskard 共识协议由概率性权益证明 PPoS(PlatON proof of stake) 和 Giskard 拜占庭容错协议-Giskard BFT(Giskard Byzantine Fault Tolerance) 组成。PPoS 使用质押、委托、随机选取的形式选出参与共识的验证节点，Giskard BFT 使用类 BFT 算法实现区块的生产和验证。

PPOS——验证节点选取

在介绍 PPoS 之前，我们先科普一下 PoS，目前 PoS 共识方案可以分为四类：

PoS 共识概述

** Chain-Based**

这是早期的一代 PoS。根据持有 token 的数量伪随机地选择验证人进行区块生产。其中还有 PoS+PoW 方案，一般是 PoW 出块，通过 PoS 选择验证人进行验证，以太坊的 Casper1.0 也是一种混合 PoS/PoW 的方案，作为其从 PoW 转换到 PoS 的中间方案。

** DPoS (Delegated Proof of Stake)**

委托权益证明。每个 token 持有人可以把权利委托给部分代表，由代表参与区块的生产和验证。

** VRF (Verifiable Random Function)**

可验证随机函数用于验证节点的随机选取。目前，Dfinity、Cardano 和 Algorand 等采用了这种方案。

** BFT (Byzantine Fault Tolerance)**

拜占庭容错。选出验证节点后通过运行 BFT 协议经过多轮投票确认区块完成共识。目前 Tendermint、Stellar、Ontology、Zilliqa、NEO 等都是采用这类共识算法。

PlatON 的共识方案 PPoS，也就是我们常说的概率性权益证明，它本质是一种 PoS 共识方案，根据节点的权益绘制成二项分布累积分布曲线，并使用 VRF 随机选取验证节点。

PPoS 解决的关键核心点在于验证人的选取不仅与节点权益的大小有关，还兼具随机性，也就是说选出的验证节点不一定是权益最高的节点，权益较低的节点也有一定的选中概率。随机性算法可以保证选取的结果不可预测、不可操控且公平可靠。PPoS 本质上是 PoS+VRF 方案的结合。

简单总结就是： PPoS 提供了一种尽可能公平、随机地从众多参与节点中选取出若干验证节点的方案。

针对验证人选取的随机性问题，我们也做了专题研究，请参看《PoS 共识中的验证人选取》一文：

【技术云图】PoS 共识中验证人选举的随机方案（上）

【技术云图】PoS 共识中验证人选举的随机方案（下）

BFT——区块共识

验证节点被选举出来之后，运行共识协议进行区块生产和验证，整个过程需要节点之间相互协作，对区块进行相互确认，得出一致结论，达成区块共识。

上文中提到，区块链中的共识算法不仅需要考虑 Crash 节点，还需要考虑 Byzantine 节点。什么是拜占庭节点？我们从一个故事说起。

拜占庭将军问题

拜占庭罗马帝国国土辽阔，为了达到防御目的，每块封地都驻扎一支由将军统领的军队，每个军队都分隔很远，将军与将军之间只能靠信差传递消息。

在战争的时候，拜占庭军队内所有将军必须达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定影响将军们达成一致共识。在已知有将军是叛徒的情况下，其余忠诚的将军如何达成一致协议的问题，这就是拜占庭将军问题。

拜占庭将军问题所描述的是好的将军不知道其他将军是好的，还是坏的，但所有好的将军的目的是：行动一致，共同进退。所以，他们需要在策略上达成一致。

看到这里，相信大家对拜占庭节点也有了初步的理解。简单地说，在区块链系统中存在以下两类错误：

• 第一类错误是节点崩溃、网络故障、丢包等，这种错误类型的节点是没有恶意的，属于非拜占庭错误。

• 第二类错误是节点可能是恶意的，不遵守协议规则。例如验证者节点可以延迟或拒绝网络中的消息、领导者可以提出无效块或者节点可以向不同的对等体发送不同的消息。在最坏的情况下，恶意节点可能会相互协作。这些被统称为拜占庭错误。

要让这个问题有解，还需要先引入一个概念—— 分布式网络模型 ，按照分布式系统理论，分布式系统的网络模型分为三类：

• 同步网络模型 ：节点所发出的消息，在一个确定的时间内，肯定会到达目标节点

• 异步网络模型 ：节点所发出的消息，不能确定一定会到达目标节点

• 部分同步网络模型 ：节点发出的消息，虽然会有延迟，但是最终会到达目标节点

拜占庭将军问题的解决，有一个十分重要的前提，那就是通信信道必须是可靠的。如果信道不能保证可靠，那么拜占庭问题无解。这也就是 FLP 不可能原理，即在异步网络模型假定下，共识算法不可能同时满足安全性（safety）和活跃性（liveness），也就是说，在一个不可靠的通信链路上试图通过通信以达成一致是基本不可能或者十分困难的。至于什么是安全性和活跃性，我们后面再说。

其实，拜占庭将军问题最早是由 Leslie Lamport 在 1982 年发表的论文《The Byzantine Generals Problem》提出的，他证明了在将军总数大于 3f，背叛者为 f 或者更少时，忠诚的将军可以达成命令上的一致，即 3f+1<=n。而 Miguel Castro 和 Barbara Liskov 在 1999 年发表的论文《Practical Byzantine Fault Tolerance》中首次提出 PBFT 算法，该算法容错数量也满足 3f+1<=n。

BFT 是一个已经被研究得比较透彻的理论，它告诉我们，基于部分同步网络模型的假定，在不超过三分之一的故障节点和作恶节点情况下，非拜占庭节点之间可达到最终一致性。PBFT 是其中最为著名的实现算法，意为实用拜占庭容错算法。目前，区块链的共识算法大多都是基于 BFT 的实现。Giskard BFT 也是由 PBFT 演进而来。

PBFT 算法在区块链共识的应用

PBFT 算法被广泛应用于各类区块链共识，它不仅解决了共识过程中可能发生的拜占庭节点问题，同时也使系统始终能够保持两个属性：安全性（safety）和活跃性（liveness）。

• 安全性 ：在 Crash 节点和 Byzantine 节点两类错误发生时，共识系统不能产生错误的结果。在区块链中，指的是不会产生双重花费和分叉。

• 活跃性 ：系统一直能持续产生提交，在区块链中，指的是共识会持续进行，不会卡住。假如一个区块链系统的共识不可持续，那么系统无法响应客户端新的交易请求，也就是不满足 liveness。

我们直接以 PBFT 算法在区块链共识的应用为例，总结算法的核心流程：

PBFT 的共识过程

由上图可知，PBFT 是一个典型的三阶段提交算法：

• pre-prepare （预备阶段） ：各节点负责接收区块、执行区块，产生区块投票签名，开始广播签名给所有共识节点

• prepare （准备阶段） ：各节点负责收集签名，某节点收集满 2*f 的签名后，表明自身达到可以提交区块的状态，开始广播 Commit 包

• Commit （提交阶段） ：各节点负责收集 Commit 包，某节点收集满 2*f+1 的 Commit 包后，直接将本地缓存的最新区块提交到数据库

看到这里，也许你会有以下疑问：

为什么不同阶段所需要的签名个数不同

对于 prepare 和 commit 阶段来说，考虑最坏的情况：我们假设收到 f 个是正常节点发过来的签名，也有 f 个是恶意节点发过来的，那么，第 2f+1 个签名只可能是正常节点发过来的（因为我们限制了最多只有 f 个恶意节点）。由此可知，「大多数」正常的节点还是可以让系统工作下去的。所以 2f+1 这个参数和 n>=3f+1 的要求是逻辑自洽的。而在 prepare 阶段，节点 0 发出消息即可认为确认消息，所以 prepare 阶段只需收集 2*f 个签名。

为什么只有两阶段消息不能达成一致性

只有 pre-prepare 和 prepare 两个阶段消息是无法达成一致的。举例说明，假设没有 commit 阶段，节点 1 在 prepare 阶段收集满 2*f 的签名后，达到 Prepared 状态，然而这个 Prepared 仅是节点 1 的一个局部视角，不是全局一致，此时节点 1 不能保证其余节点都达到 Prepared 状态，如果少于 f 个非拜占庭节点成为 Prepared 状态，节点 1 又确认了该消息，那么系统就出现了不一致。

为什么三阶段消息可以达成一致性

说到这里，其实就很好理解为什么三阶段消息可以达成一致性，某节点收集满 2*f+1 的 Commit 包意味着有 f+1 个非拜占庭节点达成了 Prepared 状态，也就意味着「多数」节点已经认同了消息。

下面，我们再介绍 PBFT 的视图和视图切换流程。

PBFT 共识算法使用视图 view 记录每个节点的共识状态，相同视图节点维护相同的 Leader 和 Replicas 节点列表。当 Leader 出现故障，为了保证协议活跃性（liveness），会发生视图切换，若视图切换成功 (至少 2*f+1 个节点达到相同视图)，则根据新的视图选出新 leader 。

话不多说，直接上视图切换流程图：

PBFT 的视图切换流程

PBFT 的视图切换流程也分为三个阶段：

• view-change ：各副本节点（Replica) 认为主节点（Primary）有问题时，会向其它节点发送 view-change 消息

• view-change-ack ：各节点接收到 2*f+1 个 view-change 消息后，选举当前存活的节点编号最小的节点成为新的主节点，并向该节点发送 view-change-ack 消息

• new-view ：当新的主节点收到 2*f+1 个其它节点的 view-change-ack 消息后，向其它节点广播 new-view 消息。注意：从节点不会发起 new-view 事件

通过对共识流程的分析，相信大家对 view 切换流程都能够很好地理解，这里我们不再赘述。接下来我们着重分析 PBFT 算法存在的问题，以及 Giskard BFT 改进优化。

PBFT 存在的问题

通过对 PBFT 共识流程三阶段的详细分析，可以看到消息传输的开销很大。系统在尝试达成状态共识时，涉及到 n 个节点都需要广播消息到 n-1 个其它节点，因此算法通信复杂度达到 O(n²)，在节点数目为 1000 的情况下所需要交换的通信量为 1,000,000。有实验得出当节点数量超过 20 时，算法的性能会急剧下降。

另外，在 PBFT 选举 Leader 的过程中，有可能经过多轮交互，选举出的 Leader 一直长时间运行，直到 Leader 节点出现故障才发起视图切换流程。但在区块链系统中，视图 view 表示一个共识单元，共识过程由一个接一个的 view 组成，每个 view 中由一个确定的提议人来主导共识协议，产生区块，其余验证人对区块进行投票签名达成共识。因为节点产生区块与利益相关（如记账权，区块奖励等），因此需要频繁地更换出块节点，也就是需要频繁地切换视图 view，这势必会带来巨大的网络资源消耗。

Giskard BFT 共识优化

所以我们基于 BFT 协议，结合区块链的特性，主要围绕着以下几点进行协议优化，设计了 Giskard BFT 。

_ view-change 流程优化_

所有的 BFT 协议都通过 view-change 来更换主节点。PBFT，SBFT 等协议具有独立的 view-change 流程，当主节点出问题后才触发。而在 Tendermint、HotStuff 等协议中没有显式的 view-change 流程、view-change 流程合入正常流程中，因此提高了 view-change 的效率，将 view-change 的通信复杂度降低。

Giskard BFT 也是基于 view 的的共识协议，为降低通讯复杂度，Giskard BFT 也没有显式的 view change 流程，而是把这个流程和正常出块流程结合。Giskard BFT 约定每个提议节点在本视图内连续产生 10 个区块，并且每个区块都达成 QC （Quorum Certificate，表示节点收到针对该区块的 2*f+1 个签名）状态后，则自动切换到下一个 view ，不需要单独的 view-change 投票流程。

下图是显式的 ViewChange 流程，可以看到它并没有类似 PBFT 中的 view-change-ack 和 new-view 阶段，这两个流程被后续的 prepareQC(n) 进行代替。

Giskard BFT viewchange 投票流程

总结一下，view-change 流程优化的两个重点：

• 不需要显式的 view change 流程，减少投票动作。

• 没有 view-change-ack 和 new-view 阶段，而是结合区块链特性，由后续的 prepareQC(n) 对新的 view 进行「间接」确认。

_ 应用 BLS 聚合签名_

为了进一步减少消息通讯量，我们采用了聚合签名技术。业界主流的聚合签名方案是 BLS 聚合签名。BLS 聚合签名是在 BLS 签名方案基础上的扩展方案。

在 Giskard BFT 中，我们把针对 block 和 view-change 消息的多个节点签名聚合成一个签名，可以简单地理解为：把多个节点的一段很长的签名「压缩」为一个签名。这种做法极大地降低了通讯量，对提高协议的通信效率也起到了很大的作用。

_ 区块生产和验证并行化_

此处优化是 Giskard BFT 的独到创新之处。这里的并行指的是：区块生产和区块验证的并行化。

上文提到，Giskard BFT 是基于视图 view 的共识协议，每个提议节点在本视图内连续产生 10 个区块，并行流程如下：

• 提议节点在一个 view 内可以连续提议多个区块，下一个区块的产生不用等上一个区块达到 QC 状态。

• 验证人在接收上一个区块投票的同时，可以并行执行下个区块的交易。

这种做法极大提高出块速度，也提高了系统的共识性能。

引进 pipeline 方式对区块进行确认

在传统 BFT 主导的区块链系统中，每个区块的共识通常都需要经历明确的 Pre-Commit 和 Commit 阶段才最终确认：

• Pre-Commit ：当节点收到 2*f+1 个 Prepare 投票时会广播 Pre-Commit，Pre-Commit 可以看作对 Prepare 阶段的确认。

• Commit ：当收到 2*f+1 个 Pre-Commit 投票时，表明所有节点对指定消息达成一致，提交到本地磁盘。

Giskard BFT 中的每个区块只有 Prepare 投票，没有明确的 Pre-Commit 和 Commit 阶段，那么区块如何达到最终的确认呢？Giskard BFT 可看作 Pipeline 版本的 BFT ，每个 prepareQC 都是对前面区块更高阶段的确认。

Giskard BFT 的区块确认流程

如图所示 prepareQC(2) 作为 Block(1) 的 Pre-Commit 阶段 prepareQC(3) 作为 Block(1) 的 Commit 阶段，Block(2) 的 Pre-Commit 阶段。

简单来说，就是「省略」了 PBFT 的 Commit 阶段，这里读者可能有疑虑：前文不是明确给出结论，必须通过三阶段消息才能达成一致性？其实 Giskard BFT 不是真的没有 Commit 阶段，而是结合区块链特性，将下一个区块的 QC 状态作为上一个区块的 Commit 间接确认。

Giskard BFT 结合区块链的链式结构，引进 pipeline 方式对区块进行确认，使得协议变得简洁而优美，能够很好地进行流程化作业，提高了协议的性能，另外也对协议的可扩展性留足了设计空间。

结语

目前，应用了 Giskard 共识协议的 PlatON 测试网、主网和 Alaya 网络都已经长时间稳定、高效运行，它的安全性（safety）和活跃性（liveness）得到了充分的验证，同时 Giskard 共识对解决系统过于中心化，降低网络通信复杂度、消息复杂度，提升共识效率以及整个区块链的交易处理性能所起到的作用毋庸置疑。

在后期的协议版本中，我们将继续深入优化：验证人的选取不仅采用 VRF，还计划结合可验证秘密分享 PVSS、BLS 等密码算法进一步增加随机性；引入分组共识再次提升算法的可扩展性，以高效支持更多的验证节点加入，增加网络的安全性和容错性。