本报告由火币区块链研究院出品，报告发布时间2018年9月6日，作者：袁煜明、胡智威。
摘要
本文首先对 BFT 类共识协议按照改进思路分为 3 大类进行综述性概览：
针对无拜占庭错误场景优化的协议，包括 PBFT、Zyzzyva 等等
针对拜占庭错误场景优化的，包括 Aardvark、Primer 等等
为公链应用而优化的协议，包括 DPoS+BFT、Zilliqa 等等
本文还选用 PBFT、Zyzzyva、Zilliqa 协议，编写程序进行实测，主要得到以下结果及技术指导建议:
Zyzzyva 和 Zilliqa 等协议的网络通讯量确实比 PBFT 降低很多。
调整 PBFT 检查点周期对性能没有太大影响；而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间，不过同时也会加大消息量对网络造成压力。
Zyzzyva 在其客户端足够的情况下，增加批量数会对吞吐量和共识时间等性能指标均有较大提升。
虽然增加批量数对 Zilliqa 等协议都有促进效果，但这也会增加带宽占用。在设计共识协议时应综合考虑性能目标与网络带宽等实际情况。
报告正文
1. 引言
共识协议被许多人视为是区块链项目的核心。无论是对区块链平台的交易处理能力、扩展性影响还是对通证经济的激励模型设计，共识协议都会产生很大影响。
共识协议从大的方面可分为自比特币诞生以来产生的 PoW 等中本聪共识协议和拜占庭容错（BFT）类共识协议这两大类协议。其中，在计算机科学的分布式系统研究领域已较多研究的 BFT 类共识协议近年来被越来越多的应用于联盟链平台。与此同时，也有越来越多的研发工作尝试将 BFT 应用于公链平台。
我们在本文中对 BFT 类协议进行了综述性概览分析，并从改进思路上将现有BFT 类共识协议分为 3 大类：针对无拜占庭错误场景优化的协议、针对拜占庭错误场景优化的协议以及为公链应用而优化的协议；另外选用了 PBFT、Zyzzyva、Zilliqa 协议，编写程序并运行后得到实测对比结果，对共识协议的具体设计提供一些技术性指导建议。
2. 主要结论
经过研究与测试分析，我们得到以下主要结论及技术建议：
·Zyzzyva 和 Zilliqa 等协议的网络通讯量确实比 PBFT 降低很多。
·对 PBFT，调整检查点周期对性能没有太大影响；而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间，不过同时也会加大消息量对网络造成压力。
·Zyzzyva 在其客户端足够的情况下，增加批量数会对吞吐量和共识时间等性能指标均有较大提升。
·虽然增加批量数对 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 大类方向：
·针对无拜占庭错误场景进行优化
·针对拜占庭错误场景进行优化
·为公链应用而做的优化
4.1.针对无拜占庭错误场景进行优化
此场景假设大部分情况下，网络中的节点运行都正常，拜占庭错误并不经常出现，因此可对这种节点均正常情况下的共识机制进行简化或优化。
下面我们根据不同的优化方法，对这些协议进行分项介绍。
4.1.1.基于协约的方法
对 BFT 协议最为经典的改进主要是以 PBFT 为代表的基于节点协约一致（Agreement）的方法。该类协议通常会有一个主节点作为网络中的枢轴。比其他节点相比，主节点在共识过程中会发出最主要的作用，但通常也会成为系统性能的瓶颈。因为主节点需要将客户端发来的请求排序后发送给所有的备节点。所有节点通过互相通信后达成一致，实现安全性（Safety）；大多数协议中所有节点也会向客户端回复响应，实现活性（Liveness）。该类协议通常需要 3f+1 个节点来实现对 f 个拜占庭节点的容错。
实用拜占庭容错（Practical Byzantine Fault Tolerance. 简称 PBFT）[12]是早期对其进行的改进，将 BFT 的消息复杂度从指数级降低为O(n2)级别，即具备了可实际使用的条件。
PBFT 协议将共识过程分为了 5 个阶段（如果不算与客户端交互的阶段，则可视为 3 个阶段）：
·Request 阶段是客户端发送信息；
·在 Pre-prepare 阶段，主节点接到消息对其签名并分配一个唯一的序号n 并将该消息发送给其他节点；
·Prepare 阶段：所有备份节点收到主节点发来的 PRE-PREPARE 消息后，将一个包含当前视图号 v、消息序号 n、消息摘要的 PREPARE 信息发给所有其他节点。如果节点收到了 2f 个以上的 PREPARE 消息后则进入到下一阶段并且该消息处于 Prepared 状态。
·Commit 阶段：每个节点广播一个保护当前视图号 v、消息序号 n 的 COMMIT 消息。当节点收到 2f 个相同的 COMMIT 消息并且小于序号 n的消息都已被执行，那么当前消息会被执行并被标记为 Committed 状态。
·Reply 阶段：所有节点将执行结果返回给客户端。
除了以上阶段流程外，协议运行过程中还涉及到几个重要概念：
·水位：每个节点在运行协议时会设置一个处理消息的窗口，消息序号在这个区间内的时候才会被处理，例如最小序号设为 h、最大序号为 H。
·检查点（Checkpoint）：在运行提交过程中所有已处于已准备好（Prepared）和已提交状态（Committed）的信息会被记录在内存中。节点会定期（每执行 k 个请求后）记录一个稳定的检查点并截断记录，即每执行 k 个请求后，会将水位 h 和 H 提高 k 个单位。
·视图切换（View Change）：但是当节点发现对某个消息的等待超过一定时间后，则认为是主节点失效，会发送视图切换（VIEW-CHANGE）消息并开始视图切换的过程。
·批量（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(n2)降低至o(logn)；使用聚合签名方式将通讯复杂度进一步降低
至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 等共识协议在一些实现细节上缺少明确描述，我们在实现程序时进行了以下设定：
·节点之间的网络时延在 5-10 毫秒内
·网络带宽设置为 100MB（假设每条请求消息平均 100B 大小）
5.2.场景 1：节点均正常的横向比较
首先在所有节点均为诚实节点的情况下，我们进行多组实测，横向比较 PBFT、Zyzzyva、Zilliqa 共识协议在不同情况下的协议吞吐量、网络中平均消息量、达成共识总时长等性能指标。
本场景的第 1 组测试条件为：
·批量大小= 10
·水位大小=30
·检查点周期=10
·客户端数量=1，消息发送间隔=1ms
横向比较的结果（其中吞吐量和网络平均消息量单位均为消息笔数，下同）如下：
整体来看，BFT 类协议的吞吐量确实均会随着节点数增加而下降（性能降低），当节点数量过多时，很难完成处理。
对于 PBFT 协议，可看到其消息量和节点数量确实有平方级的关系（本例中约为6*n2）；
而 Zyzzyva 和 Zilliqa 的消息量为线性关系，即以上协议的方法确实会降低PBFT 消息量大的问题。
由于批量大小会影响网络中处理消息的数量，因此我们在第 2 组观察批量大小对性能的影响。测试条件为：
·节点数=22
·水位大小=30
·检查点周期=10
·客户端数量=1，消息发送间隔=1ms
从结果可以看出，增加批量大小对吞吐量均有较为明显的提升，但也会增加网络中的消息量。其中，Zilliqa 的吞吐量提升最为明显，因为该算法可以在一个单位时间内进行聚合签名并且可以批量验证，即批量大小相当于打包区块的大小。所以当总带宽允许的情况下，Zilliqa 算法可以通过增加批量而获取极大的吞吐量。
PBFT 和 Zyzzyva 提升到一定阶段后在实测中会遇到瓶颈（批量数>30 后，吞吐量始终接近 1000），原因是本次测试客户端消息间隔导致。如果降低发送间隔或者增加客户端数量均可提高吞吐量。例如，当假设消息可并行处理且没有到达网络带宽瓶颈，增加客户端可得到如下 PBFT 的性能结果为：
5.3.场景 2：节点异常时的横向比较
BFT 类协议的一个复杂之处在于部分节点存在拜占庭行为情况下的处理，各个协议对不同数量的异常节点，该情况下的效率可能也不一样。
在本场景中我们设置节点数固定为 22 个。
本场景第 1 组测试设置条件为：
·批量大小=10
·水位大小=30
·检查点周期=10
·客户端数量=1
经过测试 PBFT、Zyzzyva、Zilliqa 的吞吐量分别为：
其中，可看到 PBFT 吞吐量和共识时间都优于 Zyzzyva 和 Zilliqa，是因为本次测试暂忽略了网络消息量增大对消息传播延迟的影响。
从结果也可看到网络平均消息量会减小，尤其是 PBFT 的消息量会随着节点增多而降低较快。其原因是当出现拜占庭节点时，作恶节点的消息会被忽略掉；而同时，消息传播和达成共识的时间会相应延长。
5.4.场景 3：PBFT 测试研究
下面的几个场景我们对比 PBFT 的批量、检查点周期与吞吐量、网络中平均消息量以及达成共识时间等性能表现之间的关系。
·节点数=22
·水位大小=50
可以看到，对于 PBFT 来说，检查点周期调整对性能的影响并没有太大；而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间，不过同时也会加大消息量对网络造成压力。
5.5.场景 4：Zyzzyva 测试研究
从上述场景已可看到，调整批量大小会对共识性能产生影响；而 Zyzzyva的主节点负责接收各客户端发来的请求，因此在客户端数量不同的情况下，表现可能也会不一样。因此我们针对不同的批量大小和客户端数量进行分析研究。
从结果可以看到，当批量数较小时，增加客户端数量后，Zyzzyva 整体性能并没有太大改观。
当增大批量后，Zyzzyva 的吞吐量提高较为明显；在增加客户端数量后，吞吐量和共识时间均有改观，但在增加一定程度后其表现并不会继续提升。
另外和 PBFT 类似，增加客户端数量或增大批量后，Zyzzyva 的网络消息也会随之增加。
5.6.场景 5：Zilliqa 测试研究
从场景 1 的测试中可看出，Zilliqa 的 Batch 可以设置的远比 PBFT 大从而获得极大的吞吐量，因此与前两个纵向对比测试略有不同，本场景测试着眼点在网络带宽消耗上。在不同 Batch 下，我们测试研究 Zilliqa 的消耗情况（以 PBFT 作为一个基准对比）。
测试条件为：
·节点数=22
·检查点周期=10
·消息大小=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,” in LectureNotes 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,” 2
010.
[16] A. Bessani, J. Sousa, and E. E. P. Alchieri, “State machine replication for the masses with BFT-SMART,” in Proceedings – 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2014, 2014.
[17] A. Clement et al., “Upright cluster services,” in Proceedings 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,” in Proceedings of thetwentieth 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,” in Proceedings of the sixth conference on Computer systems – EuroSys ’11, 2011.
[24] A. Shoker, J. P. Bahsoun, and M. Yabandeh, “Improving independence offailures in BFT,” in Proceedings – 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. Kapitza et 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,” in Proceedings 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,” in Proceedings of the IEEE Symposium on Reliable Distributed Systems, 2009.
[31] P. L. Aublin, S. Ben Mokhtar, and V. Quema, “RBFT: Redundant byzantine fault tolerance,” in Proceedings – International Conference on Distributed
[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,” in Proceedings 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.
