基于k-means 的動態(tài)多組織PBFT 算法

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

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

中圖分類號：TP311 文獻標志碼：A 文章編號：1000-582X（2024）07-125-15

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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