黃秋波 安慶文 蘇厚勤
(東華大學計算機科學與技術學院 上海 201620)
一種改進PBFT算法作為以太坊共識機制的研究與實現
黃秋波 安慶文 蘇厚勤
(東華大學計算機科學與技術學院 上海 201620)
針對以太坊中PoW(Proof of Work)共識機制在聯盟鏈場景下表現出的由于算力競爭造成的資源浪費和不可靠問題,提出了采用PBFT(Practical Byzantine Fault Tolerance)算法作為以太坊共識機制,并結合以太坊結構對PBFT算法進行改進。改進PBFT算法中,檢查點協議取消了定時檢查清除證書的過程,節點同步過程采用向其他節點索要區塊并校驗的方式完成同步;視圖切換協議在結合區塊生成協議的基礎上,采用超時機制進行視圖切換。實驗結果說明采用改進PBFT的以太坊適用于聯盟鏈場景中,可以在很大程度上減少算力開銷,并在一定程度上減少網絡上的數據傳輸量。
以太坊 共識機制 PBFT 聯盟鏈
近些年來,互聯網貿易越來越普及,給人們帶來極大便利,然而這個過程需要一個可信任的第三方去保證交易的執行。2009年中本聰[1]首次提出了區塊鏈這一概念。區塊鏈的產生實現了真正意義上的去中心化可信任交易系統。
區塊鏈的本質是分布式系統,該系統具有去中心化與安全可信的特點。早期的區塊鏈技術是借助虛擬電子貨幣實現去中心化的支付系統,在利用數字加密技術實現點對點的交易的基礎之上,通過隨機哈希將交易與時間戳等信息一并寫入到一個基于工作證明PoW的無限延伸的鏈式結構中,并以激勵機制鼓勵全網共同維持區塊鏈正確的延伸。以太坊[2]作為區塊鏈技術的應用,具有一套可以執行圖靈完備的腳本語言的虛擬機,并引入智能合約的概念,實現了去中心化應用DApp(Decentralized Application)。以太坊的出現,使得區塊鏈技術的應用不僅僅局限于電子貨幣的交易,基于區塊鏈的去中心化應用也推動著區塊鏈技術應用于各行各業。
隨著區塊鏈技術在商業化中的應用,區塊鏈技術已經從公鏈形式向著聯盟鏈方向發展。聯盟鏈應用之一是解決金融領域中跨行交易清算相關問題,達成在清算過程中不依賴可信任第三方作為監理的目標。本文結合該目標以實現去中心任務發布平臺作為背景展開研究。幾家銀行分別管理各自用戶的賬戶信息,這些銀行想要相互之間聯合賬戶信息搭建跨企業用戶的任務發布平臺,并根據任務完成情況進行轉賬交易。采用傳統的中心化系統運行該任務發布平臺會造成銀行間不信任的情況,因此需要依賴第三方進行監管,這種模式會造成大量開銷。本文提出采用區塊鏈技術進行解決,每個銀行負責維護以太坊節點參與區塊的生成與校驗,實現賬戶間交易去中心化執行。但以太坊在應用于聯盟鏈場景中面臨著資源浪費和不可信的問題。本文針對這些問題,本文提出采用改進的PBFT共識算法進行解決,并加以實現。
以太坊采用PoW共識機制,一方面會因為算力競爭造成大量的資源浪費,這是聯盟鏈中不期望的;另一方面,聯盟鏈中所有節點的總算力往往達不到公鏈中所有節點總算力的數量級,因此聯盟鏈中一個節點很容易通過疊加CPU達到聯盟鏈全網50%的算力并進行攻擊,因此在聯盟鏈中PoW共識機制并不可靠。
近些年人們對共識算法不斷研究并取得一定進步。King等[3]首次提出了權益證明Pos(Proof-of-Stake)的共識機制緩解了算力競爭造成的資源浪費,但仍然沒有擺脫挖礦過程。Larimer[4]提出了授權股權證明DPos(Delegated-Proof-of-Stake)的共識機制,但該機制要依賴于代幣,而在很多的商業應用中是沒有代幣的。Schwartz[5]提出了RPCA(Ripple Protocol Consensus Algorithm)共識機制,該算法結合拜占庭將軍問題,擺脫了通過挖礦達成共識的限制,但Ripple對去中心化應用研究較少。Linux基金會推出的超級賬本項目[6]采用了PBFT[7-8]算法達成全網共識。然而超級賬本項目仍然處于開發階段,系統可靠性并沒有經過大規模檢驗。PBFT算法首先由Castro[7]提出并用于解決異步分布式系統如何達成一致的問題。將PBFT[7]算法應用于區塊鏈的共識機制,具有較高的可靠性。節點間通過協商達成一致,該算法可以保證當不多于三分之一的節點發生拜占庭錯誤時區塊鏈仍能保證正常運轉。
本文結合相關研究,提出基于改進PBFT算法的以太坊共識機制,并應用于區塊的一致性校驗中。采用改進PBFT共識算法,節點不需要通過工作證明來達成共識,從而解決了資源浪費的問題。與PBFT算法相比,在執行檢查點協議和視圖切換協議時,改進PBFT算法不需要進行數據傳輸,從而減少了傳輸消耗。
本文以聯盟鏈作為應用場景,基于以太坊設計了一個異步的分布式系統,系統中各節點通過網絡進行交互。該系統類似于分布式數據庫,并以區塊的形式存儲交易信息。系統中各節點間在相互不信任的前提下,利用分布式節點共識機制完成數據生成與存儲的操作。系統中每個節點運行的程序相同,為改進后的以太坊。改進后的以太坊架構如圖1所示。

圖1 改進后以太坊系統架構
相比于以太坊架構,由于該系統模型應用于聯盟鏈場景,節點不需要被激勵也可以進行區塊鏈的維護工作,因此取消了激勵層。同時該架構保留了以太坊的智能合約層、網絡層和數據層,提供以太坊中基本的服務。在共識層中,采用改進PBFT,IPBFT(Improved Practical Byzantine Fault Tolerance)算法作為以太坊的共識機制。利用拜占庭容錯算法使分布式系統中各節點對區塊達成一致后,將區塊添加到該節點維護的區塊鏈中,實現數據的存儲。在這個過程中,網絡可能出現錯誤消息、延遲、重復消息等錯誤,但該系統仍然可以對區塊的一致性達成共識。
本文根據以太坊區塊結構,設計了適用于以太坊的一種改進PBFT共識機制,解決了以太坊在聯盟鏈場景下面臨算力競爭造成的資源浪費和不可信的問題。其中對于PBFT算法中檢查點協議和視圖切換協議進行了如下改進:在檢查點協議中,本文取消了證書刪除節點間協商過程,系統同步區塊過程采用節點索要的方式;在視圖切換協議中,本文根據區塊生成協議,采用超時機制進行視圖切換,在一定程度上減少網絡通信量。
在PBFT機制中有如下定義:
定義1Quorum是由系統節點集合組成的,并且任意兩個Quorum的交集不為空。假設系統節點集合為U,?={Q1,Q2,…,Qn},且Q1?U,滿足式(1)則稱Q為一個Quorum。
?Qi,Qj∈?且Qi∩Qj≠φ
(1)
Quorum有如下性質:
(1) 任意兩個Quorum至少有一個共同的并且正確的節點。
(2) 一定存在著沒有錯誤的Quorum。
本文定義2f+1個節點為一個Quorum,其中f代表系統中最大可容忍錯誤節點個數,這樣可以保證在一個Quorum至少有f+1個節點沒有發生錯誤。
定義2PBFT機制中正確節點以一致性的形式觀察群中節點的變化,把這樣達成一致的群稱為視圖(View),視圖進行編號,記作v。假設一個視圖共有N個節點,每一個節點的編號依次為{0,1,2,…,N-1},其中主節點的編號記為p(其余節點為備份節點稱為replica),滿足:
p=vmodN
(2)
其中v是視圖的編號。當群中主節點發生故障,則下一個編號的節點成為主節點,視圖也隨之發生切換,視圖編號增加1。
定義3證書:系統達成共識過程需要進行消息傳輸,該消息稱作為證書。其中,證書信息中包含信息的編號,本文以區塊號作為信息編號。
在區塊鏈中,交易以區塊的形式提交并永久記錄到區塊鏈中。在本系統中,交易記錄到區塊鏈中的過程如下:
(1) 主節點對交易列表中的交易進行校驗,并將交易列表中的交易寫入到區塊中,并向其他節點發送區塊。
(2) 全網其他節點對該區塊的合法性進行校驗。
(3) 校驗通過所有節點將該區塊添加到區塊鏈中,并從交易列表中清除該區塊中包含的交易。該區塊中的交易記錄到區塊鏈中并生效。
區塊的校驗包括對區塊頭信息的校驗和區塊體中交易信息的校驗,區塊頭中包含上一區塊的哈希值和當前區塊的時間戳等信息。當交易到來時,交易列表不為空,此時由主節點將交易寫入到區塊中并廣播該區塊。當全網節點對該區塊達成一致后,嘗試將該區塊添加到區塊鏈中。整個過程是異步的,節點間通過區塊號和區塊記錄的上一區塊哈希值保證區塊添加到區塊鏈的有序性。當交易列表為空時,節點會監聽區塊鏈中最優區塊的時間戳與系統時間間隔,當時間超過t會生成一個空的區塊并添加到區塊鏈中。這里考慮到在信息傳輸過程會產生網絡延遲,假設區塊從生成到達成共識并添加到區塊鏈的最長時間為Δt,其中t需要滿足t>Δt,這樣可以保證在生成空區塊時,之前的區塊已經在全網達成一致。當區塊鏈中添加空區塊后,主節點停止生成區塊,并等待交易到來時再重新觸發生成區塊。
該協議主要是保證區塊在全網達成一致。由拜占庭算法可知,一個系統可以容忍不超過全部節點的三分之一發生拜占庭錯誤,因此這里假設在區塊鏈系統中共有3f+1個節點,一個Quorum至少包含2f+1個節點。
在一個可以容忍拜占庭錯誤的系統中f的最小取值為1,因此系統至少由4個節點組成。圖2是由4個節點組成的系統進行一次正常請求的執行過程。

圖2 正常請求執行過程
由圖2可知,一個信息達成共識并執行需要經過三階段執行協商后達成一致執行,三階段協商過程如下:
(1) 當主節點中滿足生成區塊條件時生成一個新區塊時,主節點生成Pre-Prepare證書,將Pre-Prepare證書發送給其他節點后,主節點進入Prepare狀態。
(2) replica收到Pre-Prepare證書時就接收到了新生成區塊的信息,同時該節點進入到Prepare狀態。當該節點發現消息是來自于主節點時并且第一次接收時,會將Prepare證書發送給其他節點,并記錄證書信息。當發現某一條證書通過2f個節點同意的反饋,表明該區塊信息通過了一個Quorum的同意,那么對于這條證書該節點進入Commit的狀態,并向其他節點發送Commit消息。
(3) replica會接收到來自其他節點的Commit的證書,當發現該信息得到了2f+1(包括自身)個節點同意,則認為該區塊信息在系統中達成共識,并嘗試將該區塊添加到區塊鏈中。
通過上述三階段提交方式,使一個區塊實現了全網節點達成一致。以圖2為例考慮到當replica節點發生拜占庭錯誤時,由于另外兩個replica是正確節點,因此仍可以滿足2f+1個節點通過驗證,正確節點之間可以保證區塊的一致性;當主節點發生拜占庭錯誤時,通過在replica節點中重新選出主節點生成區塊并發送消息。接著將該區塊添加到區塊鏈,正確的區塊會成功添加到區塊鏈,并觸發下一個區塊的生成,這個過程是循環執行的。
執行過程主要對區塊進行校驗,當完成校驗,并證明該區塊是正確時,會將區塊內包含的交易從該節點的交易列表中清除掉,并將該區塊添加到區塊鏈中。
該協議的主要目的是為了維護節點所存儲信息的規模,解決證書信息的回收,從而降低節點的內存開銷。PBFT機制中定義檢查點協議是通過節點間定時協商后再進行清除,這是為了防止個別節點不同步需要收集之前的證書。因此清除過期證書也是一個全網達成一致的過程,這勢必又要進行3階段提交過程,造成通信浪費。本文根據區塊鏈中最優區塊的時間戳進行證書清除。區塊鏈是以鏈表的形式按照區塊的生成時間相連而成,當一個區塊添加到區塊鏈中,則說明該區塊時間戳之前的證書都已經被校驗過,即該節點中這些證書相關的狀態已經廣播完畢,并可以進行清除,而證書的信息則以區塊的形式永遠保存在該節點中。因此對添加區塊事件進行監聽,每當有區塊添加到區塊鏈中,將該節點中該區塊時間戳之前的證書進行清除。整個過程不需要節點間相互通信,同時也可以保證證書及時的清理。
以太坊中包含了節點間同步區塊的解決方案,當一個節點發現自身維護的區塊鏈與其可信任的節點維護的區塊鏈的最優區塊的區塊號相差一定大小時,該節點會向其信任的節點(一般為開發者維護的節點)索要區塊并將區塊添加到區塊鏈中。而在聯盟鏈中并不存在完全可信的節點,因此該方案并不可行。本文提出當某節點區塊鏈狀態與其他節點不一致時,向該視圖中的2f+1個節點請求該區塊鏈需要添加的區塊的區塊哈希,區塊哈希是可以唯一標識區塊的256位字節數組,當有不少于f+1個節點返回的區塊哈希一致,則認為該區塊哈希對應的區塊在全網達成共識。該節點首先會在Pre-Prepare證書中查找是否存在該區塊哈希的證書,不存在會向其中一個節點索要該區塊哈希對應的區塊,并將該區塊添加到區塊鏈中,實現同步。該過程中數據傳輸量對于網絡開銷可以忽略不計。
該協議是針對主節點發生故障,視圖發生改變,需要更換主節點的協議。PBFT機制詳細地闡述了視圖切換的過程,因為視圖的切換不當會使得整個系統不一致,因此這個過程不可避免地也需要進行節點間的相互通信。在本系統中,采用對區塊鏈最優區塊監聽的方式判斷主節點是否發生故障,當滿足添加區塊的條件下,節點沒有進行區塊的添加則認為主節點發生故障,此時需要進行視圖切換。具體算法如下:
算法1ViewChange()
Input:該節點維護的區塊鏈和交易列表
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 下一個區塊交易信息為空
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
視圖切換過程會將證書列表進行清除,并由新的主節點完成提交交易的操作,并繼續維持系統的穩定。通過上述算法,當主節點發生錯誤時,系統會在時間內完成視圖的切換。該算法需要更長的超時時間保證在主節點發生錯誤時,全網已經達成一致。這對于一般的分布式系統可能會造成服務中斷等問題,而對于聯盟鏈環境下以太坊來說,服務并不會停止。其他正確節點仍然可以將交易存入交易列表中,并由其他節點各自維護的本地數據提供服務。整個視圖切換過程根據區塊鏈中最優區塊時間戳采用超時觸發,在區塊鏈可容忍的延遲的范圍,完成主節點的切換,不需要節點間相互通信,減少了通信消耗。
本文采用了以太坊作為區塊鏈框架,采用改進PBFT算法作為以太坊的共識機制,并將該系統與原有的以太坊開源框架進行比較。
本系統保留了以太坊的絕大優勢,因此從功能方面實現了以太坊提供的功能。從資源浪費的角度,本文所采用的系統取消了挖礦的過程和激勵機制,因此節點不需要進行大量的運算,并通過算力競爭來達到共識,解決了PoW共識算法所造成的資源浪費的問題。本文所采用的改進PBFT算法更加適用于聯盟鏈的環境中,節點的可靠性較高,容錯率要求雖然達不到PoW共識算法的50%,但33%的容錯率也足以滿足場景需求。對于出塊時間,由于PoW需要計算隨機數,即使通過難度系數的調整也很難讓出塊時間穩定。一方面交易隨著區塊被記錄到區塊鏈的時間是隨機的,因此交易被記錄到區塊鏈的時間也是隨機的,另一方面,出塊時間的不確定會造成區塊鏈出現分支,不利于區塊鏈的維護。而本文采用的共識算法,當有交易的時候會即時完成區塊的一致性協商和區塊校驗,因此交易會第一時間記錄到區塊鏈中,同時由一個節點生成區塊,不存在分支的情況,可以很好地維護區塊鏈中的數據。
從PBFT算法角度看,本文針對以太坊改進的PBFT算法在檢查點協議和視圖切換的過程中,并沒有采用各節點相互協商達成一致,而是利用區塊鏈最優區塊的時間戳在各節點不通信的情況下達成一致,減少了消息傳輸成本。
本文的模型適用于聯盟鏈環境中,可以很好地支持以太坊聯盟鏈的運行,而基于PoW共識機制的以太坊適用于節點多的公網之中。
本文實驗硬件采用4核8線程的Intel(R) Core(TM) i7-4870HQ處理器,16 GB內存的硬件平臺。虛擬機8臺,1 GB內存,CPU共享主機的一個處理器核心,網絡連接100 Mbit/s LAN。
本文采用8臺虛擬機分別搭建了基于PoW共識機制和基于改進PBFT共識機制的以太坊聯盟鏈,這里認為8臺機器的算力是相同的,并使節點發生拜占庭錯誤進行實驗,其實驗結果如表1所示。從實驗結果可以看到,本文設計的改進PBFT以太坊共識算法可以實現系統的去中心化運行,在容忍系統節點錯誤率的情況下,PoW共識機制最多可以容忍3個節點發生任何形式的錯誤,而在改進PBFT共識機制中,當主節點發生錯誤時,可以完成視圖切換以及主節點的重新選擇,但是該系統最多可以容忍2個節點發生錯誤。該實驗證明了該機制可以滿足本文所提的要求,但在容錯率中,不如PoW共識機制的容錯率高。

表1 聯盟鏈節點一致性分析
本文對PoW共識機制和改進PBFT共識機制的算力使用情況做了相關實驗和分析。進行單節點測試,在相同的機器中分別運行基于PoW共識機制和改進PBFT共識機制的以太坊,其中基于PoW共識機制采用滿線程運行。由于PoW共識機制中Ethash需要提前生成1 GB的內存空間,為了只對比穩定運行的CPU使用率,因此提前生成好內存哈希值。由于本文使用的CPU是8線程因此以太坊設置為8線程挖礦方式,CPU使用率結果如圖3所示。

圖3 CPU使用率
從結果可以看出基于PoW共識機制的CPU使用率接近100%,而基于改進PBFT(IPBFT)共識機制的CPU穩定使用率僅為16%左右,因此改進PBFT共識機制很大程度上減少了算力的使用,解決了PoW共識機制因為算力競爭造成的資源浪費的問題。
本文分別對PBFT機制和改進PBFT機制進行驗證分析。其中對于檢查點協議,本文結合以太坊區塊同步機制,取消了檢查點中對證書清除的通信過程,因此數據傳輸量為零,而PBFT機制刪除證書需要節點間達成一致,與以太坊區塊同步機制重復,勢必造成傳輸浪費。圖4顯示了當主節點發生錯誤的時候,一個完整的視圖切換過程中的網絡開銷。圖中橫坐標代表系統內節點個數,縱坐標代表每次視圖切換達成共識Quorum的數量,視圖切換過程中,假設證書大小相同,因此通信開銷和Quorum有關。從圖中可以看出PBFT共識機制中,隨著最大容錯節點個數增多,開銷增大,而改進PBFT共識機制中,該部分開銷為零。由此也可以說明該改進PBFT共識機制在網絡開銷上較PBFT共識機制有一定的提高。

圖4 視圖切換傳輸消耗
本節針對以太坊在聯盟鏈場景下的應用進行描述。該應用通過聯合企業各自用戶的賬戶信息,形成公共賬戶管理平臺,并實現了賬戶間交易的去中心化執行。該應用實現了任務發布系統中賞金在賬戶間流通的功能,這個過程類似于賬戶間進行交易。其中賞金的流動過程按照以太坊智能合約規則進行流通。圖5是由四個聯盟體組成的聯盟鏈的系統框架。

圖5 系統框架
每一個聯盟體的用戶與其Web服務器進行交互,以太坊節點服務器提供WebService接口供Web服務器調用。一個用戶提交一筆交易會向Web服務器發出請求,Web服務器相當于該聯盟體管理的用戶的代理服務器,因此交易提交到以太坊節點服務器都由Web服務器完成。以太坊節點服務器接收到交易將交易廣播到其他節點,并按照改進PBFT算法對包含該交易的區塊進行全網一致性驗證,當該區塊在全網達成共識后將該區塊添加到區塊鏈中,此時認為交易被執行并永久保存到區塊鏈中。每一個以太坊節點地位相同,交易執行過程中,沒有第三方進行中心化監管,因此實現了去中心化的功能。圖6是以太坊區塊鏈監控界面的截圖信息,圖中框內表示交易柱狀圖,從監控界面得知系統完成了去中心化執行交易的功能,并可以穩定運行。

圖6 以太坊監控界面截圖
針對以太坊區塊鏈在聯盟鏈的應用場景,基于工作證明共識機制存在的資源浪費和不可信問題,設計并實現了適用于聯盟鏈環境下的以太坊共識機制。本文提出了采用PBFT算法作為以太坊共識機制,取消了基于工作證明共識機制中的挖礦過程。通過主節點生成區塊,其他節點就該區塊是否在全網達成一致進行協商的方式達成共識,解決了原系統中由于算力競爭造成的資源浪費和不可信問題。其中針對PBFT算法中檢查點協議和視圖切換協議進行改進,使該協議更適用于以太坊環境中,并在一定程度上減少了網絡通信開銷。最后采用該以太坊搭建聯盟鏈,實現任務發布系統中賞金流動的去中心化執行。
[1] Nakamoto S.Bitcoin:A peer-to-peer electronic cash system[J].Consulted,2009.
[2] Buterin V.A next-generation smart contract and decentralized application platform[J].Etherum,2014(1):1-36.
[3] King S,Nadal S.PPCoin:Peer-to-Peer Crypto-Currency with Proof-of-Stake[OL].2012.http://ppcoin.org/static/ppcoin-paper.pdf.
[4] Larimer D.Delegated proof-of-stake white paper [OL].2014.http://www.bts.hk/dpos-baipishu.html.
[5] D Schwartz,N Youngs,A Britto.The Ripple protocol consensus algorithm[OL].2015.https://ripple.com/files/ripple_consensus_whitepaper.pdf.
[6] Cachin C.Architecture of the Hyperledger Blockchain Fabric[Z].2016.
[7] Castro M,Liskov B.Practical byzantine fault tolerance and proactive recovery[J].Acm Transactions on Computer Systems,2002,20(4):398-461.
[8] Platania M,Obenshain D,Tantillo T,et al.On Choosing Server-or Client-Side Solutions for BFT[J].Acm Computing Surveys,2016,48(4):1-30.
STUDYANDREALIZATIONOFANIMPROVEDPBFTALGORITHMASANETHEREUMCONSENSUSMECHANISM
Huang Qiubo An Qingwen Su Houqin
(SchoolofComputerScienceandTechnology,DonghuaUniversity,Shanghai201620,China)
Aiming at the resource waste and unreliability caused by computing power competition of PoW consensus mechanism in the scene of Consortium blockchain, PBFT algorithm is proposed as an ethereum consensus mechanism. And the PBFT algorithm is improved with the combination of the ethereum structure. In the improved PBFT, checkpoint mechanism cancelled the process of checking and eliminating certificate regularly and the synchro process of nodes was realized by the scheme of requesting blockchain from other nodes and verifying it. On the basis of blockchain production mechanism, view-change mechanism adopted timeout scheme to change view. Experimental results show that ethereum which is based on improved PBFT algorithm is better for the scene of consortium blockchain. The computing power is reduced a lot and the amount of data transmission is also reduced.
Ethereum Consensus mechanism PBFT Consortium blockchain
TP3
A
10.3969/j.issn.1000-386x.2017.10.051
2017-01-01。黃秋波,副教授,主研領域:車聯網,大數據,分布式數據庫。安慶文,碩士生。蘇厚勤,教授級高工。