PBFT共识算法

实用的拜占庭容错算法 BFT 是区块链共识算法中，需要解决的一个核心问题。比特币的POW，eos的dpos，以及共识算法pos，这些公链算法，解决的是共识节点众多情况下的bft问题。

bft问题

拜占庭将军问题。也称为拜占庭容错。用来描述分布式系统一致性问题。

背景如下：拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。这10支军队在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队（一半以上）同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵骑马相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们才能保证有多于6支军队在同一时间一起发起进攻，从而赢取战斗？

单从上面的说明可能无法理解这个问题的复杂性，我们来简单分析一下：

　　先看在没有叛徒情况下，假如一个将军A提一个进攻提议（如：明日下午1点进攻，你愿意加入吗？）由通信兵通信分别告诉其他的将军，如果幸运中的幸运，他收到了其他6位将军以上的同意，发起进攻。如果不幸，其他的将军也在此时发出不同的进攻提议（如：明日下午2点、3点进攻，你愿意加入吗？），由于时间上的差异，不同的将军收到（并认可）的进攻提议可能是不一样的，这是可能出现A提议有3个支持者，B提议有4个支持者，C提议有2个支持者等等。

　　再加一点复杂性，在有叛徒情况下，一个叛徒会向不同的将军发出不同的进攻提议（通知A明日下午1点进攻，通知B明日下午2点进攻等等），一个叛徒也会可能同意多个进攻提议（即同意下午1点进攻又同意下午2点进攻）。

　　叛徒发送前后不一致的进攻提议，被称为“拜占庭错误”，而能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」，简称为BFT。

pbft算法

使用密码学算法保证节点之间的消息传送是不可篡改的，通过下面的算法我们可以保证A将军收到B将军发来的消息确实是B将军本人的真实请求。

我们采用的是哈希函数（散列算法）SHA256 – 从数据（byte）值中创建独一无二的hash值，并压缩成摘要，将数据格式固定下来。通过这个摘要与个人私钥生成Digital Signature 和个人公钥Public-key certificate，接收方验证签名和摘要，如果是通过验证，即证明摘要内容没有经过篡改。

pbft容忍无效或者恶意节点数量 e 。为了保证整个系统可以正常运作，需要有2f+1个正常节点，系统的总结点数为：3f+1。即pbft算法容忍小于1/3的恶意或者无效节点。原因见节点作恶的极端情况

pbft是一种状态机副本复制算法，所有副本在一个view轮换过程中操作，哪些是主节点（进攻的提议者的大将军们，轮流当）通过view中其他节点（其他将军）赋予的编号和节点数集合来确定，即：主节点p=v mod

。 v：view编号，

节点个数，p：主节点编号。关于状态机复制算法、view change的意义（主要是防止主节点作恶），主节点详见论文。

算法概述：

基于拜占庭将军问题，PBFT算法一致性的确保主要分为这三个阶段：预准备（pre-prepare）、准备(prepare)和确认(commit)。流程如下图所示：

2018_08_22_17_25_37

首先解释一下上面各个符号表达的意思：

C表示客户端；
0，1，2，3表示4个节点；
0在这里为主节点，1，2，3为副本节点；（注意，这里其他节点也可以作为主节点，若0发生错误只能由服务器监测。如果服务器在一段时间内不能完成客户端的请求，则会触发视图更换协议，将其他副本节点换为主节点）
3为故障节点；

下面结合上图，详细说一下PBFT的步骤：

Request：请求端C发送请求到主节点，这里是0节点；
Pre-Prepare：节点0收到C的请求后进行广播，扩散至123；
Prepare：123节点收到后记录并再次广播，1->023，2->013，3因为宕机无法广播（这一步是为了防止主节点作恶，给不同副本节点发送不同的请求，所以所有副本节点都进行一次广播）
Commit：0123节点在Prepare阶段，若收到超过一定数量（>2F，实际使用中，F为可以容忍的拜占庭节点个数）的相同请求，则进入Commit阶段，广播Commit请求；
Reply：0123节点在Commit阶段，若其中有一个收到超过一定数量（2F+1）的相同请求，则对C进行反馈；

根据上述流程，在 N ≥ 3F + 1 的情況下一致性是可能解決，N为总计算机数，F为有问题的计算机总数。

算法具体流程

下面所有的校验流程略去对消息内容、签名和身份的验证，即已经保证了节点之间消息传播是不可篡改的

请求：
- 将军C向主节点发送请求，主节点收到请求。
- 消息格式：
  
  <REQUEST, o, t, c>
  
  o: 请求的具体操作，t: 请求时客户端追加的时间戳，c：客户端标识。REQUEST: 包含消息内容m，以及消息摘要d(m)。
主节点收到（客户端发送或者存活的非主节点广播）请求，第一阶段认证准备：pre-prepare
- 验证请求是否非法。
- 如果合法，执行下面操作：
- 对每一个请求分配编号n，每一个请求都有一个编号。然后广播消息给其他副本节点：
  - «PRE-PREPARE, v, n, d>, m>
    
    v：视图编号，d客户端消息摘要，m消息内容。
- n要在某一个区间内的[h,H]。
  - 这是为了确保在view切换过程中，能够恢复之前的请求，具体流程见后头的垃圾回收环节
副本节点收到消息，第二阶段认证准备：prepare

副本节点i收到主节点发来的pre-prepare消息，进行如下校验：
- 副本节点i（自己）是否曾经收到了一条在同一个view下并且编号也是n，但是签名不一样的pre-prepare消息。如果有，这条新的消息就是非法的。
- d、m摘要保持一致，不一致则是非法的。
- n是否在区间[h，H]之间，如果不是，则非法。
  
  非法则丢弃
- 对正确消息的处理：
- 副本节点向其他所有节点（包括主节点和副本节点）发送（广播）一条消息：
  - <PREPARE, v, n, d, i>
    
    其中v, n, d与收到的pre-prepare消息内容一致，i则为副本节点的编号。
  - 并记录pre-prepare、prepare消息到log中，用于view change过程中恢复未完成的请求操作。
对prepare消息的确认和提交 ,第三阶段认证阶段：commit

主节点和副本节点收到prepare消息，进行如下校验：
- 当前副本节点是否已经收到了同一个view下的pre-prepare消息n，没有则非法。
- n是否在区间[h,H]中，不在则非法。
- d是否与当前存储的pre-prepare消息的d一致，不一致则非法。
- 如果副本节点i收到了2f+1个验证通过的prepare消息，则向其他所有节点（包括主节点和副本节点）发送（广播）一条消息：
  - <COMMIT, v, n, d, i>
  - 其中v, n, d与上述PREPARE消息内容相同，i则是自己的标识。
  - 记录commit消息到log记录中，用view change过程中恢复未完成的请求操作，记录其他副本节点发送的prepare消息到log记录中。
对commit消息的回复，第四回复确认阶段（最后）：reply
- 当前副本节点i是否已经收到同一view下的prepare消息n，没有收到的话判定为非法。
- d和m的摘要是否一致，不一致判定为非法。
- n是否在区间[h,H]内，不在的判定为非法。
- 如果副本节点i收到了2f+1个经过上述验证的commit消息，说明当前网络中的大部分节点已经达成共识，运行客户端的请求o，并返回回复消息给客户端。消息格式如下：
  - <REPLY, v, t, c, i, r>，r：是请求操作结果。
  - 客户端如果收到2f+1个相同的reply消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送该请求，请求链上重新进行验证。
  - 同时此时记录其他副本节点发送的commit消息到log中。

垃圾回收环节

上述算法中，比较重要的一个点是view change，为了能恢复之前的请求，每一个副本节点收到消息之后或者发送消息的时候都会记录消息到本地的log记录中。当执行请求后，副本节点需要把之前该请求的记录消息清除掉。最简单的做法是在reply消息后，在执行一次当前状态的共识同步，但是为了节省资源，一般在多条请求K后执行一次状态同步。这个状态同步就是checkpoint消息。

checkpoint详细解释：

为了节省内存，系统需要一种将日志中的无异议消息记录删除的机制。为了保证系统的安全性，副本节点在删除自己的消息日志前，需要确保至少f+1个正常副本节点执行了消息对应的请求，并且可以在视图变更时向其他副本节点证明。另外，如果一些副本节点错过部分消息，但是这些消息已经被所有正常副本节点删除了，这就需要通过传输部分或者全部服务状态实现该副本节点的同步。因此，副本节点同样需要证明状态的正确性。

在每一个操作执行后都生成这样的证明是非常消耗资源的。因此，证明过程只有在请求序号可以被某个常数（比如100）整除的时候才会周期性地进行。我们将这些请求执行后得到的状态称作检查点（checkpoint），并且将具有证明的检查点称作稳定检查点（stable checkpoint）。

流程：

副本节点i发送checkpoint消息给其他节点，消息格式如下：
- <CheckPoint, n, d, i>
- n是当前节点所保留的最后一个视图请求编号，d是对当前状态的一个摘要。
如果副本节点i收到了2f+1个验证过的checkpoint消息，则清除之前日志中的消息，并以收到的n作为当前一个stable checkpoint

上述情况是理想情况，实际上当副本节点i向其他节点发出checkpoint消息之后，其他节点还没有完成K条请求的相互共识，所以不会立即对i的请求作出响应。其他节点会按照自己的处理步骤和顺序，向前行进和共识。但是此时i发出的checkpoint没有形成stable，为了防止i太快，超过自己太多，于是被便会设置一个高水位H=h+L，其中L就是我们指定允许的高度差，等于checkpoint周期处理数K的整数倍，可以设置为L=2K。当副本节点i处理请求超过高水位H时，副本节点即使接受到请求也会视为非法请求。等待stable checkpoint发生变化，再继续向前推进处理。

View Change

如果主节点作恶，它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻请求的序号不连续。备份节点（备份主节点）应当有职责来主动检查这些序号的合法性。如果主节点掉线或者作恶不广播客户端的请求，客户端设置超时机制，超时的话，向所有副本节点广播请求消息。副本节点检测出主节点或者下线，发起view change流程。

流程：

副本节点向其他节点广播消息：
- <view-change, v+1,n,C,P,i>
- n是最新的stable checkpoint的编号，C是2f+1验证过的checkpoint消息集合，P是当前副本节点未完成的请求的pre-prepare和prepare的消息集合。
当主节点p=v+1 mod R 收到2f个有效的view-change消息后，向其他节点广播消息，消息格式如下：
- <new-view,v+1,V,O>
- V是有效的view-change消息的集合。O是主节点重新发起的未完成的pre-prepare消息集合。pre-prepare消息集合的选取规则：
  - 选取V中最小的stable checkpoint编号min-s，选取V中prepare消息的最大编号max-s。
  - 在min-s和max-s之间，如果P消息集合在这个区间，则创建pre-prepare消息并广播：
    - «pre-prepare,v+1,n,d>,m>格式和之前的pre-prepare格式一致
  - 如果不在这个区间，则创建空的pre-prepare:
    - «PRE-PREPARE, v+1, n, d(null)>, m(null)>, m(null)空消息，d(null)空消息摘要。
副本节点收到主节点的new-view消息，验证有效性。有效的话进入v+1消息，并且开始处理O中的pre-prepare消息（即生成prepare消息）

节点作恶的极端情况

我们在上面讲到，当网络中有F台有问题的计算机时，至少需要3F+1台计算机才能保证一致性问题的解决，我们在这里讨论一下原因。

我们可以考虑：由于有F个节点为故障或被攻击的节点，故我们只能从N-F个节点中进行判断。但是由于异步传输，故当收到N-F个消息后，并不能确定后面是否有新的消息。（有可能是目前收到的N-F个节点的消息中存在被攻击的节点发来的消息，而好的节点的消息由于异步传输还没有被收到。）

我们考虑最坏的情况，即剩下F个都是好的节点，收到的中有F个被攻击的节点，故我们需要使得收到的中好节点的数量(N-F)-F大于被攻击节点的数量F，于是有N-2F>F，即N>3F，所以N的最小整数为N=3F+1。

总览：

pbft是需要参与认证的节点进行的。所以一个完整的共识算法包括DPOS+PBFT。其速度是可以达到1500tps左右的。

参考文献：

https://mathpretty.com/9602.html

https://blog.csdn.net/jfkidear/article/details/81275974

Practical Byzantine Fault Tolerance

Miguel Castro and Barbara Liskov Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139 castro,liskov @lcs.mit.edu

https://www.jianshu.com/p/fb5edf031afd 部分论文翻译

PBFT Consensus Algorithm

pbft 容错算法基础