【超越白皮书5】BFT类共识协议概览与分析实测
本报告由火币区块链研究院出品，报告发布时间2018年9月6日，作者：袁煜明、胡智威。
摘要
本文首先对BFT类共识协议按照改进思路分为3大类进行综述性概览：
针对无拜占庭错误场景优化的协议，包括PBFT、Zyzzyva等等
针对拜占庭错误场景优化的，包括Aardvark、Primer等等
为公链应用而优化的协议，包括DPoS+BFT、Zilliqa等等
本文还选用PBFT、Zyzzyva、Zilliqa协议，编写程序进行实测，主要得到以下结果及技术指导建议:
1、Zyzzyva和Zilliqa等协议的网络通讯量确实比PBFT降低很多。
2、调整PBFT检查点周期对性能没有太大影响；而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间，不过同时也会加大消息量对网络造成压力。
3、Zyzzyva在其客户端足够的情况下，增加批量数会对吞吐量和共识时间等性能指标均有较大提升。
4、虽然增加批量数对Zilliqa等协议都有促进效果，但这也会增加带宽占用。在设计共识协议时应综合考虑性能目标与网络带宽等实际情况。
报告正文
1.引言
共识协议被许多人视为是区块链项目的核心。无论是对区块链平台的交易处理能力、扩展性影响还是对通证经济的激励模型设计，共识协议都会产生很大影响。
共识协议从大的方面可分为自比特币诞生以来产生的PoW等中本聪共识协议和拜占庭容错（BFT）类共识协议这两大类协议。其中，在计算机科学的分布式系统研究领域已较多研究的BFT类共识协议近年来被越来越多的应用于联盟链平台。与此同时，也有越来越多的研发工作尝试将BFT应用于公链平台。
我们在本文中对BFT类协议进行了综述性概览分析，并从改进思路上将现有BFT类共识协议分为3大类：针对无拜占庭错误场景优化的协议、针对拜占庭错误场景优化的协议以及为公链应用而优化的协议；另外选用了PBFT、Zyzzyva、Zilliqa协议，编写程序并运行后得到实测对比结果，对共识协议的具体设计提供一些技术性指导建议。
2.主要结论
经过研究与测试分析，我们得到以下主要结论及技术建议：
1、Zyzzyva和Zilliqa等协议的网络通讯量确实比PBFT降低很多。
2、对PBFT，调整检查点周期对性能没有太大影响；而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间，不过同时也会加大消息量对网络造成压力。
3、Zyzzyva在其客户端足够的情况下，增加批量数会对吞吐量和共识时间等性能指标均有较大提升。
4、虽然增加批量数对Zilliqa等协议都有促进效果，但网络中消息量也会增加。在设计共识协议时应综合考虑性能目标与网络带宽等实际情况。
3.共识问题及BFT协议简介
3.1. 一致性问题及原理
计算机世界早已从“单机版”进入了“大型多人在线”的时代，区块链的诞生与发展更是让这一特性得到了充分的体现。这个过程中不可避免的产生了多个计算机之间如何达成一致的问题。常见问题包括：
在已经大规模投入使用中的分布式数据库系统环境中，有可能存在很多的宕机错误。根据CAP原理[2]，Paxos和Raft协议被设计为在牺牲一定可用性的情况下，解决在节点服务器可能宕机问题的协议[3]。
然而这些协议在区块链领域内还不能直接使用，因为还有其他更多在区块链领域内可能出现的错误。在表1中这种任意类型错误都可能发生的场景中，服务器有可能产生原本不应该输出的内容，系统要做好最坏情况的准备。例如，当一个服务器向不同的服务器发送截然相反的消息时，那么仅可处理宕机错误Paxos协议就无能为力了。
这种类型错误，也被称为拜占庭错误，最早由Pease和Lamport在上世纪80年代通过拜占庭将军问题进行描述和分析[4][5]。
因此相较于分布式数据库，区块链的对于一致性问题的设计和实现要更为复杂，这也是为什么区块链不只是一个简单的分布式数据库的原因之一。
3.2. BFT共识原理及流程简介
Lamport等人在其经典论文[4]中除了提出拜占庭将军问题外，也提供了两种解决办法[6][7]。
第一种为“口头消息”的OM(m)协议，即除了链路上可使用加密安全保障外，不允许使用任何的加密算法。该协议需要两两之间递归的传递大量消息，因此消息复杂度很高，为指数级，不太具有可实际操作性。但这一算法仍有其很高的价值，首先是为“实用拜占庭容错”（Practical Byzantine Fault Tolerance）这一多项式级别复杂度协议的诞生做了一个铺垫；另外，其1/3容错节点数量也被证明为是该类算法的理论上限。
而第二种为“加密消息”的SM(m)协议。该算法与第一种不同之处在于使用签名算法。每个节点都能产生一个不可伪造的签名，并可由其他节点进行验证。当收到消息后，节点会通过签名来判断及验证该消息是否已收到过。最终不再收到消息后，消息共识结束。它同样假设是在一个同步网络内进行；另外，签名身份体系信息需要在网络运行前确定，较难实现扩展。Vitalik近期在其博客上发布了一篇名为《一个99%容错共识的指南》[8]就是根据这一协议在区块链实际场景中所作的适应性改造探索[9]。
3.3. 技术思路分析
与从比特币系统中衍生出的中本聪共识不同，BFT类协议基于节点间传递消息对网络中提案达成共识。因此一般来说消息复杂度较高，而且节点的加入和退出过程需要进行特别处理，但一旦达成共识则形成确定性结果，而不是中本聪共识的概率上的最终一致。
因此基于以上特性，BFT类共识目前在金融场景以及联盟链场景中应用的更多。不过随着研究的探索推进，一些可在公有链场景下使用的BFT共识也正在不断研发出来。
4.BFT类共识概览
我们在已有BFT类共识分类[10][11]的基础上，继续对目前BFT协议进行了梳理。因为BFT协议中的无论是口头协议还是书面协议都不够“实用”，很难在实际场景中直接运用。因此后来学术界和业界对BFT协议有了大量的改进。按照改进思路的不同，这些协议主要可分为以下3大类方向：
1）针对无拜占庭错误场景进行优化
2）针对拜占庭错误场景进行优化
3）为公链应用而做的优化
4.1. 针对无拜占庭错误场景进行优化
此场景假设大部分情况下，网络中的节点运行都正常，拜占庭错误并不经常出现，因此可对这种节点均正常情况下的共识机制进行简化或优化。
下面我们根据不同的优化方法，对这些协议进行分项介绍。
4.1.1. 基于协约的方法
对BFT协议最为经典的改进主要是以PBFT为代表的基于节点协约一致（Agreement）的方法。该类协议通常会有一个主节点作为网络中的枢轴。比其他节点相比，主节点在共识过程中会发出最主要的作用，但通常也会成为系统性能的瓶颈。因为主节点需要将客户端发来的请求排序后发送给所有的备节点。所有节点通过互相通信后达成一致，实现安全性（Safety）；大多数协议中所有节点也会向客户端回复响应，实现活性（Liveness）。该类协议通常需要3f+1个节点来实现对f个拜占庭节点的容错。
实用拜占庭容错（Practical Byzantine Fault Tolerance. 简称PBFT）[12]是早期对其进行的改进，将BFT的消息复杂度从指数级降低为O(n^2)级别，即具备了可实际使用的条件。
PBFT协议将共识过程分为了5个阶段（如果不算与客户端交互的阶段，则可视为3个阶段）：
1）Request阶段是客户端发送信息；
2）在Pre-prepare阶段，主节点接到消息对其签名并分配一个唯一的序号n并将该消息发送给其他节点；
3）Prepare阶段：所有备份节点收到主节点发来的PRE-PREPARE消息后，将一个包含当前视图号v、消息序号n、消息摘要的PREPARE信息发给所有其他节点。如果节点收到了2f个以上的PREPARE消息后则进入到下一阶段并且该消息处于Prepared状态。
4）Commit阶段：每个节点广播一个保护当前视图号v、消息序号n的COMMIT消息。当节点收到2f个相同的COMMIT消息并且小于序号n的消息都已被执行，那么当前消息会被执行并被标记为Committed状态。
5）Reply阶段：所有节点将执行结果返回给客户端。
除了以上阶段流程外，协议运行过程中还涉及到几个重要概念：
1）水位：每个节点在运行协议时会设置一个处理消息的窗口，消息序号在这个区间内的时候才会被处理，例如最小序号设为h、最大序号为H。
2）检查点（Checkpoint）：在运行提交过程中所有已处于已准备好（Prepared）和已提交状态（Committed）的信息会被记录在内存中。节点会定期（每执行k个请求后）记录一个稳定的检查点并截断记录，即每执行k个请求后，会将水位h和H提高k个单位。
3）视图切换（View Change）：但是当节点发现对某个消息的等待超过一定时间后，则认为是主节点失效，会发送视图切换（VIEW-CHANGE）消息并开始视图切换的过程。
4）批量（Batch）:实际执行中会采用的一些优化改进技术，例如批量方式，即实际程序并不是对单个提交来每次运行协议，而是会在以集合形式同时在网络中处理，并通过设置批量大小（Batch Size）的方式来控制处理消息的数量。
在设置了以上运行机制后，尽管消息复杂度仍然较高，PBFT已具备了实际运行的可行性。之后的许多BFT类协议均在PBFT协议基础上进行改进，并将PBFT作为研究对比的基准对象。
Chain协议。Chain协议[13]采用了一个和其名称很相似的链条式传播路径[14]。从主节点开始，每一次传播时即加入该节点的摘要信息。当客户端较多时，Chain通常会比PBFT、Zyzzyva等吞吐量更高。
Ring协议。Ring协议[15]使用环形拓扑方式来传递消息，即每个节点都有消息的上一个发送者和下一个接收者，以此方式来降低对部分节点分配更多工作而形成的性能瓶颈问题。对有无错误的不同场景，Ring分别采用两种运行模式：快速模式（Fast Mode）和弹性模式（Resilient Mode），并采用ABSTRACT框架进行切换[14]。
BFT-SMaRt协议。BFT-SMaRt[16]与PBFT、UpRight[17]类似，但增强了可靠性、模块化程度、同时还提供了灵活的编程接口。
4.1.2. 基于Quorum的方法
Quorum机制是一种分布式系统中常用的机制，用来保证数据冗余和最终一致性的投票算法。其主要思想来源于抽屉原理，常用于分布式系统的读写访问控制[18]。
该类共识协议不需要节点间相互通讯，而是由节点直接执行并响应客户端发来的请求。当受到足够数量的响应后，客户端才会将结果最终提交。但是当出现拜占庭错误场景时，通常会花费较大的代价来解决。另外，由于缺少对请求的排序机制，Quorum方法无法处理有竞争（contention）的情况。
Q/U协议。Q/U协议（Query/Update）[19]是一个典型的基于Quorum的协议。Q/U没有主节点来为请求排序，而是由客户端直接向节点发送请求并由节点反馈结果。它需要5f+1个节点来对f个拜占庭节点容错。
HQ协议（Hybrid Quorum）[20]是另一个较为早期和著名的共识协议。正如其名称，HQ综合参考并优化了Q/U协议和PBFT协议：只需要3f+1个节点进行容错，并针对没有竞争的情况简化了PBFT节点间通讯。当没有竞争情况下，共识主要分为两个阶段：第一阶段是客户端发送请求并收集节点的状态信息；当收到结果表明2f+1个节点状态相同且可以执行请求后，开始第二阶段信息发送、由节点执行请求。而如果发现有竞争，则采用类似PBFT的解决过程，性能也退化为和PBFT类似。
Quorum协议也是基于Quorum机制的一个共识协议[14]，主要没有客户端竞争的非异步网络而进行设计，只需要3f+1个节点进行拜占庭容错。当没有错误产生时，Quorum协议的传播路径和Q/U类似，节点独立执行请求并自己维护一个执行历史记录。当客户端数量较少时，其吞吐量和延迟等性能指标均比其他BFT类共识更好。但其缺点也和Q/U类似，无法处理客户端有竞争的情况[10]。
4.1.3. 基于Speculation的方法
在这类协议中，节点不需要通过需要消耗大量系统代价的3阶段提交过程即可响应客户端的请求。采用了更乐观的策略，节点同意由主节点发出的排序请求并给客户端返回结果。由客户端而不是节点来负责考虑一致性问题。如果发现不一致问题，由客户端负责通知节点回滚至一致状态。
Zyzzyva协议。Zyzzyva是该类中最典型的一个协议[21]。它需要3f+1个节点进行拜占庭容错。与基于Agreement的协议类似，Zyzzyva中的主节点也是将客户端发来的请求排序后转发其他节点。每个节点根据自身历史记录来执行请求并将结果反馈给客户端。客户端根据节点返回的一致性结果数量分别执行不同的动作。
在没有错误的场景下，Zyzzyva表现比PBFT和Q/U等协议要好；但是当有错误时，因为要涉及到和PBFT类似的view change过程，其性能也会急剧下降。
Zeno协议。Zeno协议[22]在Zyzzyva基础上进行修改，将原有的强一致性替换为一个较弱的最终一致性保证。它允许客户端偶尔忽略其他更新，但是当网络不稳定时，所有节点的状态需要进行合并以达成一致。
ZZ协议。ZZ协议[23]同样基于Speculation机制。因其还采用了分离处理的机制，也可将其归为“分离处理一致性与执行请求的阶段”的类别，我们将在后续章节继续介绍。
4.1.4. 基于客户端的方法
基于客户端的方法通过避免节点间通信的方式，来避免异常节点对正常节点的攻击、误导或延迟。协议完全依赖于这些客户端的正确性，假设客户端都没有异常、是诚实且在宕机时会被外部所感知的。
OBFT（Obfuscated BFT）协议[24]是这一类协议的典型代表。它需要3f+1个节点进行容错，但与其他很多BFT协议涉及到节点间通讯不同，OBFT协议中的节点完全不需要关注其他节点并只与客户端联系，因此避免了恶意节点干扰其他正常从而影响系统性能的问题，不过这也带来了一个较强的假设：必须完全信任客户端不会作恶。因此该类协议都存在着较难在实际场景中进行应用的问题。
4.1.5. 基于可信组件的方法
因为FLP不可能性原理（即使网络通讯可靠也无法在任何场景下都能达到共识[25]），一些协议并不使用传统的超时等机制而是基于外部的可信组件进行设计。这些组件也需要被认为是无拜占庭错误的，但允许存在宕机等临时性无法提供服务的情况[11]。基于以上条件，该类协议可以将容错节点数量从3f+1将为2f+1。
例如，CheapBFT协议[26]。需要基于一个叫做CASH的FPGA可信设备，从而降低正常情况下协议对于资源的使用。
4.1.6. 基于拜占庭锁的方法
拜占庭锁是拜占庭协议的扩展，通过利用IO绝大多数时间里不会出现竞争的特性来达到降低服务器响应时间、提高吞吐量与扩展性的效果。
这种方法最早由Zzyzx协议[27]提出，包括加锁和解锁两个部分。加解锁过程均基于现有拜占庭协议达成对客户端授权的一致。当授权完成，则获得锁的客户端可直接进行操作，从而去掉了主节点排序、节点间通讯等操作，从而大幅度提高吞吐量。但当有多个客户端需要频繁切换时，其性能也会大幅下降，因此该协议较为适用于客户端不会频繁发生变化的情况下。
4.1.7. 基于分离一致性与执行请求的方法
还有一类改进方法是将共识与执行提交的过程分开，因为执行客户端请求只需要f+1个（当没有拜占庭节点或者客户端可验证结果正确性时）或2f+1个节点（当有可能存在拜占庭节点且客户端不可验证正确性时），因此可将协议的执行分为2个部分，一部分节点负责一致性共识协议，而另一部分负责执行提交，从而提高吞吐量。
ZZ协议，通过虚拟化技术[23]把节点均正常场景下的执行所需节点数量从2f+1降为f+1个。在没有错误场景时，只通过f+1个节点来执行请求，其余服务器在休息状态；而当执行请求的节点发生错误时，客户端通过虚拟化技术快速启动更多的节点来执行[11]。
ODRC协议也是将执行节点数量将为了f+1，但与ZZ协议不同，它并没有采用额外的虚拟化等技术，而是在BFT协议过程中的节点达成一致后、执行请求前增加了一个选择执行节点的阶段。该阶段根据当前系统状态，选择指定数量的节点执行请求[11]。
4.2. 针对拜占庭错误场景进行优化
上面介绍的一类协议均是针对没有错误的场景对BFT协议进行简化而设计，因此当遇到拜占庭错误时，这类协议的性能一般都会下降比较多，甚至很难保证系统活性。而另一类协议的改进目的是为了有效对拜占庭行为（甚至是一些罕见的行为）进行容错，降低系统在有无拜占庭错误这两种场景下的表现差异。主要有以下几个比较典型的协议。
Aardvark协议。Aardvark协议[28]的通讯过程与PBFT类似，但对许多可能的错误场景设计了适应性机制以保证系统的安全性和活性。这些适应性机制包括：对客户端采用混合签名等机制来防止客户端作恶；更为积极主动的触发view change过程以避免主节点有拜占庭行为；为每个节点设计3f+1个网络接口（其中1个用于其与客户端通信，其余3f个用于节点间通讯），以此隔离网络通道来防止流量攻击。
Prime协议。因为PBFT协议中当主节点作恶的view change过程对性能的影响较大，即便主节点不进行任何主动作恶，只要在处理排序过程中刻意增加延迟就可以降低系统整体性能表现。Prime协议[29]针对此情况进行了改进，在PBFT过程前增加了一个预排序的阶段，包括PO Request、PO ACK、PO ARU等阶段。通过这种分析主节点排序时间的方式，使得所有节点来监控网络表现。因此主节点必须及时将消息发送给其他节点以避免被替换掉。因为引入了额外的阶段，Prime在正常场景中的性能要比PBFT等协议要低；但在存在错误场景中其表现要比其他协议要好。
Spinning协议。Spinning协议[30]在PBFT协议的基础上，设计用来减轻更换主节点的代价。在正常场景中的，Spinning通讯过程与PBFT相同。不过它没有view change过程，而是通过合并操作的方式来收集不同节点信息来决定之前视图中的操作是否应在新视图中执行。
RBFT协议。Redundant-BFT协议[31]利用目前所流行的多核技术来保障鲁棒性。该协议采用与PBFT类似的通讯过程，但在Pre-prepare阶段前增加了一个Propagate阶段。客户端首先将消息发送给f+1个节点，这些节点在Propagate阶段相互传递消息以此来保证客户端请求会被所有正常节点接收到。RBFT执行f+1个同一个协议的多个实例，其中每个实例都对应一个在不同物理机器上运行的主节点，不过只有被主实例所排序的请求才会被有效执行。备份实例运行的意义主要在于监测运行性能：当发现主实例运行缓慢时，备份实例将触发view change过程选择出一个新的主实例。
4.3. 为公链应用优化
传统PBFT及类似协议，其自身的特性导致应用场景有较多限制，例如消息复杂度随节点数成平方级别上升、主节点容易成为系统性能瓶颈、节点列表需要提前固定且节点间相互已知。所以在分布式账本系统中，更多应用于联盟链或私有链场景中。
为了适应公有链场景中的大规模扩展需求，有不少项目进行了有益尝试，具体方式可主要包括与公链共识结合以及基于密码学机制等两大类方式。
4.3.1. 与中本聪共识结合
为了在公有链中利用BFT类共识的结果可快速得到最终确认等优点，一类做法是将BFT类协议与中本聪协议进行结合，以此来取长补短，将BFT类共识引入应用到公有链的业务场景中。
例如，Elaine Shi等在2017年提出将BFT类共识与中本聪共识结合的办法[32]：通过PoW先选出负责共识的委员会（Commitee）；由委员会再进行PBFT过程达成共识并出块[33]。
DPoS+BFT协议也是类似的思路。该协议是BFT类协议与中本聪协议结合的一个典型代表，被用于BM开发的石墨烯[34]“全家桶”平台，包括BitShares[35]、Steemit[36]、EOS[37]等。通证持有者以投票等方式选出自己支持的“代表”，并由这些代表组成的见证人网络通过BFT的方式进行共识。例如EOS中，用户投票产生21个可出块的“超级节点”，以BFT方式共识后轮流出块，对1/3以下的“超级节点”可以容错。基于该类共识协议的平台性能较高，且不需要竞争挖矿等，但缺点是略微中心化。
DBFT协议是NEO提出的授权拜占庭容错协议[38]，和DPoS+BFT思路有些类似，是一种通过代理投票实现大规模参与的共识协议。通证持有者可通过投票选出他所支持的“代理”，然后代理再通过BFT达成共识。因此它也和DPoS+BFT类似，具有快速、扩展性好等特点，但也同样受到共识节点数量有限、中心化程度太高等质疑。
Tendermint BFT协议。Cosmos项目提出了名为Tendermint BFT的一种基于BFT的PoS共识协议[39]。它以加权轮询的方式产生验证者集合，由选出的验证者产生共识提议并进行BFT过程。因此它也是一种在半同步网络中使用的确定性算法[40]。
FBA协议。Stellar使用的恒星共识协议（Stellar Consensus Protocol）的背后是一种联邦拜占庭协议（Federated Byzantine Agreement）。该协议并不是直接把BFT和某一个中本聪共识结合，而是参考了中本聪对比特币的设计理念。该协议实现一个开放式的节点成员列表，任何人都可以加入。网络中的每个节点可自行选择其Quorum，降低对非理性行为的容忍程度，所以其性能和可扩展性都较为突出，但一些拜占庭行为也可能导致分叉等情况发生，因此节点需要花费不少代价去设置其所信任的节点列表。
还有一些项目在尝试探索把BFT协议引入当前公链平台中，例如Istanbul BFT（IBFT）[41]就是通过引入验证者（validator）并基于Quorum机制运行，并被探索用于当前以太坊平台。
除了狭义的“区块链”方式外，Hashgraph[42]也可认为是一种BFT类共识与DAG结合的协议。它通过gossip about gossip降低通信量，并且也是异步的BFT协议。
4.3.2. 基于密码学优化
另一种可运用于公链的思路是利用密码学的方法，包括聚合签名、可验证随机函数、门限签名等，以达到降低BFT类共识的通讯代价、提高共识效率的目的。
聚合签名
E.Kokoris-Kogias等在其论文中提出了在共识机制中使用聚合签名的方法。论文中提到的ByzCoin[43]以数字签名方式替代原有PBFT使用的MAC将通讯延迟从O(n^2)降低至O(n)；使用聚合签名方式将通讯复杂度进一步降低至O(logn)。但ByzCoin在主节点作恶或33%容错等方面仍有局限。
之后一些公链项目，例如Zilliqa[44]等基于这种思想，采用EC-Schnorr多签算法提高PBFT过程中Prepare和Commit阶段的消息传递效率，并结合分片等优化技术以希望突出改进公有链平台TPS。
Gosig[45]也使用该方法，同时还结合了Algorand以VRF方式选择“Leader”和多轮投票等方法来尽量降低Leader作恶可能性。
可验证随机函数
Algorand的BA★协议[46]使用了另一种密码学方法——可验证随机函数（VRF），以加密抽签的形式随机决定“验证者”，并以带有权重的方式来全网共识，可认为是BFT类共识+PoS或PoWeight的架构。投票过程分为两个阶段：第一阶段通过一个分级共识选出“验证者”共识最多的候选区块；第二阶段运行一个二元拜占庭协议（接受出块或产生空块）。执行速度很快，不太容易产生分叉且交易确认时间虽用户数增加变化不大[33]。另外，Algorand通过加密方式隐藏了“领导者”的真实身份，提高了针对Leader攻击的安全性。
VBFT协议也是使用VRF的一个共识协议[47]，由Ontology提出，可认为是PoS+VRF+BFT：在共识协议的各个阶段，分别使用VRF从网络中选出该阶段所需要的节点，例如提案节点、验证节点、确认节点等并完成最终的共识。其中的选择参数是根据PoS来确定。
门限签名
以上介绍的协议大部分都需要假设基于一个同步或半同步的网络环境，而HoneyBadger BFT是第一个知名的异步BFT类协议[48]，可在消息延迟没有明确上限的异步网络中运行。它首先将交易拆分为多份，各个节点间相互，减轻发起节点的消息发送瓶颈问题。而因为其异步网络环境，节点间收到交易是非同步的、随机顺序的。节点以二元拜占庭协议剔除无效交易和重复交易等后，得到一个异步公共交易子集（Asynchronous Common Subset）[49]。
而门限加密使得只有f+1个诚实节点共同合作才能解密出消息原文，防止恶意节点对于最终交易集的攻击。HoneyBadger BFT协议的主要限制是其在异步网络下为一个非确定性共识算法（FLP不可能性原理[25]）。
5. 实测对比
除了进行理论上的归纳总结与分析外，我们选用PBFT、Zyzzyva、Zilliqa协议，编写共识协议的程序进行实测模拟。通过横向与纵向的测试比较，以期得出以上共识协议的技术建议。
5.1. 测试方案介绍
由于共识协议都需要基于一个实际的应用场景，我们在程序中将节点处理计算的过程设定为一个固定的延时；消息传输采用消息队列方式来实现。程序基于Java 8编写实现。
因为PBFT、Zilliqa等共识协议在一些实现细节上缺少明确描述，我们在实现程序时进行了以下设定：
1）节点之间的网络时延在5-10毫秒内
2）网络带宽设置为100MB（假设每条请求消息平均100B大小）
5.2. 场景1：节点均正常的横向比较
首先在所有节点均为诚实节点的情况下，我们进行多组实测，横向比较PBFT、Zyzzyva、Zilliqa共识协议在不同情况下的协议吞吐量、网络中平均消息量、达成共识总时长等性能指标。
本场景的第1组测试条件为：
1）批量大小= 10
2）水位大小=30
3）检查点周期=10
4）客户端数量=1，消息发送间隔=1ms
横向比较的结果（其中吞吐量和网络平均消息量单位均为消息笔数，下同）如下：
整体来看，BFT类协议的吞吐量确实均会随着节点数增加而下降（性能降低），当节点数量过多时，很难完成处理。
对于PBFT协议，可看到其消息量和节点数量确实有平方级的关系（本例中约为6*n^2）；
而Zyzzyva和Zilliqa的消息量为线性关系，即以上协议的方法确实会降低PBFT消息量大的问题。
由于批量大小会影响网络中处理消息的数量，因此我们在第2组观察批量大小对性能的影响。测试条件为：
1）节点数=22
2）水位大小=30
3）检查点周期=10
4）客户端数量=1，消息发送间隔=1ms
从结果可以看出，增加批量大小对吞吐量均有较为明显的提升，但也会增加网络中的消息量。其中，Zilliqa的吞吐量提升最为明显，因为该算法可以在一个单位时间内进行聚合签名并且可以批量验证，即批量大小相当于打包区块的大小。所以当总带宽允许的情况下，Zilliqa算法可以通过增加批量而获取极大的吞吐量。
PBFT和Zyzzyva提升到一定阶段后在实测中会遇到瓶颈（批量数>30后，吞吐量始终接近1000），原因是本次测试客户端消息间隔导致。如果降低发送间隔或者增加客户端数量均可提高吞吐量。例如，当假设消息可并行处理且没有到达网络带宽瓶颈，增加客户端可得到如下PBFT的性能结果为：
5.3. 场景2：节点异常时的横向比较
BFT类协议的一个复杂之处在于部分节点存在拜占庭行为情况下的处理，各个协议对不同数量的异常节点，该情况下的效率可能也不一样。
在本场景中我们设置节点数固定为22个。
本场景第1组测试设置条件为：
1）批量大小=10
2）水位大小=30
3）检查点周期=10
4） 客户端数量=1
经过测试PBFT、Zyzzyva、Zilliqa的吞吐量分别为：
其中，可看到PBFT吞吐量和共识时间都优于Zyzzyva和Zilliqa，是因为本次测试暂忽略了网络消息量增大对消息传播延迟的影响。
从结果也可看到网络平均消息量会减小，尤其是PBFT的消息量会随着节点增多而降低较快。其原因是当出现拜占庭节点时，作恶节点的消息会被忽略掉；而同时，消息传播和达成共识的时间会相应延长。
5.4. 场景3：PBFT测试研究
下面的几个场景我们对比PBFT的批量、检查点周期与吞吐量、网络中平均消息量以及达成共识时间等性能表现之间的关系。
1）节点数=22
2）水位大小=50
可以看到，对于PBFT来说，检查点周期调整对性能的影响并没有太大；而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间，不过同时也会加大消息量对网络造成压力。
5.5. 场景4：Zyzzyva测试研究
从上述场景已可看到，调整批量大小会对共识性能产生影响；而Zyzzyva的主节点负责接收各客户端发来的请求，因此在客户端数量不同的情况下，表现可能也会不一样。因此我们针对不同的批量大小和客户端数量进行分析研究。
从结果可以看到，当批量数较小时，增加客户端数量后，Zyzzyva整体性能并没有太大改观。
当增大批量后，Zyzzyva的吞吐量提高较为明显；在增加客户端数量后，吞吐量和共识时间均有改观，但在增加一定程度后其表现并不会继续提升。
另外和PBFT类似，增加客户端数量或增大批量后，Zyzzyva的网络消息也会随之增加。
5.6. 场景5：Zilliqa测试研究
从场景1的测试中可看出，Zilliqa的Batch可以设置的远比PBFT大从而获得极大的吞吐量，因此与前两个纵向对比测试略有不同，本场景测试着眼点在网络带宽消耗上。在不同Batch下，我们测试研究Zilliqa的消耗情况（以PBFT作为一个基准对比）。
测试条件为：
1）节点数=22
2）检查点周期=10
3）消息大小=100B
可以看到，尽管可设置较大的批量数来获得更高的吞吐量，但Zilliqa的最大带宽消耗也会随着批量数而线性增长。作为对比，PBFT在批量数到达一定数量后，最大消耗带宽会趋于稳定。因此在实际应用共识协议时，应充分考虑好选用的共识协议以及实际网络带宽情况。
6.参考资料
[1] M. van Steen and A. S. Tanenbaum,Distributed Systems, 3.01. 2017.
[2] S. Gilbert and N. Lynch, “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services,”ACM SIGACT News, 2002.
[3] S. Gilbert and N. Lynch, “Perspectives on the CAP Theorem,”Computer (Long. Beach. Calif)., vol. 45, no. 2, pp. 30–36, 2012.
[4] L. Lamport, R. Shostak, and M. Pease, “The Byzantine Generals Problem,”ACM Trans. Program. Lang. Syst., 1982.
[5] LoomNetwork, “了解区块链的基本（第一部分）：拜占庭容错(Byzantine Fault Tolerance),” 2018. [Online]. Available: https://segmentfault.com/a/1190000014009235.
[6] bangerlee, “[上篇] 大话分布式系统理论基础.” [Online]. Available: https://mp.weixin.qq.com/s/p4PEZPjxJyYXKpkCCdShbw.
[7] 初夏虎, “拜占庭将军问题深入探讨,” 2015. [Online]. Available: https://www.8btc.com/article/70370.
[8] V. Buterin, “A Guide to 99% Fault Tolerant Consensus,” 2018. [Online]. Available: https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html.
[9] 袁煜明 and 胡智威, “【火线视点10】Vitalik的‘99%容错共识算法’解析.”
[10] D. Gupta, L. Perronne, and S. Bouchenak, “BFT-Bench: Towards a practical evaluation of robustness and effectiveness of BFT protocols,” inLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2016.
[11] J. FAN, L.-T. YI, and J.-W. SHU, “Research on the Technologies of Byzantine System,”J. Softw., vol. 24, no. 6, pp. 1346–1360, 2014.
[12] M. Castro and B. Liskov, “Practical byzantine fault tolerance and proactive recovery,”ACM Trans. Comput. Syst., 2002.
[13] R. van Renesse and F. B. Schneider, “Chain Replication for Supporting High Throughput and Availability,”Proc. 6th Conf. Symp. Opearting Syst. Des. Implement. - Vol. 6, 2004.
[14] P.-L. Aublin, R. Guerraoui, N. Knežević, V. Quéma, and M. Vukolić, “The Next 700 BFT Protocols,”ACM Trans. Comput. Syst., vol. 32, no. 4, pp. 1–45, 2015.
[15] R. Guerraoui, N. Knezevic, V. Quema, and M. Vukolic, “Stretching BFT,” 2010.
[16] A. Bessani, J. Sousa, and E. E. P. Alchieri, “State machine replication for the masses with BFT-SMART,” inProceedings - 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2014, 2014.
[17] A. Clementet al., “Upright cluster services,” inProceedings of the ACM SIGOPS 22nd symposium on Operating systems principles - SOSP ’09, 2009.
[18] Wikipedia, “Quorum (distributed computing).” [Online]. Available: https://en.wikipedia.org/wiki/Quorum_(distributed_computing).
[19] M. Abd-El-Malek, G. R. Ganger, G. R. Goodson, M. K. Reiter, and J. J. Wylie, “Fault-scalable Byzantine fault-tolerant services,” inProceedings of the twentieth ACM symposium on Operating systems principles - SOSP ’05, 2005.
[20] B. Bershad, D. ACM Digital Library., B. ACM Special Interest Group in Operating Systems., R. Rodrigues, and L. Shrira, “HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance,”Proc. 7th Symp. Oper. Syst. Des. Implement., p. 407, 2006.
[21] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong, “Zyzzyva: Speculative Byzantine Fault Tolerance,”Proc. Symp. Oper. Syst. Princ., pp. 45–58, 2007.
[22] A. Singh, P. Fonseca, and P. Kuznetsov, “Zeno: Eventually Consistent Byzantine-Fault Tolerance.,”Nsdi, pp. 169–184, 2009.
[23] T. Wood, R. Singh, A. Venkataramani, P. Shenoy, and E. Cecchet, “ZZ and the art of practical BFT execution,” inProceedings of the sixth conference on Computer systems - EuroSys ’11, 2011.
[24] A. Shoker, J. P. Bahsoun, and M. Yabandeh, “Improving independence of failures in BFT,” inProceedings - IEEE 12th International Symposium on Network Computing and Applications, NCA 2013, 2013.
[25] M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,”J. ACM, 1985.
[26] R. Kapitzaet al., “CheapBFT: Resource-efficient Byzantine Fault Tolerance,”Proc. 7th ACM Eur. Conf. Comput. Syst., 2012.
[27] J. Hendricks, S. Sinnamohideen, G. R. Ganger, and M. K. Reiter, “Zzyzx: Scalable fault tolerance through Byzantine locking,” inProceedings of the International Conference on Dependable Systems and Networks, 2010.
[28] A. Clement, E. Wong, L. Alvisi, M. Dahlin, and M. Marchetti, “Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults,”Symp. A Q. J. Mod. Foreign Lit., 2009.
[29] Y. Amir, B. Coan, J. Kirsch, and J. Lane, “Prime: Byzantine replication under attack,”IEEE Trans. Dependable Secur. Comput., 2011.
[30] G. S. Veronese, M. Correia, A. N. Bessani, and L. C. Lung, “Spin one’s wheels? Byzantine fault tolerance with a spinning primary,” inProceedings of the IEEE Symposium on Reliable Distributed Systems, 2009.
[31] P. L. Aublin, S. Ben Mokhtar, and V. Quema, “RBFT: Redundant byzantine fault tolerance,” inProceedings - International Conference on Distributed Computing Systems, 2013.
[32] R. Pass and E. Shi, “Hybrid consensus: {Efficient} consensus in the permissionless model,”Leibniz {Int}. {Proc}. {Informatics}, {LIPIcs}, 2017.
[33] 姚前, 数字货币初探. 中国金融出版社, 2018.
[34] “Graphene Technical Documentation.” [Online]. Available: http://docs.bitshares.org/.
[35] “BitShares Whitepapers.” [Online]. Available: http://docs.bitshares.org/bitshares/papers/.
[36] “Steem Whitepaper.” [Online]. Available: https://steem.io/steem-whitepaper.pdf.
[37] “EOS.IO Technical White Paper v2.” [Online]. Available: https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.
[38] NEO, “A Byzantine Fault Tolerance Algorithm for Blockchain.” [Online]. Available: http://docs.neo.org/en-us/basic/consensus/whitepaper.html.
[39] “Cosmos Whitepaper.” [Online]. Available: https://github.com/cosmos/cosmos/blob/master/WHITEPAPER.md.
[40] C. Unchained, “Tendermint Explained — Bringing BFT-based PoS to the Public Blockchain Domain.” [Online]. Available: https://blog.cosmos.network/tendermint-explained-bringing-bft-based-pos-to-the-public-blockchain-domain-f22e274a0fdb.
[41] Z.-C. Lin, “Istanbul BFT (IBFT).” [Online]. Available: https://medium.com/getamis/istanbul-bft-ibft-c2758b7fe6ff.
[42] H. Hashgraph, “Hedera: A Governing Council & Public Hashgraph Network.” [Online]. Available: https://s3.amazonaws.com/hedera-hashgraph/hh-whitepaper-v1.1-180518.pdf.
[43] E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford, “Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing,” 2016.
[44] T. Z. Team, “Zilliqa Technical Whitepaper,”Zilliqa, pp. 1–8, 2017.
[45] P. Li, G. Wang, X. Chen, and W. Xu, “Gosig: Scalable Byzantine Consensus on Adversarial Wide Area Network for Blockchains,” 2018.
[46] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich, “Algorand: Scaling byzantine agreements for cryptocurrencies,”Proc. 26th Symp. Oper. Syst. Princ., 2017.
[47] “VBFT算法介绍.” [Online]. Available: https://github.com/ontio/documentation/blob/master/vbft-intro/vbft-intro-CN.md.
[48] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song, “The Honey Badger of BFT Protocols,” inProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security - CCS’16, 2016.
[49] Juniway, “Honey Badger of BFT 协议详解.” [Online]. Available: https://www.jianshu.com/p/15d5b6f968d9.
报告全文下载：
【超越白皮书5】BFT类共识协议概览与分析实测 | 火币区块链研究院
火币区块链应用研究院
关于我们：
火币区块链应用研究院（简称“火币研究院”）成立于2016年4月，于2018年3月起全面拓展区块链各领域的研究与探索，主要研究内容包括区块链领域的技术研究、行业分析、应用创新、模式探索等。我们希望搭建涵盖区块链完整产业链的研究平台，为区块链产业人士提供坚实的理论基础与趋势判断，推动整个区块链行业的发展。
联系我们：
咨询邮箱：huobiresearch@huobi.com
简书公众号：火币区块链研究院
Twitter:Huobi_Research
https://twitter.com/Huobi_Research
Medium:HuobiResearch
https://medium.com/@huobiresearch
Facebook:HuobiResearch
https://www.facebook.com/Huobi-Research-655657764773922
Website:http://research.huobi.com/
免责声明：
1. 火币区块链研究院与本报告中所涉及的数字资产或其他第三方不存在任何影响报告客观性、独立性、公正性的关联关系。
2. 本报告所引用的资料及数据均来自合规渠道，资料及数据的出处皆被火币区块链研究院认为可靠，且已对其真实性、准确性及完整性进行了必要的核查，但火币区块链研究院不对其真实性、准确性或完整性做出任何保证。
3. 报告的内容仅供参考，报告中的事实和观点不构成相关数字资产的任何投资建议。火币区块链研究院不对因使用本报告内容而导致的损失承担任何责任，除非法律法规有明确规定。读者不应仅依据本报告作出投资决策，也不应依据本报告丧失独立判断的能力。
4. 本报告所载资料、意见及推测仅反映研究人员于定稿本报告当日的判断，未来基于行业变化和数据信息的更新，存在观点与判断更新的可能性。
5. 本报告版权仅为火币区块链研究院所有，如需引用本报告内容，请注明出处。如需大幅引用请事先告知，并在允许的范围内使用。在任何情况下不得对本报告进行任何有悖原意的引用、删节和修改。
