基于信譽的動態授權PBFT共識機制

李俊清 辛衍森 宋長青

摘 ?要： 區塊鏈是一種基于零信任基礎、去中心化及不可篡改的分布式賬本技術。共識算法作為區塊鏈主要技術之一，其效率直接影響區塊鏈系統性能。針對PBFT共識算法運行效率低的問題，本文提出了基于信譽的動態授權PBFT共識機制，引入信譽評價體系對系統節點進行信譽評價，動態決定從信譽最高的節點中選取共識節點，同時實現了非停機情況下動態增刪節點的功能，且隨著系統長期運行，所能容忍的拜占庭節點動態增加;優化了一致性協議，將傳統的一致性協議與基于speculation技術的拜占庭協議進行融合，降低了算力開銷和通信代價;通過對共識節點的信譽及行為分析，進一步降低惡意節點成為共識節點的概率，解決了由拜占庭節點作為主節點帶來的交易延遲增加問題。最后從算力開銷、交易吞吐量和容錯性能等方面進行了論證分析。

關鍵詞： 區塊鏈;PBFT共識算法;全局信譽模型;動態授權;speculation技術

中圖分類號： TP311.13 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.05.001

本文著錄格式：李俊清，辛衍森，宋長青，等. 基于信譽的動態授權PBFT共識機制[J]. 軟件，2019，40（5）：0107

【Abstract】： Blockchain is a distributed ledger technology based on zero-trust foundation， decentralization and non-tamperability. Consensus algorithm is one of the main techniques of blockchain， and its efficiency directly affects the performance of blockchain system. Aiming at the low efficiency of PBFT consensus algorithm， this paper proposes a reputation-based dynamic authorization PBFT consensus mechanism， introduces a reputation evaluation system to evaluate the reputation of system nodes， and dynamically decides to select consensus nodes from the nodes with the highest reputation. At the same time， the function of dynamically adding and deleting nodes in the case of non-downtime is realized， and the Byzantine nodes that can be tolerated dynamically increase with the long-term operation of the system; The consistency protocol is optimized， and the traditional consistency protocol is merged with the Byzantine protocol based on speculation technology， which reduces the computational overhead and communication cost; Through the analysis of the reputation and behavior of the consensus node， the probability of the malicious node becoming the consensus node is further reduced， and the problem of increased transaction delay caused by the Byzantine node as the master node is solved. Finally， the argumentation analysis is carried out from the aspects of computational power， transaction throughput and fault tolerance.

【Key words】： Blockchain; PBFT consensus algorithm; Global reputation model; Dynamic authorization; Speculation technology

0 ?引言

區塊鏈（Blockchain）作為當下熱門的分布式數據庫技術方案，包含分布式數據存儲技術、P2P網絡傳輸機制、分布式節點間的共識機制、加密算法、可編程的智能合約等技術[1]。由于其具有去中心化、開放性、自治性、不可篡改和匿名性的特點，區塊鏈不僅在數字貨幣等數字資產中發揮巨大作用，而且對金融服務、公共服務、社會生活等領域產生深遠影響。

區塊鏈的快速發展的同時，其存儲、共識、監管和安全等方面問題凸顯，其中共識算法效率制約著區塊鏈技術大范圍應用。起初比特幣區塊鏈采用依賴節點算力的工作量證明共識算法（POW）來實現一致性選擇[1]。隨著技術發展，非許可鏈中相繼涌現出權益證明機制（POS）和股份授權證明機制（DPOS），許可鏈發展了實用拜占庭容錯機制（PBFT）[2]等共識機制，但每種機制在吞吐量、時延、功耗等方面都難以兼顧。

本文基于DPOS的思想，利用信譽評價體系進行共識節點的選取，在PBFT共識機制基礎上融合基于speculation技術的拜占庭算法，同時引入拜占庭節點檢測機制，以保障系統長期運行環境的安全性和高效性。

1 ?相關知識

1.1 ?共識機制介紹

共識就是使得在權力高度分散的去中心化系統中各個節點達成一致，共識機制在去中心化的基礎上解決了節點間互相信任的問題。如何在分布式系統中高效達成共識是分布式計算領域的重要研究問題之一[1]。區塊鏈網絡中節點數目越多，去中心化程度越高，那么節點決策權越小，系統達成共識的效率越低。

1.1.1 ?工作量證明機制（POW）

中本聰在2009年實現的比特幣系統中采用了POW共識機制，其核心思想是通過算力進行挖礦，獲取記賬權。比特幣所采用的是一種可重復使用的Hashcash工作證明機制，使得生成工作證明量是一個概率意義上的隨機過程[2]。在系統中，所有的節點（礦工）都要根據各自計算機算力使用不同的隨機數持續計算一個特定的哈希值，該過程被稱為“挖礦”。為了驅使礦工進行挖礦，該行為設定了相應的獎勵機制。由此可知，該共識機制的優點是通過算力競爭保證系統的完全去中心化和安全性，缺點是挖礦造成大量能源消耗和硬件資源浪費。比特幣系統動態調整目標值，維持生成區塊的平均時間和交易確認時間分別在十分鐘和一小時左右，效率低，難以大范圍應用。

1.1.2 ?權益證明機制（POS）

Nick Szabo提出的POS可以說是為了解決POW的資源消耗問題的一種節能替代機制，本質上是用對貨幣所有權的證明取代算力競爭。貨幣的來源是在生成一個區塊時，由礦工發起關于特定貨幣分配的交易，POS是基于幣齡來選擇節點創建下一個區塊，節點所持有的代幣越多、時間越長，挖礦的難度越低，達成共識的時間越短。與POW相比，POS可以節省更多的資源，性能有所提高，而其容錯能力與POW相當，并沒有擺脫節點挖礦，不具有普適性。由于該機制相信權益高的節點攻擊網絡的可能性低，所以一定程度上安全性降低。

1.1.3 ?股份授權證明機制（DPOS）

DPOS是在POW及POS的基礎上，用節點的權益作為選票選出一定數量的代表節點輪流進行區塊的生成和驗證。過程中產生的收益由這些代表節點平分，并且含有權益的節點可以隨時發起投票更換“有問題”的代表節點。DPOS機制大幅降低了直接參與共識的節點，減少了對確認的需求，使共識驗證過程可以在秒級單位內完成。隨之帶來的是節點參與投票不積極或者代理投票的問題，同時對于代幣的依賴使得該機制難以適用于商業應用。

1.1.4 ?實用拜占庭容錯機制（PBFT）

拜占庭容錯技術能夠容忍任意形式的軟件錯誤和安全漏洞，作為一種解決分布式系統容錯問題的通用方案，復雜度由指數級降到了多項式級，大大降低了拜占庭協議的開銷[3]。PBFT作為一種狀態機副本復制算法，其前提要求節點共識時狀態相同，且對同一消息處理結果也必須相同。PBFT中，區塊鏈網絡中存在拜占庭節點數f，則總節點須大于3f，而多于3f的節點帶來是系統算力增加，容錯性能較低。其在交易吞吐量和共識延遲方面性能有較大提高，符合大部分應用要求，是目前最主流的共識算法。目前，HyperLedger聯盟、中國ChinaLedger聯盟等區塊鏈聯盟都在進行該共識機制的實際部署應用[2]。

1.2 ?全局信譽模型

胡建理等學者提出的一種基于反饋可信度的分布式P2P信任模型（FCTrust）[4]是在原有的基于信譽的全局信任模型上[5，6]，為了防止惡意節點進行虛假評價、共謀欺騙等惡意行為，提出的一種節點反饋信息評價機制，將全局可信度高的節點與反饋信息可信度高的節點區分開來。該反饋信息評價機制將節點間交易頻率和節點評價的相似度納入主要參考因素。FCTrust是通過參與交易的節點之間相互評價，分析節點之間的交易次數、評分比較和節點的全局信譽值，為該節點分配一個信任值，然后通過迭代運算得到一個在全局范圍內的信譽值，該信譽值在沒有交易進行的情況下對所有節點是保持不變并且唯一的。

由于其引入了節點反饋信息評價機制，所以相比EigenTrust模型對惡意節點的虛假評價、對抗共謀等惡意行為的處理更加有效，給予惡意節點更低的全局信譽值。綜合考慮了交易節點之間的局部信任、節點自身的全局信譽值和節點間反饋信息可信度，降低系統信任誤差度，使得節點最終得到的全局信譽值更加可靠和精確。FCTrust要求所取得最終的全局信譽值依賴的節點評價及反饋信息具有近期有效性，并且利用分布式求解協議計算全局信譽值，因此大大降低了算法的復雜度。例如在消息復雜度的測試中，得到EigenTrust模型為O（n2），而FCTrust模型僅為O（n）[4]。

2 ?共識機制優化

本文提出了一種優化的共識機制，以下稱為基于信譽的實用拜占庭容錯機制，簡稱RPBFT（reputation practical byzantine fault tolerance）。利用全局信任模型決定直接參與共識的節點;采用傳統一致性協議融合基于speculation技術的拜占庭協議，降低網絡開銷，提高系統效率;通過對共識節點的行為和其自身的全局信譽值分析，引入拜占庭節點的檢測機制，對拜占庭節點進行降級處理，提高該系統所能容忍的最大惡意節點數。

2.1 ?共識節點的選擇

基于DPOS的思想，同時為了避免投票機制帶來的投票者不積極、代理投票等導致投票的有效性降低的問題，本文利用全局信任模型，將節點的全局信譽值作為選擇共識節點的重要標準。為了確保選取的共識節點都處于正常在線狀態，為每一個節點設置一個狀態標識。然后按照公式1：

Rf=GrfState ? ? （1）

公式1中，Rf是節點信用系數值，Grf代表節點的全局信譽值，State（Boolean類型）表示節點狀態;當節點出現掛機、被攻擊、自身故障、網絡問題、離線狀態等不能正常運行時State為0。由公式得出每個節點的信用系數值，按照該信任系數值從高到低選取前100位組成共識節點集，其中各節點之間是相互平等的，繼續選取前50位組成預備共識節點集，兩節點集中節點數目可由所有節點投票動態決定。

當共識節點集正在進行區塊的生成及驗證時，由于節點的State可能發生變化，要求預備共識節點集是動態變化的。隨著交易進行對節點評價和反饋消息會不斷更新，同時要求這些評價和反饋消息具有近期有效性，以保證節點的全局信譽值是動態變化的。因此，為保障系統實時有效性，共識節點集每經過一段時間需進行更新。該時間間隔內若在共識節點集中發現惡意節點，系統將惡意節點賦予更低全局信譽值并將其剔除共識節點集，由預備共識節點集的首個節點代替該節點參與共識。隨著系統的運行，正常節點交易越頻繁，全局信譽值越高，而各類惡意節點能夠被全局信任模型有效識別并賦予更低的全局信譽值，系統開始良性循環，惡意節點被選作共識節點的可能性非常低。共識算法中所能容忍的拜占庭節點數不變，但惡意節點被選作共識節點的可能性降低，因此整個系統可容忍的惡意節點數量動態增加。

2.2 ?RPBFT共識算法

2.2.1 ?算法定義

PBFT共識機制在保證活性和安全性的基礎上，當總節點數目為3f+1時，其能容忍的拜占庭節點數最大為f。該算法中由一致性協議保證每一個正常節點以相同順序執行客戶端的請求消息;在主節點發生系統錯誤或成為拜占庭節點時利用視圖更換協議更換主節點，使正常節點執行過的客戶端請求不被篡改;檢查點協議用以清除日志記錄、設置水線值（h和H）、同步節點狀態。

RPBFT共識機制，相對于傳統的一致性協議，融合了基于Zyzzyva5協議[7]的拜占庭算法，該算法引入了speculation技術，在節點接收請求后直接執行請求，省去了一致性協議中耗時的兩兩交互環節，但在共識過程中若存在拜占庭節點，其性能會大大降低。因此，我們利用全局信任模型和拜占庭節點檢測機制大幅降低甚至消除共識節點中拜占庭節點的存在，將傳統的一致性協議和基于speculation技術的拜占庭協議進行結合。

2.2.2 ?算法流程

假設共識節點共有n個，則從0到n-1對節點進行編號，所有節點的相同狀態信息稱為視圖，同時對視圖由0開始遞增編號。視圖中要求有一個主節點（primary），該主節點采用公式2選取，

p=（h+v）mod n ?（2）

公式2中p代表節點編號，h代表當前共識區塊高度，v代表視圖編號;其余共識節點稱作從節點（replica）;當primary節點失效時，從replica節點中依據公式2選取一個新的primary節點[8]。算法如下：

（1）若共識節點中無拜占庭節點

RPBFT共識的具體步驟如下：

a）客戶端將交易信息發送到primary節點。

b）primary節點收到客戶端請求消息后打包排序，然后廣播預準備消息給replica節點。

c）節點執行該請求，最后向客戶端反饋結果，如果客戶端收到3f+1個節點反饋的信息并且信息全部相同，則共識成功。

d）若客戶端沒有收到所有節點的反饋信息或者存在不相同的反饋信息，則說明共識失敗，共識節點中存在拜占庭節點，轉到一致性協議共識流程重新共識。

RPBFT共識流程采用基于Zyzzyva5協議的共識流程，如圖1所示。

（2）若共識節點中存在拜占庭節點

RPBFT共識的具體步驟如下：

a）客戶端將交易信息發送到primary節點。

b）primary節點接收消息后進行打包并檢驗其中交易合法性，刪除非法交易信息，分配序列號。然后向replica節點發送預準備消息<m>。

c）replica節點收到預準備消息，則表明消息通過節點驗證（該驗證包括視圖編號、消息序號、摘要、簽名等）且進入準備階段，發送準備消息。

d）在節點收到2f個準備消息后進行合法性驗證，寫入日志，準備消息必須寫入日志，而預準備消息則可進行選擇記錄，日志的寫入標志著準備階段完成。發送確認消息，進入Commit階段。

e）節點收到2f+1個確認消息，代表著達成共識，然后節點執行該請求并寫入數據，最后向客戶端反饋信息。

RPBFT共識流程采用基于傳統一致性協議流程，如圖2所示。

隨著系統運行，節點的全局信譽值越來越精確，共識節點中存在拜占庭節點的可能性大大降低，因此系統將會采用基于speculation技術的算法進行共識并保持良性循環。從而降低共識的響應延遲、增加系統吞吐量、減少算力、降低功耗。圖3為系統完整的共識算法流程圖。

2.3 ?拜占庭節點檢測與降級

在共識節點集沒進行更新的這段時間內，共識節點有可能會發生系統故障、網絡延遲或遭受惡意攻擊等錯誤，則該節點被稱為拜占庭節點。因此，當一個共識階段完成后，未能向客戶端發送反饋消息或者反饋消息不一致的節點，則認為產生錯誤行為，此時本算法將降低其全局信譽值并且立即剔除共識節點集，由預備共識節點集中首個節點代替參與共識。進一步降低了共識節點中拜占庭節點存在的可能性，配合全局信任模型為系統執行基于speculation技術的拜占庭協議提供保障，提高系統效率。

3 ?性能分析

現有的共識算法中，全球大部分算力被比特幣區塊鏈系統所吸引，因此其它采用POW的系統很難獲得足夠算力以保障系統安全，而且系統達成共識時間較長;POS雖然解決了一部分資源浪費的問題，但仍然沒有擺脫挖礦過程，沒有解決其本質問題;DPOS是在POS的基礎上發展而來，卻沒有擺脫代幣的制約;因此，POW、POS、DPOS在眾多的應用中都存在著制約問題。許可鏈中普遍采用的PBFT共識效率和吞吐量高，但是較低的容錯性和兩兩交互的通信代價導致其只適用于小規模的許可鏈。本文提出的RPBFT在PBFT基礎上，利用全局信任模型選取共識節點，提高共識效率，增強系統容錯性;將PBFT中靜態的共識節點機制調整為動態可加入、剔除和降級處理機制，適用于非許可鏈系統和大規模的許可鏈系統。

從算力開銷、交易吞吐量和容錯性能三個方面進行RPBFT與PBFT對比分析如下：

3.1 ?算力開銷

PBFT共識算法中存在兩次全網節點相互通信的過程，通信代價高，所以限制了該共識在公有鏈和大規模的聯盟鏈系統中的適用性。RPBFT相比PBFT大大降低兩兩通信交互的過程，因此其通信代價大幅降低。

由于RPBFT引用了全局信任模型，通信代價有所增加，但其復雜度遠小于PBFT的復雜度;同時RPBFT將傳統的一致性協議與基于speculation技術的拜占庭協議進行結合，全局信譽值低的惡意節點參與共識的概率非常低，配合拜占庭節點檢測與降級機制，最優情況下可以消除共識節點中拜占庭節點，所以大部分共識過程中，系統采用基于speculation技術的拜占庭協議進行區塊生成與驗證。

下面利用該全局信任模型求解所選出的共識節點中惡意節點的概率，該模型的性能評價中引入成功交易率（STR），即系統中成功交易次數占總交易次數的比例。這里可以認為是一個節點選擇另一個節點進行交易，若交易節點是正常節點，則交易成功，否則交易失敗，可以認為成功交易率亦代表節點選擇正常節點的概率。惡意節點包括簡單惡意節點（SMS）、不誠實推薦節點（SMR）、協同惡意節點（CM）和策略型惡意節點（SMP）[4]。由于SMP節點能夠視具體情況進行相應評價，以避免被模型識別并賦予較低信譽值，因此，其對系統的影響要大于其他種類的惡意節點。假設系統中惡意節點全為SMP節點且占系統總節點33%，STR在隨SMP節點的變化情況，如圖4

由圖4可知，當SMP節點占比為33%時，STR約為0.84。由于現實系統中惡意節點不只是SMP類型，即說明在惡意節點為33%的系統中，選擇共識節點時正常節點的概率要大于84%。若節點在共識中不作為，則可認為該節點為“漏網”的拜占庭節點，賦予低信譽值并且降級處理，進一步降低拜占庭節點的存在，降低算力開銷。

3.2 ?交易吞吐量

區塊鏈系統的交易吞吐量是量化系統運行效率高低的一個重要標準。RPBFT有效的降低了交易延遲、提高吞吐量。

RPBFT中主節點發生故障的可能性降低，降低調用試圖切換協議的頻率，降低了交易延遲;算力開銷降低，縮短了交易處理時間，進一步提高了交易吞吐量;因此，RPBFT的交易吞吐量隨著系統運行時間增加而增加，相比PBFT的相對穩定值有較大提高。

3.3 ?容錯性能

PBFT共識算法要求系統能容忍的最大拜占庭節點數不超過全網結點的1/3，容錯能力較低，對系統性能影響較大。RPBFT的容錯性能要大于33%。

RPBFT能夠隨著系統的長期運行，共識節點中拜占庭節點數大大降低甚至消除，惡意節點的全局信譽值越來越低，所以惡意節點在共識節點的選取上所發揮的作用微乎其微。由圖4可知，SMP節點占比增加至40%時，STR仍高達0.8，配合拜占庭檢測機制，則當系統中惡意節點適當增加時并不會對系統產生影響。因此，RPBFT能容忍的惡意節點數隨著系統進入良性循環而增加，可由交易吞吐量檢測來間接反應適當增加惡意節點時對系統性能的影響。

以上分析對比在相同的非必要因素條件下，論證了RPBFT共識機制具有更低的通信開銷、更高的交易吞吐量和容錯能力。

4 ?總結與展望

本文提出的基于信譽的PBFT共識機制，通過全局信任模型為每個節點分配全局信譽值，配合拜占庭節點檢測和剔除機制，并融合了傳統一致性協議算法和基于speculation技術的協議，有效改善了PBFT的容錯性能較低和靜態節點結構，進一步提高系統性能。

本文下一步工作是：如何利用信譽評價模型賦予每個節點更加精確和準確的信譽值，縮短系統運行進入良性循環的時間;在共識節點選取和讀取節點信譽值進行比較時，如何嚴格的保障數據的隱私安全。

參考文獻

[1] 袁勇， 王飛躍. 區塊鏈技術發展現狀與展望[J]. 自動化學報， 2016， 42（4）： 481-494.

[2] 蔡亮， 李啟雷， 梁秀波. 區塊鏈技術進階與實戰[M]. 北京： 人民郵電出版社， 2018.

[3] 范捷， 易樂天， 舒繼武. 拜占庭系統技術研究綜述[J]. 軟件學報， 2013， 24（06）： 1346-1360.

[4] 胡建理， 吳泉源， 周斌， 劉家紅. 一種基于反饋可信度的分布式P2P信任模型[J]. 軟件學報， 2009， 20（10）： 2885- 2898.

[5] 竇文， 王懷民， 賈焰， 鄒鵬. 構造基于推薦的Peer-to-Peer環境下的Trust模型[J]. 軟件學報， 2004（04）： 571-583.

[6] Xiong L， Liu L. PeerTrust： Supporting Reputation-Based Trust for Peer-to-Peer Electronic Communities[J]. IEEE Transactions on Knowledge & Data Engineering， 2004， 16（7）： 843-857.

[7] Kotla R， Alvisi L， Dahlin M， Clement A， Wong E. Zyzzyva： Speculative Byzantine fault tolerance. In： Proc. of the 21st ACM SIGOPS Symp. on Operating Systems Principles. New York： ACM Press， 2007， 45-58. [doi：10.1145/1294261. 1294267]

[8] 劉肖飛. 基于動態授權的拜占庭容錯共識算法的區塊鏈性能改進研究[D]. 浙江大學， 2017.

[9] Miguel Castro， Barbara Liskov. Practical byzantine fault tolerance and proactive recovery[J]. ACM Transactions on Computer Systems （TOCS）， 2002， 20（4）.

[10] Cowling J， Myers D， Liskov B， Rodrigues R， Shrira L. HQ replication： A hybrid quorum protocol for Byzantine fault tolerance. In： Proc. of the 7th Symp. on Operating Systems Design and Implementation. Berkeley： USENIX Association， 2006. 177-190.

[11] 王曉光. 區塊鏈技術共識算法綜述[J]. 信息與電腦（理論版）， 2017（9）： 72-74.

[12] 周鄴飛. 區塊鏈核心技術演進之路——共識機制演進（1）[J]. 計算機教育， 2017（4）： 155-158.

[13] Nakamoto S. Bitcoin： A peer-to-peer electronic cash system[J]. Consulted， 2008.

[14] Hendricks J， Sinnamohideen S， Ganger GR， Reiter MK. Zzyzx： Scalable fault tolerance through Byzantine locking. In： Proc. of the 2010 IEEE/IFIP Intl Conf. on Dependable Systems and Networks. 2010. 363-372. [doi：10.1109/DSN.2010.5544297]

[15] 常文軍， 孫超平， 胡鑫. 基于分布式偏好關系的多屬性決策方法及應用[J]. 計算機應用研究， 2017， 34（12）： 3693- 3697+3707.

[16] 閔新平， 李慶忠， 孔蘭菊， 張世棟， 鄭永清， 肖宗水. 許可鏈多中心動態共識機制[J]. 計算機學報， 2018， 41（05）： 1005-1020.

[17] I Bentov， C Lee， A Mizrahi， M Rosenfeld. Proof of Activity： Extending BitcoinS Proof of Work via Proof of Stake. Acm Sigmetrics Performance Evaluation Review， 2014. 42（3）： 34-37.

[18] 苑超， 徐蜜雪， 斯雪明. 基于聚合簽名的共識算法優化方案[J]. 計算機科學， 2018， 45（02）： 53-56+83.

[19] 張永， 李曉輝. 一種改進的區塊鏈共識機制的研究與實現[J]. 電子設計工程， 2018， 26（01）： 38-42+47.

[20] Happe A， Krenn S， Lornnser T. PBFT and Secret—Sharing in Storage Settings[C]//Twenty-fourth International Workshop on Security Protocols. 2016.