共识算法系列之一：私链的raft算法和联盟链的 pbft 算法

对数据顺序达成一致共识是很多共识算法要解决的本质问题

创新互联提供网站建设、成都做网站、网页设计，品牌网站制作，1元广告等致力于企业网站建设与公司网站制作，10年的网站开发和建站经验,助力企业信息化建设，成功案例突破近1000家,是您实现网站建设的好选择.

Fabic的pbft算法实现

现阶段的共识算法主要可以分成三大类：公链，联盟链和私链

私链，所有节点可信

联盟链，存在对等的不信任节点

私链：私链的共识算法即区块链这个概念还没普及时的传统分布式系统里的共识算法，比如 zookeeper 的 zab 协议，就是类 paxos 算法的一种。私链的适用环境一般是不考虑集群中存在作恶节点，只考虑因为系统或者网络原因导致的故障节点。

联盟链：联盟链中，经典的代表项目是 Hyperledger 组织下的 Fabric 项目， Fabric0.6 版本使用的就是 pbft 算法。联盟链的适用环境除了需要考虑集群中存在故障节点，还需要考虑集群中存在作恶节点。对于联盟链，每个新加入的节点都是需要验证和审核的。

公链：公链不仅需要考虑网络中存在故障节点，还需要考虑作恶节点，这一点和联盟链是类似的。和联盟链最大的区别就是，公链中的节点可以很自由的加入或者退出，不需要严格的验证和审核。

在公有链中用的最多的是pow算法和pos算法，这些算法都是参与者的利益直接相关，通过利益来制约节点诚实的工作，解决分布式系统中的拜占庭问题。拜占庭容错算法是一种状态机副本复制算法，通过节点间的多轮消息传递，网络内的所有诚实节点就可以达成一致的共识。

使用拜占庭容错算法不需要发行加密货币，但是只能用于私有链或者联盟链，需要对节点的加入进行权限控制；不能用于公有链，因为公有链中所有节点都可以随意加入退出，无法抵挡女巫攻击（sybil attack）

raft 算法包含三种角色，分别是：跟随者（ follower ），候选人（candidate ）和领导者（ leader ）。集群中的一个节点在某一时刻只能是这三种状态的其中一种，这三种角色是可以随着时间和条件的变化而互相转换的。

raft 算法主要有两个过程：一个过程是领导者选举，另一个过程是日志复制，其中日志复制过程会分记录日志和提交数据两个阶段。raft 算法支持最大的容错故障节点是（N-1）/2，其中 N 为 集群中总的节点数量。

国外有一个动画介绍raft算法介绍的很透彻，链接地址为： 。这个动画主要包含三部分内容，第一部分介绍简单版的领导者选举和日志复制的过程，第二部分内容介绍详细版的领导者选举和日志复制的过程，第三部分内容介绍的是如果遇到网络分区（脑裂），raft 算法是如何恢复网络一致的。

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 算法的最大容错节点数量是（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。

第二种情况，故障节点和作恶节点都是不同的节点。那么就会有 f 个问题节点和 f 个故障节点，当发现节点是问题节点后，会被集群排除在外，剩下 f 个故障节点，那么根据小数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即 f+1 个节点，确节点的数量就会比故障节点数量多，那么集群就能达成共识。所以，所有类型的节点数量加起来就是 f+1 个正确节点，f个故障节点和f个问题节点，即 3f+1=n。

结合上述两种情况，因此 pbft 算法支持的最大容错节点数量是（n-1）/3

pbft 算法的基本流程主要有以下四步：

客户端发送请求给主节点

主节点广播请求给其它节点，节点执行 pbft 算法的三阶段共识流程。

节点处理完三阶段流程后，返回消息给客户端。

客户端收到来自 f+1 个节点的相同消息后，代表共识已经正确完成。

为什么收到 f+1 个节点的相同消息后就代表共识已经正确完成？从上一小节的推导里可知，无论是最好的情况还是最坏的情况，如果客户端收到 f+1 个节点的相同消息，那么就代表有足够多的正确节点已全部达成共识并处理完毕了。

3.算法核心三阶段流程

算法的核心三个阶段分别是 pre-prepare 阶段（预准备阶段），prepare 阶段（准备阶段）， commit 阶段（提交阶段）

流程的对比上，对于 leader 选举这块， raft 算法本质是谁快谁当选，而 pbft 算法是按编号依次轮流做主节点。对于共识过程和重选 leader 机制这块，为了更形象的描述这两个算法，接下来会把 raft 和 pbft 的共识过程比喻成一个团队是如何执行命令的过程，从这个角度去理解 raft 算法和 pbft 的区别。

一个团队一定会有一个老大和普通成员。对于 raft 算法，共识过程就是：只要老大还没挂，老大说什么，我们（团队普通成员）就做什么，坚决执行。那什么时候重新老大呢？只有当老大挂了才重选老大，不然生是老大的人，死是老大的鬼。

对于 pbft 算法，共识过程就是：老大向我发送命令时，当我认为老大的命令是有问题时，我会拒绝执行。就算我认为老大的命令是对的，我还会问下团队的其它成员老大的命令是否是对的，只有大多数人 （2f+1） 都认为老大的命令是对的时候，我才会去执行命令。那什么时候重选老大呢？老大挂了当然要重选，如果大多数人都认为老大不称职或者有问题时，我们也会重新选择老大。

四、结语

raft 算法和 pbft 算法是私链和联盟链中经典的共识算法，本文主要介绍了 raft 和 pbft 算法的流程和区别。 raft 和 pbft 算法有两点根本区别：

raft 算法从节点不会拒绝主节点的请求，而 pbft 算法从节点在某些情况下会拒绝主节点的请求 ;

raft 算法只能容错故障节点，并且最大容错节点数为 （n-1）/2 ，而 pbft 算法能容错故障节点和作恶节点，最大容错节点数为 （n-1）/3 。

pbft算法是通过投票来达成共识，可以很好的解决包括分叉等问题的同时提升效率。但仅仅比较适合于联盟链私有链，因为两两节点之间通信量是O(n^2)（通过优化可以减少通信量），一般来说不能应用于超过100个节点。

pbft有解的前提是 信道必须是可靠的 ，存在的问题是 可扩展性（scalability）差

部分来自：

区块链在设计上就是为了BFT

区块链笔记——PBFT

PBFT是实用拜占庭容错的简称，是解决拜占庭将军问题的一种方案。比起最开始的BFT算法，PBFT额外要求网络封闭，即节点数目确定并提前互通，但将复杂度从指数级降低到多项式级，使得BFT系列算法真正具有可行性。

与POW、POS等大家耳熟能详的共识不同，BFT系列的共识不需要“Proof”，亦即不需要节点投入算力或其他资源来确权，因此不需要代币激励便可完成共识。缺点是原始的BFT效率太低，只能存在于理论而无法应用。而改进的PBFT虽然效率大大提高，却对节点数量和状态提出了要求，导致合格的记帐节点太少，并且也只能维持在少数，过多的节点会拖慢网络速度。因此PBFT更多是用在联盟链和私链上。公链也有应用，例如NEO，便是采用了PBFT算法。

拜占庭将军问题的实质是在恶劣的通讯环境中，如何使各参与方达成一致意见。POW和POS等共识要求参与方投入成本，争夺唯一的发言权。在某一段时间内只有唯一的发言人，自然只会有一个意见，从而达成共识。PBFT采取不同的思路，要求各参与方相互发送及验证彼此的信息，最终采用多数原则达成共识。

PBFT能够以一种低成本的方式实现节点间共识，其理念其实相当贴近我们的生活习惯。例如在老师布置作业后，同学们总要互相问问确认一下，才放心地把今天的作业记到本子上。当然实现上还有很多细节，保证各节点的平等关系。在节点数目不多的时候，节点之间实现相互通信的成本并不高，节点之间可以快速发送确认。但节点数目增长却会带来整体性能的下降。PBFT可以容忍的坏节点数量不多于总数的三分之一，如果节点损坏率比较固定，提高总节点数量虽然能使系统获得更好的冗余，却会大大增加通讯量，造成效率下降。加上PBFT没有激励机制，其适合联盟链和私链场景。作为公链不可避免地节点数量太少，分布过分集中，例如NEO只有七个节点。

PBFT要求坏节点数量f=(n-1)/3，这里n是总节点数。只要f满足这个条件，共识总是可以达成。为什么f要满足这个条件？简单来说，假设网络中存在恶意节点联盟，其控制了数量为f的节点，这些节点可以故意发布错误的信息。此时网络中正常节点数量为n-f个。将这n-f个节点分为两部分，各自包含一部分节点。对于任一部分正常节点来说，只要恶意节点数f大于自身节点数，同时大于剩余的正常节点数，这部分正常节点便会与恶意节点联盟达成共识。此时只要恶意节点联盟先后向两部分正常节点发送不同的共识信息，便可造成网络分叉。因此要保证网络运行，对于每一部分正常节点来说，网络中恶意节点数量不能同时大于自身节点数和网络剩余正常节点数。代入计算便得到f=(n-1)/3。

实用拜占庭容错算法（PBFT）

 拜占庭帝国即东罗马帝国，拥有巨大的财富，并对邻邦垂诞已久，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？这就是著名的拜占庭将军问题【在分布式系统中指的是消息不仅可以被丢失、延迟、重放，还可以被伪造】。

    PBFT(Practical Byzantine Fault Tolerance)算法由Miguel Castro 和Barbara Liskov在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。

    PBFT是一种状态机副本复制算法，一般包括三种协议:一致性协议(agreement)、检查点协议(checkpoint)和视图更换协议(view change)。该算法要满足以下两个性质：   

    安全性(safety)：safety means nothing bad happens.                                                        活性(liveness)：liveness means that something good eventually happens.

    在一个拜占庭系统里面，要容忍f个拜占庭节点错误，则replica数量至少为3f+1，这是满足安全性的前提。因为网络延迟或宕机，系统存在f个节点不回复响应（f个节点包括拜占庭节点和非拜占庭节点，最坏情况f个节点全是非拜占庭节点），剩下2f+1个响应中可能有f个拜占庭节点，从而得到n-2ff，即响应中非拜占庭节点数目大于拜占庭节点数目（f+1f）。

    算法不依赖同步提供安全性，则必须依赖同步提供活性，否则违背FLP定理(在异步通信场景，即使只有一个进程失败了，没有任何算法能保证非失败进程能够达到一致性)。在拜占庭节点不超过f，并且delay(t)有界的情况下就能保证系统活性，delay(t)表示从消息发送到接受的时间间隔。

    在一个view里面，会从replicas中选择一个primary，其余的replicas则叫backups。如果主节点行为发生异常，则进行view change换主。                                  

   游戏从client向primary发送请求 开始。 状态机操作， 时戳。                                                                                                                                       游戏从client至少收到f+1个replicas的响应 结束。 视图编号， 时戳， 客户端身份， replica编号， 请求结果。【why f+1？因为在2f+1个committed中有f个拜占庭节点表面上同意请求，实际上根本不会回复请求】

3.1 重彩大戏------三阶段协议

Pre-prepare:

    Primary为客户端请求分配一个序列号n，向所有backups发现预准备消息 。 视图编号， 消息 的摘要。

Prepare:

    若满足以下条件，backups接受预准备消息：                                                                    1.客户端请求和预准备消息具有正确签名。                                                                        2.当前视图编号是v。                                                                                                          3.backups从未在当前视图v接收过序列号为n但摘要不同的预准备请求。                          4.hnH。【防止一个拜占庭节点选择一个大的序号来消耗序号空间】

    如果上述条件满足，backups接收预准备消息，进入prepare阶段，向其他节点广播准备消息 ，并将预准备和准备消息写入日志。

commit:

   如果backups收到2f【包括自己】个与预准备消息一致的准备消息，请求消息和预准备消息具有相同的视图v和序列号n，并且已将相关消息写入日志，则进入commit阶段，向其他节点广播一条确认消息 。如果各节点收到2f+1条相同的commits消息，则向客户端发送一条reply消息。

3.2 垃圾回收

  PBFT是一种状态机副本复制算法，replicas会将执行过消息记录在本地日志中，为了节省内存，需要一种机制来清理日志。何时来清理？在每次操作完后执行是不明智的，因为比较耗资源。可以定期清理，比如每100次清理一次。我们将请求后执行的状态称为检查点checkpoint；带证明的检查点称为stable certificate，当节点收到2f+1个checkpoint消息时，可证明稳定检查点是正确的。稳定检查点之前的日志消息均可删除。                       

  当清理检查点时replica i向其他replicas广播一条检查点协议 ， 是最近一次正确执行请求序号， 是其当前状态摘要。如果每一个replica收到2f+1个具有相同序号 和摘要 的检查点消息，这时每一个replica可以清理序列号 小于等于n的日志信息。

   检查点协议也用来更新水平线。低水平线 等于最近稳定检查点的序号，高水平线 ， 为日志大小。

3.3 视图更改

    当主节点挂掉，或者在commit阶段有些节点收到2f+1个commit，有些没有收到2f+1个commit，导致状态不一致，这些状况都需要更改视图来提供系统活性和安全性。

    当请求超时，备份节点进入视图v+1，广播视图更改消息 。 稳定检查点序列号， 是稳定检查点证明， 是一个集合，包含对请求 （请求的序列号大于 ）相关消息集合 。 包含2f+1个相同的准备消息。

     当视图v+1的主节点收到2f个相同个视图更改消息，向其他副本广播新视图消息 ， 是2f+1个视图更改消息， 的计算规则如下：        1.确定序列号 和 。其中 等于 中稳定检查点序列号, 等于 中最大prepare消息序列号。                                                                                                  2.主节点为 和 之间的每一个序列号n分配pre-prepare消息。如果 中包含n对应的 组合，则对应的预准备消息为 （也就是说序列号n对应的请求有2f+1个prepare消息，在新视图中依然提交这个请求）。如果 中不包含n对应的 组合，则提交null消息为 ，即不做任何处理。

    副本收到新视图消息后，广播一次prepare消息，进入v+1，视图更换完成。

拜占庭共识算法

拜占庭共识算法有一个前提：

安全节点数 R(eliable) 大于不安全节点数 E(vil)。而且理想情况下R方希望投票结果是统一的。

所以结合两个不等式

P R/2 +E

P R

得出

R R/2 + E

这就可推测出

R + R/2 R + E

(3/2) R ALL(总节点数)

辣么 R ALL(2/3)

所以当安全节点数 R(eliable) 大于总节点的(2/3)时，投出来的票才是可靠的

然后，祭出拜占庭投票的流程，以及算法模拟流程

其中D为发送请求端，R0 R1 R2 R3为服务端：

最后本来想自己写个实现的，但是Java实现太重量级了，贴个别人用Go语言实现的吧

新闻标题：go语言pbft算法实现的简单介绍
URL地址：http://pwwzsj.com/article/hiiccp.html