基于節(jié)點(diǎn)動(dòng)態(tài)評(píng)分機(jī)制的分組共識(shí)算法

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

關(guān)鍵詞：區(qū)塊鏈； 共識(shí)算法； 實(shí)用拜占庭容錯(cuò)算法； 節(jié)點(diǎn)動(dòng)態(tài)評(píng)分； 分組共識(shí)

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼： A文章編號(hào)：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 引言

區(qū)塊鏈?zhǔn)且环N點(diǎn)對(duì)點(diǎn)的分布式存儲(chǔ)系統(tǒng)，具有安全性能好、容錯(cuò)性高，適合加密等特性［1，2］，正是因?yàn)閰^(qū)塊鏈的這些特點(diǎn)，現(xiàn)如今已經(jīng)與大數(shù)據(jù)［3］、云計(jì)算［4］及人工智能［5］四個(gè)領(lǐng)域合稱為信息產(chǎn)業(yè)里的黑科技，而其中的底層核心——共識(shí)算法［6］也慢慢進(jìn)入大眾視野。

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

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

為了解決改進(jìn)后的PBFT算法仍有較大通信開銷，主節(jié)點(diǎn)隨機(jī)選取，有一定的局限性，不能在動(dòng)態(tài)網(wǎng)絡(luò)中完成共識(shí)，無(wú)法識(shí)別系統(tǒng)中的拜占庭節(jié)點(diǎn)等問題，本文基于自適應(yīng)選取共識(shí)節(jié)點(diǎn)提出了基于節(jié)點(diǎn)動(dòng)態(tài)評(píng)分機(jī)制的分組共識(shí)算法（DS－PBFT）。

1 PBFT算法相關(guān)理論及技術(shù)

1.1 PBFT算法流程

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

a）預(yù)準(zhǔn)備階段（pre－prepare）：主節(jié)點(diǎn)向其他節(jié)點(diǎn)廣播消息，提議一個(gè)新的區(qū)塊，包括區(qū)塊內(nèi)容和序列號(hào)。其他節(jié)點(diǎn)接收到此消息后對(duì)消息進(jìn)行驗(yàn)證，如果合法則發(fā)出“準(zhǔn)備”消息，否則不作處理。

b）準(zhǔn)備階段（prepare）：節(jié)點(diǎn)從主節(jié)點(diǎn)接收消息后，會(huì)檢驗(yàn)這個(gè)消息的正確性，并將“準(zhǔn)備”消息廣播給其他節(jié)點(diǎn)，以表示自己已經(jīng)接受該消息。節(jié)點(diǎn)在此階段還要等待來(lái)自其他節(jié)點(diǎn)的“準(zhǔn)備”消息，以確保有足夠多的節(jié)點(diǎn)接受了該消息。

c）確認(rèn)階段（commit）：節(jié)點(diǎn)接收到足夠多的“準(zhǔn)備”消息后，將“確認(rèn)”消息發(fā)送給其他節(jié)點(diǎn)，表示該消息已經(jīng)被確認(rèn)，可以寫入?yún)^(qū)塊鏈。節(jié)點(diǎn)在此階段還要等待來(lái)自其他節(jié)點(diǎn)的“確認(rèn)”消息，以確保有足夠多的節(jié)點(diǎn)確認(rèn)了該消息。

d）回復(fù)階段（complete）：節(jié)點(diǎn)收到足夠數(shù)量的“確認(rèn)”消息后，確認(rèn)該消息已經(jīng)寫入?yún)^(qū)塊鏈，并將其傳播給其他節(jié)點(diǎn)，以便更新狀態(tài)。

1.2 PBFT協(xié)議

PBFT算法包括以下協(xié)議：

a）一致性協(xié)議是對(duì)共識(shí)過程的描述，該過程用于對(duì)請(qǐng)求達(dá)成一致［29］。

b）檢查點(diǎn)協(xié)議可以安全地丟棄以前的日志消息，降低節(jié)點(diǎn)的內(nèi)存開銷，也可以幫助落后的節(jié)點(diǎn)同步最新狀態(tài)。

c）視圖切換協(xié)議用于主節(jié)點(diǎn)為惡意節(jié)點(diǎn)的情況，幫助系統(tǒng)更換主節(jié)點(diǎn)，成功達(dá)成共識(shí)。

為提高系統(tǒng)效率，可以從以上三方面進(jìn)行優(yōu)化。

1.3 PBFT算法缺點(diǎn)

a）一致性協(xié)議需要三階段廣播，廣播數(shù)量多，并且耗費(fèi)資源，降低共識(shí)效率，使用X來(lái)定義完成共識(shí)過程的消息數(shù)量，N為共識(shí)節(jié)點(diǎn)數(shù)量，則關(guān)系如式（1）所示。

X=2N2-2N （1）

b）隨機(jī)選取主節(jié)點(diǎn)存在安全風(fēng)險(xiǎn)，若多次選擇惡意節(jié)點(diǎn)為主節(jié)點(diǎn)，會(huì)顯著降低共識(shí)效率，浪費(fèi)系統(tǒng)資源，并帶來(lái)系統(tǒng)風(fēng)險(xiǎn)。

c）客戶端只能向主節(jié)點(diǎn)發(fā)送消息，如果消息過多，主節(jié)點(diǎn)就會(huì)有很大負(fù)擔(dān)，并不適用于區(qū)塊鏈點(diǎn)對(duì)點(diǎn)（peer－to－peer，P2P）的網(wǎng)絡(luò)環(huán)境［30］。

2 改進(jìn)PBFT共識(shí)算法

2.1 算法思想

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

針對(duì)PBFT三階段的通信流程，優(yōu)化了一致性協(xié)議，將傳統(tǒng)PBFT在準(zhǔn)備階段和確認(rèn)階段的兩次兩兩交互簡(jiǎn)化為直接通信。根據(jù)改進(jìn)PBFT算法所展現(xiàn)出來(lái)的優(yōu)化思路發(fā)現(xiàn)，這種共識(shí)算法可快速完成共識(shí)，提高共識(shí)效率。

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

然而，仍需考慮以下幾點(diǎn)：

a）安全考慮：PBFT算法是一種容錯(cuò)共識(shí)算法，可以容忍一定數(shù)量的拜占庭錯(cuò)誤（惡意行為）。減少節(jié)點(diǎn)數(shù)量可能會(huì)降低系統(tǒng)抵抗攻擊的能力。然而，本文提出了一種基于節(jié)點(diǎn)動(dòng)態(tài)評(píng)分機(jī)制的分組共識(shí)算法，根據(jù)節(jié)點(diǎn)的歷史行為進(jìn)行評(píng)分。通過這種方法檢測(cè)到的惡意節(jié)點(diǎn)取消參與下次共識(shí)過程的資格，只能對(duì)共識(shí)過程作出反應(yīng)。因此，在減少節(jié)點(diǎn)數(shù)量時(shí)，可以確保系統(tǒng)仍足夠安全，能夠容忍一定數(shù)量的惡意節(jié)點(diǎn)。

b）分布式：PBFT的優(yōu)勢(shì)之一是其分布式性質(zhì)，可以在去中心化環(huán)境中實(shí)現(xiàn)共識(shí)。減少節(jié)點(diǎn)數(shù)量可能會(huì)導(dǎo)致中心化風(fēng)險(xiǎn)，并降低系統(tǒng)的分布式性質(zhì)。然而，本文提出動(dòng)態(tài)計(jì)算參與共識(shí)的節(jié)點(diǎn)，共識(shí)節(jié)點(diǎn)和其數(shù)量都是在歷史行為下不斷變化的。按節(jié)點(diǎn)評(píng)分降序排列所有節(jié)點(diǎn)，并對(duì)它們進(jìn)行分組，從而可以解決節(jié)點(diǎn)分?jǐn)?shù)累計(jì)的問題。

針對(duì)惡意節(jié)點(diǎn)成為主節(jié)點(diǎn)時(shí)視圖切換協(xié)議和垃圾回收機(jī)制過于復(fù)雜、開銷大的問題，提出節(jié)點(diǎn)動(dòng)態(tài)選擇參與共識(shí)的節(jié)點(diǎn)優(yōu)化視圖切換協(xié)議和垃圾回收機(jī)制。根據(jù)以上算法思想，本文算法可以降低系統(tǒng)中心化程度，在抵御惡意節(jié)點(diǎn)的攻擊下提高共識(shí)效率，并保證區(qū)塊鏈系統(tǒng)的安全性和可靠性。

2.2 算法符號(hào)

a）在本文算法中，C代表客戶端自己的標(biāo)識(shí)，RC代表客戶端的請(qǐng)求操作，m代表客戶端所發(fā)出的請(qǐng)求，v代表視圖編號(hào)，n代表請(qǐng)求的序列號(hào)，h代表請(qǐng)求的哈希值，f代表拜占庭節(jié)點(diǎn)的個(gè)數(shù)，t代表時(shí)間戳，S代表簽名，I代表節(jié)點(diǎn)。

b）本文算法對(duì)節(jié)點(diǎn)數(shù)是有一定要求的。如果系統(tǒng)中有f個(gè)拜占庭節(jié)點(diǎn)，則必須讓所有節(jié)點(diǎn)的總數(shù)比3f+1大才可以完成共識(shí)， 一般在實(shí)驗(yàn)條件下，為了減少系統(tǒng)負(fù)載，會(huì)讓其等于3f+1。

c）本文算法對(duì)節(jié)點(diǎn)進(jìn)行分組，可分為共識(shí)節(jié)點(diǎn)組和候選節(jié)點(diǎn)組。共識(shí)節(jié)點(diǎn)組用A表示，包括主節(jié)點(diǎn)和從節(jié)點(diǎn)，第i個(gè)共識(shí)節(jié)點(diǎn)用Ai表示，候選節(jié)點(diǎn)組用B表示。

2.3 共識(shí)過程描述

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

a）請(qǐng)求階段：客戶端節(jié)點(diǎn)向主節(jié)點(diǎn)發(fā)起請(qǐng)求消息〈〈 Request，C，RC，t〉，SC〉，主節(jié)點(diǎn)接收提供的Request消息。

b）預(yù)準(zhǔn)備階段：客戶端節(jié)點(diǎn)的請(qǐng)求被主節(jié)點(diǎn)接收后，觸發(fā)預(yù)準(zhǔn)備階段。主節(jié)點(diǎn)會(huì)向所有副本節(jié)點(diǎn)廣播預(yù)準(zhǔn)備消息〈〈Pre－prepare，v，n，h〉，SP，m〉。當(dāng)副本節(jié)點(diǎn)接收到Pre－prepare消息時(shí)，它會(huì)對(duì)該消息進(jìn)行驗(yàn)證。如果驗(yàn)證成功，副本節(jié)點(diǎn)將進(jìn)入準(zhǔn)備階段，準(zhǔn)備參與后續(xù)的共識(shí)過程；然而，如果驗(yàn)證失敗，副本節(jié)點(diǎn)將不會(huì)采取任何進(jìn)一步的行動(dòng)。

c）準(zhǔn)備階段：如果節(jié)點(diǎn)成功驗(yàn)證了接收到的預(yù)準(zhǔn)備消息，那么該節(jié)點(diǎn)將進(jìn)入準(zhǔn)備階段。在準(zhǔn)備階段，從節(jié)點(diǎn)會(huì)向主節(jié)點(diǎn)發(fā)送確認(rèn)已收到的準(zhǔn)備消息〈〈Prepare，v，n，h，I〉，SI〉。如果主節(jié)點(diǎn)接收到一定數(shù)量的準(zhǔn)備消息，將進(jìn)入確認(rèn)階段。

d）確認(rèn)階段：一旦主節(jié)點(diǎn)收到超過2f+1個(gè)相同的準(zhǔn)備消息，就會(huì)認(rèn)為共識(shí)已經(jīng)達(dá)成。在這種情況下，主節(jié)點(diǎn)將向所有節(jié)點(diǎn)（包括候選節(jié)點(diǎn)）確認(rèn)達(dá)成的共識(shí)結(jié)果〈〈Commit，v，n，h〉，SP，m〉，同時(shí)更新所有節(jié)點(diǎn)的得分。將得分按高到低進(jìn)行排序，具有最低分的m個(gè)節(jié)點(diǎn)進(jìn)入候選組，并且附加到候選組的末尾。將候選組中具有最高分?jǐn)?shù)的m個(gè)節(jié)點(diǎn)添加到共識(shí)節(jié)點(diǎn)組中，至此，一輪共識(shí)過程結(jié)束。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}//主節(jié)點(diǎn)廣播共識(shí)結(jié)果

the consensus nodes will update the result to their own state machines//共識(shí)節(jié)點(diǎn)完成共識(shí)并更新共識(shí)結(jié)果

}

output：result{i}；

end

2.4 節(jié)點(diǎn)動(dòng)態(tài)評(píng)分機(jī)制

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

系統(tǒng)依據(jù)最近三個(gè)輪次的共識(shí)行為來(lái)確定節(jié)點(diǎn)的得分情況，將得分累加即為節(jié)點(diǎn)的新分?jǐn)?shù)，本文算法避免了隨機(jī)性，使系統(tǒng)能夠區(qū)分惡意節(jié)點(diǎn)，并提高共識(shí)過程的安全性和穩(wěn)定性，同時(shí)，未參與共識(shí)的節(jié)點(diǎn)仍然需要少量加分，其目的是增加共識(shí)過程的動(dòng)態(tài)性，并提高每一個(gè)節(jié)點(diǎn)的積極性，使每個(gè)歷史表現(xiàn)良好的節(jié)點(diǎn)都有概率參與到共識(shí)過程，防止出現(xiàn)共識(shí)中心化問題。

隨著節(jié)點(diǎn)數(shù)量的增多，傳統(tǒng)PBFT算法要求所有節(jié)點(diǎn)均參與共識(shí)過程，這就必然導(dǎo)致系統(tǒng)時(shí)延增加。為此，本文提出節(jié)點(diǎn)分值計(jì)算，公式如下：

其中：Scorei表示第i輪次節(jié)點(diǎn)的平均得分情況，Smi代表節(jié)點(diǎn)m在參與第i輪共識(shí)時(shí)候的得分，ΔSmi代表節(jié)點(diǎn)m在第i輪共識(shí)時(shí)候得分的偏差，N代表總體節(jié)點(diǎn)數(shù)量。

由式（2）計(jì)算每輪共識(shí)的節(jié)點(diǎn)平均得分，并且規(guī)定系統(tǒng)節(jié)點(diǎn)初始得分為50，在共識(shí)過程中分值確保在50≤Scorei≤100，提出用節(jié)點(diǎn)得分來(lái)規(guī)劃下一輪參與共識(shí)的節(jié)點(diǎn)數(shù)量，如式（3）所示。

其中：Number為預(yù)計(jì)分配的共識(shí)節(jié)點(diǎn)數(shù)量。由式（3）可以看出，當(dāng)節(jié)點(diǎn)平均分?jǐn)?shù)在初始狀態(tài)為50時(shí)代表著所有節(jié)點(diǎn)都參與共識(shí)過程，而當(dāng)節(jié)點(diǎn)平均分?jǐn)?shù)不斷趨向上限100時(shí)，發(fā)現(xiàn)共識(shí)節(jié)點(diǎn)為所有節(jié)點(diǎn)的2/3。由此可以得出結(jié)論，在共識(shí)過程中拜占庭節(jié)點(diǎn)數(shù)量較少甚至沒有拜占庭節(jié)點(diǎn)時(shí)，在經(jīng)過幾次共識(shí)輪次后，共識(shí)節(jié)點(diǎn)的數(shù)目將逐漸接近總節(jié)點(diǎn)數(shù)的2/3?？蓪⒐?jié)點(diǎn)按照分值降序排列，從高到低選取參與共識(shí)的節(jié)點(diǎn)，使得分高的節(jié)點(diǎn)作為共識(shí)節(jié)點(diǎn)，更能保證共識(shí)過程中的安全性，節(jié)點(diǎn)權(quán)限如表2所示。

在上述所提出的優(yōu)化方案中，由于減少了共識(shí)節(jié)點(diǎn)的數(shù)量，在拜占庭節(jié)點(diǎn)較多的情況下容易存在安全問題，由此提出在共識(shí)過程失敗時(shí)，將所有節(jié)點(diǎn)的平均分值統(tǒng)一減少15，通過式（3）可以保證在參與下一輪共識(shí)過程中共識(shí)的節(jié)點(diǎn)數(shù)量會(huì)增加，以降低可能出現(xiàn)的安全風(fēng)險(xiǎn)，并重新對(duì)共識(shí)失敗的消息進(jìn)行共識(shí)，降低共識(shí)失敗的概率。

本文提出的依據(jù)節(jié)點(diǎn)分值選取共識(shí)節(jié)點(diǎn)，可以確保參與共識(shí)的節(jié)點(diǎn)大多都是較為誠(chéng)實(shí)的，而惡意節(jié)點(diǎn)在經(jīng)過多個(gè)輪次后會(huì)進(jìn)入到候選組，并不參與共識(shí)過程，僅僅只是對(duì)共識(shí)過程作出反應(yīng)。由此可以保證，在惡意節(jié)點(diǎn)較少的情況下，共識(shí)失敗的概率很低，共識(shí)節(jié)點(diǎn)的數(shù)量將趨向于總節(jié)點(diǎn)數(shù)的2/3。而在惡意節(jié)點(diǎn)較多的情況下，系統(tǒng)能夠自動(dòng)計(jì)算出參與共識(shí)節(jié)點(diǎn)的數(shù)量，以避免持續(xù)的共識(shí)失敗。

因此，本文中提出的基于節(jié)點(diǎn)動(dòng)態(tài)評(píng)分機(jī)制的分組共識(shí)算法可以根據(jù)不同的歷史行為進(jìn)行動(dòng)態(tài)調(diào)整，使誠(chéng)實(shí)節(jié)點(diǎn)組成共識(shí)組參與共識(shí)過程，提高共識(shí)效率。

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

2.5 視圖切換協(xié)議和垃圾回收機(jī)制的優(yōu)化

2.5.1 優(yōu)化視圖切換策略

視圖切換是指若主節(jié)點(diǎn)是拜占庭節(jié)點(diǎn)，在指定時(shí)間內(nèi)未能發(fā)出共識(shí)請(qǐng)求消息或請(qǐng)求超時(shí)，其余從節(jié)點(diǎn)可以發(fā)出替換視圖請(qǐng)求，推翻主節(jié)點(diǎn)，并重新選擇可信主節(jié)點(diǎn)參與。如果發(fā)現(xiàn)主節(jié)點(diǎn)被推翻，將再次切換新的視圖，保存上一階段完成共識(shí)的區(qū)塊，未完成共識(shí)的區(qū)塊將被丟棄，新的主節(jié)點(diǎn)選出后，在前一階段被丟棄的區(qū)塊將重新達(dá)成共識(shí)。新視圖開始時(shí)，會(huì)及時(shí)同步和校驗(yàn)全局節(jié)點(diǎn)，從而保證數(shù)據(jù)的完整一致性，等待下一輪共識(shí)。傳統(tǒng)PBFT算法的視圖切換主節(jié)點(diǎn)的選擇根據(jù)式（4）確定。

P=v mod K （4）

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

2.5.2 優(yōu)化垃圾回收策略

在傳統(tǒng)的PBFT算法中，通常周期性執(zhí)行垃圾回收機(jī)制，這樣做的目的是避免因?yàn)榫W(wǎng)絡(luò)的延遲節(jié)點(diǎn)收到不一致的信息，確保系統(tǒng)的正常運(yùn)行，同時(shí)防止過多的日志信息占用空間，需要對(duì)舊的日志消息進(jìn)行及時(shí)清除，要確定節(jié)點(diǎn)之間通信同步，必須保證有至少f+1個(gè)節(jié)點(diǎn)去執(zhí)行消息，所以導(dǎo)致每次垃圾回收機(jī)制會(huì)產(chǎn)生巨大的開銷。

而優(yōu)化的DS－PBFT算法能夠及時(shí)更新節(jié)點(diǎn)的得分來(lái)完善垃圾回收機(jī)制，當(dāng)執(zhí)行一致性協(xié)議的節(jié)點(diǎn)得分超過閾值時(shí)，在完成一致性協(xié)議之后，可以運(yùn)行垃圾回收機(jī)制，刪除本地舊的交易日志信息，減少網(wǎng)絡(luò)通信消耗，并將一定范圍內(nèi)歷史得分高的節(jié)點(diǎn)隨機(jī)分配新的高分，使得分最高的節(jié)點(diǎn)成為新的主節(jié)點(diǎn)，增加共識(shí)機(jī)制的動(dòng)態(tài)性。

3 理論與實(shí)驗(yàn)結(jié)果分析

3.1 理論分析

3.1.1 安全性分析

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

3.1.2 共識(shí)效率分析

傳統(tǒng)PBFT算法要求所有節(jié)點(diǎn)共同參與共識(shí)過程，節(jié)點(diǎn)與節(jié)點(diǎn)之間兩兩交互，使得共識(shí)效率不高，消耗大量資源。本文提出的DS－PBFT算法從以下三個(gè)方面提高了共識(shí)效率：a）優(yōu)化一致性協(xié)議，簡(jiǎn)化三階段流程，減少節(jié)點(diǎn)之間的通信次數(shù)；b）提出節(jié)點(diǎn)動(dòng)態(tài)評(píng)分機(jī)制，依據(jù)節(jié)點(diǎn)的歷史行為計(jì)算節(jié)點(diǎn)得分，使共識(shí)節(jié)點(diǎn)都是表現(xiàn)良好的節(jié)點(diǎn)，降低視圖切換的概率；c）提出依據(jù)節(jié)點(diǎn)評(píng)分動(dòng)態(tài)選取參與共識(shí)的節(jié)點(diǎn)，能夠減少參與共識(shí)的節(jié)點(diǎn)數(shù)量，從根本上提高共識(shí)效率。

3.2 實(shí)驗(yàn)結(jié)果分析

3.2.1 實(shí)驗(yàn)環(huán)境

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

3.2.2 吞吐量

吞吐量定義為系統(tǒng)在單位時(shí)間內(nèi)處理一個(gè)請(qǐng)求的事物量，吞吐量越高處理的事物量越多，設(shè)置PBFT、RIPPB、EPBFT和DS－PBFT四種共識(shí)算法分別在5、10、15、20、25、30、35、40、45、50個(gè)節(jié)點(diǎn)中，進(jìn)行30次實(shí)驗(yàn)設(shè)置事件量為1 200，計(jì)算30次重復(fù)實(shí)驗(yàn)的平均值為吞吐量，TPS（transaction per second）表示系統(tǒng)吞吐量，計(jì)算公式如式（5）所示。

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

其中：Δt表示從交易信息發(fā)出到區(qū)塊存儲(chǔ)完成的時(shí)間，即出塊時(shí)間；TransactionsΔt表示每個(gè)區(qū)塊在出塊的時(shí)間間隔內(nèi)完成交易的數(shù)量。系統(tǒng)的吞吐量還與網(wǎng)絡(luò)環(huán)境和塊大小有關(guān)，區(qū)塊越大，它所承載的交易數(shù)也越多，相應(yīng)的網(wǎng)絡(luò)負(fù)載也會(huì)增加，最終結(jié)果如圖4所示。

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

3.2.3 延遲

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

延遲=TC-TR（6）

其中：TC表示共識(shí)確認(rèn)完成的時(shí)間，TR表示共識(shí)請(qǐng)求的時(shí)間。利用Caliper工具進(jìn)行多次測(cè)試取平均值，結(jié)果如圖5所示。

通過分析實(shí)驗(yàn)結(jié)果并對(duì)比四種算法，參與節(jié)點(diǎn)數(shù)越多，延遲時(shí)間越長(zhǎng)，一開始四種算法在節(jié)點(diǎn)數(shù)目較少的情況下差別并不大， 但是當(dāng)節(jié)點(diǎn)數(shù)目增多時(shí)差別明顯。傳統(tǒng)的PBFT算法復(fù)雜的三階段通信過程導(dǎo)致共識(shí)過程延時(shí)比較長(zhǎng)；RIPPB算法對(duì)一致性協(xié)議進(jìn)行優(yōu)化，降低節(jié)點(diǎn)通信次數(shù)，使延遲時(shí)間變短；EPBFT雖然分層分組共識(shí)但并沒有減少共識(shí)節(jié)點(diǎn)的數(shù)量，延遲時(shí)間只是略有提高；而DS－PBFT算法不論在一致性協(xié)議還是共識(shí)節(jié)點(diǎn)數(shù)量上都有很好的改進(jìn)，經(jīng)測(cè)試改進(jìn)后的DS－PBFT算法延遲低于其他三種算法，在延遲方面較為穩(wěn)定，共識(shí)效率較高。

3.2.4 容錯(cuò)性

拜占庭容錯(cuò)性是分布式網(wǎng)絡(luò)的一種容錯(cuò)能力，即存在惡意節(jié)點(diǎn)的情況下，仍能讓誠(chéng)實(shí)節(jié)點(diǎn)達(dá)成共識(shí)。在實(shí)驗(yàn)中加入拜占庭節(jié)點(diǎn)來(lái)測(cè)試共識(shí)算法的容錯(cuò)性，設(shè)置拜占庭節(jié)點(diǎn)占比為5%、10%、15%、20%、25%、30%，總節(jié)點(diǎn)數(shù)為50的區(qū)塊鏈網(wǎng)絡(luò)中，比較PBFT、RIPPB、EPBFT和DS－PBFT算法在不同數(shù)量的拜占庭節(jié)點(diǎn)下完成相同數(shù)量交易的延遲和吞吐量，結(jié)果如圖6、7所示。

經(jīng)實(shí)驗(yàn)驗(yàn)證，四種算法都具有一定的容錯(cuò)性，拜占庭節(jié)點(diǎn)數(shù)為16時(shí)，沒有超過節(jié)點(diǎn)數(shù)的1/3，可以正常出塊，但當(dāng)拜占庭節(jié)點(diǎn)數(shù)為17時(shí)，超過節(jié)點(diǎn)數(shù)的1/3，因此不能成功出塊。從圖6中可以看出，四種算法的延遲都隨著拜占庭節(jié)點(diǎn)數(shù)量的增多而變長(zhǎng)，但DS－PBFT算法延遲比其他三種算法的延遲低；從圖7中可以看出，拜占庭節(jié)點(diǎn)數(shù)越多，其吞吐量就越低，但DS－PBFT算法始終比其他三種算法的吞吐量高。因此，DS－PBFT算法更優(yōu)。

3.2.5 通信復(fù)雜度

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

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

3.3 相關(guān)共識(shí)算法的比較

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

［1］姚爽，張大偉，李勇，等.區(qū)塊鏈交易內(nèi)容隱私保護(hù)技術(shù)研究綜述［J］.密碼學(xué)報(bào)，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］肖瑤，馮勇，李英娜，等.基于同態(tài)加密的區(qū)塊鏈交易數(shù)據(jù)隱私保護(hù)方案［J］.密碼學(xué)報(bào)，2022， 9 （6）：1053－1066. （Xiao Yao，F(xiàn)eng 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］韓育芳.大數(shù)據(jù)時(shí)代計(jì)算機(jī)軟件技術(shù)的應(yīng)用研究［J］.電子技術(shù)與軟件工程，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ì)算機(jī)網(wǎng)絡(luò)與云計(jì)算技術(shù)的應(yīng)用［J］.集成電路應(yīng)用，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］郭曉語(yǔ)，劉唯賓，錢雨.我國(guó)人工智能產(chǎn)業(yè)及技術(shù)發(fā)展現(xiàn)狀［J］.質(zhì)量與認(rèn)證，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］靳世雄，張瀟丹，葛敬國(guó)，等.區(qū)塊鏈共識(shí)算法研究綜述［J］.信息安全學(xué)報(bào)，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］朱曉武，魏文石.區(qū)塊鏈的共識(shí)與分叉：the DAO案例對(duì)以太坊分叉的影響分析及啟示［J］.管理評(píng)論，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］王森，李志淮，賈志鵬.主節(jié)點(diǎn)隨機(jī)選取的改進(jìn)PBFT共識(shí)算法［J］.計(jì)算機(jī)應(yīng)用與軟件，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］方軼，鄧建球，叢林虎，等.一種基于環(huán)簽名的PBFT區(qū)塊鏈共識(shí)算法改進(jìn)方案［J］.計(jì)算機(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ìn)拜占庭容錯(cuò)共識(shí)算法［J］.計(jì)算機(jī)應(yīng)用研究，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］任璽羽，童向榮，張偉.基于信任評(píng)估模型的PBFT共識(shí)算法［J］.山西大學(xué)學(xué)報(bào)：自然科學(xué)版 ，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］秦偉杰.基于節(jié)點(diǎn)劃分聚類的PBFT共識(shí)算法［J］.信息技術(shù)與信息化，2023（1）：65－69. （Qin Weijie.PBFT consensus algorithm based on node partition clustering［J］. Information Technology and Informatization ，2023（1）：65－69.）

［26］馮了了，丁滟，劉坤林，等.區(qū)塊鏈BFT共識(shí)算法研究進(jìn)展［J］.計(jì)算機(jī)科學(xué)，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共識(shí)機(jī)制研究［J］.計(jì)算機(jī)應(yīng)用與軟件，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中基于區(qū)塊鏈的分布式匿名認(rèn)證方案［J］.通信學(xué)報(bào)，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］吳騰，黃鍇，周琳琳，等.具有狀態(tài)合法性驗(yàn)證的區(qū)塊鏈一致性算法研究［J］.計(jì)算機(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 基金項(xiàng)目：國(guó)家自然科學(xué)基金面上項(xiàng)目（62173171）

作者簡(jiǎn)介：沈?qū)W利（1969—），男，江蘇連云港人，教授，碩導(dǎo)，碩士，CCF會(huì)員，主要研究方向?yàn)橹悄苄畔⑻幚淼?；李欣儒?999—），女（通信作者），山東東平人，碩士研究生，主要研究方向?yàn)閰^(qū)塊鏈共識(shí)算法等（495535394@qq.com）．