区块链快速⼊门（四）——BFT（拜占庭容错）共识算法⼀、BFT简介
1、拜占庭将军问题简介
拜占庭将军问题（Byzantine Generals Problem）是Leslie Lamport（2013年的图灵奖得主）⽤来为描述分布式系统⼀致性问题（Distributed Connsus）在论⽂中抽象出来⼀个著名的例⼦。
拜占庭将军问题简易的⾮正式描述如下：
拜占庭帝国想要进攻⼀个强⼤的敌⼈，为此派出了10⽀军队去包围这个敌⼈。这个敌⼈虽不⽐拜占庭帝国，但也⾜以抵御5⽀常规拜占庭军队的同时袭击。基于⼀些原因，这10⽀军队不能集合在⼀起单点突破，必须在分开的包围状态下同时攻击。他们任⼀⽀军队单独进攻都毫⽆胜算，除⾮有⾄少6⽀军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅⾃变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到⼀种分布式的协议来让他们能够远程协商，从⽽赢取战⽃？这就是著名的拜占庭将军问题。
拜占庭将军问题中并不去考虑通信兵是否会被截获或⽆法传达信息等问题，即消息传递的信道绝⽆问题。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的⽅式达到⼀致性是不可能
的。所以，在研究拜占庭将军问题的时候，假定信道是没有问题的，然后去做⼀致性和容错性相关研究。
2、两将军问题
拜占庭问题前，就已经存在两将军问题(Two Generals Paradox)：两个将军要通过信使来达成进攻还是撤退的约定，但信使可能迷路或被敌军阻拦(消息丢失或伪造)，如何达成⼀致?
根据FLP不可能原理，两将军问题⽆通⽤解。
3、BFT简介
BFT（Byzantine Fault Tolerance），即拜占庭容错，是分布式计算领域的容错技术，拜占庭容错来源于拜占庭将军问题。拜占庭将军问题是对现实世界的模型化，由于硬件错误、⽹络拥塞或中断以及遭到恶意攻击等原因，计算机和⽹络可能出现不可预料的⾏为。拜占庭容错技术被设计⽤来处理现实存在的异常⾏为，并满⾜所要解决的问题的规范要求。
区块链⽹络环境符合拜占庭将军问题模型，有运⾏正常的服务器（忠诚的拜占庭将军），有故障的服务器，还有破坏者的服务器（叛变的拜占庭将军）。共识算法的核⼼是在正常的节点间形成对⽹络状态的共识。
通常，发⽣故障的节点被称为拜占庭节点，⽽正常的节点为⾮拜占庭节点。
拜占庭容错系统是⼀个拥有n台节点的系统，整个系统对于每⼀个请求，满⾜以下条件：
A、所有⾮拜占庭节点使⽤相同的输⼊信息，产⽣同样的结果；
B、如果输⼊的信息正确，那么所有⾮拜占庭节点必须接收这个信息，并计算相应的结果。
拜占庭系统普遍采⽤的假设条件包括：
A、拜占庭节点的⾏为可以是任意的，拜占庭节点之间可以共谋；
B、节点之间的错误是不相关的；
C、节点之间通过异步⽹络连接，⽹络中的消息可能丢失、乱序并延时到达，但⼤部分协议假设消息在有限的时间⾥能传达到⽬的地；
D、服务器之间传递的信息，第三⽅可以嗅探到，但是不能篡改、伪造信息的内容和验证信息的完整性。
原始的拜占庭容错系统由于需要展⽰其理论上的可⾏性⽽缺乏实⽤性。另外，还需要额外的时钟同步
机制⽀持，算法的复杂度也是随节点增加⽽指数级增加。
⼆、PBFT算法
1、PBFT算法简介
PBFT（Practical Byzantine Fault Tolerance），即实⽤拜占庭容错算法，由Miguel Castro和Barbara Liskov在1999年发表的论⽂《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出。PBFT算法可以⼯作在异步环境中，并且通过优化解决了原始拜占庭容错算法效率不⾼的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应⽤中变得可⾏，⽬前已得到⼴泛应⽤。PBFT算法可以在失效节点不超过总数1/3的情况下同时保证Safety和Liveness。
PBFT 算法采⽤密码学相关技术(RSA 签名算法、消息验证编码和摘要)确保消息传递过程⽆法被篡改和破坏。
2、PBFT算法原理
PBFT是⼀种状态机副本复制算法，即服务作为状态机进⾏建模，状态机在分布式系统的不同节点进⾏副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使⽤⼤写字母R表⽰，使⽤0到|R|-1的整数表⽰每⼀个副本。为了描述⽅便，通常假设故障节点
数为f个，整个服务节点数为|R|=3f+1个，f是有可能失效的副本的最⼤个数。尽管可以存在多于3f+1个副本，但额外的副本除了降低性能外不能提⾼可靠性。
所有的副本在⼀个被称为视图（View）的轮换过程中运作。在某个视图中，⼀个副本作为主节点（primary），其它的副本节点作为备份节点（backups）。视图是连续编号的整数。主节点由公式p = v mod |R|计算得到，v是视图编号，p是副本编号，|R|是副本集合的个数。当主节点失效的时候就需要启动视图轮换过程。
PBFT算法实现流程如下：
（1）REQUEST
客户端C向主节点p发送<REQUEST, o, t, c>请求。
o：请求的具体操作
t：请求时客户端追加的时间戳
c：客户端标识。
REQUEST: 包含消息内容m，以及消息摘要d(m)。
客户端对请求进⾏签名。
（2）PRE-PREPARE
主节点收到客户端的请求，需要对客户端请求消息签名是否正确进⾏校验。
⾮法请求则丢弃。正确请求，分配⼀个编号n，编号n主要⽤于对客户端的请求进⾏排序。然后⼴播⼀条<<PRE-PREPARE, v, n, d>, m>消息给其它副本节点。
v：视图编号
d客户端消息摘要
m：消息内容
<PRE-PREPARE, v, n, d>进⾏主节点签名。
n是要在某⼀个范围区间内的[h, H]。
（3）PREPARE
副本节点i收到主节点的PRE-PREPARE消息，需要进⾏以下校验：
A、主节点PRE-PREPARE消息签名是否正确。
B、当前副本节点是否已经收到了⼀条在同⼀v下并且编号也是n，但是签名不同的PRE-PREPARE信息。
C、d与m的摘要是否⼀致。
D、n是否在区间[h, H]内。
⾮法请求则丢弃。正确请求，副本节点i向其它节点包括主节点发送⼀条<PREPARE, v, n, d, i>消息, v, n, d, m与上述PRE-PREPARE消息内容相同，i是当前副本节点编号。<PREPARE, v, n, d, i>进⾏副本节点i的签名。记录PRE-PREPARE和PREPARE消息到log中，⽤于视图轮换过程中恢复未完成的请求操作。
PREPARE阶段如果发⽣视图轮换会导致丢弃PREPARE阶段的请求。
（4）COMMIT
主节点和副本节点收到PREPARE消息，需要进⾏以下校验：
A、副本节点PREPARE消息签名是否正确。
B、当前副本节点是否已经收到了同⼀视图v下的n。
C、 n是否在区间[h, H]内。
D、d是否和当前已收到PRE-PPREPARE中的d相同
⾮法请求则丢弃。如果副本节点i收到了2f+1个验证通过的PREPARE消息，表明⽹络中的⼤多数节点已经收到同意信息，则向其它节点包括主节点发送⼀条<COMMIT, v, n, d, i>消息，v, n, d, i与上述PREPARE消息内容相同。<COMMIT, v, n, d, i>进⾏副本节点i的签名。记录COMMIT消息到⽇志中，⽤于视图轮换过程中恢复未完成的请求操作。记录其它副本节点发送的PREPARE消息到log中。
COMMIT阶段⽤来确保⽹络中⼤多数节点都已经收到⾜够多的信息来达成共识，如果COMMIT阶段发⽣视图轮换，会保存原来COMMIT阶段的请求，不会达不成共识，也不会丢失请求编号。
（5）REPLY
主节点和副本节点收到COMMIT消息，需要进⾏以下校验：
A、副本节点COMMIT消息签名是否正确。
B、当前副本节点是否已经收到了同⼀视图v下的n。
C、d与m的摘要是否⼀致。
D、n是否在区间[h, H]内。
⾮法请求则丢弃。如果副本节点i收到了2f+1个验证通过的COMMIT消息，说明当前⽹络中的⼤部分节点已经达成共识，运⾏客户端的请求操作o，并返回<REPLY, v, t, c, i, r>给客户端，r：是请求操作结果，客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全⽹共识，否则客户端需要判断是否重新发送请求给主节点。记录其它副本节点发送的COMMIT消息到log中。
3、PBFT算法的垃圾回收
为了确保在视图轮换的过程中，能够恢复先前的请求，每⼀个副本节点都记录⼀些消息到本地的log中，
当执⾏请求后副本节点需要把之前该请求的记录消息清除掉。最简单的做法是在Reply消息后，再执⾏⼀次当前状态的共识同步，但成本⽐较⾼，因此可以在执⾏完多条请求K（例如：100条）后执⾏⼀次状态同步。状态同步消息就是CheckPoint消息。
副本节点i发送<CheckPoint, n, d, i>给其它节点，n是当前节点所保留的最后⼀个视图请求编号，d是对当前状态的⼀个摘要，该CheckPoint消息记录到log中。如果副本节点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、PBFT算法的视图轮换
如果主节点作恶，可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻的序号不连续。备份节点应当有职责来主动检查这些序号的合法性。如果主节点掉线或者作恶不⼴播客户端的请
求，客户端设置超时机制，超时的话，向所有副本节点⼴播请求消息。副本节点检测出主节点作恶或者下线，发起视图轮换协议。
副本节点向其它节点⼴播<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消息集合的选取规则如下：
A、选取V中最⼩的stable checkpoint编号min-s，选取V中prepare消息的最⼤编号max-s。
B、在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)为空消息摘要。
副本节点收到主节点的NEW-VIEW消息，验证有效性，有效的话，进⼊v+1状态，并且开始O中的PRE-PREPARE消息处理流程。
5、PBFT算法的优缺点
PBFT算法的优点:
PBFT算法具有⾼交易通量和吞吐量，⾼可⽤性，易于理解。
PBFT算法的缺点:
A、计算效率依赖于参与协议的节点数量，由于每个副本节点都需要和其它节点进⾏P2P的共识同步，因此随着节点的增多，性能会下降的很快，但在较少节点的情况下可以有不错的性能，并且分叉的⼏率很低，不适⽤于节点数量过⼤的区块链，扩展性差。
B、系统节点是固定的，⽆法应对公有链的开放环境，只适⽤于联盟链或私
有链环境。
C、PBFT算法要求总节点数n>=3f+1(其中，f代表作恶节点数)。系统的失效节点数量不得超过全⽹节点的1/3，容错率相对较低。
6、PBFT算法的应⽤场景
PBFT算法的节点数量是固定的，节点⾝份提前确定，⽆法动态添加或删除，只能适⽤于节点数⽬固定的联盟链或私有链场景中。
PBFT在很多场景都有应⽤，在区块链场景中，⼀般适合于对强⼀致性有要求的私有链和联盟链场景，但如果能够结合DPOS节点代表选举规则，也可以应⽤于公有链，并且可以在⼀个不可信的⽹络⾥解决拜占庭容错问题。在Hyperledger Fabric项⽬中，共识模块被设计成可插拔的模块，⽀持像PBFT、Raft等共识算法。
三、POW算法
1、POW算法简介
POW（Proof of Work），即⼯作量证明，也称挖矿。⼯作量证明通过计算来猜测⼀个数值(nonce)，使得拼凑上交易数据后内容的Hash 值满⾜规定的上限。由于Hash难题在⽬前计算模型下需要⼤量的计算，可以保证在⼀段时间内，系统中只能出现少数合法提案。如果能够提出合法提案，证明提案者确实已经付出了⼀定的⼯作量。
哈希现⾦是⼀种⼯作量证明机制，是Adam Back在1997年发明的，⽤于抵抗邮件的拒绝服务攻击及垃圾邮件⽹关滥⽤。
2、POW算法原理
⼯作量证明的主要特征是客户端需要做⼀定难度的⼯作得出⼀个结果，验证⽅却很容易通过结果来检查出客户端是不是做了相应的⼯作。⼯作量证明⽅案的⼀个核⼼特征是不对称性：⼯作对于请求⽅是适中的，对于验证⽅则是易于验证的。
给定⼀个基本字符串，在基本字符串后⾯添加⼀个叫做nonce的整数值，对变更后（添加nonce)的字符串进⾏SHA256哈希运算，如果得到的哈希结果（以16进制的形式表⽰）是以某个字符串（如"0000"）开头的，则验证通过。为了达到⼯作量证明的⽬标，需要不停的递增nonce值，对得到的新字符串进⾏SHA256哈希运算。
由于给定的基本字符串在不同的场合并不确定，对于不同的基本字符串和nonce的组合，要使⽤SHA256计算得到某个字符串开头Hash值的计算次数并不确定，但会是⼀个符合统计学规律的概率事件。
按照规则，预期⼤概要进⾏2^16 次尝试（哈希值的伪随机特性可以做概率估算），才能得到4个前导0
的哈希散列。
3、⽐特币的POW实现
⽐特币区块由区块头和该区块所包含的交易列表组成。区块头⼤⼩为80字节，其构成包括：
4字节：版本号
32字节：上⼀个区块的哈希值
32字节：交易列表的Merkle根哈希值
4字节：当前时间戳
4字节：当前难度值
4字节：随机数Nonce值
80字节长度的区块头，即为⽐特币Pow算法的输⼊字符串。
交易列表附加在区块头之后，其中第⼀笔交易为矿⼯获得奖励和⼿续费的特殊交易。
⼯作量证明过程，即为不断调整Nonce值，对区块头做双重SHA256哈希运算，使得结果满⾜给定数量前导0的哈希值的过程，其中前导0的个数，取决于挖矿难度，前导0的个数越多，挖矿难度越⼤。
每创建2016个块后将计算新的难度，此后的2016个块使⽤新的难度。计算步骤如下：
A、找到前2016个块的第⼀个块，计算⽣成这2016个块花费的时间。
即最后⼀个块的时间与第⼀个块的时间差。时间差不⼩于3.5天，不⼤于56天。
B、计算前2016个块的难度总和，即单个块的难度x总时间。
C、计算新的难度，即2016个块的难度总和/14天的秒数，得到每秒的难度值。
D、要求新的难度，难度不低于参数定义的最⼩难度。
4、POW算法的优缺点
POW算法的优点：
A、完全去中⼼化
B、节点⾃由进出
C、安全性⾼
POW算法的缺点：
A、记账权向资本集中
B、挖矿造成⼤量的资源浪费。
C、⽹络性能太低，需要等待多个确认，容易产⽣分叉，区块的确认共识达成的周期较长，不适合商业应⽤。
5、POW算法的应⽤场景
POW共识机制⽤在了⼤部分挖矿的区块链项⽬，⽐如BTC、ETH、LTC。
四、POS算法
1、POS算法简介
POS（Proof of Stake），即权益证明，是POW的⼀种升级共识机制，根据每个节点所占代币的⽐例和时间，等⽐例的降低挖矿难度，从⽽加快找随机数的速度。
鉴于POW的缺陷，2012年Sunny King提出了POS，并基于POW和POS的混合机制发布了点点币PPCoin。
2、POS算法原理
