在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í)，是無法檢測(cè)到的。在這樣的條件下，如果其中有任意一個(gè)進(jìn)程出現(xiàn)問題，沒有任何一個(gè)分布式算法，可以讓所有的非故障進(jìn)程，達(dá)成一致性共識(shí)。

因?yàn)橛蠪LP不可能性的限制，大部分區(qū)塊鏈項(xiàng)目的共識(shí)算法都把大部分節(jié)點(diǎn)是誠(chéng)實(shí)的和滿足一定的同步性作為前提。POW認(rèn)為51% 的節(jié)點(diǎn)是誠(chéng)實(shí)的，并且有一定的同步性。POS和PBFT也認(rèn)為大部分節(jié)點(diǎn)（66%）是誠(chéng)實(shí)的。

2. CAP理論概要

在2000年的分布式計(jì)算原則研討會(huì)（PODC）上，計(jì)算機(jī)科學(xué)家埃里克。布魯爾針對(duì)分布式計(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ù)對(duì)象上，這和其他大多數(shù)正式定義一致性服務(wù)的方法相同。滿足一致性條件的系統(tǒng)，對(duì)所有操作都有統(tǒng)一記錄，這些操作記錄看起來像是一個(gè)單獨(dú)的實(shí)例完成的。這要求分布式系統(tǒng)的所有請(qǐng)求必須進(jìn)行同步，然后才能執(zhí)行操作。最終呈現(xiàn)的結(jié)果，像是同一個(gè)節(jié)點(diǎn)在同一時(shí)間響應(yīng)，然后執(zhí)行的一樣。

這是提供給用戶理解的，最簡(jiǎn)單的一致性保障模型，也是給設(shè)計(jì)分布式客戶端應(yīng)用的人理解的最簡(jiǎn)單的模型。

2.2.可用性（Availability）

為了能讓分布式系統(tǒng)持續(xù)可用，每個(gè)請(qǐng)求會(huì)被發(fā)送給一個(gè)系統(tǒng)中的正常節(jié)點(diǎn)，并收到響應(yīng)。這是任何分布式服務(wù)使用的算法必須要滿足的。

CAP理論的論證中，將可用性定義為兩種：

· 弱可用性：在終止之前，算法運(yùn)行的多久是沒有邊界的，因此允許沒有邊界的計(jì)算。

· 強(qiáng)可用性：當(dāng)服務(wù)網(wǎng)絡(luò)發(fā)生錯(cuò)誤時(shí)，每個(gè)請(qǐng)求也必須被響應(yīng)。

在弱可用性條件下，系統(tǒng)對(duì)響應(yīng)時(shí)間可以不做保證，但是必須做出響應(yīng)，當(dāng)系統(tǒng)出現(xiàn)錯(cuò)誤時(shí)，并不保證對(duì)請(qǐng)求做出響應(yīng)。而在強(qiáng)可用性條件下，即使系統(tǒng)出現(xiàn)錯(cuò)誤，請(qǐng)求也必須得到響應(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)收到的客戶端請(qǐng)求必須被響應(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ù)對(duì)象同時(shí)具備可用性和一致性是不可能的。我們將該結(jié)論和證明過程，對(duì)應(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)安全的基本前提?；蛘哒f區(qū)塊鏈的安全性是比分布式系統(tǒng)的一致性更加嚴(yán)格的需求。安全性》一致性。

3.2.可用性與可擴(kuò)展性

在CAP理論的可用性定義中，分為弱可用性和強(qiáng)可用性，但是這兩種可用性都要求，系統(tǒng)可以對(duì)所有正常請(qǐ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ò)展性的前提?；蛘哒f區(qū)塊鏈的可擴(kuò)展性是比分布式系統(tǒng)的可用性更加嚴(yán)格?？蓴U(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í)算法對(duì)CAP的平衡

在CAP理論中，分區(qū)被認(rèn)為是分布式系統(tǒng)必然存在的，所以討論沒有分區(qū)情況的分布式系統(tǒng)是沒有意義的。區(qū)塊鏈作為典型的分布式系統(tǒng)，其不同的共識(shí)算法在滿足分區(qū)的前提下，對(duì)系統(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ì)遵循最長(zhǎng)鏈原則，不同分區(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ì)遵循最長(zhǎng)鏈原則，進(jìn)行區(qū)塊鏈的合并。因此NULS創(chuàng)新使用的POC優(yōu)先考慮的是可用性。

注：A《C代表該共識(shí)算法更優(yōu)先考慮Consistency；

C《A代表該共識(shí)算法更優(yōu)先考慮Availability；

4.結(jié)論

通過以上對(duì)一致性（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ū)塊鏈的不可能三角不可突破。