• <option id="cacee"><noscript id="cacee"></noscript></option>
  • <table id="cacee"><noscript id="cacee"></noscript></table>
  • <td id="cacee"></td>
  • <option id="cacee"></option>
  • <table id="cacee"></table>
  • <option id="cacee"><option id="cacee"></option></option>
  • <table id="cacee"><source id="cacee"></source></table><td id="cacee"><rt id="cacee"></rt></td>
    <option id="cacee"><option id="cacee"></option></option>
     找回密碼
     立即注冊

    掃一掃,登錄網站

    首頁 百科 查看內容
    • 3935
    • 0
    • 分享到

    讀懂共識算法|區塊鏈系統中如何高效地達成共識

    2018-4-13 11:48

    來源: 獨角區塊鏈 作者: 譚雅文

    讀懂共識算法|區塊鏈系統中如何高效地達成共識


    區塊鏈五大特征中,去中心化始終是激辯的話題。狹義來講,區塊鏈是一種分布式賬本,這意味著在區塊鏈這一分布式系統中,是通過各個節點來識別、傳播和記載信息。
     
    如何在分布式系統中高效地達成共識是分布式計算領域的重要研究問題。

    拜占庭將軍問題

    1982年,Leslie Lamport提出一個故事模型:擁有巨大財富的拜占庭帝國被鄰國垂涎已久,然而想要拿下拜占庭,周圍鄰邦必須同時進攻。然而彼此相距甚遠,中間如果有叛徒必定無法完成進攻。
     
    這就相當于一個由非信任或半信任的鄰國構成的分布式網絡,在這一環境中,各鄰邦如何達成正確的共識?
     
    這樣就可以理解,區塊鏈所在的無效區塊或問題區塊環境(拜占庭),其中多達三分之一的參與者可能是具有優勢或控制網絡的攻擊者。如何確保各個節點得到一致的執行結果?
    共識算法
     
    共識算法解決的是對某個提案 (Proposal),大家達成一致意見的過程。
     
    提案的含義在分布式系統中十分寬泛,如多個事件發生的順序, 某個鍵對應的值, 誰是領導等。可以認為任何需要達成一致的信息都是一個提案。實踐中,一致性的結果往往還需要客戶端的特殊支持,典型地通過訪問足夠多個服務節點 (背書節點) 來驗證確保獲取共識后結果。
     
    實際上,如果分布式系統中各個節點都能保證以十分強大的性能 (瞬間響應,高吞吐) 無故障的運行,則實現共識過程并不復雜,簡單通過多播過程投票即可。可惜的是,現實中這樣 “完美” 的系統并不存在,如響應請求往往存在時延,網絡會發生中斷,節點會發生故障,甚至存在惡意節點故意要破壞系統。一般地,把故障 (不響應) 的情況稱為 “非拜占庭錯誤”,惡意響應的情況稱為 “拜占庭錯誤” (對應節點為拜占庭節點)。
     
    針對非拜占庭錯誤的情況,一般包括 Paxos、Raft算法及其變種。對于要能容忍拜占庭錯誤的情況,一般包括PBFT系列、PoW系列算法等。從概率角度,PBFT系列算法是確定的,一旦達成共識就不可逆轉; 而PoW系列算法則是不確定的,隨著時間推移,被推翻的概率越來越小。 

    PBFT算法

     實用拜占庭容錯算法(Practical Byzantine Fault Tolerance Algorithm,PBFT),是首個實用的在異步分布式網絡中實現拜占庭容錯的共識算法。
     
    分布式網絡的異步是指不對節點的相對處理速度與消息遞送時間延遲做任何設定。所謂拜占庭容錯,是指在一個若干服務器的系統中,存在非拜占庭錯誤,即系統中存在少量拜占庭出錯節點,仍然能形成共識,則稱該系統是拜占庭容錯的。
     
    PBFT采用三階段的協議,分別是預準備、準備、確認。預準備和準備階段保證發送請求的順序執行;確認階段保證確認請求的順序。
     
    是保證所有正常節點按照相同的順序執行所有有效的客戶請求。

    分布式一致性算法 

    傳統靜態拓撲主從模型分布式一致性算法存在嚴重負載不均及單點性能瓶頸效應,且崩潰節點大于集群規模的 50% 時算法無法正常工作。針對上述問題,永旗鏈 (VBC) 提出基于動態拓撲及有限表決思想的分布式一致性算法 (YAC – Yet Another Consensus), 這種算法伴隨模塊化架構以及簡易實現。
     
    算法動態生成參與一致性表決的成員子集及Leader節點并時分遷移,形成統計負載均衡;去除要求全體多數派成員參與表決的強約束,使算法具備更高的失效容忍性;并通過日志鏈機制重新建立算法安全性約束,同時證明了算法的正確性。
     
    分布式計算技術的發展平衡了13益膨脹的應用計算性能需求與單機性能瓶頸之間的矛盾,一致性問題是保證分布式系統正確性與可靠性的核心問題。

    傳統分布式一致性算法,無論幕于 P2P 模型還是主從模型,都存在必須要求半數以上節點存活并參加一致性表決的強約束,也稱法定集約束。這是由于從集合論的角度,不可能存在兩個多數派成員集合同時投票贊成兩個不同議案,因此從數學角度確保一致性算法的正確性,這顯著制約了算法的失效容忍性上限。

    YAC算法

    YAC 分布式系統針對上述傳統主流分布式算法中存在的問題提出了改良方法。YAC 算法不采用固定Leader節點,而采用特定的策略動態生成決策成員集合,該集合在集群成員節點中隨時域動態遷移,形成統計負載均衡,作為臨時負載中心的Leader角色也采用共識機制隨上述集合的產生動態生成。YAC 算法放棄采用傳統分布式一致性算法中關于半數以上成員節點組成法定集參加表決的幄約束,而在特定時間片內由映射的角色成員集合參與一致性表決。
     
    該算法允許實現輕量級客戶端,而不需要維護交易的完整歷史。每個客戶端都與一個用戶相連,該用戶持有區塊鏈系統中注冊的公鑰。首先,客戶端發送交易至排序服務,然后為交易排序和發出提議區塊(一組將被節點驗證的交易)。最后,排序服務與所有節點共享提議區塊。

    在收到排序服務的提議區塊后,節點會對已驗證的提議區塊進行計算。當節點對區塊哈希值進行投票時,它會生成當前回合的節點順序。該順序是節點的排列,用于在網絡中傳播選票。該順序由一個取區塊哈希值及初始節點列表為參數的函數生成。排序函數應為純函數,并返回分布一致的列表。
     
    在這一過程中,客戶端的角色是生成交易并將其發送給節點,網絡中的每個客戶端都將自己的交易傳播到排序服務。排序服務收集所有交易,對其進行排序并生成提議區塊。節點負責對提議區塊中的交易達成一致,并在區塊中存儲已達成一致的交易。為驗證提議區塊,它需維護完整的交易歷史。
     
    YAC 與已知的驗證節點集合共同合作,主要受傳統 PBFT 算法的影響,但在其基礎上有顯著的提高。傳統的基于領導者的算法有一個明顯的弱點: 領導者暴露在 DoS 攻擊之下,可以審查交易或投票。YAC 算法不需要選舉領導者,每個節點都可以收集協作信息。
     
    為確保算法安全性,即中間不含寫操作的情形下,向集群任意 點發起的任意讀請求序列讀取到的狀態值序列都一致,YAC 定義了下列安全性約束:
     
    約束 1:如果一個節點支持一個決議,那么本時間片內不再支持任何其他決議。

    約束 2:表決團是原子的,當且僅當半數以上的成員支持一項決議,該決議才獲得通過。

    約束 3:一個時間片內僅執行一次表決,如果一個時間片內,節點未表決通過或被通知通過一個表決成功的議案,那么節點生成一個空的 Log Entry 鏈接到本地 Log Chain 副本中。

    約束 4:如果同一時問片內,Log Chain的對應Log Entry在集群中同時存在空和非空版本,那么非空Log Entry對應正確的主分支版本。
    版權申明:本內容來自于互聯網,屬第三方匯集推薦平臺。本文的版權歸原作者所有,文章言論不代表鏈門戶的觀點,鏈門戶不承擔任何法律責任。如有侵權請聯系QQ:3341927519進行反饋。
    相關新聞
    發表評論

    請先 注冊/登錄 后參與評論

      回頂部
    • <option id="cacee"><noscript id="cacee"></noscript></option>
    • <table id="cacee"><noscript id="cacee"></noscript></table>
    • <td id="cacee"></td>
    • <option id="cacee"></option>
    • <table id="cacee"></table>
    • <option id="cacee"><option id="cacee"></option></option>
    • <table id="cacee"><source id="cacee"></source></table><td id="cacee"><rt id="cacee"></rt></td>
      <option id="cacee"><option id="cacee"></option></option>
      妖精视频