开放科学（资源服务）标志码（OSID）：

0 概述

共识算法根据容错类型可分为故障容错（Crash Fault Tolerance，CFT）共识算法和拜占庭容错（Byzantine Fault Tolerance，BFT）共识算法^[1]。故障容错共识算法主要采用Paxos^[2]及Raft^[3]等，只能容忍节点发生宕机等错误，若存在恶意节点，则无法保证诚实节点数据的一致性。拜占庭容错共识算法的目的是解决拜占庭将军问题^[4]，即使系统中存在恶意节点（不超过一定比例），依旧能够保证诚实节点数据的一致性。拜占庭将军问题最早由LAMPORT等人在1982年提出，并给出了口头协议和书面协议2种拜占庭容错算法，但其复杂度为指数级，在实际中并不实用。1999年，LISCOV等^[5]提出实用拜占庭容错（Practical Byzantine Fault Tolerance，PBFT）算法，通过两轮投票的方式将其复杂度降至多项式级，但是，拜占庭容错应用场景较少，因此，该算法未获得学术界的广泛关注。2008年，中本聪提出比特币的概念，随着数字货币及其底层区块链技术的逐渐兴起，拜占庭容错算法逐渐受到重视。

目前，区块链中常用的拜占庭容错算法可分为弱一致性（又称最终一致性）算法和强一致性算法^[6]。弱一致性算法允许数据在某一时间点可以存在不一致的情况，其典型代表包括工作量证明（Proof of Work，PoW）^[7]、权益证明（Proof of Stack，PoS）^[8]和委托权益证明（Delegate Proof of Stack，DPoS）^[9]等，由于需要使用最长链原则解决分叉问题，因此一笔交易发出后并不能确保一定能够成功，这在商用区块链场景下是不可接受的，因此，弱一致性算法在公有链中应用较为广泛，在联盟链中应用较少。强一致性算法则在任何情况下都不允许区块链出现分叉情况，一个区块一旦添加便不会被撤销，其更加适用于商用联盟链场景。

PBFT作为一种经典的强一致性算法，被广泛应用于区块链中，如Hyperledger Fabric^[10]、Neo^[11]等。在PBFT中，一个区块达成共识需要O(n²)的复杂度。主节点发起的一轮共识称作一个视图（View），为保证活性，需要对每个视图设置一个超时时间，若超时前无法达成共识，则将更换新的主节点并开始新的视图，该操作称为视图更换（View Change），具有O(n³)，的复杂度，复杂度过高导致其无法应用于大规模节点的网络环境中。目前，有诸多基于PBFT的改进共识算法^[12-14]被提出，其中，以Tendermint^[15]最具代表性。Tendermint将PBFT中的视图更换融入进普通的共识过程中，并通过锁定和解锁机制，将视图更换的复杂度降至O(n²)，但复杂度依旧过高。YIN等^[16]提出了HotStuff，其使用门限签名^[17-19]对Tendermint进行改进，将共识与视图更换的复杂度均降至O(n)，并通过三轮投票五个阶段（NewView、Prepare、PreCommit、Commit、Decide）的方式实现乐观响应性（Optimistic Responsiveness）。由于HotStuff具有较低的复杂度，因此受到了广泛关注，Facebook的Libra^[20]项目便采用了HotStuff算法。此后，JALALZAI等^[21]提出了Fast-HostStuff，在NewView阶段使用聚合签名^[22]代替HotStuff中的门限签名，实现两轮投票四个阶段（NewView、Prepare、PreCommit、Commit）的HotStuff，提高了执行效率，并同时具备乐观响应性。在HotStuff与Fast-HostStuff中，若共识能够正常执行或主节点在第二轮投票后发生错误，则均能保证较高的吞吐量，然而若主节点在第一轮投票后发生错误，则吞吐量将大幅降低。

本文提出一种改进的Fast-HotStuff算法，并实现一种新的特性，定义为乐观扩展性（Optimistic Extensibility）。乐观扩展性要求在乐观条件下，即便主节点在第一轮投票后发生错误，下一视图中新的主节点依旧能够根据其上一视图中未达成共识的区块进行扩展，在一个新的高度生成新区块并发起共识。其中，乐观条件是指当前视图的主节点为诚实节点，且至少有n-f（n）为节点总数，f为最大容错个数）个诚实节点能够收到主节点的新区块提案。实现乐观扩展性意味着若主节点在第一轮投票后发生错误，则能够在出错情况下的共识时延内使更多区块达成共识，从而提交更多区块上链，达到提高吞吐量的目的。为实现乐观扩展性，本文算法设计一个新的区块扩展方式，区块在某一视图的共识过程中，若主节点在第一轮投票发生错误导致视图更换，则副本节点将其第一轮投票消息传递至下一视图，下一视图中的主节点若收到f+1个相同区块的投票消息，则根据该区块进行扩展生成新的区块并发起共识。

1 Fast-HotStuf算法

在Fast-HotStuff算法中，设节点总数为n，最大容错个数为f，且n=3f+1。共识在一个视图下进行，每个视图具有唯一且单调递增的视图编号，且存在一个主节点主导共识，共识完成后将开始下一视图。如果遇到主节点宕机、恶意等异常情况，则等待视图超时后更换新的主节点并开始新的视图。

Fast-HotStuff算法的共识过程如图 1所示，其中，Prepare、PreCommit是对一个区块进行两轮投票的阶段。

在Prepare阶段，主节点向副本节点广播新区块提案，副本节点向主节点发送对该区块的投票消息，投票即为对该消息进行签名。主节点收到n-f个消息后，将所有消息及其签名进行聚合生成一个QC（Quorum Certificate），称为prepareQC，视作第一轮投票达成的证据。

在PreCommit阶段，主节点将prepareQC广播给副本节点，副本节点向主节点发送第二轮投票消息，主节点收到消息后生成preCommitQC，视作第二轮投票达成的证据。

在Commit阶段，主节点向副本节点广播preCommitQC，副本节点收到后将区块提交至区块链中。

在每个视图开始前的NewView阶段，副本节点向主节点发送NewView消息，消息中包含副本节点所保存的视图编号最大的prepareQC。主节点从收到的n-f个消息中挑选视图编号最大的prepareQC作为highQC，并根据highQC.block（highQC的区块）进行扩展生成新的区块，然后对n-f个NewView消息及其签名进行聚合生成aggQC，主节点在Prepare阶段会将新区块以及aggQC一起广播给副本节点。

prepareQC以及preCommitQC的生成使用的是门限签名，而aggQC的生成使用的是聚合签名，这是由于n-f个NewView消息内容可能存在不同的情况，而聚合签名可以对不同消息的签名进行聚合。副本节点收到后会从aggQC中提取出highQC，并判断新区块是否为highQC.block的扩展，如果是，则接受该区块并发出投票。

在Fast-HotStuff中，如果主节点在第二轮投票后发生错误，无法在Commit阶段广播第二轮的投票结果（preCommitQC），那么在视图更换之后的新视图中，新的主节点依旧可以在一个新的区块高度生成新区块，这是由于新区块的生成是根据第一轮投票结果（prepareQC）。然而，如果主节点在第一轮投票完成后发生错误，无法在PreCommit阶段广播第一轮的投票结果（prepareQC），则新的主节点便无法在一个新的区块高度生成新区块，设想以下案例：

1）假设在某一视图中所共识区块的高度为h，在Prepare阶段至少有n-f个副本节点向主节点发送了该区块的第一轮投票消息，而此时主节点发生错误，无法向副本节点广播prepareQC。

2）副本节点在视图超时前未收到主节点发送的prepareQC，将向新的主节点发送NewView消息并开启新的视图。

3）新的主节点收到了n-f=2f+1个副本节点发送的NewView消息，但其中不包含旧的主节点所持有的最新prepareQC，因此，新主节点将重新生成一个高度为h的区块并发起共识。

从上述案例可以发现，各节点已收到主节点的新区块提案，并对高度为h的区块进行投票，然而主节点发生错误导致视图更换，新的主节点无法收到投票结果从而根据上一视图中的区块进行扩展，在一个新的高度（h+1）生成区块并发起共识。如果连续f个视图中的主节点在上述情况中发生错误，则相当于连续f+1个视图中仅生成了一个区块，这将大幅降低区块链的吞吐量，这一问题不仅存在于Fast-HotStuff中，在HotStuff中也同样存在。

2 改进的Fast-HotStuff算法 2.1 算法概述

算法容错模型：设系统中包括n=3f+1个节点，用i表示节点编号，i∈[n] where [n]={1，2，…，n}。设恶意节点集合为F⊂[n]，则集合最大容错个数为|F|=f。

算法网络模型：算法采用部分同步（Partial Synchrony）网络模型，即系统中存在不确定且无法预知的全局稳定时间（Global Stable Time，GST）和消息传输上限。在GST之前，系统处于异步（Asynchronous）状态；在GST之后，系统处于同步（Synchrony）状态，即在GST之后，节点间的消息能够在消息传输上限内到达。其次，网络通信是点对点且可靠的，通信内容是经过签名且可验证的，恶意节点不具有进行哈希碰撞、签名伪造等密码学攻击方式所需的计算能力。

算法中的数字签名技术：相比聚合签名，门限签名效率更高，但只能对同一消息进行聚合，而聚合签名则可以对不同消息进行聚合，因此，本文算法在NewView阶段使用聚合签名，而在其他阶段使用门限签名。

算法中的区块链结构：每个节点都维持一个区块树，一个父区块可以有多个子区块，子区块中包含父区块的哈希值，但并非所有区块都是有效区块，只有区块链中的区块才是有效区块。区块链是区块树中的一个分支，即最后一个完成算法所有阶段的区块所在的分支。在正常情况下，区块链中的所有区块都将完成所有阶段，但若存在恶意节点阻碍共识或出现网络延迟，则可能导致区块链中某些区块未完成所有阶段，但是这对安全性并不会造成影响，因为所有诚实节点都将认同区块树中唯一的一条区块链。

改进的Fast-HotStuff算法分为NewView、Prepare、PreCommit和Commit 4个阶段，具体如下：

1）在NewView阶段，主节点将收集n-f个副本节点发送的NewView消息，并生成一个新区块，在新的视图中开启共识。

2）在Prepare阶段，主节点向副本节点发送包含新区块的Prepare消息，副本节点收到后向主节点发送PrepareVote消息并进行第一轮投票，投票即是对该消息生成签名。

3）在PreCommit阶段，主节点在收到n-f个PrepareVote消息后，将所有消息及其签名进行聚合生成prepareQC，并向副本节点发送PreCommit消息，消息中包含prepareQC。副本节点收到后向主节点发送PreCommitVote消息并进行第二轮投票。

4）在Commit阶段，主节点在收到n-f个PreCommitVote消息后，将所有消息及其签名进行聚合生成preCommitQC，并向副本节点发送Commit消息，消息中包含preCommitQC，副本节点收到后将区块提交至区块链中。

为实现乐观扩展性，本文算法对NewView阶段及Prepare阶段进行改进，增加一个新的区块扩展方式。在某一视图中，若主节点在第一轮投票后发生错误，无法广播第一轮投票结果prepareQC，从而导致视图超时，则副本节点将其在该视图中的PrepareVote消息包含于NewView消息中发送给下一视图中新的主节点，新的主节点所收到的n-f个NewView消息中若存在f+1个相同的PrepareVote，则根据PrepareVote.block进行扩展以生成新的区块，从而使新的主节点能够根据上一视图中未达成共识的区块进行扩展，在一个新的高度生成区块并发起共识。其中，要求f+1的原因是因为新的主节点所收到的n-f个PrepareVote中，可能存在f个恶意节点所发送的PrepareVote与诚实节点不同，因此要求n-f-f=f+1个相同的PrepareVote。基于区块链的链式结构以及算法的容错模型，若在新的视图中一个新高度的区块达成了共识，则保证了该区块之前未达成共识的父区块或更早的区块也达成了共识，因此，在出错情况下的共识时延内，能够提交更多的区块上链，从而提高吞吐量。

2.2 算法设计 2.2.1 NewView阶段

主节点接收n-f个副本节点（包括主节点自身）所发送的NewView消息：

< "NewView"，viewNumber，PrepareVote or prepare QC，sig_i >

其中，"NewView"为消息头，表示该消息为NewView消息，viewNumber为新视图的视图编号，PrepareVote为节点本地所保存的viewNumber最大的PrepareVote消息，prepareQC为节点本地所保存的viewNumber最大的prepareQC，sig_i为节点i对该消息的签名。

副本节点根据算法1中第1行~第6行判断NewView消息中第3个字段要发送的内容，如果prepareQC.viewNumber ≥ PrepareVote.viewNumber，则发送prepareQC；否则，发送PrepareVote。

算法1  NewView阶段

For Replica：

1.if prepareQC.viewNumber ≥ PrepareVote.view Number：

2. viewNumber ← prepareQC.viewNumber+1

3. NewView ←（"NewView"，viewNumber，prepareQC，sig_i）

4.else：

5. viewNumber ← PrepareVote.viewNumber+1

6. NewView ←（"NewView"，viewNumber，PrepareVote，sig_i）

7.send NewView message to leader

2.2.2 Prepare阶段

Prepare阶段包括以下过程：

1）主节点广播消息

如算法2中第3行、第4行所示，主节点在收到的n-f个NewView消息中挑选视图编号最大的prepareQC和PrepareVote作为highQC和highVote。

设当前视图将对高度为h的区块进行共识，主节点根据算法2中第5行~第11行的规则进行新区块生成。如果highQC.viewNumber ≥ highVote.viewNumber，则根据highQC.block_h-1进行扩展以生成新区块block_h，其中，block下标表示区块高度。

如果highQC.viewNumber < highVote.viewNumber，则判断是否存在至少f+1个相同的PrepareVote.block_h-1=highVote.block_h-1（包括highVote自身），若存在，则根据highVote.block_h-1进行扩展生成新区块block_h；若不存在，则根据highQC.block_h-1进行扩展生成新区块block_h。

如算法2中第12行~第14行所示，主节点将n-f个NewView消息及其签名使用聚合签名算法进行聚合生成aggQC，向副本节点发送Prepare消息：

< "Prepare"，viewNumber，block_h，aggQC >

在Prepare消息中，block_h为实质区块，而在其他消息中，block_h则为区块的哈希值，此举是为了减少通信量，但为简化描述，本文统一使用block_h进行表示。

2）副本节点回复消息

如算法2中第16行、第17行所示，副本节点收到Prepare消息后，从aggQC中提取highQC或f+1个相同的highVote，并根据以下规则判断是否接受该消息中的block_h：

（1）block_h是highQC.block_h-1的扩展。

（2）block_h是highVote_h-1的扩展。

符合上述任意一条则向主节点发送PrepareVote消息：

< "PrepareVote"，viewNumber，block_h，sig_i>

算法2  Prepare阶段

For Leader：

1.wait for n-f NewView messages from replica

2.NV ← NV∪NewView

3. ${\rm{highQC}} \leftarrow \mathop {\max }\limits_{{\rm{NewView}} \in {\rm{NV}}} ({\rm{NewView}}{\rm{.prepareQC)}}$

4. ${\rm{highVote}} \leftarrow \mathop {\max }\limits_{{\rm{NewView}} \in {\rm{NV}}} ({\rm{NewView}}{\rm{.prepareVote)}}$

5.if highQC.viewNumber ≥ highVote.viewNumber：

6. extend highQC.block_h‒1 to generate block_h

7.else：

8. if f+1PrepareVote.block_h‒1 = highVote.block_h‒1：

9. extend highVote.block_h‒1 to generate block_h

10. else：

11. extend highQC.block_h‒1 to generate block_h

12. ${\rm{aggQC}} \leftarrow \mathop {{\rm{aggCombine}}}\limits_{{\rm{NewView}} \in {\rm{NV}}} {\rm{(NewView}}, {\rm{NewView}}{\rm{.si}}{{\rm{g}}_{\rm{i}}}{\rm{)}}$

13.Prepare ←（"Prepare"，viewNumber，block_h，aggQC）

14.broadcast Prepare message to replica

For Replica：

15.wait for Prepare message from leader

16.extract highQC or f+1 highVote from Prepare.aggQC

17.if Prepare.block_h extends from highQC.block_h‒1 or highVote.block_h‒1

18.PrepareVote ←（"PrepareVote"，viewNumber，block_h，sig_i）

19.send PrepareVote message to leader

2.2.3 PreCommit阶段

PreCommit阶段包括以下过程：

1）主节点广播消息

如算法3中第1行~第5行所示，主节点将收到的n-f个PrepareVote消息及其签名使用门限签名算法进行聚合生成prepareQC，向副本节点发送PreCommit消息：

< "PreCommit"，viewNumber，block_h，prepareQC >

2）副本节点回复消息

如算法3中第6行~第8行所示，副本节点收到PreCommit消息后，向主节点发送PreCommitVote消息：

< "PreCommitVote"，viewNumber，block_h, sig_i >

算法3  PreCommit阶段

For Leader：

1.wait for n-f PrepareVote messages from replica：

2.PV ← PV∪PrepareVote

3. ${\rm{prepareQC}}{ \leftarrow _{\mathop {{\rm{thCombine}}}\limits_{{\rm{PrepareVote}}\; \in \;{\rm{PV}}} }}\;({\rm{PrepareVote}}, {\rm{PrepareVote}}.{\rm{si}}{{\rm{g}}_{\rm{i}}}{\rm{)}}$

4.PreCommit ←（"PreCommit"，viewNumber，block_h，prepareQC）

5.broadcast PreCommit message to replica

For Replica：

6.wait for PreCommit message from leader

7.PreCommitVote ←（"PreCommitVote"，viewNumber，block_h，sig_i）

8.send PreCommitVote message to leader

2.2.4 Commit阶段

Commit阶段主要包括以下过程：

1）主节点广播消息

如算法4中第1行~第5行所示，主节点将收到的n-f个PreCommitVote消息及其签名使用门限签名算法进行聚合生成preCommitQC，并向副本节点发送Commit消息：

< "Commit"，viewNumber，block_h，preCommitQC >

2）副本节点添加区块

如算法4中第6行、第7行所示，副本节点收到Commit消息后，将block_h提交到区块链中，至此一个区块的共识完成，副本节点将向主节点发送NewView消息并开始下一个视图。

算法4  Commit阶段

For Leader：

1.wait for n-f PreCommitVote messages from replica：

2.PCV ← PCV∪PreCommitVote

3. ${\rm{preCommitQC}}{ \leftarrow _{\mathop {{\rm{thCombine}}}\limits_{{\rm{PreCommitVote}}\; \in \;{\rm{PCV}}} }}\;({\rm{PreCommitVote}}, {\rm{PreCommitVote}}.{\rm{si}}{{\rm{g}}_{\rm{i}}})$

4.Commit ←（"Commit"，viewNumber，block_h，preCommitQC）

5.broadcast Commit message to replica

For Replica：

6.wait for Commit message from leader

7.add block_h to blockchain

3 算法分析

本文首先给出若干基本引理，然后根据基本引理对算法的安全性、活性、乐观响应性以及乐观扩展性进行证明，最后分析算法复杂度。

3.1 基本引理

算法中存在2种类型的QC，即prepareQC和preCommitQC，以QC.type表示QC类型，QC.viewNumber表示QC的视图编号，QC.block_h表示该QC高度为h的区块。

引理1  对于任意2个有效的QC1和QC2，假设QC1.type=QC2.type，且QC1.block_h和QC2.block_h冲突，则必然有QC1.viewNumber ≠ QC2.viewNumber。

证明  假设QC1.viewNumber = QC2.viewNumber，由于一个有效的QC是由n-f=2f+1个节点的投票（签名）所组成的，则说明至少存在一个诚实节点在同一个视图中的同一个阶段发出了2个不同区块的投票消息，这与n=3f+1的容错模型相悖。

引理2  如果在某一视图中至少n-f个节点收到了prepareQC，那么下一个区块block_h+1将是prepareQC.block_h的扩展。

证明  如果在某一视图中至少n-f=2f+1个节点收到了prepareQC，那么在下一视图中主节点所收到的n-f=2f+1个NewView消息中，将至少包含1个诚实节点所发送的prepareQC，该prepareQC将作为highQC，因此下一个区块block_h+1将是PrepareQC.block_h的扩展。

引理3  如果在某一视图中主节点是诚实节点，且在该视图中至少n-f个诚实节点收到了新区块提案并发出PrepareVote消息，那么下一个区块block_h+1将是PrepareVote.block_h的扩展。

证明  如果在某一视图viewNumber=v中主节点是诚实节点，且在该视图中至少n-f个诚实节点收到了新区块提案并发出PrepareVote消息，那么在下一视图viewNumber=v+1中，主节点所收到的n-f=2f+1个NewView消息中，将至少包含f+1个诚实节点在视图v中所发送的PrepareVote，该PrepareVote将作为highVote，因此下一个区块block_h+1将是PrepareVote.block_h的扩展。

3.2 安全性分析

定理1  在同一视图中不会提交2个冲突的区块。

证明  根据算法流程可知，提交一个区块至区块链中需要完成算法的所有阶段，而在这些阶段中将产生prepareQC和preCommitQC，根据引理1可知，同一视图中不会存在2个相同类型的不同QC，因此，不会存在2个区块在同一视图中完成所有阶段，即同一视图中不会提交2个冲突的区块。

定理2  在不同的视图中不会提交2个冲突的区块。

证明  假设存在区块block1_h和block2_h冲突，且block1_h.viewNumber < block2_h.viewNumber。如果block1_h已被至少1个节点提交，则说明该节点收到了preCommitQC.block1_h，进而说明至少n-f=2f+1个节点收到了prepareQC.block1_h。根据引理2可知，下一个区块block_h+1将是prepareQC.block1_h的扩展，即下一个区块的高度应为h+1。如果下一视图中主节点发起block2_h的共识，则会被至少f+1个诚实节点所拒绝，而block2_h将无法完成共识，因此，在不同的视图中不会提交2个冲突的区块。

3.3 活性分析

定理3  在GST之后，存在一个有界时间T，如果在T内至少n-f个诚实节点都在同一视图中，且该视图中的主节点是诚实节点，那么该视图中一定会提交一个区块至区块链中。

证明  根据算法流程可知，在共识开始前副本节点需要给主节点发送包含PrepareVote.block_h或prepareQC.block_h的NewView消息，而主节点将根据PrepareVote或prepareQC进行扩展生成新区块并发起共识。而在GST之后的时间T内，若所有诚实节点都处在同一视图中，且该视图中的主节点是诚实节点，则所有诚实节点都将完成算法的Prepare、PreCommit和Commit阶段，并最终提交新的区块至区块链中。

3.4 乐观响应性分析

定理4  如果某一视图中的主节点为诚实节点，则主节点一旦收到n-f个NewView消息，便可以创建一个可以被所有副本节点所接受的新区块。

证明  根据算法流程可知，主节点在收到n-f个NewView消息后需要从中挑选视图编号最高的prepareQC，或视图编号最高的f+1个PrepareVote，从而根据其中一个进行扩展生成新区块。其次，需要将所有NewView消息及其签名进行聚合生成aggQC，并在Prepare阶段将其发送给副本节点。而副本节点收到后将从aggQC中提取出新区块以及视图编号最高的prepareQC或f+1个PrepareVote，并判断新区块是否是其中一个的扩展，以判断主节点发出的新区块是否安全。而一个主节点如果是诚实的，那么其总能遵循算法流程，并生成一个安全的区块提案被所有副本节点所接受。

3.5 乐观扩展性分析

定理5  如果某一视图中的主节点为诚实节点，且在该视图中至少n-f个诚实节点收到了新区块提案并投票，则在下一视图中的主节点一旦收到n-f个NewView消息，便能够根据上一视图中未达成共识的区块进行扩展，在一个新的高度生成新区块并发起共识。

证明  如果某一视图中至少n-f个诚实节点收到了新区块提案并发出投票消息PrepareVote，此时主节点发生错误，所有副本节点将移动到下一视图。根据引理3可知，下一视图中的主节点将生成一个新高度的区块block_h+1，且该区块是PrepareVote.block_h的扩展，即下一视图中的主节点能够根据上一视图中未达成共识的区块进行扩展，在一个新的区块高度发起共识。

3.6 算法复杂度分析

本文算法与目前主流强一致性共识算法的复杂度对比结果如表 1所示。

PBFT算法需要节点间互相通信，其中，区块达成共识的复杂度为O(n²)，视图更换的复杂度为O(n³)。Tendermint算法需要节点间互相通信，但将PBFT的视图更换融合进普通的共识过程中，共识与视图更换的复杂度均为O(n²)。HotStuff算法使用门限签名将多个签名聚合为一个，仅需与主节点进行通信，共识与视图更换的复杂度均为O(n)。Fast-HotStuff算法在HotStuff的NewView阶段使用聚合签名代替门限签名，减少了一轮投票，但在复杂度方面没有跨越式改进，依旧为O(n)。本文算法在Fast-HotStuff的基础上增加了一个新的区块扩展方式，但在复杂度方面没有跨越式改进，依旧为O(n)。

4 性能对比

本文采用64位Windows20操作系统，CPU为i7-2675QM，8 GB内存，在单机搭建私有链环境，通过不同端口模拟区块链多节点通信，使用Go-Lang语言对HotStuff、Fast-HotStuff以及本文算法进行仿真实现，并对比共识时延与吞吐量。

4.1 共识时延对比

共识时延表示区块链网络中的出块时间，即区块提交上链所经过的时间。

设节点数量分别为19、31、40、49、61，区块大小为1 MB，3种算法在正常情况下以及主节点在第一轮投票后出错情况下的共识时延对比如图 2所示。其中，在出错情况下，将HotStuff算法的视图超时时间在节点数量为19、31、40、49、61时分别设置为500 ms、800 ms、1 100 ms、1 300 ms、1 600 ms；在本文算法和Fast-HotStuff算法中，将视图超时时间分别设置为500 ms、700 ms、900 ms、1 100 ms、1 300 ms。

由图 2可知，随着节点数量的增加，3种算法在正常情况下以及主节点在第一轮投票后出错情况下，共识时延均呈上升趋势。其中，本文算法与Fast-HotStuff算法中区块的共识过程与视图超时时间均相同，尽管在出错情况下2种算法的区块扩展方式不同，但这并不使得共识时延产生明显差异，因此，无论是在正常情况下还是出错情况下，2种算法的共识时延均相同，且优于HotStuff算法。

4.2 吞吐量对比

尽管在共识时延方面本文算法与Fast-HotStuff算法相同，但在出错情况下的共识时延内，2种算法所能达成共识的区块数量有所不同，因此，提交上链的区块数量不同，这也造成了出错情况下吞吐量的巨大差异。当主节点在第一轮投票后出错时，所有节点将等待超时并进入下一个视图，由于HotStuff和Fast-HotStuff不具备乐观扩展性，因此下一视图中将在一个旧的区块高度进行共识，即在出错情况下的共识时延内仅能使一个区块达成共识，提交一个区块上链。本文算法具备乐观扩展性，因此，下一个视图中将基于上一视图中未达成共识的区块进行扩展，在一个新的区块高度进行共识，基于区块链的链式结构以及算法的容错模型，若新区块达成了共识，则保证了该区块之前未达成共识的父区块也达成了共识，因此，在出错情况下的共识时延内能够提交2个区块上链。当连续f个视图中的主节点在第一轮投票后出错时，HotStuff和Fast-HotStuff在出错情况下的共识时延内依旧仅能提交一个区块上链，而本文算法则为f+1个。

区块链中的吞吐量TPS（Transaction Per-Second）定义为每秒完成的交易数量：

${\rm{TPS}} = {\rm{Transaction}}{{\rm{s}}_{{{\mathit{\Delta}} _t}}}/{{\mathit{\Delta}} _t} $

其中，Δ_t为出块时间，即共识时延，Transactions_∆t为共识时延内的交易总量，一个1 MB的区块通常包含3 000笔交易。

当主节点在第一轮投票后出错时，由于HotStuff和Fast-HotStuff仅提交一个区块上链，交易总量为一个区块内的交易量，即3 000，因此HotStuff与Fast-HotStuff的吞吐量TPS = 3 000/∆_t。本文算法则能提交2个区块上链，交易总量为2个区块内的交易量，即6 000，因此，本文算法的吞吐量TPS = 6 000/∆_t。

图 3所示为主节点在第一轮投票后出错时3种算法的吞吐量对比。

由图 3可知，主节点在第一轮投票后出错时，本文算法在节点数量为19时吞吐量依旧稳定地保持在6 500TPS以上，节点数量增长至61时保持在2 500TPS以上。而HotStuff与Fast-HotStuff则在节点数量为19时吞吐量均为3 500TPS以下，节点数量增长至61时则为1 500TPS以下。

当连续f个视图中的主节点在第一轮投票后出错时，HotStuff和Fast-HotStuff仅提交一个区块上链，交易总量为一个区块内的交易量，即3 000，因此，HotStuff与Fast-HotStuff的吞吐量TPS = 3 000/∆_t。本文算法能够提交f+1个区块上链，交易总量为f+1个区块内的交易量，因此，本文算法的吞吐量TPS = (f+1)×3 000/∆_t。

图 4所示为连续f个视图中的主节点在第一轮投票后出错时3种算法的吞吐量对比。

由图 4可知，当连续f个视图中的主节点在第一轮投票后出错时，本文算法在节点数量为19时吞吐量依旧稳定地保持在6 000TPS以上，节点数量增长至61时保持在2 000TPS以上。而HotStuff与Fast-HotStuff则在节点数量为19时吞吐量均为1 000TPS以下，且随着节点数量的增长，吞吐量将降至500TPS以下。

5 结束语

共识算法的性能直接影响区块链的吞吐量，不仅需要在共识正常的情况下提高吞吐量，还需要在共识发生错误时保证吞吐量不会大幅下降。针对Fast-HotStuff算法中主节点在第一轮投票发生错误时存在吞吐量大幅下降的问题，本文对该算法的NewView阶段和Prepare阶段进行改进，增加一个新的区块扩展方式，当主节点在第一轮投票发生错误时，各节点将其投票消息发送给下一视图中新的主节点，使新的主节点能够根据上一视图中未达成共识的区块进行扩展，在一个新的区块高度发起共识，从而能够在出错情况下的共识时延内提交更多的区块上链，达到提高吞吐量的目的。实验结果表明，相较Fast-HotStuff算法和HotStuff算法，改进算法能够有效提高出错情况下的吞吐量，保证吞吐量的稳定性。下一步将从分片角度对本文算法进行改进，从而提高算法的可扩展性。