在2002年，Lynch和Gilbert發(fā)表的論文中，提出了CAP理論。CAP理論證明了，在一個分布式系統(tǒng)中，最多只能同時滿足一致性（Consistency）、可用性（Availability）和分區(qū)容錯性（PartiTIon tolerance）這三項中的兩項。

區(qū)塊鏈作為典型的分布式系統(tǒng)，F(xiàn)LP和CAP同樣適用于區(qū)塊鏈。本文將基于FLP理論和CAP理論，分析一致性（Consistency）、可用性（Availability）和分區(qū)容錯性（ParTITIon tolerance）與區(qū)塊鏈不可能三角間的邏輯關(guān)系，從而解釋為什么區(qū)塊鏈不可能三角不可突破。

1.FLP理論概要

1985年4月，F(xiàn)ischer，Lynch和Patterson證明的FLP理論，是最重要的分布式系統(tǒng)理論之一，他們也憑借論證FLP理論的論文，獲得了分布式計算中最具影響力的Dijkstra論文獎。

FLP理論證明了，在異步通信系統(tǒng)中，存在節(jié)點失效（即便只有一個），不存在一個可以解決一致性問題的確定性算法。

在同步的系統(tǒng)中，達成共識是可以被解決的。因為在同步系統(tǒng)中，當(dāng)有進程出現(xiàn)故障，或者響應(yīng)超時，我們可以認定它已經(jīng)崩潰。

在異步的系統(tǒng)中，當(dāng)一個進程出現(xiàn)故障，或者響應(yīng)丟失時，是無法檢測到的。在這樣的條件下，如果其中有任意一個進程出現(xiàn)問題，沒有任何一個分布式算法，可以讓所有的非故障進程，達成一致性共識。

因為有FLP不可能性的限制，大部分區(qū)塊鏈項目的共識算法都把大部分節(jié)點是誠實的和滿足一定的同步性作為前提。POW認為51% 的節(jié)點是誠實的，并且有一定的同步性。POS和PBFT也認為大部分節(jié)點（66%）是誠實的。

2. CAP理論概要

在2000年的分布式計算原則研討會（PODC）上，計算機科學(xué)家埃里克。布魯爾針對分布式計算系統(tǒng)的一致性（Consistency）、可用性（Availability）、分區(qū)容錯性（ParTItion-tolerant）提出了猜想。在2002年，他的猜想得到了來自麻省理工學(xué)院的兩位教授Nancy Lynch 和 Seth Gilbert的證明，并被稱為CAP定理。

CAP定理證明了：當(dāng)網(wǎng)絡(luò)存在分區(qū)時，提供可靠的原子一致性數(shù)據(jù)是不可能的，但是想要實現(xiàn)一致性、可用性、分區(qū)容錯性，三個屬性中的兩個是可行的。在異步通信系統(tǒng)中，當(dāng)沒有鎖提供時，如果出現(xiàn)消息丟失，即使允許過時的數(shù)據(jù)返回，提供一致性數(shù)據(jù)也是不可能的。在同步通信系統(tǒng)中，可以在一致性和可用性間取得一定的平衡。

2.1.一致性（Consistency）

CAP理論的論證中，把一致性定義限定在原子數(shù)據(jù)對象上，這和其他大多數(shù)正式定義一致性服務(wù)的方法相同。滿足一致性條件的系統(tǒng)，對所有操作都有統(tǒng)一記錄，這些操作記錄看起來像是一個單獨的實例完成的。這要求分布式系統(tǒng)的所有請求必須進行同步，然后才能執(zhí)行操作。最終呈現(xiàn)的結(jié)果，像是同一個節(jié)點在同一時間響應(yīng)，然后執(zhí)行的一樣。

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

2.2.可用性（Availability）

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

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

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

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

在弱可用性條件下，系統(tǒng)對響應(yīng)時間可以不做保證，但是必須做出響應(yīng)，當(dāng)系統(tǒng)出現(xiàn)錯誤時，并不保證對請求做出響應(yīng)。而在強可用性條件下，即使系統(tǒng)出現(xiàn)錯誤，請求也必須得到響應(yīng)。

2.3.分區(qū)容錯性（Partition-tolerant）

CAP理論的論證中，分區(qū)指的是，網(wǎng)絡(luò)中允許丟失從一個節(jié)點發(fā)送到另一個節(jié)點的任意數(shù)量的消息。這意味著當(dāng)網(wǎng)絡(luò)中出現(xiàn)分區(qū)時，從一個分區(qū)中的節(jié)點發(fā)送給另外一個分區(qū)的節(jié)點的消息將會全部丟失。

分區(qū)容錯指的是，在出現(xiàn)分區(qū)時，系統(tǒng)依然能夠滿足以上定義中的一致性和可用性。原子性要求意味著每一個響應(yīng)將會是原子性的，盡管任意作為算法的一部分的消息可能不會被傳遞?？捎眯砸笠馕吨?，每個節(jié)點收到的客戶端請求必須被響應(yīng)，盡管任意的消息都可能丟失。

3.用CAP理論來解鎖區(qū)塊鏈不可能三角為什么不可突破

在區(qū)塊鏈領(lǐng)域中，安全性、可擴展性、去中心化，三者被稱作區(qū)塊鏈的“不可能三角”，意思是說，在同一個區(qū)塊鏈系統(tǒng)中，想要同時做到三者，并且都達到足夠高的要求，是不可能做到的。

我們的基本論證思路是，CAP理論在分布式系統(tǒng)中成立，區(qū)塊鏈屬于分布式系統(tǒng)，區(qū)塊鏈必然遵守CAP理論，只要能證明CAP理論中的一致性（Consistency）、可用性（Availability）和分區(qū)容錯性（Partition tolerance），與區(qū)塊鏈的不可能三角存在相應(yīng)的邏輯關(guān)系，即可證明區(qū)塊鏈不可能三角不可突破。

3.1.一致性與安全性

在CAP理論的證明過程中，證明了在異步網(wǎng)絡(luò)模型中，實現(xiàn)一個讀/寫數(shù)據(jù)對象同時具備可用性和一致性是不可能的。我們將該結(jié)論和證明過程，對應(yīng)到區(qū)塊鏈系統(tǒng)中。

在CAP理論限定的網(wǎng)絡(luò)環(huán)境中，我們假設(shè)一個區(qū)塊鏈系統(tǒng)中，存在A和B兩個節(jié)點，其中A和B同時記錄了一個地址H的加密貨幣余額為X1，此時A和B出現(xiàn)了分區(qū)。

當(dāng)用戶在A節(jié)點所在的分區(qū)發(fā)起一筆交易時，地址H中的余額將會發(fā)生變化，成為X2。當(dāng)用戶在B節(jié)點所在的分區(qū)發(fā)起一次余額查詢操作時，地址H中的余額依然是X1。由此我們說區(qū)塊鏈系統(tǒng)中，出現(xiàn)了賬本不一致的情況。

當(dāng)區(qū)塊鏈系統(tǒng)中出現(xiàn)不一致狀態(tài)時，我們認定這樣的區(qū)塊鏈系統(tǒng)是不安全的。在這樣的定義下，一致性是區(qū)塊鏈系統(tǒng)安全的基本前提?；蛘哒f區(qū)塊鏈的安全性是比分布式系統(tǒng)的一致性更加嚴格的需求。安全性》一致性。

3.2.可用性與可擴展性

在CAP理論的可用性定義中，分為弱可用性和強可用性，但是這兩種可用性都要求，系統(tǒng)可以對所有正常請求做出響應(yīng)。從技術(shù)的角度來講，即是可以實現(xiàn)正常的可讀可寫。

在區(qū)塊鏈系統(tǒng)中，可擴展性指的是，每秒可以處理的交易量。從技術(shù)的角度來講，高可擴展性即是實現(xiàn)每秒鐘高頻次的可讀可寫操作。

從邏輯上，我們可以看出，可用性是比可擴展性更基礎(chǔ)的網(wǎng)絡(luò)要求，不能實現(xiàn)可用性的區(qū)塊鏈系統(tǒng)，是不能實現(xiàn)可擴展性的，即是可用性是可擴展性的前提?；蛘哒f區(qū)塊鏈的可擴展性是比分布式系統(tǒng)的可用性更加嚴格?？蓴U展性》可用性。

3.3.分區(qū)容錯性與去中心化

在CAP理論中，分區(qū)被認為是分布式系統(tǒng)必然存在的。事實也的確如此，在真實分布式環(huán)境中，不可能保證系統(tǒng)中的每個節(jié)點，都不會出現(xiàn)任何故障。

去中心化作為區(qū)塊鏈的基本特征，意味著區(qū)塊鏈系統(tǒng)必然是分布式的，也就是說去中心化必定導(dǎo)致發(fā)生分區(qū)的可能，由此也意味著分區(qū)容錯性是實現(xiàn)去中心化的前提。

3.4.現(xiàn)有共識算法對CAP的平衡

在CAP理論中，分區(qū)被認為是分布式系統(tǒng)必然存在的，所以討論沒有分區(qū)情況的分布式系統(tǒng)是沒有意義的。區(qū)塊鏈作為典型的分布式系統(tǒng)，其不同的共識算法在滿足分區(qū)的前提下，對系統(tǒng)的一致性（Consistency）和可用性（Availability）做出了一定的平衡。

Tendermint： Tendermint是POS類型的共識算法，主要包括NewHeight -》 Propose -》Prevote -》 Precommit -》 Commit五個階段。其中Propose-》 Prevote -》 Precommit屬于共識階段，是算法的核心，被稱作一個Round。在進行區(qū)塊的提交確認時，一個區(qū)塊可能需要多個Round。在多個Round中，區(qū)塊的高度并不會增加，只是向系統(tǒng)提交空塊，并且一個區(qū)塊一旦被確認，是不可能被修改的。所以Tendermint理論上有可能被卡住，區(qū)塊高度永遠不會增加。 這意味著Tendermint在出現(xiàn)分區(qū)時，更加側(cè)重于一致性（Consistency）。

Casper FFG： Casper FFG是POS類型的共識算法。在Casper FFG的設(shè)計中， 優(yōu)先考慮一致性，因為它不允許在沒有絕大多數(shù)驗證者同意的情況下完成checkpoint，這樣區(qū)塊也就不會達到最終的確認狀態(tài)。

Algorand： Algorand是POS類型的共識算法。Algorand與Tendermint的設(shè)計中有類似的地方，當(dāng)出現(xiàn)一致性和可用性沖突時，系統(tǒng)會更傾向于產(chǎn)生空塊，不會產(chǎn)生真正意義的區(qū)塊。所以Algorand更優(yōu)先考慮一致性。

Dfinity： Dfinity是POS類型的共識算法。當(dāng)網(wǎng)絡(luò)出現(xiàn)分區(qū)時，它會自動使隨機信標(biāo)暫停，不允許網(wǎng)絡(luò)中的任何分區(qū)繼續(xù)。所以Dfinity更優(yōu)先考慮一致性。

POW：當(dāng)使用POW的網(wǎng)絡(luò)出現(xiàn)分區(qū)時，所有的分區(qū)都可以正常的進行出塊，等到網(wǎng)絡(luò)恢復(fù)，分區(qū)結(jié)束時，會遵循最長鏈原則，不同分區(qū)的鏈將會進行合并，最終成為一條鏈。因此POW優(yōu)先考慮可用性。

POC:POC的全稱是Proof of Credit ，是全球開源社區(qū)項目NULS，創(chuàng)新使用的共識算法。當(dāng)使用POC的網(wǎng)絡(luò)出現(xiàn)分區(qū)時，所有分區(qū)都可以正常進行出塊。等到網(wǎng)絡(luò)恢復(fù)時，與POW類似，將會遵循最長鏈原則，進行區(qū)塊鏈的合并。因此NULS創(chuàng)新使用的POC優(yōu)先考慮的是可用性。

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

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

4.結(jié)論

通過以上對一致性（Consistency）與安全性、可用性（Availability）與可擴展性、分區(qū)容錯性（Partition-tolerant）與去中心化的邏輯關(guān)系推導(dǎo)，我們可以得出以下結(jié)論：

· 一致性（Consistency）是安全性的必要條件

· 可用性（Availability）是可擴展性的必要條件

· 分區(qū)容錯性是去中心化的必要條件

通過CAP理論可以知道一致性、可用性、分區(qū)容錯性是不能同時滿足的，所以我們可以得出：在CAP理論限定的條件下，安全性、可擴展性、去中心化不能同時滿足，即是區(qū)塊鏈的不可能三角不可突破。