一種基于積分制的改進實用拜占庭容錯算法

沈 瑞，李玲娟

(南京郵電大學 計算機學院，江蘇 南京 210023)

0 引 言

比特幣誕生于2008年，由一個化名為中本聰的學者在論文中首次提出[1]，其背后的區塊鏈技術得到越來越多的重視與發展。區塊鏈是一種計算機技術在價值互聯網時代的創新應用模式，是數據庫、密碼學、網絡技術等多種技術整合集成的結果，具有去中心化、去信任化、集體維護、不可篡改等特點[2]。從數據的角度，可以把區塊鏈看成由一個個區塊組成，區塊記錄著經過驗證的、區塊創建過程中發生的所有交易記錄。近年來，區塊鏈技術的價值不斷被挖掘，在金融、身份驗證、社交通訊等多個領域都有著廣泛的應用，并得到了許多國家政府的高度重視。

共識算法是區塊鏈技術的核心，用于解決在去中心化的分布式互連網絡中，如何判斷區塊數據正確性和所有權，以使所有的節點達成共識的問題[3]。由于應用場景的不同，共識算法的側重點也不同。公有鏈大部分采用PoW算法[4]、PoS算法[5]、DPoS算法[6]和它們的變形算法，而目前落地的實際應用大多數基于聯盟鏈運行，其采用的共識算法主要是基于消息傳遞，主流算法有PBFT算法[7]、Paxos算法[8]和Raft算法[9]。

PBFT算法在區塊鏈中得到廣泛應用，但也存在一些不足，不能完全適應所有的應用場景。為了解決PBFT算法通信開銷大、節點參與共識的積極性不夠高等問題，該文提出一種基于積分制的改進的實用拜占庭算法(improved practical Byzantine algorithm based on point system，P-PBFT)。

1 相關知識

1.1 區塊鏈的類型

按照應用場景和設計體系的不同，區塊鏈可分為公有鏈、聯盟鏈、私有鏈[10]。

(1)公有鏈。

公有鏈所有節點都對外開放，每個人都可以從公有鏈中讀取數據，發送交易。在公有鏈上，每個節點都可以自由加入或者退出，網絡運行時以扁平、無分層的對等網絡拓撲結構相互連通，不存在任何中心化的服務節點，是一種完全去中心化的區塊鏈[11]。訪問門檻低，數據公開透明且無法篡改、匿名性等是其主要特點，比特幣就是公有鏈的典型代表。

(2)私有鏈。

私有鏈是指區塊鏈的開發與維護由一個組織統一管理，各個節點的讀取權限與寫入權限由該組織決定，不對公共網絡開放的區塊鏈[12]。私有鏈雖然節點權限有所限制，但區塊鏈網絡仍然運行在多個節點，其數據的安全性依舊會得到一定的保證。與公有鏈相比，私有鏈具有處理交易速度快、交易成本低、隱私保護好等特點。

(3)聯盟鏈。

聯盟鏈是一種介于公有鏈和私有鏈之間的區塊鏈，通常應用于不同的企業或組織之間。鏈上節點都有著相對應的實體，不同的實體組成聯盟，節點的加入需要聯盟授權，參與者共同維護區塊鏈的運行。聯盟鏈的讀取權限對所有節點開放，寫入和驗證權限則需要聯盟內部決定，屬于部分去中心化區塊鏈。目前已有很多聯盟鏈，比較知名的有超級賬本(hyperledger)項目[13]。

1.2 共識算法

共識算法起源于分布式系統領域，傳統共識算法一般面向分布式數據庫操作。而在區塊鏈環境下，更多的是面對拜占庭容錯問題[14]，傳統共識算法不能很好地解決這類問題，因此一系列新的共識算法被提出。常用共識算法如下:

(1)工作量證明(proof of work，PoW)。

PoW的核心思想是通過分布式節點的算力競爭來保證數據的一致性和共識的安全性。而在區塊鏈中，比特幣系統則是這一算法的最早實踐者，比特幣系統的各節點通過計算一個求解復雜但是驗證容易的SHA256數學難題來競爭記賬權，最快解決該難題的節點將獲得下一區塊的記賬權和系統自動生成的比特幣獎勵。

PoW算法雖有效地保證了區塊鏈網絡的安全性和去中心化性，但其缺點也十分顯著。PoW算法需要節點進行大量的計算，但這種計算不具有現實意義，只會帶來大量的電力資源消耗，且需要的交易確認時間過長，不適合一般的商業應用。

(2)權益證明(proof of stake，PoS)。

權益證明是為了彌補工作量證明的一些不足而誕生的，在權益證明機制中，記賬權的歸屬不再是算力最高的節點，而是具有最高權益的節點。權益體現在節點對于虛擬貨幣的所有權，在最早的PoS應用Peercoin中，權益被稱為幣齡。一個節點的幣齡越長，其在區塊鏈系統中的權力越大，挖礦的難度越低，所獲得獎勵也越多。

與PoW算法相比，PoS算法共識過程主要依靠系統內部的權益，而不需要消耗太多外部算力和資源，因此可以有效地解決PoW中算力浪費的問題，并且能夠在一定程度上縮短達成共識的時間，提升系統運行性能。

(3)委任權益證明(delegated proof of stake，DPoS)。

DPoS算法由比特股項目提出，是PoS算法的一種演化版本。DPoS算法采用了類似董事會投票的機制，系統中每個節點都是股東，權益相當于選舉票，每個節點都可以把自己的選舉票投給信任的代表。最后得票最高的一部分節點成為董事會成員，按照既定的時間表輪流對交易進行打包結算、并且生產新區塊。相比于PoS算法，DPoS減少了參與驗證區塊的節點數量，區塊可以得到更快的確認，區塊鏈系統的性能得到了進一步的提升。

(4)實用拜占庭容錯(practical Byzantine fault tolerance，PBFT)。

拜占庭容錯算法BFT最早由Pease和Lamport在20世紀80年代提出，不同于以上幾種共識算法，BFT類協議是依靠節點之間相互傳遞消息來對提案達成確定性共識結果，因此早期的拜占庭系統需要指數級的操作，所以未能得到實際應用。直到1999年Miguel Castro和 Barbara Liskov提出了PBFT(實用拜占庭容錯)算法，解決了原始BFT算法的信息傳輸復雜度太高的問題，由此實用拜占庭容錯算法在實際系統中變得可行[15]。而在區塊鏈環境下，實用拜占庭容錯算法多使用于聯盟鏈中。

1.3 P2P網絡

區塊鏈與P2P的出發點都是去中心化。

P2P網絡即對等網絡，是在同等地位的節點之間分配計算任務與網絡負載的分布式網絡架構[16]。P2P網絡模型與客戶端/服務器模型不同，P2P網絡中沒有客戶端或服務器的概念，不存在中心節點，只存在對等的同級節點。每個節點既尋求服務，同時也提供服務。P2P網絡中的節點沒有數量、范圍、時間或空間上的限制，每個節點都可以自由地加入或退出P2P網絡。

P2P網絡具有去中心化、可擴展性、健壯性、高性價比、隱私保護和負載均衡的特點[17]。在P2P網絡中，節點不需要服務器即可提供資源和服務，避免了中心服務器的瓶頸，且起到了負載均衡的效果。

從技術上來講，區塊鏈就是應用P2P的網絡架構，通過密碼學來保證數據的安全，通過共識算法來保證數據的一致性。P2P一般存在4種網絡模型，分別是：集中式、純分布式、混合式和結構化模型。區塊鏈應用依據自身的實際情況選擇不同的P2P網絡模型，比特幣采用的是混合式網絡模型，而以太坊采用的則是結構化網絡模型。

1.4 Merkle樹

Merkle樹屬于區塊鏈數據層，是區塊鏈中重要的數據結構，其基本結構如圖1所示。

圖1 Merkle樹

該樹的每個葉子節點值是對應數據的哈希值，非葉子節點是它的兩個子節點合在一起的哈希值，依次疊加，直到計算出整棵樹的根節點，最后生成Merkle根。Merkle根是由所有葉子節點值得到的，因此只要驗證Merkle根是否相等，就可以知道葉子節點的數據是否有改動。在分布式系統中，Merkle樹可以快速驗證在傳輸過程中數據否發生變化，大大降低了計算復雜度。

1.5 加密技術

加密算法是區塊鏈中不可缺少的一個環節，在區塊鏈中所涉及的加密技術主要包括非對稱加密、哈希算法和數字簽名。

非對稱加密算法是指在對數據進行加密和解密過程中使用不同密鑰的一種加密算法。非對稱加密過程中使用的密鑰成對產生，其中公開的密鑰叫公鑰，任何人都可以獲取，非公開的密鑰叫私鑰，對外是保密的。公鑰與私鑰都可以用來加解密，如果用私鑰對信息進行加密，只能用公鑰解密信息。如果用公鑰對信息進行加密，只能用私鑰解密信息。與對稱加密相比，非對稱加密無需交換密鑰且算法強度高，所以具有更高的安全性，但是其加解密過程復雜度高且耗費時間較長，一般只適合加密少量數據，適用于數字簽名、登錄驗證等場景。常見的非對稱加密算法有ECC(橢圓曲線加密)算法和RSA加密算法等。相比RSA，ECC優勢是可以使用更短的密鑰來實現與RSA相當或更高的安全性。

哈希函數也稱散列函數，是一種單向映射函數。哈希函數將輸入數據通過哈希算法生成特定長度的值，該值就稱之為哈希值。哈希函數具有單向性、不可逆等特征，逆向求解哈希函數十分困難，幾乎不能通過現有的哈希值反推出原文，因此可以有效保證信息的安全性。通過散列算法運算求得的哈希值具有固定長度，且哈希值遠遠小于輸入長度，壓縮性保證了任意長度消息壓縮映射得到確定長度散列值。哈希函數具有高度靈敏性，如果輸入的數據發生字節變化，那通過哈希運算得到的哈希值可能完全不同。哈希函數在區塊鏈中發揮了極其重要的作用，可以進行數據驗證、數字簽名，保證了區塊鏈系統中數據的安全性和完整性。

數字簽名是數字摘要技術和非對稱加密技術相結合的應用，為數字信息的完整性和發送者身份的真實性提供了強有力的保障。數字簽名的流程是發送方將自己要傳輸的消息進行哈希，得到摘要，再用私鑰將哈希值進行加密，最終得到加密數據。發送方將數字信息原文、加密后的數字摘要和公鑰一同發給接收方。同時，接收方會用相同的散列函數生成數字信息的數字摘要。然后接收方使用發送方的公鑰對消息和消息摘要進行解密，得到數字摘要。如果發送方的摘要和接收方的摘要相同，則即可證明數字信息的完整性和發送方身份的真實性。如果不同，則說明數字信息已經被篡改。

2 基于積分制的改進實用拜占庭容錯算法P-PBFT的設計與分析

2.1 PBFT算法分析

PBFT算法每次共識發生在一個視圖(view)中，視圖是連續編號的整數，每個視圖對應一個主節點，其余都是備份節點。在總節點數為n的系統中，PBFT算法所能容忍的錯誤節點數f最大為(n-1)/3。

(1)PBFT算法流程。

PBFT算法通過五個階段達成共識，如圖2所示。

圖2 PBFT算法共識流程

各階段的具體流程如下：

請求階段：客戶端節點向主節點發送請求m。

預準備階段：主節點接收到來自客戶端的請求后，給該請求分配一個序列號n，生成一個預準備消息，預準備消息的格式為，這里的v是視圖編號，d是客戶端發送的請求m的摘要。然后向所有備份節點發送預準備消息。

準備階段：備份節點接收到主節點的消息并對預準備消息進行驗證，如果驗證通過，生成準備消息并向其他節點廣播，同時將預準備和準備消息寫入消息日志，i表示節點編號。

確認階段：節點收到來自其他備份節點的準備消息，對消息內容進行驗證，若驗證通過則向所有節點發送確認消息。

回復階段：當節點完成確認階段后，向客戶端發送回復消息，當客戶端接收到f+1個不同的節點發來的相同消息時，回復階段完成，共識流程結束。

(2)視圖切換。

PBFT在視圖中執行共識流程時，如果主節點發生宕機或者成為惡意節點，導致共識流程無法進行的時候，系統會運行視圖變更協議，根據p=v mod R的規則重新選舉主節點，其中v是視圖編號，R是節點個數。

(3)PBFT算法的不足。

PBFT算法在節點數量較多的情況下，通信開銷很大，無法滿足實際系統的需要。另外，主節點選舉隨意，在實際應用中無法起到激勵節點的作用，且增大了主節點的作惡幾率，降低了系統運轉的可持續性和安全性。

2.2 P-PBFT算法設計思想

針對PBFT算法的不足，結合實際區塊鏈系統的應用情況，該文提出的P-PBFT算法對PBFT做了以下幾點改進：

(1)結合DPOS思想，成立節點委員會，委員會里的節點數目根據實際需要設置，只有委員會里的節點才可以參與共識和競爭主節點，其余的節點只進行投票與結果保存，可以降低系統的通信開銷，提升系統性能。

(2)引入積分制的概念，給每個節點設置積分，節點的初始積分可根據實際應用的需要來設置。節點使用積分進行投票，選舉參與共識流程的節點。當主節點發生錯誤從而觸發視圖切換協議的時候，扣除當前主節點的5%積分作為懲罰，然后根據積分的排名順次選舉主節點，這樣可以保證主節點的可靠性，提高節點競爭主節點的積極性。

(3)設置積分衰減周期T，按70%的比例減少節點的積分，防止系統過度中心化。

2.3 P-PBFT算法流程

P-PBFT算法流程如圖3所示。

圖3 P-PBFT算法流程

具體步驟如下：

第一步：客戶端發送請求，系統進行響應，如果系統存在主節點，直接進入第二步。系統不存在主節點的時候，所有節點投票選舉出委員會節點和主節點。

第二步：委員會里的節點走共識流程，共識成功，主節點增加5積分，委員會節點增加3積分，其余節點增加1積分。如果主節點發生錯誤從而觸發視圖切換，則進行第三步。

第三步：扣除當前主節點的5%積分，積分排名第二的節點當選為主節點。

此外，每T個周期后，系統進行積分衰減，每個節點減少70%的積分，并且重新選舉委員會成員。

2.4 P-PBFT算法通信開銷分析

設定系統的節點個數為N，對于PBFT算法，參與共識的節點個數即為N，三階段共識的通信開銷為2N(N-1)。對于P-PBFT算法，設定委員會節點個數為M，則三階段共識的通信開銷為2M(M-1)，M≤N，且隨著M/N的減小，通信開銷的降低會更加明顯。

3 仿真實驗及結果分析

該文基于Go語言實現了一個小型區塊鏈系統，分別運行PBFT算法和P-PBFT算法，(每秒完成的交易數量，單位為個/秒)進行對比，以檢驗算法的總體效果。

實驗環境是：操作系統為Windows10，CPU為Intel (R) Core (TM) i5 - 6300U 2.30 GHz，內存為12 GB。算法實現語言為Go，測試工具為Apache-JMeter。

(1)固定數量節點在不同時刻的吞吐量測試。

測試基于本地10個服務端節點，其中委員會節點數量設置為4個，另開一個客戶端節點，負責向服務端發送需要共識的交易。開啟Apache-JMeter進行壓力測試，配置50個線程，創建Http請求，共識完成則記錄一次請求成功，結果如圖4所示，橫坐標為時間，縱坐標為吞吐量。

圖4 固定數量節點在不同時刻的吞吐量對比

可以看出，不同時刻吞吐量略有不同，后續測試將觀察平均吞吐量。

(2)不同節點數量下的吞吐量測試。

實驗分別開啟6節點、8節點、10節點、12節點、14節點、16節點、18節點，作為服務器端，其中P-PBFT算法的委員會節點個數設置為6，另開客戶端接口，取平均數據吞吐量，結果如圖5所示，其中橫坐標為節點數，縱坐標為吞吐量。

圖5 不同節點數量下的吞吐量對比

可以看出，在節點數量較少的情況下，P-PBFT算法和PBFT算法的吞吐量相差不大。這是因為節點數量較少的時候，P-PBFT算法參與共識的節點數量和PBFT算法相近，且選舉委員會節點也需要消耗一定的資源和時間。

(3)積分變化測試。

對10個節點分別編號為N1～N10，其中N1、N2、N3、N4的積分賦值為10、8、6、4，其余節點的積分賦值為1，N1、N2、N3、N4成為委員會節點，N1節點擔任主節點，設置衰減周期為10分鐘。經過十輪交易之后，各節點積分如表1所示。

表1 十輪交易前后積分對比

可以看出，隨著共識成功的交易量增加，委員會里的節點與其他節點的積分差距擴大，可以提高參與共識的節點的積極性。

當將主節點端口關閉(即模擬主節點發生錯誤的情況)時，客戶端發送請求，會觸發視圖切換協議，主節點被扣除5%的積分，積分排名第二的N2就成為新的主節點。系統運行十分鐘后，所有節點積分全部扣除70%，并重新進行委員會節點選舉。

4 結束語

針對實用拜占庭算法PBFT在聯盟鏈節點數較多的情況下性能欠佳的問題，對其加以改進，設計了一種基于積分制的共識算法P-PBFT。結合DPOS思想并引入積分制度，降低了算法通信開銷，可以支持更多的節點。改進主節點的選舉方式，提高了節點參與共識的積極性；設置積分衰減機制，避免了聯盟鏈中可能出現的過度中心化問題，使得算法更加適應實際的區塊鏈系統。實驗與分析表明P-PBFT算法能有效地減少系統通信開銷，提高系統吞吐量。