PBFT共识算法

PBFT算法概述

定义与介绍

定义

Practical Byzantine Fault Tolerance（PBFT）是一种用于分布式计算和分布式系统中的共识算法，旨在解决拜占庭容错问题。（拜占庭容错问题涉及到在分布式系统中存在故障或恶意节点的情况下，如何确保系统能够维持一致性）。

介绍

PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。为了描述方便，假设|R|=3f+1，这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但是额外的副本除了降低性能之外不能提高可靠性。

PBFT算法中节点只有两种角色，主节点（primary）和副本（replica），两种角色之间可以相互转换。两者之间的转换又引入了视图（view）的概念，视图在PBFT算法中起到逻辑时钟的作用。

特点与工作原理

特点

拜占庭容错： PBFT旨在解决拜占庭容错问题，这意味着系统可以继续正常运行，即使有一些节点是恶意的或出现了故障。
节点投票： 在PBFT中，网络中的节点会相互交流以达成共识。每个节点会对提出的交易或区块进行投票，表达自己的意见。
三阶段协议： PBFT采用了一种三阶段的协议，包括预备（pre-prepare）、准备（prepare）和提交（commit）阶段。在每个阶段，节点都会按照协议的规则发送消息，以便其他节点验证并最终达成共识。
多数原则： PBFT要求绝大多数节点达成一致意见，才能够执行交易或添加区块。这有助于防止恶意节点或错误导致的不一致性。
较高性能： PBFT通常具有较高的性能，因为节点之间的通信和共识是快速的，不需要执行复杂的计算难题（如PoW）。
可扩展性： 尽管PBFT对于确保一致性非常有效，但它的可扩展性在大型网络中可能受到限制。

工作原理

其核心工作原理是在存在拜占庭错误的情况下，通过多个节点协作完成共识，保证系统的一致性和可靠性。

具体：

1. 请求阶段（Request）

客户端（Client）向主节点发送请求，内容包括操作类型和参数。
请求格式为：<请求ID, 操作, 客户端ID>，通过消息认证机制确保其来源可信。

2. 预准备阶段（Pre-Prepare）

主节点接收到客户端请求后，为该请求分配序列号（Sequence Number）。
主节点将请求与序列号组成的消息广播给所有备节点，格式为：
<视图号, 序列号, 请求内容>。
备节点验证：
1. 消息的完整性和合法性。
2. 主节点是否按照请求的顺序分配序列号。
若验证通过，备节点记录该消息并进入下一阶段。

3. 准备阶段（Prepare）

每个备节点将自己接收到的 Pre-Prepare 消息广播给其他节点，形成 Prepare 消息。
节点收到至少 2f+1条来自不同节点的 Prepare 消息（包括自身）后，确认该请求在网络中达成了一致性，记录状态并进入下一阶段。

4. 提交阶段（Commit）

每个节点将 Prepare 消息汇总并广播一个 Commit 消息。
当一个节点收到至少 2f+1条 Commit消息后：
1. 确认请求已被网络中大多数节点接受。
2. 执行操作，并记录操作结果。

5. 回复阶段（Reply）

节点将执行结果发送给客户端。
客户端接收到来自至少 f+1 个不同节点的相同回复后，确认操作成功完成。

PBFT算法流程

在算法开始阶段，主节点由 p = v mod n计算得出，随着v的增长可以看到p不断变化。

首先客户端发送消息m给主节点p，主节点就开始了PBFT三阶段协议，其中pre-prepare和prepare阶段最重要的任务是保证同一个主节点发出的请求在同一个视图（view）中的顺序是一致的，prepare和commit阶段最重要的任务是保证请求在不同视图之间的顺序是一致的。

主节点收到客户端发送来的消息后，构造pre-prepare消息结构体< <PRE-PREPARE, v, n, d>, m >广播到集群中的其它节点。
1. PRE-PREPARE标识当前消息所处的协议阶段。
2. v标识当前视图编号。
3. n为主节点广播消息的一个唯一递增序号。
4. d为m的消息摘要。
5. m为客户端发来的消息。
副本(backup)收到主节点请求后，会对消息进行检查，检查通过会存储在本节点。当节点收到2f+1（包括自己）个相同的消息后，会进入PREPARE状态，广播消息< <PREPARA, v, n, d, i> >，其中i是本节点的编号。对消息的有效性有如下检查：
1. 检查收到的消息体中摘要d，是否和自己对m生成的摘要一致，确保消息的完整性。
2. 检查v是否和当前视图v一致。
3. 检查序号n是否在水线h和H之间，避免快速消耗可用序号。
4. 检查之前是否接收过相同序号n和v，但是不同摘要d的消息。
副本收到2f+1（包括自己）个一致的PREPARE消息后，会进入COMMIT阶段，并且广播消息< COMMIT, v, n, D(m), i >给集群中的其它节点。在收到PREPARE消息后，副本同样也会对消息进行有效性检查，检查的内容是上文1, 2, 3。
副本收到2f+1（包括自己）个一致的COMMIT个消息后执行m中包含的操作，其中，如果有多个m则按照序号n从小到大执行，执行完毕后发送执行成功的消息给客户端。

算法的流程图：

Pbft算法的时间复杂度？
A：Pbft算法的时间复杂度O(n^2)，在prepare和commit阶段会将消息广播两次，一般而言，Pbft集群中的节点都不会超过100。

PBFT 算法的优势与挑战

优势

适用场景

PBFT是一种可行的共识算法，特别适用于需要高度安全性和快速共识的场景，例如金融领域或联盟区块链。

较高容错性

为了更多的容错性，PBFT算法最大的容错节点数量( n - 1 ) / 3，也就是是说4个节点的集群最多只能容忍一个节点作恶或者故障。

保证集群的可用性&稳定性

具有视图切换（View-Change）机制。

view-change提供了一种当主节点宕机以后依然可以保证集群可用性的机制。view-change通过计时器来进行切换，避免副本长时间的等待请求。
当副本收到请求时，就启动一个计时器，如果这个时候刚好有定时器在运行就重置（reset）定时器，但是主节点宕机的时候，副本i就会在当前视图v中超时，这个时候副本i就会触发view-change的操作，将视图切换为v+1。

副本i会停止接收除了checkpoint,view-change和new view-change以外的请求，同时广播消息
1
<VIEW-CHANGE, v+1, n, C, P, i>
的消息到集群。
1. n是节点i知道的最后一个stable checkpoint的消息序号。
2. C是节点i保存的经过2f+1个节点确认stable checkpoint消息的集合。
3. P是一个保存了n之后所有已经达到prepared状态消息的集合。
当在视图( v+1 )中的主节点p1接收到2f个有效的将视图变更为v+1的消息以后，p1就会广播一条消息
1
<NEW-VIEW, v+1, V, Q>
1. V是p1收到的，包括自己发送的view-change的消息集合。
2. Q是PRE-PREPARE状态的消息集合，但是这个PRE-PREPARE消息是从PREPARE状态的消息转换过来的。
从节点接收到NEW-VIEW消息后，校验签名，V和Q中的消息是否合法，验证通过，主节点和副本都进入视图v+1。

当p1在接收到2f+1个VIEW-CHANGE消息以后，可以确定stable checkpoint之前的消息在视图切换的过程中不会丢，但是当前检查点之后，下一个检查点之前的已经PREPARE可能会被丢弃，在视图切换到v+1后，Pbft会把旧视图中已经PREPARE的消息变为PRE-PREPARE然后新广播。

如果集合P为空，广播<PRE-PREPARE, v+1, n, null>，接收节点就什么也不做。
如果集合P不为空，广播<PRE-PREPARE, v+1, n,d>

总结一下，在view-change中最为重要的就是C，P，Q三个消息的集合，C确保了视图变更的时候，stable checkpoint之前的状态安全。P确保了视图变更前，已经PREPARE的消息的安全。Q确保了视图变更后P集合中的消息安全。回想一下pre-prepare和prepare阶段最重要的任务是保证，同一个主节点发出的请求在同一个视图（view）中的顺序是一致的，而在视图切换过程中的C，P，Q三个集合就是解决这个问题的。

视图协商（NegotiateView）机制

集群在运行过程中，可能出现网络抖动、磁盘故障等原因，会导致部分节点的执行速度落后大多数节点，在Pbft中采用了视图协商（NegotiateView）的机制来保持同步。

当一个节点多次view-change失败就触发NegotiateView同步集群数据，流程如下：

新增节点Replica 4发起NegotiateView消息给其他节点；
其余节点收到消息以后，返回自己的视图信息，节点ID，节点总数N；
Replica 4收到2f+1个相同的消息后，如果quorum个视图编号和自己不同，则同步view和N；
Replica 4同步完视图后，发送RevoeryToCheckpoint的消息，其中包含自身的checkpoint信息；
其余节点收到RevoeryToCheckpoint后将自身最新的检查点信息返回给Replica 4;
Replica 4收到quorum个消息后，更新自己的检查点到最新，更新完成以后向正常节点索要pset、qset和cset的信息（即PBFT算法中pre-prepare阶段、prepare阶段和commit阶段的数据）同步至全网最新状态；

遵循线性一致性（ linearizability ）

（线性一致性的解释：就是在并发编程里，我们进行了一番操作，得到了一个结果。然后这个操作的运行记录，和按照串行顺序一步步来的运行记录相一致，我们就能称其为「线性一致的（linearizable）」）。

挑战

PBFT的实现可能相对复杂，且在大规模网络中可能面临一些挑战。

PBFT算法假设的环境比Raft算法更加的’恶劣‘，Raft算法只支持容错故障节点，而PBFT算法除了需要支持容错故障节点之外，还需要容忍作恶节点（作恶节点节点是指可能对接收到的消息作出截然相反的回复，甚至伪造消息）。

PBFT算法的实现与优化

与传统的Proof of Work（PoW）和Proof of Stake（PoS）等共识算法不同，PBFT通常用于私有或联盟区块链网络，其中节点的身份已知，且相互信任。其和 Raft算法解决的核心问题都是在分布式环境下如何保持集群状态的一致性，简而言之就是一组服务，给定一组操作，最后得到一致的结果。