王春東，姜鑫

基于可驗(yàn)證延遲函數(shù)的改進(jìn)實(shí)用拜占庭容錯算法

王春東*，姜鑫

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

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

區(qū)塊鏈；實(shí)用拜占庭容錯；可驗(yàn)證延遲函數(shù)；投票機(jī)制；哈希函數(shù)；交易延遲

0 引言

區(qū)塊鏈技術(shù)是結(jié)合密碼學(xué)、點(diǎn)對點(diǎn)網(wǎng)絡(luò)、分布式存儲、共識機(jī)制和激勵機(jī)制的分布式網(wǎng)絡(luò)數(shù)據(jù)存儲技術(shù)，具有分布式對等結(jié)構(gòu)、去中心化信任、數(shù)據(jù)公開透明和防篡改特點(diǎn)［1］，近年來已經(jīng)被應(yīng)用于醫(yī)療數(shù)據(jù)共享［2］、輔助醫(yī)療決策和解決重大公共衛(wèi)生等領(lǐng)域。

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

聯(lián)盟鏈中的PBFT共識算法不僅考慮系統(tǒng)中的故障節(jié)點(diǎn)，而且通過大多數(shù)誠實(shí)節(jié)點(diǎn)一致共識忽略惡意節(jié)點(diǎn)作惡行為。與公有鏈相比，PBFT節(jié)點(diǎn)更加穩(wěn)定，共識效率更高，更符合醫(yī)療數(shù)據(jù)共享聯(lián)盟鏈需求。

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

1 相關(guān)知識

1.1　PBFT共識算法

1.1.1PBFT共識過程

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

圖1　PBFT共識過程

1.1.2垃圾回收機(jī)制

垃圾回收機(jī)制［17］是指PBFT算法定期生成系統(tǒng)日志文件，當(dāng)共識發(fā)生錯誤時進(jìn)行恢復(fù)，以確保系統(tǒng)中大多數(shù)節(jié)點(diǎn)都可保存狀態(tài)機(jī)中最新數(shù)據(jù)。主要協(xié)議如下：

1.1.3視圖更換協(xié)議

主節(jié)點(diǎn)選舉：共識節(jié)點(diǎn)網(wǎng)絡(luò)根據(jù)如下計算公式生成新視圖下主共識節(jié)點(diǎn)。

1.2　可驗(yàn)證延遲函數(shù)

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

圖2　VDF算法流程

2 VPBFT算法設(shè)計與實(shí)現(xiàn)

2.1　整體思想

PBFT作為強(qiáng)一致性共識機(jī)制，當(dāng)網(wǎng)絡(luò)中共識節(jié)點(diǎn)數(shù)目過多時很難快速達(dá)成共識，同時區(qū)塊生成率較低。為了使PBFT算法更符合醫(yī)療數(shù)據(jù)共享場景，本文提出一種基于VDF的改進(jìn)算法VPBFT。該算法使用投票機(jī)制進(jìn)行節(jié)點(diǎn)選取，并改進(jìn)主節(jié)點(diǎn)選舉策略，利用VDF延遲可驗(yàn)證特性分布式選舉主節(jié)點(diǎn)。最后，優(yōu)化PBFT算法共識過程，提高通信效率。VPBFT算法設(shè)計流程如圖3所示。具體改進(jìn)措施如下：

在PBFT算法中引入投票機(jī)制進(jìn)行節(jié)點(diǎn)選舉，根據(jù)投票結(jié)果將節(jié)點(diǎn)劃分為普通節(jié)點(diǎn)、投票節(jié)點(diǎn)、備份節(jié)點(diǎn)和共識節(jié)點(diǎn)，由可信度較高的投票節(jié)點(diǎn)隨機(jī)選舉產(chǎn)生備份節(jié)點(diǎn)和共識節(jié)點(diǎn)主導(dǎo)共識過程，減少通信開銷。

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

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

圖3　VPBFT算法流程

2.2　算法設(shè)計

2.2.1系統(tǒng)節(jié)點(diǎn)選取

為了增加參與節(jié)點(diǎn)的可信度，保證共識安全，本方案使用投票機(jī)制進(jìn)行節(jié)點(diǎn)選取，通過隨機(jī)節(jié)點(diǎn)廣播投票，其余節(jié)點(diǎn)相互驗(yàn)證方式選舉系統(tǒng)節(jié)點(diǎn)。設(shè)置節(jié)點(diǎn)委員會實(shí)現(xiàn)不同節(jié)點(diǎn)間相互制約，同時根據(jù)網(wǎng)絡(luò)規(guī)模設(shè)定節(jié)點(diǎn)數(shù)量，保證系統(tǒng)穩(wěn)定運(yùn)行。

委員會節(jié)點(diǎn)由普通節(jié)點(diǎn)、投票節(jié)點(diǎn)、備份節(jié)點(diǎn)和共識節(jié)點(diǎn)組成，其中，投票節(jié)點(diǎn)負(fù)責(zé)對備份節(jié)點(diǎn)和共識節(jié)點(diǎn)進(jìn)行推薦和投票，并驗(yàn)證和轉(zhuǎn)發(fā)主節(jié)點(diǎn)廣播交易。作為系統(tǒng)選舉初始化節(jié)點(diǎn)，投票節(jié)點(diǎn)由普通節(jié)點(diǎn)實(shí)名認(rèn)證生成；共識節(jié)點(diǎn)發(fā)起新區(qū)提案并對交易進(jìn)行驗(yàn)證，主導(dǎo)當(dāng)前視圖的共識過程；備份節(jié)點(diǎn)不可發(fā)起新區(qū)塊共識，但可以驗(yàn)證和接收新區(qū)塊，并擁有全網(wǎng)數(shù)據(jù)副本，當(dāng)共識節(jié)點(diǎn)有違規(guī)和退出行為時，由備份節(jié)點(diǎn)遞補(bǔ)；普通節(jié)點(diǎn)可以發(fā)布交易，不可參與共識，可以隨機(jī)加入和退出。VPBFT節(jié)點(diǎn)模型如圖4所示。

VPBFT網(wǎng)絡(luò)中系統(tǒng)節(jié)點(diǎn)數(shù)量可動態(tài)調(diào)整。從共識節(jié)點(diǎn)中選擇主節(jié)點(diǎn)，同時隔離惡意節(jié)點(diǎn)，在視圖更換時伴隨系統(tǒng)節(jié)點(diǎn)重新選舉，根據(jù)節(jié)點(diǎn)可靠性對普通節(jié)點(diǎn)、投票節(jié)點(diǎn)、備份節(jié)點(diǎn)和共識節(jié)點(diǎn)角色動態(tài)調(diào)整，以適應(yīng)動態(tài)網(wǎng)絡(luò)，優(yōu)化共識性能。

圖4　VPBFT節(jié)點(diǎn)模型

VPBFT節(jié)點(diǎn)選擇投票過程如下：

2）投票節(jié)點(diǎn)匯總本地投票信息表，得到當(dāng)前網(wǎng)絡(luò)規(guī)模下各共識節(jié)點(diǎn)、備份節(jié)點(diǎn)和普通節(jié)點(diǎn)數(shù)目，生成委員會節(jié)點(diǎn)列表并相互廣播確認(rèn)。

3）各投票節(jié)點(diǎn)收集委員會各投票節(jié)點(diǎn)廣播信息，當(dāng)有效廣播信息超過/2時，完成本視圖下節(jié)點(diǎn)選取過程。

2.2.2主節(jié)點(diǎn)選舉策略

VPBFT分布式主節(jié)點(diǎn)選舉過程如下：

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

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

共識節(jié)點(diǎn)和備份節(jié)點(diǎn)收到驗(yàn)證廣播后，運(yùn)行VDF驗(yàn)證函數(shù)Verify，校驗(yàn)通過后保存結(jié)果值哈希值到本地索引表并轉(zhuǎn)播廣播內(nèi)容，驗(yàn)證失敗將消息丟棄。Verify函數(shù)計算公式如下：

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

圖5　VPBFT主節(jié)點(diǎn)選舉流程

2.2.3VPBFT共識過程

本方案提出的VPBFT算法使用分布式網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，事務(wù)的發(fā)起方從原始客戶端變?yōu)橹鞴?jié)點(diǎn)。假設(shè)共識網(wǎng)絡(luò)中參與節(jié)點(diǎn)原始狀態(tài)一致，那么每個節(jié)點(diǎn)的配置信息、存儲備份和區(qū)塊高度等也相同，保證了節(jié)點(diǎn)參與競爭主節(jié)點(diǎn)的公平性。

PBFT是一個經(jīng)典的分布式共識算法，它的三階段請求方法也基于分布式進(jìn)行設(shè)計，主要目的是在以狀態(tài)機(jī)副本為主的分布式系統(tǒng)中正確執(zhí)行指令順序，由于在區(qū)塊鏈上達(dá)成共識需要在整個網(wǎng)絡(luò)中進(jìn)行多次信息廣播和驗(yàn)證，因此可以合并原始客戶端發(fā)送階段，由當(dāng)前主節(jié)點(diǎn)完成與客戶端的交互行為，減少共識過程中信息的傳遞，提高共識效率。

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

1）發(fā)起共識。主節(jié)點(diǎn)根據(jù)共識策略從內(nèi)存池中選舉事務(wù)并將它們打包到一個請求消息中進(jìn)行廣播，以啟動新一輪共識。如果共識節(jié)點(diǎn)和普通節(jié)點(diǎn)在超時之前接收到廣播消息，將對消息進(jìn)行驗(yàn)證；否則主節(jié)點(diǎn)違規(guī)超時，其余共識節(jié)點(diǎn)廣播視圖更換消息，請求更換視圖。

2）廣播響應(yīng)消息。共識節(jié)點(diǎn)和備份節(jié)點(diǎn)如果在超時之前接收所有的請求消息，對消息進(jìn)行驗(yàn)證，驗(yàn)證通過進(jìn)行廣播回復(fù)，否則嘗試更換視圖。

3）收集響應(yīng)消息并廣播承諾消息。主節(jié)點(diǎn)和其余節(jié)點(diǎn)在超時前收集足夠的回復(fù)消息并進(jìn)行驗(yàn)證，如果驗(yàn)證通過將進(jìn)行廣播驗(yàn)證，否則將更改視圖。

4）收集承諾消息并生成新區(qū)塊。參與共識的每個節(jié)點(diǎn)如果在超時前收集到足夠多有效承諾消息，則在驗(yàn)證通過后將生成新區(qū)塊并相互廣播，實(shí)現(xiàn)區(qū)塊同步，完成共識。

3 VPBFT算法實(shí)驗(yàn)分析

3.1　安全性分析

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

3.1.1可靠性分析

VPBFT安全性主要受兩個方面影響：投票式節(jié)點(diǎn)選取保證只有隨機(jī)投票數(shù)較高的節(jié)點(diǎn)才能參與系統(tǒng)，維持系統(tǒng)節(jié)點(diǎn)安全性；主節(jié)點(diǎn)選舉策略實(shí)現(xiàn)當(dāng)前視圖下主節(jié)點(diǎn)的分布式隨機(jī)選舉，避免惡意節(jié)點(diǎn)控制共識過程，危害系統(tǒng)安全。

在節(jié)點(diǎn)選取階段，普通節(jié)點(diǎn)經(jīng)過實(shí)名認(rèn)證獲得投票權(quán)利，保證了投票節(jié)點(diǎn)的可信度與安全性。備份節(jié)點(diǎn)和共識節(jié)點(diǎn)都由投票節(jié)點(diǎn)隨機(jī)投票選取獲得，同時備份節(jié)點(diǎn)監(jiān)督共識節(jié)點(diǎn)行為，當(dāng)共識節(jié)點(diǎn)產(chǎn)生違規(guī)行為時，投票節(jié)點(diǎn)和備份節(jié)點(diǎn)都可啟動視圖更換協(xié)議，完成主節(jié)點(diǎn)更換，保證共識過程安全。

主節(jié)點(diǎn)選舉過程中根據(jù)系統(tǒng)規(guī)模設(shè)置延遲參數(shù)抵抗惡意用戶通過硬件優(yōu)勢競爭主節(jié)點(diǎn)地位，避免算力浪費(fèi)。同時，用戶分布式獨(dú)立生成安全參數(shù)保證系統(tǒng)去中心化特性，并使用區(qū)塊哈希值和用戶私鑰組合方式增加主節(jié)點(diǎn)選舉的不可預(yù)測性，通過一系列節(jié)點(diǎn)廣播和累計有效廣播保證當(dāng)選節(jié)點(diǎn)有效主導(dǎo)共識，增加系統(tǒng)可靠性。

隨著系統(tǒng)運(yùn)行，節(jié)點(diǎn)選取策略和主節(jié)點(diǎn)安全選舉保證了VPBFT共識的可靠性，降低惡意節(jié)點(diǎn)當(dāng)選主節(jié)點(diǎn)概率，使主節(jié)點(diǎn)錯誤率降低，提高了VPBFT的效率，即單位時間內(nèi)的工作量（Transaction Per Second， TPS），共識結(jié)果更加可靠，實(shí)驗(yàn)結(jié)果如圖6所示，VPBFT算法比PBFT算法可靠性更高。

圖6　VPBFT和PBFT的可靠性比較

3.1.2容錯性分析

3.2　性能驗(yàn)證

本文實(shí)現(xiàn)了一個基于Python語言的區(qū)塊鏈原型系統(tǒng)，并分別運(yùn)行PBFT和VPBFT算法，通過測試和比較驗(yàn)證了VPBFT算法的整體效果。測試環(huán)境為Windows操作系統(tǒng)，CPU為Intel Core i5-6200U 2.30 GHz，內(nèi)存為8 GB，固態(tài)硬盤為512 GB。

3.2.1交易延遲測試

交易延遲指由節(jié)點(diǎn)發(fā)起的一筆交易從廣播到添加到區(qū)塊所消耗的時間。在P2P網(wǎng)絡(luò)上進(jìn)行測試，設(shè)定事務(wù)數(shù)為200，分別對5、10、15、20、25和30個節(jié)點(diǎn)進(jìn)行測試，結(jié)果如圖7所示。可以看出，VPBFT算法交易延遲明顯比PBFT算法短，而且隨節(jié)點(diǎn)數(shù)的增加，PBFT算法的交易延遲增加得更快，而VPBFT算法交易延遲相對穩(wěn)定，增長較慢。因此，在節(jié)點(diǎn)數(shù)較多的情況下，VPBFT算法優(yōu)勢更明顯。

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

3.2.2出塊效率比較

出塊效率為單位時間內(nèi)生成區(qū)塊數(shù)，是區(qū)塊鏈系統(tǒng)穩(wěn)定性的重要標(biāo)志。如圖8所示，通過區(qū)塊鏈原型測試，在15個共識節(jié)點(diǎn)參與共識場景下，分別對100、200、300、400和500個事務(wù)量進(jìn)行比較，PBFT算法平均出塊效率為2.17，VPBFT算法的平均出塊效率為3.94，是PBFT的1.8倍。因此，與PBFT算法相比，VPBFT算法的出塊效率有較大的提高，在穩(wěn)定性方面具有優(yōu)勢。

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

為了進(jìn)一步比較大規(guī)模節(jié)點(diǎn)下VPBFT與PBFT的出塊效率，分別設(shè)置了100到500節(jié)點(diǎn)模擬驗(yàn)證區(qū)塊出塊效率，實(shí)驗(yàn)結(jié)果如圖9所示。

圖9　不同節(jié)點(diǎn)規(guī)模下VPBFT和PBFT的區(qū)塊生成率比較

由圖9可以看出，在VPBFT與PBFT運(yùn)行期間出塊效率是穩(wěn)定的，由于VPBFT進(jìn)行了惡意節(jié)點(diǎn)識別與主節(jié)點(diǎn)隨機(jī)選舉，改進(jìn)后的VPBFT共識機(jī)制更高效，在大規(guī)模網(wǎng)絡(luò)節(jié)點(diǎn)下出塊效率更高。

4 結(jié)語

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

[1] 張亮，劉百祥，張如意，等. 區(qū)塊鏈技術(shù)綜述［J］. 計算機(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] 羅文俊，聞勝蓮，程雨. 基于區(qū)塊鏈的電子醫(yī)療病歷共享方案［J］. 計算機(jī)應(yīng)用， 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] 郭上銅，王瑞錦，張鳳荔. 區(qū)塊鏈技術(shù)原理與應(yīng)用綜述［J］. 計算機(jī)科學(xué)， 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] 方維維，王子岳，宋慧麗，等. 一種面向區(qū)塊鏈的優(yōu)化PBFT共識算法［J］.北京交通大學(xué)學(xué)報， 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] 任秀麗，張雷. 基于實(shí)用拜占庭容錯的改進(jìn)的多主節(jié)點(diǎn)共識機(jī)制［J］. 計算機(jī)應(yīng)用， 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] 甘俊，李強(qiáng)，陳子豪，等. 區(qū)塊鏈實(shí)用拜占庭容錯共識算法的改進(jìn)［J］. 計算機(jī)應(yīng)用， 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] 劉懿中，劉建偉，張宗洋，等. 區(qū)塊鏈共識機(jī)制研究綜述［J］. 密碼學(xué)報， 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共識算法的改進(jìn)及其應(yīng)用研究［D］. 邯鄲：河北工程大學(xué)， 2021： 2.（LI T. Improvement and application of practical Byzantine fault tolerance consensus algorithm［D］. Handan： Hebei University of Engineering， 2021： 2.）

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

[18] 孫耀景. 基于實(shí)用拜占庭容錯算法的區(qū)塊鏈共識算法研究［D］. 湘潭：湘潭大學(xué)， 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；

“科技助力經(jīng)濟(jì)2020”重點(diǎn)專項(xiàng)（SQ2020YFF0413781）；天津市科委重大專項(xiàng)（15ZXDSGX00030）； 國家自然科學(xué)基金面上—聯(lián)合基金資助項(xiàng)目（U1536122）。

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

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.