基于k-means 的動態多組織PBFT 算法

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

關鍵詞：區塊鏈；拜占庭容錯算法；k-means 算法；信譽機制；節點任期機制

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

2）提出信譽值機制，根據節點的歷史行為動態調整節點的信譽值，將網絡中的節點分為誠實節點與作惡節點。每組中信譽值最高的節點會當選為組代表節點，而組節點代表中信譽值最高的節點當選為主節點。以此提高網絡的安全性，并對作惡節點做出懲罰。

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