Vitalik發(fā)布了一篇名為一個(gè)99%容錯(cuò)共識(shí)的指南

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

1、一個(gè)新的算法？

Vitalik在其博客上發(fā)布了一篇名為《一個(gè)99%容錯(cuò)共識(shí)的指南》。一時(shí)間各大媒體紛紛發(fā)布消息稱“V神發(fā)布的新算法僅需1%節(jié)點(diǎn)不作惡”。區(qū)塊鏈?zhǔn)澜缡欠褚灰怪g進(jìn)入了一個(gè)新的篇章？答案可能令人有些沮喪：這并不是一個(gè)新研究出來的算法。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4、“99%容錯(cuò)共識(shí)算法”及對(duì)比分析

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

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

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

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

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

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

5、應(yīng)用及啟發(fā)

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

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

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

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

6. 總結(jié)

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

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