基于防預(yù)測(cè)分組的PBFT 算法改進(jìn)方案*

周昌慧 劉萬里 梁 峰 李榮臻 徐 雷

（1.南京理工大學(xué)計(jì)算機(jī)與工程學(xué)院 南京 210094）

（2.南京市中西醫(yī)結(jié)合醫(yī)院 南京 210014）

（3.連云港市廣播電視臺(tái) 連云港 222000）

1 引言

區(qū)塊鏈這一概念起源于中本聰提出的比特幣［1］，其本質(zhì)是在對(duì)等網(wǎng)絡(luò)中基于密碼學(xué)構(gòu)建去中心化的分布式數(shù)據(jù)庫［2］。利用區(qū)塊鏈所具有的防篡改、可追溯、鏈上信息透明公開的特點(diǎn)，網(wǎng)絡(luò)中的對(duì)等節(jié)點(diǎn)之間互相信任，一致行動(dòng)，保證了在分布式場(chǎng)景下的鏈上數(shù)據(jù)一致可靠。近些年對(duì)于區(qū)塊鏈的相關(guān)技術(shù)的研究愈發(fā)火熱。2020 年12 月，中國信息通信研究院發(fā)布了《區(qū)塊鏈白皮書（2020年）》針對(duì)區(qū)塊鏈的生態(tài)和發(fā)展做出了系統(tǒng)性的全景觀望。隨著廣大研究者的不懈鉆研，逐漸發(fā)掘出了區(qū)塊鏈更多的潛力，并擴(kuò)展出醫(yī)療、教育、供應(yīng)鏈、物聯(lián)網(wǎng)等非金融領(lǐng)域的應(yīng)用可能［3］。

區(qū)塊鏈的核心技術(shù)中，哈希算法保證了鏈上數(shù)據(jù)不可篡改，分布式存儲(chǔ)實(shí)現(xiàn)了去中心化，密碼學(xué)保證了電子貨幣和個(gè)人資產(chǎn)的安全，共識(shí)算法解決分布式一致性問題［4］。其中，共識(shí)算法是當(dāng)下區(qū)塊鏈研究的熱點(diǎn)。針對(duì)不同的分布式應(yīng)用場(chǎng)景，共識(shí)算法需要滿足不同的可擴(kuò)展性、共識(shí)效率、數(shù)據(jù)一致性、分區(qū)容錯(cuò)性的需求［5］。研究者基于去中心化程度，將區(qū)塊鏈分為公有鏈、私有鏈和聯(lián)盟鏈。在公有鏈中，為滿足高去中心化需求，共識(shí)算法主要以證明機(jī)制為主［6］。在私有鏈和聯(lián)盟鏈中，節(jié)點(diǎn)身份相對(duì)較為可靠［7］，因此共識(shí)算法的關(guān)注點(diǎn)在于鏈上數(shù)據(jù)的一致性和網(wǎng)絡(luò)的健壯性。目前在區(qū)塊鏈領(lǐng)域得到廣泛應(yīng)用的共識(shí)算法主要有工作量證明算法（proof of work，PoW）［1］、權(quán)益證明算法（proof of stake，PoS）［8］、委任權(quán)益證明算法（delegated proof of work，DPoS）［9］和實(shí)用拜占庭容錯(cuò)算法（practical Byzantine fault tolerance，PBFT）［10］以及基于上述幾種算法的混合算法。

2 相關(guān)工作

PBFT算法是當(dāng)前區(qū)塊鏈領(lǐng)域中解決分布式系統(tǒng)下的拜占庭將軍問題的主要算法之一，并且可以實(shí)際應(yīng)用在吞吐量較小的分布式系統(tǒng)中，比如在Hyperledger Fabric 項(xiàng)目中被采用［11］。該算法通過三個(gè)階段的節(jié)點(diǎn)通信，其中包括兩次全網(wǎng)絡(luò)的廣播通信，算法的復(fù)雜度為節(jié)點(diǎn)規(guī)模的指數(shù)級(jí)，所以隨著網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量的增長，算法的共識(shí)效率快速下降，并且通信開銷大幅增長。

針對(duì)PBFT 算法的局限性，研究人員試圖通過優(yōu)化共識(shí)流程，提高算法在大規(guī)模分布式系統(tǒng)下的表現(xiàn)。一種被普遍接受的思路是將網(wǎng)絡(luò)分組，將一個(gè)大規(guī)模問題轉(zhuǎn)化成多個(gè)并行小規(guī)模問題。文獻(xiàn)［12］提出了一種基于Raft集群的改進(jìn)PBFT算法—RBFT。文獻(xiàn)［13］提出了一種基于距離的改進(jìn)PBFT 算法—DS_PBFT。文獻(xiàn)［14］提出了一種基于通信時(shí)間分組的改進(jìn)PBFT算法—GBFT。

多數(shù)結(jié)果表明，針對(duì)大規(guī)模分布式系統(tǒng)，網(wǎng)絡(luò)分組確實(shí)能夠減小通信開銷，提高共識(shí)效率。但是網(wǎng)絡(luò)分組的解決方案隱含了一個(gè)問題，即共識(shí)階段由于參與共識(shí)的節(jié)點(diǎn)數(shù)量急劇減少所導(dǎo)致的分布式系統(tǒng)的拜占庭容錯(cuò)能力的大幅下降。拜占庭將軍問題（Byzantine failures），是由Pease 和Leslie Lamport提出的點(diǎn)對(duì)點(diǎn)通信網(wǎng)絡(luò)中的基本問題［15～16］。特別是在分組結(jié)果或分組規(guī)則被獲知的情況下，該問題的危害性會(huì)被放大，攻擊者能夠以一個(gè)更小的代價(jià)癱瘓整個(gè)分布式系統(tǒng)。

本文測(cè)試了基于網(wǎng)絡(luò)分組的兩階段PBFT 算法，采用固定網(wǎng)絡(luò)分組的方式模擬網(wǎng)絡(luò)分組結(jié)果被攻擊者獲知的情況。模擬結(jié)果表示，在最壞情況下，攻擊者針對(duì)性地使其中的兩個(gè)節(jié)點(diǎn)下線便可以癱瘓共識(shí)網(wǎng)絡(luò)，而PBFT 算法該網(wǎng)絡(luò)規(guī)模下應(yīng)該能夠提供四個(gè)拜占庭節(jié)點(diǎn)的容錯(cuò)能力，可以看出分組結(jié)果被獲知或是被預(yù)測(cè)將帶來極大的安全隱患。

為解決上述問題，分組算法應(yīng)具備抗預(yù)測(cè)能力，主要通過以下特性實(shí)現(xiàn)：

1）隨機(jī)性，分組算法中引入隨機(jī)數(shù)或隨機(jī)性算法。

2）不相干性，分組結(jié)果相互獨(dú)立，多次分組之間互不影響。

3）局部性，只有少部分節(jié)點(diǎn)知道全網(wǎng)分組結(jié)果，大部分節(jié)點(diǎn)只知道局部分組結(jié)果。

基于上述思考，本文提出了一種抗預(yù)測(cè)分組算法，并證明該算法具備上述特性。本文將該分組算法結(jié)合前文的兩階段PBFT 改進(jìn)算法，實(shí)現(xiàn)了一種基于抗預(yù)測(cè)分組的PBFT 改進(jìn)算法—RS-PBFT 算法。仿真實(shí)驗(yàn)結(jié)果表示，該算法在具有比PBFT 算法更高的共識(shí)效率和吞吐量的同時(shí)極大程度地保留了PBFT算法的拜占庭容錯(cuò)能力。

3 RS-PBFT算法模型

3.1 抗預(yù)測(cè)分組算法

基于該算法需要具備局部性的考慮，抗預(yù)測(cè)分組算法的思路是由主節(jié)點(diǎn)進(jìn)行分組，將剩余節(jié)點(diǎn)分為小組主節(jié)點(diǎn)和共識(shí)節(jié)點(diǎn)，主節(jié)點(diǎn)告知小組主節(jié)點(diǎn)所在小組的共識(shí)節(jié)點(diǎn)成員，并提供簽名作為證明，然后由小組主節(jié)點(diǎn)向共識(shí)節(jié)點(diǎn)轉(zhuǎn)發(fā)，這樣保證了除了主節(jié)點(diǎn)以外的其余節(jié)點(diǎn)均只知道局部的分組信息。

抗預(yù)測(cè)分組算法的流程如圖1。

PBFT 算法中的主節(jié)點(diǎn)選取基于透明的規(guī)則，即當(dāng)前視圖編號(hào)對(duì)節(jié)點(diǎn)規(guī)模取模得到主節(jié)點(diǎn)的序號(hào)，這種方式在存在拜占庭節(jié)點(diǎn)的網(wǎng)絡(luò)環(huán)境下會(huì)產(chǎn)生安全隱患?？诡A(yù)測(cè)分組算法的主節(jié)點(diǎn)選取方法參考Raft算法，通過三種身份、隨機(jī)過期時(shí)間、獲取選票、心跳維持狀態(tài)等機(jī)制保證主節(jié)點(diǎn)選取具備隨機(jī)性和健壯性。

非主節(jié)點(diǎn)在收到主節(jié)點(diǎn)宣告身份之后，會(huì)生成一個(gè)分組投票地圖，為每個(gè)節(jié)點(diǎn)隨機(jī)生成一個(gè)數(shù)字，然后發(fā)送給主節(jié)點(diǎn)。主節(jié)點(diǎn)會(huì)維護(hù)一個(gè)分組投票統(tǒng)計(jì)的數(shù)據(jù)結(jié)構(gòu)用于緩存其他節(jié)點(diǎn)發(fā)來的分組投票地圖，然后接受其他節(jié)點(diǎn)的投票信息，主節(jié)點(diǎn)自身不參與投票。主節(jié)點(diǎn)在收到超過全網(wǎng)三分之二節(jié)點(diǎn)的投票信息之后會(huì)根據(jù)投票結(jié)果得出分組，并告知小組主節(jié)點(diǎn)自身小組內(nèi)的成員組成，小組主節(jié)點(diǎn)再轉(zhuǎn)發(fā)給小組內(nèi)的其他成員。

抗預(yù)測(cè)分組算法具備隨機(jī)性、不相干性和局部性。主節(jié)點(diǎn)的選舉基于隨機(jī)過期時(shí)間，每個(gè)節(jié)點(diǎn)成為主節(jié)點(diǎn)的可能性相同，選舉結(jié)果具備隨機(jī)性。主節(jié)點(diǎn)不參與分組投票，分組投票由全網(wǎng)節(jié)點(diǎn)參與，基于多個(gè)隨機(jī)數(shù)地圖加和產(chǎn)生，分組結(jié)果具備隨機(jī)性。每次分組結(jié)果僅依賴于本輪收集到的隨機(jī)數(shù)地圖，不受其他參數(shù)和環(huán)境影響，具備不相干性。除了主節(jié)點(diǎn)之外的節(jié)點(diǎn)僅知道自身分組的情況，沒有其他分組的節(jié)點(diǎn)規(guī)模和節(jié)點(diǎn)身份的信息，具備局部性。進(jìn)行多次模擬實(shí)驗(yàn)記錄分組情況，得到的結(jié)果也滿足隨機(jī)性和不相干性。

3.2 RS-PBFT算法

RS-PBFT 算法是將抗預(yù)測(cè)分組算法與兩階段PBFT 改進(jìn)算法結(jié)合，需要考慮拜占庭網(wǎng)絡(luò)中節(jié)點(diǎn)可能做出的異常行為，對(duì)抗預(yù)測(cè)分組算法的流程進(jìn)行修改。

在主節(jié)點(diǎn)選舉過程中，拜占庭節(jié)點(diǎn)可能私自設(shè)置一個(gè)極小的喚醒時(shí)間，保證自己成為主節(jié)點(diǎn)，這樣不僅能夠知道全網(wǎng)的分組結(jié)果，更給系統(tǒng)帶來極大的安全隱患。RS-PBFT 算法在主節(jié)點(diǎn)選舉階段加入水線，將選舉階段開始之后固定間隔的一個(gè)時(shí)間作為水線，對(duì)于水線時(shí)間之前的請(qǐng)求選票行為不作回應(yīng)。

在主節(jié)點(diǎn)選舉過程中，拜占庭節(jié)點(diǎn)可能偽造當(dāng)選信息欺騙其他節(jié)點(diǎn)，擾亂正常的選舉過程，形成系統(tǒng)內(nèi)部“分裂”的結(jié)果。RS-PBFT 算法在投票階段加入節(jié)點(diǎn)簽名信息，主節(jié)點(diǎn)在廣播當(dāng)選信息時(shí)需要帶上獲得的全部選票信息及節(jié)點(diǎn)的簽名信息，其他節(jié)點(diǎn)只有驗(yàn)證過該節(jié)點(diǎn)的正當(dāng)選票數(shù)量達(dá)標(biāo)才承認(rèn)其主節(jié)點(diǎn)的身份，否則不作回應(yīng)。

在分組投票過程中，拜占庭節(jié)點(diǎn)可能為自己和同謀分配一個(gè)極大值，保證自己和同謀成為小組主節(jié)點(diǎn)，多個(gè)拜占庭節(jié)點(diǎn)成為小組主節(jié)點(diǎn)會(huì)增加共識(shí)結(jié)果被操縱的可能性。RS-PBFT 算法在接受投票地圖的時(shí)候設(shè)置一個(gè)閾值，對(duì)于超過閾值的數(shù)做0處理。

在節(jié)點(diǎn)通信過程中，拜占庭節(jié)點(diǎn)可能利用歷史信息或偽造信息來混亂網(wǎng)絡(luò)的正常運(yùn)作。RS-PBFT 算法在進(jìn)行關(guān)鍵性階段的通信時(shí)，會(huì)進(jìn)行報(bào)文的摘要和簽名的驗(yàn)證，并且將通信結(jié)果寫入日志。

4 仿真與實(shí)驗(yàn)分析

下面從通信開銷、共識(shí)時(shí)延、容錯(cuò)能力三個(gè)方面對(duì)RS-PBFT 算法進(jìn)行測(cè)試分析，實(shí)驗(yàn)環(huán)境為64位Windows10 操作系統(tǒng)，8 核CPU，8GB 運(yùn)行內(nèi)存，通過多進(jìn)程加端口映射的方式模擬P2P節(jié)點(diǎn)網(wǎng)絡(luò)，測(cè)試代碼開發(fā)環(huán)境為GoLang1.15+Goland2021.2.3。

4.1 通信開銷

假設(shè)系統(tǒng)內(nèi)節(jié)點(diǎn)個(gè)數(shù)為n，PBFT 算法進(jìn)行單次共識(shí)所需要的通信次數(shù)為

假設(shè)系統(tǒng)內(nèi)分組數(shù)目為G，每個(gè)分組內(nèi)的節(jié)點(diǎn)個(gè)數(shù)為g，RS-PBFT 算法進(jìn)行單次共識(shí)所需要的通信次數(shù)為

RS-PBFT 算法進(jìn)行一次節(jié)點(diǎn)分組需要的通信次數(shù)為

當(dāng)n=13，G=3 時(shí)，RS-PBFT算法進(jìn)行單次共識(shí)所需的通信次數(shù)約為PBFT 算法的35%，進(jìn)行一次分組所需的通信次數(shù)是進(jìn)行單次共識(shí)的56%，綜合來看在通信開銷方面具備很大優(yōu)勢(shì)。并且隨著n增長，RS-PBFT 算法的通信次數(shù)的漲幅會(huì)比PBFT小。

4.2 共識(shí)時(shí)延

以PBFT算法為對(duì)照，以系統(tǒng)內(nèi)節(jié)點(diǎn)個(gè)數(shù)n=13為起點(diǎn)，每次增加4 個(gè)節(jié)點(diǎn)，通過多組實(shí)驗(yàn)進(jìn)行RS-PBFT 算法的共識(shí)時(shí)延測(cè)試，在此定義共識(shí)時(shí)延為發(fā)送請(qǐng)求到收到回復(fù)之間的間隔。測(cè)試結(jié)果如圖2所示，可以看出RS-PBFT算法的共識(shí)效率較PBFT算法有明顯提升。

圖2 RS-PBFT與PBFT共識(shí)時(shí)延對(duì)比折線圖

4.3 容錯(cuò)能力

此處測(cè)試RS-PBFT 算法在面對(duì)攻擊者隨機(jī)攻擊使節(jié)點(diǎn)下線時(shí)的抵抗能力，以系統(tǒng)內(nèi)節(jié)點(diǎn)個(gè)數(shù)n=13，G=3 為網(wǎng)絡(luò)參數(shù)，使用RS-PBFT 算法進(jìn)行多輪共識(shí)，每輪共識(shí)之前隨機(jī)使一個(gè)節(jié)點(diǎn)下線，測(cè)試指標(biāo)為不能夠完成共識(shí)的輪次。測(cè)試結(jié)果如圖3 所示。最后得到平均結(jié)果為3.952 輪，而PBFT 算法的結(jié)果為5輪，說明RS-PBFT算法較好地保留了PBFT算法的容錯(cuò)能力。

圖3 RS-PBFT容錯(cuò)能力測(cè)試折線圖

5 結(jié)語

區(qū)塊鏈共識(shí)算法中的PBFT算法由于共識(shí)流程中大量的消息廣播表現(xiàn)出通信開銷大、共識(shí)效率低下的問題。針對(duì)這一問題，研究者普遍認(rèn)可通過網(wǎng)絡(luò)分片的方式提升算法的性能。但分組會(huì)帶來拜占庭容錯(cuò)能力下降的問題，特別是在節(jié)點(diǎn)分組結(jié)果被預(yù)測(cè)的情況下，攻擊者能夠以更小的代價(jià)使網(wǎng)絡(luò)失去共識(shí)能力。本文提出具備隨機(jī)性、不相關(guān)性和局部性的抗預(yù)測(cè)分組算法，并考慮拜占庭節(jié)點(diǎn)行為做出抗拜占庭算法改進(jìn)，將其與兩階段PBFT 改進(jìn)算法結(jié)合提出RS-PBFT 算法。經(jīng)過分析和實(shí)驗(yàn)表明，RS-PBFT 算法在解決了通信開銷大和共識(shí)效率低下的問題，并且在容錯(cuò)能力上較好地保留了PBFT算法的性能。