H-Algorand：基于多塊輸出的公有鏈共識機制

王 波，任英琦，黃冬艷

（1.桂林電子科技大學認知無線電與信息處理省部共建教育部重點實驗室，廣西桂林 541004；2.桂林電子科技大學廣西無線寬帶通信與信號處理重點實驗室，廣西桂林 541004）

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

0 引言

區(qū)塊鏈的概念源于2008 年Satoshi Nakamoto 發(fā)表的論文《Bitcoin：A peer-to-peer electronic cash system》［1］。近年來區(qū)塊鏈技術因其分布式、匿名性、難以篡改等特性受到學術界和企業(yè)界的高度關注。

區(qū)塊鏈網(wǎng)絡的種類從利益方的角度進行分類，可以分為公有鏈、聯(lián)盟鏈和私有鏈［2-3］。公有鏈是應用范圍最為廣泛的一類區(qū)塊鏈，有望支撐新型商業(yè)形態(tài)［4］。公有鏈可以分為需要認證的公有鏈網(wǎng)絡和無需認證的公有鏈網(wǎng)絡［5-6］。無需認證的公有鏈應用有Bitcoin［1］等，需要認證的公有鏈應用有EOS（Enterprise Operation System）［7］等。

區(qū)塊鏈技術由分布式存儲、密碼學、共識機制、智能合約等技術構成，其中，共識機制的作用旨在可容錯的網(wǎng)絡環(huán)境下實現(xiàn)狀態(tài)機復制排序的一致性［6］。公有鏈的共識機制包括工作量證明（Proof Of Work，POW）［1］、權益證明（Proof Of Stake，POS）［8］、委托權益證明（Delegated Proof Of Stake，DPOS）［9］、Algorand 機制［10］等。但公有鏈中如何提高區(qū)塊的共識效率，一直是一個挑戰(zhàn)［4］。

Algorand 機制由Micali［10］提出，該算法之后由Gilad 等實現(xiàn)［11］。其中使用到的可驗證的隨機函數(shù)（Verifiable Random Functions，VRFs）［12］抽簽算法，使每個節(jié)點都有機會參與到共識中，提高了共識的可拓展性。其中使用到的拜占庭協(xié)議（Byzantine Agreement，BA★）令節(jié)點只在當前區(qū)塊和空白塊之間做二元共識［11］，使得鏈條分叉概率僅為10-18［10］，即使在惡意節(jié)點能力很強的區(qū)塊鏈網(wǎng)絡環(huán)境下依舊能保持良好的性能。2 MB的區(qū)塊使用Algorand機制在50 000用戶的區(qū)塊鏈網(wǎng)絡中從提出到完成共識只需22 s［11］。

日后隨著區(qū)塊鏈網(wǎng)絡的大規(guī)模推廣，網(wǎng)絡數(shù)據(jù)交互頻率和數(shù)據(jù)量都會增大［13］，如果將Algorand 機制用于銀行等大規(guī)模交易系統(tǒng)，交易延遲將會累積爆發(fā)，造成銀行系統(tǒng)癱瘓。因此，Algorand機制的共識效率仍有待提高。

針對Algorand 機制共識效率不高的問題，本文首先提出多塊Algorand 共識機制（Multi-Block-Algorand，MB-Algorand），以有效提升出塊效率；其次針對分布式拒絕服務（Distributed Denial of Service，DDoS）攻擊，結合Algorand 與MB-Algorand 兩者的優(yōu)勢提出H-Algorand（Hybid-Algorand）機制。該機制以犧牲一定的安全性能為代價，以換取區(qū)塊鏈網(wǎng)絡共識效率的顯著提升。

1 工作機制

1.1 公有鏈網(wǎng)絡工作機制

公有鏈網(wǎng)絡從有無委員會的角度來說可以分為有委員會的區(qū)塊鏈網(wǎng)絡和無委員會的區(qū)塊鏈網(wǎng)絡。本文關注有委員會的區(qū)塊鏈網(wǎng)絡，包括以下5個步驟。

步驟一 消息廣播。區(qū)塊鏈網(wǎng)絡中的每個節(jié)點通過gossip 等通信協(xié)議向網(wǎng)絡中的節(jié)點廣播消息。每個消息都會簽署始發(fā)節(jié)點的私鑰以防止消息被偽造。其他節(jié)點在轉發(fā)這些消息前會檢查簽名。對于相同的消息，每個節(jié)點只會轉發(fā)一次。

步驟二 委員會選舉。區(qū)塊鏈網(wǎng)絡可以通過投票機制［9，14］、滑窗機制［15］、抽簽機制［10］等選舉出委員會。委員會代表整個區(qū)塊鏈網(wǎng)絡對網(wǎng)絡新生成的區(qū)塊進行共識。

步驟三 領導者選舉及出塊。委員會可以通過隨機數(shù)機制［9］、優(yōu)先級機制［10］等選舉出領導者節(jié)點。領導者節(jié)點負責將它收集到的消息，打包到待共識的區(qū)塊里，在委員會里轉發(fā)。設打包及轉發(fā)的時間為tp。

步驟四 委員會共識。委員會利用實用拜占庭容錯（Practical Byzantine Fault Tolerance，PBFT）、BA★［11］等共識機制，對領導者提出的區(qū)塊進行共識。設共識時間為tc。

步驟五 新區(qū)塊寫入。共識成功的區(qū)塊在區(qū)塊鏈網(wǎng)絡中轉發(fā)，被各個節(jié)點添加到各自維護的賬本中。

1.2 Algorand機制出塊-共識原理

在步驟二“委員會選舉”階段，Algorand 機制根據(jù)權重，在所有用戶之間隨機選擇完成一屆（兩批）委員會選舉，保證委員會的成員足夠誠實，從而避免Sybil攻擊。

在步驟三“領導者選舉”中，委員會中優(yōu)先級較高的節(jié)點（1～70 個）向委員會發(fā)送自己的優(yōu)先級、自己打包的塊及證明。優(yōu)先級消息約200 B，可以在網(wǎng)絡中快速傳播。優(yōu)先級最高的節(jié)點會獲得委員會的認可，成為領導者。而其他節(jié)點發(fā)送的區(qū)塊則會被過濾。領導者的選舉在時間上與領導者出塊和委員會共識是并行執(zhí)行的。

Algorand機制的出塊-共識所對應的時序如圖1所示。

Algorand 機制一屆委員會只出一個區(qū)塊。當領導者出塊后，委員會將對該區(qū)塊進行委員會共識。委員會的各節(jié)點通過BA★算法對領導者提出的區(qū)塊進行二元共識。

綜上所述，Algorand 機制中，一個區(qū)塊出塊-共識所需要的時間為：

圖1 Algorand機制“出塊-共識”時序圖Fig.1 “Propose-consensus”sequence diagram of Algorand mechanism

2 MB-Algorand機制的工作機制

如圖1所示，Algorand機制使得每一屆委員會只能對本屆領導者提出的區(qū)塊進行共識，并且第i+1 塊待共識區(qū)塊的出塊需等到第i塊區(qū)塊委員會共識結束后方可進行，這就導致Algorand機制的出塊效率較低。

為了提高區(qū)塊鏈網(wǎng)絡出塊效率，本文提出MB-Algorand機制。本機制借鑒EOS共識機制，在執(zhí)行步驟三和步驟四時，使得領導者出塊和委員會共識并行處理，從而有效提高區(qū)塊鏈網(wǎng)絡整體出塊效率，其共識時序如圖2所示。

圖2 MB-Algorand機制“出塊-共識”時序圖Fig.2 “Propose-consensus”sequence diagram of MB-Algorand mechanism

在MB-Algorand 機制第i屆委員會期間，當領導者提議第一個區(qū)塊i1之后，委員會開始對區(qū)塊i1進行共識。由于區(qū)塊i2為同一個領導者提出，該領導者必然確定自己出的每一個塊都是可信的。因此，領導者不需要等待委員會的共識時間，便開始提議第二個區(qū)塊i2，直到領導者提議至目標出塊數(shù)第N個區(qū)塊iN為止。MB-Algorand 機制實現(xiàn)了共識與出塊的并行處理，從而可以有效提高共識效率。

因為區(qū)塊大小不同，會使得塊提議時間tp不同，而塊共識時間tc大小幾乎不變。以tp和tc大小關系作為條件，又可以分為以下兩種情況：

CaseⅠ：當tp＜tc時，即提議區(qū)塊較小于4 MB［11］，N個區(qū)塊“領導者出塊”和“委員會共識”所需要的時間為：

CaseⅡ：當tp≥tc時，即提議區(qū)塊大于4 MB［11］，N個區(qū)塊“領導者出塊”和“委員會共識”所需要的時間為：

3 H-Algorand機制的工作機制

MB-Algorand 機制連續(xù)共識多個塊雖然可以有效提高共識效率，但是也會帶來安全性的下降。為了使共識機制能夠適應網(wǎng)絡狀態(tài)的變化而使得區(qū)塊鏈網(wǎng)絡保持安全高效，本文基于Algorand 機制和MB-Algorand 機制提出一種混合Algorand（Hybid-Algorand，H-Algorand）共識機制。

其運行機制如圖3 所示，第i屆委員會執(zhí)行一個塊數(shù)為N的出塊周期，設n為當前區(qū)塊編號，[i，n]為第i屆委員會共識的編號為n的區(qū)塊。首先判斷網(wǎng)絡狀態(tài)是否符合運行MBAlgorand 機制的安全標準：若不符合，則使用Algorand 機制完成共識，即N個待共識區(qū)塊將由第i屆至第i+j，j∈[0，N)屆領導者與委員會逐個提議并共識；若符合，則啟動MBAlgorand 機制，即N個區(qū)塊都由i屆領導者與i屆委員會進行共識。在運行MB-Algorand 機制時，如果第i屆領導者提議的某個區(qū)塊在第i屆委員會中共識失敗（失敗的原因在下一章進行討論），則失敗的這一輪共識一個空白區(qū)塊，提交上鏈。以空白塊為起點，N個區(qū)塊中剩余N-n個待共識區(qū)塊，轉為Algorand 機 制，即 由i+j，j∈[1，N-n] 屆領導者與i+j，j∈[1，N-n]屆委員會進行共識。

圖3 H-Algorand網(wǎng)絡運行機制Fig.3 Operation mechanism of H-Algorand network

4 H-Algorand機制的性能分析

H-Algorand 機制中包含MB-Algorand 機制，MB-Algorand機制中領導者可以連續(xù)出塊使得領導者出塊和委員會共識并行處理，提高了出塊效率。但是，由于領導者連續(xù)出塊，導致其與委員會暴露在網(wǎng)絡當中。暴露的時間越長，被惡意的攻擊者發(fā)現(xiàn)、執(zhí)行攻擊以及攻擊成功的概率加大。下面將分析H-Algorand機制在出塊效率和安全性之間的折中性能。

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

4.1.1 概述

區(qū)塊鏈網(wǎng)絡主要采用兩種網(wǎng)絡模型，強同步網(wǎng)絡模型和弱同步網(wǎng)絡模型［16］。本文主要討論強同步網(wǎng)絡模型下HAlgorand 機制的性能。強同步網(wǎng)絡模型下區(qū)塊鏈遭受的安全威脅主要來自七類惡意攻擊［17］，這些攻擊從各個層面對區(qū)塊共識造成影響。

H-Algorand 機制屬于有委員會的區(qū)塊鏈網(wǎng)絡。在有委員會的區(qū)塊鏈網(wǎng)絡中，委員會成員之間的交互容易泄露委員會的身份，從而遭到攻擊者的分布式拒絕服務（Distributed Denial of Service，DDoS）攻擊［17］，本文主要分析DDoS 對于HAlgorand機制的影響。

本文假設區(qū)塊鏈網(wǎng)絡對于惡意攻擊有相應的檢測機制與防御機制，使其可以對網(wǎng)絡狀況進行安全性評估。區(qū)塊鏈網(wǎng)絡中各節(jié)點擁有數(shù)據(jù)檢驗的能力，不可能進行基于數(shù)據(jù)偽造的作惡。區(qū)塊鏈網(wǎng)絡中節(jié)點之間的賄賂行為會受到懲罰［18］。

4.1.2 出塊效率

本文假設Algorand 機制共識以概率1 成功。H-Algorand機制中領導者目標出塊數(shù)為N，優(yōu)先以MB-Algorand 機制運行。MB-Algorand 機制產(chǎn)生的第一個區(qū)塊的共識過程可以認為和Algorand 機制相同，以概率1 成功，其余剩下的N-1 個區(qū)塊由于領導者和委員會暴露在區(qū)塊鏈網(wǎng)絡中，都存在共識失敗的概率。設在遭受DDoS攻擊威脅的網(wǎng)絡環(huán)境下，每一個區(qū)塊共識失敗的概率為Pfault，為了便于分析，Pfault為一定值。則每個塊共識成功的概率為Psuccess=1-Pfault，N個塊全部共識成功的概率為。

Algorand機制對N個區(qū)塊共識所需時間為：

理想條件下，即網(wǎng)絡中不存在惡意攻擊時，MB-Algorand機制共識N個區(qū)塊出塊提升效率為：

當N→∞時

由式（6）可得，當tc/tp越小時，出塊效率越大；當tp=tc時，出塊效率的上限為50%。在實際的區(qū)塊鏈網(wǎng)絡中，當塊大小為4 MB左右時，tp≈tc，此時可以達到最大出塊效率［11］。

在實際的區(qū)塊鏈網(wǎng)絡中，MB-Algorand機制每個待共識區(qū)塊共識失敗概率為Pfault。設從第二個塊開始，H-Algorand 機制使用MB-Algorand 機制的多塊方式連續(xù)提出并成功共識的區(qū)塊數(shù)為n，則使用Algorand機制的單塊方式提出并共識的區(qū)塊數(shù)為N-1-n。

首先將H-Algorand 機制簡單的看成n重伯努利實驗，則H-Algorand 機制使用MB-Algorand 機制連續(xù)共識成功n個區(qū)塊花費的時間為：

由于區(qū)塊鏈網(wǎng)絡的鏈式結構，新區(qū)塊必須建立在前一區(qū)塊的基礎之上。因此實際H-Algorand 機制使用MB-Algorand機制連續(xù)共識成功n個區(qū)塊花費的時間由式（7）修正為式（8）：

其中：第一項表示n=N-1時，H-Algorand 機制所花費的時間；第二項表示n∈[0，N-2]時，H-Algorand 機制所花費的時間。

4.1.3 安全性

當H-Algorand 機制使用MB-Algorand 機制領導者提議的目標出塊數(shù)為N時，N個塊全部共識成功的概率為，則H-Algorand機制安全性損失為。

4.1.4 收益函數(shù)

對H-Algorand 機制的出塊效率和安全性進行折中考慮，建立收益函數(shù)：

其中β為權重因子。

最優(yōu)化問題表示為：

約束條件（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 收益函數(shù)

其最優(yōu)化模型與式（9）相同，為：

5 實驗與分析

本章對H-Algorand 機制在Case I 和Case II 兩種情況下的性能進行仿真分析。

5.1 實驗參數(shù)

H-Algorand機制的仿真參數(shù)及取值如表1所示。

表1 參數(shù)表Tab.1 Parameter table

如表1 所示，領導者出塊時間tp在CaseⅠ與CaseⅡ下分別為10 s，26 s［11］，委員會共識時間tc在CaseⅠ與CaseⅡ下分別為12 s，12 s［11］；令H-Algorand 機制在目標出塊數(shù)N下區(qū)塊共識成功的目標概率M=70%，此時H-Algorand 機制下，領導者的目標出塊數(shù)N的大小被限定在2到8之間；為了考察不同網(wǎng)絡環(huán)境下H-Algorand 機制的性能，H-Algorand 機制第［2，N］個區(qū)塊受到惡意攻擊后共識失敗概率設定為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 機制進行共識時的領導者目標出塊數(shù)N與收益函數(shù)的關系。從圖4 首先可以看出，一定的Pfault時，存在一個最優(yōu)的N*，使得收益函數(shù)取得最大值；其次，一定的N時，Pfault值越低，收益函數(shù)越大。

圖4 CaseⅠ：所提算法收益函數(shù)示意圖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 機制進行共識時的最優(yōu)出塊數(shù)N*，相對于傳統(tǒng)的Algorand 機制，100%使用MB-Algorand 機制進行共識的出塊提升效率以及相應的安全性損失，和50%使用MB-Algorand 機制進行共識的出塊提升效率。可以看出，隨著Pfault的增加，最優(yōu)出塊數(shù)下降，出塊提升效率降低，而安全性損失將會增加。

表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 機制進行共識最優(yōu)出塊數(shù)N*的一半50%N*（向上取整）時，相對于傳統(tǒng)的Algorand機制，其出塊提升效率也是可觀的。

5.3 H-Algorand機制在CaseⅡ下的仿真與分析

圖5 所示為CaseⅡ下，β=0.5，Pfault分別為1%、2%、3%、4%時，H-Algorand 機制下使用MB-Algorand 機制進行共識時的領導者的目標出塊數(shù)N與收益函數(shù)的關系。CaseⅡ可以得出與Case I相同的結論。

表3 所示為Case II 下，β=0.5，Pfault分別為1%、2%、3%、4%時，H-Algorand 機制下使用MB-Algorand 機制進行共識時的最優(yōu)出塊數(shù)N*，相對于傳統(tǒng)的Algorand 機制，100%使用MB-Algorand機制的出塊提升效率以及相應的安全性損失，和50%使用MB-Algorand機制的出塊提升效率。

從表中可以看出，當Pfault較小時（如1%），H-Algorand 機制100%使用MB-Algorand 機制進行共識時，能夠以安全性損失4.9%的代價換來出塊效率26.32%的提升，其效率提升程度比CaseⅠ略差一些。

當H-Algorand 機制下使用MB-Algorand 機制進行共識最優(yōu)出塊數(shù)N*的一半50%N*（向上取整）時，相對于傳統(tǒng)的Algorand機制，其出塊效率也得到了提升。

圖5 CaseⅡ：所提算法收益函數(shù)示意圖Fig.5 CaseⅡ：schematic diagram of revenue function of the proposed algorithm

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

綜合CaseⅠ和CaseⅡ來看，產(chǎn)生一個區(qū)塊的時間越多時，即區(qū)塊越大時，H-Algorand 機制使用MB-Algorand 機制相對于使用傳統(tǒng)Algorand 機制獲得的收益會減少，因此H-Algorand機制適用于區(qū)塊小于4 MB且網(wǎng)絡環(huán)境較為安全的場景。

6 結語

本文針對受到業(yè)界普遍重視的公有鏈網(wǎng)絡，首先提出了一種多塊輸出的共識機制——MB-Algorand，該機制的領導者可以連續(xù)出塊，從而有效地提升了出塊效率；其次在公有鏈委員會受到DDoS 攻擊的場景下，提出融合了Algorand 和MBAlgorand 兩者優(yōu)點的H-Algorand 機制。該機制折中考慮了出塊效率與安全性兩方面。將H-Algorand 機制與Algorand 機制進行仿真對比發(fā)現(xiàn)，H-Algorand 機制能在惡意攻擊成功率為1%～4%的條件下，以犧牲少量安全性為代價換取共識效率的有效提升。本文僅對H-Algorand 機制在強同步網(wǎng)絡模型下進行了分析研究，未來將對弱同步網(wǎng)絡模型下的共識機制進行分析研究。