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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

FLP不可能定理

因?yàn)橥酵ㄐ胖械囊恢滦员蛔C明是可以達(dá)到的，因此一直有人嘗試各種算法解決異步環(huán)境的一致性問題。然而Fischer， Lynch and Patterson三位作者于1985年發(fā)表了一篇論文，提出并證明了一個(gè)定理，即“FLP不可能定理”：

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

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

CAP定理

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

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

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

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

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

對(duì)于分布式數(shù)據(jù)系統(tǒng)，分區(qū)容錯(cuò)性是基本要求，因?yàn)楣收系拇嬖谑潜厝坏?。因此設(shè)計(jì)分布式數(shù)據(jù)系統(tǒng)，就是在一致性和可用性之間取一個(gè)平衡。

拜占庭將軍問題

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

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

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

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

上述的故事映射到計(jì)算機(jī)系統(tǒng)里，將軍便成了計(jì)算機(jī)，而信差就是通信系統(tǒng)。雖然上述的問題涉及了電子化的決策支持與信息安全，卻沒辦法單純的用密碼學(xué)與數(shù)字簽名來解決。因?yàn)椴徽５碾妷喝钥赡苡绊懻麄€(gè)加密過程，這不是密碼學(xué)與數(shù)字簽名算法在解決的問題。因此計(jì)算機(jī)就有可能將錯(cuò)誤的結(jié)果提交去，亦可能導(dǎo)致錯(cuò)誤的決策。

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

DSS猜想

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

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

而去中心化的全量共識(shí)和存儲(chǔ)的要求，是難以擴(kuò)展的。因?yàn)槿粢蓴U(kuò)展性，就不能要求節(jié)點(diǎn)執(zhí)行全量、全量存儲(chǔ)，而是要分散計(jì)算和存儲(chǔ)，每個(gè)節(jié)點(diǎn)只保存部分?jǐn)?shù)據(jù)，即每個(gè)交易數(shù)據(jù)只存儲(chǔ)在少數(shù)節(jié)點(diǎn)中，但這樣一來，安全性就無法保證，因?yàn)楣粽咧灰羯贁?shù)節(jié)點(diǎn)，即能控制區(qū)塊數(shù)據(jù)。例如數(shù)據(jù)分成100份保存在不同節(jié)點(diǎn)，那攻擊者只要實(shí)施1%攻擊，即能控制其中1份區(qū)塊數(shù)據(jù)，攻擊難度大大降低。

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

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

上圖演示了區(qū)塊鏈如何在這三個(gè)因素之間作選擇及對(duì)應(yīng)的策略：

若要滿足安全性與去中心化，則需要所有節(jié)點(diǎn)參與共識(shí)、計(jì)算、全量存儲(chǔ)，但由此帶來的問題是失去可擴(kuò)展性，也就是系統(tǒng)的總體性能無法隨著節(jié)點(diǎn)的增多而提升；

若要滿足可擴(kuò)展性與安全性，則需要中心化管理，需要保證參與共識(shí)的節(jié)點(diǎn)是可信的；

若要滿足可擴(kuò)展性與去中心化，則采用分散存儲(chǔ)、計(jì)算的策略，不做全量共識(shí)，則攻擊網(wǎng)絡(luò)的難度降低，安全性難以保證。

共識(shí)算法應(yīng)該滿足的條件

盡管算法多種多樣，可以根據(jù)需要采用各種策略，但大家公認(rèn)的理想的共識(shí)算法應(yīng)該滿足的條件包括：

1） 可終止性（Termination）：一致的結(jié)果在有限時(shí)間內(nèi)能完成；

2） 共識(shí)性（Consensus）：不同節(jié)點(diǎn)最終完成決策的結(jié)果應(yīng)該相同；

3） 合法性（Validity）：決策的結(jié)果必然是其它進(jìn)程提出的提案。