PBFT算法
1.前提假设
抱成团1.1系统同步模型
区块链是⼀个典型的分布式系统，⽽分布式系统中如果要研究共识的话，就需要明确系统同步模型。
同步模型分为：
synchrony：节点所发出的消息，在⼀个确定的时间内，肯定会到达⽬标节点；
asynchrony：节点所发出的消息，不⼀定会到达⽬标节点；
partial synchrony：节点所发出的消息，虽然会有⼀定延迟，但消息⼀定会送达；
synchrony是最理想的情况，若分布式系统为⼀个同步系统，共识算法的设计可以简化不少。在同步系统中节点的问题认定就是：超时没收到消息。asynchorny是更贴近现实的模型，但根据FLP impossible原理，但在asynchrony假定下，共识算法不可能同时满⾜safety和liveness。但我们为了设计符合实际应⽤场景的共识算法，⽬前的BFT类共识算法⼤多是基于partial synchrony假定，在PBFT原论⽂中称之为：weak synchrony。
即PBFT假设系统是异步的，⽹络中消息会出现延迟，但不会被⽆限的延迟。
数学家小故事1.1.1safety 和 liveness
① safety：坏的事情永远不会发⽣，也就是共识机制不会产⽣错误的结果，⽐如⼀部分节点返回yes，另⼀部分返回no，在区块链的实际情况下，指的就是不会产⽣区块链分叉。
② liveness：好的事情⼀定会发⽣，也就是系统持续有响应，在区块链的实际情况下，指的是共识机制持续正常运⾏，不会卡住，假如⼀个区块链系统的共识机制卡在了某个位置，那么新的交易是⽆法进⾏回应的，也就是不满⾜liveness。
1.2模型容错类型
PBFT算法假定错误可以是拜占庭类型的，也就是可以容忍任意类型的错误，⽐如节点作恶、说谎等。这跟crash-down类型的错误不⼀样，raft、paxos这类共识算法只允许crash-down的类型错误。节点智能crash但不能产⽣假消息
1.2.1引⼊参数
PBFT容忍⽆效或者恶意节点数：f
系统中总节点数为：n
对于不同的错误类型，保证协议正常⼯作的总节点数如下表
错误类型总节点数n
Byzantine fault3f+1
crash-down fault2f+1
1.2.2防⽌拜占庭类错误总节点的数⽬的推算
①.假设系统中可能存在f个拜占庭结点，系统中有n个节点并且需要根据节点发送过来额消息进⾏判断。
②.为了使共识机制正常运作，在收到n-f个消息的时候，就应该对消息进⾏处理，因为可能有f个节点根本不发送消息。
③.我们根据收到的n-f个消息进⾏判断，判断的原则为⾄少有f+1个节点相同结果，即n-f>f。
④.在收到的n-f个消息中，⽆法确定其中有⽆错误节点过来的消息，其中也可能存在f个假消息。所以n-
f-f>f。
1.3系统建模
由⼀组节点构成状态机复制系统，⼀个节点作为主节点（primary），其他节点作为备份节点（back-ups）。轮到某个节点作为主节点时，这称为系统的⼀个view（视图）。当节点出了问题，就需要进⾏view的更新，切换到下⼀个节点担任主节点。主节点更替不需要选举的过程，⽽是采⽤round-robin⽅式。
当系统的主节点接收到client（客户）发送来的请求，并产⽣pre-prepare消息，进⼊共识流程。
我们需要系统满⾜以下条件：
最新dj
1.deterministic（确定性）：在⼀个给定状态上的操作，产⽣⼀样的执⾏结果。
2.起点⼀致性：保证每个节点都有相同的起始状态
要保证non-fault节点对于执⾏请求的全局顺序达成⼀致。
2.共识机制流程
正常状态下的共识机制如下图所⽰。
共识机制发挥作⽤的三个阶段(pre-prepare、prepare、commit)
其中pre-prepare阶段和prepare阶段确保了在同⼀个view下，正常节点对于消息m达成了全局⼀致的的顺序，使⽤order<v，m，n>来表⽰，在view = v下，正常节点都会对消息m，确认⼀个序号n。接下来的commit过程，配合上viewchange的设计（主节点可能会发⽣故障），实现了view的切换，也保证了对于m的的全局⼀致顺序，即order<v+1,m,n>，视图切换到v+1，依然会对消息m，确认序号n。
以下会将分别介绍五个阶段
2.1 request
客户端c向primary节点发送请求。消息格式为<REQUST,o,t,c>。o为请求的具体操作，t为请求时客户端追加的时间戳，c为客户端标识。REQUST：包含消息内容m，消息摘要d(m)。客户端对于请求进⾏签名
2.2 pre-prepare
①primary节点收到客户端的请求，进⾏校验客户端请求消息签名，⾮法请求则予以丢弃。正常则进⼊
②primary节点收到请求m，将请求m⼴播给其他节点，并给请求m分配⼀个序号n，并⼴播给其他节点。⼴播后消息会存在本地的lo中。
pre-prepare阶段的消息格式，其中v表⽰当前view的编号，n为表⽰给m分配的序号，d为客户端消息摘
要，m为消息内容。<PRE-PREPARE, v, n, d>为主节点签名。
③当back-up节点i节点收到主节点发来的pre-prepare消息时，会做以下⼏项验证操作：
五月天香蕉
1.验证主节点发来的消息签名。
2.当前副本节点没有收到了⼀条在同⼀v下并且编号也是n，但是签名不同的PRE-PREPARE信息。
3.收到的消息序号n，在当前接收窗⼝内<h,H>。
4.d与m的摘要是否⼀致。
若以上全部通过，则接受该消息，之后进⼊prepare阶段。该节点会⼴播（向所有节点包括primary节点⼴播）prepare消息。之后将消息存⼊⾃⼰的log中。
2.3 prepare
节点收到prepare消息后，会验证签名并检查是否为当前view的消息，同时检查消息序号n是否在当前的接收窗⼝内，验证通过则接受该消息，保存到⾃⼰的log中。
当节点满⾜以下3点时表明节点达成了prepared状态，记为prepared（m,v,n,i）
1.在log中存在消息m
2.在log中存在m的pre-prepare消息，pre-prepare（m,v,n）
3.在log中存在2f个来⾃其他节点的prepare消息，prepare（m,v,n,i）
⾄此，可以确保view在不发⽣切换的情况下，对于消息m有全局⼀致的顺序。此外记录pre-prepare和prepare消息到log中，⽤于View Change过程中恢复未完成的请求操作。
也就是说在view不变的情况下：
油画棒作品1.⼀个正常节点i，不能对两个及两个以上的不同消息，达成相同序号n的prepared状态。也就是不能同时存在prepared（m,v,n,i）和prepared(m',v,n,i)
2.两个正常节点i、j，必须对相同的消息m达成相同序号n的prepared状态。
prepared状态⼗分重要，其涉及到view转换时，为了保证view切换前后的safety特性，需要将上⼀轮的view的信息传递到新的view。在pbft中就是将prepared状态信息传递到新的view。即新的view中需要在上⼀轮view的prepared信息基础之上，继续进⾏共识。
达成prepared状态后，节点会⼴播commit消息<COMMIT,v,n,d,i>i.
2.4 commit
当节点接收commit消息后，会进⾏⼀下⼏步验证：
1.验证其他节点发来的消息签名。
喝红酒有什么好处2.当前副本节点没有收到了⼀条在同⼀v下并且编号也是n，但是签名不同的commit信息。
3.收到的消息序号n，在当前接收窗⼝内<h,H>。
rf射频4.d与m的摘要是否⼀致。
当节点i满⾜：
达成了prepared（m,v,n,i）状态，并且收到了2f+1个commit（v,n,d,i）消息，则该节点达成了commit-local（m,v,n,i）状态。
达成commit-local状态之后，节点对于消息m就有了⼀个全局⼀致的顺序，可以执⾏reply to客户端了。
其中commit-local状态说明有2f+1个节点达成了prepared状态。其中需要记录其他节点发来的commit消息到log中。
2.5 relpy
节点达到commit-local后运⾏客户端的请求操作o，并返回<REPLY, v, t, c, i, r>给客户端，r：是请求操作结果，客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全⽹共识，否则客户端需要判断是否重新发送请求给主节点。
3.垃圾回收
好听的古风
在以上算法流程中，为了确保在view change的过程中，能够恢复先前的请求，每⼀个副本节点都记录⼀些消息到本地的log中，当执⾏请求后back-up节点需要把之前该请求的消息清楚掉。最简单的做法是在reply消息后，再执⾏⼀次当前状态的共识同步，但这样会消耗很多资源，因此可以在执⾏完多条请求K条，后执⾏⼀次状态同步。这个状态同步消息就是checkpoint消息。
back-up节点i发送<CheckPoint,n,d,i>给其他节点，n是当前节点所保留的最后⼀个视图的请求编号，d是当前状态的⼀个摘要，该checkpoint消息记录到log中。如果back-up节点i收到了2f+1个验证过的checkpoint消息，则清楚先前⽇志中的消息，并以n作为当前的stable checkpoint。
实际上当副本节点i向其他节点发出checkpoint消息后，其他节点还没有完成K条请求，所以并不⽴即对节点i的请求作出响应，它还会按⾃⼰的节奏向前⾏进，但此时发出的checkpoint并未形成stable，为了防⽌节点i的处理请求过快，设置⼀个上⽂提到的⾼低⽔位区间[h,H]来解决这个问题。低⽔位h等于上⼀个stable checkpoint的编号，⾼⽔位H=h+L，L为我们指定的数值，等于checkpoint周期处理请
求数K 的整数倍，⽐如L=2K。当节点i处理请求超过H时，就会停⽌脚步，等待stable checkpoint发⽣变化，再继续前进。
以上机制类似于计算机⽹络中的滑动窗⼝机制。
4.视图切换（view change）
若primary节点作恶，它可能会给不同的请求编上相同的序号，活不分配序号，或让相邻序号不连续，back-up节点应当有义务来主动核实这些序号的合法性。若primary节点离线或者作恶，客户端设置超时机制，若超时，客会向所有back-up节点⼴播请求消息。back-up节点检测出primary节点作恶或离线，发起view change协议。
back-up节点向其他节点⼴播<VIEW-CHANGE,v+1,n,C,P,i>消息，
n：为最新的stable checkpoint的编号
C：对应于n的check-point 2f+1个CHECKPOINT消息集合
P: ⼀个组成的集合,m表⽰消息，m的序号是⼤于n的，表⽰序号为m的达成prepared状态的消息集合。内容包含关于m 的1个pre-prepare消息和2f条prepare消息集合。
i：节点id
当主节点p = v+1 mod |R| 收到2f个有效的VIEW-CHANGE消息后，向其他节点⼴播<NEW-VIEW,v+1,V,O>消息，V为有效的VIEW-CHANGE消息集合。O是主节点重新发起的未经完成的PRE-PERPARE消息集合。PER-PREARE消息集合的选取规则：
1.选取V中最⼩的stable checkpoint编号min-s，选取V中prepare消息的最⼤编号max-s。
2.在min-s和max-s之间，如果存在P消息集合，则创建<<PRE-PREPARE，v+1，n，d>，m>消息。否则创建⼀个空的PRE-PREPARE消息，即：<<PRE-PREPARE，v+1，n，d（null）>，m（null）>，m（null）为空消息，d（null）空消息摘要。
back-up节点收到primary节点的NEW-VIEW消息，验证有效性，若通过，则进⼊view = v+1，并开始O中PRE-PREPARE消息处理流程。
