區(qū)塊鏈分布式系統(tǒng)面臨一致性問題及共識算法的理論知識解析

共識機制已經(jīng)成為了目前區(qū)塊鏈系統(tǒng)性能提升的關(guān)鍵瓶頸。

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

分布式系統(tǒng)面臨的挑戰(zhàn)

區(qū)塊鏈?zhǔn)且粋€分布式系統(tǒng)，分布式系統(tǒng)碰到的第一個問題就是一致性問題。

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

如果一個分布式系統(tǒng)無法保證處理結(jié)果一致的話，那任何建立于其上的業(yè)務(wù)系統(tǒng)都無法正常工作。

分布式系統(tǒng)面臨的主要挑戰(zhàn)包括：

1）資源受限：節(jié)點間的通信需要通過網(wǎng)絡(luò)，而網(wǎng)絡(luò)存在帶寬限制和時延，節(jié)點也無法做到瞬間響應(yīng)和高吞吐。

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

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

4）并發(fā)：分布式系統(tǒng)的目的，是為了更好的共享資源。同步調(diào)用會讓系統(tǒng)阻塞，因此節(jié)點間通信通常設(shè)計成異步的。

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

由于上述挑戰(zhàn)的存在，分布式系統(tǒng)中的一致性保證機制是分布式系統(tǒng)設(shè)計中最關(guān)鍵也是最有難度的領(lǐng)域，分布式系統(tǒng)中關(guān)于一致性的理論基礎(chǔ)已經(jīng)比較完善，在理論指導(dǎo)下，學(xué)術(shù)界和業(yè)界都提出了很多的共識算法試圖解決分布式系統(tǒng)中的一致性問題。

接下來我們先來了解一下分布式系統(tǒng)中關(guān)于一致性的理論基礎(chǔ)，再基于理論來分析幾個被區(qū)塊鏈項目所廣泛采用的一致算法。

共識算法的理論基礎(chǔ)

FLP不可能定理

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

在網(wǎng)絡(luò)可靠，存在節(jié)點失效（即便只有一個）的最小化異步模型系統(tǒng)中，不存在一個可以解決一致性問題的確定性算法。

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

CAP定理

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

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

CAP定理即描述了分布式系統(tǒng)中關(guān)于一致性和可用性的關(guān)系：

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

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

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

拜占庭將軍問題

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

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

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

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

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

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

DSS猜想

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

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

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

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

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

區(qū)塊鏈分布式系統(tǒng)面臨一致性問題及共識算法的理論知識解析