Jan's website

PBFT共识协议

Contents

概述 #

在分布式系统中，节点之间需要达成共识才能保证数据的一致性。然而，在现实环境中，节点可能会因为网络故障、硬件故障或者恶意攻击而出现各种问题。传统的共识算法（如 Raft）只能处理节点故障（crash fault），但无法应对节点可能发送错误消息的情况，即拜占庭故障（Byzantine fault）。

BFT（Byzantine Fault Tolerance，拜占庭容错）是一套描述分布式系统如何在存在恶意节点的情况下通讯（达成共识）的理论。PBFT（Practical Byzantine Fault Tolerance，实用拜占庭容错）则是对 BFT 理论的具体算法实现，由 Miguel Castro 和 Barbara Liskov 在 1999 年提出。

PBFT 算法能够在异步网络环境下，容忍不超过 1/3 的节点是拜占庭节点（即可能发送错误消息或恶意行为的节点），并能够达成共识。这使得 PBFT 在区块链、分布式数据库等需要强一致性的场景中得到广泛应用。

PBFT 算法复杂度为 O(n2)，视图更换时为 O(n3)，最坏情况（f 个 Leader 都出故障）时为 O(n4)。

假设 f 是允许的作恶节点个数，n 是总节点个数，则 n=3f+1。

为什么是 3f+1？

这个公式的推导基于以下考虑：需要 f+1 个正确节点（少数服从多数），f 个作恶节点，f 个故障节点，所以总共是 3f+1。相比之下，Raft 算法是 n=2f+1，因为它只需要处理节点故障，不存在作恶节点。

正确节点需要 f+1 是因为：假如反对票的 f 个节点全部宕机，就需要 f+1 个投赞成票的节点才能形成多数，遵循少数服从多数的原则。

checkpoint： 就是当前节点处理的最新请求序号。

stable checkpoint （文档检查点）： stable checkpoint 就是大部分节点 （2f+1） 已经共识完成的最大请求序号。

作用：最大的目的就是减少内存的占用。因为每个节点应该记录下之前曾经共识过什么请求，但如果一直记录下去，数据会越来越大，所以应该有一个机制来实现对数据的删除。那怎么删呢？很简单，比如现在的稳定检查点是 213，那么代表 213 号之前的记录已经共识完成了，所以之前的记录就可以删掉了。

高低水位： 高水位和低水位用来限制那些消息能被接收。低水位等于最后的稳定检查点，高水位=低水位+L。

算法核心流程 #

PBFT核心流程

算法的核心三个阶段分别是 pre-prepare 阶段（预准备阶段），prepare 阶段（准备阶段）， commit 阶段（提交阶段）。图中的C代表客户端，0，1，2，3 代表节点的编号，打叉的3代表可能是故障节点或者是问题节点，这里表现的行为就是对其它节点的请求无响应。0 是主节点。整个过程大致如下：

  • request：首先，客户端向主节点发起请求，请求消息m=[op,ts,c-id,c-sig]

    • op：需要执行的操作

    • ts：时间戳

    • c-id：客户端ID

    • c-sig：客户端的签名

  • pre-prepare（预准备阶段）：主节点接收到请求后赋值一个序列号sn，然后广播一条消息PP=[vn,sn,D(m),p-sig,m]，这时候其他节点接收到pre-prepare消息可以接受或拒绝，什么时候拒绝呢？一种典型的情况是消息里的vn和sn在之前的消息里出现过，但D(m)和m却和之前的消息不一致，或者请求编号（sn）不在高低水位之间。

    • vn：视图号，视图的编号是什么意思呢？比如当前主节点为 A，视图编号为 1，如果主节点换成 B，那么视图编号就为 2。

    • sn：请求编号

    • D(m)：客户消息（见request阶段）的哈希值

    • p-sig：主节点的签名数据

    • m：客户消息

  • prepare（准备阶段）：其他节点同意后会广播一条消息P=[vn,sn,D(m),b-id,b-sig]，并将消息添加到日志。注意：当节点收到Prepare消息后，会检查消息视图号是否等于当前视图号，也会检查上下水位。

    • b-id：从节点id

    • b-sig：从节点签名数据

commit（确认阶段）：

当收到2f个Prepare消息后（主节点本身是认可这条消息的，所以只需2f），广播消息C=[vn,sn,D(m),b-id,b-sig]。在这个阶段，为什么是2f+1？在3f+1的基础上减去一个f，这个f是宕机的，既然是宕机就不会广播消息，所以收到2f+1就可以了。

当收到2f+1Commit消息，到达commit-local状态，这时候执行m请求的操作，写入数据。

response（响应阶段）：接上面，然后返回消息R=[vn,ts,b-sig]给客户端。

客户端等待来自不同节点的响应，若收到f+1个响应相同，则该响应即为运算结果。为什么是f+1？ 假设最坏的情况，f个节点都是作恶节点，那么第 f+1个节点是诚实的，有一个诚实的节点证明就可以了，经过前面的阶段，这个诚实的节点可以代表大多数。

为什么需要三个阶段？

第二个阶段（Prepared 状态）只能证明非拜占庭节点在只有请求 m 使用 <v, n> 上达成一致，但节点i无法确定其他节点也到达prepare状态。如果少于2f+1个节点成为prepare状态（比如这时候更换主节点导致），然后执行了请求m，系统可能就会出现不一致。

那么为什么加了commit阶段就可以达成共识呢？

情况1：如果到达prepare阶段，这时候更换主节点，新的主节点会把上个视图未执行完的请求重新走一遍共识。

情况2：如果到达commit阶段，且只有少数节点收到2f+1确认消息，并执行了请求。这时候更换主节点，由于多数节点都未执行，所以新节点会重新把这条请求走一遍共识，注意，这条消息已经是到达prepare阶段了（因为已经被2f+1确定），所以共识直接从prepare阶段开始，当那几个少数已执行过的节点收到，只会检查消息的视图是否和当前视图一致。

即到达prepare状态只能令"我知道大家都知道了"，但是要达成共识必须"大家都知道大家都知道了"，也就是commit状态。

2f+1 个 Commit 消息，去掉最多 f 个拜占庭节点伪造的消息，得出至少 f+1 个非拜占庭节点发送了 Commit 消息，即至少 f+1 个非拜占庭节点是 Prepared 状态，证明了"大家都知道大家都知道"。

检查点协议 #

节点执行完一个请求，并得到足够的证据后，会写入日志做存证。但是不可能一直写入，这样开销太大，因此，PBFT提供一个检查点协议，在请求序号到达一定阶段（如能被某个常数100整除）时设立检查点。

当达到条件后，节点广播消息：CheckPoint=[n,d,i]，每个节点收到2f+1个相同n的消息后，从日志删除n之前的数据。

视图转换（view change） #

视图转换

当主节点挂了（超时无响应）或者从节点集体认为主节点是问题节点时，就会触发 ViewChange 事件，ViewChange 完成后，视图编号将会加 1。下图展示 ViewChange 的三个阶段流程：

从节点认为主节点有问题时（通过时钟超时），会向其它节点发送 view-change 消息ViewChange=[v+1,n,C,P,i]，当前存活的节点编号最小的节点将成为新的主节点。

  • v：当前视图号

  • n：节点当前的稳定检查点

  • C：2f+1个节点的有效checkpoint信息集合，也就是支持n是有效的证据。

  • P：每个i节点中上一个view中编号大于n的已到达prepare状态的请求消息的集合，这些请求需要继续执行。（为什么是到达prepare？我猜是到达prepare才有2f+1个有效签名）

  • i：节点的编号

当前主节点（编号最小的）收到2f+1个ViewChange后，确认大多数人觉得需要更换后，广播消息NewView=[v+1,V,O]，然后主节点继续执行上个视图未处理完的请求，从 pre-prepare 阶段开始，其他节点收到pre-prepare请求后正常执行。到这时，正式进入v+1时代。

  • V：新的主节点收到的view-change的消息集合，即多数人支持换主的证据。

  • O：pre-prepare消息的集合

View-Change流程

总结 #

PBFT 能够在异步网络环境下，容忍不超过 1/3 的节点是拜占庭节点，并能够达成共识。这看似与 FLP 不可能定理（在完全异步的分布式系统中，即使只有一个节点可能故障，也无法达成确定性共识）相矛盾，但实际上两者对异步通信环境的假设不同。FLP 定理假设的是完全异步环境且没有超时机制，而 PBFT 引入了超时机制，这使得它能够在保证安全性的同时，也保证了系统的活性（Liveness）。

此外，PBFT 还通过消息认证机制确保消息发送者的身份可以被确定，这进一步增强了系统的安全性。虽然 PBFT 的通信复杂度较高（O(n2)），但在需要强一致性和拜占庭容错的场景中，它仍然是一个重要的共识算法选择。