惠二鑫 趙鵬 彭俊霞

（太原師范學院 山西省晉中市 030619）

區(qū)塊鏈技術(shù)隨著比特幣的出現(xiàn)而問世，其并非一種新的技術(shù)，而是將分布式存儲、對等網(wǎng)絡(luò)、非對稱加密、共識機制等計算機技術(shù)整合起來的新型應(yīng)用模式[1]。具有去中心化、公開透明、共同維護及不可篡改等特性。

最為區(qū)塊鏈核心技術(shù)的共識算法，是近年來分布式系統(tǒng)研究的熱點。是保證分布式系統(tǒng)中各節(jié)點數(shù)據(jù)一致性的關(guān)鍵，目前，區(qū)塊鏈系統(tǒng)中所使用的經(jīng)典共識算法有PoW 算法，PoS 算法、BFT 算法、PBFT 算法等，不同的算法有各自的優(yōu)缺點。許多學者在共識策略、一致性協(xié)議以及區(qū)塊結(jié)構(gòu)等方面對PBFT 算法進行了改進，但是該算法應(yīng)用在一些需要不斷擴張的領(lǐng)域中，依舊存在節(jié)點網(wǎng)絡(luò)靜態(tài)不可變的問題[2]，因此解決PBFT 算法動態(tài)性差成為一個急需解決的問題。

1 實用拜占庭容錯算法

實用拜占庭容錯算法（Practical Byzantine Fault Tolerance, PBFT）[3]是在1999年由Miguel Castro 和Barbara Liskov 提出的。能夠在失效節(jié)點不超過（n-1）/3（n 為集群節(jié)點總數(shù)）的情況下確保共識系統(tǒng)的安全性和一致性[4]。PBFT 共識機制中所有節(jié)點需要保證數(shù)據(jù)達成最終一致性，為此PBFT 需進行一致性協(xié)議、檢查點協(xié)議和視圖更換協(xié)議[5]來確保各個節(jié)點的行動一致。

一致性協(xié)議是PBFT 共識算法的核心部分，主要通過預(yù)準備、準備和確認三個階段來保證數(shù)據(jù)的一致性。在集群中每一次共識都是在某一個視圖狀態(tài)下進行的，且每個視圖狀態(tài)下只存在唯一的主節(jié)點，共識集群中的其他節(jié)點都是副本節(jié)點。共識的具體過程如圖1 所示，其中C 是客戶端，副本0 是主節(jié)點，副本3 是失效節(jié)點。

在傳統(tǒng)PBFT 算法的分布式系統(tǒng)中，所有節(jié)點相互獨立，且節(jié)點發(fā)生拜占庭錯誤也相互獨立，共識節(jié)點和拜占庭的節(jié)點的個數(shù)分別為N、f，兩者間的約束條件如公式（1）所示：

從上面公式可以看出，在分布式系統(tǒng)中，共識節(jié)點的總數(shù)和可接受的拜占庭節(jié)點數(shù)與密切相關(guān)。由于PBFT 共識機制本身沒有動態(tài)機制，不能進行動態(tài)共識，因此每一輪的共識節(jié)點都是固定的。這個特性在聯(lián)盟鏈的實際應(yīng)用中有很多缺點。例如，新的節(jié)點無法加入到網(wǎng)絡(luò)中；作惡節(jié)點也無法從網(wǎng)絡(luò)中退出。

2 算法改進

2.1 算法思想

針對PBFT 算法節(jié)點無法動態(tài)感知的問題，本文將PBFT 算法進行改進，首先增設(shè)一個額外的候補節(jié)點集合，在新增的候補節(jié)點中進行備選主節(jié)點的選取，讓節(jié)點可以動態(tài)增加或刪除。DPBFT算法思路如圖2 所示。

圖2：DPBFT 算法思路

2.2 增加候補節(jié)點

將系統(tǒng)中的節(jié)點分為兩部分，一部分是共識節(jié)點；另一部分是候補節(jié)點。共識節(jié)點負責系統(tǒng)的共識，候補節(jié)點用于備選主節(jié)點的選取。在候補節(jié)點集合中存放的是新加入系統(tǒng)的節(jié)點和共識過程中發(fā)生拜占庭錯誤的節(jié)點。

共識節(jié)點集合和候補節(jié)點集合用R1、R2 表示，其定義如下：

當R1 中主節(jié)點拜占庭錯誤或其他共識節(jié)點退出系統(tǒng)中時，R2中選舉產(chǎn)生的備用主節(jié)點將其替換，被替換掉的節(jié)點將淘汰到R2集合中，保證了系統(tǒng)中共識節(jié)點數(shù)量的穩(wěn)定，實現(xiàn)了節(jié)點的動態(tài)替換。

在候補節(jié)點集合R2中信任節(jié)點的選舉方式采用投票選舉機制。為了提升節(jié)點替換效率，R1 中節(jié)點的共識和R2 中信任節(jié)點的選取是同步進行的。主節(jié)點發(fā)生拜占庭錯誤時，使用R2 中選出備選主節(jié)點將其替換，整個過程省去了視圖切換。

此外為預(yù)防發(fā)生拜占庭問題的主節(jié)點重復當選主節(jié)點的可能，增加一個參數(shù)H，候選主節(jié)點的計算公式如（4）所示：

其中h 表示區(qū)塊高度，R2 為候補節(jié)點集合v，表示當前視圖編號P 為主節(jié)點選取結(jié)果。

將視圖切換過程和主節(jié)點的選舉相結(jié)合，可有效減少視圖切換次數(shù)，降低了整個共識過程的共識時延。

2.3 候補主節(jié)點選取

第一步：在R2 中通過公式（4）計算出候選節(jié)點，該向其他節(jié)點發(fā)送自己將要選舉的消息。

第二步：當R2 中其他節(jié)點收到候選節(jié)點發(fā)送的消息后，進行確認。如果R2 集合中有半數(shù)以上的節(jié)點同意，候選節(jié)點將被選舉為備用主節(jié)點，否則重新選舉。

第三步：為防止在選舉的過程中參與投票的節(jié)點發(fā)生超時而導致惡性循環(huán)選舉問題的出現(xiàn)。改進后的算法為每個節(jié)點設(shè)置唯一的超時值，當參與投票時節(jié)點會有序的進行投票。有效避免所有節(jié)點的得票都不足一半情況。節(jié)點分先后，最終確定一個唯一的備用主節(jié)點，用來替換共識集合R1 中的問題節(jié)點。選舉過程流程圖如圖3 所示。

圖3：選舉過程

2.4 算法的整體流程

根據(jù)改進算法的設(shè)計思想和具體設(shè)計，給出DPBFT 算法的整體流程。如圖4 所示。

圖4：算法整體流程

DPBFT 算法的總流程如下：

（1）備選主節(jié)點成功選舉

（2）request 階段：客戶端向主節(jié)點發(fā)提案消息。

（3）pre-prepare 階段：在此階段主節(jié)點向所有副本節(jié)點發(fā)送預(yù)準備消息；

（4）副本節(jié)點驗證收到的提案消息和主節(jié)點的狀態(tài)。如果接收的提案消息正確，進入階段；否則接受的提案消息被丟棄，轉(zhuǎn)到（2）。如果主節(jié)點發(fā)生拜占庭錯誤，視圖將進行切換，轉(zhuǎn)到（1）；

（5）prepare 階段：向所有副本節(jié)點發(fā)送準備消息；

當某個節(jié)點收到超過2f+1 準備消息并且完成驗證，告知客戶端發(fā)送共識達成，否則跳轉(zhuǎn)到（1）；

（6）reply 階段：若有f+1 個副本節(jié)點向客戶端進行了反饋，則認為系統(tǒng)共識達成。

3 實驗驗證及分析

本次實驗測試的是在系統(tǒng)運行一段時間后觀察PBFT 算法和DPBFT 算法中共識節(jié)點和拜占庭節(jié)點數(shù)。實驗將傳統(tǒng)PBFT 和改進后的算法中共識節(jié)點設(shè)置為10 個（包含3 個拜占庭節(jié)點）；另外在候補集合中添加3 個節(jié)點，在實驗開始前候補集合中不設(shè)置拜占庭節(jié)點。實驗結(jié)果如圖5 所示。

圖5：算法效率對比實驗

分析實驗結(jié)果可知，當系統(tǒng)完成3 次視圖切換后，PBFT 算法中拜占庭節(jié)點的個數(shù)始終為3。而DPBFT 算法共識集合中的拜占庭節(jié)點在每次視圖切換完成后都會添加到拜占庭節(jié)點候補集合中，此時候補節(jié)點中的拜占庭節(jié)點會加1。直到三次視圖切換完成，PBFT 算法中的拜占庭節(jié)點全部轉(zhuǎn)移到候補節(jié)點中。

4 總結(jié)展望

本文針對PBFT 算法中節(jié)點網(wǎng)絡(luò)無法動態(tài)變化，提出一種動態(tài)性的共識算法DPBFT（ Dynamic Practical Byzantine Fault Tolerance）。改進的算法通過增設(shè)額外的候補節(jié)點集合，在新增的候補節(jié)點中進行備選主節(jié)點的選取，當主節(jié)點出現(xiàn)拜占庭錯誤時，使用候補節(jié)點集合中的備選主節(jié)點進行替換，使系統(tǒng)中共識節(jié)點的數(shù)量可以動態(tài)增加或減少。

下一步將在DPBFT 算法的吞吐量上進行研究探索，在不影響系統(tǒng)共識效率的基礎(chǔ)上增加吞吐量，使其可以更好的應(yīng)用商業(yè)領(lǐng)域中。