一文了解Alaya共识方案（一）：初识BFT共识协议

PlatON元网络Alaya于10月24日正式启动，一经启动，便赢得了用户广泛关注，作为Alaya运用了怎样的底层技术？如何支撑起未来大规模应用的部署？

我们将分几期内容详解Alaya的底层技术。

在Alaya中，我们提出了一种基于部分同步假设情形下的并行拜占庭容错协议，解决区块链共识效率的问题，基于此我们延展出了全新的共识协议，我们称之为

这里分析了PBFT，Tendermint，Hotstuff等共识协议，Giskard共识协议综合了其优点，通过pipeline的方式完成区块生成和确认的并行，在一个视图窗口内可以出多个块，并可以在O(n2)内完成视图窗口切换，从而提高共识效率。

按照分布式系统理论，分布式系统的网络模型分为三类：

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

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

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

同步网络模型是十分理想的情况，异步网络模型是更为贴近实际的模型，但据FLP不可能[1]原理，在异步网络模型假定下，共识算法不可能同时满足安全性（safety）和活跃性（liveness）。目前的BFT类共识算法多是基于部分同步网络模型假定。我们也是基于部分同步网络模型假定来进行讨论。

BFT共识协议

一个分布式系统是由多个节点组成，节点之间需要网络发送消息通信，根据它们遵循的协议在某个任务消息达成共识并一致执行。这个过程中会出现很多类型的错误，但它们基本上可以分为两大类。

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

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

考虑到这两种错误，我们希望系统始终能够保持两个属性：

安全性：在以上两类错误发生时，共识系统不能产生错误的结果。在区块链的语义下，指的是不会产生双重花费和分叉。

活跃性：系统一直能持续产生提交，在区块链的语义下，指的是共识会持续进行，不会卡住。假如一个区块链系统的共识卡在了某个高度，那么新的交易是没有回应的，也就是不满足liveness。

BFT(拜占庭容错协议)是一种即使系统中存在恶意节点也能保证分布式系统的安全性和活跃性的协议。根据Lamport[2]的经典论文，所有BFT协议都有一个基本假设：节点总数大于3f时，恶意节点最大为f ，诚实节点可以达成一致的正确结果。

PBFT

实用拜占庭容错算法（PBFT[3]）是现实世界里首批能够同时处理第一类和第二类错误的拜占庭容错协议之一，基于部分同步模型，解决了之前BFT类算法效率不高的问题，将算法复杂度由节点数的指数级降低到节点数的平方级，使得拜占庭容错算法在实际系统应用中变得可行。

目前区块链中使用的BFT类共识协议都可以认为是PBFT的变形，与PBFT一脉相承。

1. 正常流程

PBFT正常流程如下所示（图1中C为客户端，系统中有编号分别为0～3的四个节点，且节点3为拜占庭节点）:

PBFT正常流程

正常流程为3阶段协议：

pre-prepare：主节点（Primary）广播预准备消息（Preprepare）到各副本节点（Replica)

prepare：该阶段是各个节点告诉其他节点我已经知道了这个消息，一旦某个节点收到了 包含n-f 个prepare消息（我们将使用QC也就是Quorum Certificate来指代，下同）则进入prepared状态

commit：该阶段是各个节点以及知道其他节点知道了这个消息，一旦某个节点收到了n-f 个commit消息（QC）则进入committed状态

2.

是PBFT最为关键的设计，当主节点挂了（超时无响应）或者副本节点集体认为主节点是问题节点时，就会触发ViewChange事件，开始viewchange阶段。

此时，系统中的节点会广播视图切换请求，当某个节点收到足够多的视图切换请求后会发送视图切换确认给新的主节点。当新的主节点收到足够多的视图切换确认后开始下一视图，每个视图切换请求都要包含该节点达到prepared状态序号的消息。

在视图切换过程中，我们需要确保提交的消息序号在整个视图更改中也是一致的。简单来说，当一个消息定序为n，且收到2f+1个prepare 消息之后，在下个视图中，依然会被分配序号为n，并重新开始正常流程。

PBFT视图切换流程

如图2所示，viewchange会有三个阶段，分别是view-change，view-change-ack和new-view阶段。从节点认为主节点有问题时，会向其它节点发送view-change消息，当前存活的节点编号最小的节点将成为新的主节点。当新的主节点收到2f个其它节点的view-change消息，则证明有足够多的节点认为主节点有问题，于是就会向其它节点广播。

（未完待续）