基于改進PBFT算法防御區(qū)塊鏈中sybil攻擊的研究

賴英旭，薄尊旭，劉靜,4

（1.北京工業(yè)大學(xué)信息學(xué)部，北京 100124；2.信息保障技術(shù)重點實驗室，北京 100072；3.智能感知與自主控制教育部工程研究中心，北京 100124；4.西安電子科技大學(xué)陜西省網(wǎng)絡(luò)與系統(tǒng)安全重點實驗室，陜西 西安 710071）

1 引言

自2008年比特幣問世以來，電子加密貨幣已成為當今社會的熱點話題。作為電子加密貨幣底層支撐技術(shù)的區(qū)塊鏈也進入了大眾視野并得到了廣泛關(guān)注。目前，區(qū)塊鏈被應(yīng)用在金融、物聯(lián)網(wǎng)和貿(mào)易管理等多種場景中，這對區(qū)塊鏈的安全性提出了更高的要求，要使區(qū)塊鏈真正得到實際應(yīng)用，解決其安全性是首要條件[1]。已經(jīng)出現(xiàn)的智能合約代碼漏洞[2]、自私挖礦[3]、Eclipse攻擊[4]等安全問題對區(qū)塊鏈的存在與發(fā)展帶來了危害。

區(qū)塊鏈的網(wǎng)絡(luò)架構(gòu)一般采用點對點（P2P,peer-to-peer）網(wǎng)絡(luò)架構(gòu)，所有節(jié)點的地位都是對等的，并且以拓撲結(jié)構(gòu)相互連通，節(jié)點之間采用中繼轉(zhuǎn)發(fā)的模式進行通信[5]。由于區(qū)塊鏈采用P2P的網(wǎng)絡(luò)架構(gòu)，因此更容易遭受sybil攻擊，這種攻擊發(fā)生在惡意節(jié)點偽造多個虛假節(jié)點身份加入?yún)^(qū)塊鏈網(wǎng)絡(luò)的過程中。例如，共識節(jié)點進行投票的過程中，sybil節(jié)點為了謀取利益故意投票反對正確的共識結(jié)果，從而妨礙區(qū)塊鏈中的節(jié)點達成共識。此外，sybil攻擊也可以破壞數(shù)據(jù)的冗余機制，惡意節(jié)點通過偽造多個虛假節(jié)點，將之前需要備份到多個節(jié)點的數(shù)據(jù)備份到了同一個惡意節(jié)點，嚴重破壞了分布式存儲系統(tǒng)的安全性和可靠性。

目前，區(qū)塊鏈中的sybil攻擊通常配合Eclipse攻擊共同發(fā)起。當區(qū)塊鏈中的正常節(jié)點受到攻擊時，無論是發(fā)出的還是接收的請求信息都可能被sybil節(jié)點截獲并進行篡改，如果正常節(jié)點收到的信息是被sybil節(jié)點篡改過的，就無法進行正常的共識過程，sybil攻擊對區(qū)塊鏈技術(shù)有極大的危害。本文針對防御區(qū)塊鏈中的sybil攻擊開展研究，主要貢獻如下。

1)針對sybil攻擊的特點，在區(qū)塊鏈網(wǎng)絡(luò)中建立信譽模型來計算各共識節(jié)點的信譽值，借鑒權(quán)益證明（PoS,proof of stack）引入幣齡的概念，通過幣齡大小的關(guān)系降低了計算機進行Hash計算的難度[6]。將共識節(jié)點的信譽值與共識節(jié)點的投票權(quán)重相對應(yīng)，各節(jié)點的信譽值不同，其擁有的話語權(quán)也不同，在共識過程中各節(jié)點根據(jù)投票權(quán)重來達成共識。

2)對實用拜占庭容錯（PBFT,practical Byzantine fault tolerance）算法進行改進，根據(jù)共識節(jié)點的信譽值選出信譽值最高的當前節(jié)點作為主節(jié)點Sp。共識協(xié)議中增加了pre-commit階段，不僅保證了節(jié)點間仍能正常達成共識，而且減少了節(jié)點間通信的次數(shù)。

3)對改進的共識協(xié)議進行形式化證明，驗證共識協(xié)議的安全性，通過實驗證明改進的共識協(xié)議仍是安全的。

2 相關(guān)研究

2.1 sybil攻擊

Douceur等[7]在P2P網(wǎng)絡(luò)系統(tǒng)的應(yīng)用中提出sybil攻擊的存在，認為如果網(wǎng)絡(luò)中沒有一個集中式認證機構(gòu)，很可能會出現(xiàn)sybil攻擊?，F(xiàn)階段，大型P2P系統(tǒng)在處理遠程攻擊或者系統(tǒng)故障時，大多采用數(shù)據(jù)冗余措施來防御這些安全威脅，然而如果有一個惡意節(jié)點偽造出多個節(jié)點身份，同時對外宣稱都是正常節(jié)點，那么這個惡意節(jié)點將會破壞系統(tǒng)的數(shù)據(jù)冗余機制。

如圖1所示，sybil攻擊是指攻擊者通過創(chuàng)建多個虛假身份加入P2P網(wǎng)絡(luò)，并使用這些sybil節(jié)點來獲得不成比例的影響，從而為自身謀取不正當?shù)睦?。sybil攻擊不僅會破壞對等網(wǎng)絡(luò)中資源共享的安全性、消耗正常節(jié)點的計算資源，嚴重時甚至?xí)刂普麄€網(wǎng)絡(luò)系統(tǒng)，造成更大的危害。

圖1 sybil攻擊

當前針對sybil攻擊防御和檢測的方法主要分為4類：基于圖的方法、基于機器學(xué)習(xí)的方法、手動驗證和傳統(tǒng)防御方法[8]。其中，基于圖的方法[9-12]是利用社交網(wǎng)絡(luò)信息來識別sybil節(jié)點，但這些方法都依賴sybil節(jié)點和正常節(jié)點的連接是有限的這一假設(shè)，因此這類方法的擴展性很差。基于機器學(xué)習(xí)的方法[13-15]是從節(jié)點的行為和日志中提取特征來區(qū)分正常節(jié)點和sybil節(jié)點，但這類方法是根據(jù)已知sybil節(jié)點的行為來檢測未知sybil節(jié)點，因此sybil節(jié)點可以通過改變不利于自身的行為來輕松地逃避檢測。手動驗證的方法是給經(jīng)過人工驗證的社交網(wǎng)絡(luò)賬戶設(shè)置特別標志，擁有這樣標志的用戶發(fā)布的內(nèi)容最有可能是真實的，但這種方法不僅驗證效率低，也不適用于擁有眾多對等節(jié)點的P2P網(wǎng)絡(luò)。傳統(tǒng)防御sybil攻擊的方法是通過引入可信任的權(quán)威認證機構(gòu)來對加入網(wǎng)絡(luò)的節(jié)點進行認證，這種方法同樣不適用于沒有集中式認證機構(gòu)的分布式系統(tǒng)，并且Fabric1.0版本中采用CA（certificate authority）作為證書的頒發(fā)機構(gòu)，節(jié)點之間通信使用的公私鑰由CA提供，如果CA服務(wù)出現(xiàn)故障，那么整個系統(tǒng)都會出現(xiàn)問題，因此對于去中心化的區(qū)塊鏈系統(tǒng)來說擴展性差。

2.2 實用拜占庭容錯算法

PBFT算法由Castro和Liskov提出[16]，解決了BFT算法效率差的問題，并且算法的復(fù)雜度由指數(shù)級降為多項式級，使其可以應(yīng)用于需要處理大量事件但吞吐量不大的系統(tǒng)。PBFT作為經(jīng)典的BFT狀態(tài)機副本復(fù)制算法和基于投票的主流算法，同時保證了安全性和活性。

活性：所有客戶端都會收到針對他們請求的回復(fù)，使用弱同步假設(shè)保證在一定時間內(nèi)傳遞消息規(guī)避FLP（Fischer,Lynch,Patterson）不可能性的結(jié)果。

在PBFT算法中，共識節(jié)點發(fā)送的消息都必須由節(jié)點進行簽名，其他節(jié)點以此驗證消息的真?zhèn)?。該算法的共識過程主要分為3個階段：預(yù)準備、準備和提交。如果收到超過不同節(jié)點的同意消息，則提交的交易信息是有效的。在使用PBFT算法作為共識算法的區(qū)塊鏈網(wǎng)絡(luò)中，N個節(jié)點可以包含f個拜占庭惡意節(jié)點，其中。也就是說，N-f≥2f+1，因此PBFT算法要達成共識，需要至少2f+1個節(jié)點將共識信息添加到分布式賬本中。

由于PBFT算法是分布式系統(tǒng)中達成共識一致性的一種性能良好的解決方案，增強了分布式環(huán)境下數(shù)據(jù)和系統(tǒng)服務(wù)的可用性[17]，因此PBFT算法在區(qū)塊鏈中得到了廣泛的應(yīng)用。王海勇等[18]提出在PBFT算法中引入投票機制，以監(jiān)督生產(chǎn)節(jié)點誠實工作。Wang等[19]提出了基于信用授權(quán)的拜占庭容錯（CDBFT,credit-delegated Byzantine fault tolerance）算法，通過投票獎懲和信用評估共識過程中每個節(jié)點的行為。文獻[20]提出了一種高性能、可擴展的拜占庭容錯（HSBFT,high performance and scalable Byzantine fault tolerance）算法，在正常情況下可將算法的復(fù)雜度降到O(n)。在Fabric項目0.6版本和Honey badger[21]項目中都使用PBFT作為核心的共識算法。然而，上述研究在防御惡意節(jié)點方面作用有限，缺乏對不同參與節(jié)點分配不同話語權(quán)的考慮。

在PBFT共識算法下關(guān)于防御sybil攻擊的研究中，Alex等[22]將信譽系統(tǒng)與分布式一致性協(xié)議相結(jié)合，引入聲譽模塊ReCon放置在PBFT等各種共識協(xié)議上，對sybil攻擊有很強的抵抗能力。閔新平等[23]提出了許可鏈多中心動態(tài)共識機制，并且設(shè)計了一種多主節(jié)點的PBFT算法（MPBFT,multi primary node Byzantine fault tolerance），通過安全性分析與證明，許可鏈多中心動態(tài)共識機制可保證交易不可篡改，同時預(yù)防sybil攻擊。Zhang等[24]利用區(qū)塊鏈的不可篡改性提出了一種Hash-oriented的PBFT算法，旨在減少共識確認的時延，安全性分析表明，其能夠有效防御區(qū)塊鏈中的雙花攻擊和sybil攻擊。

2.3 信譽模型

在當前的研究工作中，P2P網(wǎng)絡(luò)中已經(jīng)實現(xiàn)了各種不同的信譽系統(tǒng)。實現(xiàn)電子商務(wù)等的信譽系統(tǒng)需要可靠的中央服務(wù)器，用來記錄用戶的歷史行為并進行信譽評級。而有些信譽系統(tǒng)則使用分布式數(shù)據(jù)庫，網(wǎng)絡(luò)中所有節(jié)點的地位都是對等的并且都能實時更新本地副本，使用這種信譽系統(tǒng)的節(jié)點只記錄與其發(fā)生信息交互的對等節(jié)點的信譽值。

Janbi等[25]提出了一種對分布式排名的信譽系統(tǒng)DRank進行結(jié)構(gòu)優(yōu)化的方法，提高了DRank的性能，但容易受惡意節(jié)點共謀攻擊的影響。Sarah等[26]對AuthenticPeer進行改進，通過防止不受信任的文件傳播來增加信譽，并減少惡意節(jié)點的集體欺騙行為。Gupta等[27]在P2P網(wǎng)絡(luò)上實現(xiàn)了集中式服務(wù)器模型，確保網(wǎng)絡(luò)中的所有節(jié)點都可以訪問最新數(shù)據(jù)且不要求網(wǎng)絡(luò)中的所有節(jié)點使用信譽服務(wù)，但該方案的前提是網(wǎng)絡(luò)中不存在惡意節(jié)點，所以未能解決惡意節(jié)點可能串通來增加其自身信譽值以便從系統(tǒng)中獲利的可能性。黃建華等[28]提出了基于信任度證明的共識機制（PoT,proof of trust），解決了權(quán)益證明機制中存在的易受賄賂攻擊、幣齡累積攻擊，以及工作量證明機制中存在的自私挖礦等問題，但是對區(qū)塊鏈中存在的sybil攻擊沒有提出很好的解決方案。

2.4 網(wǎng)絡(luò)安全協(xié)議的形式化證明與分析

在網(wǎng)絡(luò)安全協(xié)議的形式化證明與分析中，安全協(xié)議的分析方法主要包括模態(tài)邏輯技術(shù)、定理證明和模型檢測技術(shù)[29]。其中，模態(tài)邏輯技術(shù)是一種比較重要的安全協(xié)議分析方法。模態(tài)邏輯用命題假設(shè)和推理規(guī)則來表示主體對消息的知識或信仰，運用推理規(guī)則可以從已知的知識和信仰推導(dǎo)出新的知識和信仰[30]。

在總結(jié)和完善BAN（Burrows,Abadi and Needham）邏輯和其他類BAN邏輯缺點和不足的基礎(chǔ)上發(fā)展出了SVO（Syverson,Van Orschot）邏輯，它的出現(xiàn)也標志著模態(tài)邏輯在安全協(xié)議的分析方法中走向成熟。SVO邏輯不僅擁有規(guī)范的模態(tài)理論語義和極其出色的擴展能力，還建立了完備的理論模型和詳細的計算模型，消除了在理解模態(tài)邏輯形式化表達式含義的過程中可能存在的歧義，通過規(guī)范的理論語義可以更好地理解協(xié)議消息所要表達的真正含義。

3 共識算法的改進

在本文改進的PBFT算法中，通過共識節(jié)點的可信狀態(tài)選出一個信譽值最高的節(jié)點作為主節(jié)點Sp。由于在PBFT共識過程中，有2個階段需要傳輸?shù)木W(wǎng)絡(luò)消息數(shù)為O(n2)，造成了很大的網(wǎng)絡(luò)開銷，因此在改進的共識算法中增加了pre-commit階段來減少節(jié)點間通信的次數(shù)。每輪共識過程中主節(jié)點Sp會生成一個新區(qū)塊并廣播到所有的共識節(jié)點，同時參與共識的節(jié)點依據(jù)信譽模型計算節(jié)點的信譽值，依據(jù)信譽值為共識節(jié)點賦予不同的話語權(quán)。在達成共識的投票過程中，各節(jié)點擁有不同的投票權(quán)重，信譽值高的節(jié)點擁有更大的投票權(quán)重，而惡意節(jié)點由于信譽值低擁有很小的投票權(quán)重甚至沒有投票權(quán)重，因此可以杜絕惡意節(jié)點對投票結(jié)果的干擾。本文的全局變量參數(shù)如表1所示。

表1 全局變量參數(shù)

3.1 系統(tǒng)模型

本文假設(shè)在區(qū)塊鏈系統(tǒng)中有N個共識節(jié)點S={S0,S1,...,SN-1}，每輪共識過程都存在一個主節(jié)點Sp，所有共識節(jié)點把接收的事務(wù)信息先緩存到本地，同時主節(jié)點Sp將客戶端發(fā)來的有效交易事務(wù)打包到一個區(qū)塊中。如果新區(qū)塊被大多數(shù)共識節(jié)點驗證通過，則認為它是有效的，該區(qū)塊將被添加到區(qū)塊鏈中。如果沒有被大多數(shù)共識節(jié)點驗證通過，那么這個區(qū)塊被舍棄。在區(qū)塊鏈系統(tǒng)中對PBFT算法進行改進，將共識節(jié)點的投票權(quán)重與所擁有的信譽值相對應(yīng)，每個共識節(jié)點都維護更新一個共識節(jié)點信息表（CNIL,consensus node information table），如表2所示。

表2 共識節(jié)點信息

CNIL包含當前區(qū)塊鏈系統(tǒng)中與本節(jié)點進行過信息交互的鄰居節(jié)點的集合、信譽值、可信狀態(tài)以及節(jié)點的ID，其中每個節(jié)點隨機選擇鄰居節(jié)點建立連接[31]。及時更新和維護共識節(jié)點的信息列表非常重要，關(guān)系到節(jié)點的信譽值和節(jié)點擁有的不同話語權(quán)，將所有節(jié)點的信息列表的初始值設(shè)為相同值。

3.2 建立信譽模型

信譽模型用來計算每個節(jié)點的信譽值，而信譽值由共識過程中節(jié)點的行為決定。信譽模型作為共識協(xié)議的一部分，可以在每個參與共識的節(jié)點中執(zhí)行，并且信譽值是獨立計算的，可以與共識消息進行同步廣播。在改進的共識算法中，設(shè)定的信譽值R是0～1的實數(shù)，信譽值越大，可信度越高。對于系統(tǒng)新添加的共識節(jié)點，其初始信譽值都設(shè)為0.5。由于主節(jié)點和其他副本節(jié)點在共識過程中的行為不同，本文分別討論了2種情況。

3.2.1Si為主節(jié)點

對于主節(jié)點而言，在t輪共識過程中如果有新區(qū)塊產(chǎn)生，那么主節(jié)點的信譽值會增加，并且隨著共識輪次越來越多，信譽值增長的速度會越來越慢，但最大值不會超過1。如果沒有新區(qū)塊產(chǎn)生，那么主節(jié)點的信譽值會下降，下降的速度由系數(shù)x的值決定。如果主節(jié)點向其他節(jié)點發(fā)送了不同的節(jié)點信息列表，那么主節(jié)點的信譽值會降為0，并將其從當前的共識節(jié)點信息列表中刪除。設(shè)Ri(t)為區(qū)塊鏈中第t輪共識后節(jié)點Si的信譽值，則Ri(t+1)為

3.2.2Si為副本節(jié)點

對于副本節(jié)點而言，在t輪共識的過程中如果向其他節(jié)點發(fā)送了相同的信息列表并且投票結(jié)果與最終結(jié)果一致，則副本節(jié)點的信譽值會緩慢增加，但不會超過1。如果副本節(jié)點在本輪沒有參與共識過程，則其信譽值會降低，下降的速度由x的取值決定。如果副本節(jié)點參與了共識過程，但是投票結(jié)果與最終結(jié)果不一致，則其信譽值會降低，下降速度由系數(shù)y的取值決定。雖然x和y的值都決定了信譽值降低的速度，但根據(jù)節(jié)點行為的不同，需要以不同的速度來降低節(jié)點的信譽值。如果檢測到同一共識節(jié)點發(fā)送了不同的信息列表，則該節(jié)點將被視為sybil節(jié)點，其信譽值降為0，并將其從當前的共識節(jié)點信息列表中刪除，如式(2)所示。

在上述信譽模型中，所有正常參與共識的節(jié)點的信譽值都是緩慢增加的。隨著系統(tǒng)持續(xù)運行，系統(tǒng)的話語權(quán)將更多集中于正確的共識節(jié)點。此外，可以考慮在系統(tǒng)的實際應(yīng)用中加入激勵機制，正常工作的節(jié)點擁有更高的信譽值、更多的話語權(quán)，會獲得更多實質(zhì)性的獎勵。如果節(jié)點的信譽值過低，則獲得很少的獎勵，甚至?xí)⑵鋸漠斍暗墓沧R節(jié)點信息列表中刪除。

3.3 主節(jié)點更新算法

其中，S為共識節(jié)點集合；P為共識節(jié)點當選為主節(jié)點的概率；D為指數(shù)分布，在C2C（consumer to consumer）網(wǎng)絡(luò)和大多數(shù)社交網(wǎng)絡(luò)中的信譽分布都是指數(shù)分布[32]。指數(shù)分布的概率密度函數(shù)F(x)如式(4)所示。

為了保證信譽值越高的節(jié)點有越大的概率當選為主節(jié)點，根據(jù)文獻[22]中模擬實驗，當設(shè)置最小惡意節(jié)點的概率α1=0.05時，共識節(jié)點N={5 000,10 000,20 000,30 000}分別運行10 000輪后達成共識的成功率最高。本文不僅考慮共識節(jié)點的可信狀態(tài)μ，同時確保指數(shù)分布截斷在區(qū)間(0,N]，因此取μ=1,2,3分別對應(yīng)共識節(jié)點的前3種可信狀態(tài)，當共識節(jié)點的信譽值低于初始設(shè)定值0.5時，則其不在更換主節(jié)點的考慮范圍內(nèi)。共識節(jié)點的可信狀態(tài)TS=1，則μ=1時，有

也就是說，可信狀態(tài)TS=1的共識節(jié)點有95%的概率當選為主節(jié)點。依次類推，TS=2和TS=3的共識節(jié)點分別有80%和55%的概率當選為主節(jié)點。本文使用指數(shù)分布，信譽值較高的節(jié)點有較大的概率當選主節(jié)點，而信譽值較低的節(jié)點當選主節(jié)點的概率較小。如果有多個節(jié)點的信譽值相等，則優(yōu)先選擇沒有當選過的節(jié)點作為主節(jié)點。

共識節(jié)點的可信狀態(tài)由信譽值R決定，因此可將共識節(jié)點分為6種可信狀態(tài)，分別為良好節(jié)點、正常節(jié)點、初始節(jié)點、異常節(jié)點、錯誤節(jié)點和惡意節(jié)點，如表3所示。

表3 節(jié)點可信狀態(tài)

在本文設(shè)計的信譽模型中，分析了節(jié)點作為主節(jié)點和副本節(jié)點的不同行為特征的評價標準。在共識過程中，當主節(jié)點被認為是惡意節(jié)點時，其信譽值會直接降為0。這時需要在參與的共識節(jié)點中重新選舉主節(jié)點。更新主節(jié)點的基本原則是，節(jié)點的信譽值越高越容易當選主節(jié)點。主節(jié)點的更新流程如圖2所示。

圖2 主節(jié)點的更新流程

變更主節(jié)點算法的具體步驟如下。

步驟1共識過程中，當主節(jié)點的信譽值低于設(shè)定的閾值時，各副本節(jié)點需要選取當前節(jié)點中信譽值最大的節(jié)點作為主節(jié)點，副本節(jié)點向其他節(jié)點廣播primary-change消息的內(nèi)容為，其中Sm為新當選主節(jié)點的序號，Rmax為當前節(jié)點的最大信譽值，i為副本節(jié)點序號。

步驟2其他副本節(jié)點收集并計算是否有2f個不同副本節(jié)點（不包括其自身）發(fā)送更新主節(jié)點為Sm的priamry-change消息，如果是，則副本節(jié)點向Sm發(fā)送primary-change-ack消息，其內(nèi)容為，并執(zhí)行步驟3；否則直接結(jié)束。

步驟3新當選的主節(jié)點Sm向其他副本節(jié)點發(fā)送new-primary消息的內(nèi)容為，其中V為primary-change消息集合。

3.4 改進共識算法

在共識算法的改進中，通過計算各節(jié)點的信譽值為各節(jié)點分配不同的話語權(quán)。根據(jù)各共識節(jié)點提供的信息列表評估共識過程中每個節(jié)點的信譽值，不僅可以檢測出其中的惡意節(jié)點，而且可以將檢測出的惡意節(jié)點從共識節(jié)點信息表清除。良好節(jié)點的信譽值會逐漸累加，在共識過程中的話語權(quán)也逐漸增加，而惡意節(jié)點的影響會逐漸減少。共識過程中，節(jié)點i更新共識狀態(tài)的條件是向其發(fā)送消息的共識節(jié)點的信譽值總和Rv足夠大。其他節(jié)點信譽值總和Rv的計算方式如下。

假設(shè)區(qū)塊鏈網(wǎng)絡(luò)是一個有向網(wǎng)絡(luò)G(ε,E)，其中ε為n個節(jié)點集合，E為有向鏈路加權(quán)集合，可以用來預(yù)測共識節(jié)點之間協(xié)商的可能結(jié)果。

在區(qū)塊鏈網(wǎng)絡(luò)中，Rv由與其進行信息交互的節(jié)點信譽值共同決定，即節(jié)點i在t輪共識中收到的信譽值為

其中，Ri(t)為節(jié)點i在t輪共識時的信譽值，矩陣由網(wǎng)絡(luò)拓撲及鏈路上的信譽值構(gòu)成，φT為其轉(zhuǎn)置矩陣。

如果Rv受到多個共識節(jié)點的影響，那么節(jié)點i收到的信譽值就是作用于i上所有影響的總和，如式(7)所示。

狀態(tài)方程可表示為ΔR(t)=LR(t)，其中L是φT的Laplacian矩陣。因此，更新規(guī)則為

收到的其他節(jié)點Rv應(yīng)不小于設(shè)定的閾值Rthreshold，如式(9)所示。

改進的PBFT算法共有6個階段，其中最主要是以下4個階段：預(yù)準備、準備、預(yù)提交和提交。改進的PBFT算法中引入了信譽模型，通過各節(jié)點共識過程中的行為對節(jié)點進行信譽評估，檢測區(qū)塊鏈中的sybil節(jié)點，工作流程如圖3所示，具體步驟如算法1所示。

算法1改進PBFT算法

輸入交易tx

輸出共識結(jié)果

1)客戶端c發(fā)起交易tx，并將交易廣播到主節(jié)點0。主節(jié)點0收到發(fā)送的交易tx，首先驗證tx是否有效，若無效直接將其刪除；若有效則將tx打包到區(qū)塊中，并根據(jù)區(qū)塊體內(nèi)的信息生成區(qū)塊頭Bhead。

2)主節(jié)點0廣播預(yù)準備（pre-prepare）消息到各副本節(jié)點，內(nèi)容為

圖3 改進PBFT算法工作流程

其中，h是當前新區(qū)塊的高度，d是區(qū)塊頭Bhead的摘要，t是當前的時間戳，P0是當前主節(jié)點0的ID，CNIL0是主節(jié)點0的共識節(jié)點信息表。

3)副本節(jié)點1,2收到主節(jié)點0發(fā)送的預(yù)準備消息，首先驗證新區(qū)塊的有效性，驗證通過則分別向其他節(jié)點發(fā)送prepare消息，內(nèi)容為

4)副本節(jié)點1,2收到其他副本節(jié)點發(fā)送的prepare消息，發(fā)送消息的節(jié)點擁有不同的信譽值。首先副本節(jié)點計算當前向其發(fā)送消息的節(jié)點的Rv，如果Rv≥Rthershold則在本地更新交易信息的共識狀態(tài)并發(fā)送pre-commit信息，內(nèi)容為

5)主節(jié)點0將收到的副本節(jié)點發(fā)送的pre-commit信息進行比較，根據(jù)信譽模型計算當前每個節(jié)點的信譽值，更新本地的共識節(jié)點信息列表，同時將共識結(jié)果反饋給客戶端和所有的副本節(jié)點，發(fā)送commit消息，內(nèi)容為

6)完成提交狀態(tài)后，區(qū)塊鏈中的副本節(jié)點更新本地的共識節(jié)點信息表，并將共識結(jié)果反饋給客戶端，準備下一輪的共識過程。

在節(jié)點進行共識過程的不同階段需要分別驗證交易和新區(qū)塊的有效性，驗證的主要內(nèi)容如下。

1)驗證交易的有效性

在進行共識的預(yù)準備階段，主節(jié)點需要驗證收到客戶端發(fā)送的交易tx的有效性。驗證tx的格式是否正確和時間戳是否有效，驗證事務(wù)中的腳本是否可以正確的執(zhí)行，如果通過驗證則tx是有效的。

2)驗證新區(qū)塊的有效性

當副本節(jié)點收到主節(jié)點生成的新區(qū)塊時，需要驗證新區(qū)塊的有效性。驗證區(qū)塊頭中的Merkle根是否正確和區(qū)塊頭中是否引用前一區(qū)塊的哈希值，同時驗證區(qū)塊中的交易是否有效，如果通過驗證則新區(qū)塊則是有效的。

4 共識協(xié)議的形式化分析驗證

共識協(xié)議的形式化分析驗證主要分為共識協(xié)議的安全性分析和對協(xié)議的安全性測試。

4.1 共識協(xié)議的安全性分析

共識協(xié)議的安全性分析主要分為共識協(xié)議的理想化描述、初始化假設(shè)、設(shè)定安全目標和對協(xié)議進行理論分析4個部分。

4.1.1共識協(xié)議的理想化描述

使用SVO邏輯對改進的PBFT算法的共識協(xié)議進行安全分析。首先需要對該協(xié)議的工作流程進行符合SVO邏輯的理想化描述。描述結(jié)果如下。

1)客戶端c向主節(jié)點0發(fā)送交易tx，交易信息中帶有時間戳和客戶端標識。

2)主節(jié)點0對tx進行驗證，驗證通過后向其他副本節(jié)點發(fā)送帶有自己簽名的預(yù)準備消息，該消息中包含當前區(qū)塊的高度、區(qū)塊頭的哈希摘要、主節(jié)點的ID以及共識節(jié)點信息表。

3)副本節(jié)點1,2,3收到預(yù)準備消息驗證之后向其他節(jié)點發(fā)送各自簽名的準備消息，將接收到的其他共識節(jié)點信息表存儲到本地。

4)各共識節(jié)點收集其他節(jié)點的準備消息，如果Rv≥Rthershold，則在本地更新交易信息的共識狀態(tài)，并發(fā)送pre-commit信息。

5)主節(jié)點和各副本節(jié)點向客戶端c發(fā)送響應(yīng)消息，將達成的共識結(jié)果返回給客戶端。

4.1.2協(xié)議的初始化假設(shè)

使用SVO邏輯對共識協(xié)議進行推理分析的過程中，首先進行初始假設(shè)，即定義共識協(xié)議中每個節(jié)點在初始時刻擁有的知識和信仰。初始化假設(shè)是進行推理證明的第一步，根據(jù)共識協(xié)議流程，設(shè)定如下假設(shè)。

1)關(guān)于密鑰的有效性

2)關(guān)于信息的發(fā)送

客戶端c向主節(jié)點0發(fā)送交易tx，并驗證交易的格式和時間戳，以及事務(wù)的腳本能否正常執(zhí)行，驗證通過后向副本節(jié)點發(fā)送信息

副本節(jié)點收到主節(jié)點0發(fā)送的信息，驗證新生成區(qū)塊的Merkel根和指向前一區(qū)塊的哈希值，驗證通過后向其他節(jié)點發(fā)送消息

3)關(guān)于信息的接收

各共識節(jié)點收集其他節(jié)點的準備消息，如果Rv≥Rthershold，則在本地更新交易信息的共識狀態(tài)。

主節(jié)點0收到的信息為

副本節(jié)點1收到的信息為

副本節(jié)點2收到的信息為

副本節(jié)點3收到的信息為

4)關(guān)于信息的新鮮性

4.1.3協(xié)議的安全目標

由于改進的PBFT算法中加入了共識節(jié)點信息表，每輪共識之后都要根據(jù)各節(jié)點的行為計算信譽值并且更新CNIL。因此共識協(xié)議需要達到的安全目標主要是各節(jié)點的能否收到其他節(jié)點發(fā)送的CNIL，同時保證客戶端發(fā)送的請求能夠達成共識。共識協(xié)議的安全目標用SVO邏輯語言表達如下。

首先，確保每個節(jié)點都能收到其他節(jié)點發(fā)送的共識節(jié)點信息表。

其次，確保每個節(jié)點都能收到客戶端發(fā)送的請求

4.1.4協(xié)議分析

根據(jù)初始化假設(shè)，使用SVO邏輯對共識協(xié)議進行邏輯推理，驗證共識協(xié)議是否達到預(yù)先設(shè)定的安全目標，以此分析共識協(xié)議的安全性。共識協(xié)議的分析過程如下。

由假設(shè)c:N1?(h,d,P0,CNIL0)和接收公理，可得

同理，可得

由假設(shè)c:N1? (h,d,P0,CNIL0) 和接收公理，可得

同理，可得

綜合上述分析，可得

4.2 協(xié)議的安全性測試

4.2.1測試工具

AVISPA（automated validation of internet security protocols and application）是自動驗證網(wǎng)絡(luò)協(xié)議和應(yīng)用程序是否安全的模型工具，其融合了4種不同的分析組件：動態(tài)模型檢驗器（OFMC,on-the-fly model-checker）、基于邏輯約束的攻擊搜索器（CL-AtSe,constraint-logic-based attack searcher）、基于SAT的模型檢驗器（SATMC,SAT-based model-checker）和基于自動逼近的樹自動機安全協(xié)議分析（TA4SP,tree automata based on automatic approximations for analysis of security protocol）[33]。

AVISPA工具提供了一種模塊化和富有表現(xiàn)力的高級協(xié)議規(guī)范語言HLPSL（high-level protocol specification language），用于指定安全問題和數(shù)據(jù)結(jié)構(gòu)。其集成了多種不同的檢測后端，能夠自動進行各種分析技術(shù)，從協(xié)議偽造（通過發(fā)現(xiàn)輸入?yún)f(xié)議的攻擊）到有限和無限數(shù)量會話的基于抽象的驗證方法[34]。其架構(gòu)如圖4所示。

圖4 AVISPA 架構(gòu)

4.2.2基本角色

在共識協(xié)議中分別為每個參與者定義一個角色，即客戶端c、主節(jié)點N0、副本節(jié)點N1,N2,N3的角色，如表4所示。

4.2.3會話場景

本文根據(jù)改進的PBFT算法定義了3種會話場景來驗證共識協(xié)議是否符合安全目標，如表5所示。場景1為正常的會話過程，其中包含所有合法的場景；場景2中主節(jié)點為sybil節(jié)點；場景3中副本節(jié)點為sybil節(jié)點。

4.2.4安全目標

為了評估改進的PBFT算法共識協(xié)議的安全性，首先要明確協(xié)議需要達到的安全目標。AVISPA工具中提供了不同的關(guān)鍵字表示安全目標。在本文的安全性測試中，用關(guān)鍵字描述如下。

1)共識過程中的請求信息Q是由客戶端C產(chǎn)生的，并且將此信息廣播給主節(jié)點N0。

其中，t是安全目標中的標識符。

2)關(guān)鍵字request聲明副本節(jié)點N{1,2,3}收到了主節(jié)點N0發(fā)送的共識信息Q，關(guān)鍵字witness聲明主節(jié)點N0向副本節(jié)點N{1,2,3}發(fā)送了共識信息Q。

為了對共識協(xié)議的安全性進行測試，本文定義了如下安全目標。

1)在共識協(xié)議中，主節(jié)點N0驗證客戶端C發(fā)送的請求信息的有效性，確保請求信息的交易格式和時間戳有效。其他副本節(jié)點N{1,2,3}需要驗證主節(jié)點生成的新區(qū)塊的有效性，驗證區(qū)塊頭中的Merkel根是否正確，以及區(qū)塊頭是否引用前一區(qū)塊的哈希值，以此判斷主節(jié)點是否是sybil節(jié)點。用HLSPL描述如下。

2)在共識協(xié)議中，每一輪共識之后各節(jié)點之間需要同步共識節(jié)點信息表，防止sybil節(jié)點篡改共識信息，干擾正常的共識，保證各節(jié)點的信譽值能夠同步進行更新。用HLSPL描述如下。

4.2.5實驗結(jié)果

在AVISPA中使用OFMC和CL-AtSe分析工具對改進PBFT算法的共識協(xié)議進行分析，實驗結(jié)果如圖5所示。

由圖5可知，使用OFMC和CL-AtSe分析組件對改進PBFT算法的共識協(xié)議的分析結(jié)果是安全的，即SUMMARY:SAFE，并且沒有發(fā)現(xiàn)協(xié)議中存在缺陷。因為如果檢測到協(xié)議中有缺陷，SUMMARY字段會顯示UNSAFE，而DETAILS字段會提示ATTACK_FOUND。

在分析過程中，改進PBFT算法的共識協(xié)議由HLPSL的高級協(xié)議規(guī)范語言轉(zhuǎn)換為IF語言形式，保存在PROTOCOL字段給出的路徑中，其文件名為hlpslGenFile.if。圖5中的BACKEND字段顯示實驗所用的分析工具的類型，STATISTICS字段顯示分析工具所運行的時間以及搜索的節(jié)點數(shù)。

表4 基本角色定義

表5 會話場景定義

圖5 測試結(jié)果摘要

5 改進PBFT算法的性能分析與評估

本文實現(xiàn)了一個簡單的區(qū)塊鏈系統(tǒng)，主要包括共識模塊和生成區(qū)塊模塊兩部分。其中，共識模塊將達成共識的信息發(fā)送給生成區(qū)塊模塊，從而生成包含交易信息的區(qū)塊鏈。共識模塊中分別包含不同的共識算法，即PBFT和改進的PBFT，來驗證交易、生成和提交新塊。本文實驗在平臺上模擬不同的共識節(jié)點進行共識的過程。實驗平臺參數(shù)如下：Intel Core i5-8265U，2.60 GHz，8 GB RAM。

從3個方面來評估改進PBFT算法的性能，分別為事務(wù)吞吐量、時延和算法的時間復(fù)雜度。本文實驗設(shè)計的共識節(jié)點數(shù)量分別為4、7、10、13和16，統(tǒng)計的塊生成周期分別為3 s、6 s、9 s、12 s、15 s和18 s。當系統(tǒng)運行穩(wěn)定時，統(tǒng)計區(qū)塊鏈系統(tǒng)的TPS（transaction per second）和生成區(qū)塊的時延。

5.1 TPS的比較

在區(qū)塊鏈系統(tǒng)中，TPS是指系統(tǒng)每秒鐘能夠處理的事務(wù)數(shù)量。TPS的大小直接反映了系統(tǒng)處理能力的高低。

實驗中分別設(shè)定不同數(shù)量的共識節(jié)點，不斷向區(qū)塊鏈系統(tǒng)中發(fā)送交易，待系統(tǒng)穩(wěn)定后，每隔3 s統(tǒng)計一次區(qū)塊鏈系統(tǒng)處理的交易數(shù)量，然后進行計算。圖6對比了相同的實驗平臺下，PBFT算法和改進的PBFT算法在不同數(shù)量共識節(jié)點下的TPS。

由圖6可知，當系統(tǒng)運行時間為12 s和18 s時，系統(tǒng)中的TPS基本保持在同一水平。當運行時間為15 s時，改進的PBFT算法的TPS達到最高，平均值約為3 850，PBFT算法的TPS平均值約為2 760，改進的PBFT算法的TPS提高了40%左右。與PBFT算法相比，改進的PBFT算法的TPS全面提高，并且隨著共識節(jié)點數(shù)量的增多，TPS下降的速度也在放緩。

5.2 生成區(qū)塊時延的比較

生成區(qū)塊的時延Tdelay是指區(qū)塊從生成到經(jīng)過共識算法得到節(jié)點確認的過程。時延越短表示共識算法的執(zhí)行時間越短，共識的效率也就越高。區(qū)塊時延包括共識算法的執(zhí)行時間Tconsensus、信息的廣播時間Tbroadcast、區(qū)塊中交易的打包時間Tpackage和區(qū)塊的確認時間Tconfirm。

圖6 2種算法不同數(shù)量共識節(jié)點的TPS對比

區(qū)塊時延主要由Tconsensus和Tbroadcast組成，而Tpackage和Tconfirm可以忽略。在相同的實驗平臺下，本節(jié)分別統(tǒng)計了PBFT算法和改進的PBFT算法在不同數(shù)量共識節(jié)點下生成區(qū)塊的時延，如圖7所示。

由圖7可知，改進的PBFT算法中共識節(jié)點生成區(qū)塊的時延比PBFT算法整體上減少了10 ms左右，并且隨著共識節(jié)點數(shù)量的增多，共識節(jié)點生成區(qū)塊的時延減少的效果更加明顯，尤其在運行時間為15 s時，生成區(qū)塊的時延減少最多。以上數(shù)據(jù)說明改進的PBFT算法在減少生成區(qū)塊的時延方面也有很大的提升。

5.3 時間復(fù)雜度的比較

在PBFT算法的3個主要階段中，在預(yù)準備階段主節(jié)點廣播pre-prepare消息給其他副本節(jié)點，通信次數(shù)為(n-1)；在準備階段，每個節(jié)點向其他節(jié)點廣播parepare消息，總的通信次數(shù)為n(n-1)；在提交階段，每個節(jié)點向其他節(jié)點廣播commit消息，通信次數(shù)也為n(n-1)。PBFT算法總通信次數(shù)為(2n2-n-1)，時間復(fù)雜度為O(n2)。

改進的PBFT算法在節(jié)點進行共識的過程中加入了對節(jié)點信譽值的計算，并且增加了pre-commit階段，因此改進PBFT算法的總通信次數(shù)為(n2+2n-3)。雖然改進算法的時間復(fù)雜度仍維持在O(n2)，但減少了節(jié)點間通信的次數(shù)。

6 結(jié)束語

圖7 2種算法不同數(shù)量共識節(jié)點生成區(qū)塊的時延對比

本文說明了sybil攻擊對區(qū)塊鏈的危害，分析了各種防御sybil攻擊的方案的不足。本文提出了一種能有效防御區(qū)塊鏈中sybil攻擊的方法，借鑒基于權(quán)益證明的共識思想在PBFT算法中加入信譽模型，將共識節(jié)點的投票權(quán)重與所擁有的信譽值相對應(yīng)，根據(jù)共識節(jié)點的信譽值為節(jié)點分配不同的權(quán)重，在達成共識的投票過程中，不同節(jié)點擁有不同的投票權(quán)重。通過對PBFT算法進行改進，根據(jù)共識節(jié)點的可信狀態(tài)選擇當前信譽值最高的節(jié)點作為主節(jié)點，同時在共識協(xié)議的過程中加入pre-commit階段來減少節(jié)點間通信的次數(shù)。

通過設(shè)計的一個簡單區(qū)塊鏈系統(tǒng)開展實驗，將改進的PBFT算法與原PBFT算法在TPS、生成區(qū)塊的時延和算法復(fù)雜度3個方面進行了對比，得出的主要結(jié)論如下。

1)改進的PBFT算法在系統(tǒng)運行時間為15 s時，TPS提高最多，整體上提高了40%左右，并且隨著共識節(jié)點數(shù)量的增多，TPS下降的速度也在放緩。

2)改進的PBFT算法在共識節(jié)點數(shù)量為4、統(tǒng)計時間為15 s時生成區(qū)塊的時延減少最多，相比PBFT算法生成區(qū)塊的時延整體上減少了約10 ms。

3)改進的PBFT算法增加了pre-commit階段，雖然時間復(fù)雜度仍維持在O(n2)，但減少了節(jié)點間通信的次數(shù)。

本文對改進的PBFT算法共識協(xié)議的安全性進行了形式化證明，通過理論推導(dǎo)以及實驗證明改進的共識協(xié)議在通信過程中仍然是安全的。

本文方案不僅可以有效地防御區(qū)塊鏈中的sybil攻擊，而且使區(qū)塊鏈的TPS和生成區(qū)塊的時延的性能全面提升，因此本文方案可以滿足大多數(shù)區(qū)塊鏈系統(tǒng)的性能要求，同時可以保證系統(tǒng)的安全和性能的穩(wěn)定。接下來的工作重點是進一步優(yōu)化PBFT算法，降低PBFT算法的時間復(fù)雜度，在保證達成共識一致性的前提下減少節(jié)點間通信的次數(shù)。