摘要
在1985年，由Fischer、Lynch和Patterson三位科學(xué)家發(fā)表的論文中进胯，提出了FLP理論。FLP理論證明了原押，在一個(gè)完全異步的分布式系統(tǒng)中胁镐，如果有一個(gè)節(jié)點(diǎn)出現(xiàn)故障，沒有任何一種共識(shí)協(xié)議诸衔，能夠?qū)崿F(xiàn)完全的一致性盯漂。
在2002年，Lynch和Gilbert發(fā)表的論文中笨农，提出了CAP理論就缆。CAP理論證明了，在一個(gè)分布式系統(tǒng)中谒亦，最多只能同時(shí)滿足一致性(Consistency)竭宰、可用性(Availability)和分區(qū)容錯(cuò)性(Partition tolerance)這三項(xiàng)中的兩項(xiàng)空郊。
區(qū)塊鏈作為典型的分布式系統(tǒng)，F(xiàn)LP和CAP同樣適用于區(qū)塊鏈切揭。本文將基于FLP理論和CAP理論狞甚，分析一致性(Consistency)、可用性(Availability)和分區(qū)容錯(cuò)性(Partition tolerance)與區(qū)塊鏈不可能三角間的邏輯關(guān)系廓旬，從而解釋為什么區(qū)塊鏈不可能三角不可突破哼审。
1. FLP理論概要
1985年4月，F(xiàn)ischer孕豹，Lynch和Patterson證明的FLP理論涩盾，是最重要的分布式系統(tǒng)理論之一，他們也憑借論證FLP理論的論文励背，獲得了分布式計(jì)算中最具影響力的Dijkstra論文獎(jiǎng)旁赊。
FLP理論證明了，在異步通信系統(tǒng)中椅野，存在節(jié)點(diǎn)失效（即便只有一個(gè)），不存在一個(gè)可以解決一致性問題的確定性算法籍胯。
在同步的系統(tǒng)中竟闪，達(dá)成共識(shí)是可以被解決的。因?yàn)樵谕较到y(tǒng)中杖狼，當(dāng)有進(jìn)程出現(xiàn)故障炼蛤，或者響應(yīng)超時(shí)，我們可以認(rèn)定它已經(jīng)崩潰蝶涩。
在異步的系統(tǒng)中理朋，當(dāng)一個(gè)進(jìn)程出現(xiàn)故障，或者響應(yīng)丟失時(shí)绿聘，是無法檢測到的嗽上。在這樣的條件下，如果其中有任意一個(gè)進(jìn)程出現(xiàn)問題熄攘，沒有任何一個(gè)分布式算法兽愤，可以讓所有的非故障進(jìn)程，達(dá)成一致性共識(shí)挪圾。
因?yàn)橛蠪LP不可能性的限制浅萧，大部分區(qū)塊鏈項(xiàng)目的共識(shí)算法都把大部分節(jié)點(diǎn)是誠實(shí)的和滿足一定的同步性作為前提。POW認(rèn)為51% 的節(jié)點(diǎn)是誠實(shí)的哲思，并且有一定的同步性洼畅。POS和PBFT也認(rèn)為大部分節(jié)點(diǎn)（66%）是誠實(shí)的.
2. CAP理論概要
在2000年的分布式計(jì)算原則研討會(huì)(PODC)上，計(jì)算機(jī)科學(xué)家埃里克.布魯爾針對分布式計(jì)算系統(tǒng)的一致性(Consistency)棚赔、可用性(Availability)帝簇、分區(qū)容錯(cuò)性(Partition-tolerant)提出了猜想徘郭。在2002年，他的猜想得到了來自麻省理工學(xué)院的兩位教授Nancy Lynch 和 Seth Gilbert的證明己儒，并被稱為CAP定理崎岂。
CAP定理證明了：當(dāng)網(wǎng)絡(luò)存在分區(qū)時(shí)，提供可靠的原子一致性數(shù)據(jù)是不可能的闪湾，但是想要實(shí)現(xiàn)一致性冲甘、可用性、分區(qū)容錯(cuò)性途样，三個(gè)屬性中的兩個(gè)是可行的江醇。在異步通信系統(tǒng)中，當(dāng)沒有鎖提供時(shí)何暇，如果出現(xiàn)消息丟失陶夜，即使允許過時(shí)的數(shù)據(jù)返回，提供一致性數(shù)據(jù)也是不可能的裆站。在同步通信系統(tǒng)中条辟，可以在一致性和可用性間取得一定的平衡。
2.1. 一致性(Consistency)
CAP理論的論證中宏胯，把一致性定義限定在原子數(shù)據(jù)對象上羽嫡，這和其他大多數(shù)正式定義一致性服務(wù)的方法相同。滿足一致性條件的系統(tǒng)肩袍，對所有操作都有統(tǒng)一記錄杭棵，這些操作記錄看起來像是一個(gè)單獨(dú)的實(shí)例完成的。這要求分布式系統(tǒng)的所有請求必須進(jìn)行同步氛赐，然后才能執(zhí)行操作魂爪。最終呈現(xiàn)的結(jié)果，像是同一個(gè)節(jié)點(diǎn)在同一時(shí)間響應(yīng)艰管，然后執(zhí)行的一樣滓侍。
這是提供給用戶理解的，最簡單的一致性保障模型蛙婴，也是給設(shè)計(jì)分布式客戶端應(yīng)用的人理解的最簡單的模型粗井。
2.2. 可用性(Availability)
為了能讓分布式系統(tǒng)持續(xù)可用，每個(gè)請求會(huì)被發(fā)送給一個(gè)系統(tǒng)中的正常節(jié)點(diǎn)街图，并收到響應(yīng)浇衬。這是任何分布式服務(wù)使用的算法必須要滿足的。
CAP理論的論證中餐济，將可用性定義為兩種：
l 弱可用性：在終止之前耘擂，算法運(yùn)行的多久是沒有邊界的，因此允許沒有邊界的計(jì)算絮姆。
l 強(qiáng)可用性：當(dāng)服務(wù)網(wǎng)絡(luò)發(fā)生錯(cuò)誤時(shí)醉冤，每個(gè)請求也必須被響應(yīng)秩霍。
在弱可用性條件下，系統(tǒng)對響應(yīng)時(shí)間可以不做保證蚁阳，但是必須做出響應(yīng)铃绒，當(dāng)系統(tǒng)出現(xiàn)錯(cuò)誤時(shí)，并不保證對請求做出響應(yīng)螺捐。而在強(qiáng)可用性條件下颠悬，即使系統(tǒng)出現(xiàn)錯(cuò)誤，請求也必須得到響應(yīng)定血。
2.3. 分區(qū)容錯(cuò)性(Partition-tolerant)
CAP理論的論證中赔癌，分區(qū)指的是，網(wǎng)絡(luò)中允許丟失從一個(gè)節(jié)點(diǎn)發(fā)送到另一個(gè)節(jié)點(diǎn)的任意數(shù)量的消息澜沟。這意味著當(dāng)網(wǎng)絡(luò)中出現(xiàn)分區(qū)時(shí)灾票，從一個(gè)分區(qū)中的節(jié)點(diǎn)發(fā)送給另外一個(gè)分區(qū)的節(jié)點(diǎn)的消息將會(huì)全部丟失。
分區(qū)容錯(cuò)指的是茫虽，在出現(xiàn)分區(qū)時(shí)刊苍，系統(tǒng)依然能夠滿足以上定義中的一致性和可用性。原子性要求意味著每一個(gè)響應(yīng)將會(huì)是原子性的濒析，盡管任意作為算法的一部分的消息可能不會(huì)被傳遞班缰。可用性要求意味著悼枢，每個(gè)節(jié)點(diǎn)收到的客戶端請求必須被響應(yīng)，盡管任意的消息都可能丟失脾拆。
3. 用CAP理論來解鎖區(qū)塊鏈不可能三角為什么不可突破
在區(qū)塊鏈領(lǐng)域中馒索，安全性、可擴(kuò)展性名船、去中心化绰上，三者被稱作區(qū)塊鏈的“不可能三角”，意思是說渠驼，在同一個(gè)區(qū)塊鏈系統(tǒng)中蜈块，想要同時(shí)做到三者，并且都達(dá)到足夠高的要求迷扇，是不可能做到的百揭。
我們的基本論證思路是，CAP理論在分布式系統(tǒng)中成立蜓席，區(qū)塊鏈屬于分布式系統(tǒng)器一，區(qū)塊鏈必然遵守CAP理論，只要能證明CAP理論中的一致性(Consistency)厨内、可用性(Availability)和分區(qū)容錯(cuò)性(Partition tolerance)祈秕，與區(qū)塊鏈的不可能三角存在相應(yīng)的邏輯關(guān)系渺贤，即可證明區(qū)塊鏈不可能三角不可突破。
3.1. 一致性與安全性
在CAP理論的證明過程中请毛，證明了在異步網(wǎng)絡(luò)模型中志鞍，實(shí)現(xiàn)一個(gè)讀/寫數(shù)據(jù)對象同時(shí)具備可用性和一致性是不可能的。我們將該結(jié)論和證明過程方仿，對應(yīng)到區(qū)塊鏈系統(tǒng)中固棚。
在CAP理論限定的網(wǎng)絡(luò)環(huán)境中，我們假設(shè)一個(gè)區(qū)塊鏈系統(tǒng)中兼丰，存在A和B兩個(gè)節(jié)點(diǎn)玻孟，其中A和B同時(shí)記錄了一個(gè)地址H的加密貨幣余額為X1，此時(shí)A和B出現(xiàn)了分區(qū)鳍征。
當(dāng)用戶在A節(jié)點(diǎn)所在的分區(qū)發(fā)起一筆交易時(shí)黍翎，地址H中的余額將會(huì)發(fā)生變化，成為X2艳丛。當(dāng)用戶在B節(jié)點(diǎn)所在的分區(qū)發(fā)起一次余額查詢操作時(shí)匣掸，地址H中的余額依然是X1。由此我們說區(qū)塊鏈系統(tǒng)中，出現(xiàn)了賬本不一致的情況敛劝。
當(dāng)區(qū)塊鏈系統(tǒng)中出現(xiàn)不一致狀態(tài)時(shí)离陶，我們認(rèn)定這樣的區(qū)塊鏈系統(tǒng)是不安全的。在這樣的定義下送爸，一致性是區(qū)塊鏈系統(tǒng)安全的基本前提∨停或者說區(qū)塊鏈的安全性是比分布式系統(tǒng)的一致性更加嚴(yán)格的需求袭厂。安全性>一致性。
3.2. 可用性與可擴(kuò)展性
在CAP理論的可用性定義中球匕，分為弱可用性和強(qiáng)可用性纹磺，但是這兩種可用性都要求，系統(tǒng)可以對所有正常請求做出響應(yīng)亮曹。從技術(shù)的角度來講橄杨，即是可以實(shí)現(xiàn)正常的可讀可寫。
在區(qū)塊鏈系統(tǒng)中照卦，可擴(kuò)展性指的是式矫，每秒可以處理的交易量。從技術(shù)的角度來講役耕，高可擴(kuò)展性即是實(shí)現(xiàn)每秒鐘高頻次的可讀可寫操作衷佃。
從邏輯上，我們可以看出蹄葱，可用性是比可擴(kuò)展性更基礎(chǔ)的網(wǎng)絡(luò)要求氏义，不能實(shí)現(xiàn)可用性的區(qū)塊鏈系統(tǒng)锄列，是不能實(shí)現(xiàn)可擴(kuò)展性的，即是可用性是可擴(kuò)展性的前提惯悠×谟剩或者說區(qū)塊鏈的可擴(kuò)展性是比分布式系統(tǒng)的可用性更加嚴(yán)格】松簦可擴(kuò)展性>可用性筒严。
3.3. 分區(qū)容錯(cuò)性與去中心化
在CAP理論中，分區(qū)被認(rèn)為是分布式系統(tǒng)必然存在的情萤。事實(shí)也的確如此鸭蛙，在真實(shí)分布式環(huán)境中，不可能保證系統(tǒng)中的每個(gè)節(jié)點(diǎn)筋岛，都不會(huì)出現(xiàn)任何故障娶视。
去中心化作為區(qū)塊鏈的基本特征，意味著區(qū)塊鏈系統(tǒng)必然是分布式的睁宰，也就是說去中心化必定導(dǎo)致發(fā)生分區(qū)的可能肪获，由此也意味著分區(qū)容錯(cuò)性是實(shí)現(xiàn)去中心化的前提。
3.4. 現(xiàn)有共識(shí)算法對CAP的平衡
在CAP理論中柒傻，分區(qū)被認(rèn)為是分布式系統(tǒng)必然存在的孝赫，所以討論沒有分區(qū)情況的分布式系統(tǒng)是沒有意義的。區(qū)塊鏈作為典型的分布式系統(tǒng)红符，其不同的共識(shí)算法在滿足分區(qū)的前提下青柄，對系統(tǒng)的一致性(Consistency)和可用性(Availability)做出了一定的平衡。
Tendermint: Tendermint是POS類型的共識(shí)算法预侯，主要包括NewHeight -> Propose -> Prevote -> Precommit -> Commit五個(gè)階段刹前。其中Propose -> Prevote -> Precommit屬于共識(shí)階段，是算法的核心雌桑，被稱作一個(gè)Round。在進(jìn)行區(qū)塊的提交確認(rèn)時(shí)祖今，一個(gè)區(qū)塊可能需要多個(gè)Round校坑。在多個(gè)Round中，區(qū)塊的高度并不會(huì)增加千诬，只是向系統(tǒng)提交空塊耍目，并且一個(gè)區(qū)塊一旦被確認(rèn)，是不可能被修改的徐绑。所以Tendermint理論上有可能被卡住邪驮，區(qū)塊高度永遠(yuǎn)不會(huì)增加。 這意味著Tendermint在出現(xiàn)分區(qū)時(shí)傲茄，更加側(cè)重于一致性(Consistency)毅访。
Casper FFG: Casper FFG是POS類型的共識(shí)算法沮榜。在Casper FFG的設(shè)計(jì)中， 優(yōu)先考慮一致性喻粹，因?yàn)樗辉试S在沒有絕大多數(shù)驗(yàn)證者同意的情況下完成checkpoint蟆融，這樣區(qū)塊也就不會(huì)達(dá)到最終的確認(rèn)狀態(tài)。
Algorand: Algorand是POS類型的共識(shí)算法守呜。Algorand與Tendermint的設(shè)計(jì)中有類似的地方型酥，當(dāng)出現(xiàn)一致性和可用性沖突時(shí)，系統(tǒng)會(huì)更傾向于產(chǎn)生空塊查乒，不會(huì)產(chǎn)生真正意義的區(qū)塊弥喉。所以Algorand更優(yōu)先考慮一致性。
Dfinity: Dfinity是POS類型的共識(shí)算法玛迄。當(dāng)網(wǎng)絡(luò)出現(xiàn)分區(qū)時(shí)由境，它會(huì)自動(dòng)使隨機(jī)信標(biāo)暫停，不允許網(wǎng)絡(luò)中的任何分區(qū)繼續(xù)憔晒。所以Dfinity更優(yōu)先考慮一致性藻肄。
POW:當(dāng)使用POW的網(wǎng)絡(luò)出現(xiàn)分區(qū)時(shí)，所有的分區(qū)都可以正常的進(jìn)行出塊拒担，等到網(wǎng)絡(luò)恢復(fù)嘹屯，分區(qū)結(jié)束時(shí)，會(huì)遵循最長鏈原則从撼，不同分區(qū)的鏈將會(huì)進(jìn)行合并州弟，最終成為一條鏈。因此POW優(yōu)先考慮可用性低零。
POC:POC的全稱是Proof of Credit ,是全球開源社區(qū)項(xiàng)目NULS婆翔，創(chuàng)新使用的共識(shí)算法。當(dāng)使用POC的網(wǎng)絡(luò)出現(xiàn)分區(qū)時(shí)掏婶，所有分區(qū)都可以正常進(jìn)行出塊啃奴。等到網(wǎng)絡(luò)恢復(fù)時(shí)，與POW類似雄妥，將會(huì)遵循最長鏈原則最蕾，進(jìn)行區(qū)塊鏈的合并。因此NULS創(chuàng)新使用的POC優(yōu)先考慮的是可用性老厌。
4. 結(jié)論
通過以上對一致性(Consistency)與安全性枝秤、可用性(Availability)與可擴(kuò)展性醋拧、分區(qū)容錯(cuò)性(Partition-tolerant)與去中心化的邏輯關(guān)系推導(dǎo)，我們可以得出以下結(jié)論：
一致性(Consistency)是安全性的必要條件
可用性(Availability)是可擴(kuò)展性的必要條件
分區(qū)容錯(cuò)性是去中心化的必要條件
又通過CAP理論可以知道一致性、可用性丹壕、分區(qū)容錯(cuò)性是不能同時(shí)滿足的庆械，所以我們可以得出：在CAP理論限定的條件下，安全性雀费、可擴(kuò)展性干奢、去中心化不能同時(shí)滿足，即是區(qū)塊鏈的不可能三角不可突破盏袄。
作者簡介：
黃連金
著名區(qū)塊鏈專家忿峻，核聚鏈?zhǔn)紫茖W(xué)家、美國 DistributedApps CEO辕羽、中國電子學(xué)會(huì)區(qū)塊鏈分會(huì)專家委員逛尚、NULS技術(shù)顧問。
向文波
Java軟件工程師刁愿，Cryptotech-Writer绰寞，NULS Core Team成員。專注于區(qū)塊鏈技術(shù)研究和區(qū)塊鏈解決方案铣口。
參考文獻(xiàn)：
Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services Seth Gilbert滤钱，Nancy Lynch
Impossibility of Distributed Consensus with One Faulty Process MICHAEL J. FISCHER，NANCY A. LYNCH脑题，MICHAEL S. PATERSON
分布式系統(tǒng)的CAP理論：https://www.hollischuang.com/archives/666
比較各種共識(shí)算法的Finality和Liveness:
https://www.odaily.com/post/5134107
Finality in Blockchain Consensus:
https://medium.com/mechanism-labs/finality-in-blockchain-consensus-d1f83c120a9a
