基于改進的PBFT 算法的性能模型研究?

儲勁松 鮑可進 夏純中

（江蘇大學計算機科學與通信工程學院 鎮(zhèn)江 212001）

1 引言

比特幣［1～2］密碼貨幣［3］的成功使人們對區(qū)塊鏈技術越來越感興趣，通過使用區(qū)塊鏈［4］中分布式賬本［5］來完成交易可以解決一些現(xiàn)實難以解決的問題。區(qū)塊鏈是一個加密的分布式數(shù)據(jù)庫交易系統(tǒng)，所有對等網(wǎng)絡節(jié)點以分散，可信和安全的方式共享信息。在本論文中，我們使用Hyperledger Fabric［6］的1.0的版本作為實驗平臺，由IBM、DAH等企業(yè)于2015 年底提交到社區(qū)，它是一個開源的面向企業(yè)的分布式賬本平臺［7］，用于在模塊化體系結(jié)構中運行智能合約，創(chuàng)新地引入了權限管理支持，支持可插拔、可擴展的共識機制。

在像比特幣這樣的基于POW 和POS 共識機制的公共區(qū)塊鏈網(wǎng)絡中，任何人和機構都可以加入該網(wǎng)絡，這會導致系統(tǒng)網(wǎng)絡遭到Sybil攻擊［8］的風險變大。比特幣網(wǎng)絡解決這個問題的方法是，讓同等節(jié)點使用工作量證明機制（PoW）的共識方法提出新的交易區(qū)塊，但是這種共識方法的缺點是會消耗特別大的算力資源。雖然加密貨幣是一個很吸引人的區(qū)塊鏈應用項目，但是令人擔憂的是其性能問題，比特幣系統(tǒng)每次確認交易時間往往將達到10分鐘或更久，而且僅能實現(xiàn)每秒7 個交易［9］的最大吞吐量（即7TPS）。在私有區(qū)塊鏈網(wǎng)絡中，所有參與者節(jié)點都被列入白名單，并受到嚴格合約義務的約束，在表面上所有節(jié)點都表示為安全節(jié)點，為了避免受到惡意節(jié)點的攻擊，需要選擇使用更有效的共識協(xié)議，如拜占庭容錯［10］共識機制（PBFT）。PBFT［11］的工作原理是假設只有不到三分之一的節(jié)點出現(xiàn)故障（記故障節(jié)點數(shù)為f），這意味著網(wǎng)絡中應該至少包含n=3f+1 個節(jié)點，以容忍f 個惡意節(jié)點。因此f=（n-1）/3。使用PBFT 共識機制的網(wǎng)絡需要至少2f+1個節(jié)點達成一致才能完成新區(qū)塊的創(chuàng)建，這就保證了生成的新交易區(qū)塊為正確節(jié)點所創(chuàng)建。

圖1 區(qū)塊鏈網(wǎng)絡交易共識圖

圖1 顯示了一個私有區(qū)塊鏈網(wǎng)絡的高級視圖。每個參與機構都是一個對等節(jié)點（VP），在進行共識之前會隨機選擇一個節(jié)點作為領導者（Leader）。進行交易的客戶向他們各自所屬機構的VP 提出交易請求，VP 確認交易后將其通過廣播的形式傳播給其他VP。幾秒鐘后（定義為批處理超時）或交易達到一定數(shù)量（定義為批處理大?。┲?，Leader 節(jié)點創(chuàng)建一個待處理事務的區(qū)塊，按交易提交的時間對交易進行排序，利用時間戳維護交易秩序。然后它向其他副本節(jié)點廣播這個可執(zhí)行的區(qū)塊，以使用PBFT 獲得關于該塊的共識結(jié)果。如果2f+1 個對等節(jié)點同意該區(qū)塊的創(chuàng)建，則每個VP 執(zhí)行所有交易并將該塊附加為其私人分類賬上的下一個區(qū)塊。每個區(qū)塊都有一個HASH 地址［12］，每一個新區(qū)塊的地址都是包含前一區(qū)塊地址的HASH 進行連接而成，形成一個鏈，從而稱為區(qū)塊鏈。

2 視圖切換協(xié)議

PBFT算法在主節(jié)點發(fā)生故障的時候就需要更換主節(jié)點，改變視圖，這個協(xié)議就稱為視圖切換協(xié)議［13］。PBFT 共識算法機制中詳細地介紹了更換視圖，改變主節(jié)點的過程。整個系統(tǒng)不會在視圖切換的過程發(fā)生不一致的現(xiàn)象，因此這個過程同樣地也需要進行所有節(jié)點間的通信。本文采用的視圖切換協(xié)議，采用對區(qū)塊鏈最優(yōu)區(qū)塊監(jiān)聽的方式判斷主節(jié)點是否發(fā)生故障，當滿足添加區(qū)塊的條件下，節(jié)點沒有進行區(qū)塊的添加則認為主節(jié)點發(fā)生故障，此時需要進行視圖切換。具體算法如下：

算法1 ViewChange（）

Input：該節(jié)點維護的區(qū)塊鏈和交易列表

Output：是否進行視圖切換

1：time←CurrentTime

2：Repeat

3： if 交易列表不為空then

4： if BestBlock 的交易信息為空then

5： if CurrentTime-time 大于t then

6： ChangeView

7： else

8： time←BestBlock 的時間戳

9： if CurrentTime-time 大于t then 10：ChangeView

11： else

12： if BestBlock 的交易信息為空then

13： if 下一個區(qū)塊交易信息為空

14： ViewChange

15： else

16： Thread．Sleep（t）

17： time←CurrentTime

18： else

19： time←BestBlock 的時間戳

20： if CurrentTime-time 大于t then

21： ChangeView

22：Until ViewChange

視圖切換的同時會清除證書列表，完成提交交易的操作交由新的主節(jié)點進行，并持續(xù)地維持系統(tǒng)的穩(wěn)定運行。上述算法中，在主節(jié)點發(fā)生故障時，系統(tǒng)會在一定時間內(nèi)完成視圖的切換。這對以普通的分布式系統(tǒng)可能會造成服務中斷的問題。而對于基于PBFT 共識算法的聯(lián)盟鏈［14］環(huán)境，服務并不會停止。其他節(jié)點可以將交易存入交易列表中，并由其他節(jié)點各自維護的本地數(shù)據(jù)提供服務。整個視圖切換過程在區(qū)塊鏈可容忍的延遲的范圍，完成主節(jié)點的切換，避免了節(jié)點間通信，減少了通信的消耗。

3 PBFT共識過程性能模型

本文，針對改進視圖切換協(xié)議的PBFT算法，利用隨機回報網(wǎng)［15］（SRN），通過捕捉三個最耗時的步驟對PBFT完成共識一致過程的“平均完成時間”進行建模。這三段時間分別為：對等節(jié)點之間消息傳輸?shù)臅r間T1（即圖中下標為TC 的時間），節(jié)點處理傳入的一致消息的時間T2（即圖中下標DW 的時間），以及為下一個傳輸階段準備一致消息的時間T3（即圖中下標為RD 的時間）。在這個模型中我們作出以下假設：

1）在生成區(qū)塊的事務開始之前已經(jīng)選擇了一個主節(jié)點，并且在單個塊的三階段共識協(xié)議執(zhí)行過程中，它不會改變；

2）每個副節(jié)點的消息處理速率都是一樣的；

3）所有對等節(jié)點之間的消息傳輸速率是相同的；

4）在生成單個區(qū)塊的三階段共識協(xié)議執(zhí)行過程中，每一個節(jié)點在任何時候都不會失敗。

圖2 四個節(jié)點工程過程模型圖

在圖2 中的四節(jié)點的共識過程的性能模型中，使用令牌的形式控制每一個階段的進行；從主節(jié)點已經(jīng)準備新的信息區(qū)塊開始到三階段的共識協(xié)議完成，所有節(jié)點同意該區(qū)塊的生成。主節(jié)點分別用數(shù)字0和其他VP 作分別，其他節(jié)點編號分別為1、2和3。該模型直觀地顯示了PBFT 共識協(xié)議的三階段的每一個步驟，易于跟蹤。

對于這個模型有以下約束函數(shù)，見表1。

表1 性能模型約束函數(shù)表

4 實驗分析

實驗硬件采用4核8線程的Intel（R）Core（TM）i7-4870HQ 處理器，16 GB 內(nèi)存的硬件平臺。虛擬機8 臺，1GB 內(nèi)存，CPU 共享主機的一個處理器核心，網(wǎng)絡連接100Mbit/s LAN。采用50 臺虛擬機從4 個節(jié)點依次到50 個節(jié)點搭建了基于改進PBFT共識機制的區(qū)塊鏈網(wǎng)絡，這里認為50 臺機器的算力是相同的，運行IBM Watson 團隊開發(fā)的IoT 應用程序。連續(xù)運行一周，每小時大約有700 個區(qū)塊提交，我們從中隨機選擇50 個區(qū)塊的日志進行分析。對于這個模型來說，在指定的地方存放令牌的總時間相當于完成創(chuàng)建一個區(qū)塊的一致性共識的時間。程序運行了接近500 次程序，計算平均時間作為我們的結(jié)果，平均時間為4.45ms。由于實驗結(jié)果中存在異常值，將這個模型估計的平均共識時間與中位數(shù)時間進行比較，中位數(shù)時間為4.872ms，相對誤差約為8.7%，結(jié)果具有可比性，模型得到了驗證。由于我們的模型檢驗的是改進PBFT算法的性能，不考慮故障節(jié)點的情況即不考慮發(fā)生拜占庭容錯的情況。

我們對節(jié)點數(shù)n的生成模型，其中n=4，7，10的故障節(jié)點個數(shù)分別用f=1，2，3，直到n=49，f =16。我們利用實驗驗證的參數(shù)對模型進行了評估。如圖3所示在最多10個網(wǎng)絡節(jié)點的網(wǎng)絡中，我們發(fā)現(xiàn)平均共識的時間隨著n 的增加而增加，在n=7 時增加的斜率減小。因為每個對等節(jié)點在準備階段和提交階段都需要2f+1 個一致性消息。在提交驗證階段，n=4 的時候，達成協(xié)商一致所需的正確節(jié)點的數(shù)量是3個，正確節(jié)點的比例為75%，到n=7的時候正確節(jié)點個數(shù)需要5 個，正確節(jié)點的比例為71.42%；以此類推最后接近三分二也就是66.667%。但在n=10后，平均共識時間增長的斜率又開始增大。這是由于準備階段和提交階段中消息隊列延遲隨著節(jié)點數(shù)增加而增加所導致。曲線繼續(xù)隨著n 的增加，略有皺折。最后，n=50 的平均協(xié)商時間是n=4的2.14倍。

圖3 完成共識平均時間結(jié)果圖

在網(wǎng)絡節(jié)點設置中，各個節(jié)點位于同一機架中。我們考慮一個現(xiàn)實場景，某一節(jié)點位于機架中心的區(qū)域或者邊角區(qū)域，發(fā)送消息的平均時間要大得多。對網(wǎng)絡節(jié)點間假設在所有對等節(jié)點之間傳輸消息的平均時間是5.5ms。我們會發(fā)現(xiàn)類似的平均時間的走向圖，然而，在n=34 的共識時間比n=4的共識時間增長了23%，而此時相對于0.75ms的平均傳輸消息的時間，平均共識時間增長了134%，但是對于平均延遲更大的網(wǎng)絡，這一百分比不會繼續(xù)增大。因此，如果傳輸延遲比處理排隊消息的時間大一個或兩個數(shù)量級，平均共識一致的時間不會隨著n的增加而顯著增加。

由上可知，模型可以根據(jù)不同的系統(tǒng)配置和參數(shù)來估計性能指標，并對潛在的性能瓶頸提供早期反饋。在正在進行的工作中，我們將在對更多的對等節(jié)點以及更廣泛更高效的PBFT共識算法的參數(shù)和系統(tǒng)配置進行驗證。

5 結(jié)語

本文針對改進的PBFT 算法進行系統(tǒng)建模，基于IBM 公司的hyperledger composer 平臺搭建運行環(huán)境，并運行IBM Watson 團隊開發(fā)的IoT 應用程序測試了改進的PBFT 算法的性能，驗證出改進的PBFT 算法能夠在至少50 個網(wǎng)絡節(jié)點的區(qū)塊鏈網(wǎng)絡中安全有效地進行共識工作；分析其性能影響。后續(xù)我們還準備對PBFT 算法進一步的改進，因為三階段的共識會耗費巨大的網(wǎng)絡開銷，影響系統(tǒng)的吞吐量，針對這一問題的改進，依然可以嘗試利用本文對算法建立性能模型的方式對算法進行進一步的性能測試。然后繼續(xù)增加網(wǎng)絡的節(jié)點，對更大規(guī)模的網(wǎng)絡進行模型測試。