改進Fast-HotStuff 區塊鏈共識算法

李啟南，薛志浩，張學軍

（蘭州交通大學電子與信息工程學院，蘭州 730070）

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(n2)的復雜度。主節點發起的一輪共識稱作一個視圖（View），為保證活性，需要對每個視圖設置一個超時時間，若超時前無法達成共識，則將更換新的主節點并開始新的視圖，該操作稱為視圖更換（View Change），具有O(n3)的復雜度，復雜度過高導致其無法應用于大規模節點的網絡環境中。目前，有諸多基于PBFT 的改進共識算法［12-14］被提出，其中，以Tendermint［15］最具代表性。Tendermint 將PBFT 中的視圖更換融入進普通的共識過程中，并通過鎖定和解鎖機制，將視圖更換的復雜度降至O(n2)，但復雜度依舊過高。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-HotStuff 算法

在Fast-HotStuff 算法中，設節點總數為n，最大容錯個數為f，且n=3f+1。共識在一個視圖下進行，每個視圖具有唯一且單調遞增的視圖編號，且存在一個主節點主導共識，共識完成后將開始下一視圖。如果遇到主節點宕機、惡意等異常情況，則等待視圖超時后更換新的主節點并開始新的視圖。

Fast-HotStuff 算法的共識過程如圖1 所示，其中，Prepare、PreCommit 是對一個區塊進行兩輪投票的階段。

圖1 Fast-HotStuff 算法的共識過程Fig.1 Consensus process of Fast-HotStuff algorithm

在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"為消息頭，表示該消息為NewView消息，viewNumber為新視圖的視圖編號，PrepareVote為節點本地所保存的viewNumber 最大的PrepareVote 消息，prepareQC 為節點本地所保存的viewNumber 最大的prepareQC，sigi為節點i對該消息的簽名。

副本節點根據算法1中第1行～第6行判斷NewView消息中第3 個字段要發送的內容，如果prepareQC.viewNumber≥PrepareVote.viewNumber，則發送prepareQC；否則，發送PrepareVote。

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.blockh-1進行擴展以生成新區塊blockh，其中，block下標表示區塊高度。

如果highQC.viewNumber

如算法2中第12行～第14行所示，主節點將n-f個NewView 消息及其簽名使用聚合簽名算法進行聚合生成aggQC，向副本節點發送Prepare 消息：

<"Prepare"，viewNumber，blockh，aggQC >

在Prepare 消息中，blockh為實質區塊，而在其他消息中，blockh則為區塊的哈希值，此舉是為了減少通信量，但為簡化描述，本文統一使用blockh進行表示。

2）副本節點回復消息

如算法2 中第16 行、第17 行所示，副本節點收到Prepare 消息后，從aggQC 中提取highQC 或f+1 個相同的highVote，并根據以下規則判斷是否接受該消息中的blockh：

（1）blockh是highQC.blockh-1的擴展。

（2）blockh是highVote.blockh-1的擴展。

符合上述任意一條則向主節點發送PrepareVote消息：

2.2.3 PreCommit 階段

PreCommit 階段包括以下過程：

1）主節點廣播消息

如算法3 中第1 行～第5 行所示，主節點將收到的n-f 個PrepareVote 消息及其簽名使用門限簽名算法進行聚合生成prepareQC，向副本節點發送PreCommit消息：

<"PreCommit"，viewNumber，blockh，prepareQC >

2）副本節點回復消息

如算法3 中第6 行～第8 行所示，副本節點收到PreCommit消息后，向主節點發送PreCommitVote消息：

2.2.4 Commit 階段

Commit 階段主要包括以下過程：

1）主節點廣播消息

如算法4 中第1 行～第5 行所示，主節點將收到的n-f個PreCommitVote 消息及其簽名使用門限簽名算法進行聚合生成preCommitQC，并向副本節點發送Commit 消息：

<"Commit"，viewNumber，blockh，preCommitQC>

2）副本節點添加區塊

如算法4 中第6 行、第7 行所示，副本節點收到Commit 消息后，將blockh提交到區塊鏈中，至此一個區塊的共識完成，副本節點將向主節點發送NewView 消息并開始下一個視圖。

3 算法分析

本文首先給出若干基本引理，然后根據基本引理對算法的安全性、活性、樂觀響應性以及樂觀擴展性進行證明，最后分析算法復雜度。

3.1 基本引理

算法中存在2 種類型的QC，即prepareQC 和preCommitQC，以QC.type 表示QC類型，QC.viewNumber 表示QC的視圖編號，QC.blockh表示該QC高度為h的區塊。

引理1對于任意2 個有效的QC1 和QC2，假設QC1.type=QC2.type，且QC1.blockh和QC2.blockh沖突，則必然有QC1.viewNumber ≠QC2.viewNumber。

證明假設QC1.viewNumber=QC2.viewNumber，由于一個有效的QC 是由n-f=2f+1 個節點的投票（簽名）所組成的，則說明至少存在一個誠實節點在同一個視圖中的同一個階段發出了2 個不同區塊的投票消息，這與n=3f+1 的容錯模型相悖。

引理2如果在某一視圖中至少n-f個節點收到了prepareQC，那么下一個區塊blockh+1將是prepareQC.blockh的擴展。

證明如果在某一視圖中至少n-f=2f+1個節點收到了prepareQC，那么在下一視圖中主節點所收到的n-f=2f+1 個NewView 消息中，將至少包含1 個誠實節點所發送的prepareQC，該prepareQC 將作為highQC，因此下一個區塊blockh+1將是prepareQC.blockh的擴展。

引理3如果在某一視圖中主節點是誠實節點，且在該視圖中至少n-f個誠實節點收到了新區塊提案并發出PrepareVote 消息，那么下一個區塊blockh+1將是PrepareVote.blockh的擴展。

證明如果在某一視圖viewNumber=ν中主節點是誠實節點，且在該視圖中至少n-f個誠實節點收到了新區塊提案并發出PrepareVote 消息，那么在下一視圖viewNumber=ν+1 中，主節點所收到的n-f=2f+1 個NewView 消息中，將至少包含f+1 個誠實節點在視圖ν中所發送的PrepareVote，該PrepareVote將作為highVote，因此下一個區塊blockh+1將是PrepareVote.blockh的擴展。

3.2 安全性分析

定理1在同一視圖中不會提交2 個沖突的區塊。

證明根據算法流程可知，提交一個區塊至區塊鏈中需要完成算法的所有階段，而在這些階段中將產生prepareQC 和preCommitQC，根據引理1 可知，同一視圖中不會存在2 個相同類型的不同QC，因此，不會存在2 個區塊在同一視圖中完成所有階段，即同一視圖中不會提交2 個沖突的區塊。

定理2在不同的視圖中不會提交2個沖突的區塊。

證明假設存在區塊block1h和block2h沖突，且block1h.viewNumber ＜block2h.viewNumber。如 果block1h已被至少1 個節點提交，則說明該節點收到了preCommitQC.block1h，進而說明至少n-f=2f+1 個節點收到了prepareQC.block1h。根據引理2 可知，下一個區塊blockh+1將是prepareQC.block1h的擴展，即下一個區塊的高度應為h+1。如果下一視圖中主節點發起block2h的共識，則會被至少f+1 個誠實節點所拒絕，而block2h將無法完成共識，因此，在不同的視圖中不會提交2 個沖突的區塊。

3.3 活性分析

定理3在GST 之后，存在一個有界時間T，如果在T內至少n-f個誠實節點都在同一視圖中，且該視圖中的主節點是誠實節點，那么該視圖中一定會提交一個區塊至區塊鏈中。

證明根據算法流程可知，在共識開始前副本節點需要給主節點發送包含PrepareVote 或prepareQC 的NewView 消息，而主節點將根據PrepareVote.blockh或prepareQC.blockh進行擴展生成新區塊并發起共識。而在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 可知，下一視圖中的主節點將生成一個新高度的區塊blockh+1，且該區塊是PrepareVote.blockh的擴展，即下一視圖中的主節點能夠根據上一視圖中未達成共識的區塊進行擴展，在一個新的區塊高度發起共識。

3.6 算法復雜度分析

本文算法與目前主流強一致性共識算法的復雜度對比結果如表1 所示。

表1 復雜度對比結果Table 1 Complexity comparison results

PBFT 算法需要節點間互相通信，其中，區塊達成共識的復雜度為O(n2)，視圖更換的復雜度為O(n3)。Tendermint 算法需要節點間互相通信，但將PBFT 的視圖更換融合進普通的共識過程中，共識與視圖更換的復雜度均為O(n2)。HotStuff算法使用門限簽名將多個簽名聚合為一個，僅需與主節點進行通信，共識與視圖更換的復雜度均為O(n)。Fast-HotStuff算法在HotStuff的NewView 階段使用聚合簽名代替門限簽名，減少了一輪投票，但在復雜度方面沒有跨越式改進，依舊為O(n)。本文算法在Fast-HotStuff 的基礎上增加了一個新的區塊擴展方式，但在復雜度方面沒有跨越式改進，依舊為O(n)。

4 性能對比

本文采用64 位Windows10 操作系統，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 共識時延對比Fig.2 Consensus delay comparison

由圖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）定義為每秒完成的交易數量：

其中，Δ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 吞吐量對比結果1Fig.3 Throughput comparison result 1

由圖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 吞吐量對比結果2Fig.4 Throughput comparison result 2

由圖4 可知，當連續f個視圖中的主節點在第一輪投票后出錯時，本文算法在節點數量為19 時吞吐量依舊穩定地保持在6 000TPS 以上，節點數量增長至61 時保持在2 000TPS 以上。而HotStuff 與Fast-HotStuff 則在節點數量為19 時吞吐量均為1 000TPS 以下，且隨著節點數量的增長，吞吐量將降至500TPS 以下。

5 結束語

共識算法的性能直接影響區塊鏈的吞吐量，不僅需要在共識正常的情況下提高吞吐量，還需要在共識發生錯誤時保證吞吐量不會大幅下降。針對Fast-HotStuff 算法中主節點在第一輪投票發生錯誤時存在吞吐量大幅下降的問題，本文對該算法的NewView 階段和Prepare 階段進行改進，增加一個新的區塊擴展方式，當主節點在第一輪投票發生錯誤時，各節點將其投票消息發送給下一視圖中新的主節點，使新的主節點能夠根據上一視圖中未達成共識的區塊進行擴展，在一個新的區塊高度發起共識，從而能夠在出錯情況下的共識時延內提交更多的區塊上鏈，達到提高吞吐量的目的。實驗結果表明，相較Fast-HotStuff 算法和HotStuff算法，改進算法能夠有效提高出錯情況下的吞吐量，保證吞吐量的穩定性。下一步將從分片角度對本文算法進行改進，從而提高算法的可擴展性。