基于節點動態評分機制的分組共識算法

摘 要：針對實用拜占庭容錯（practical Byzantine fault tolerance，PBFT）共識算法三階段流程通信開銷大，主節點隨機選取且缺乏獎懲機制等問題，提出基于節點動態評分機制的分組共識算法（dynamic scoring practical Byzantine fault tolerance，DS－PBFT）。首先，優化一致性協議，簡化三階段通信流程從而提高共識效率；其次，提出節點評分分組機制，通過節點在共識過程中的歷史行為進行評分，并分為共識組和候選組，降低惡意節點參與共識過程的可能性；最后，提出動態過程選擇參與共識的節點，優化視圖切換協議和垃圾回收機制，減少參與共識的節點數量，從根本上提高共識效率。用Docker容器模擬多個節點的仿真實驗表明，在網絡穩定、可信節點較多的聯盟鏈中，提出的DS－PBFT共識算法在共識時延、吞吐量、容錯性和通信復雜度等方面比PBFT共識算法及其他改進算法相比具有更好的性能，能夠快速達成共識，提高共識效率。

關鍵詞：區塊鏈； 共識算法； 實用拜占庭容錯算法； 節點動態評分； 分組共識

中圖分類號：TP311文獻標志碼： A文章編號：1001－3695（2024）04－004－0989－06

doi：10.19734/j.issn.1001－3695.2023.07.0348

Group consensus algorithm based on node dynamic scoring mechanism

Shen Xueli， Li Xinru

Abstract：In response to the issues of high communication overhead random primary node selection and the absence of incentive mechanisms in the three－stage process of PBFT consensus algorithm，as well as problems with，this paper introduced a new grouped consensus algorithm named DS－PBFT.Firstly，this paper optimized the consensus protocol simplified of the three－phase communication process，thereby enhancing consensus efficiency.Secondly，this paper proposed a node scoring and grouping mechanism，where nodes received scores based on their historical behavior during the consensus process and fell into consensus and candidate groups，reducing the likelihood of malicious node participation.Lastly，this paper introduced a dynamic process for selecting nodes to participate in consensus，optimized view－change protocols and garbage collection mechanisms to fundamentally reduce the number of participating nodes，resulting in enhanced consensus efficiency.Using Docker containers to simulate multiple nodes，the experimental results show that in a consortium blockchain with network stability and a significant number of trusted nodes，the proposed DS－PBFT consensus algorithm outperforms the PBFT consensus algorithm and other improved algorithms in terms of consensus latency，throughput，fault tolerance，and communication complexity.It can quickly achieve consensus and improve consensus efficiency.

Key words：blockchain； consensus algorithm； practical Byzantine fault－tolerant algorithm； node dynamic scoring； group consensus

0 引言

區塊鏈是一種點對點的分布式存儲系統，具有安全性能好、容錯性高，適合加密等特性［1，2］，正是因為區塊鏈的這些特點，現如今已經與大數據［3］、云計算［4］及人工智能［5］四個領域合稱為信息產業里的黑科技，而其中的底層核心——共識算法［6］也慢慢進入大眾視野。

早期共識算法起源于Lamport提出的分布式算法Paxos［7～9］，但其有著很大的局限性，無法在現實生活中實現。隨后Stanford提出實用的Raft算法［10］（replication and fault tolerant）；Lamport等人［11］提出拜占庭將軍問題；文獻[12]為解決此問題提出了較為經典的PBFT算法；中本聰提出工作量證明算法［13～15］（proof of work，PoW），但其應用在區塊鏈中性能較差；權益證明算法［16］（proof of stake，PoS）基于此缺陷做了改進，但中心化較為明顯，不符合區塊鏈去中心化的特性，在其發展過程中又有許多算法嘗試解決這類問題，將PoW和PoS相結合，形成混合共識機制，PoW作為競爭記賬權的方法，同時PoS作為防止分叉的方法。類似這樣的結合算法還有很多，例如Tendermint［17］及其改進算法HoneyBadger［18］將PoS和PBFT結合、Tangaroa共識算法［19］將PBFT和Raft算法結合，把兩者的優點統一，保留了Raft的簡單易理解性和PBFT識別拜占庭節點的優勢。由于PoW、PoS和代理權益證明（delegated proof of stake，DPoS）很可能會導致分叉［20］，需要發行代幣，而PBFT算法則可以做到無分叉，不依賴代幣，同時容忍拜占庭節點。由此來看，PBFT算法是較理想的共識算法，但PBFT算法仍有不足之處，如三階段流程通信開銷大、節點全部參與共識過程、不適應動態網絡等，所以很多專家學者對PBFT進行了改進［21～25］。

PBFT算法中分為一致性協議、視圖切換協議和檢查點協議三種協議，很多改進算法都是基于以上三方面的優化。文獻［21］提出隨機選取主節點的改進PBFT共識算法，優化三段式流程降低通信復雜度，同時節點可以動態加入、退出，提高系統可用性，但主節點隨機選取使得共識過程缺少安全性，容易觸發視圖切換協議；文獻［22］提出使用環簽名的改進PBFT算法，用節點簽名時自動成環的方式，增加共識的動態性，同時優化視圖切換效率；文獻［23］提出推薦信任模型的改進拜占庭容錯共識算法，加入了獎懲機制，不隨意選取主節點和共識節點，提高共識安全性，但其通信開銷大的問題仍然存在；文獻［24］也提出基于信任評估模型的PBFT共識算法，雖然將共識節點分組，提高共識效率，但一致性協議過程并沒有改變，通信復雜度也僅僅略小于O（n2）， 其中n是參與共識的節點數量；文獻［25］提出通過聚類方法將節點分類的改進PBFT共識算法，根據節點在共識過程中的響應情況作為數據維度，并將K－means+ +聚類算法與之結合，減少參與共識過程的節點數量，提高共識節點質量，但三階段的通信次數并沒有很大程度改進。

為了解決改進后的PBFT算法仍有較大通信開銷，主節點隨機選取，有一定的局限性，不能在動態網絡中完成共識，無法識別系統中的拜占庭節點等問題，本文基于自適應選取共識節點提出了基于節點動態評分機制的分組共識算法（DS－PBFT）。

1 PBFT算法相關理論及技術

1.1 PBFT算法流程

PBFT算法也稱為實用拜占庭容錯算法［26，27］，是經典的一致性算法，最初是作為一種保證分布式網絡完整性的機制而發展起來的［28］，在算法中要求所有節點必須參與投票才能添加下一個塊，誠實節點數量只有大于等于所有節點數的三分之二才能達成共識，節點之間進行消息交換，保證了網絡的完整性，但三階段流程通信開銷大，共識效率低，浪費了許多時間和精力，PBFT算法共識流程如圖1所示。

a）預準備階段（pre－prepare）：主節點向其他節點廣播消息，提議一個新的區塊，包括區塊內容和序列號。其他節點接收到此消息后對消息進行驗證，如果合法則發出“準備”消息，否則不作處理。

b）準備階段（prepare）：節點從主節點接收消息后，會檢驗這個消息的正確性，并將“準備”消息廣播給其他節點，以表示自己已經接受該消息。節點在此階段還要等待來自其他節點的“準備”消息，以確保有足夠多的節點接受了該消息。

c）確認階段（commit）：節點接收到足夠多的“準備”消息后，將“確認”消息發送給其他節點，表示該消息已經被確認，可以寫入區塊鏈。節點在此階段還要等待來自其他節點的“確認”消息，以確保有足夠多的節點確認了該消息。

d）回復階段（complete）：節點收到足夠數量的“確認”消息后，確認該消息已經寫入區塊鏈，并將其傳播給其他節點，以便更新狀態。

1.2 PBFT協議

PBFT算法包括以下協議：

a）一致性協議是對共識過程的描述，該過程用于對請求達成一致［29］。

b）檢查點協議可以安全地丟棄以前的日志消息，降低節點的內存開銷，也可以幫助落后的節點同步最新狀態。

c）視圖切換協議用于主節點為惡意節點的情況，幫助系統更換主節點，成功達成共識。

為提高系統效率，可以從以上三方面進行優化。

1.3 PBFT算法缺點

a）一致性協議需要三階段廣播，廣播數量多，并且耗費資源，降低共識效率，使用X來定義完成共識過程的消息數量，N為共識節點數量，則關系如式（1）所示。

X=2N2-2N （1）

b）隨機選取主節點存在安全風險，若多次選擇惡意節點為主節點，會顯著降低共識效率，浪費系統資源，并帶來系統風險。

c）客戶端只能向主節點發送消息，如果消息過多，主節點就會有很大負擔，并不適用于區塊鏈點對點（peer－to－peer，P2P）的網絡環境［30］。

2 改進PBFT共識算法

2.1 算法思想

傳統PBFT及其改進算法要求所有節點全部參與共識，再加上PBFT算法的三階段通信流程導致其通信開銷很大，達到指數級別，同時為了防止惡意節點成為共識節點，甚至成為主節點，有的算法提出可以依據歷史行為累計信譽值，讓信譽值高的節點去完成共識，此算法雖然可以保證共識過程的安全性，卻使其他節點失去積極性，發生信譽值累計造成中心化程度過高的現象。為了解決以上問題，本文提出基于節點動態評分機制的分組共識算法。

針對PBFT三階段的通信流程，優化了一致性協議，將傳統PBFT在準備階段和確認階段的兩次兩兩交互簡化為直接通信。根據改進PBFT算法所展現出來的優化思路發現，這種共識算法可快速完成共識，提高共識效率。

針對避免惡意節點成為共識節點或成為主節點和避免傳統PBFT及其改進算法要求所有節點全部參與共識的思想，提出依據歷史表現計算分數給節點評分，對評分進行降序排列并依據評分的分數動態計算出下一次參與共識的節點數量，從而降低總是選取固定分值高的節點成為主節點的可能性，解決了得分機制類共識算法產生節點分值累計問題。在保證共識過程安全性的同時減少參與共識的節點數量，從根本上提高共識效率，而且每次共識不一定是相同節點參與的，使節點在共識中具有積極性。減少參與共識的節點數量是優化PBFT共識算法時的一個可能的優化方向。其優勢如下：a）降低延遲：PBFT的性能受到網絡通信和消息傳遞的延遲影響，減少參與共識的節點數量可以減輕消息傳遞和通信的負擔，從而降低整體共識延遲；b）降低計算成本：共識算法要求參與節點執行計算、簽名和其他操作，減少節點數量可以降低計算成本和資源消耗；c）簡化協調：較少數量的節點可能會簡化共識協議的協調過程并降低復雜性。

然而，仍需考慮以下幾點：

a）安全考慮：PBFT算法是一種容錯共識算法，可以容忍一定數量的拜占庭錯誤（惡意行為）。減少節點數量可能會降低系統抵抗攻擊的能力。然而，本文提出了一種基于節點動態評分機制的分組共識算法，根據節點的歷史行為進行評分。通過這種方法檢測到的惡意節點取消參與下次共識過程的資格，只能對共識過程作出反應。因此，在減少節點數量時，可以確保系統仍足夠安全，能夠容忍一定數量的惡意節點。

b）分布式：PBFT的優勢之一是其分布式性質，可以在去中心化環境中實現共識。減少節點數量可能會導致中心化風險，并降低系統的分布式性質。然而，本文提出動態計算參與共識的節點，共識節點和其數量都是在歷史行為下不斷變化的。按節點評分降序排列所有節點，并對它們進行分組，從而可以解決節點分數累計的問題。

針對惡意節點成為主節點時視圖切換協議和垃圾回收機制過于復雜、開銷大的問題，提出節點動態選擇參與共識的節點優化視圖切換協議和垃圾回收機制。根據以上算法思想，本文算法可以降低系統中心化程度，在抵御惡意節點的攻擊下提高共識效率，并保證區塊鏈系統的安全性和可靠性。

2.2 算法符號

a）在本文算法中，C代表客戶端自己的標識，RC代表客戶端的請求操作，m代表客戶端所發出的請求，v代表視圖編號，n代表請求的序列號，h代表請求的哈希值，f代表拜占庭節點的個數，t代表時間戳，S代表簽名，I代表節點。

b）本文算法對節點數是有一定要求的。如果系統中有f個拜占庭節點，則必須讓所有節點的總數比3f+1大才可以完成共識， 一般在實驗條件下，為了減少系統負載，會讓其等于3f+1。

c）本文算法對節點進行分組，可分為共識節點組和候選節點組。共識節點組用A表示，包括主節點和從節點，第i個共識節點用Ai表示，候選節點組用B表示。

2.3 共識過程描述

首先，初始化所有節點，并將每個節點的初始分數設為50分。其次，將這些節點分成共識節點組和候選節點組。在初始化階段，節點的排列順序是隨機的。在共識節點組中，節點將參與共識過程；而在候選節點組中在達成共識時，節點會更新其本地狀態，暫時暫停參與實際的共識流程。整個系統中共有N個節點，允許存在最多f個拜占庭節點，要求共識節點的數量滿足條件K≥3f+1，以確保系統能夠在任何情況下都達成一致，這里的K表示共識節點的數量，同時定義主節點的選擇策略為p=v mod K，其中p代表主節點，v代表視圖號，具體DS－PBFT算法共識過程如圖2所示。

a）請求階段：客戶端節點向主節點發起請求消息〈〈 Request，C，RC，t〉，SC〉，主節點接收提供的Request消息。

b）預準備階段：客戶端節點的請求被主節點接收后，觸發預準備階段。主節點會向所有副本節點廣播預準備消息〈〈Pre－prepare，v，n，h〉，SP，m〉。當副本節點接收到Pre－prepare消息時，它會對該消息進行驗證。如果驗證成功，副本節點將進入準備階段，準備參與后續的共識過程；然而，如果驗證失敗，副本節點將不會采取任何進一步的行動。

c）準備階段：如果節點成功驗證了接收到的預準備消息，那么該節點將進入準備階段。在準備階段，從節點會向主節點發送確認已收到的準備消息〈〈Prepare，v，n，h，I〉，SI〉。如果主節點接收到一定數量的準備消息，將進入確認階段。

d）確認階段：一旦主節點收到超過2f+1個相同的準備消息，就會認為共識已經達成。在這種情況下，主節點將向所有節點（包括候選節點）確認達成的共識結果〈〈Commit，v，n，h〉，SP，m〉，同時更新所有節點的得分。將得分按高到低進行排序，具有最低分的m個節點進入候選組，并且附加到候選組的末尾。將候選組中具有最高分數的m個節點添加到共識節點組中，至此，一輪共識過程結束。DS－PBFT的偽代碼如下：

input：C，RC，t，Si，m，n，h，v，P，I；

begin

while 〈〈Request，C，RC，t 〉，SC〉=TRUE do

Broadcast〈〈Pre－prepare，v，n，h〉，SP，m〉；

if 〈Pre－prepare〉=TRUE{

Broadcast〈〈Prepare，v，n，h，I 〉，SI〉；

Receive〈Prepare，v，n，h，〉，Sn〉；

}

else do nothing；

if 〈Prepare〉=TRUE{

Broadcast 〈〈Commit，v，n，h〉，SP，m〉；

}

else do nothing；

if result{i}gt;（2f+1） {

the master node will broadcast the result{i}//主節點廣播共識結果

the consensus nodes will update the result to their own state machines//共識節點完成共識并更新共識結果

}

output：result{i}；

end

2.4 節點動態評分機制

為了提高系統效率，必須減少主節點視圖更換次數，使無惡意、安全的節點選為主節點，DS－PBFT算法應用了基于節點動態評分機制的分組共識算法，依據節點以歷史行為的評分將節點劃分為兩種類型：一種類型被稱為共識節點，其功能是參與共識過程，其數量為N-f；另一部分為候選節點，其數量為f，不參與共識過程，但對共識結果作出反應。在DS－PBFT算法中，每個節點都會維護節點的分數，并依照這個評價來選取主節點，節點得分高表示節點可信，在共識過程中表現良好。在節點開始共識之前，初始化節點分值把每個節點的初始得分設置為50，并使其限制在0～100。得分規則如下：節點分為共識成功、共識失敗和未參與共識三種狀態，取最近三輪次共識的和作為節點的得分，具體得分規則如表1所示。

系統依據最近三個輪次的共識行為來確定節點的得分情況，將得分累加即為節點的新分數，本文算法避免了隨機性，使系統能夠區分惡意節點，并提高共識過程的安全性和穩定性，同時，未參與共識的節點仍然需要少量加分，其目的是增加共識過程的動態性，并提高每一個節點的積極性，使每個歷史表現良好的節點都有概率參與到共識過程，防止出現共識中心化問題。

隨著節點數量的增多，傳統PBFT算法要求所有節點均參與共識過程，這就必然導致系統時延增加。為此，本文提出節點分值計算，公式如下：

其中：Scorei表示第i輪次節點的平均得分情況，Smi代表節點m在參與第i輪共識時候的得分，ΔSmi代表節點m在第i輪共識時候得分的偏差，N代表總體節點數量。

由式（2）計算每輪共識的節點平均得分，并且規定系統節點初始得分為50，在共識過程中分值確保在50≤Scorei≤100，提出用節點得分來規劃下一輪參與共識的節點數量，如式（3）所示。

其中：Number為預計分配的共識節點數量。由式（3）可以看出，當節點平均分數在初始狀態為50時代表著所有節點都參與共識過程，而當節點平均分數不斷趨向上限100時，發現共識節點為所有節點的2/3。由此可以得出結論，在共識過程中拜占庭節點數量較少甚至沒有拜占庭節點時，在經過幾次共識輪次后，共識節點的數目將逐漸接近總節點數的2/3。可將節點按照分值降序排列，從高到低選取參與共識的節點，使得分高的節點作為共識節點，更能保證共識過程中的安全性，節點權限如表2所示。

在上述所提出的優化方案中，由于減少了共識節點的數量，在拜占庭節點較多的情況下容易存在安全問題，由此提出在共識過程失敗時，將所有節點的平均分值統一減少15，通過式（3）可以保證在參與下一輪共識過程中共識的節點數量會增加，以降低可能出現的安全風險，并重新對共識失敗的消息進行共識，降低共識失敗的概率。

本文提出的依據節點分值選取共識節點，可以確保參與共識的節點大多都是較為誠實的，而惡意節點在經過多個輪次后會進入到候選組，并不參與共識過程，僅僅只是對共識過程作出反應。由此可以保證，在惡意節點較少的情況下，共識失敗的概率很低，共識節點的數量將趨向于總節點數的2/3。而在惡意節點較多的情況下，系統能夠自動計算出參與共識節點的數量，以避免持續的共識失敗。

因此，本文中提出的基于節點動態評分機制的分組共識算法可以根據不同的歷史行為進行動態調整，使誠實節點組成共識組參與共識過程，提高共識效率。

DS－PBFT算法的流程如圖3所示。

2.5 視圖切換協議和垃圾回收機制的優化

2.5.1 優化視圖切換策略

視圖切換是指若主節點是拜占庭節點，在指定時間內未能發出共識請求消息或請求超時，其余從節點可以發出替換視圖請求，推翻主節點，并重新選擇可信主節點參與。如果發現主節點被推翻，將再次切換新的視圖，保存上一階段完成共識的區塊，未完成共識的區塊將被丟棄，新的主節點選出后，在前一階段被丟棄的區塊將重新達成共識。新視圖開始時，會及時同步和校驗全局節點，從而保證數據的完整一致性，等待下一輪共識。傳統PBFT算法的視圖切換主節點的選擇根據式（4）確定。

P=v mod K （4）

其中：P為新選舉的主節點編號，主節點編號為v，節點總數為K。此時是用輪詢的方式切換傳統的一致性協議視圖， 這種隨機的方式有很大概率使惡意節點成為主節點，具有一定的風險性。針對該問題，提出基于歷史表現的節點評分機制，對一致性協議的視圖切換策略進行改進，以節點得分作為主要參考指標，根據以往的歷史表現，將得分按高到低進行排序，得分高的節點將大概率選為新的主節點，可以減少視圖切換次數，降低惡意節點成為主節點的可能，同時提高共識效率和系統安全性。

2.5.2 優化垃圾回收策略

在傳統的PBFT算法中，通常周期性執行垃圾回收機制，這樣做的目的是避免因為網絡的延遲節點收到不一致的信息，確保系統的正常運行，同時防止過多的日志信息占用空間，需要對舊的日志消息進行及時清除，要確定節點之間通信同步，必須保證有至少f+1個節點去執行消息，所以導致每次垃圾回收機制會產生巨大的開銷。

而優化的DS－PBFT算法能夠及時更新節點的得分來完善垃圾回收機制，當執行一致性協議的節點得分超過閾值時，在完成一致性協議之后，可以運行垃圾回收機制，刪除本地舊的交易日志信息，減少網絡通信消耗，并將一定范圍內歷史得分高的節點隨機分配新的高分，使得分最高的節點成為新的主節點，增加共識機制的動態性。

3 理論與實驗結果分析

3.1 理論分析

3.1.1 安全性分析

傳統PBFT算法以輪詢方式選取主節點，有一定的概率會選取拜占庭節點，一旦觸發視圖切換協議，將延誤共識過程，而且下一個主節點仍以此方式選取主節點，風險并沒有下降。本文提出的DS－PBFT算法采用節點動態評分機制的分組共識算法，根據節點歷史表現計算每個節點的分值，并以此分組，使得分較高的節點大概率成為共識節點。DS－PBFT算法與普通的僅僅增加獎懲機制的改進算法不同，DS－PBFT算法動態地計算出下一次共識過程中共識節點的數量，使得每一次共識輪次中參與共識過程的節點數目有差別，并讓分低的節點進入候選組，不讓其參與共識過程，提高共識過程安全性。

3.1.2 共識效率分析

傳統PBFT算法要求所有節點共同參與共識過程，節點與節點之間兩兩交互，使得共識效率不高，消耗大量資源。本文提出的DS－PBFT算法從以下三個方面提高了共識效率：a）優化一致性協議，簡化三階段流程，減少節點之間的通信次數；b）提出節點動態評分機制，依據節點的歷史行為計算節點得分，使共識節點都是表現良好的節點，降低視圖切換的概率；c）提出依據節點評分動態選取參與共識的節點，能夠減少參與共識的節點數量，從根本上提高共識效率。

3.2 實驗結果分析

3.2.1 實驗環境

本文實驗采用Docker容器模擬多個節點，對比傳統PBFT及其改進算法，分析改進算法的優缺點。實驗環境為Ubuntu 18.04操作系統，16 GB系統內存，CPU為Intel Core i7處理器，Docker Engine容器引擎。在進行改進PBFT共識算法的仿真實驗中，通過在節點的配置中指定其角色，可以將節點區分為主節點和從節點，從而模擬實際系統中的不同角色和行為，本實驗使用Docker容器進行模擬。首先，為PBFT節點編寫一個Dockerfile，并創建一個Dockerfile來定義改進PBFT節點的鏡像，其中包含了所需的操作系統、軟件依賴和節點配置，設置節點的運行環境，并指定節點的角色（主節點或從節點）。隨后，構建好的鏡像被用來為50個節點運行容器，每個容器被分配了一個不同的端口，以便進行互通。在Docker容器內部，使用一個配置文件來定義每個節點的配置，包括節點ID、網絡地址和角色，保證每個節點是一個獨立的實體，具有自己的身份、狀態和行為，通過將每個節點放置在一個獨立的Docker容器中，可以隔離節點的運行環境，使得每個節點在一個相對獨立的虛擬環境中運行。根據PBFT共識算法，若有f個拜占庭節點，則節點總數不少于3f+1。從吞吐量、延遲、容錯性和通信復雜度四個方面對PBFT算法、使用信譽值作為節點共識的投票權重來對抗Sybil攻擊的算法（robust and improved PBFT protocol for blockchain，RIPPB）［31］、基于分層和分組的BFT共識算法（hie－rarchical and group－based Byzantine fault tolerant consensus algorithm，EBFT）［32］和本文DS－PBFT算法展開對比實驗，通過實驗結果對四種算法的性能進行分析。

3.2.2 吞吐量

吞吐量定義為系統在單位時間內處理一個請求的事物量，吞吐量越高處理的事物量越多，設置PBFT、RIPPB、EPBFT和DS－PBFT四種共識算法分別在5、10、15、20、25、30、35、40、45、50個節點中，進行30次實驗設置事件量為1 200，計算30次重復實驗的平均值為吞吐量，TPS（transaction per second）表示系統吞吐量，計算公式如式（5）所示。

TPSΔt=TransactionsΔt/Δt （5）

其中：Δt表示從交易信息發出到區塊存儲完成的時間，即出塊時間；TransactionsΔt表示每個區塊在出塊的時間間隔內完成交易的數量。系統的吞吐量還與網絡環境和塊大小有關，區塊越大，它所承載的交易數也越多，相應的網絡負載也會增加，最終結果如圖4所示。

通過分析實驗結果并對比四種算法，隨著節點數量的增加，四種算法的吞吐量均下降，但DS－PBFT算法的吞吐量比其他三種算法的吞吐量要高。由于傳統PBFT算法三階段共識過程過于復雜，所以吞吐量呈現較低趨勢；RIPPB算法雖然使節點通信次數減少了，但復雜度仍然為O（n2）；而EPBFT算法雖然分層分組共識通信復雜度降至多項式水平，但并沒有減少參與共識過程節點的數量，經測試改進后的DS－PBFT算法在吞吐量上有明顯的提升。

3.2.3 延遲

區塊鏈的吞吐量主要受延遲影響，在其他方面一致的前提下，延遲越小，區塊鏈系統的吞吐量就越高；此外，較低的延遲也可以改善區塊鏈共識確認的速度，提高系統共識效率。設置PBFT、RIPPB、EPBFT和DS－PBFT四種共識算法分別在5、10、15、20、25、30、35、40、45、50個節點中分別重復完成30次交易，計算30次交易的平均延遲，在本文中，延遲定義為一個區塊完成共識所花費的時間，如式（6）所示。

延遲=TC-TR（6）

其中：TC表示共識確認完成的時間，TR表示共識請求的時間。利用Caliper工具進行多次測試取平均值，結果如圖5所示。

通過分析實驗結果并對比四種算法，參與節點數越多，延遲時間越長，一開始四種算法在節點數目較少的情況下差別并不大， 但是當節點數目增多時差別明顯。傳統的PBFT算法復雜的三階段通信過程導致共識過程延時比較長；RIPPB算法對一致性協議進行優化，降低節點通信次數，使延遲時間變短；EPBFT雖然分層分組共識但并沒有減少共識節點的數量，延遲時間只是略有提高；而DS－PBFT算法不論在一致性協議還是共識節點數量上都有很好的改進，經測試改進后的DS－PBFT算法延遲低于其他三種算法，在延遲方面較為穩定，共識效率較高。

3.2.4 容錯性

拜占庭容錯性是分布式網絡的一種容錯能力，即存在惡意節點的情況下，仍能讓誠實節點達成共識。在實驗中加入拜占庭節點來測試共識算法的容錯性，設置拜占庭節點占比為5%、10%、15%、20%、25%、30%，總節點數為50的區塊鏈網絡中，比較PBFT、RIPPB、EPBFT和DS－PBFT算法在不同數量的拜占庭節點下完成相同數量交易的延遲和吞吐量，結果如圖6、7所示。

經實驗驗證，四種算法都具有一定的容錯性，拜占庭節點數為16時，沒有超過節點數的1/3，可以正常出塊，但當拜占庭節點數為17時，超過節點數的1/3，因此不能成功出塊。從圖6中可以看出，四種算法的延遲都隨著拜占庭節點數量的增多而變長，但DS－PBFT算法延遲比其他三種算法的延遲低；從圖7中可以看出，拜占庭節點數越多，其吞吐量就越低，但DS－PBFT算法始終比其他三種算法的吞吐量高。因此，DS－PBFT算法更優。

3.2.5 通信復雜度

共識算法的通信復雜度表示系統完成共識過程每個節點的交互情況，也可稱為廣播數，通信復雜度越高，共識的效率越低，耗費的資源越大。在傳統PBFT算法預準備過程中，主節點把預準備消息廣播給除自己以外的所有節點，此時通信數為N-1，其中N是參與共識的節點數量；在準備過程中，驗證接收到的消息發送準備消息，此過程通信數為（N-1）2；進入確認階段，驗證準備消息并給所有節點發送確認消息，此時通信數為N（N-1）。將以上三個過程相結合即為傳統PBFT算法發送的消息數，發送了N-1+（N-1）2+N（N-1）=2N2-2N條消息，通信復雜度為O（n2）。

在本文DS－PBFT算法中，預準備、準備和確認階段發送的消息數都是N-1，即在共識全過程中，共發送了N-1+N-1+N-1=3N-3條消息，通信復雜度為O（n），并且經過節點評分機制的篩選，多次共識之后誠實的節點多數都進入共識組，惡意節點多數進入候選組，不讓惡意節點參與共識過程。由此可以看出，改進后的DS－PBFT算法的通信復雜度降低，得到了優化，算法的適用范圍也變得更廣，共識效率更高。

3.3 相關共識算法的比較

如表3所示，比較傳統PBFT、RIPPB、EPBFT和DS－PBFT算法。

可以看到，DS－PBFT算法與其他共識算法相比具有以下優勢：a）DS－PBFT算法增加了節點評分機制，根據節點的歷史行為給出獎勵或懲罰，增加了共識過程的安全性；b）DS－PBFT算法可以識別拜占庭節點，并減小這些拜占庭節點參與共識過程的可能性，增加系統的穩健性，以此優化視圖切換協議，提高達成共識的速度；c）DS－PBFT算法減少了網絡中的通信開銷，優化一致性協議使共識所需的通信復雜度從O（n2）降低到O（n）；d）DS－PBFT算法提出分組共識，并與節點評分機制中的分值相結合動態選出主節點和共識節點，減少了參與共識的節點數量，從根本上提高共識效率。

4 結束語

本文提出DS－PBFT共識算法，簡化三階段通信流程，降低通信開銷快速達成共識，引入節點評分機制，依據歷史行為對節點實施獎勵或懲罰，使系統具有識別拜占庭節點的能力，安全性得到保證，優化視圖切換協議。同時，對節點分組并與節點評分機制中的分值相結合動態選出合適的主節點和共識節點，減少共識節點數量，從根本上保障共識效率。經實驗驗證，DS－PBFT算法在吞吐量、延遲、容錯性和通信復雜度方面都優于傳統PBFT算法及其改進算法，在主節點誠實的情況下，DS－PBFT算法的優勢更加明顯。因此，DS－PBFT算法適用于網絡穩定、可信節點較多的聯盟鏈。本文算法仍有一定的不足之處，如在網絡不穩定、惡意節點較多的情況下，共識節點數量增多，共識效率還需進一步提高。下一步工作重點是在不影響安全性和動態性的前提下，如何面對較多惡意節點快速達成共識，使共識效率最大化。

參考文獻：

［1］姚爽，張大偉，李勇，等.區塊鏈交易內容隱私保護技術研究綜述［J］.密碼學報，2022， 9 （4）：596－618. （Yao Shuang，Zhang Dawei，Li Yong，et al.Overview of research on privacy protection technology of blockchain transaction content［J］. Journal of Cryptography ，2022， 9 （4）：596－618.）

［2］肖瑤，馮勇，李英娜，等.基于同態加密的區塊鏈交易數據隱私保護方案［J］.密碼學報，2022， 9 （6）：1053－1066. （Xiao Yao，Feng Yong，Li Yingna，et al.A privacy－preserved scheme for blockchain transaction based on homomorphic encryption［J］. Journal of Cryptography ，2022， 9 （6）：1053－1066.）

［3］韓育芳.大數據時代計算機軟件技術的應用研究［J］.電子技術與軟件工程，2023（2）：47－51. （Han Yufang.Research on the application of computer software technology in the age of big data［J］. Electronic Technology and Software Engineering ，2023（2）：47－51.）

［4］張玉超.計算機網絡與云計算技術的應用［J］.集成電路應用，2023， 40 （2）：44－46. （Zhang Yuchao.Application of computer network and cloud computing technology［J］. Integrated Circuit Application ，2023， 40 （2）：44－46.）

［5］郭曉語，劉唯賓，錢雨.我國人工智能產業及技術發展現狀［J］.質量與認證，2023（4）：46－48. （Guo Xiaoyu，Liu Weibin，Qian Yu.China’s artificial intelligence industry and state of the art［J］. Quality and Certification ，2023（4）：46－48.）

［6］靳世雄，張瀟丹，葛敬國，等.區塊鏈共識算法研究綜述［J］.信息安全學報，202 6 （2）：85－100. （Jin Shixiong，Zhang Xiaodan，Ge Jingguo，et al.A review of blockchain consensus algorithms［J］. Journal of Information Security ，202 6 （2）：85－100.）

［7］Lamport L.Time，clocks，and the ordering of events in a distributed system［J］. Communications of the ACM ，1978， 21 （7）：558－565.

［8］Lamport L.The part－time parliament［J］. ACM Trans on Computer Systems ，1998， 16 （2）：133－169.

［9］Pires M，Ravi S，Rodrigues R.Generalized Paxos made Byzantine（and less complex）［M］//Lecture Notes in Computer Science.Cham：Springer International Publishing，2017：203－218.

［10］https：//kafka.apache.org/documentation［EB/OL］.

［11］Lamport L，Shostak R，Pease M.The Byzantine generals problem［J］. ACM Trans on Programming Languages and Systems ，1982， 4 （3）：382－401.

［12］Sukhwani H，Martínez J M，Chang Xiaolin，et al.Performance mode－ling of PBFT consensus process for permissioned blockchain network（Hyperledger Fabric）［C］//Proc of the 36th Symposium on Reliable Distributed Systems.Piscataway，NJ：IEEE Press，2017：253－255.

［13］Ongaro D，Ousterhout J K.In search of an understandable consensus algorithm［C］//Proc of USENIX Annual Technical Conference.2014：305－320.

［14］Dwork C，Naor M.Pricing via processing or combatting junk mail［C］//Advances in Cryptology.Berlin：Springer，2019：139－147.

［15］Back A.Hashcash：a denial of service counter－measure［EB/OL］.（2019）.http：//www.hashcash.org/papers/hashcash.pdf.

［16］King S.ppcoin：peer－to－peer crypto－currency with proof－of stake［EB/OL］.（2014）.https：//peercoin.net/assets/paper/peercoin－paper.pdf.

［17］Tendermint：consensus without mining［EB/OL］.（2019）. https：//tendermint.com/static/docs/tendermint.pdf.

［18］Miller A，Xia Y，Croman K，et al.The honey badger of BFT protocols［C］//Proc of ACM SIGSAC Conference on Computer and Communications Security.New York：ACM Press，2016：31－42.

［19］Tangaroa：a Byzantine fault tolerant Raft［EB/OL］.（2019）.http：//www.scs.stanford.edu/14aucs244b/labs/projects/copeland zhong.pdf.

［20］朱曉武，魏文石.區塊鏈的共識與分叉：the DAO案例對以太坊分叉的影響分析及啟示［J］.管理評論，202 33 （11）：324－340. （Zhu Xiaowu，Wei Wenshi.Consensus and bifurcation of blockchain：analysis of the impact of the DAO case on Ethereum bifurcation and its enlightenment［J］. Management Review ，202 33 （11）：324－340.）

［21］王森，李志淮，賈志鵬.主節點隨機選取的改進PBFT共識算法［J］.計算機應用與軟件，2022， 39 （10）：299－306. （Wang Sen，Li Zhihuai，Jia Zhipeng.Improved PBFT consensus algorithm for randomly selecting main nodes［J］. Computer Application and Software ，2022， 39 （10）：299－306.）

［22］方軼，鄧建球，叢林虎，等.一種基于環簽名的PBFT區塊鏈共識算法改進方案［J］.計算機工程，2019， 45 （11）：32－36. （Fang Yi，Deng Jianqiu，Cong Linhu，et al.An improved PBFT blockchain consensus algorithm based on ring signature［J］. Computer Enginee－ring ，2019， 45 （11）：32－36.）

［23］張猛，王寶成.基于推薦信任模型改進拜占庭容錯共識算法［J］.計算機應用研究，2023， 40 （3）：667－670. （Zhang Meng，Wang Baocheng.Improving Byzantine fault tolerance consensus algorithm based on recommended trust model［J］. Application Research of Computers ，2023， 40 （3）：667－670.）

［24］任璽羽，童向榮，張偉.基于信任評估模型的PBFT共識算法［J］.山西大學學報：自然科學版 ，2023， 46 （1）：108－118. （Ren Xiyu，Tong Xiangrong，Zhang Wei.PBFT consensus algorithm based on trust evaluation model［J］. Journal of Shanxi University：Natural Science Edition ，2023， 46 （1）：108－118.）

［25］秦偉杰.基于節點劃分聚類的PBFT共識算法［J］.信息技術與信息化，2023（1）：65－69. （Qin Weijie.PBFT consensus algorithm based on node partition clustering［J］. Information Technology and Informatization ，2023（1）：65－69.）

［26］馮了了，丁滟，劉坤林，等.區塊鏈BFT共識算法研究進展［J］.計算機科學，2022， 49 （4）：329－339. （Feng Liaoliao，Ding Yan，Liu Kunlin，et al.Progress in blockchain BFT consensus algorithm research［J］. Computer Science ，2022， 49 （4）：329－339.）

［27］趙立瑾，王新勝，夏純中.基于信任模型的PBFT共識機制研究［J］.計算機應用與軟件，2022， 39 （7）：304－309. （Zhao Lijin，Wang Xinsheng，Xia Chunzhong.Research on PBFT consensus mechanism based on trust model［J］. Computer Application and Software ，2022， 39 （7）：304－309.）

［28］馮霞，崔凱平，謝晴晴，等.VANET中基于區塊鏈的分布式匿名認證方案［J］.通信學報，2022， 43 （9）：134－147. （Feng Xia，Cui Kaiping，Xie Qingqing，et al.A distributed anonymous authentication scheme based on blockchain in VANET［J］. Journal on Communications ，2022， 43 （9）：134－147.）

［29］吳騰，黃鍇，周琳琳，等.具有狀態合法性驗證的區塊鏈一致性算法研究［J］.計算機工程，2018， 44 （1）：160－164. （Wu Teng，Huang Kai，Zhou Linlin，et al.Research on blockchain consistency algorithm with state legitimacy verification［J］. Computer Enginee－ring ，2018， 44 （1）：160－164.）

［30］Fox G.Peer－to－peer networks［J］. Computing in Science amp; Engineering ，200 3 （3）：75－77.

［31］Ding Meng，He Heng，Qiao Rui，et al.RIPPB：a robust and improved PBFT protocol for blockchain［C］//Proc of the 17th IEEE Conference on Industrial Electronics and Applications.2022：384－389.

［32］Li Wenzheng，He Mingsheng.EBFT：a hierarchical and group－based Byzantine fault tolerant consensus algorithm［C］//Proc of the 12th IEEE International Conference on Software Engineering and Service Science.2021：32－37.

收稿日期：2023－07－20；修回日期：2023－09－05 基金項目：國家自然科學基金面上項目（62173171）

作者簡介：沈學利（1969—），男，江蘇連云港人，教授，碩導，碩士，CCF會員，主要研究方向為智能信息處理等；李欣儒（1999—），女（通信作者），山東東平人，碩士研究生，主要研究方向為區塊鏈共識算法等（495535394@qq.com）．