基于可驗證延遲函數的改進實用拜占庭容錯算法

王春東，姜鑫

基于可驗證延遲函數的改進實用拜占庭容錯算法

王春東*，姜鑫

（天津理工大學 計算機科學與工程學院，天津 300384）（ ? 通信作者電子郵箱michael3769@163.com）

針對實用拜占庭容錯（PBFT）共識機制的主節點選擇不合理和高交易延遲問題，提出一種基于可驗證延遲函數（VDF）的改進實用拜占庭容錯共識機制VPBFT。首先，針對原有的PBFT算法引入投票機制進行節點選取，并根據隨機投票結果將節點劃分為普通節點、投票節點、備份節點和共識節點；其次，改進PBFT算法主節點選舉機制，即使用VDF進行主節點選舉，并利用上一區塊哈希值和用戶私鑰生成隨機數，增加主節點的不可預測性，保證共識安全；最后，優化PBFT算法的共識過程，將共識過程簡化為三個階段，從而降低算法復雜度，減少通信開銷。實驗結果表明，所提出的VPBFT在安全性和共識性能方面優于原有PBFT算法。

區塊鏈；實用拜占庭容錯；可驗證延遲函數；投票機制；哈希函數；交易延遲

0 引言

區塊鏈技術是結合密碼學、點對點網絡、分布式存儲、共識機制和激勵機制的分布式網絡數據存儲技術，具有分布式對等結構、去中心化信任、數據公開透明和防篡改特點［1］，近年來已經被應用于醫療數據共享［2］、輔助醫療決策和解決重大公共衛生等領域。

區塊鏈沒有中央權威節點，所有節點都可平等地參與共識過程。因此，共識機制［3］是確保數據一致性，維護系統安全的核心要素。區塊鏈主要共識算法有工作量證明（Proof of Work， PoW）、權益證明（Proof of Stake， PoS）、委托權益證明（Delegated Proof of Stake， DPoS）和實用拜占庭容錯（Practical Byzantine Fault Tolerance， PBFT）等［4］。其中，PoW算法主要應用于公有鏈中，以比特幣為代表的區塊鏈節點通過算力競爭主節點地位，主導共識過程；PoS算法根據節點擁有的幣齡決定挖礦難度，擁有最高權益的節點更容易獲得新區塊的記賬權和區塊獎勵；DPoS算法［5］通過擁有權益的節點使用代幣投票選出共識節點，需要代幣激勵。所以，以上基于證明的共識機制不適用于醫療數據共享領域。

聯盟鏈中的PBFT共識算法不僅考慮系統中的故障節點，而且通過大多數誠實節點一致共識忽略惡意節點作惡行為。與公有鏈相比，PBFT節點更加穩定，共識效率更高，更符合醫療數據共享聯盟鏈需求。

針對現有研究和PBFT算法的不足，本文提出一種基于可驗證延遲函數（Verifiable Delay Function， VDF）的實用拜占庭改進算法VPBFT。首先，在原有PBFT算法中引入投票機制進行節點選舉，并成立共識節點委員會，根據隨機投票結果將節點分為普通節點、候選節點、投票節點和共識節點；其次，提出一種基于VDF的主節點選擇機制，參與節點分布式運行VDF并相互驗證結果，實現當前視圖下主節點的分布式選舉；最后，將PBFT算法的共識過程修改為請求、響應和承諾三階段，降低通信開銷，提高共識效率。

1 相關知識

1.1　PBFT共識算法

1.1.1PBFT共識過程

PBFT共識過程如圖1所示。具體共識流程［16］如下：

圖1　PBFT共識過程

1.1.2垃圾回收機制

垃圾回收機制［17］是指PBFT算法定期生成系統日志文件，當共識發生錯誤時進行恢復，以確保系統中大多數節點都可保存狀態機中最新數據。主要協議如下：

1.1.3視圖更換協議

主節點選舉：共識節點網絡根據如下計算公式生成新視圖下主共識節點。

1.2　可驗證延遲函數

VDF［19］是有固定運算順序并且可以快速驗證的大規模并行算法，由初始化算法Setup、計算算法Eval和驗證算法Verify組成，算法流程如圖2所示。

圖2　VDF算法流程

2 VPBFT算法設計與實現

2.1　整體思想

PBFT作為強一致性共識機制，當網絡中共識節點數目過多時很難快速達成共識，同時區塊生成率較低。為了使PBFT算法更符合醫療數據共享場景，本文提出一種基于VDF的改進算法VPBFT。該算法使用投票機制進行節點選取，并改進主節點選舉策略，利用VDF延遲可驗證特性分布式選舉主節點。最后，優化PBFT算法共識過程，提高通信效率。VPBFT算法設計流程如圖3所示。具體改進措施如下：

在PBFT算法中引入投票機制進行節點選舉，根據投票結果將節點劃分為普通節點、投票節點、備份節點和共識節點，由可信度較高的投票節點隨機選舉產生備份節點和共識節點主導共識過程，減少通信開銷。

提出基于VDF的主節點分布式選舉，在節點選取階段生成主節點后，各主節點獨立運行VDF的初始化函數，通過將上一區塊哈希值和自身私鑰作為函數輸入保證VDF輸出唯一性。同時，設置延遲參數檢測惡意挖礦競爭，抵抗曠工硬件優勢帶來的并行加速優勢，保證共識安全。

為減少通信開銷，本文方案將共識過程簡化為請求、響應、承諾三個階段。投票式節點選取和分布式主節點選舉策略保證了系統節點的可靠性，因此刪除PBFT算法中客戶端和系統節點之間的交互操作，由主節點完成與客戶端的交互。

圖3　VPBFT算法流程

2.2　算法設計

2.2.1系統節點選取

為了增加參與節點的可信度，保證共識安全，本方案使用投票機制進行節點選取，通過隨機節點廣播投票，其余節點相互驗證方式選舉系統節點。設置節點委員會實現不同節點間相互制約，同時根據網絡規模設定節點數量，保證系統穩定運行。

委員會節點由普通節點、投票節點、備份節點和共識節點組成，其中，投票節點負責對備份節點和共識節點進行推薦和投票，并驗證和轉發主節點廣播交易。作為系統選舉初始化節點，投票節點由普通節點實名認證生成；共識節點發起新區提案并對交易進行驗證，主導當前視圖的共識過程；備份節點不可發起新區塊共識，但可以驗證和接收新區塊，并擁有全網數據副本，當共識節點有違規和退出行為時，由備份節點遞補；普通節點可以發布交易，不可參與共識，可以隨機加入和退出。VPBFT節點模型如圖4所示。

VPBFT網絡中系統節點數量可動態調整。從共識節點中選擇主節點，同時隔離惡意節點，在視圖更換時伴隨系統節點重新選舉，根據節點可靠性對普通節點、投票節點、備份節點和共識節點角色動態調整，以適應動態網絡，優化共識性能。

圖4　VPBFT節點模型

VPBFT節點選擇投票過程如下：

2）投票節點匯總本地投票信息表，得到當前網絡規模下各共識節點、備份節點和普通節點數目，生成委員會節點列表并相互廣播確認。

3）各投票節點收集委員會各投票節點廣播信息，當有效廣播信息超過/2時，完成本視圖下節點選取過程。

2.2.2主節點選舉策略

VPBFT分布式主節點選舉過程如下：

1）初始化階段：各共識節點獨立計算私鑰哈希值初始化隨機安全參數，通過私鑰保密性保證分布式隨機生成，確保VDF去中心化運行。根據節點規模設置延遲時間，保證共識速度和出塊效率，參數的設置使得惡意節點使用硬件優勢并行加速不可行。最后各共識節點運行Setup函數生成計算參數和用于驗證參數，Setup函數計算公式如下：

2）競爭階段：各共識節點完成參數初始化后，以最新區塊高度的哈希值作為輸入，運行VDF計算函數Eval，競爭主節點地位，廣播計算結果、證明和證明參數，便于其余節點驗證。Eval函數計算公式如下：

共識節點和備份節點收到驗證廣播后，運行VDF驗證函數Verify，校驗通過后保存結果值哈希值到本地索引表并轉播廣播內容，驗證失敗將消息丟棄。Verify函數計算公式如下：

在時間段中，參與競爭共識節點不斷接收計算哈希值廣播，并與當前存儲哈希值進行比較，小于當前哈希值則進行替換操作，否則丟棄此哈希值。最終每個共識節點保留一份時間段內生成最小哈希值記錄，廣播此記錄。

圖5　VPBFT主節點選舉流程

2.2.3VPBFT共識過程

本方案提出的VPBFT算法使用分布式網絡拓撲結構，事務的發起方從原始客戶端變為主節點。假設共識網絡中參與節點原始狀態一致，那么每個節點的配置信息、存儲備份和區塊高度等也相同，保證了節點參與競爭主節點的公平性。

PBFT是一個經典的分布式共識算法，它的三階段請求方法也基于分布式進行設計，主要目的是在以狀態機副本為主的分布式系統中正確執行指令順序，由于在區塊鏈上達成共識需要在整個網絡中進行多次信息廣播和驗證，因此可以合并原始客戶端發送階段，由當前主節點完成與客戶端的交互行為，減少共識過程中信息的傳遞，提高共識效率。

VPBFT共識過程具體步驟如下：

1）發起共識。主節點根據共識策略從內存池中選舉事務并將它們打包到一個請求消息中進行廣播，以啟動新一輪共識。如果共識節點和普通節點在超時之前接收到廣播消息，將對消息進行驗證；否則主節點違規超時，其余共識節點廣播視圖更換消息，請求更換視圖。

2）廣播響應消息。共識節點和備份節點如果在超時之前接收所有的請求消息，對消息進行驗證，驗證通過進行廣播回復，否則嘗試更換視圖。

3）收集響應消息并廣播承諾消息。主節點和其余節點在超時前收集足夠的回復消息并進行驗證，如果驗證通過將進行廣播驗證，否則將更改視圖。

4）收集承諾消息并生成新區塊。參與共識的每個節點如果在超時前收集到足夠多有效承諾消息，則在驗證通過后將生成新區塊并相互廣播，實現區塊同步，完成共識。

3 VPBFT算法實驗分析

3.1　安全性分析

VPBFT的安全性主要體現在高可靠性和高容錯性兩方面，具體分析如下。

3.1.1可靠性分析

VPBFT安全性主要受兩個方面影響：投票式節點選取保證只有隨機投票數較高的節點才能參與系統，維持系統節點安全性；主節點選舉策略實現當前視圖下主節點的分布式隨機選舉，避免惡意節點控制共識過程，危害系統安全。

在節點選取階段，普通節點經過實名認證獲得投票權利，保證了投票節點的可信度與安全性。備份節點和共識節點都由投票節點隨機投票選取獲得，同時備份節點監督共識節點行為，當共識節點產生違規行為時，投票節點和備份節點都可啟動視圖更換協議，完成主節點更換，保證共識過程安全。

主節點選舉過程中根據系統規模設置延遲參數抵抗惡意用戶通過硬件優勢競爭主節點地位，避免算力浪費。同時，用戶分布式獨立生成安全參數保證系統去中心化特性，并使用區塊哈希值和用戶私鑰組合方式增加主節點選舉的不可預測性，通過一系列節點廣播和累計有效廣播保證當選節點有效主導共識，增加系統可靠性。

隨著系統運行，節點選取策略和主節點安全選舉保證了VPBFT共識的可靠性，降低惡意節點當選主節點概率，使主節點錯誤率降低，提高了VPBFT的效率，即單位時間內的工作量（Transaction Per Second， TPS），共識結果更加可靠，實驗結果如圖6所示，VPBFT算法比PBFT算法可靠性更高。

圖6　VPBFT和PBFT的可靠性比較

3.1.2容錯性分析

3.2　性能驗證

本文實現了一個基于Python語言的區塊鏈原型系統，并分別運行PBFT和VPBFT算法，通過測試和比較驗證了VPBFT算法的整體效果。測試環境為Windows操作系統，CPU為Intel Core i5-6200U 2.30 GHz，內存為8 GB，固態硬盤為512 GB。

3.2.1交易延遲測試

交易延遲指由節點發起的一筆交易從廣播到添加到區塊所消耗的時間。在P2P網絡上進行測試，設定事務數為200，分別對5、10、15、20、25和30個節點進行測試，結果如圖7所示?？梢钥闯?，VPBFT算法交易延遲明顯比PBFT算法短，而且隨節點數的增加，PBFT算法的交易延遲增加得更快，而VPBFT算法交易延遲相對穩定，增長較慢。因此，在節點數較多的情況下，VPBFT算法優勢更明顯。

圖7　VPBFT和PBFT的交易延遲比較

3.2.2出塊效率比較

出塊效率為單位時間內生成區塊數，是區塊鏈系統穩定性的重要標志。如圖8所示，通過區塊鏈原型測試，在15個共識節點參與共識場景下，分別對100、200、300、400和500個事務量進行比較，PBFT算法平均出塊效率為2.17，VPBFT算法的平均出塊效率為3.94，是PBFT的1.8倍。因此，與PBFT算法相比，VPBFT算法的出塊效率有較大的提高，在穩定性方面具有優勢。

圖8　不同事務量下VPBFT和PBFT的出塊效率比較

為了進一步比較大規模節點下VPBFT與PBFT的出塊效率，分別設置了100到500節點模擬驗證區塊出塊效率，實驗結果如圖9所示。

圖9　不同節點規模下VPBFT和PBFT的區塊生成率比較

由圖9可以看出，在VPBFT與PBFT運行期間出塊效率是穩定的，由于VPBFT進行了惡意節點識別與主節點隨機選舉，改進后的VPBFT共識機制更高效，在大規模網絡節點下出塊效率更高。

4 結語

為了提高PBFT算法主節點選擇安全性和共識效率，本文提出了VPBFT，并通過投票處理將節點分為普通節點、投票節點、備份節點和共識節點。同時使用可驗證延遲函數改進PBFT主節點選舉方式，增加主節點選舉的不可預測性，保證共識安全。最后，共識節點參與共識過程，并將共識過程簡化為三個階段，減少帶寬資源消耗。實驗結果表明，VPBFT算法在可靠性、容錯性、交易延遲和區塊生成率方面比PBFT算法具有優勢，更適合于實際應用。

[1] 張亮，劉百祥，張如意，等. 區塊鏈技術綜述［J］. 計算機工程， 2019， 45（5）：1-12.（ZHANG L， LIU B X， ZHANG R Y， et al. Overview of blockchain technology［J］. Computer Engineering， 2019， 45（5）： 1-12.）

[2] 羅文俊，聞勝蓮，程雨. 基于區塊鏈的電子醫療病歷共享方案［J］. 計算機應用， 2020， 40（1）：157-161. （LUO W J， WEN S L， CHENG Y. Blockchain-based electronic medical record sharing scheme［J］. Journal of Computer Applications， 2020， 40（1）： 157-161.）

[3] 郭上銅，王瑞錦，張鳳荔. 區塊鏈技術原理與應用綜述［J］. 計算機科學， 2021， 48（2）：271-281.（GUO S T， WANG R J， ZHANG F L. Summary of principle and application of blockchain［J］. Computer Science， 2021， 48（2）： 271-281.）

[4] WANG W， HONG D T， HU P， et al. A survey on consensus mechanisms and mining strategy management in blockchain networks［J］. IEEE Access， 2019， 7： 22328-22370.

[5] 方維維，王子岳，宋慧麗，等. 一種面向區塊鏈的優化PBFT共識算法［J］.北京交通大學學報， 2019， 43（5）：58-64. （FANG W W， WANG Z Y， SONG H L， et al. An optimized PBFT consensus algorithm for blockchain［J］. Journal of Beijing Jiaotong University， 2019， 43（5）： 58-64.）

[6] LI Y， WANG Z， FAN J， et al. An extensible consensus algorithm based on PBFT［C］// Proceedings of the 2019 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery. Piscataway： IEEE， 2019： 17-23.

[7] GAB B， WU Q， LI X， et al. Classification of blockchain consensus mechanisms based on PBFT algorithm［C］// Proceedings of the 2021 International Conference on Computer Engineering and Application. Piscataway： IEEE， 2021： 26-29.

[8] 任秀麗，張雷. 基于實用拜占庭容錯的改進的多主節點共識機制［J］. 計算機應用， 2022， 42（5）：1500-1507. （RENG X L， ZHANG L. Improved multi-primary node consensus mechanism based on practical Byzantine fault tolerance［J］. Journal of Computer Applications， 2022， 42（5）： 1500-1507.）

[9] 甘俊，李強，陳子豪，等. 區塊鏈實用拜占庭容錯共識算法的改進［J］. 計算機應用， 2019， 39（7）：2148-2155.（GAN J， LI Q， CHEN Z H， et al. Improvement of blockchain practical Byzantine fault tolerance consensus algorithm［J］. Journal of Computer Applications， 2019， 39（7）： 2148-2155.

[10] GUAN G， FENG L， NING J， et al. Improvement of practical Byzantine fault tolerant consensus algorithm for blockchain［C］// Proceedings of the IEEE 3rd International Conference on Frontiers Technology of Information and Computer. Piscataway： IEEE， 2021： 182-187.

[11] JIANG W， CHEN L， WANG Y， et al. An efficient Byzantine fault-tolerant consensus mechanism based on threshold signature［C］// Proceedings of the 2020 International Conference on Internet of Things and Intelligent Applications. Piscataway： IEEE， 2020： 1-5.

[12] CHEN R， WANG L， ZHU R， et al. An improved practical Byzantine fault tolerance algorithm based on vague sets and random numbers［C］// Proceedings of the 7th International Conference on Intelligent Computing and Signal Processing. Piscataway： IEEE， 2022： 151-155.

[13] ZHANG Z， ZHU D， FAN W. QPBFT： practical Byzantine fault tolerance consensus algorithm based on quantified-role［C］// Proceedings of the IEEE 19th International Conference on Trust， Security and Privacy in Computing and Communications. Piscataway： IEEE， 2020： 991-997.

[14] YU G， WU B， NIU X. Improved blockchain consensus mechanism based on PBFT algorithm［C］// Proceedings of the 2nd International Conference on Advances in Computer Technology， Information Science and Communications. Piscataway： IEEE， 2020： 14-21.

[15] 劉懿中，劉建偉，張宗洋，等. 區塊鏈共識機制研究綜述［J］. 密碼學報， 2019， 6（4）：395-432.（LIU Y Z， LIU J W， ZHANG Z Y， et al. Overview on blockchain consensus mechanisms［J］. Journal of Cryptologic Research， 2019， 6（4）： 395-432.）

[16] 李騰. PBFT共識算法的改進及其應用研究［D］. 邯鄲：河北工程大學， 2021： 2.（LI T. Improvement and application of practical Byzantine fault tolerance consensus algorithm［D］. Handan： Hebei University of Engineering， 2021： 2.）

[17] 顏丙輝. 基于拜占庭容錯的區塊鏈共識方法研究［D］. 哈爾濱：哈爾濱工程大學， 2020： 2.（YAN B H. Research on block chain consensus methods based on Byzantine fault tolerance［D］. Harbin： Harbin Engineering University， 2020： 2.）

[18] 孫耀景. 基于實用拜占庭容錯算法的區塊鏈共識算法研究［D］. 湘潭：湘潭大學， 2020： 2.（SUN Y J. Research on the blockchain consensus algorithm based on practical Byzantine fault tolerant algorithm［D］. Xiangtan： Xiangtan University， 2020： 2.）

[19] BONEH D， BONNEAU J， BüNZ B， et al. Verifiable delay functions［C］// Proceedings of the 2018 Annual International Cryptology Conference， LNCS 10991. Cham： Springer， 2018： 757-788.

[20] ZHOU M， LIN X， LIU A， et al. An improved blockchain consensus protocol with distributed verifiable delay function［C］// Proceedings of the 2021 IEEE International Conference on Electronic Technology， Communication and Information. Piscataway： IEEE， 2021： 330-337.

Improved practical Byzantine fault tolerance algorithm based on verifiable delay function

WANG Chundong*， JIANG Xin

（，，300384，）

To solve the problems of unreasonable primary node selection and high transaction delay in Practical Byzantine Fault Tolerance （PBFT） consensus mechanism， an improved PBFT consensus mechanism based on Verifiable Delay Function （VDF） was proposed， called VPBFT. Firstly， a voting mechanism was introduced into original PBFT algorithm to select nodes， which were divided into ordinary nodes， voting nodes， backup nodes and consensus nodes according to random voting results. Secondly， the primary node selection mechanism of PBFT algorithm was improved by using VDF for primary node selection， and random numbers were generated by the hash value of the previous block and the user’s private key to increase the unpredictability of the primary node and ensure the consensus security. Finally， the consensus process of PBFT algorithm was optimized by simplifying consensus process into three stages， thereby reducing the algorithm complexity and communication overhead. Experimental results show that the proposed VPBFT outperforms the original PBFT algorithm in terms of security and consensus performance.

blockchain; Practical Byzantine Fault Tolerance (PBFT); Verifiable Delay Function (VDF); voting mechanism; hash function; transaction delay

1001-9081（2023）11-3484-06

10.11772/j.issn.1001-9081.2022111708

2022?11?18；

2023?02?24；

“科技助力經濟2020”重點專項（SQ2020YFF0413781）；天津市科委重大專項（15ZXDSGX00030）； 國家自然科學基金面上—聯合基金資助項目（U1536122）。

王春東（1969－），男，天津人，教授，博士，CCF會員，主要研究方向：網絡信息安全、普適計算、移動計算、智能信息處理； 姜鑫（1997－），男，山東菏澤人，碩士研究生，主要研究方向：區塊鏈、數據共享。

TP301

A

2023?02?25。

This work is partially supported by “National High Science and Technology for Economy 2020” Key Project （SQ2020YFF0413781）， Major Project of Tianjin Science and Technology Commission （15ZXDSGX00030）， National Natural Science Foundation of China （General Joint Fund） （U1536122）.

WANG Chundong， born in 1969， Ph. D.， professor. His research interests include network information security， ubiquitous computing， mobile computing， intelligent information processing.

JIANG Xin， born in 1997， M. S. candidate. His research interests include blockchain， data sharing.