Vitalik近期在其博客上發(fā)布了一篇名為《一個99%容錯共識的指南》讓許多人以為誕生了一個“黑科技”般的新共識算法。然而正如Vitalik自己所說，這一共識算法仍是經(jīng)典拜占庭將軍問題的算法。通過解析，我們可以看到共識算法的研究與創(chuàng)新仍需要遵循CAP等已經(jīng)被證明過的理論；在此基礎上把各類經(jīng)典分布式算法和加密算法改造應用于區(qū)塊鏈領域內(nèi)，將有可能獲得不錯的效果。

1、一個新的算法？

Vitalik在其博客上發(fā)布了一篇名為《一個99%容錯共識的指南》。一時間各大媒體紛紛發(fā)布消息稱“V神發(fā)布的新算法僅需1%節(jié)點不作惡”。區(qū)塊鏈世界是否一夜之間進入了一個新的篇章？答案可能令人有些沮喪：這并不是一個新研究出來的算法。

事實上，Vitalik在博客中已明確說明“Leslie Lamport在他1982年《拜占庭將軍問題》的著名論文里已包含了（增加容錯率）的算法，下面我嘗試來描述并用一個簡化形式來實現(xiàn)它”。他之后也在twitter上強調(diào)說明，“我并沒有發(fā)明出一個可以99%容錯的共識協(xié)議，而是Leslie Lamport發(fā)明的。我只是做了一個解釋并把這個算法適應在區(qū)塊鏈領域內(nèi)”。

這究竟是怎么一回事？為弄清楚來龍去脈，我們需要先來討論共識問題與分布式系統(tǒng)等理論問題。

2、分布式系統(tǒng)理論

實際上在區(qū)塊鏈誕生以前，計算機科學就對一致性問題已經(jīng)有了較多的研究，形成了經(jīng)過嚴格證明的分布式系統(tǒng)理論。其中較為經(jīng)典的理論包括FLP和CAP等。

FLP不可能性原理為：“在網(wǎng)絡可靠，存在節(jié)點失效（即便只有一個）的最小化異步模型系統(tǒng)中，不存在一個可以解決一致性問題的確定性算法?！凹匆恢滦詥栴}的理論下限是無解的。異步分布式系統(tǒng)中不存在一個任意場景下都能實現(xiàn)的共識算法。

CAP原理稱為CAP不可能三角，即一致性（Consistency）、可用性（Availablity）和分區(qū)容忍性（Partition）三者無法同時滿足，需要弱化某個特性來設計分布式系統(tǒng)。所以在FLP不可能性原理前提下，CAP原理為工程實踐提供了理論指導。

比CAP更一般的，分布式系統(tǒng)理論中還有對于網(wǎng)絡環(huán)境特性的定義：包括安全性（Safety）、活性（Liveness）、通訊不可靠性（Unreliable）。通過這些特性我們可以對CAP進行更為一般和直觀的定義：

由此可見，一般來說網(wǎng)絡分區(qū)容忍性P并不是一個可選項，而是必須要在算法中去考慮的因素。這也是為什么分布式系統(tǒng)一般都會在安全性（Safety）和可用性（Liveness）之間進行權衡。

其中，最后一個任意類型的錯誤是最為嚴重和棘手的。在這種任意類型錯誤都可能發(fā)生的場景中，服務器有可能產(chǎn)生原本不應該輸出的內(nèi)容，系統(tǒng)要做好最壞情況的準備。例如，當一個服務器向不同的服務器發(fā)送截然相反的消息時。這種類型錯誤，就是拜占庭錯誤，最早由Pease和Lamport等在上世紀80年代初通過拜占庭將軍問題進行描述和分析。

因此相較于分布式數(shù)據(jù)庫，區(qū)塊鏈的對于一致性問題的設計和實現(xiàn)要更為復雜，這也是為什么區(qū)塊鏈不只是一個簡單的分布式數(shù)據(jù)庫的原因之一。

3、 拜占庭將軍問題的經(jīng)典解法

關于BFT問題本身的描述，本文不再贅述。而Lamport等人在其經(jīng)典論文中除了提出拜占庭將軍問題外，也提供了兩種解決辦法。

第一種為“口頭消息”的OM（m）協(xié)議，即除了鏈路上可使用加密安全保障外，不允許使用任何的加密算法。該協(xié)議需要兩兩之間遞歸的傳遞大量消息，因此消息復雜度很高，為指數(shù)級，不太具有可實際操作性。但這一算法仍有其很高的價值，首先是為“實用拜占庭容錯”（Practical Byzantine Fault Tolerance）這一多項式級別復雜度協(xié)議的誕生做了一個鋪墊；另外，其1/3容錯節(jié)點數(shù)量也被證明為是該類算法的理論上限。

而第二種為“加密消息”的SM（m）協(xié)議。該算法與第一種不同之處在于使用簽名算法。每個節(jié)點都能產(chǎn)生一個不可偽造的簽名，并可由其他節(jié)點進行驗證。當收到消息后，節(jié)點會通過簽名來判斷及驗證該消息是否已收到過。最終不再收到消息后，消息共識結(jié)束。

該論文已證明該第二種算法可對任意多個節(jié)點實現(xiàn)容錯（當然網(wǎng)絡中至少還應包括2個正常節(jié)點，否則無意義）。具體過程可參考論文原文。

然而這一算法也存在其局限性：與許多拜占庭算法在一個異步或者半同步網(wǎng)絡環(huán)境的假設不同，它假設是在一個“同步”網(wǎng)絡內(nèi)進行，忽略網(wǎng)絡節(jié)點間通訊延遲；另外，簽名身份體系信息需要在網(wǎng)絡運行前確定，較難實現(xiàn)擴展。因此，根據(jù)CAP理論可以說，這種方式是在不考慮對網(wǎng)絡分區(qū)（P）等情況容忍的情況下，實現(xiàn)一個很高的一致性（C）與可用性（A）。

4、“99%容錯共識算法”及對比分析

作為對比，我們再繼續(xù)來看一下Vitalik所說的“由Lamport發(fā)明而自己進行了描述與簡化實現(xiàn)”的共識算法（以下簡稱“實現(xiàn)版本”；Lamport論文中的版本成為“原版本”）。

該實現(xiàn)版本仍然保留了原有的數(shù)字簽名體系，即每個節(jié)點都能產(chǎn)生一個不可偽造的簽名，并可由其他節(jié)點進行驗證。

與原版本不同的是，為了實現(xiàn)節(jié)點間的消息傳遞，實現(xiàn)版本的算法指定了消息的超時時間，即節(jié)點接收到一個消息后，對于消息的檢查除了查看簽名是否已收到過并且在集合當中以外，還要檢查收到消息的時間不應晚于簽名對應的時間節(jié)點。

在經(jīng)過確定好的時間（根據(jù)輪次計算得出）后，節(jié)點將停止監(jiān)聽，并按照某種確定好的規(guī)則來從檢查合法的消息中選擇一個值來作為共識的結(jié)果。

我們對比即可發(fā)現(xiàn)，兩種算法并沒有太本質(zhì)上的不同，其算法本質(zhì)都是需要基于簽名體系進行。而Vitalik實現(xiàn)版本的共識算法增加的延遲時間要求。這一設計實現(xiàn)在共識協(xié)議的具體編寫實現(xiàn)時會經(jīng)常遇到，可確定消息的傳播輪次、確保消息傳播可在一個指定的時間內(nèi)結(jié)束。

另外，實現(xiàn)版本還討論了觀察者（Observer）作為一個獨立角色在網(wǎng)絡中傳遞消息。觀察者作為網(wǎng)絡中一個被動查看的角色，可接收、檢查消息并直接轉(zhuǎn)發(fā)（不簽名）給其他節(jié)點。這需要對觀察者引入一個不一樣的延遲時間，以解決惡意節(jié)點故意給觀察者晚發(fā)消息使得正常消息超時的問題。

5、應用及啟發(fā)

正如上述討論的那樣，該類共識方法的主要問題在于對于網(wǎng)絡的同步要求較高、可擴展性較差。另外一個實現(xiàn)版本的缺點在于消息量也較大（需要進行N-1輪的N個節(jié)點向其他N-1個節(jié)點發(fā)消息的過程，即消息復雜度為），所以在實際場景中，該類共識方法較難直接應用。

為了更能適用于區(qū)塊鏈領域，Vitalik在其文章中也提到該方法可以與目前的其他共識算法（例如PBFT、PoS等）進行結(jié)合，例如可間隔一些特定時間運行該算法采用上述討論的觀察者模式隨機選擇出一些節(jié)點運行上述共識進行檢查。但如果在兩種共識算法相關前提假設都不能滿足的情況下，那么共識算法也將失效，即這種改進優(yōu)化并不能違背原有理論體系。

不過，我們?nèi)钥色@得不少啟發(fā)：充分挖掘分布式系統(tǒng)領域的經(jīng)典理論，并將其改造為適用于區(qū)塊鏈領域的共識算法可獲得出人意料的效果。例如，PBFT與中本聰類共識結(jié)合、Vitalik提出的BFT論文中的SM（m）算法與現(xiàn)有區(qū)塊鏈共識結(jié)合等等。

此外，嘗試應用安全領域內(nèi)的各種加密算法也可能會獲得不錯的效果。例如，ByzCoin等也在嘗試使用聚合簽名等加密算法來對共識機制進行優(yōu)化改造，可大幅度降低通訊復雜度。

6. 總結(jié)

共識算法的研究與創(chuàng)新仍需要遵循CAP等已經(jīng)被證明過的理論。

在這些理論基礎上，可將計算機分布式理論中各類經(jīng)典算法、安全領域內(nèi)的各種加密算法加以適應性改造，以應用于區(qū)塊鏈領域內(nèi)，將有可能獲得不錯的效果。