关键字：pBFT、分布式一致性、拜占庭
前言
论文描述了一个新的 replication 算法来解决拜占庭问题，作者相信随着软件行业的不断发展，恶意攻击和软件错误将会越来越多，从而拜占庭将军算法将会变的越来越重要。作者认为之前的拜占庭将军算法过于沉迷于理论证明而忽视了实践可行性，所以提出了一个更加可行的算法--> pBFT：它可以在异步环境下正常工作、一系列的优化来提高响应时间（相较于之前的算法效率提高了一个数量级）。
关于拜占庭将军问题可以参考文章：拜占庭将军问题
算法特点
论文第一章基本上就强调一个事情：跟之前的一系列“妖艳贱货”不一样，它不是花瓶，而是一个更加靠谱、可以实战的算法...不过必要的前置约束还是一个都不能少：
- 节点总数为 3f+1 的情况下，最多允许 f 个恶意节点
- 恶意节点无法伪造其余节点的消息（通过签名算法保证，每个节点都知道其余节点的公钥，用来验证签名是否正确）
- 部分逻辑采用类似同步的通信机制保证算法正确性：比如超时的情况下，client 通过重发的机制来保证系统的 liveness（可以将重发看成同步通信，因为纯异步网络环境下，保证分布式一致性目前是 human beings 的知识盲区）
论文第三章强调了两个属性：safety 和 liveness，下面简单解释一下：
safety：safety 意味着整个系统满足线性一致性（linearizability），也可以理解为：即使存在作恶节点的情况下，其他节点访问系统的 state 得到的依然是统一一致的的结果。比如作恶节点A向一部分节点发送指令a，向另一部分节点发送指令b（假设指令执行最终都是对应着系统 state 的改变），依然不会造成整个系统 state 错乱。
liveness：liveness 意味着 client 最终都能收到它们发出去的 requests 的 replies，也就是上面提到的同步通信，不过基于一个前提下才成立：网络延迟不会无期限增长，因为这样的话就无法模拟同步通信。
算法模型
假设存在R个节点，分别给它们标上标号：{0,...,|R|-1}。同时假设 |R| = 3f + 1，其中 f 即为作恶节点的个数。同时节点也有两种角色：primary 和 replica（也叫backup）。primary 等价于 Raft 中的 leader，replica 等价于 Raft 中的 follower。同一时间只能有一个 primary，其余为 replica。（Raft论文笔记）
另外算法定义了一个属性：view（类似于 Raft 算法中的 term，term 主要应用在 leader 切换），view 可以看做是一个连续增长的数字，每条消息都会携带当前的 view 值，当 primary 有问题时（超时或者被其余节点发现为作恶节点时），会发生 view change，切换成功后将 view 值 +1，而且算法规定：当前的 primary 由 view 值来确定，规则是 p = v mod |R|，即当前 view 值对 R 取模，值为当前 primary 的下标。
算法粗浅的流程：
1. client 向 primary 发送一个 request
2. primary 将这个 request 广播给其余的 replicas
3. replicas 执行这个 request 并且将 reply 直接回复给 client
4. client 等待 replies，如果收到 f+1 个 reply 都是同一个结果的话，那么 client 便会认可这个 reply 为本次 request 的结果（client 可能还会收到一小部分与上面 f+1 个 reply 不一致的 reply，即作恶节点发送的错误 reply）
单看这简单的4步是无法理解为什么这样就能解决拜占庭将军问题，下面进一步描述：
首先我们需要知道 request 的格式是什么样的：<request, o, t, c>，其中 request 代表消息类型，o 即为这个 request 的具体操作，t 为 client 为该消息加的时间戳，c 为 client 的身份 id。首先想一下为什么要有这几个字段：request 的作用是用来区分消息类型 request | reply，c 用来标识是哪个 client 发送的请求，o 是请求内容，这些都好理解，那 t 是用来干啥的？t 的作用是为了保证可以全局有序的处理这个 client 的请求。
而 reply 的格式是这样的：<reply, v, t, c, i, r>，重复的字段就不再解释了，v 为 view number，i 则是 replica 的标识，表明这个消息是哪个 replica 回复的，r 即为回复的结果。
细心地人可能想到了，client 会首先给 primary 发消息，然后由 primary 广播，那 client 是怎么知道哪个是 primary？答案就在 reply 里面，reply 里面的 view number 可以计算出 primary 的下标。（思考：初始状态，没有任何 reply 消息的前提下怎么确认 primary？）
同样的，刚才说到 reply 里面的 i 值用来标识 replica，但是假如 reply 是由作恶节点伪造 i 发送的呢，如何发现？答案：节点互相知道对方的公钥，可以通过验签的方式来保证作恶节点无法伪造成别的节点。
client 等待 f+1 个相同的 replies 后（相同的 t 和 r）便会认为这个 r 的结果是可信有效的。why？后面再说吧，先记住这个结论。
还有一个问题需要处理：假如 client 没有及时的收到足够多的 reply 消息怎么办？比如存在一种情况：primary 作恶，它故意不广播接收到的 request 是完全有可能的。解决方案：如果 client 等不及了，它就会自己亲自上，把 request 广播给所有的 replicas，如果某个 replica 已经处理过这个 request 了，这个 replica 会直接返回上次的处理结果，避免多次执行。
除此之外，replica 也会将这个消息发送给 primary，如果 primary 依然没有将这个 request 再次广播的话，replica 有理由怀疑这个 primary 有问题，会主动发起一个 view change，如果发起的 replica 足够多，那么这个 primary 会被投下去。
f+1
下面我们重点关注一下为什么收到 f+1 个相同的 reply，就可以认为该 request 已被处理并达成共识。
pBFT 整体看起来是一个三阶段提交（两/三阶段提交），primary 收到 request 之后便开启了三阶段提交的流程。
primary 在接收到 request 后，将一个 pre-prepare 消息广播给所有 replica，pre-prepare 的消息格式：<<pre-prepare, v, n, d>p', m>，v 代表了当前的 view number，n 是 sequence number，可以简单理解是给消息分配的唯一编号（sequence number 应该是全局有序的，但是不确定，知道的可以留言回复），排序用的，d 是 m 的摘要。
这里注意一点：m 的格式即为内部尖括号所示，里面的尖括号是 primary 对 m 的签名，用 p' 表示，pre-prepare 并没有携带 request 的具体内容，这是因为论文表示 request 可以通过另外的端口单独发送，尽量减小三阶段提交中消息格式的大小来提高通信效率（这段不重要）。
满足以下条件后，replica 才会接受这个 pre-prepare 消息：
1. 验证签名是否正确，pre-prepare 格式是否正确，m 的摘要 d 是否正确
2. 该消息的 view 是 v
3. 节点目前还未接收到 view 为 v，sequence number 也为 n，但是摘要不一样的 pre-prepare
4. sequence number 没有超过最大值 H 和最小值 h（为了防止 primary 恶意发送超大数字而耗尽 sequence number，H 和 h 的取值范围暂时忽略）
如果 replica 接受该 pre-prepare 后进入 prepare 阶段，它将会对外广播 prepare(m, v, n, i)，同时当一个 replica 收到 2f 个 prepare 与自己的 pre-prepare 匹配时，对于该节点来说，它认为 prepare 消息达成共识，开始进入 commit 阶段。
考虑一下为什么收到 2f 个匹配消息之后就可以进入 commit 阶段？反证法：收到 2f 个 prepare(m, v, n, i) 消息意味着至少 f+1 个非作恶节点认可了这个消息（包括它自身，假设存在 f 个作恶节点），假如存在另一个 prepare(m', v, n, i) 也能达成共识的话，说明存在另外 f+1 个非作恶节点认可了后面这个 prepare，但是非作恶节点总数为 2f+1 个，两个集合中必然存在交集，而一个正常的节点是不会发出两个不同的消息的，所以这种事情不会发生。
另考虑一下：节点收到 2f 个匹配的 prepare 后能不能认为 request 达成共识了？答案：当然是不可以，要不然 commit 阶段存在的意义是啥。。。某个节点收到 2f 个 prepare 消息并不代表所有正常节点都收到 2f 个匹配的 prepare，因此需要进一步确认至少 f+1 个正常节点都收到 2f 个 prepare 消息才可以认为 request 达成了共识，即 commit 阶段所做的事情。
节点进入 commit 阶段后会广播 commit(m, v, n, i) 消息，当某个节点收到 2f 个匹配的 commit 消息后，意味着除了它自己，至少有 f 个正常的节点已经认可了这个 request，满足上面提到的超过半数的正常节点达成共识，节点此时可以执行 commit 操作，至此以这个节点的视角来看，本次三阶段提交执行完毕。
而以client的视角来看，它需要等待 f+1 个节点向他返回相同的 reply 后便会认可这个 request 处理成功。三阶段提交中 prepare 和 commit 阶段都需要收到 2f+1 个相同的消息，而 client 最终只需收到 f+1 相同的消息即可，思考一下原因。
pBFT 算法的本质：1.通过一系列操作屏蔽作恶节点对正常节点的影响。2. 在不受恶意节点干扰的情况下，让超过50%的正常节点达成共识，然后同时保证其余的正常节点少数服从多数，遵循 major 的共识。
收到 f+1 个相同的 reply 意味着其中肯定含有一个 reply 是正常节点返回的，而一个正常节点能够完成 commit 阶段并且发送 reply 的前提是：至少有个 f+1 正常节点已经认可了这个 request。
view change
上面的描述的是共识成功的流程，但是随着头发越来越少，慢慢发现猿类们大部分时间并不是在写正常的业务流程，而是在处理异常边界情况。
假设 primary 是个作恶节点，它向 1/3 个正常节点发送指令A，向另外 1/3 发送指令B，其余的发送指令C，会有什么后果？肯定是正常节点永远都无法达成共识。
所以 pBFT 引入了超时机制保证节点不会无期限的等待某个 request 达成共识，如果规定的时间内 request 无法达成共识的话，该节点会发起 view change，发起的节点多了，自然就把 primary 投下去了。
具体怎么投，并且保证之前正在进行的消息能够继续正确的被处理是下面要讲的内容，不过在讲这个之前还需要先介绍一下 checkpoint。
checkpoint
pBFT 为了保证可靠性，三阶段中所有认可的消息都需要持久化到 log 中，log 会越来越大，那就需要裁减，checkpoint 就闪亮登场了。不太想写了，一切从简吧....简单理解：对系统状态定时生成 checkpoint<n, d, i>，n 是 sequence number，d 是摘要。生成规则自定义：比如每100个 request 生成一个 checkpoint，也就意味着会有很多 checkpoint，所以还需要对 checkpoint 进行清理。
节点每生成一个 checkpoint 都会将该 checkpoint 广播出去，跟上述描述的类似，节点如果收到了同样的 2f+1 个 checkpoint 的话，说明这个 checkpoint 达成共识，即标记该 checkpoint 是一个 stable checkpoint，并且将之前的 checkpoint 和该 checkpoint 之前的 log 都删除（通过 sequence number 来区别 log 和 checkpoint 的先后顺序，所以笔者认为 sequence number 是全局有序的）。
下面继续讲 view change，当节点对 primary 有那么一丝丝怀疑的时候会发起 view change request：<view-change, v+1, n, C, P, i>
i：replica 的下标
n：replica i 目前 stable checkpoint（暂称：s）的 sequence number
C：验证 checkpoint s 正确性的 2f+1 个checkpoint消息（checkpoint验证的时候接收到的消息）
P：P 比较讲究，比较长。它是一个集合，它的每个元素可以认为是一个对象，比如 Pm 对应就是 request m 相关的信息，Pm 中记录的是：一个 pre-prepare 消息、2f 个验证该 pre-prepare 的 prepare 消息。且只有 sequence number 大于 n 的 request 才能被记录在 P 中。换句话说：P 中记录的是 sequence number 大于 n 的且 prepare 阶段验证通过的 request。（这些 request 需要继续执行来决定是否可以被共识，思考一下：为啥满足接收到 2f 个 prepare 的消息才有资格放在 P 中？）
当新的 primary 收到了 2f 个 v+1 的 view change request 时，它会广播一个<new-view, v+1, V, O>消息，
V：这个是大写，它包含的是：刚才说到的 (2f 个 view change request) + (它自己的 view change request)，也就是 2f+1 个 request
O：O 也比较讲究，首先新的 primary 先从刚才 2f 个 view change requests 中的 checkpoint 中挑出来最小的 sequence number --> min-s，然后再从 view change requests 中的 P 集合中挑出来最大的 sequence number --> max-s。然后 primary 给每一个在 min-s 和 max-s 之间的 request，在 v+1 的视图下创建一个新的 pre-prepare，但是 P 集合在 min-s 和 max-s 之间的不一定所有高度都会有 request，此时又有两种情况：1. 对于存在于这两个高度之间的 request，选取 v 值最大的 request（因为可同一个 sequence number 可能存在多个 request），直接对其创建<pre-prepare, v+1, n, d>消息。2. 对于不存在的，直接创建一个<pre-prepare, v+1, n, d-null>消息。
注：有点绕，看不懂的多看看论文，疑问：为什么一定要将 min-s 和 max-s 之间的 request 用 null 补全，不补全会有什么后果？
replicas 收到 primary 的广播后会用同样的方式验证一下这个 request 的正确性，更新视图至 v+1，然后为 min-s 和 max-s 之间的 request 广播 prepare 消息，这样确保在 v+1 视图下，之前未处理完成的 request 能够被正常处理（因为算法规定 v+1 不应该处理小于该视图的任何 request）。同样 replica 通过保留的信息判断该 request 是否已经处理过，如果已经 replica 已经将该 request 的 reply 回复给 client 的话，replica 会直接跳过这个 request。
上述流程相对比较复杂，论文中给出了推导过程并证明了正确性，后续还介绍了一些优化的细节，并且采用 pBFT 算法实现了一个文件系统，测试表明和传统的文件系统相比性能几乎没有下降。本文略过了很多论文的细节，想要对 pBFT 有更深入了解的话还是建议参看论文。
总结
目前一些公链的共识算法都优先选用 pBFT 或者其变种来加快区块的确认来满足更多对延时要求较高的业务场景。比如 pBFT 在跨链应用中就有着举足轻重的作用，知名度较高的两个跨链项目 cosmos 和 polkadot 共识机制中都有 pBFT 的身影。也有一些公链共识采用 pBFT 和 DPoS 的组合，利用 pBFT 加速区块确认，同时利用 DPoS 来保证区块的最终共识，既保证了时效性，又具备稳定和可靠性。
pBFT 算法提供了一种高效的方式解决了拜占庭将军问题，随着技术的不断普及和融合，除了信息的载体，互联网也有可能成为信任的载体，届时 pBFT 也将会扮演重要的作用。
