H-Algorand：基于多块输出的公有链共识机制

王 波，任英琦，黄冬艳

（1.桂林电子科技大学认知无线电与信息处理省部共建教育部重点实验室，广西桂林 541004；2.桂林电子科技大学广西无线宽带通信与信号处理重点实验室，广西桂林 541004）

（*通信作者电子邮箱huangdongyan-gua@163.com）

0 引言

区块链的概念源于2008 年Satoshi Nakamoto 发表的论文《Bitcoin：A peer-to-peer electronic cash system》［1］。近年来区块链技术因其分布式、匿名性、难以篡改等特性受到学术界和企业界的高度关注。

区块链网络的种类从利益方的角度进行分类，可以分为公有链、联盟链和私有链［2-3］。公有链是应用范围最为广泛的一类区块链，有望支撑新型商业形态［4］。公有链可以分为需要认证的公有链网络和无需认证的公有链网络［5-6］。无需认证的公有链应用有Bitcoin［1］等，需要认证的公有链应用有EOS（Enterprise Operation System）［7］等。

区块链技术由分布式存储、密码学、共识机制、智能合约等技术构成，其中，共识机制的作用旨在可容错的网络环境下实现状态机复制排序的一致性［6］。公有链的共识机制包括工作量证明（Proof Of Work，POW）［1］、权益证明（Proof Of Stake，POS）［8］、委托权益证明（Delegated Proof Of Stake，DPOS）［9］、Algorand 机制［10］等。但公有链中如何提高区块的共识效率，一直是一个挑战［4］。

Algorand 机制由Micali［10］提出，该算法之后由Gilad 等实现［11］。其中使用到的可验证的随机函数（Verifiable Random Functions，VRFs）［12］抽签算法，使每个节点都有机会参与到共识中，提高了共识的可拓展性。其中使用到的拜占庭协议（Byzantine Agreement，BA★）令节点只在当前区块和空白块之间做二元共识［11］，使得链条分叉概率仅为10-18［10］，即使在恶意节点能力很强的区块链网络环境下依旧能保持良好的性能。2 MB的区块使用Algorand机制在50 000用户的区块链网络中从提出到完成共识只需22 s［11］。

日后随着区块链网络的大规模推广，网络数据交互频率和数据量都会增大［13］，如果将Algorand 机制用于银行等大规模交易系统，交易延迟将会累积爆发，造成银行系统瘫痪。因此，Algorand机制的共识效率仍有待提高。

针对Algorand 机制共识效率不高的问题，本文首先提出多块Algorand 共识机制（Multi-Block-Algorand，MB-Algorand），以有效提升出块效率；其次针对分布式拒绝服务（Distributed Denial of Service，DDoS）攻击，结合Algorand 与MB-Algorand 两者的优势提出H-Algorand（Hybid-Algorand）机制。该机制以牺牲一定的安全性能为代价，以换取区块链网络共识效率的显著提升。

1 工作机制

1.1 公有链网络工作机制

公有链网络从有无委员会的角度来说可以分为有委员会的区块链网络和无委员会的区块链网络。本文关注有委员会的区块链网络，包括以下5个步骤。

步骤一 消息广播。区块链网络中的每个节点通过gossip 等通信协议向网络中的节点广播消息。每个消息都会签署始发节点的私钥以防止消息被伪造。其他节点在转发这些消息前会检查签名。对于相同的消息，每个节点只会转发一次。

步骤二 委员会选举。区块链网络可以通过投票机制［9，14］、滑窗机制［15］、抽签机制［10］等选举出委员会。委员会代表整个区块链网络对网络新生成的区块进行共识。

步骤三 领导者选举及出块。委员会可以通过随机数机制［9］、优先级机制［10］等选举出领导者节点。领导者节点负责将它收集到的消息，打包到待共识的区块里，在委员会里转发。设打包及转发的时间为tp。

步骤四 委员会共识。委员会利用实用拜占庭容错（Practical Byzantine Fault Tolerance，PBFT）、BA★［11］等共识机制，对领导者提出的区块进行共识。设共识时间为tc。

步骤五 新区块写入。共识成功的区块在区块链网络中转发，被各个节点添加到各自维护的账本中。

1.2 Algorand机制出块-共识原理

在步骤二“委员会选举”阶段，Algorand 机制根据权重，在所有用户之间随机选择完成一届（两批）委员会选举，保证委员会的成员足够诚实，从而避免Sybil攻击。

在步骤三“领导者选举”中，委员会中优先级较高的节点（1～70 个）向委员会发送自己的优先级、自己打包的块及证明。优先级消息约200 B，可以在网络中快速传播。优先级最高的节点会获得委员会的认可，成为领导者。而其他节点发送的区块则会被过滤。领导者的选举在时间上与领导者出块和委员会共识是并行执行的。

Algorand机制的出块-共识所对应的时序如图1所示。

Algorand 机制一届委员会只出一个区块。当领导者出块后，委员会将对该区块进行委员会共识。委员会的各节点通过BA★算法对领导者提出的区块进行二元共识。

综上所述，Algorand 机制中，一个区块出块-共识所需要的时间为：

图1 Algorand机制“出块-共识”时序图Fig.1 “Propose-consensus”sequence diagram of Algorand mechanism

2 MB-Algorand机制的工作机制

如图1所示，Algorand机制使得每一届委员会只能对本届领导者提出的区块进行共识，并且第i+1 块待共识区块的出块需等到第i块区块委员会共识结束后方可进行，这就导致Algorand机制的出块效率较低。

为了提高区块链网络出块效率，本文提出MB-Algorand机制。本机制借鉴EOS共识机制，在执行步骤三和步骤四时，使得领导者出块和委员会共识并行处理，从而有效提高区块链网络整体出块效率，其共识时序如图2所示。

图2 MB-Algorand机制“出块-共识”时序图Fig.2 “Propose-consensus”sequence diagram of MB-Algorand mechanism

在MB-Algorand 机制第i届委员会期间，当领导者提议第一个区块i1之后，委员会开始对区块i1进行共识。由于区块i2为同一个领导者提出，该领导者必然确定自己出的每一个块都是可信的。因此，领导者不需要等待委员会的共识时间，便开始提议第二个区块i2，直到领导者提议至目标出块数第N个区块iN为止。MB-Algorand 机制实现了共识与出块的并行处理，从而可以有效提高共识效率。

因为区块大小不同，会使得块提议时间tp不同，而块共识时间tc大小几乎不变。以tp和tc大小关系作为条件，又可以分为以下两种情况：

CaseⅠ：当tp＜tc时，即提议区块较小于4 MB［11］，N个区块“领导者出块”和“委员会共识”所需要的时间为：

CaseⅡ：当tp≥tc时，即提议区块大于4 MB［11］，N个区块“领导者出块”和“委员会共识”所需要的时间为：

3 H-Algorand机制的工作机制

MB-Algorand 机制连续共识多个块虽然可以有效提高共识效率，但是也会带来安全性的下降。为了使共识机制能够适应网络状态的变化而使得区块链网络保持安全高效，本文基于Algorand 机制和MB-Algorand 机制提出一种混合Algorand（Hybid-Algorand，H-Algorand）共识机制。

其运行机制如图3 所示，第i届委员会执行一个块数为N的出块周期，设n为当前区块编号，[i，n]为第i届委员会共识的编号为n的区块。首先判断网络状态是否符合运行MBAlgorand 机制的安全标准：若不符合，则使用Algorand 机制完成共识，即N个待共识区块将由第i届至第i+j，j∈[0，N)届领导者与委员会逐个提议并共识；若符合，则启动MBAlgorand 机制，即N个区块都由i届领导者与i届委员会进行共识。在运行MB-Algorand 机制时，如果第i届领导者提议的某个区块在第i届委员会中共识失败（失败的原因在下一章进行讨论），则失败的这一轮共识一个空白区块，提交上链。以空白块为起点，N个区块中剩余N-n个待共识区块，转为Algorand 机 制，即 由i+j，j∈[1，N-n] 届领导者与i+j，j∈[1，N-n]届委员会进行共识。

图3 H-Algorand网络运行机制Fig.3 Operation mechanism of H-Algorand network

4 H-Algorand机制的性能分析

H-Algorand 机制中包含MB-Algorand 机制，MB-Algorand机制中领导者可以连续出块使得领导者出块和委员会共识并行处理，提高了出块效率。但是，由于领导者连续出块，导致其与委员会暴露在网络当中。暴露的时间越长，被恶意的攻击者发现、执行攻击以及攻击成功的概率加大。下面将分析H-Algorand机制在出块效率和安全性之间的折中性能。

4.1 H-Algorand机制在CaseⅠ下的性能分析

4.1.1 概述

区块链网络主要采用两种网络模型，强同步网络模型和弱同步网络模型［16］。本文主要讨论强同步网络模型下HAlgorand 机制的性能。强同步网络模型下区块链遭受的安全威胁主要来自七类恶意攻击［17］，这些攻击从各个层面对区块共识造成影响。

H-Algorand 机制属于有委员会的区块链网络。在有委员会的区块链网络中，委员会成员之间的交互容易泄露委员会的身份，从而遭到攻击者的分布式拒绝服务（Distributed Denial of Service，DDoS）攻击［17］，本文主要分析DDoS 对于HAlgorand机制的影响。

本文假设区块链网络对于恶意攻击有相应的检测机制与防御机制，使其可以对网络状况进行安全性评估。区块链网络中各节点拥有数据检验的能力，不可能进行基于数据伪造的作恶。区块链网络中节点之间的贿赂行为会受到惩罚［18］。

4.1.2 出块效率

本文假设Algorand 机制共识以概率1 成功。H-Algorand机制中领导者目标出块数为N，优先以MB-Algorand 机制运行。MB-Algorand 机制产生的第一个区块的共识过程可以认为和Algorand 机制相同，以概率1 成功，其余剩下的N-1 个区块由于领导者和委员会暴露在区块链网络中，都存在共识失败的概率。设在遭受DDoS攻击威胁的网络环境下，每一个区块共识失败的概率为Pfault，为了便于分析，Pfault为一定值。则每个块共识成功的概率为Psuccess=1-Pfault，N个块全部共识成功的概率为。

Algorand机制对N个区块共识所需时间为：

理想条件下，即网络中不存在恶意攻击时，MB-Algorand机制共识N个区块出块提升效率为：

当N→∞时

由式（6）可得，当tc/tp越小时，出块效率越大；当tp=tc时，出块效率的上限为50%。在实际的区块链网络中，当块大小为4 MB左右时，tp≈tc，此时可以达到最大出块效率［11］。

在实际的区块链网络中，MB-Algorand机制每个待共识区块共识失败概率为Pfault。设从第二个块开始，H-Algorand 机制使用MB-Algorand 机制的多块方式连续提出并成功共识的区块数为n，则使用Algorand机制的单块方式提出并共识的区块数为N-1-n。

首先将H-Algorand 机制简单的看成n重伯努利实验，则H-Algorand 机制使用MB-Algorand 机制连续共识成功n个区块花费的时间为：

由于区块链网络的链式结构，新区块必须建立在前一区块的基础之上。因此实际H-Algorand 机制使用MB-Algorand机制连续共识成功n个区块花费的时间由式（7）修正为式（8）：

其中：第一项表示n=N-1时，H-Algorand 机制所花费的时间；第二项表示n∈[0，N-2]时，H-Algorand 机制所花费的时间。

4.1.3 安全性

当H-Algorand 机制使用MB-Algorand 机制领导者提议的目标出块数为N时，N个块全部共识成功的概率为，则H-Algorand机制安全性损失为。

4.1.4 收益函数

对H-Algorand 机制的出块效率和安全性进行折中考虑，建立收益函数：

其中β为权重因子。

最优化问题表示为：

约束条件（11）表示共识N(N＞2)个块时，H-Algorand 机制完全使用MB-Algorand 机制共识成功的目标概率在M以上。

4.2 H-Algorand机制在CaseⅡ下的性能分析

4.2.1 出块效率

MB-Algorand 机制在理想条件下提出N个块的出块效率为：

当N→∞时

即当tp/tc越小时，出块效率越大。

则H-Algorand 机制实际所花费的时间的与CaseⅠ类似，为：

4.2.2 收益函数

其最优化模型与式（9）相同，为：

5 实验与分析

本章对H-Algorand 机制在Case I 和Case II 两种情况下的性能进行仿真分析。

5.1 实验参数

H-Algorand机制的仿真参数及取值如表1所示。

表1 参数表Tab.1 Parameter table

如表1 所示，领导者出块时间tp在CaseⅠ与CaseⅡ下分别为10 s，26 s［11］，委员会共识时间tc在CaseⅠ与CaseⅡ下分别为12 s，12 s［11］；令H-Algorand 机制在目标出块数N下区块共识成功的目标概率M=70%，此时H-Algorand 机制下，领导者的目标出块数N的大小被限定在2到8之间；为了考察不同网络环境下H-Algorand 机制的性能，H-Algorand 机制第［2，N］个区块受到恶意攻击后共识失败概率设定为1%、2%、3%、4%。本文认为时间上的收益和安全上的收益同样重要，因此β=0.5。

5.2 H-Algorand机制在Case I下的仿真与分析

图4 所示为CaseⅠ下，β=0.5，Pfault分别为1%、2%、3%、4%时，H-Algorand 机制下使用MB-Algorand 机制进行共识时的领导者目标出块数N与收益函数的关系。从图4 首先可以看出，一定的Pfault时，存在一个最优的N*，使得收益函数取得最大值；其次，一定的N时，Pfault值越低，收益函数越大。

图4 CaseⅠ：所提算法收益函数示意图Fig.4 CaseⅠ：schematic diagram of revenue function of the proposed algorithm

表2 所示为CaseⅠ下，β=0.5，Pfault分别为1%、2%、3%、4%时，H-Algorand 机制下使用MB-Algorand 机制进行共识时的最优出块数N*，相对于传统的Algorand 机制，100%使用MB-Algorand 机制进行共识的出块提升效率以及相应的安全性损失，和50%使用MB-Algorand 机制进行共识的出块提升效率。可以看出，随着Pfault的增加，最优出块数下降，出块提升效率降低，而安全性损失将会增加。

表2 CaseⅠ：安全性与共识效率Tab.2 CaseⅠ：safety and consensus efficiency

从表2还可以看出，当Pfault较小时（如1%），H-Algorand机制100%使用MB-Algorand 机制进行共识时，能够以安全性损失5.85%的代价换来出块效率37.87%的提升，这表明HAlgorand机制具有很强的工程实用价值。

且当H-Algorand 机制下使用MB-Algorand 机制进行共识最优出块数N*的一半50%N*（向上取整）时，相对于传统的Algorand机制，其出块提升效率也是可观的。

5.3 H-Algorand机制在CaseⅡ下的仿真与分析

图5 所示为CaseⅡ下，β=0.5，Pfault分别为1%、2%、3%、4%时，H-Algorand 机制下使用MB-Algorand 机制进行共识时的领导者的目标出块数N与收益函数的关系。CaseⅡ可以得出与Case I相同的结论。

表3 所示为Case II 下，β=0.5，Pfault分别为1%、2%、3%、4%时，H-Algorand 机制下使用MB-Algorand 机制进行共识时的最优出块数N*，相对于传统的Algorand 机制，100%使用MB-Algorand机制的出块提升效率以及相应的安全性损失，和50%使用MB-Algorand机制的出块提升效率。

从表中可以看出，当Pfault较小时（如1%），H-Algorand 机制100%使用MB-Algorand 机制进行共识时，能够以安全性损失4.9%的代价换来出块效率26.32%的提升，其效率提升程度比CaseⅠ略差一些。

当H-Algorand 机制下使用MB-Algorand 机制进行共识最优出块数N*的一半50%N*（向上取整）时，相对于传统的Algorand机制，其出块效率也得到了提升。

图5 CaseⅡ：所提算法收益函数示意图Fig.5 CaseⅡ：schematic diagram of revenue function of the proposed algorithm

表3 CaseⅡ：安全性与共识效率Tab.3 CaseⅡ：safety and consensus efficiency

综合CaseⅠ和CaseⅡ来看，产生一个区块的时间越多时，即区块越大时，H-Algorand 机制使用MB-Algorand 机制相对于使用传统Algorand 机制获得的收益会减少，因此H-Algorand机制适用于区块小于4 MB且网络环境较为安全的场景。

6 结语

本文针对受到业界普遍重视的公有链网络，首先提出了一种多块输出的共识机制——MB-Algorand，该机制的领导者可以连续出块，从而有效地提升了出块效率；其次在公有链委员会受到DDoS 攻击的场景下，提出融合了Algorand 和MBAlgorand 两者优点的H-Algorand 机制。该机制折中考虑了出块效率与安全性两方面。将H-Algorand 机制与Algorand 机制进行仿真对比发现，H-Algorand 机制能在恶意攻击成功率为1%～4%的条件下，以牺牲少量安全性为代价换取共识效率的有效提升。本文仅对H-Algorand 机制在强同步网络模型下进行了分析研究，未来将对弱同步网络模型下的共识机制进行分析研究。