一开始接触区块链技术，只是出于工程问题的需要，结果后来学术问题也要走这个方向了。机缘巧合定了共识问题为现在的研究方向，主要考虑大网络中的共识，也就是有关区块链扩容的部分。后续我应该也希望好好写一些区块链的扩容问题的专题。但总之，万变不离其宗，实用拜占庭容错共识算法我想一定是共识领域里逃不开的一篇文章。

1. 介绍

research gap

  1. 现有的算法主要是基于同步网络的假设
  2. 现有的算法在不太实用slow（之前的bft共识的通信复杂度大概在指数量级，根本没法用）

本文的贡献
在部分异步模型的假设下，提出一种兼具安全性和活性的共识算法/状态复制算法，容错率为1/3，通信复杂度降到多项式级（一般过程为平方阶视图切换为立方阶）。

2. 系统模型

· asynchronous distributed system 系统假设为异步分布式的，通过网络传输的消息可能丢失、延迟、重复或者乱序。
· Byzantine failure model 节点的失效必须是独立发生，互相之间没有影响。
· cryptographic techniques 用了一些密码学方面的技术，防止欺骗攻击和重播攻击，以及检测被破坏的消息。
· limit adversary 控制拜占庭节点的敌手很强大，可以操纵多个失效节点、延迟通讯、甚至延迟正确节点，但是不能无限期地延迟正确的节点，不能破解加密算法。

3. 服务属性

本文的算法是用于实现具有确定性的副本复制服务（一个状态+多个操作），假设不超过 ⌊ n−13⌋\lfloor\frac{n-1}{3}\rfloor ⌊3n−1​⌋ 节点故障的情况下，同时满足安全性和活性。

安全性 复制服务满足线性一致性，也就是说像中心化系统一样原子化执行操作。至于如果客户端有故障的话，这种安全性保证不属于本算法的讨论范围。
活性 FLP不可能原理告诉我们异步网络下无法同时保证安全性和活性。所以本文也是基于部分异步模型的假设，即所有客户端最终都会收到针对他们请求的回复，只要失效副本的数量不超过 ⌊n − 13⌋\lfloor\frac{n-1}{3}\rfloor⌊3n−1​⌋，并且延迟delay(t)不会无限增长。delay(t)：t 时刻发出的消息到它被目标最终接收的时间间隔，假设发送者持续重传直到消息被接收。

为啥要n要大于等于3f+1？
假设系统中共有n个节点参与共识，其中f个为故障节点。那么为了保证活性，最多只能等n-f个节点回应。这n-f个节点还不一定都是好节点，其中最多可能有f个故障节点，在这种糟糕情况下，等到的好节点为n-f-f=n-2f。为了要达成共识，回应的好节点必须要比故障节点多，所以要让n-2f>f，即n>3f。

这个算法有个局限性，就是它没有考虑信息保密的问题the problem of fault-tolerant privacy，失效的副本有可能将信息泄露给攻击者。

4. 算法部分

PBFT 是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。
所有的副本组成的集合R，用 {0,1,…,|R|-1} 中的每个整数表示每一个副本，其中|R|=3f+1，f为有可能失效的副本的最大个数。
所有的副本在一个视图view中运作。在某个视图中，选择一个副本p作为主节点，其他的副本作为备份节点，视图v是连续编号的整数。主节点由公式 p=v mod |R | 计算得到。

PBFT过程概述

  1. 客户端向主节点发送请求调用服务操作；
  2. 主节点通过广播将请求发送给其他副本；
  3. 所有副本都执行请求（实际上就是后面的两轮投票）并将结果发回客户端 ；
  4. 客户端需要等待 f+1 个不同副本节点发回相同的结果，作为整个操作的最终结果。

和所有的状态机副本复制技术一样，对副本节点有两个要求：确定性（给定状态和参数相同的情况下，操作执行的结果必须相同）；从相同的状态开始。由此，即使故障副本节点存在，对所有的非故障节点请求执行全序一致。这其实也就是共识问题本质要解决的问题。

1）共识的一般流程

request和reply阶段是和客户端交互的阶段，中间三个阶段是共识的重点，本质上是一个三阶段协议three-phase protocol，其中包括两阶段投票。

客户端相关
[request] 客户端 c 通过点对点消息向它自己认为的主节点 p 发送消息 σc _{\sigma_c} <REQUEST,o,t,c>σc​​ 请求执行状态机操作 o， 时间戳 t 是递增的，用来保证客户端请求只会执行一次。

[reply] 副本发给客户端的响应为 σi _{\sigma_i} <REPLY,v,t,c,i,r>σi​​，v 是视图编号，t 是时间戳，i 是副本的编号，r 是请求执行的结果。
这里的v是为了使得客户端能够跟踪视图编号，从而进一步推算出当前主节点的编号。

客户端等待 f+1 个从不同副本得到的相同响应，这样他才能认为r为正确执行的结果。
 为什么客户端等f+1？
 故障节点不超过f个，故f+1个副本一致响应，起码有一个正确的，所以必定能代表结果正确有效。
 怎么验证响应正确？
 签名 σ\sigmaσ正确，同样的时间戳 t 和执行结果 r。

特殊情况
如果客户端没有在有限时间内收到回复，请求将向所有副本节点进行广播：

  • 如果请求已经在副本节点处理过了，副本就向客户端重发一遍执行结果。
  • 如果请求没有在副本节点处理过，该副本节点将把请求转发给主节点。
    · 如果主节点没有将该请求进行广播，那么就有认为主节点失效；
    · 如果有足够多的副本节点认为主节点失效，则会触发一次视图变更。

本文假设客户端会等待上一个请求完成才会发起下一个请求，但是只要能够保证请求顺序，可以允许请求是异步的（即不阻塞，一个线程发请求，另一个线程接响应）。

三阶段协议
每个副本节点的状态包含：
服务状态
已经接受消息的日志
当前的视图编号v
当主节点p收到客户端请求时，除非正在协议的消息数超过设定的最大值，否则主节点将立即启动三阶段协议。（若超过，请求先进入缓冲，之后缓冲请求将作为一个组进行多播，这种优化类似于事务系统中的多播。）
三阶段协议包括[pre-prepare][prepare][commit]三个阶段
[pre-prepare][prepare]的作用：即使（对请求进行排序的）主节点是故障的，同一视图中的请求依旧是全排序的；
[prepare][commit]的作用：确保不同视图之间的请求依旧是全排序的。

[pre-prepare] 主节点p给请求分配一个序列号 n ，然后向所有备份节点发送 <

 σp ,m><_{\sigma_p},m> <<PRE−PREPARE,v,n,d>σp​​,m>，其中 v是视图编号，m是客户端发送的请求消息，d是请求消息m的摘要。
 为什么请求 m 本身是不包含在预准备的消息里面？（注意理解 ‘with m piggybacked to all the backups’)
  实际上三阶段协议中消息仅包括请求的序列号和相关元数据。1. 本阶段的消息后续会作为视图切换阶段 请求已经在视图v中分配序列号n 的证据；2. 将 “对请求进行全排序的协议” 和“广播请求的协议”进行解耦，优化传输效率。
  备份节点接受pre-prepare消息的条件：
  1. 请求的签名正确，用消息摘要d验证过消息m正确；
  2. 当前视图编号是 v；
  3. 该备份节点从未在视图 v 中接受过序号为 n 但是摘要 d 不同的消息 m；
  4. 序列号 n 在水位线h和H之间. (这是为了避免故障的主节点通过设置一个超大的 n 来穷尽编号)
[prepare] 如果一个备份节点接收了pre-prepare消息，那么它进入prepare阶段，即向其他所有副本节点发送  σi _{\sigma_i} <PREPARE,v,n,d,i>σi​​ ，并将pre-prepare和prepare消息写进它自己的日志。
  副本节点接受prepare消息的条件：
  1. 消息签名正确；
  2. 消息的视图编号v与当前副本节点的v相同；
  3. 请求的序列号n在水位线h和H之间。
  准备阶段完成的标志（达成prepared状态）：
 当且仅当节点 i 将以下消息写进日志后, 我们才认为节点进入准备完毕状态, 记做 prepared(m, v, n, i)。
  • 请求 m
  • 视图v中序列号为n的请求m的[pre-prepare]消息
  • 2f 个来自不同备份节点的对应于 [pre-prepare]消息 的 [prepare] 消息(这2f个不包括主节点消息，主节点在prepare阶段不发送消息，但是包括自己的消息) —-如何验证对应关系” /> ≠\ne=m’，则对两种请求投票的两部分f+1个节点不相交，所以起码有2f+2个好节点。但是基于假设，该系统只有3f+1-f=2f+1个好节点。所以推出矛盾！
    [commit] 副本节点i进入prepared状态之后，向其他所有副本节点发送  σi >_{\sigma_i}> <COMMIT,v,n,D(m),i>σi​​>
      副本节点接受commit消息的条件：
    1. 消息签名正确；
    2. 消息的视图编号v与当前副本节点的v相同；
    3. 请求的序列号n在水位线h和H之间。
    其实跟prepare节点要验的东西相同，对于节点来说，这俩阶段的操作没什么大不同，两轮投票罢了。
      确认阶段完成的标志（达成committed状态）：
     如果一个副本节点收到了2f+1条对应于pre-prepare的commit消息，且它进入了prepared状态，那么它会进入 committed-local(m,v,n,i) 状态。
     如果有f+1个给故障的副本节点进入了prepared状态，那么这个系统进入了 committed(m,v,n) 状态。
     · 本质上以上两种状态是统一的，当有一个非故障节点i进入了committed-local状态，实际上也意味着整个系统进入了committed状态。
     · 证明：当一个好节点i进入了committed-local状态，意味着它至少收到了2f+1条commit消息，也就说明了至少有f+1个好节点发送了commit消息。如果一个好节点能发送commit消息，意味着该节点已经进入了prepared状态。所以，至少有f+1个好节点进入了prepared状态，也就至少有2f+1个好节点会达到committed状态。
    当副本节点i达成committed-local(m,v,n,i)状态后就会执行请求m，节点i的状态反映了所有编号小于 n 的请求依次顺序执行。这就确保了所有非故障节点以同样的顺序执行所有请求，这样就保证了算法的正确性safety。
     在完成请求的操作之后，每个副本节点都向客户端发送回复。副本节点会把时间戳比已回复时间戳更小的请求丢弃，以保证请求只会被执行一次。
    注意，该协议不依赖于消息的顺序传递，因此某个副本节点可能乱序确认请求。因为每个副本节点在请求执行之前已经将预准备、准备和确认这三个消息记录到了日志中，这样乱序就不成问题了。（在传统的拜占庭共识问题中，所有正确节点需要达成一致的执行顺序，而具体达成什么样的顺序并不重要。但实际上在实际依赖拜占庭共识的许可链中，节点的利益与该顺序紧密相关。2020年OSDI的最佳论文Byzantine Ordered Consensus without Byzantine Oligarchy恰恰是在讨论这个问题。）
    2）垃圾回收机制
    为了节省存储空间，副本节点需要定期清理日志。以下对于哪些日志可以删除，以及删除了怎么恢复进行说明。
     检查点和稳定检查点
     一些特殊序列号的请求（请求序号可以被某个常数，eg.100 整除的时候）执行之后的状态，我们称之为检查点。其中拥有证明的检查点称为稳定检查点。
     检查点的正确性证明的生成过程：
     当副本节点 i 生成一个检查点后，向其他副本节点广播检查点消息  σi _{\sigma_i} <CHECKPOINT,n,d,i>σi​​ ，这里 n 是最近一个影响状态的请求序号，d 是状态的摘要。每个副本节点都默默地在各自的日志中收集并记录其他节点发过来的检查点消息，直到收到来自 2f+1 个不同副本节点的具有相同序号 n 和摘要 d 的检查点消息。这 2f+1 个消息就是这个检查点的正确性证明。
     具有证明的检查点成为稳定检查点，然后副本节点就可以将所有序号小于等于 n 的预准备、准备和确认消息从日志中删除。同时也可以将之前的检查点和检查点消息一并删除。
     注意，检查点协议还被用于调整水线，最低的标志h等于最新的稳定检查点的序列号，最高的标志H=h+k。k 需要足够大才能使副本不至于为了等待稳定检查点而停顿。加入检查点每 100 个请求产生一次，k 的取值可以是 200。
    3）视图切换机制
    视图切换机制是为了保证PBFT活性存在的，防止备份节点无期限地等待请求的执行，它通过计时器的超时机制触发。
     定时器设置
     我们定义一个备份节点正在等待请求：如果它收到一个有效的请求但还没执行。
     当备份节点收到一个请求，但是定时器还没有运行，那么该备份节点开启定时器；如果备份节点不再等待执行请求，那么该备份节点关闭定时器；如果备份节点开始等待执行其他请求，那么该备份节点会重启定时器。
     备份节点发起视图切换
     如果备份节点i的定时器在视图v中超时了，那么该备份节点将会触发视图切换，进入v+1视图。
     · 该备份节点停止接受不了消息（除了检查点、视图切换和新视图消息），并广播  σi _{\sigma_i} <VIEW−CHANGE,v+1,n,C,P,i>σi​​ 消息给所有副本节点。
    其中，n为最近一个稳定检查点的序请求序列号，C为2f+1个有效检查点证明的集合，P为若干个Pm的集合，Pm为序列号大于n且在该节点i已经达到prepared的消息（包括一个合法的pre-prepare消息，其中不包括对应的客户端消息，2f个不同节点签名的prepare消息，这些消息v、n、D(m)相同）
     新视图的主节点上任
     当视图v+1的主节点收到2f个有效的视图切换消息，它会广播  σP _{\sigma_{P}} <NEW−VIEW,v+1,V,O>σP​​ 给所有其他的副本节点。
    其中，V为包含 主节点收到的有效的视图切换请求的消息、主节点发送(或者应该发送) 的关于切换到v+1视图的消息 的集合；O为包含pre-prepare消息的集合（不包括请求m），集合O的推断如下：
     · 主节点确定从集合V中确定最新的稳定检查点的请求序列号min-s，从集合V中确定所有prepare消息中最大的序列号为max-s；
     · 对于min-s到max-s中的每一个序列号，主节点创建一个新的pre-prepare消息。
    情况1. 对于V中的某个编号为 n 的视图切换消息, 其 P 集合不为空。（实际上就是在视图v中，已经就该请求达成了prepared） 这种情况下, 主节点创建一个新的消息 
     σp _{\sigma_p} <PRE−PREPARE,v+1,n,d>σp​​ 。其中，d是在V中最高视图编号的序列号n下的请求的摘要。
    情况2. 对于V中的某个编号为 n 的视图切换消息, 其 P 集合为空。这种情况下，主节点创界一个新的 pre-prepare 消息 
     σp _{\sigma_p} <PRE−PREPARE,v+1,n,dnull>σp​​ ，代表无操作。
    接下来，主节点把集合O中的消息写入它的日志中。如果min-s比它的最新的稳定检查点的序列号大，那么主节点还要计算序列号为 min-s 的稳定点的证据, 并将其写进日志中, 并对min-s之前的日志进行垃圾回收。至此, 主节点正式进入视图v+1, 可以接受关于v+1的消息。
     备份节点接收新的主节点，进入新视图
    备份节点接受视图切换消息的条件：
    • 签名合法；
    • V 中的 view-change 消息合法；
    • O 合法 (算法类似于主节点创建 O 的算法)
    从节点会将这些消息加入到日志中 (跟上一段的主节点操作一样), 然后对于 O 中的每一个 pre-prepare 消息, 广播对应的 prepare 消息到所有节点, 从此备份节点也进入视图v+1。
    写在最后：
    1. 这篇论文后面还有一些关于PBFT优化的部分，但主体的思想还是以上的部分。
    2. PBFT其实在被用于区块链之后，就不考虑水位线和检查点的问题。我的理解是：日志->链式结构，一方面区块链的设计也不用为并发请求设计水位线，另一方面区块链的不可篡改性导致你直接查本地节点的账本就可以了，而不需要去寻求一些证明。但是垃圾回收机制里，稳定检查点这个思想倒是经常看到，也可称为快照。
    3. 传统BFT共识，其实就是状态机复制技术，所有正确节点需要达成一致的执行顺序，而具体达成什么样的顺序并不重要。但对于区块链的应用场景而言，这个顺序还是挺重要的->拜占庭有序共识。
    4. PBFT的通信复杂度还是比较大的，导致它的可扩展性比较差，一旦很多个节点加入根本就不能用的。从政治上讲，就是小国寡民可以通过一人一票可以保证绝对公平，但是对于大国而言人人投一票效率太差，这时候怎么和“去中心化”进行平衡。此外，一人一票就是最好的吗？其实也未必，比如选择一些优良节点组成委员会，这就是分层的思想。
    5. PBFT的视图切换机制应该是它最复杂的部分，也是大家通常会忽略的部分，几乎有很少的论文去很严格地讨论这一部分。HotStuff应该是关注这一部分优化的最好的，其实它整个设计都非常精妙，非常值得一读。其实我觉得单从共识过程本身研究，HotStuff某种意义上已经优雅到一个尽头了，统一的线性通信复杂度+流水线的设计，还能更美妙吗？
    6. …