拜占庭容错和PBFT共识算法
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 |R| 。 v：view编号，|R|节点个数，p：主节点编号。关于状态机复制算法、view change的意义（主要是防⽌主节点作恶），主节点详见论⽂。
算法概述：
基于拜占庭将军问题，PBFT算法⼀致性的确保主要分为这三个阶段：预准备（pre-prepare）、准备(prepare)和确认(commit)。流程如下图所⽰：
[图⽚上传失败...(image-e3329d-1562488133052)]
⾸先解释⼀下上⾯各个符号表达的意思：
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为有问题的计算机总数。
accent是什么意思
算法具体流程
下⾯所有的校验流程略去对消息内容、签名和⾝份的验证，即已经保证了节点之间消息传播是不可篡改的
请求：
将军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>
2013四级考试时间其中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的消息集合。
rvr
当主节点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左右的。
参考⽂献：
Practical Byzantine Fault Tolerance
科学英语怎么读Miguel Castro and Barbara Liskov Laboratory for Computer Science, Massachutts Institute of Technology, 545 Technology Square, Cambridge, MA 02139 castro,liskov @lcs.mit.edu
