基于二項(xiàng)交換林和HotStuff的改進(jìn)共識(shí)算法

湯春明，陳雨晴，張梓迪

基于二項(xiàng)交換林和HotStuff的改進(jìn)共識(shí)算法

湯春明1*，陳雨晴2，張梓迪3

（1.天津工業(yè)大學(xué) 人工智能學(xué)院，天津 300387； 2.天津工業(yè)大學(xué) 控制科學(xué)與工程學(xué)院，天津 300387； 3.天津大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300350）（ ? 通信作者電子郵箱tangchunminga@hotmail.com）

針對(duì)區(qū)塊鏈中拜占庭容錯(cuò)類的共識(shí)機(jī)制存在通信復(fù)雜度高、視圖切換復(fù)雜以及擴(kuò)展性差的問(wèn)題，提出了一種基于二項(xiàng)交換林和HotStuff的改進(jìn)共識(shí)算法，即增強(qiáng)HotStuff（HSP）共識(shí)算法。為實(shí)現(xiàn)簽名批量驗(yàn)證和簽名聚合，采用了BLS簽名算法；為降低系統(tǒng)的通信復(fù)雜度，采用了門限簽名技術(shù)；為降低視圖切換時(shí)的通信復(fù)雜度，共識(shí)過(guò)程采用了三階段確認(rèn)方式；為減少主副節(jié)點(diǎn)間的通信次數(shù)并降低主節(jié)點(diǎn)聚合簽名的壓力，采用了改進(jìn)的二項(xiàng)交換林技術(shù)。測(cè)試結(jié)果表明，HSP共識(shí)算法在系統(tǒng)節(jié)點(diǎn)總數(shù)為64且請(qǐng)求和響應(yīng)均為256字節(jié)的情況下，吞吐量較HotStuff共識(shí)機(jī)制提升了33.8%，共識(shí)延遲縮短了16.4%。HSP共識(shí)算法在節(jié)點(diǎn)多的情況下，具有較好的性能。

區(qū)塊鏈；共識(shí)機(jī)制；門限簽名；二項(xiàng)交換林；視圖切換

0 引言

區(qū)塊鏈的四大核心技術(shù)分別是密碼學(xué)、分布式賬本、共識(shí)機(jī)制以及智能合約，其中密碼學(xué)是區(qū)塊鏈的基石。區(qū)塊鏈中涉及的密碼學(xué)算法主要有兩種，一種是哈希算法，一種是數(shù)字簽名算法。哈希算法可以理解為一種特殊的函數(shù)，即不論輸入多長(zhǎng)的字符，輸出均為一個(gè)固定長(zhǎng)度的字符，區(qū)塊鏈中使用哈希算法來(lái)對(duì)信息做數(shù)字摘要，數(shù)字摘要可用來(lái)驗(yàn)證信息的完整性。數(shù)字簽名是指僅信息的發(fā)送者才能產(chǎn)生的他人無(wú)法偽造的一段數(shù)字串，區(qū)塊鏈中使用數(shù)字簽名技術(shù)來(lái)保證交易的不可篡改性和可驗(yàn)證性。一個(gè)區(qū)塊中包含上千筆交易，每筆交易都對(duì)應(yīng)一個(gè)數(shù)字簽名，驗(yàn)證區(qū)塊相當(dāng)于驗(yàn)證區(qū)塊中的數(shù)字簽名。為提升區(qū)塊驗(yàn)證速度，聚合簽名技術(shù)和門限簽名技術(shù)被應(yīng)用到區(qū)塊鏈中。聚合簽名技術(shù)將多個(gè)簽名聚合為一個(gè)簽名，最終驗(yàn)證的時(shí)候僅需驗(yàn)證聚合之后的簽名，聚合簽名技術(shù)用來(lái)批量驗(yàn)證區(qū)塊中交易的簽名信息。聚合簽名有多種實(shí)現(xiàn)形式，橢圓曲線數(shù)字簽名算法（Elliptic Curve Digital Signature Algorithm，ECDSA）由Johnson等［1］提出，實(shí)現(xiàn)聚合簽名效率較低且較為復(fù)雜；Schnorr簽名算法由Schnorr［2］提出，實(shí)現(xiàn)聚合簽名較為容易但必須依賴隨機(jī)數(shù)生成器且需要多輪通信，如果在通信過(guò)程中某個(gè)節(jié)點(diǎn)出現(xiàn)故障，則聚合失敗；BLS（Boneh-Lynn-Shacham， BLS）簽名算法由Boneh等［3］初次提出，并在2018年對(duì)此方案進(jìn)行了更新，BLS簽名算法解決了Schnorr簽名存在的問(wèn)題，聚合簽名時(shí)不再需要節(jié)點(diǎn)間的多輪通信，不依賴于隨機(jī)數(shù)。門限簽名技術(shù)是指根據(jù)系統(tǒng)需求將秘密分成若干份密鑰碎片，將密鑰碎片分發(fā)給系統(tǒng)內(nèi)節(jié)點(diǎn)，只有聚集起滿足閾值數(shù)量的密鑰碎片才可以恢復(fù)出最初的秘密，門限簽名技術(shù)用來(lái)降低節(jié)點(diǎn)間的通信復(fù)雜度。門限簽名技術(shù)涉及兩個(gè)方面內(nèi)容，一是門限密鑰生成，一是簽名生成。在密鑰生成階段，沙米爾秘密分享是由Shamir［4］提出，是最簡(jiǎn)單的依賴中心節(jié)點(diǎn)的門限密鑰生成方式，基本原理是拉格朗日插值法。為解決中心作惡?jiǎn)栴}，基于承諾的可驗(yàn)證秘密分享［5］應(yīng)運(yùn)而生。在簽名生成階段，選取不同的數(shù)字簽名算法，實(shí)現(xiàn)門限簽名的難度是不一樣的。如果用ECDSA實(shí)現(xiàn)門限簽名則難度較大；用Schnorr簽名算法實(shí)現(xiàn)門限簽名［6］時(shí)，需要形成一個(gè)公共密鑰的默克爾樹(shù)，如果節(jié)點(diǎn)數(shù)量較多，默克爾樹(shù)會(huì)變得十分龐大，效率較低；用BLS簽名算法實(shí)現(xiàn)門限簽名較為容易，但也存在不足，即配對(duì)效率低，它的簽名驗(yàn)證時(shí)間比Schnorr簽名算法長(zhǎng)。在實(shí)際應(yīng)用中，根據(jù)系統(tǒng)需求，選擇適宜的數(shù)字簽名算法可以提高系統(tǒng)性能。

共識(shí)機(jī)制作為區(qū)塊鏈的四大核心技術(shù)之一，被用來(lái)保證系統(tǒng)的正確運(yùn)行，使系統(tǒng)的狀態(tài)保持一致。區(qū)塊鏈按照應(yīng)用場(chǎng)景可分為公有鏈、私有鏈和聯(lián)盟鏈。不同的區(qū)塊鏈類型對(duì)應(yīng)不同的共識(shí)機(jī)制［7-9］。公有鏈即所有的用戶均可以加入到區(qū)塊鏈網(wǎng)絡(luò)中，典型的共識(shí)機(jī)制有工作量證明（Proof of Work， PoW）和權(quán)益證明（Proof of Stake， PoS），有向無(wú)環(huán)圖結(jié)構(gòu)也被應(yīng)用到共識(shí)機(jī)制的設(shè)計(jì)中，如GHOST（Greedy Heaviest Observed Sub-Tree）［10］、Bitcoin-ng［11］和Conflux［12］等；私有鏈主要是企業(yè)內(nèi)部使用，要求系統(tǒng)內(nèi)節(jié)點(diǎn)全部可信，典型的共識(shí)機(jī)制有Paxos和Raft；聯(lián)盟鏈為節(jié)點(diǎn)設(shè)置準(zhǔn)入機(jī)制，通過(guò)身份驗(yàn)證的節(jié)點(diǎn)才可加入到區(qū)塊鏈網(wǎng)絡(luò)中，較為典型的共識(shí)機(jī)制為實(shí)用拜占庭容錯(cuò)（Practical Byzantine Fault Tolerance， PBFT）算法［13］。產(chǎn)品溯源、資產(chǎn)證券化等應(yīng)用均可通過(guò)聯(lián)盟鏈實(shí)現(xiàn)，聯(lián)盟鏈具有廣闊的應(yīng)用前景。

綜上所述，本文選取HotStuff算法進(jìn)行改進(jìn)。將改進(jìn)后的算法命名為HSP（HotStuff Plus）共識(shí)算法。使用BLS門限簽名技術(shù)，實(shí)現(xiàn)簽名的批量驗(yàn)證和簽名聚合；使用改進(jìn)的二項(xiàng)交換林技術(shù)，增強(qiáng)系統(tǒng)的可擴(kuò)展性并且降低主節(jié)點(diǎn)聚合簽名時(shí)的壓力；在共識(shí)時(shí)采用三階段確認(rèn)，降低視圖切換時(shí)的通信復(fù)雜度。

1 HotStuff算法

1.1　共識(shí)流程

HotStuff算法與其他的拜占庭容錯(cuò)類算法最大的區(qū)別就是將兩階段確認(rèn)變?yōu)槿A段確認(rèn)，降低了視圖切換時(shí)的通信復(fù)雜度。HotStuff算法每完成一次共識(shí)，更換一個(gè)主節(jié)點(diǎn)。其達(dá)成共識(shí)需要Prepare、Pre-Commit、Commit和Decide四個(gè)階段，共識(shí)流程如圖1所示。假設(shè)系統(tǒng)中節(jié)點(diǎn)總數(shù)為3+1，拜占庭節(jié)點(diǎn)數(shù)為。在Prepare階段，每個(gè)視圖開(kāi)始時(shí)，新的主節(jié)點(diǎn)收集由2+1個(gè)副本節(jié)點(diǎn)發(fā)送的new-view消息，new-view消息中包含了此節(jié)點(diǎn)上高度最高的prepareQC，prepareQC是共識(shí)過(guò)程中第一階段確認(rèn)達(dá)成的證據(jù)。主節(jié)點(diǎn)從收到的new-view消息中，選取高度最高的preparedQC作為highQC，主節(jié)點(diǎn)廣播prepare消息，prepare消息中包含了新的區(qū)塊和highQC，highQC作為prepare消息的安全性驗(yàn)證。副本節(jié)點(diǎn)收到當(dāng)前視圖編號(hào)對(duì)應(yīng)的主節(jié)點(diǎn)的prepare消息，副本節(jié)點(diǎn)對(duì)prepare消息進(jìn)行驗(yàn)證，驗(yàn)證通過(guò)后，對(duì)prepare消息簽名，將簽名發(fā)送給主節(jié)點(diǎn)。Pre-Commit階段，主節(jié)點(diǎn)收集簽名，收集到至少2+1個(gè)關(guān)于該prepare消息的簽名后進(jìn)行簽名聚合操作，聚合后的簽名作為prepareQC保存在本地，然后將其放入pre-commit消息中廣播給副本節(jié)點(diǎn)；副本節(jié)點(diǎn)收到pre-commit消息，進(jìn)行驗(yàn)證，驗(yàn)證通過(guò)后，對(duì)pre-commit消息簽名，將簽名發(fā)送給主節(jié)點(diǎn)。Commit階段，主節(jié)點(diǎn)收集至少2+1個(gè)關(guān)于pre-commit消息的簽名后進(jìn)行簽名聚合操作，聚合簽名作為precommitQC，并將其放在commit消息中廣播；副本節(jié)點(diǎn)收到commit消息，進(jìn)行驗(yàn)證，驗(yàn)證通過(guò)后，對(duì)commit消息簽名，然后回復(fù)給主節(jié)點(diǎn)，此時(shí)副本節(jié)點(diǎn)鎖定precommitQC，將本地的lockQC更新成收到的precommitQC。Decide階段，當(dāng)主節(jié)點(diǎn)收到至少2+1個(gè)關(guān)于commit消息的簽名，聚合成commitQC，廣播decide消息；副本節(jié)點(diǎn)收到decide消息中的commitQC后，執(zhí)行區(qū)塊中的交易，同時(shí)視圖編號(hào)加1，開(kāi)始新的視圖。

圖 1　HotStuff共識(shí)流程

1.2　HotStuff視圖切換流程及其缺點(diǎn)

HotStuff存在以下缺點(diǎn)：HotStuff使用secp256k1簽名算法來(lái)實(shí)現(xiàn)數(shù)字簽名，secp256k1算法是ECDSA的一種，因此其在實(shí)現(xiàn)聚合簽名和門限簽名方面，效率較低；HotStuff中主節(jié)點(diǎn)需要完成接受請(qǐng)求、發(fā)送消息、收集簽名、聚合簽名和驗(yàn)證簽名5項(xiàng)任務(wù)，而其他副本節(jié)點(diǎn)僅需要驗(yàn)證消息和對(duì)消息進(jìn)行簽名，工作量分配不均衡。

2 改進(jìn)HotStuff共識(shí)算法

2.1　改進(jìn)二項(xiàng)交換林

傳統(tǒng)的二項(xiàng)交換林［19］，每個(gè)節(jié)點(diǎn)均會(huì)創(chuàng)建一棵完整的二項(xiàng)交換林，此種方式會(huì)產(chǎn)生不必要的開(kāi)銷。針對(duì)該問(wèn)題進(jìn)行如下改進(jìn)：將系統(tǒng)內(nèi)節(jié)點(diǎn)分組，主根節(jié)點(diǎn)在每個(gè)小組內(nèi)部選擇一個(gè)節(jié)點(diǎn)與其進(jìn)行數(shù)據(jù)交換，被選擇的節(jié)點(diǎn)作為小組的分根節(jié)點(diǎn)，重復(fù)相同的分組操作和數(shù)據(jù)交換操作。如圖2所示，根節(jié)點(diǎn)011每次只與每個(gè)小組內(nèi)的一個(gè)節(jié)點(diǎn)進(jìn)行信息交換，同根節(jié)點(diǎn)進(jìn)行信息交換的節(jié)點(diǎn)id由根節(jié)點(diǎn)隨機(jī)選擇。具體根節(jié)點(diǎn)011首先同010節(jié)點(diǎn)進(jìn)行信息交換，再同001節(jié)點(diǎn)進(jìn)行信息交換，最后同101節(jié)點(diǎn)進(jìn)行信息交換。Group3中，101節(jié)點(diǎn)作為分根節(jié)點(diǎn)，首先進(jìn)行分組，分組后首先同100節(jié)點(diǎn)進(jìn)行信息交換，之后在110節(jié)點(diǎn)和111節(jié)點(diǎn)隨機(jī)選擇一個(gè)節(jié)點(diǎn)進(jìn)行第二次的信息交換。

算法實(shí)現(xiàn)部分：系統(tǒng)內(nèi)節(jié)點(diǎn)的ID默認(rèn)均為十進(jìn)制表示，需要將節(jié)點(diǎn)id全部轉(zhuǎn)換為二進(jìn)制表示，下面所述節(jié)點(diǎn)id均為二進(jìn)制數(shù)。

第一步 將系統(tǒng)總節(jié)點(diǎn)數(shù)轉(zhuǎn)換為二進(jìn)制表示，記為，的長(zhǎng)度為bit，則可將全部節(jié)點(diǎn)分為組。

第三步 根節(jié)點(diǎn)從每個(gè)小組中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為此小組的根節(jié)點(diǎn)；小組內(nèi)的根節(jié)點(diǎn)再次進(jìn)行分組，分組流程類似第二步，一直迭代，直到形成二項(xiàng)交換林。

第四步 子節(jié)點(diǎn)同其父節(jié)點(diǎn)進(jìn)行信息交換，最終主節(jié)點(diǎn)獲得完整數(shù)據(jù)。

圖 2　改進(jìn)二項(xiàng)交換林

2.2　共識(shí)流程

HSP共識(shí)算法采用BLS簽名算法來(lái)實(shí)現(xiàn)門限簽名，降低通信復(fù)雜度；同時(shí)使用改進(jìn)的二項(xiàng)交換林技術(shù)，來(lái)減小主節(jié)點(diǎn)聚合簽名的壓力；采取三階段確認(rèn)方式，將視圖切換過(guò)程和正常共識(shí)過(guò)程合并，降低視圖切換的通信復(fù)雜度。

根據(jù)系統(tǒng)胺液總量和脫鹽前后HSS的濃度差進(jìn)行計(jì)算，累計(jì)脫除熱穩(wěn)定鹽43.45 t。脫鹽期間能耗主要有除鹽水、電、氫氧化鈉溶液和少量鹽酸(清洗膜堆)，產(chǎn)生含胺廢水217 t，具體數(shù)據(jù)見(jiàn)表1。由表1可知，每去除1 t HSS的平均能耗為5332.7 MJ，消耗30%(w)的NaOH溶液0.3 t，并產(chǎn)生含鹽、含胺廢水5.0 t。廢水中MDEA質(zhì)量濃度為0.03 g/m L，平均每去除1 t HSS的胺液損耗為0.15 t，其原因是在電場(chǎng)作用下，部分MDEA因發(fā)生質(zhì)子化而帶電荷，從而穿過(guò)陽(yáng)膜進(jìn)入濃鹽室，和廢水一起排出。

圖 3　HSP共識(shí)流程

2.3　安全性分析

區(qū)塊鏈系統(tǒng)的基本安全目標(biāo)是通過(guò)密碼學(xué)和網(wǎng)絡(luò)安全等技術(shù)手段，保證區(qū)塊鏈系統(tǒng)中的數(shù)據(jù)安全、共識(shí)安全、智能合約安全和內(nèi)容安全。本文采用一致性和活性兩個(gè)安全屬性來(lái)衡量和評(píng)估區(qū)塊鏈的共識(shí)安全［20］。

一致性可理解為當(dāng)網(wǎng)絡(luò)中存在沖突區(qū)塊時(shí)，誠(chéng)實(shí)節(jié)點(diǎn)均會(huì)對(duì)同一個(gè)區(qū)塊進(jìn)行確認(rèn)，也可理解為攻擊者無(wú)法通過(guò)有效手段使得區(qū)塊鏈分叉。系統(tǒng)在進(jìn)行視圖切換時(shí)容易出現(xiàn)鏈分叉的情況，HSP針對(duì)沖突區(qū)塊的處理類似HotStuff。假設(shè)系統(tǒng)內(nèi)節(jié)點(diǎn)數(shù)為3+1，拜占庭節(jié)點(diǎn)數(shù)為，針對(duì)區(qū)塊B若有小于2+1個(gè)節(jié)點(diǎn)處于prepared狀態(tài)，則換掉B，如果大于等于2+1個(gè)節(jié)點(diǎn)處于prepared狀態(tài)或更高狀態(tài)，則新區(qū)塊的高度高于區(qū)塊B。此種策略可保證一致性。

活性指誠(chéng)實(shí)節(jié)點(diǎn)提交的合法數(shù)據(jù)終將由全網(wǎng)節(jié)點(diǎn)達(dá)成共識(shí)并被記錄在區(qū)塊鏈上。由CAP（Consistency，Aavailability，Partition）定理可知，在可能存在故障節(jié)點(diǎn)的異步網(wǎng)絡(luò)中，一致性和活性是不可能同時(shí)達(dá)成的。因此，HSP共識(shí)算法的應(yīng)用場(chǎng)景設(shè)置為部分同步系統(tǒng)，部分同步系統(tǒng)即消息在網(wǎng)絡(luò)中傳輸時(shí)有延遲上限，但上限未知。若消息傳輸時(shí)間超過(guò)延遲上限，則節(jié)點(diǎn)可發(fā)起視圖切換請(qǐng)求，重新選擇主節(jié)點(diǎn)，重新進(jìn)行消息傳輸，保證了系統(tǒng)活性。

3 實(shí)驗(yàn)與結(jié)果分析

由于吞吐量和共識(shí)延遲是衡量共識(shí)算法的兩個(gè)基本標(biāo)準(zhǔn)，因此本文通過(guò)分析吞吐量和共識(shí)延遲來(lái)分析HSP共識(shí)算法的性能。

3.1　實(shí)驗(yàn)環(huán)境

使用Java語(yǔ)言完成算法編寫，使用Docker容器技術(shù)模擬搭建多節(jié)點(diǎn)區(qū)塊鏈環(huán)境，設(shè)定區(qū)塊鏈環(huán)境的網(wǎng)絡(luò)為部分同步網(wǎng)絡(luò)。區(qū)塊鏈環(huán)境搭建細(xì)節(jié)為：將節(jié)點(diǎn)程序進(jìn)行封裝后部署在Docker容器中，一個(gè)Docker容器可部署一個(gè)節(jié)點(diǎn)，也可部署多個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)間通過(guò)IP地址進(jìn)行信息通信。搭建測(cè)試環(huán)境的操作系統(tǒng)為64位Windows10專業(yè)版，CPU為Intel Core i5-6200U CPU @2.30 GHz （4 CPUs），～2.4 GHz，內(nèi)存為16 GB，Docker版本為19.03.12，Java的JDK版本為1.8。

3.2　實(shí)驗(yàn)設(shè)計(jì)

第一組實(shí)驗(yàn) 取拜占庭節(jié)點(diǎn)數(shù)為0，節(jié)點(diǎn)總數(shù)為4，測(cè)試HotStuff（ECDSA）算法（記HS-ini）和HotStuff（BLS）算法（記HS+BLS）在請(qǐng)求和響應(yīng)均為0字節(jié)、256字節(jié)和512字節(jié)三種情況下的吞吐量和共識(shí)延遲。實(shí)驗(yàn)?zāi)康模簻y(cè)試BLS數(shù)字簽名算法對(duì)HotStuff算法的影響。

第三組實(shí)驗(yàn) 取系統(tǒng)內(nèi)節(jié)點(diǎn)總數(shù)依次為4、7、10、16、64，人為制造網(wǎng)絡(luò)故障和節(jié)點(diǎn)故障，故障節(jié)點(diǎn)數(shù)不得超過(guò)節(jié)點(diǎn)總數(shù)的1/3，針對(duì)不同的request/reply做兩組實(shí)驗(yàn)，測(cè)試發(fā)生視圖切換時(shí)HotStuff（BLS）和HSP的吞吐量和共識(shí)延遲。實(shí)驗(yàn)?zāi)康模?）測(cè)試由于網(wǎng)絡(luò)故障引起的視圖切換對(duì)系統(tǒng)的性能的影響；2）測(cè)試主節(jié)點(diǎn)連續(xù)故障引起的連續(xù)視圖切換對(duì)系統(tǒng)的性能的影響；3）視圖切換時(shí)系統(tǒng)一致性和活性。

3.3　實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)一的測(cè)試結(jié)果如圖4、5所示。隨著request/reply的變大，吞吐量降低，共識(shí)延遲加長(zhǎng)。當(dāng)request/reply=256/256時(shí)，HotStuff（BLS）算法較HotStuff（ECDSA）算法吞吐量提升了19.5%，共識(shí)延遲降低了19.9%；當(dāng)request/reply=512/512時(shí)，HotStuff（BLS）算法較HotStuff（ECDSA）算法吞吐量提升了22.6%，共識(shí)延遲降低了17.3%。

圖 4　吞吐量對(duì)比（實(shí)驗(yàn)一）

圖 5　共識(shí)延遲對(duì)比（實(shí)驗(yàn)一）

實(shí)驗(yàn)二的測(cè)試結(jié)果如圖6、7所示。節(jié)點(diǎn)數(shù)較少時(shí)，HotStuff（BLS）的表現(xiàn)優(yōu)于HSP；隨著節(jié)點(diǎn)數(shù)量增多，HSP和HotStuff（BLS）的差距變小。在節(jié)點(diǎn)數(shù)為64且請(qǐng)求和響應(yīng)均為256字節(jié)時(shí)，HSP較HotStuff（BLS）吞吐量提升了33.8%，共識(shí)延遲下降了16.4%；當(dāng)請(qǐng)求和響應(yīng)均為512字節(jié)時(shí)，HSP較HotStuff（BLS）吞吐量提升了69.0%，共識(shí)延遲下降了11.2%。

圖 6　吞吐量對(duì)比（實(shí)驗(yàn)二）

圖 7　共識(shí)延遲對(duì)比（實(shí)驗(yàn)二）

實(shí)驗(yàn)三的測(cè)試結(jié)果如圖8、9所示。其中后標(biāo)為net的曲線代表視圖切換的原因?yàn)榫W(wǎng)絡(luò)故障；后標(biāo)為L(zhǎng)eader的曲線代表視圖切換的原因?yàn)橹鞴?jié)點(diǎn)故障。在節(jié)點(diǎn)總數(shù)為64且請(qǐng)求和響應(yīng)均為256字節(jié)時(shí)，在由于網(wǎng)絡(luò)故障而發(fā)生視圖切換的情況下，HSP算法較HotStuff算法吞吐量提升了35.1%，共識(shí)延遲下降了22.6%；在由于主節(jié)點(diǎn)連續(xù)故障而連續(xù)進(jìn)行視圖切換的情況下，HSP算法較HotStuff（BLS）吞吐量提升了34.4%，共識(shí)延遲降低了17.9%。

3.4　實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)一結(jié)果分析 BLS簽名算法比ECDSA實(shí)現(xiàn)交易批量驗(yàn)證和門限簽名更為簡(jiǎn)單，提高了交易驗(yàn)證速度，所以共識(shí)時(shí)間較短，吞吐量較高。

實(shí)驗(yàn)二結(jié)果分析 在節(jié)點(diǎn)數(shù)量較少的情況下，HSP算法需要對(duì)節(jié)點(diǎn)進(jìn)行分組操作，分組操作會(huì)消耗一定時(shí)間；在節(jié)點(diǎn)數(shù)量多的情況下，主節(jié)點(diǎn)并不是同所有的其他節(jié)點(diǎn)進(jìn)行信息交換，只是同每個(gè)小組內(nèi)的一個(gè)成員進(jìn)行信息交換的優(yōu)點(diǎn)便可更明顯體現(xiàn)；分節(jié)點(diǎn)會(huì)聚合其子節(jié)點(diǎn)的簽名，降低了主節(jié)點(diǎn)聚合全部簽名的壓力，縮短了共識(shí)時(shí)長(zhǎng)。

實(shí)驗(yàn)三結(jié)果分析 當(dāng)系統(tǒng)進(jìn)行視圖切換時(shí)，兩種算法的性能較無(wú)視圖切換時(shí)均降低，此為正常情況，因?yàn)橐晥D切換過(guò)程會(huì)消耗時(shí)間。節(jié)點(diǎn)數(shù)量和request/reply相同時(shí)，由網(wǎng)絡(luò)延遲而產(chǎn)生視圖切換時(shí)的系統(tǒng)性能較因主節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)而引發(fā)的視圖切換時(shí)的系統(tǒng)性能好，因?yàn)樾氯沃鞴?jié)點(diǎn)為拜占庭節(jié)點(diǎn)可引發(fā)視圖連環(huán)切換，視圖切換時(shí)，系統(tǒng)內(nèi)節(jié)點(diǎn)不處理交易，因此吞吐量降低、共識(shí)延遲加長(zhǎng)。同時(shí)，可知當(dāng)系統(tǒng)內(nèi)存在拜占庭節(jié)點(diǎn)且故障節(jié)點(diǎn)數(shù)量少于節(jié)點(diǎn)總數(shù)的1/3時(shí)，系統(tǒng)依舊可以完成共識(shí)流程并達(dá)成共識(shí)，因此說(shuō)明此系統(tǒng)在該測(cè)試環(huán)境下可以同時(shí)保證活性和一致性。

圖 8　視圖切換時(shí)的吞吐量（實(shí)驗(yàn)三）

圖 9　視圖切換時(shí)共識(shí)延遲（實(shí)驗(yàn)三）

4 結(jié)語(yǔ)

本文在 HotStuff 算法的基礎(chǔ)上提出了HSP共識(shí)算法，該算法引入了二項(xiàng)交換林的概念，使得系統(tǒng)在節(jié)點(diǎn)數(shù)量多的情況下，可以保證吞吐量；使用BLS門限簽名算法，降低了節(jié)點(diǎn)的通信復(fù)雜度；使用三階段確認(rèn)取代二階段確認(rèn)，將視圖切換時(shí)的通信復(fù)雜度降為多項(xiàng)式級(jí)別。實(shí)驗(yàn)結(jié)果表明，在系統(tǒng)節(jié)點(diǎn)數(shù)量較少的情況下，HSP算法的優(yōu)勢(shì)較HotStuff稍弱；隨著節(jié)點(diǎn)數(shù)量的增加，HSP共識(shí)算法的優(yōu)勢(shì)逐漸體現(xiàn)，吞吐量高于HotStuff算法且共識(shí)延遲也低于HotStuff算法。此外該算法仍然存在值得改進(jìn)的地方，如不能動(dòng)態(tài)地增加刪除節(jié)點(diǎn)，下一步工作是實(shí)現(xiàn)動(dòng)態(tài)增加刪除節(jié)點(diǎn)。

[1] JOHNSON D， MENEZES A， VANSTONE S. The Elliptic Curve Digital Signature Algorithm （ECDSA）［J］. International Journal of Information Security， 2001， 1（1）：36-63.

[2] SCHNORR C P. Efficient signature generation by smart cards ［J］. Journal of Cryptology， 1991， 4（3）：161-174.

[3] BONEH D， DRIJVERS M， NEVEN G. Compact multi-signatures for smaller blockchains ［C］// Proceedings of the 2018 International Conference on the Theory and Application of Cryptology and Information Security， LNCS 11273. Cham： Springer， 2018： 435-464.

[4] SHAMIR A. How to share a secret［J］. Communications of the ACM， 1979， 22（11）： 612-613.

[5] FELDMAN P. A practical scheme for non-interactive verifiable secret sharing ［C］// Proceedings of the 28th Annual Symposium on Foundations of Computer Science. Piscataway： IEEE， 1987： 427-438.

[6] SYTA E， TAMAS I， VISHER D， et al. Keeping authorities “honest or bust” with decentralized witness cosigning［C］// Proceedings of the 2016 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2016：526-545.

[7] BANO S， SONNINO A， AL-BASSAM M， et al. SoK： consensus in the age of blockchains ［C］// Proceedings of the 1st ACM Conference on Advances in Financial Technologies. New York： ACM， 2019： 183-198.

[8] WAN S H， LI M J， LIU G Y， et al. Recent advances in consensus protocols for blockchain： a survey［J］. Wireless Networks， 2020， 26（8）：5579-5593.

[9] 袁勇，倪曉春，曾帥，等. 區(qū)塊鏈共識(shí)算法的發(fā)展現(xiàn)狀與展望［J］. 自動(dòng)化學(xué)報(bào)， 2018， 44（11）：2011-2022.（YUAN Y， NI X C， ZENG S， et al. Blockchain consensus algorithms： the state of the art and future trends［J］. Acta Automatica Sinica， 2018， 44（11）：2011-2022.）

[10] SOMPOLINSKY Y， ZOHAR A. Secure high-rate transaction processing in Bitcoin［C］// Proceedings of the 2015 International Conference on Financial Cryptography and Data Security， LNCS 8975. Berlin： Springer， 2015： 507-527.

[11] EYAL I， GENCER A E， SIRER E G， et al. Bitcoin-NG： a scalable blockchain protocol［C］// Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation. Berkeley： USENIX Association， 2016： 45-59.

[12] LI C X， LI P L， ZHOU D， et al. A decentralized blockchain with high throughput and fast confirmation［C］// Proceedings of the 2020 USENIX Annual Technical Conference. Berkeley： USENIX Association， 2020： 515-528.

[13] CASTRO M， LISKOV B. Practical Byzantine fault tolerance and proactive recovery［J］. ACM Transactions on Computer Systems， 2002， 20（4）： 398-461.

[14] 孫一蓬.基于聯(lián)盟鏈的多鏈?zhǔn)絽^(qū)塊鏈共識(shí)性能研究［D］. 南昌：東華理工大學(xué)，2019.（SUN Y P. Research on consensus performance of multi-chain blockchain based on league chain［D］. Nanchang： East China University of Technology， 2019.）

[15] 王海勇，郭凱璇，潘啟青. 基于投票機(jī)制的拜占庭容錯(cuò)共識(shí)算法［J］.計(jì)算機(jī)應(yīng)用， 2019， 39（6）：1766-1771.（WANG H Y， GUO K X， PAN Q Q. Byzantine fault tolerance consensus algorithm based on voting mechanism［J］. Journal of Computer Applications， 2019， 39（6）： 1766-1771.）

[16] GUETA G G， ABRAHAM I， GROSSMAN S， et al. SBFT： a scalable and decentralized trust infrastructure ［C］// Proceedings of the 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks. Piscataway： IEEE， 2019： 568-580.

[17] YIN M F， MALKHI D， REITER M K， et al. HotStuff： BFT consensus with linearity and responsiveness［C］// Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. New York： ACM， 2019： 347-356.

[18] ABRAHAM I， MALKHI D， NAYAK K， et al. Sync HotStuff： simple and practical synchronous state machine replication［C］// Proceedings of the 2020 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2020： 106-118.

[19] CAPPOS J， HARTMAN J H. San Fermín： aggregating large data sets using a binomial swap forest［C］// Proceedings of the 5th USENIX Symposium on Networked System Design and Implementation. Berkeley： USENIX Association， 2008： 147-160.

[20] 韓璇，袁勇，王飛躍. 區(qū)塊鏈安全問(wèn)題：研究現(xiàn)狀與展望［J］. 自動(dòng)化學(xué)報(bào)， 2019， 45（1）： 206-225.（HAN X， YUAN Y， WANG F Y. Security problems on blockchain： the state of the art and future trends［J］. Acta Automatica Sinica， 2019， 45（1）：206-225.）

TANG Chunming， born in 1971， Ph. D.， professor. Her research interests include computer vision， deep learning， blockchain.

CHEN Yuqing， born in 1997， M. S. candidate. Her research interests include blockchain， data security.

ZHANG Zidi， born in 2001. His research interests include computer vision， blockchain.

Improved consensus algorithm based on binomial swap forest and HotStuff

TANG Chunming1*， CHEN Yuqing2， ZHANG Zidi3

（1，，300387，；2，，300387，；3，，300350，）

Aiming at the problems of Byzantine Fault Tolerant （BFT） consensus mechanisms in the blockchain such as high communication complexity， complex view change and poor scalability， a consensus algorithm based on binomial swap forest and HotStuff named HSP （HotStuff Plus） consensus algorithm was proposed. In order to realize signature batch verification and signature aggregation， the Boneh-Lynn-Shacham （BLS） signature algorithm was adopted； in order to reduce the communication complexity of the system， threshold signature technology was adopted； in order to reduce the communication complexity during view change， the consensus process adopted a three-phase confirmation method； in order to reduce the number of communications between the primary and secondary nodes and reduce the pressure on the primary node when aggregating signatures， an improved binomial swap forest technology was adopted. Test results show that when the total number of system nodes is 64 and the request and reply are both 256 bytes， the throughput of HSP consensus algorithm is 33.8% higher than that of HotStuff consensus mechanism， and the consensus delay of HSP consensus algorithm is 16.4% lower than that of HotStuff consensus mechanism. It can be seen that HSP consensus algorithm has better performance when the number of nodes is large.

blockchain; consensus mechanism; threshold signature; binomial swap forest; view change

TP311

A

1001-9081（2022）07-2112-06

10.11772/j.issn.1001-9081.2021040659

2021?04?25；

2021?06?25；

2021?07?15。

湯春明（1971—），女，吉林吉林人，教授，博士生導(dǎo)師，博士，主要研究方向：計(jì)算機(jī)視覺(jué)、深度學(xué)習(xí)、區(qū)塊鏈； 陳雨晴（1997—），女，河北廊坊人，碩士研究生，主要研究方向：區(qū)塊鏈、數(shù)據(jù)安全； 張梓迪（2001—），男，吉林長(zhǎng)春人，主要研究方向：計(jì)算機(jī)視覺(jué)、區(qū)塊鏈。