電子發燒友網>區塊鏈>區塊鏈分布式系統面臨一致性問題及共識算法的理論知識解析

區塊鏈分布式系統面臨一致性問題及共識算法的理論知識解析

共識機制已經成為了目前區塊鏈系統性能提升的關鍵瓶頸。

單一的共識算法均存在各種問題，如PoW算法存在消耗大量計算資源及性能低下的問題，PoS或DPoS存在“富豪統治”問題，融合多種共識算法優勢的想法正受到越來越廣泛的關注。

分布式系統面臨的挑戰

區塊鏈是一個分布式系統，分布式系統碰到的第一個問題就是一致性問題。

在分布式系統中，一致性是指：對于系統中的多個服務節點，給定一系列操作，在協議（往往通過某種共識算法）保障下，試圖使得他們對處理結果達成某種程度的一致。

如果一個分布式系統無法保證處理結果一致的話，那任何建立于其上的業務系統都無法正常工作。

分布式系統面臨的主要挑戰包括：

1）資源受限：節點間的通信需要通過網絡，而網絡存在帶寬限制和時延，節點也無法做到瞬間響應和高吞吐。

2）故障的獨立性：系統的任何一個模塊都可能發生故障，如節點之間的網絡通訊是不可靠的，隨時可能發生網絡故障或任意延遲；節點的處理可能是錯誤的，甚至節點自身隨時可能宕機。

3）不透明性：分布式系統中任何組件所在的位置、性能、狀態、是否故障等情況對于其它組件來說都是不可見的、也無法預知的。

4）并發：分布式系統的目的，是為了更好的共享資源。同步調用會讓系統阻塞，因此節點間通信通常設計成異步的。

5）缺乏全局時鐘：在程序需要協作時，它們通過交換消息來協調它們的動作。緊密的協調經常依賴于對程序動作發生時間的共識，但是，實際上網絡上計算機同步時鐘的準確性受到極大的限制，即沒有一個一致的全局時間的概念。這是通過網絡發送消息作為唯一的通信方式這一事實帶來的直接結果。

由于上述挑戰的存在，分布式系統中的一致性保證機制是分布式系統設計中最關鍵也是最有難度的領域，分布式系統中關于一致性的理論基礎已經比較完善，在理論指導下，學術界和業界都提出了很多的共識算法試圖解決分布式系統中的一致性問題。

接下來我們先來了解一下分布式系統中關于一致性的理論基礎，再基于理論來分析幾個被區塊鏈項目所廣泛采用的一致算法。

共識算法的理論基礎

FLP不可能定理

因為同步通信中的一致性被證明是可以達到的，因此一直有人嘗試各種算法解決異步環境的一致性問題。然而Fischer， Lynch and Patte rson三位作者于1985年發表了一篇論文，提出并證明了一個定理，即“FLP不可能定理”：

在網絡可靠，存在節點失效（即便只有一個）的最小化異步模型系統中，不存在一個可以解決一致性問題的確定性算法。

FLP不可能定理論證了最壞的情況是沒有下限，要實現一個完美的容錯的異步的一致性系統是不可能的。

CAP定理

FLP不可能定理只是說明了100%保證一致性是不可能的，這并不影響我們對分布一致性的探索。

例如99%以上的一致性還是完全有可能做到的；又如放寬時間限制，即要求系統在一段時間后最終達到一致性（達不成一致則系統不可用），也是可以做到的；再如，將部分通信改成同步的，犧牲一定的可用性和吞吐量，就能得到一個一致性較強的協議。

CAP定理即描述了分布式系統中關于一致性和可用性的關系：

一個分布式系統最多只能同時滿足（強）一致性（Consistency）、可用性（Availability）和分區容錯性（Partition tolerance）這三項要素中的兩項。

CAP定理起源于計算機科學家埃里克·布魯爾在2000年的分布式計算原則研討會（Symposium on Principles of Distributed Computing（PODC））上提出的一個猜想。在2002年，麻省理工學院（MIT）的Nancy Lynch （跟證明FLP定理的Lynch是同一位）和Seth Gilbert發表了布魯爾猜想的證明，使之成為一個定理。

對于分布式數據系統，分區容錯性是基本要求，因為故障的存在是必然的。因此設計分布式數據系統，就是在一致性和可用性之間取一個平衡。

拜占庭將軍問題

拜占庭將軍問題（Byzantine Generals Problem），是由萊斯利·蘭波特在其同名論文中提出的分布式對等網絡通信容錯問題，對網絡中存在作惡節點的情況進行建模。由于作惡節點的存在，拜占庭將軍問題被認為是容錯性問題中最難的問題類型之一。

萊斯利·蘭波特在其論文中描述了如下問題：

一組拜占庭將軍分別各率領一支軍隊共同圍困一座城市。為了簡化問題，將各支軍隊的行動策略限定為進攻或撤離兩種。因為部分軍隊進攻部分軍隊撤離可能會造成災難性后果，因此各位將軍必須通過投票來達成一致策略，即所有軍隊一起進攻或所有軍隊一起撤離。因為各位將軍分處城市不同方向，他們只能通過信使互相聯系。在投票過程中每位將軍都將自己投票給進攻還是撤退的信息通過信使分別通知其他所有將軍，這樣一來每位將軍根據自己的投票和其他所有將軍送來的信息就可以知道共同的投票結果而決定行動策略。

但問題在于，將軍中可能出現叛徒，他們不僅可能向較為糟糕的策略投票，還可能選擇性地發送投票信息。假始那些忠誠（或是沒有出錯）的將軍仍然能通過多數決定來決定他們的戰略，便稱達到了拜占庭容錯。在此，票都會有一個默認值，若消息（票）沒有被收到，則使用此默認值來投票。

上述的故事映射到計算機系統里，將軍便成了計算機，而信差就是通信系統。雖然上述的問題涉及了電子化的決策支持與信息安全，卻沒辦法單純的用密碼學與數字簽名來解決。因為不正常的電壓仍可能影響整個加密過程，這不是密碼學與數字簽名算法在解決的問題。因此計算機就有可能將錯誤的結果提交去，亦可能導致錯誤的決策。

在分布式對等網絡中需要按照共同一致策略協作的成員計算機即為問題中的將軍，而各成員計算機賴以進行通訊的網絡鏈路即為信使。拜占庭將軍問題描述的就是某些成員計算機或網絡鏈路出現錯誤、甚至被蓄意破壞者控制的情況。

DSS猜想

不同于中心化的分布式系統，去中心化是區塊鏈系統的一個核心特性。去中心化的系統中，為了保證數據可信，需要所有節點參與共識、避免被攻擊（如51%攻擊）、任何節點都要有能力驗證交易的合法性、所有交易要按順序執行和驗證、所有節點都要保存所有的交易數據等。

在分布式系統中，可擴展性是指系統的總體性能隨著節點的增多而提升。在中心化的分布式系統設計中，可擴展性是的、最基本要求之一。對于中心化的系統，要保證可擴展性也是相對簡單的。

而去中心化的全量共識和存儲的要求，是難以擴展的。因為若要可擴展性，就不能要求節點執行全量、全量存儲，而是要分散計算和存儲，每個節點只保存部分數據，即每個交易數據只存儲在少數節點中，但這樣一來，安全性就無法保證，因為攻擊者只要攻擊少數節點，即能控制區塊數據。例如數據分成100份保存在不同節點，那攻擊者只要實施1%攻擊，即能控制其中1份區塊數據，攻擊難度大大降低。

由于去中心化的要求，區塊鏈的分布式系統也有自身特有的理論，其中一個描述了去中心化與可擴展性之間的矛盾，它尚未被嚴格證明，只能被稱為猜想，但實際系統設計過程中卻能感覺到時時受其挑戰：

DSS猜想：去中心化（Decentralization），安全性（Security）和可擴展性（Scalability）這三個屬性，區塊鏈系統最多只能三選其二。

區塊鏈分布式系統面臨一致性問題及共識算法的理論知識解析