深⼊剖析区块链的共识算法RaftPBFT
导语：区块链技术中，共识算法是其中核⼼的⼀个组成部分，⽐特币使⽤的是POW（Proof of Work，⼯作量证明），以太币将来使⽤POS（Proof of Stake，权益证明）。对于不需要货币体系的联盟链或者私链⽽⾔，传统的⼀致性算法成为⾸选，常见的有：PBFT（拜占庭容错）、PAXOS、RAFT。本⽂将详细阐述私链的raft算法和联盟链的PBFT算法，从算法的基本流程切⼊，深⼊介绍PBFT算法，并对⽐分析raft算法和PBFT算法的区别。
作者简介：梁敏鸿，美图区块链架构师，专注于区块链技术研究与产品应⽤落地。
区块链技术中，共识算法是其中核⼼的⼀个组成部分。⾸先我们来思考⼀个问题：什么是共识？对于现实世界，共识就是⼀群⼈对⼀件或者多件事情达成⼀致的看法或者协议。那么在计算机世界当中，共识是什么呢？
我的理解包含两个层⾯，第⼀个层⾯是点的层⾯，即多个节点对某个数据达成⼀致共识。第⼆个层⾯是线的层⾯，即多个节点对多个数据的顺序达成⼀致共识。这⾥的节点可以是任意的计算机设备，⽐如pc电脑，笔记本，⼿机，路由器等，这⾥的数据可以是交易数据，状态数据等。其中对数据顺序达成⼀致共识是很多共识算法要解决的本质问题。
常见的共识算法都有哪些呢？现阶段的共识算法主要可以分成三⼤类：公链，联盟链和私链。下⾯描述这三种类别的特征。
私链：私链的共识算法即区块链这个概念还没普及时的传统分布式系统⾥的共识算法，⽐如zookeeper 的zab 协议，就是类 paxos 算法的⼀种。私链的适⽤环境⼀般是不考虑集群中存在作恶节点，只考虑因为系统或者⽹络原因导致的故障节点。
联盟链：联盟链中，经典的代表项⽬是 Hyperledger 组织下的 Fabric 项⽬，Fabric0.6 版本使⽤的就是 pbft 算法。联盟链的适⽤环境除了需要考虑集群中存在故障节点，还需要考虑集群中存在作恶节点。对于联盟链，每个新加⼊的节点都是需要验证和审核的。
公链：公链不仅需要考虑⽹络中存在故障节点，还需要考虑作恶节点，这⼀点和联盟链是类似的。和联盟链最⼤的区别就是，公链中的节点可以很⾃由的加⼊或者退出，不需要严格的验证和审核。
本⽂接下来将会主要阐述私链的 raft 算法和联盟链的 pbft 算法，以及它们的区别和对⽐。
⼀. raft 算法
因为⽹上已经有⼤量⽂章对raft 算法进⾏过详细的介绍，因此这部分只会简单的阐述算法的基本原理和流程。raft 算法包含三种⾓⾊，分别是：跟随者（follower），候选⼈（candidate）和领导者（leader）。集群中的⼀个节点在某⼀时刻只能是这三种状态的其中⼀种，这三种⾓⾊是可以随着时间和条件的变化⽽互相转换的。
raft 算法主要有两个过程：⼀个过程是领导者选举，另⼀个过程是⽇志复制，其中⽇志复制过程会分记录⽇志和提交数据两个阶段。raft 算法⽀持最⼤的容错故障节点是（N-1）/2，其中N为集群中总的节点数量。
国外有⼀个动画介绍raft 算法介绍的很透彻，链接地址在这⾥[1]。这个动画主要包含三部分内容，第⼀部分介绍简单版的领导者选举和⽇志复制的过程，第⼆部分内容介绍详细版的领导者选举和⽇志复制的过程，第三部分内容介绍的是如果遇到⽹络分区（脑裂），raft 算法是如何恢复⽹络⼀致的。有兴趣的朋友可以结合这个动画来更好的理解raft算法。
⼆. pbft 算法
pbft算法的提出主要是为了解决拜占庭将军问题。什么是拜占庭将军问题呢？拜占庭位于如今的⼟⽿其的伊斯坦布尔，是古代东罗马帝国的⾸都。拜占庭罗马帝国国⼟辽阔，为了达到防御⽬的，每块封地都驻扎⼀⽀由将军统领的军队，每个军队都分隔很远，将军与将军之间只能靠信差传递消息。在战争的时候，拜占庭军队内所有将军必需达成⼀致的共识，决定是否有赢的机会才去攻打敌⼈的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定影响将军们达成⼀致共识。在已知有将军是叛徒的情况下，其余忠诚的将军如何达成⼀致协议的问题，这就是拜占庭将军问题。
要让这个问题有解，有⼀个⼗分重要的前提，那就是信道必须是可靠的。如果信道不能保证可靠，那么拜占庭问题⽆解。关于信道可靠问题，会引出两军问题。两军问题的结论是，在⼀个不可靠的通信链路上试图通过通信以达成⼀致是基本不可能或者⼗分困难的。
那么如果在信道可靠的情况下，要如何解这个问题呢？拜占庭将军问题其实有很多种解法，接下来先
介绍两位⼤⽜，这两位⼤⽜都在解决拜占庭问题上做出了突出的贡献。
如上图所⽰，拜占庭将军问题最早是由Leslie Lamport 与另外两⼈在1982年发表的论⽂《The Byzantine Generals Problem 》提出的，他证明了在将军总数⼤于3f ，背叛者为f 或者更少时，忠诚的将军可以达成命令上的⼀致，即3f+1<=n。算法复杂度为o（n^(f+1))。⽽Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年发表的论⽂《Practical Byzantine Fault Tolerance》中⾸次提出pbft算法，该算法容错数量也满⾜3f+1<=n，算法复杂度为o（n^2）。
⽹上关于pbft的算法介绍基本上是基于liskov在1999年发表的论⽂《Practical Byzantine Fault Tolerance》来进⾏解释的。当前⽹上介绍pbft的中⽂⽂章不算太多，基本上只有那⼏篇，并且感觉有
些关键点解释得不够清晰，因此接下来会详细描述下 pbft 算法的过程和原理。
2.1 推论：raft算法的2f+1<=n和pbft的3f+1<=n
⾸先我们先来思考⼀个问题，为什么pbft算法的最⼤容错节点数量是（n-1）/3，⽽raft算法的最⼤容错节点数量是（n-1）/2？
对于raft算法，raft算法的的容错只⽀持容错故障节点，不⽀持容错作恶节点。什么是故障节点呢？就是节点因为系统繁忙、宕机或者⽹络问题等其它异常情况导致的⽆响应，出现这种情况的节点就是故障节点。那什么是作恶节点呢？作恶节点除了可以故意对集群的其它节点的请求⽆响应之外，还可以故意发送错误的数据，或者给不同的其它节点发送不同的数据，使整个集群的节点最终⽆法达成共识，这种节点就是作恶节点。
raft算法只⽀持容错故障节点，假设集群总节点数为n，故障节点为f，根据⼩数服从多数的原则，集群⾥正常节点只需要⽐f个节点再多⼀个节点，即f+1个节点，正确节点的数量就会⽐故障节点数量多，那么集群就能达成共识。因此raft算法⽀持的最⼤容错节点数量是（n-1）/2。
对于pbft算法，因为pbft算法的除了需要⽀持容错故障节点之外，还需要⽀持容错作恶节点。假设集群节点数为N，有问题的节点为f。有问题的节点中，可以既是故障节点，也可以是作恶节点，或者只是故障节点或者只是作恶节点。那么会产⽣以下两种极端情况：
第⼀种情况，f个有问题节点既是故障节点，⼜是作恶节点，那么根据⼩数服从多数的原则，集群⾥正常节点只需要⽐f 个节点再多⼀个节点，即f+1个节点，确节点的数量就会⽐故障节点数量多，那么集群就能达成共识。也就是说这种情况⽀持的最⼤容错节点数量是（n-1）/2。
况⽀持的最⼤容错节点数量是（n-1）/2。
第⼆种情况，故障节点和作恶节点都是不同的节点。那么就会有f个问题节点和f个故障节点，当发现节点是问题节点后，会被集群排除在外，剩下f个故障节点，那么根据⼩数服从多数的原则，集群⾥正常节点只需要⽐f个节点再多⼀个节点，即f+1个节点，确节点的数量就会⽐故障节点数量多，那么集群就能达成共识。所以，所有类型的节点数量加起来就是f+1个正确节点，f个故障节点和f个问题节点，即3f+1=n。
结合上述两种情况，因此pbft算法⽀持的最⼤容错节点数量是（n-1）/3。下图展⽰了论⽂⾥证明pbft算法为什么3f+1<=n 的⼀段原⽂，以及根据原⽂提到的两种情况对应的⽰意图。
3f+1<=n这个结论在pbft算法的流程中会⼤量使⽤到，因此在介绍pbft算法流程前先解释下这个推论。
2.2 算法基本流程
pbft算法的基本流程主要有以下四步：
1.客户端发送请求给主节点
2.主节点⼴播请求给其它节点，节点执⾏pbft算法的三阶段共识流程。
3.节点处理完三阶段流程后，返回消息给客户端。
4.客户端收到来⾃f+1个节点的相同消息后，代表共识已经正确完成。
为什么收到f+1个节点的相同消息后就代表共识已经正确完成？从上⼀⼩节的推导⾥可知，⽆论是最好的情况还是最坏的情况，如果客户端收到f+1个节点的相同消息，那么就代表有⾜够多的正确节点已全部达成共识并处理完毕了。
2.3 算法核⼼三阶段流程
下⾯介绍pbft算法的核⼼三阶段流程，如下图所⽰：
算法的核⼼三个阶段分别是pre-prepare阶段（预准备阶段），prepare阶段（准备阶段），commit阶段（提交阶段）。图中的C代表客户端，0，1，2，3代表节点的编号，打叉的3代表可能是故障节点或者是问题节点，这⾥表现的⾏为就是对其它节点的请求⽆响应。0是主节点。整个过程⼤致是：
⾸先，客户端向主节点发起请求，主节点0收到客户端请求，会向其它节点发送pre-prepare 消息，其它节点就收到了pre-prepare 消息，就开始了这个核⼼三阶段共识过程了。
Pre-prepare阶段：节点收到pre-prepare消息后，会有两种选择，⼀种是接受，⼀种是不接受。什么时候才不接受主节点发来的pre-prepare消息呢？⼀种典型的情况就是如果⼀个节点接到了⼀条pre-pre消息，消息⾥的v和n在之前收到⾥的消息是曾经出现过的，但是d和m却和之前的消息不⼀致，或者请求编号不在⾼低⽔位之间（⾼低⽔位的概念在2.4节会进⾏解释），这时候就会拒绝请求。拒绝的逻辑就是主节点不会发送两条具有相同的v和n，但d和m却不同的消息。
会进⾏解释），这时候就会拒绝请求。拒绝的逻辑就是主节点不会发送两条具有相同的v和n，但d和m却不同的消息。Prepare阶段：节点同意请求后会向其它节点发送prepare消息。这⾥要注意⼀点，同⼀时刻不是只有⼀个节点在进⾏这
个过程，可能有n个节点也在进⾏这个过程。因此节点是有可能收到其它节点发送的prepare消息的。在⼀定时间范围内，如果收到超过2f个不同节点的prepare消息，就代表prepare阶段已经完成。
Commit阶段：于是进⼊commit阶段。向其它节点⼴播commit消息，同理，这个过程可能是有n个节点也在进⾏的。因此可能会收到其它节点发过来的commit消息，当收到2f+1个commit消息后（包括⾃⼰），代表⼤多数节点已经进⼊commit阶段，这⼀阶段已经达成共识，于是节点就会执⾏请求，写⼊数据。
处理完毕后，节点会返回消息给客户端，这就是pbft算法的全部流程。
为了更清晰的展现这个过程和⼀些细节，下⾯以流程图来表⽰这个过程。
注解：
V：当前视图的编号。视图的编号是什么意思呢？⽐如当前主节点为A，视图编号为1，如果主节点换成B，那么视图编号就为2.这个概念和raft的term任期是很类似的。
N：当前请求的编号。主节点收到客户端的每个请求都以⼀个编号来标记。
M：消息的内容
d或D（m）：消息内容的摘要
i：节点的编号
2.4 checkpoint、stable checkpoint和⾼低⽔位
什么是checkpoint呢？checkpoint就是当前节点处理的最新请求序号。前⽂已经提到主节点收到请求是会给请求记录编号的。⽐如⼀个节点正在共识的⼀个请求编号是101，那么对于这个节点，它的checkpoint就是101.
那什么是stable checkpoint（稳定检查点）呢？stable checkpoint就是⼤部分节点（2f+1）已经共识完
成的最⼤请求序号。⽐如系统有4个节点，三个节点都已经共识完了的请求编号是213.那么这个213就是stable checkpoint了。
那设置这个stable checkpoint有什么作⽤呢？最⼤的⽬的就是减少内存的占⽤。因为每个节点应该记录下之前曾经共识过什么请求，但如果⼀直记录下去，数据会越来越⼤，所以应该有⼀个机制来实现对数据的删除。那怎么删呢？很简单，⽐如现在的稳定检查点是213，那么代表213号之前的记录已经共识过的了，所以之前的记录就可以删掉了。
那什么是⾼低⽔位呢？下⾯以⼀个⽰意图来进⾏解释。
图中A节点的当前请求编号是1039，即checkpoint为1039，B节点的checkpoint为1133.当前系统stable checkpoint为1034.那么1034这个编号就是低⽔位，⽽⾼⽔位H=低⽔位h+L，其中L是可以设定的数值。因此图中系统的⾼⽔位为1034+100=1134。
举个例⼦：如果B当前的checkpoint已经为1034，⽽A的checkpoint还是1039，假如有新请求给B处理时，B会选择等待，等到A节点也处理到和B差不多的请求编号时，⽐如A也处理到1112了，这时会有⼀个机制更新所有节点的stabel checkpoint ，⽐如可以把stabel checkpoint设置成1100，于是B⼜可以处理新的请求了，如果L保持100不变，这时的⾼⽔位就会变成1100+100=1200了。
2.5 ViewChange（视图更改）事件
当主节点挂了（超时⽆响应）或者从节点集体认为主节点是问题节点时，就会触发ViewChange事件，ViewChange完成后，视图编号将会加1。
下图展⽰ViewChange的三个阶段流程。
如图所⽰，viewchange会有三个阶段，分别是view-change，view-change-ack和new-view阶段。从节点认为主节点有问题时，会向其它节点发送view-change消息，当前存活的节点编号最⼩的节点将成为新的主节点。当新的主节点收到2f个其它节点的view-change消息，则证明有⾜够多⼈的节点认为主节点有问题，于是就会向其它节点⼴播
New-view消息。注意：从节点不会发起new-view事件。对于主节点，发送new-view消息后会继续执⾏上个视图未处理完的请求，从pre-prepare阶段开始。其它节点验证new-view消息通过后，就会处理主节点发来的pre-prepare消息，这时执⾏的过程就是前⾯描述的pbft过程。到这时，正式进⼊ v+1（视图编号加1）的时代了。
为了更清晰的展现ViewChange这个过程和⼀些细节，下⾯以流程图来表⽰这个过程。
