李啟南，薛志浩，張學(xué)軍

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

0 概述

共識算法根據(jù)容錯類型可分為故障容錯（Crash Fault Tolerance，CFT）共識算法和拜占庭容錯（Byzantine Fault Tolerance，BFT）共識算法［1］。故障容錯共識算法主要采用Paxos［2］及Raft［3］等，只能容忍節(jié)點(diǎn)發(fā)生宕機(jī)等錯誤，若存在惡意節(jié)點(diǎn)，則無法保證誠實(shí)節(jié)點(diǎn)數(shù)據(jù)的一致性。拜占庭容錯共識算法的目的是解決拜占庭將軍問題［4］，即使系統(tǒng)中存在惡意節(jié)點(diǎn)（不超過一定比例），依舊能夠保證誠實(shí)節(jié)點(diǎn)數(shù)據(jù)的一致性。拜占庭將軍問題最早由LAMPORT 等人在1982 年提出，并給出了口頭協(xié)議和書面協(xié)議2 種拜占庭容錯算法，但其復(fù)雜度為指數(shù)級，在實(shí)際中并不實(shí)用。1999 年，LISCOV 等［5］提出實(shí)用拜占庭容錯（Practical Byzantine Fault Tolerance，PBFT）算法，通過兩輪投票的方式將其復(fù)雜度降至多項(xiàng)式級，但是，拜占庭容錯應(yīng)用場景較少，因此，該算法未獲得學(xué)術(shù)界的廣泛關(guān)注。2008 年，中本聰提出比特幣的概念，隨著數(shù)字貨幣及其底層區(qū)塊鏈技術(shù)的逐漸興起，拜占庭容錯算法逐漸受到重視。

目前，區(qū)塊鏈中常用的拜占庭容錯算法可分為弱一致性（又稱最終一致性）算法和強(qiáng)一致性算法［6］。弱一致性算法允許數(shù)據(jù)在某一時間點(diǎn)可以存在不一致的情況，其典型代表包括工作量證明（Proof of Work，PoW）［7］、權(quán)益證明（Proof of Stack，PoS）［8］和委托權(quán)益證明（Delegate Proof of Stack，DPoS）［9］等，由于需要使用最長鏈原則解決分叉問題，因此一筆交易發(fā)出后并不能確保一定能夠成功，這在商用區(qū)塊鏈場景下是不可接受的，因此，弱一致性算法在公有鏈中應(yīng)用較為廣泛，在聯(lián)盟鏈中應(yīng)用較少。強(qiáng)一致性算法則在任何情況下都不允許區(qū)塊鏈出現(xiàn)分叉情況，一個區(qū)塊一旦添加便不會被撤銷，其更加適用于商用聯(lián)盟鏈場景。

PBFT 作為一種經(jīng)典的強(qiáng)一致性算法，被廣泛應(yīng)用于區(qū)塊鏈中，如Hyperledger Fabric［10］、Neo［11］等。在PBFT 中，一個區(qū)塊達(dá)成共識需要O(n2)的復(fù)雜度。主節(jié)點(diǎn)發(fā)起的一輪共識稱作一個視圖（View），為保證活性，需要對每個視圖設(shè)置一個超時時間，若超時前無法達(dá)成共識，則將更換新的主節(jié)點(diǎn)并開始新的視圖，該操作稱為視圖更換（View Change），具有O(n3)的復(fù)雜度，復(fù)雜度過高導(dǎo)致其無法應(yīng)用于大規(guī)模節(jié)點(diǎn)的網(wǎng)絡(luò)環(huán)境中。目前，有諸多基于PBFT 的改進(jìn)共識算法［12-14］被提出，其中，以Tendermint［15］最具代表性。Tendermint 將PBFT 中的視圖更換融入進(jìn)普通的共識過程中，并通過鎖定和解鎖機(jī)制，將視圖更換的復(fù)雜度降至O(n2)，但復(fù)雜度依舊過高。YIN 等［16］提出了HotStuff，其使用門限簽名［17-19］對Tendermint進(jìn)行改進(jìn)，將共識與視圖更換的復(fù)雜度均降至O(n)，并通過三輪投票五個階段（NewView、Prepare、PreCommit、Commit、Decide）的方式實(shí)現(xiàn)樂觀響應(yīng)性（Optimistic Responsiveness）。由于HotStuff 具有較低的復(fù)雜度，因此受到了廣泛關(guān)注，F(xiàn)acebook的Libra［20］項(xiàng)目便采用了HotStuff算法。此后，JALALZAI 等［21］提出了Fast-HostStuff，在NewView 階段使用聚合簽名［22］代替HotStuff 中的門限簽名，實(shí)現(xiàn)兩輪投票四個階段（NewView、Prepare、PreCommit、Commit）的HotStuff，提高了執(zhí)行效率，并同時具備樂觀響應(yīng)性。在HotStuff 與Fast-HostStuff 中，若共識能夠正常執(zhí)行或主節(jié)點(diǎn)在第二輪投票后發(fā)生錯誤，則均能保證較高的吞吐量，然而若主節(jié)點(diǎn)在第一輪投票后發(fā)生錯誤，則吞吐量將大幅降低。

本文提出一種改進(jìn)的Fast-HotStuff 算法，并實(shí)現(xiàn)一種新的特性，定義為樂觀擴(kuò)展性（Optimistic Extensibility）。樂觀擴(kuò)展性要求在樂觀條件下，即便主節(jié)點(diǎn)在第一輪投票后發(fā)生錯誤，下一視圖中新的主節(jié)點(diǎn)依舊能夠根據(jù)其上一視圖中未達(dá)成共識的區(qū)塊進(jìn)行擴(kuò)展，在一個新的高度生成新區(qū)塊并發(fā)起共識。其中，樂觀條件是指當(dāng)前視圖的主節(jié)點(diǎn)為誠實(shí)節(jié)點(diǎn)，且至少有n-f（n為節(jié)點(diǎn)總數(shù)，f為最大容錯個數(shù)）個誠實(shí)節(jié)點(diǎn)能夠收到主節(jié)點(diǎn)的新區(qū)塊提案。實(shí)現(xiàn)樂觀擴(kuò)展性意味著若主節(jié)點(diǎn)在第一輪投票后發(fā)生錯誤，則能夠在出錯情況下的共識時延內(nèi)使更多區(qū)塊達(dá)成共識，從而提交更多區(qū)塊上鏈，達(dá)到提高吞吐量的目的。為實(shí)現(xiàn)樂觀擴(kuò)展性，本文算法設(shè)計一個新的區(qū)塊擴(kuò)展方式，區(qū)塊在某一視圖的共識過程中，若主節(jié)點(diǎn)在第一輪投票發(fā)生錯誤導(dǎo)致視圖更換，則副本節(jié)點(diǎn)將其第一輪投票消息傳遞至下一視圖，下一視圖中的主節(jié)點(diǎn)若收到f+1 個相同區(qū)塊的投票消息，則根據(jù)該區(qū)塊進(jìn)行擴(kuò)展生成新的區(qū)塊并發(fā)起共識。

1 Fast-HotStuff 算法

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

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

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

在Prepare 階段，主節(jié)點(diǎn)向副本節(jié)點(diǎn)廣播新區(qū)塊提案，副本節(jié)點(diǎn)向主節(jié)點(diǎn)發(fā)送對該區(qū)塊的投票消息，投票即為對該消息進(jìn)行簽名。主節(jié)點(diǎn)收到n-f個消息后，將所有消息及其簽名進(jìn)行聚合生成一個QC（Quorum Certificate），稱為prepareQC，視作第一輪投票達(dá)成的證據(jù)。

在PreCommit 階段，主節(jié)點(diǎn)將prepareQC 廣播給副本節(jié)點(diǎn)，副本節(jié)點(diǎn)向主節(jié)點(diǎn)發(fā)送第二輪投票消息，主節(jié)點(diǎn)收到消息后生成preCommitQC，視作第二輪投票達(dá)成的證據(jù)。

在Commit 階段，主節(jié)點(diǎn)向副本節(jié)點(diǎn)廣播preCommitQC，副本節(jié)點(diǎn)收到后將區(qū)塊提交至區(qū)塊鏈中。

在每個視圖開始前的NewView 階段，副本節(jié)點(diǎn)向主節(jié)點(diǎn)發(fā)送NewView 消息，消息中包含副本節(jié)點(diǎn)所保存的視圖編號最大的prepareQC。主節(jié)點(diǎn)從收到的n-f個消息中挑選視圖編號最大的prepareQC 作為highQC，并根據(jù)highQC.block（highQC 的區(qū)塊）進(jìn)行擴(kuò)展生成新的區(qū)塊，然后對n-f個NewView 消息及其簽名進(jìn)行聚合生成aggQC，主節(jié)點(diǎn)在Prepare 階段會將新區(qū)塊以及aggQC 一起廣播給副本節(jié)點(diǎn)。

prepareQC 以及preCommitQC 的生成使用的是門限簽名，而aggQC 的生成使用的是聚合簽名，這是由于n-f個NewView 消息內(nèi)容可能存在不同的情況，而聚合簽名可以對不同消息的簽名進(jìn)行聚合。副本節(jié)點(diǎn)收到后會從aggQC 中提取出highQC，并判斷新區(qū)塊是否為highQC.block 的擴(kuò)展，如果是，則接受該區(qū)塊并發(fā)出投票。

在Fast-HotStuff 中，如果主節(jié)點(diǎn)在第二輪投票后發(fā)生錯誤，無法在Commit 階段廣播第二輪的投票結(jié)果（preCommitQC），那么在視圖更換之后的新視圖中，新的主節(jié)點(diǎn)依舊可以在一個新的區(qū)塊高度生成新區(qū)塊，這是由于新區(qū)塊的生成是根據(jù)第一輪投票結(jié)果（prepareQC）。然而，如果主節(jié)點(diǎn)在第一輪投票完成后發(fā)生錯誤，無法在PreCommit 階段廣播第一輪的投票結(jié)果（prepareQC），則新的主節(jié)點(diǎn)便無法在一個新的區(qū)塊高度生成新區(qū)塊，設(shè)想以下案例：

1）假設(shè)在某一視圖中所共識區(qū)塊的高度為h，在Prepare 階段至少有n-f個副本節(jié)點(diǎn)向主節(jié)點(diǎn)發(fā)送了該區(qū)塊的第一輪投票消息，而此時主節(jié)點(diǎn)發(fā)生錯誤，無法向副本節(jié)點(diǎn)廣播prepareQC。

2）副本節(jié)點(diǎn)在視圖超時前未收到主節(jié)點(diǎn)發(fā)送的prepareQC，將向新的主節(jié)點(diǎn)發(fā)送NewView 消息并開啟新的視圖。

3）新的主節(jié)點(diǎn)收到了n-f=2f+1 個副本節(jié)點(diǎn)發(fā)送的NewView 消息，但其中不包含舊的主節(jié)點(diǎn)所持有的最新prepareQC，因此，新主節(jié)點(diǎn)將重新生成一個高度為h的區(qū)塊并發(fā)起共識。

從上述案例可以發(fā)現(xiàn)，各節(jié)點(diǎn)已收到主節(jié)點(diǎn)的新區(qū)塊提案，并對高度為h的區(qū)塊進(jìn)行投票，然而主節(jié)點(diǎn)發(fā)生錯誤導(dǎo)致視圖更換，新的主節(jié)點(diǎn)無法收到投票結(jié)果從而根據(jù)上一視圖中的區(qū)塊進(jìn)行擴(kuò)展，在一個新的高度（h+1）生成區(qū)塊并發(fā)起共識。如果連續(xù)f個視圖中的主節(jié)點(diǎn)在上述情況中發(fā)生錯誤，則相當(dāng)于連續(xù)f+1 個視圖中僅生成了一個區(qū)塊，這將大幅降低區(qū)塊鏈的吞吐量，這一問題不僅存在于Fast-HotStuff 中，在HotStuff 中也同 樣存在。

2 改進(jìn)的Fast-HotStuff 算法

2.1 算法概述

算法容錯模型：設(shè)系統(tǒng)中包括n=3f+1 個節(jié)點(diǎn)，用i表示節(jié)點(diǎn)編號，i∈［n］where［n］=｛1，2，…，n｝。設(shè)惡意節(jié)點(diǎn)集合為F?［n］，則集合最大容錯個數(shù)為|F|=f。

算法網(wǎng)絡(luò)模型：算法采用部分同步（Partial Synchrony）網(wǎng)絡(luò)模型，即系統(tǒng)中存在不確定且無法預(yù)知的全局穩(wěn)定時間（Global Stable Time，GST）和消息傳輸上限。在GST 之前，系統(tǒng)處于異步（Asynchronous）狀態(tài)；在GST 之后，系統(tǒng)處于同步（Synchrony）狀態(tài)，即在GST 之后，節(jié)點(diǎn)間的消息能夠在消息傳輸上限內(nèi)到達(dá)。其次，網(wǎng)絡(luò)通信是點(diǎn)對點(diǎn)且可靠的，通信內(nèi)容是經(jīng)過簽名且可驗(yàn)證的，惡意節(jié)點(diǎn)不具有進(jìn)行哈希碰撞、簽名偽造等密碼學(xué)攻擊方式所需的計算能力。

算法中的數(shù)字簽名技術(shù)：相比聚合簽名，門限簽名效率更高，但只能對同一消息進(jìn)行聚合，而聚合簽名則可以對不同消息進(jìn)行聚合，因此，本文算法在NewView 階段使用聚合簽名，而在其他階段使用門限簽名。

算法中的區(qū)塊鏈結(jié)構(gòu)：每個節(jié)點(diǎn)都維持一個區(qū)塊樹，一個父區(qū)塊可以有多個子區(qū)塊，子區(qū)塊中包含父區(qū)塊的哈希值，但并非所有區(qū)塊都是有效區(qū)塊，只有區(qū)塊鏈中的區(qū)塊才是有效區(qū)塊。區(qū)塊鏈?zhǔn)菂^(qū)塊樹中的一個分支，即最后一個完成算法所有階段的區(qū)塊所在的分支。在正常情況下，區(qū)塊鏈中的所有區(qū)塊都將完成所有階段，但若存在惡意節(jié)點(diǎn)阻礙共識或出現(xiàn)網(wǎng)絡(luò)延遲，則可能導(dǎo)致區(qū)塊鏈中某些區(qū)塊未完成所有階段，但是這對安全性并不會造成影響，因?yàn)樗姓\實(shí)節(jié)點(diǎn)都將認(rèn)同區(qū)塊樹中唯一的一條區(qū)塊鏈。

改進(jìn)的Fast-HotStuff 算法分為NewView、Prepare、PreCommit 和Commit 4 個階段，具體如下：

1）在NewView 階段，主節(jié)點(diǎn)將收集n-f個副本節(jié)點(diǎn)發(fā)送的NewView 消息，并生成一個新區(qū)塊，在新的視圖中開啟共識。

2）在Prepare 階段，主節(jié)點(diǎn)向副本節(jié)點(diǎn)發(fā)送包含新區(qū)塊的Prepare 消息，副本節(jié)點(diǎn)收到后向主節(jié)點(diǎn)發(fā)送PrepareVote 消息并進(jìn)行第一輪投票，投票即是對該消息生成簽名。

3）在PreCommit 階段，主節(jié)點(diǎn)在收到n-f個PrepareVote 消息后，將所有消息及其簽名進(jìn)行聚合生成prepareQC，并向副本節(jié)點(diǎn)發(fā)送PreCommit 消息，消息中包含prepareQC。副本節(jié)點(diǎn)收到后向主節(jié)點(diǎn)發(fā)送PreCommitVote 消息并進(jìn)行第二輪投票。

4）在Commit 階段，主節(jié)點(diǎn)在收到n-f個PreCommitVote 消息后，將所有消息及其簽名進(jìn)行聚合生成preCommitQC，并向副本節(jié)點(diǎn)發(fā)送Commit 消息，消息中包含preCommitQC，副本節(jié)點(diǎn)收到后將區(qū)塊提交至區(qū)塊鏈中。

為實(shí)現(xiàn)樂觀擴(kuò)展性，本文算法對NewView 階段及Prepare 階段進(jìn)行改進(jìn)，增加一個新的區(qū)塊擴(kuò)展方式。在某一視圖中，若主節(jié)點(diǎn)在第一輪投票后發(fā)生錯誤，無法廣播第一輪投票結(jié)果prepareQC，從而導(dǎo)致視圖超時，則副本節(jié)點(diǎn)將其在該視圖中的PrepareVote 消息包含于NewView 消息中發(fā)送給下一視圖中新的主節(jié)點(diǎn)，新的主節(jié)點(diǎn)所收到的n-f個NewView 消息中若存在f+1 個相同的PrepareVote，則根據(jù)PrepareVote.block 進(jìn)行擴(kuò)展以生成新的區(qū)塊，從而使新的主節(jié)點(diǎn)能夠根據(jù)上一視圖中未達(dá)成共識的區(qū)塊進(jìn)行擴(kuò)展，在一個新的高度生成區(qū)塊并發(fā)起共識。其中，要求f+1 的原因是因?yàn)樾碌闹鞴?jié)點(diǎn)所收到的n-f個PrepareVote 中，可能存在f個惡意節(jié)點(diǎn)所發(fā)送的PrepareVote 與誠實(shí)節(jié)點(diǎn)不同，因此要求n-f-f=f+1 個相同的PrepareVote?；趨^(qū)塊鏈的鏈?zhǔn)浇Y(jié)構(gòu)以及算法的容錯模型，若在新的視圖中一個新高度的區(qū)塊達(dá)成了共識，則保證了該區(qū)塊之前未達(dá)成共識的父區(qū)塊或更早的區(qū)塊也達(dá)成了共識，因此，在出錯情況下的共識時延內(nèi)，能夠提交更多的區(qū)塊上鏈，從而提高吞吐量。

2.2 算法設(shè)計

2.2.1 NewView 階段

主節(jié)點(diǎn)接收n-f個副本節(jié)點(diǎn)（包括主節(jié)點(diǎn)自身）所發(fā)送的NewView 消息：

其中，"NewView"為消息頭，表示該消息為NewView消息，viewNumber為新視圖的視圖編號，PrepareVote為節(jié)點(diǎn)本地所保存的viewNumber 最大的PrepareVote 消息，prepareQC 為節(jié)點(diǎn)本地所保存的viewNumber 最大的prepareQC，sigi為節(jié)點(diǎn)i對該消息的簽名。

副本節(jié)點(diǎn)根據(jù)算法1中第1行～第6行判斷NewView消息中第3 個字段要發(fā)送的內(nèi)容，如果prepareQC.viewNumber≥PrepareVote.viewNumber，則發(fā)送prepareQC；否則，發(fā)送PrepareVote。

2.2.2 Prepare 階段

Prepare 階段包括以下過程：

1）主節(jié)點(diǎn)廣播消息

如算法2 中第3 行、第4 行所示，主節(jié)點(diǎn)在收到的n-f個NewView 消息中挑選視圖編號最大的prepareQC和PrepareVote 作為highQC 和highVote。

設(shè)當(dāng)前視圖將對高度為h的區(qū)塊進(jìn)行共識，主節(jié)點(diǎn)根據(jù)算法2 中第5 行～第11 行的規(guī)則進(jìn)行新區(qū)塊生成。如果highQC.viewNumber ≥highVote.viewNumber，則根據(jù)highQC.blockh-1進(jìn)行擴(kuò)展以生成新區(qū)塊blockh，其中，block下標(biāo)表示區(qū)塊高度。

如果highQC.viewNumber

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

<"Prepare"，viewNumber，blockh，aggQC >

在Prepare 消息中，blockh為實(shí)質(zhì)區(qū)塊，而在其他消息中，blockh則為區(qū)塊的哈希值，此舉是為了減少通信量，但為簡化描述，本文統(tǒng)一使用blockh進(jìn)行表示。

2）副本節(jié)點(diǎn)回復(fù)消息

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

（1）blockh是highQC.blockh-1的擴(kuò)展。

（2）blockh是highVote.blockh-1的擴(kuò)展。

符合上述任意一條則向主節(jié)點(diǎn)發(fā)送PrepareVote消息：

2.2.3 PreCommit 階段

PreCommit 階段包括以下過程：

1）主節(jié)點(diǎn)廣播消息

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

<"PreCommit"，viewNumber，blockh，prepareQC >

2）副本節(jié)點(diǎn)回復(fù)消息

如算法3 中第6 行～第8 行所示，副本節(jié)點(diǎn)收到PreCommit消息后，向主節(jié)點(diǎn)發(fā)送PreCommitVote消息：

2.2.4 Commit 階段

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

1）主節(jié)點(diǎn)廣播消息

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

<"Commit"，viewNumber，blockh，preCommitQC>

2）副本節(jié)點(diǎn)添加區(qū)塊

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

3 算法分析

本文首先給出若干基本引理，然后根據(jù)基本引理對算法的安全性、活性、樂觀響應(yīng)性以及樂觀擴(kuò)展性進(jìn)行證明，最后分析算法復(fù)雜度。

3.1 基本引理

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

引理1對于任意2 個有效的QC1 和QC2，假設(shè)QC1.type=QC2.type，且QC1.blockh和QC2.blockh沖突，則必然有QC1.viewNumber ≠Q(mào)C2.viewNumber。

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

引理2如果在某一視圖中至少n-f個節(jié)點(diǎn)收到了prepareQC，那么下一個區(qū)塊blockh+1將是prepareQC.blockh的擴(kuò)展。

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

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

證明如果在某一視圖viewNumber=ν中主節(jié)點(diǎn)是誠實(shí)節(jié)點(diǎn)，且在該視圖中至少n-f個誠實(shí)節(jié)點(diǎn)收到了新區(qū)塊提案并發(fā)出PrepareVote 消息，那么在下一視圖viewNumber=ν+1 中，主節(jié)點(diǎn)所收到的n-f=2f+1 個NewView 消息中，將至少包含f+1 個誠實(shí)節(jié)點(diǎn)在視圖ν中所發(fā)送的PrepareVote，該P(yáng)repareVote將作為highVote，因此下一個區(qū)塊blockh+1將是PrepareVote.blockh的擴(kuò)展。

3.2 安全性分析

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

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

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

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

3.3 活性分析

定理3在GST 之后，存在一個有界時間T，如果在T內(nèi)至少n-f個誠實(shí)節(jié)點(diǎn)都在同一視圖中，且該視圖中的主節(jié)點(diǎn)是誠實(shí)節(jié)點(diǎn)，那么該視圖中一定會提交一個區(qū)塊至區(qū)塊鏈中。

證明根據(jù)算法流程可知，在共識開始前副本節(jié)點(diǎn)需要給主節(jié)點(diǎn)發(fā)送包含PrepareVote 或prepareQC 的NewView 消息，而主節(jié)點(diǎn)將根據(jù)PrepareVote.blockh或prepareQC.blockh進(jìn)行擴(kuò)展生成新區(qū)塊并發(fā)起共識。而在GST 之后的時間T內(nèi)，若所有誠實(shí)節(jié)點(diǎn)都處在同一視圖中，且該視圖中的主節(jié)點(diǎn)是誠實(shí)節(jié)點(diǎn)，則所有誠實(shí)節(jié)點(diǎn)都將完成算法的Prepare、PreCommit 和Commit階段，并最終提交新的區(qū)塊至區(qū)塊鏈中。

3.4 樂觀響應(yīng)性分析

定理4如果某一視圖中的主節(jié)點(diǎn)為誠實(shí)節(jié)點(diǎn)，則主節(jié)點(diǎn)一旦收到n-f個NewView 消息，便可以創(chuàng)建一個可以被所有副本節(jié)點(diǎn)所接受的新區(qū)塊。

證明根據(jù)算法流程可知，主節(jié)點(diǎn)在收到n-f個NewView 消息后需要從中挑選視圖編號最高的prepareQC，或視圖編號最高的f+1 個PrepareVote，從而根據(jù)其中一個進(jìn)行擴(kuò)展生成新區(qū)塊。其次，需要將所有NewView 消息及其簽名進(jìn)行聚合生成aggQC，并在Prepare 階段將其發(fā)送給副本節(jié)點(diǎn)。而副本節(jié)點(diǎn)收到后將從aggQC 中提取出新區(qū)塊以及視圖編號最高的prepareQC 或f+1 個PrepareVote，并判斷新區(qū)塊是否是其中一個的擴(kuò)展，以判斷主節(jié)點(diǎn)發(fā)出的新區(qū)塊是否安全。而一個主節(jié)點(diǎn)如果是誠實(shí)的，那么其總能遵循算法流程，并生成一個安全的區(qū)塊提案被所有副本節(jié)點(diǎn)所接受。

3.5 樂觀擴(kuò)展性分析

定理5如果某一視圖中的主節(jié)點(diǎn)為誠實(shí)節(jié)點(diǎn)，且在該視圖中至少n-f個誠實(shí)節(jié)點(diǎn)收到了新區(qū)塊提案并投票，則在下一視圖中的主節(jié)點(diǎn)一旦收到n-f個NewView 消息，便能夠根據(jù)上一視圖中未達(dá)成共識的區(qū)塊進(jìn)行擴(kuò)展，在一個新的高度生成新區(qū)塊并發(fā)起共識。

證明如果某一視圖中至少n-f個誠實(shí)節(jié)點(diǎn)收到了新區(qū)塊提案并發(fā)出投票消息PrepareVote，此時主節(jié)點(diǎn)發(fā)生錯誤，所有副本節(jié)點(diǎn)將移動到下一視圖。根據(jù)引理3 可知，下一視圖中的主節(jié)點(diǎn)將生成一個新高度的區(qū)塊blockh+1，且該區(qū)塊是PrepareVote.blockh的擴(kuò)展，即下一視圖中的主節(jié)點(diǎn)能夠根據(jù)上一視圖中未達(dá)成共識的區(qū)塊進(jìn)行擴(kuò)展，在一個新的區(qū)塊高度發(fā)起共識。

3.6 算法復(fù)雜度分析

本文算法與目前主流強(qiáng)一致性共識算法的復(fù)雜度對比結(jié)果如表1 所示。

表1 復(fù)雜度對比結(jié)果Table 1 Complexity comparison results

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

4 性能對比

本文采用64 位Windows10 操作系統(tǒng)，CPU 為i7-2675QM，8 GB 內(nèi)存，在單機(jī)搭建私有鏈環(huán)境，通過不同端口模擬區(qū)塊鏈多節(jié)點(diǎn)通信，使用Go-Lang語言對HotStuff、Fast-HotStuff 以及本文算法進(jìn)行仿真實(shí)現(xiàn)，并對比共識時延與吞吐量。

4.1 共識時延對比

共識時延表示區(qū)塊鏈網(wǎng)絡(luò)中的出塊時間，即區(qū)塊提交上鏈所經(jīng)過的時間。

設(shè)節(jié)點(diǎn)數(shù)量分別為19、31、40、49、61，區(qū)塊大小為1 MB，3 種算法在正常情況下以及主節(jié)點(diǎn)在第一輪投票后出錯情況下的共識時延對比如圖2 所示。其中，在出錯情況下，將HotStuff 算法的視圖超時時間在節(jié)點(diǎn)數(shù)量為19、31、40、49、61 時分別設(shè)置為500 ms、800 ms、1 100 ms、1 300 ms、1 600 ms；在本文算法和Fast-HotStuff 算法中，將視圖超時時間分別設(shè)置為500 ms、700 ms、900 ms、1 100 ms、1 300 ms。

圖2 共識時延對比Fig.2 Consensus delay comparison

由圖2 可知，隨著節(jié)點(diǎn)數(shù)量的增加，3 種算法在正常情況下以及主節(jié)點(diǎn)在第一輪投票后出錯情況下，共識時延均呈上升趨勢。其中，本文算法與Fast-HotStuff 算法中區(qū)塊的共識過程與視圖超時時間均相同，盡管在出錯情況下2 種算法的區(qū)塊擴(kuò)展方式不同，但這并不使得共識時延產(chǎn)生明顯差異，因此，無論是在正常情況下還是出錯情況下，2 種算法的共識時延均相同，且優(yōu)于HotStuff 算法。

4.2 吞吐量對比

盡管在共識時延方面本文算法與Fast-HotStuff算法相同，但在出錯情況下的共識時延內(nèi)，2 種算法所能達(dá)成共識的區(qū)塊數(shù)量有所不同，因此，提交上鏈的區(qū)塊數(shù)量不同，這也造成了出錯情況下吞吐量的巨大差異。當(dāng)主節(jié)點(diǎn)在第一輪投票后出錯時，所有節(jié)點(diǎn)將等待超時并進(jìn)入下一個視圖，由于HotStuff和Fast-HotStuff 不具備樂觀擴(kuò)展性，因此下一視圖中將在一個舊的區(qū)塊高度進(jìn)行共識，即在出錯情況下的共識時延內(nèi)僅能使一個區(qū)塊達(dá)成共識，提交一個區(qū)塊上鏈。本文算法具備樂觀擴(kuò)展性，因此，下一個視圖中將基于上一視圖中未達(dá)成共識的區(qū)塊進(jìn)行擴(kuò)展，在一個新的區(qū)塊高度進(jìn)行共識，基于區(qū)塊鏈的鏈?zhǔn)浇Y(jié)構(gòu)以及算法的容錯模型，若新區(qū)塊達(dá)成了共識，則保證了該區(qū)塊之前未達(dá)成共識的父區(qū)塊也達(dá)成了共識，因此，在出錯情況下的共識時延內(nèi)能夠提交2 個區(qū)塊上鏈。當(dāng)連續(xù)f個視圖中的主節(jié)點(diǎn)在第一輪投票后出錯時，HotStuff 和Fast-HotStuff 在出錯情況下的共識時延內(nèi)依舊僅能提交一個區(qū)塊上鏈，而本文算法則為f+1 個。

區(qū)塊鏈中的吞吐量TPS（Transaction Per-Second）定義為每秒完成的交易數(shù)量：

其中，Δt為出塊時間，即共識時延為共識時延內(nèi)的交易總量，一個1 MB 的區(qū)塊通常包含3 000 筆交易。

當(dāng)主節(jié)點(diǎn)在第一輪投票后出錯時，由于HotStuff和Fast-HotStuff僅提交一個區(qū)塊上鏈，交易總量為一個區(qū)塊內(nèi)的交易量，即3 000，因此HotStuff 與Fast-HotStuff的吞吐量TPS=3 000/Δt。本文算法則能提交2 個區(qū)塊上鏈，交易總量為2 個區(qū)塊內(nèi)的交易量，即6 000，因此，本文算法的吞吐量TPS=6 000/Δt。

圖3 所示為主節(jié)點(diǎn)在第一輪投票后出錯時3 種算法的吞吐量對比。

圖3 吞吐量對比結(jié)果1Fig.3 Throughput comparison result 1

由圖3 可知，主節(jié)點(diǎn)在第一輪投票后出錯時，本文算法在節(jié)點(diǎn)數(shù)量為19 時吞吐量依舊穩(wěn)定地保持在6 500TPS 以上，節(jié)點(diǎn)數(shù)量增長至61 時保持在2 500TPS以上。而HotStuff 與Fast-HotStuff 則在節(jié)點(diǎn)數(shù)量為19時吞吐量均為3 500TPS 以下，節(jié)點(diǎn)數(shù)量增長至61 時則為1 500TPS 以下。

當(dāng)連續(xù)f個視圖中的主節(jié)點(diǎn)在第一輪投票后出錯時，HotStuff 和Fast-HotStuff 僅提交一個區(qū)塊上鏈，交易總量為一個區(qū)塊內(nèi)的交易量，即3 000，因此，HotStuff 與Fast-HotStuff 的吞吐量TPS=3 000/Δt。本文算法能夠提交f+1 個區(qū)塊上鏈，交易總量為f+1 個區(qū)塊內(nèi)的交易量，因此，本文算法的吞吐量TPS=(f+1)×3 000/Δt。

圖4 所示為連續(xù)f個視圖中的主節(jié)點(diǎn)在第一輪投票后出錯時3 種算法的吞吐量對比。

圖4 吞吐量對比結(jié)果2Fig.4 Throughput comparison result 2

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

5 結(jié)束語

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