快速响应的高效多值拜占庭共识方案

周旺，胡红钢，俞能海

快速响应的高效多值拜占庭共识方案

周旺1,2，胡红钢1,2，俞能海1,2

（1.中国科学院电磁空间信息重点实验室，安徽 合肥 230027；2. 中国科学技术大学网络空间安全学院，安徽 合肥 230027）

由于网络设备的增多和传输环境的不确定性，消息时延同样具有不确定性，异步共识协议发挥出更多优势。Miller等于2016年提出第一个异步共识协议HoneyBadgerBFT，但其在实现高吞吐量的同时传输效率依然可以再优化。针对HoneyBadgerBFT中的广播协议进行改进，减少广播过程中的消息复杂度，同时增加可选的消息请求过程，以达到快速响应和高效传输的效果。

快速响应；高传输效率；拜占庭协议；共识方案

1 引言

自2008年中本聪首次提出比特币[1]的概念后，区块链作为其底层技术也被广泛关注。区块链本质上是一个分布式数据库，同时具有去中心化、开放性、自治性、信息不可篡改和匿名性这五大特性。区块链系统与传统数据库系统的区别在于其能够在不依赖第三方的情况下，在分布式环境中正确运行，其核心之一是共识机制，即如何在一组节点之间达成消息的一致。

对于共识机制的研究一直热度不减，从20世纪70年代末开始，研究人员便对分布式系统中的容错问题进行了深入研究。对于宕机容错（CFT）问题，Lamport于1989年做出了开拓性的工作，提出了一个新的状态机复制协议—— Paxos[2]，并在2001年进行了解释[3]。1982年，Lamport等提出了一个新的问题——拜占庭将军问题[4]，对于新的拜占庭容错（BFT）问题，Castro和Liskov于1999提出了著名的PBFT[5]方案。2008年以后，随着比特币的关注度升高，同时由于其使用的工作量证明（PoW）机制的公平性，实现简单，PoW受到追捧，以太坊[6]、莱特币等部分主流“数字货币”使用的均是PoW机制。但鉴于其消耗大量计算资源与电力资源，相关社区一直在寻找PoW的替代机制。权益证明（PoS）依据系统中的稀缺资源，如资金，选取出块者，抵抗女巫攻击的同时不用消耗大量资源，并且近些年来有研究人员提出了可证明安全的PoS协议[7-9]，所以PoS机制正逐渐被区块链系统设计者考虑使用。为了解决共识机制的可拓展性与低吞吐量问题，一系列新的方案与机制被提出[10-13]，所以对于共识的研究会根据应用场景、需求的变化一直持续下去。

上述协议为保证可用性大多需要弱同步甚至同步环境的假定，但当底层网络由于某些原因导致消息转发缓慢甚至停止时，同步协议的性能将明显下降，异步共识协议在这种环境下展示出较大优势。HoneybadgerBFT[14]是由 Miller等于2016年提出的第一个异步拜占庭协议，但协议过程中传输效率可进一步优化，文献[15]直接将HoneybadgerBFT中的异步公共子集（ACS）协议作为一个单独模块，提出一种“先共识消息哈希，后请求缺失消息”的共识思路，单位传输代价优于HoneybadgerBFT。但文献[15]对消息先通过广播哈希值，接收多个签名的方式进行处理，增加了时间消耗，无法快速响应共识请求。本文则对ACS协议进行改进，替换其中的广播子模块，增加可选的消息请求模块，避免对消息预处理的同时减小带宽消耗，达到快速响应、高效传输的效果。

2 预备知识

2.1 时间假设

底层网络可能因为拥堵或攻击导致消息转发缓慢，甚至由于恶意节点的操作使消息停止转发，这使共识协议的设计、运行变得愈加困难。研究人员针对不同应用需求，根据消息延迟的界定义了不同的时间假设。

1) 同步：发送的每个消息最多在延迟一段时间后收到，即消息的延迟存在上界。

2) 部分同步[16]：有两种不同的情形。第一种是网络存在最大延迟，但对于参与者是未知的；第二种是在一个未知时间（被称为全局标准时间，GTS）后，网络变为完全同步。

3) 弱同步：延迟的界随时间变化，但增长速度不会比时间的多项式函数级快。

4) 异步：消息的延迟没有上界，但诚实用户之间发送的消息最终会达到。

2.2 HoneyBagerBFT

HoneyBadgerBFT协议是Miller等在2016年提出的一种BFT协议。其作为第一个异步的BFT共识协议，完全不依赖于网络中对时间条件的假设。与传统的PBFT共识协议相比，当节点增加时，效率不会明显下降。

HoneyBadgerBFT由两个模块组成：门限加密（TPKE）模块和异步公共子集（ACS）模块。ACS模块负责最终交易集合的共识，TPKE模块保证协议的公平性，防止有针对性的审查攻击。ACS模块也由两个模块组成：可靠广播（RBC[17]）模块和二元共识（ABA）模块。RBC模块将每个节点提出的建议值广播给其他节点，ABA模块对所有节点之间在个比特上达成共识，第个比特为1，代表节点提出的建议值被包含在最终交易集合中。本文关注ACS协议中的RBC模块，ACS协议及RBC协议流程如下。

//系统维护个RBC实例，个ABA实例

输入 每个节点的建议值

输出 所有建议值的一个子集

3) 当已向−个ABA实例提供过输入，则将0作为未提供输入的ABA实例的输入；

4) 当所有ABA实例均已完成，取输出为1的ABA实例对应RBC输出的并集作为最终共识的交易集合。

5)当收到+1个匹配的READY()，若还未发送过READY消息，则广播READY()。

6) 当收到2+1个匹配的READY()，等待−2个ECHO消息，解码恢复。

2.3 AVID-FP

AVID-FP[18]是Hendricks于2007年提出的用于优化纠删码带宽的方案，其使用同态指纹作为每次广播的信息。同态指纹保持了纠删码的结构，允许每个编码块可以单独验证其是否对应特定的原信息，于是每个节点均可以利用首次收到的编码块以及对应的指纹信息验证收到的编码块的正确性，同时仅需在之后的广播消息中加入指纹信息即可确保所有诚实节点拥有的编码块对应于同一个原信息，由于其带宽消耗最优，文献[19]中使用AVID-FP作为线性存储的实现方案。AVID-FP协议流程如下。

AVID-FP协议流程

//客户端分发消息

//客户端恢复消息

1)向所有服务器发送消息恢复请求（RETRIEVED）；

3)当收到的对应的编码块数量为时，恢复消息。

//服务器端

2)当从其他服务器收到（ECHO，fpcc），若ECHO消息数为+，并且READY消息数少于+1，则向其他服务器广播（READY，fpcc）。

3) 当从其他服务器收到（READY，fpcc），若READY消息数为+1，并且ECHO消息数小于+，则向其他服务器广播（READY，fpcc）；

5) 当从客户端收到消息恢复请求（RETRIEVED）时，向客户端发送（VERIFIED，echoed）。

3 协议设计

在RBC广播协议中，为了验证每个收到的广播消息的正确性，即是否对应于特定原消息，在广播消息中需加入编码块、对应的默克尔树根以及默克尔树路径信息，所以，对于大小不可忽略的输入，RBC协议执行时将占用大量带宽。文献[15]直接将ACS协议作为单独的模块，并依据本地节点的消息和最终建议值集合中的消息有交集的假定，对消息哈希先签名后广播，在收到多个签名后组成建议值特定格式项，然后使用ACS先共识消息哈希，再请求缺失消息。其通过形成特殊格式的建议值，将该值作为ACS协议的输入，在ACS协议的广播模块执行时，广播消息的大小大大降低。本文通过对ACS协议的广播子模块进行替换，使用AVID-FP进行消息的广播，在不需要对输入做特定预处理的情况下，广播模块执行时，其广播消息的大小与消息请求模块请求内容的大小相比可忽略，而且由于使用了同态指纹技术，对每个收到的广播消息均可验证其正确性，于是在不需要更多预处理操作的同时达到高效传输的效果。

需要注意的是，使用AVID-FP替换广播子模块后的ACS协议在执行完后，共识的结果依旧是大小可忽略的fpcc集合，为了获得最终的共识消息，需要增加额外的消息请求模块。但在AVID-FP算法流程中有消息恢复的部分，于是恢复消息模块可由各节点以客户端的角色运行消息恢复部分得到最终共识消息。

协议整体流程如下：系统中维护个AVID-FP实例，个ABA实例，每个节点均选取一定交易消息作为建议值，然后以客户端的角色运行AVID-FP协议，分发选取的建议值，并以服务器端的角色共识fpcc；每当一个fpcc验证，在向客户端发送（STROED）消息时，向对应的ABA实例输入1；若该节点已经向−个ABA实例提供过输入，则向其他所有ABA实例输入0；等待所有ABA实例完成，取输出为1的ABA实例对应的AVID-FP输出的fpcc的并集作为最终建议值指纹集合；若此时节点网络环境不佳，则可以先进行下一轮共识，而不需要立即请求fpcc对应的建议值集合，否则节点依次广播消息恢复请求（RETRIEVED），在最优情况下只需从其他+1个节点收到每个建议值的编码块即可恢复相应的建议值，进而得出最终建议值集合。改进的ACS协议流程如下。

//系统维护个AVID-FP实例，N个ABA实例

输入 每个节点的建议值

输出 所有建议值指纹的一个子集或所有建议值的一个子集

3)当已向−个ABA实例提供过输入，则将0作为未提供输入的ABA实例的输入。

4) 当所有ABA实例均已完成，取输出为1的ABA实例对应的AVID-FP输出的fpcc并集作为最终共识的建议值指纹集合。

5)由fpcc集合发送消息恢复请求，并根据收到的编码块恢复消息集合。

在文献[15]中，为了使本地节点的消息和最终建议值集合中的消息交集最大化，在将消息输入ACS协议之前，需要对消息做处理，形成如下格式的消息插入本地建议值集合中。

在本文的协议中，没有处理用户发来消息的时间消耗，而且消息恢复模块不影响共识的进程，若只考虑共识的fpcc，则可对参与的节点进行快速的响应；即使考虑完全恢复最终建议值集合，也会比文献[15]中的改进方案响应更快。改进前后流程如图1所示，模块对比如表1所示。

4 传输效率分析

4.1 本协议传输效率分析

对于之后的消息恢复模块，因为仅需个编码块便可恢复出原消息，对于某个建议值最优情况下仅需发送个消息恢复请求，收到个诚实节点发送的建议值编码块即可恢复出此建议值。所以，最优情况下的单位传输代价为

最坏情况下系统中有个敌手，在消息恢复模块需要请求至少+个编码块以恢复原建议值。于是，最坏情况下单位传输代价为

4.2 HoneyBadgerBFT传输效率分析

图1 改进前后ACS协议流程

Figure 1 ACS protocol flow charts before and after improvement

表1 改进前后模块对比

在最优情况下，即

1) 系统中个节点均为诚实节点；

2) 各个建议值之间没有重复消息；

3) 一轮中建议值均被共识。

HoneyBadgerBFT的单位传输代价为

在最坏情况下，即

1) 系统中有个恶意节点；

2) 每轮只有2+1个建议值被共识，且其中的个来自恶意节点，+1个来自诚实节点。

4.3 文献[15]中共识方案传输效率分析

文献[15]直接将ACS协议作为单独模块，使用了“共识消息哈希，后请求缺失消息”的共识思路，并预先对用户发来的消息进行了处理，形成特定格式的建议值，广播消息的大小与消息请求模块请求内容的大小相比可忽略不计，于是在最优情况下，即

1) 所有节点均是诚实节点；

2) 所有节点均有了建议值中的原消息。

所有节点不会对最终共识的哈希列表中的项发起原消息传输请求，此时协议的单位传输代价为

通过表2对比可知，本文协议的传输效率在最优、最坏情况下均优于HoneyBadgerBFT，最优情况下与文献[15]相同，最坏情况下比文献[15]略差，响应速度由第3节分析可知，本文协议比文献[15]响应速度更快。

表2 单位传输代价比较

5 结束语

在异步共识协议中不仅要考虑传输效率的高低，同时需要关注对于请求的响应速度。本文在HoneyBadgerBFT的基础上，使用修改的AVID-FP协议改进其RBC协议，使在某些特定场景下不需要恢复最终建议值集合也能快速响应共识请求，即使在请求完整建议值集合时也比文献[8]响应更快速，同时传输代价比HoneyBadgerBFT在最优、最差情况下都有所改善。

值得关注的是，在ACS与ABA协议中有多次广播操作，消耗大部分带宽资源，所以，如何在减少广播操作的同时达到相同的功能是接下来的研究重点。

[1] NAKAMOTO S. Bitcoin: a peer-to-peer electronic cash system[R]. 2008.

[2] LAMPORT L. The part-time parliament[J]. ACM Transactions on Computer Systems (TOCS), 1998, 16(2): 133-169.

[3] LAMPORT L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.

[4] LAMPORT L, SHOSTAK R, PEASE M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 382-401.

[5] CASTRO M, LISKOV B. Practical Byzantine fault tolerance[C]//OSDI. 1999: 173-186.

[6] WOOD G. Ethereum: a secure decentralised generalised transaction ledger[J]. Ethereum Project Yellow Paper, 2014, 151: 1-32.

[7] KIAYIAS A, RUSSELL A, DAVID B, et al. Ouroboros: a provably secure proof-of-stake blockchain protocol[C]//Annual International Cryptology Conference. 2017: 357-388.

[8] DAVID B, GAŽI P, KIAYIAS A, et al. Ouroboros praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2018: 66-98.

[9] BENTOV I, PASS R, SHI E. Snow white: provably secure proofs of stake[J]. IACR Cryptology ePrint Archive, 2016: 919.

[10] EYAL I, GENCER A E, SIRER E G, et al. Bitcoin-ng: a scalable blockchain protocol[C]//13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16). 2016: 45-59.

[11] KOKORIS-KOGIAS E, JOVANOVIC P, GASSER L, et al. Omniledger: a secure, scale-out, decentralized ledger via sharding[C]// 2018 IEEE Symposium on Security and Privacy (SP). 2018: 583-598.

[12] ZAMANI M, MOVAHEDI M, RAYKOVA M. Rapidchain: scaling blockchain via full sharding[C]//2018 ACM SIGSAC Conference on Computer and Communications Security. 2018: 931-948.

[13] WANG J, WANG H. Monoxide: scale out blockchains with asynchronous consensus zones[C]//16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). 2019: 95-112.

[14] MILLER A, XIA Y, CROMAN K, et al. The honey badger of BFT protocols[C]//2016 ACM SIGSAC Conference on Computer and Communications Security. 2016: 31-42

[15] 郭兵勇, 李新宇. 一个高传输效率的多值拜占庭共识方案[J]. 密码学报, 2018, 5(5): 516–528. GUO B Y, LI X Y. Multi-valued Byzantine consensus scheme with high transmission efficiency[J]. Journal of Cryptologic Research, 2018, 5(5): 516–528.

[16] DWORK C, LYNCH N, STOCKMEYER L. Consensus in the presence of partial synchrony[J]. Journal of the ACM (JACM), 1988, 35(2): 288-323.

[17] BRACHA G. Asynchronous Byzantine agreement protocols[J]. Information and Computation, 1987, 75(2): 130-143.

[18] HENDRICKS J, GANGER G R, REITER M K. Verifying distributed erasure-coded data[C]//The 26th Annual ACM Symposium on Principles of Distributed Computing. 2007: 139-146.

[19] DUAN S, REITER M K, ZHANG H. BEAT: asynchronous BFT made practical[C]//2018 ACM SIGSAC Conference on Computer and Communications Security. 2018: 2028-2041.

[20] CACHIN C, TESSARO S. Asynchronous verifiable information dispersal[C]//24th IEEE Symposium on Reliable Distributed Systems (SRDS'05). 2005: 191-201.

[21] REED I S, SOLOMON G. Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial and Applied Mathematics, 1960, 8(2): 300-304.

Rapid responsive and efficient multi-valued Byzantine consensus scheme

ZHOU Wang1,2, HU Honggang1,2, YU Nenghai1,2

1. Key Laboratory of Electromagnetic Space Information, Chinese Academy of Sciences, Hefei 230027, China 2. School of CyberScience, University of Science and Technology of China, Hefei 230027, China

Due to the increase of network equipments and the uncertainty of the transmission environment, the message delay is also uncertain, and the asynchronous consensus protocol possesses more advantages. Miller et al proposed the first asynchronous consensus protocol HoneyBadgerBFT in 2016, but its transmission efficiency can be optimized furthermore while achieving high throughput. The broadcast protocol in HoneyBadgerBFT was improved by reducing the message complexity in the broadcast process, and adding optional message request process to achieve rapid response and efficient transmission.

rapid response,efficient transmission, Byzantine protocol, consensus scheme

TP309.3

A

10.11959/j.issn.2096−109x.20201006

2020−01−14；

2020−03−02

胡红钢，hghu2005@uste.edu.cn

国家自然科学基金（61632013，61972370）

The National Natural Science Foundation of China (61632013, 61972370)

周旺, 胡红钢, 俞能海. 快速响应的高效多值拜占庭共识方案[J]. 网络与信息安全学报, 2021, 7(1): 57-64.

ZHOU W, HU H G, YU N H. Rapid responsive and efficient multi-valued Byzantine consensus scheme[J]. Chinese Journal of Network and Information Security, 2021, 7(1): 57-64.

周旺（1995− ），男，安徽淮南人，中国科学技术大学硕士生，主要研究方向为共识协议、区块链应用。

胡红钢（1978− ），男，四川彭州人，博士，中国科学技术大学教授、博士生导师，主要研究方向为密码学、网络安全。

俞能海（1964− ），男，安徽无为人，博士，中国科学技术大学教授、博士生导师，主要研究方向为多媒体数据处理分析与检索、互联网信息检索、数字内容安全。