摘要：聯(lián)盟區(qū)塊鏈系統(tǒng)被廣泛用于金融和物流等場(chǎng)景?，F(xiàn)有應(yīng)用于區(qū)塊鏈系統(tǒng)的實(shí)用拜占庭算法（practical Byzantine fault tolerance，PBFT）存在可擴(kuò)展性較低及通信成本較高等問題，阻礙了區(qū)塊鏈系統(tǒng)在大規(guī)模場(chǎng)景中的應(yīng)用。針對(duì)上述問題，提出了一種動(dòng)態(tài)多組織實(shí)用拜占庭容錯(cuò)算法（kmeans-practical Byzantine fault tolerance，k-PBFT）。通過改進(jìn)k-means 算法，根據(jù)節(jié)點(diǎn)的時(shí)延以及節(jié)點(diǎn)間通信距離將節(jié)點(diǎn)分為多個(gè)自治組織，各組織之間通過組織代表節(jié)點(diǎn)進(jìn)行通信。當(dāng)新節(jié)點(diǎn)加入時(shí)，根據(jù)其特點(diǎn)將其分配到最合理的組織。同時(shí)，引入信譽(yù)機(jī)制以辨別系統(tǒng)中的誠(chéng)實(shí)節(jié)點(diǎn)與惡意節(jié)點(diǎn)，從而提高系統(tǒng)的安全性。此外，該算法還引入節(jié)點(diǎn)任期機(jī)制，使區(qū)塊鏈中每個(gè)誠(chéng)實(shí)節(jié)點(diǎn)都有機(jī)會(huì)充當(dāng)組織代表節(jié)點(diǎn)或主節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，與PBFT 算法相比，k-PBFT 算法通信復(fù)雜度降低了75%；當(dāng)節(jié)點(diǎn)數(shù)為100 時(shí)，相比于PBFT 算法，時(shí)延降低了210 ms，吞吐量提高了100%。在高延遲環(huán)境下，相較于基于信譽(yù)分組的PBFT 改進(jìn)算法，當(dāng)節(jié)點(diǎn)數(shù)為100 時(shí)，時(shí)延降低了20%，吞吐量提高了17%。

關(guān)鍵詞：區(qū)塊鏈；拜占庭容錯(cuò)算法；k-means 算法；信譽(yù)機(jī)制；節(jié)點(diǎn)任期機(jī)制

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1000-582X（2024）07-125-15

在分布式網(wǎng)絡(luò)中，共識(shí)問題是一個(gè)經(jīng)典的問題，在20 世紀(jì)90 年代，Shankar 等[1]對(duì)共識(shí)問題中的拜占庭容錯(cuò)問題進(jìn)行了研究。隨著學(xué)者Nakamoto 在2008 年提出了名為Bitcoin 的數(shù)字貨幣[2]，引發(fā)了區(qū)塊鏈技術(shù)及其核心技術(shù)——共識(shí)算法[3]的研究熱潮。近年來，學(xué)者們對(duì)共識(shí)算法進(jìn)行了深入研究，并將其應(yīng)用于醫(yī)療保健[4]、數(shù)據(jù)安全[5]和能源[6]等領(lǐng)域。

共識(shí)算法是區(qū)塊鏈技術(shù)的核心，它確保分布式網(wǎng)絡(luò)中的節(jié)點(diǎn)維護(hù)相同的賬本。在幾種流行的共識(shí)算法中，PoW（proof of work）算法[7]和PoS（proof of stake）算法[8]應(yīng)用于公有區(qū)塊鏈，DPoS（delegated proof of stake）算法[9]應(yīng)用于私有區(qū)塊鏈，Raft（raft consensus algorithm）算法[10]和PBFT 算法[11]應(yīng)用于聯(lián)盟區(qū)塊鏈。在上述算法中，PoW、PoS 和DPoS 算法需要引入鏈上代幣激勵(lì)層，根據(jù)中國(guó)的法律法規(guī)，不支持使用代幣搭建區(qū)塊鏈服務(wù)平臺(tái)。因此，國(guó)家重點(diǎn)鼓勵(lì)發(fā)展許可加入型的區(qū)塊鏈——聯(lián)盟區(qū)塊鏈。在聯(lián)盟區(qū)塊鏈中，PBFT 算法是最受歡迎的共識(shí)算法，這是因?yàn)樵诜植际骄W(wǎng)絡(luò)中，即使有三分之一的節(jié)點(diǎn)作惡，PBFT 算法也能確保整個(gè)網(wǎng)絡(luò)的賬本是正確的，并且具有可以脫離代幣機(jī)制運(yùn)行、共識(shí)機(jī)制簡(jiǎn)單、易于維護(hù)等特點(diǎn)[12-15]。雖然PBFT 算法可以保持分布式網(wǎng)絡(luò)的高容錯(cuò)性，但隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的增加，網(wǎng)絡(luò)的通信開銷會(huì)變得十分龐大，節(jié)點(diǎn)間達(dá)成共識(shí)效率會(huì)很低，這使得大型區(qū)塊鏈項(xiàng)目無法開展。因此，許多學(xué)者改進(jìn)了PBFT 算法以適用于大型區(qū)塊鏈。

Yu 等[12]提出基于分組共識(shí)的改進(jìn)PBFT 算法，這種共識(shí)算法的最終一致性是由組內(nèi)代表節(jié)點(diǎn)達(dá)成的，而組內(nèi)的一致性則由每個(gè)組節(jié)點(diǎn)來維持。然而，這種策略忽略了節(jié)點(diǎn)之間的時(shí)延。Wang 等[14]利用信譽(yù)機(jī)制改進(jìn)PBFT 算法和評(píng)估每個(gè)節(jié)點(diǎn)的行為，只有值得信任的少數(shù)節(jié)點(diǎn)才能參與網(wǎng)絡(luò)共識(shí)。這種方法可以降低通信的復(fù)雜度，增加網(wǎng)絡(luò)的規(guī)模。然而，這種方法有以下缺點(diǎn)：首先，少數(shù)高信譽(yù)節(jié)點(diǎn)負(fù)載會(huì)很高，可能有崩潰的風(fēng)險(xiǎn)；其次，即使是高信譽(yù)節(jié)點(diǎn)也有作惡的可能，如果網(wǎng)絡(luò)共識(shí)僅僅由少數(shù)幾個(gè)節(jié)點(diǎn)完成，則會(huì)增加節(jié)點(diǎn)作惡的風(fēng)險(xiǎn)；最后，這種做法違背了去中心化的初衷，降低了區(qū)塊鏈的民主性。

基于前述背景與研究現(xiàn)狀，筆者引入改進(jìn)的k-means 算法、信譽(yù)機(jī)制及任期機(jī)制，對(duì)傳統(tǒng)的PBFT 算法進(jìn)行改進(jìn)，并提出了k-PBFT 算法；在不損害現(xiàn)有區(qū)塊鏈網(wǎng)絡(luò)的民主性和安全性的前提下，提高了PBFT 算法的可擴(kuò)展性，使其更適用于大規(guī)模聯(lián)盟區(qū)塊鏈網(wǎng)絡(luò)。

1 相關(guān)工作

近年來，學(xué)者們主要研究如何提高PBFT 算法的可擴(kuò)展性和降低其通信復(fù)雜度。PBFT 算法的通信復(fù)雜度較高，導(dǎo)致其可擴(kuò)展性較低，通常只適用于小型網(wǎng)絡(luò)[16]。為了提高PBFT 算法的可擴(kuò)展性，學(xué)者們提出了很多解決方案。Li 等[17]提出采用分層技術(shù)的改進(jìn)PBFT 算法來提高網(wǎng)絡(luò)的可擴(kuò)展性，避免大型網(wǎng)絡(luò)中由于節(jié)點(diǎn)數(shù)量過多而導(dǎo)致通信成本增加的問題。與分層PBFT 算法不同，Yang 等[18]提出一種多組共識(shí)的PBFT 算法，它首先在組內(nèi)進(jìn)行共識(shí)，然后進(jìn)行組間共識(shí)，同樣提高了網(wǎng)絡(luò)的可擴(kuò)展性。然而，可擴(kuò)展性的提高可能會(huì)帶來安全風(fēng)險(xiǎn)。通過網(wǎng)絡(luò)分片的方式來增強(qiáng)網(wǎng)絡(luò)的可擴(kuò)展性，當(dāng)某一個(gè)分片的數(shù)據(jù)丟失，會(huì)使整個(gè)記錄無法查詢[19]。分組或多中心的PBFT 算法可以降低通信成本，但以此算法作為共識(shí)基礎(chǔ)的區(qū)塊鏈網(wǎng)絡(luò)的安全性取決于組織代表節(jié)點(diǎn)及主節(jié)點(diǎn)，當(dāng)代表節(jié)點(diǎn)數(shù)量過少時(shí)，可能會(huì)出現(xiàn)代表節(jié)點(diǎn)聯(lián)合作惡，影響網(wǎng)絡(luò)安全[20]。

與本文所提算法較為相似的是文獻(xiàn)[21]報(bào)道的算法，一種采用k-medios 算法對(duì)參與區(qū)塊鏈共識(shí)的節(jié)點(diǎn)進(jìn)行分類的方法，采用惰性系數(shù)P 來減少k-medios 算法計(jì)算的復(fù)雜度。然而，該研究沒有控制每個(gè)簇內(nèi)的成員數(shù)量，當(dāng)簇內(nèi)成員數(shù)量過低時(shí)，會(huì)影響區(qū)塊鏈網(wǎng)絡(luò)的安全；并且該研究沒有引用信譽(yù)機(jī)制來懲罰網(wǎng)絡(luò)中的作惡節(jié)點(diǎn)，當(dāng)作惡節(jié)點(diǎn)成為代表節(jié)點(diǎn)時(shí)，會(huì)造成網(wǎng)絡(luò)頻繁進(jìn)行視圖切換而崩潰。而且，若少數(shù)幾個(gè)節(jié)點(diǎn)一直充當(dāng)代表節(jié)點(diǎn)，會(huì)增加該節(jié)點(diǎn)的壓力，且會(huì)提高網(wǎng)絡(luò)中心化程度，違背了區(qū)塊鏈網(wǎng)絡(luò)去中心化和民主性的初衷。在筆者所提算法中，首先改進(jìn)了k-means 算法，降低孤立點(diǎn)對(duì)聚類中心的影響，并控制簇內(nèi)成員數(shù)量，防止成員數(shù)量太少對(duì)區(qū)塊鏈網(wǎng)絡(luò)造成影響，最后引入信譽(yù)機(jī)制來檢測(cè)并懲罰網(wǎng)絡(luò)中的作惡節(jié)點(diǎn)，并引入節(jié)點(diǎn)任期機(jī)制來提高網(wǎng)絡(luò)的去中心化程度，保持區(qū)塊鏈網(wǎng)絡(luò)的民主性。

上述算法提高了PBFT 算法的可擴(kuò)展性，但可能忽略了PBFT 算法的容錯(cuò)性。雖然PBFT 算法只適用于小型網(wǎng)絡(luò)，但它可以容忍網(wǎng)絡(luò)中33% 的節(jié)點(diǎn)為作惡節(jié)點(diǎn)。在實(shí)踐中，高可擴(kuò)展性算法適用于大型網(wǎng)絡(luò)，但需要高容錯(cuò)性來保證算法能夠在惡劣的環(huán)境下正常運(yùn)行。Yang 等[22]對(duì)PBFT 算法的容錯(cuò)性進(jìn)行了深入研究，為保證分組共識(shí)的容錯(cuò)能力，提出了節(jié)點(diǎn)決策廣播模型與閾值計(jì)票模型。Aifandi 等[23]提出了能夠容忍拜占庭錯(cuò)誤的基于物聯(lián)網(wǎng)的共識(shí)算法。

筆者在多組織設(shè)計(jì)中考慮了算法的容錯(cuò)性，并對(duì)k-means 聚類過程進(jìn)行了改進(jìn)，以控制簇內(nèi)成員的數(shù)量，以期在保留算法的容錯(cuò)性的同時(shí)，提高算法的可擴(kuò)展性。目前的分組共識(shí)策略犧牲了區(qū)塊鏈網(wǎng)絡(luò)的去中心化特性以減少通信開銷。在整個(gè)網(wǎng)絡(luò)中由少數(shù)幾個(gè)組代表節(jié)點(diǎn)執(zhí)行共識(shí)的情況下，區(qū)塊鏈網(wǎng)絡(luò)的去中心化程度降低，同時(shí)降低網(wǎng)絡(luò)資源的利用率。

考慮到上述問題，筆者設(shè)計(jì)了一種基于改進(jìn)k-means 的PBFT 算法，即k-PBFT。該算法主要從以下幾個(gè)方面進(jìn)行了優(yōu)化。

1）利用改進(jìn)的k-means 算法，根據(jù)節(jié)點(diǎn)間的時(shí)延和距離將節(jié)點(diǎn)分為多個(gè)自治組織。與其他基于分組的PBFT 算法不同，k-PBFT 算法中每個(gè)自治組織節(jié)點(diǎn)間的時(shí)延更低。

2）提出信譽(yù)值機(jī)制，根據(jù)節(jié)點(diǎn)的歷史行為動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的信譽(yù)值，將網(wǎng)絡(luò)中的節(jié)點(diǎn)分為誠(chéng)實(shí)節(jié)點(diǎn)與作惡節(jié)點(diǎn)。每組中信譽(yù)值最高的節(jié)點(diǎn)會(huì)當(dāng)選為組代表節(jié)點(diǎn)，而組節(jié)點(diǎn)代表中信譽(yù)值最高的節(jié)點(diǎn)當(dāng)選為主節(jié)點(diǎn)。以此提高網(wǎng)絡(luò)的安全性，并對(duì)作惡節(jié)點(diǎn)做出懲罰。

3）為了改善網(wǎng)絡(luò)中僅有幾個(gè)組代表節(jié)點(diǎn)與主節(jié)點(diǎn)參與共識(shí)的問題，提出節(jié)點(diǎn)任期機(jī)制，設(shè)置節(jié)點(diǎn)的任期。當(dāng)節(jié)點(diǎn)充當(dāng)組代表節(jié)點(diǎn)或主節(jié)點(diǎn)任期到期后，會(huì)重新選舉組代表節(jié)點(diǎn)和主節(jié)點(diǎn)。可以降低少數(shù)幾個(gè)節(jié)點(diǎn)的負(fù)載，并提高網(wǎng)絡(luò)的民主性。