湯春明，陳雨晴，張梓迪

基于二項交換林和HotStuff的改進共識算法

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

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

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

區(qū)塊鏈；共識機制；門限簽名；二項交換林；視圖切換

0 引言

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

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

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

1 HotStuff算法

1.1　共識流程

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

圖 1　HotStuff共識流程

1.2　HotStuff視圖切換流程及其缺點

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

2 改進HotStuff共識算法

2.1　改進二項交換林

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

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

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

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

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

圖 2　改進二項交換林

2.2　共識流程

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

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

圖 3　HSP共識流程

2.3　安全性分析

區(qū)塊鏈系統(tǒng)的基本安全目標是通過密碼學和網絡安全等技術手段，保證區(qū)塊鏈系統(tǒng)中的數(shù)據(jù)安全、共識安全、智能合約安全和內容安全。本文采用一致性和活性兩個安全屬性來衡量和評估區(qū)塊鏈的共識安全［20］。

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

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

3 實驗與結果分析

由于吞吐量和共識延遲是衡量共識算法的兩個基本標準，因此本文通過分析吞吐量和共識延遲來分析HSP共識算法的性能。

3.1　實驗環(huán)境

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

3.2　實驗設計

第一組實驗 取拜占庭節(jié)點數(shù)為0，節(jié)點總數(shù)為4，測試HotStuff（ECDSA）算法（記HS-ini）和HotStuff（BLS）算法（記HS+BLS）在請求和響應均為0字節(jié)、256字節(jié)和512字節(jié)三種情況下的吞吐量和共識延遲。實驗目的：測試BLS數(shù)字簽名算法對HotStuff算法的影響。

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

3.3　實驗結果

實驗一的測試結果如圖4、5所示。隨著request/reply的變大，吞吐量降低，共識延遲加長。當request/reply=256/256時，HotStuff（BLS）算法較HotStuff（ECDSA）算法吞吐量提升了19.5%，共識延遲降低了19.9%；當request/reply=512/512時，HotStuff（BLS）算法較HotStuff（ECDSA）算法吞吐量提升了22.6%，共識延遲降低了17.3%。

圖 4　吞吐量對比（實驗一）

圖 5　共識延遲對比（實驗一）

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

圖 6　吞吐量對比（實驗二）

圖 7　共識延遲對比（實驗二）

實驗三的測試結果如圖8、9所示。其中后標為net的曲線代表視圖切換的原因為網絡故障；后標為Leader的曲線代表視圖切換的原因為主節(jié)點故障。在節(jié)點總數(shù)為64且請求和響應均為256字節(jié)時，在由于網絡故障而發(fā)生視圖切換的情況下，HSP算法較HotStuff算法吞吐量提升了35.1%，共識延遲下降了22.6%；在由于主節(jié)點連續(xù)故障而連續(xù)進行視圖切換的情況下，HSP算法較HotStuff（BLS）吞吐量提升了34.4%，共識延遲降低了17.9%。

3.4　實驗結果分析

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

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

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

圖 8　視圖切換時的吞吐量（實驗三）

圖 9　視圖切換時共識延遲（實驗三）

4 結語

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

[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ū)塊鏈共識算法的發(fā)展現(xiàn)狀與展望［J］. 自動化學報， 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)盟鏈的多鏈式區(qū)塊鏈共識性能研究［D］. 南昌：東華理工大學，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］.計算機應用， 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ū)塊鏈安全問題：研究現(xiàn)狀與展望［J］. 自動化學報， 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—），女，吉林吉林人，教授，博士生導師，博士，主要研究方向：計算機視覺、深度學習、區(qū)塊鏈； 陳雨晴（1997—），女，河北廊坊人，碩士研究生，主要研究方向：區(qū)塊鏈、數(shù)據(jù)安全； 張梓迪（2001—），男，吉林長春人，主要研究方向：計算機視覺、區(qū)塊鏈。