PBFT实⽤拜占庭容错算法详解
分布式架构遭遇的问题
分布式架构会遭遇到以下问题：
1、异构环境的分布式架构⾸先可能遇到⽹络传输问题，⽐如数据丢失、延迟、重复、乱序。
2、欺骗攻击和重播攻击
3、操纵多个失效节点，延迟通讯，制造混乱。
具体到区块链世界，存在同样类似的问题：
区块链是⼀个分布式账本系统，参与者通过点对点⽹络连接，所有消息都通过⼴播的形式来 发送。系统中存在两种⾓⾊：普通节点和记账节点。普通节点使⽤系统来进⾏转账、交易等操作，并接受账本中的数据；记账节点负责向全⽹提供记账服务，并维护全局账本。 我们假设在此⽹络中，消息可能会丢失、损坏、延迟、重复发送，并且接受的顺序与发送的 顺序不⼀致。此外，节点的⾏为可以是任意的：可以随时加⼊、退出⽹络，可以丢弃消息、 伪造消息、停⽌⼯作等，还可能发⽣各种⼈为或⾮⼈为的故障。
其实这就是拜占庭将军问题。
实⽤拜占庭容错算法PBFT（Practical Byzantine Fault Tolerance）
为了解决节点故障可能造成对系统的危害，PBFT采⽤了⼀种⽐较简洁的办法。
⾸先借⽤⼀个类⽐（知乎[Devin Zeng]：
PBFT算法要求⾄少要4个参与者，⼀个被选举为军长，3个师长。军长接到总司令命令：你们向前⾏军500公⾥。军长就会给3个师长发命令向前⾏军500公⾥。3个师长收到消息后会执⾏命令，并汇报结果。A师长说我在⾸都以东500公⾥，B师长说我在⾸都以东500公⾥，C 师长说我在⾸都以东250公⾥。军长总结3个师长的汇报，发现⾸都以东500公⾥占多数（2票>1票），所以就会忽略C师长的汇报结果，给总司令汇报说，好了，现在部队是在⾸都以东500公⾥了。这就是PBFT算法。
PBFT算法的核⼼理论是n>=3f+1
n是系统中的总节点数，f是允许出现故障的节点数。换句话说，如果这个系统允许出现f个故障，那么这个系统必须包括n个节点，才能解决故障。
5个概念
client：请求（request）⾃愿者，上例中指总司令。
replica：副本，所有参与提供服务的节点，上例指军长和师长
primary：承担起提供服务主要职责的节点，上例是军长
backup：其他副本，但相对于primary⾓⾊。上例指师长。
view：处于存在primary-bakup场景中的相对稳定的关系，叫视图。
如果primary出现故障，这种相对稳定的视图关系就会转变（transit）。⽐如军长叛逃（出现故障，对外表现为不可见），那么某个师长就会转变成为军长。系统也就从视图a转变为视图b（a,b均为整数）。
4个阶段
request：client请求阶段（有些说法不包括这个阶段）。总司令给军长下命令。
预准备（pre-prepare）：主节点向所有backup节点发送预准备消息，其中包括当前视图编号，client请求以及请求摘要，签名是否⼀致等。军长对各位师长说：现在是我的时代（视图），我是军长，你们都是师长，所有⼈都得听我的。现在公布总司令的命令（先说说总司令是谁，命令摘要）。
准备(prepare)：包括主节点在内的所有副本节点在收到准备消息之后，对消息的签名是否正确，视图编号是否⼀致，以及消息序号是否满⾜⽔线限制这三个条件进⾏验证，如果验证通过则把这个准备消息写⼊消息⽇志中。backup节点核对签名信息，⽐如其他师长听到总司令的名字，说对，总司令就是这个⼈没错，然后核对总司令曾经任命这家伙当军长，好吧，那就听他的吧。
确认(commit)：每个副本接受确认消息的条件是：1）签名正确；2）消息的视图编号与节点的当前视图编号⼀致；3）消息的序号n满⾜⽔线条件，在h和H之间。⼀旦确认消息的接受条件满⾜了，则该副本节点将确认消息写⼊消息⽇志中。每个师长都经过上述核对，确认⽆误，就会接受命令进⾏执⾏。
回复（reply）：结果反馈。
预准备和准备两个阶段⽤来确保同⼀个视图中请求发送的时序性（即使对请求进⾏排序的主节点失效了），准备和确认两个阶段⽤来确保在不同的视图之间的确认请求是严格排序的。
⾮主节点失效的例⼦
下图展⽰了在没有发⽣主节点失效的情况下算法的正常执⾏流程，其中副本0是主节点，副本3是失效节点，⽽C是客户端。通过这个例⼦，也帮助我们理解n>=3f+1的算法。
从发起请求到最终收到reply，中间的共识过程需要经过3个阶段：
pre-prepare：primary收到请求，⽣成新区块并⼴播
prepare：所有replica收到区块后，⼴播区块验证结果，同时等待接收超过2/3的节点的⼴播
commit：收到2/3的节点⼴播或者超时后，再次发送⼴播，同时再次等待接收超过2/3的节点的⼴播
这⾥的逻辑有点绕：
第⼀次等待超过2/3的节点⼴播，是为了确认“已经有超过2/3的节点收到区块了”。但是这只是你⾃⼰知道，别⼈并不知道啊，因此需要再发送⼀次⼴播，告诉别的节点“我已经确认有超过2/3的节点收到区块啦”。⽽第⼆次等待超过2/3的节点⼴播，则是为了确认“已经有超过2/3的节点确认(有超过2/3的节点收到区块啦)”，此时说明已经达成共识，可以把该区块写到链上了。
PBFT流程
简单再回顾⼀下：
1、总司令给军长下命令向前⾏军500公⾥；
2、军长将消息（不只有命令）传递给所有师长；
3、1号2号师长⼜把消息传给其他师长，3号师长处于叛逃状态；
4、军长再次询问各位师长是否同意执⾏命令。
4、所有军官（包括军长和师长）向总司令汇报结果。
PBFT状态机
这个原⽂是没有图的，只能根据⽂字描述⾃⾏理解，还是挺复杂的：
图中的圆⾓矩形表⽰状态，六边形表⽰等待阶段，绿线代表正常流程，红线代表异常流程。下⾯⼀个⼀个的来介绍：
wait request
即等待请求状态，所有节点初始均处于该状态
primary收到REQUEST消息后，会转换到pre-prepare状态
backup收到区块后，会转换到prepare状态
pre-prepare
这个状态是primary专属的，primary⽣成区块并⼴播PRE-PREPARE消息后，转换到prepare状态
prepare
进⼊该状态后，⼴播PREPARE消息，并等待2f+1个节点确认
wait for 2f+1 prepare
如果等到了2f+1个节点确认（accept或reject），转换到commit状态
如果超时，转换到view change状态
commit
进⼊该状态后，⼴播COMMIT消息，并等待2f+1个节点确认
wait for 2f+1 commit
如果等到了2f+1个节点确认（accept或reject），发送REPLY消息，转换回wait request状态
如果超时，转换到view change状态
view change
进⼊该状态后，⼴播v+1的VIEW-CHNAGE消息，等待接收2f个节点的VIEW-CHANGE消息
wait for 2f view change
这个状态⽐较复杂，可以分为以下4种情形：
收到了2f个节点的VIEW-CHANGE消息，并且是新的primary，⼴播NEW-VIEW消息，并转换到pre-prepare状态
收到了2f个节点的VIEW-CHANGE消息，并且是backup，转换到wait request状态
接收超时，重新回到view change状态，⼴播v+2的VIEW-CHANGE消息
在收到2f个节点的VIEW-CHANGE消息之前，收到了NEW-VIEW消息，则转换到prepare状态
需要注意的是，如果接收到了NEW-VIEW消息，则表⽰当前view未达成共识，需要在更⾼层的view上完成共识。因此，不管当前处于哪个阶段，都需要重新回到prepare状态。
数据结构
接下来就是介绍⼀下相关的数据结构了，主要是状态和消息。
State
节点的状态主要包含三部分：
世界状态（即最新区块信息）
消息⽇志
当前view
Three Pha Protocol
这⾥列出了三阶段协议相关的消息结构，其中PRE-PREPARE消息包含新⽣成的区块，其他消息则主要包含⼀些id、quence number、区块内容摘要和签名等信息。
VIEW-CHANGE
VIEW-CHANGE消息包含的内容⽐较多：
⾸先需要基于⼀个稳定的checkpoint，因此需要包含2f+1个CHECKPOINT消息以证明该checkpoint是有效的。
然后，在该checkpoint之上的所有quence number，都需要打包对应的PRE-PREPARE消息以及2f个PREPARE消息。
NEW-VIEW
NEW-VIEW消息⾸先需要包含2f+1个VIEW-CHANGE消息，以证明确实有超过2/3的节点同意在更⾼的view上进⾏新⼀轮共识。
然后，根据收到的所有VIEW-CHANGE消息中的checkpoint信息，找出最⼩值min_s和最⼤值max_s，打包该区间内的每⼀个quence number对应的PRE-PREPARE消息。
特别的，为了减少重复验证，如果在某个quence number上从未进⾏过view change（即第⼀轮就达成了共识），则PRE-PREPARE中包含⼀个特殊的null请求的摘要信息。
具体逻辑参见下图：
总结
特征/优点：
通信复杂度O(n^2)。
⾸次提出在异步⽹络环境下使⽤状态机副本复制协议，该算法可以⼯作在异步环境中，并且通过优化在早期算法的基础上把响应性能提升了⼀个数量级以上。作者使⽤这个算法实现了拜占庭容错的⽹络⽂件系统（NFS），性能测试证明了该系统仅⽐⽆副本复制的标准NFS慢了3%。
使⽤了加密技术来防⽌欺骗攻击和重播攻击，以及检测被破坏的消息。消息包含了公钥签名（其实就是RSA算法）、消息验证编码（MAC）和⽆碰撞哈希函数⽣成的消息摘要（message digest）。
适⽤于permissioned systems (联盟链/私有链)，能容纳故障节点，也能容纳作恶节点。要求所有节点数量⾄少为3f+1（f为作恶/故障不回应节点的数量），这样才能保证在异步系统中提供安全性和活性。
解决了原始拜占庭容错(BFT)算法效率不⾼的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应⽤中变
