简介
PBFT中的P指的是Practical。PBFT算法的实用性体现在它适用于异步的网络环境，例如因特网。而且相比更早的算法，PBFT将响应时间降低了多个数量级。异步网络环境的不利因素包括：消息发送失败、消息发送超时/延迟、重复发送消息、消息乱序抵达。
PBFT算法在n台相互连接的、运行相同服务的机器（replica）上运行。服务是有状态（stated）的，并且保证在任意状态下，对给定操作（operation），服务节点执行的运算是确定的（deterministic）。
三阶段算法
PBFT算法的总体流程如下：
- 客户端（client）向服务集群（replicas）中的某台服务器发送操作请求（request），该request会直接发给或者被转发给primary，进而唤起集群的主节点（primary）
- primary向所有的非主节点（backups）广播该请求
- 所有的replicas执行该请求，执行完毕后，各自将回复发送给client
- client等待 $f+1$ 个结果相同的、签名验证有效的、来自不同replica的回复，并且将该回复作为最终结果
PBFT用 $0、1、2、…、R-1$ 这些整数来标识不同机器上运行的 $R$ 个replicas，$R=3f+1$ 。
PBFT中所有的replicas都维护一个全局的视图（view），视图的编号为 $v$ ，视图编号是递增的整数。我个人理解是，视图编号 $v$ 用来标识集群当前的选举状态，编号改变代表集群选举出了新的主节点。每个replica都记录着“自认为的”当前集群视图的编号。集群的主节点取决于视图编号，$primary = v \bmod R$ ，在该视图中，primary以外的所有replicas都叫backups。
PBFT算法的执行部分分为三个阶段：PRE-PREPARE、PREPARE和COMMIT。PRE-PREPARE和PREPARE保证视图内部的requests是有序的，COMMIT保证视图之间的requests是有序的。
REQUEST
client向primary发送request消息 ${\langle REQUEST, o, t, c \rangle}_{\sigma_c}$
- REQUEST消息标识符
- 具体操作请求o
- 时间戳o，防止同一个request被重复执行
- 该client的标识符c
- client对以上内容的摘要的签名
第一阶段：PRE-PREPARE
primary收到request消息并验证有效后，向所有backups广播pre-prepare消息 ${\langle {\langle PRE-PREPARE, v, n, d \rangle}_{\sigma_p}, m \rangle}$
- PRE-PREPARE消息标识符
- 当前视图编号v
- primary为该request指定的序号n
- 该request的摘要d
- primary对以上内容的摘要的签名
- client的request消息被附着在pre-prepare之后
第二阶段：PREPARE
如果 backup收到primary广播的pre-prepare消息并验证有效，backup就会进入PREPARE阶段，并且将prepare消息 ${\langle PREPARE, v, n, d, i \rangle}_{\sigma_i}$ 广播给其他所有replicas
- PREPARE消息标识符
- 当前视图编号v
- 该request的序号n
- 该request的摘要d
- 该backup的标识符i
- backup i对以上内容的摘要的签名
第三阶段：COMMIT
定义四元谓词 $prepare(m, v, n, i)$ ，谓词成立的条件是replica i将以下内容写入了自己的message log：
- 该request消息m
- 该request消息所对应的pre-prepare消息，由视图编号v和序号n唯一标识，不存在二义性
- 来自其他 $2f$ 个不同replicas（不包括自己）发送过来的、验证有效的prepare消息
如果replica将 $prepare(m, v, n, i)$ 判定为true，那么replica就会进入COMMIT阶段，并且将commit消息 ${\langle COMMIT, v, n, D(m), i \rangle}_{\sigma_i}$ 广播给其他所有replicas
- COMMIT消息标识符
- 当前视图编号v
- 该request的序号n
- 该request的摘要D(m)
- 该replica的标识符i
- replica i对以上内容的摘要的签名
定义三元谓词 $committed(m, v, n)$ ，谓词成立的条件是有 $f+1$ 个non-faulty replica都将$prepare(m, v, n, i)$ 判定为true。
定义四元谓词 $committed-local(m, v, n, i)$ ，谓词成立的条件是 $prepare(m, v, n, i)$ 判定为true，并且replica i已经接受了来自 $2f+1$ 个不同replicas（允许包含自己）的commit消息。
如果存在replica i，能满足$committed-local(m, v, n, i)$为true，那么 $committed(m, v, n)$ 也为true，此时replica i开始执行request。
REPLY
执行完毕后，replica各自将reply消息 ${\langle REPLY, v, t, c, i, r \rangle}{\sigma}$ 发送给client，client等待 $f+1$ 个来自不同的replicas、且执行结果相同的reply消息后，接受该结果。
- REPLY消息标识符
- 当前视图编号v
- 该请求的时间戳t
- 该client的标识符c
- 该replica的标识符i
- 执行结果r
- replica i对以上内容的摘要的签名
容错保证
3f+1
在故障节点数目为 $f$ 的情况下， $3f+1$ 是最少最优的节点总数。它假设 $f$ 个故障节点的都故意发送了错误的消息，而 $f$ 个无故障节点因为延迟而没有发送消息，在这种极端情况下，仍然有 $f+1$ 个节点能及时发送正确的消息。因为 $f+1 > f$ ，因此保证了一致性。
在满足故障节点数目$\le \lfloor \frac{n-1}{3} \rfloor$的情况下，算法保证安全性（safety）与存活性（liveness）。
PBFT的容错不仅仅能容忍软件故障和机器故障，还能容忍蓄意的攻击。PBFT假设存在非常强的攻击者，能够控制多个故障节点，阻断或者延迟网络中的通讯，最大化对系统的损失。
安全性
安全性指的是，从外部观察者的角度来看，运行PBFT的分布式集群和中心化的系统没有区别，都能原子化地一次执行一个任务。
PBFT算法的安全性保证与恶意的用户数量无关。
存活性
存活性指的是，客户能在故障的服务节点数目$\le \lfloor \frac{n-1}{3} \rfloor$、且收发时间 $delay(t)$ 不会无限地随着 $t$ 增长的条件下，客户发送请求后能保证收到回复。PBFT只能在同步的网络条件下才能保证存活性。
此处的同步的网络条件，并不是服务节点之间的网络，而是指客户与服务节点进行发送请求、接收回复的网络条件。
辅助机制
数字签名
PBFT算法使用数字签名来验证消息发送者的身份：
- 假设有消息 $m$ 和节点 $i$
- 将被节点 $i$ 签名后的消息 $m$ 标记为 ${\langle m \rangle}_{\sigma_i}$
- 将消息 $m$ 的摘要（digest）标记为 $D(m)$ ，这里的摘要一般是指hash函数
在发送消息之前，节点 $i$ 先计算消息 $m$ 的摘要$D(m)$ ，然后用自己的私钥为$D(m)$ 进行签名得到 ${\langle m \rangle}{\sigma_i}$，认证信息${\langle m \rangle}{\sigma_i}$被附加在消息 $m$ 之后。网络中，所有节点都互相知道各自的公钥，也就可以认证消息的来源。
checkpoint
每个replica在执行完request的相关操作（收发pre-prepare、prepare、commit消息）后，都会记录下当前状态（state），写进自己的message log里。
为了减少不必要的存储开销，PBFT设计了checkpoint机制，安全地删除掉message log中已经得到 $f+1$ 个非故障节点证明有效的消息。为了节省checkpoint机制本身的开销，PBFT论文中建议，在执行完多个（例如，每执行完100个requests）后，replica将message log中有关于这些requests的操作记录统称为checkpoint，而将还不足以产生checkpoint的message log称为current state。
从另一个角度看，每个replica在message log中存储的内容应包括：
- 上一个稳定的checkpoint（last stable checkpoint）（之前的稳定的checkpoint都被安全地删除了）
- 零个或多个不稳定的checkpoint（zero or more checkpoints that are not stable）
- 当前的状态（current state）（之后再生成checkpoint）
当replica在本地生成新的checkpoint后，需要向所有其他replicas广播checkpoint消息 ${\langle CHECKPOINT, n, d, i \rangle}_{\sigma_i}$ 。
- CHECKPOINT消息标识符
- 该replica执行的上一个request的标识符n，该request的执行记录反应在本checkpoint记录的状态中
- 当前状态的摘要d
- 该replica的标识符i
- replica i对以上内容的摘要的签名
当replica接收到来自 $2f+1$ 个不同replicas（包括自己）发送的checkpoint消息，那么就可以确认该checkpoint是stable checkpoint。这表明所有序号 $\le n$ 的request的执行记录都到了确认，replica就可以安全地从message log中删除之前的checkpoint。
高低水位
PBFT中的高低水位机制指的是一对用来控制request序号的区间上下界的变量。primary为request指定的序号n必须在 (low water mark, high water mark) 之间，其他backups在接收到消息后都要检查序号n是否满足这一范围。PBFT采用这种机制，一方面是为了防止恶意的primary故意选择非常大的序号n来穷尽序号空间，另一方面是为了控制集群处理requests的吞吐量。如果replica接收到的request序号高于high water mark，那么replica会等待，直到high water mark增长为止。
PBFT建议设置high water mark = low water mark + k，k是固定值。低水位low water mark等于上一个stable checkpoint对应的request序号。这也意味着，每产生新的stable checkpoint，高水位和低水位都会“上涨”。
view change
PBFT的view change协议能在primary fail的情况下，集群自动重新推举出新primary，确保算法的存活性。
在一次视图内部，每个backup都维护了自己的计时器timer，计时器记录着该backup从接收到request到开始执行request的等待时间。一旦计时器超时，backup就可以认为primary可能出问题，因此触发view-change事件，停止收发pre-prepare、prepare、commit消息，向所有replicas广播view-change消息 ${\langle VIEW-CHANGE, v+1, n, C, P, i \rangle}_{\sigma_i}$ 。
- VIEW-CHANGE消息标识符
- 新视图标识符v+1
- 上一个stable checkpoint对应的request标识符n
- C是 $2f+1$ 个checkpoint消息的集合，证明上一个stable checkpoint的有效性
- P是a set of prepared requests at replica i with a sequence number higher than n
- 该replica的标识符i
- replica i对以上内容的摘要的签名
当新视图v+1下的的新primary收到了来自 $2f$ 个其他replicas发送过来的view-change消息后，向所有replicas广播new-view消息 ${\langle NEW-VIEW, v+1, V, O \rangle}_{\sigma_p}$
- NEW-VIEW消息标识符
- 新视图标识符v+1
- V是新primary收到的view-change消息的集合
- 集合O中的计算比较复杂
- 从集合V中确定last stable checkpoint对应的request的标识符，记为min-s
- 从集合V中确定prepared requests中最大的序号，记为max-s
- 如果max-s > min-s，那么从集合V中产生一堆新消息 ${\langle PRE-PREPARE, v+1, n, d \rangle}_{\sigma_p}$
- 否则，产生新消息 ${\langle PRE-PREPARE, v+1, n, d^{null} \rangle}_{\sigma_p}$
新backups在接收到new-view消息并验证有效后，进入新视图v+1，然后从集合O中取出pre-prepare消息，生成对应的prepare消息并广播。
如果新backups漏掉了一些requests或stable checkpoint，那么它可以从集合V中取出缺失的信息。