Vitalik的“99%容錯共識算法”解析區塊鏈
Vitalik近期在其博客上發布了一篇名為《一個99%容錯共識的指南》讓許多人以為誕生了一個“黑科技”般的新共識算法。
然而正如Vitalik自己所說，這一共識算法仍是經典拜占庭將軍問題的算法。通過解析，我們可以看到共識算法的研究與創新仍需要遵循CAP等已經被證明過的理論；在此基礎上把各類經典分布式算法和加密算法改造應用于區塊鏈領域內，將有可能獲得不錯的效果。
1、一個新的算法？
Vitalik在其博客上發布了一篇名為《一個99%容錯共識的指南》。一時間各大媒體紛紛發布消息稱“V神發布的新算法僅需1%節點不作惡”。區塊鏈世界是否一夜之間進入了一個新的篇章？答案可能令人有些沮喪：這并不是一個新研究出來的算法。
事實上，Vitalik在博客中已明確說明“Leslie Lamport在他1982年《拜占庭將軍問題》的著名論文里已包含了（增加容錯率）的算法，下面我嘗試來描述并用一個簡化形式來實現它”。他之后也在twitter上強調說明，“我并沒有發明出一個可以99%容錯的共識協議，而是Leslie Lamport發明的。我只是做了一個解釋并把這個算法適應在區塊鏈領域內”。
這究竟是怎么一回事？為弄清楚來龍去脈，我們需要先來討論共識問題與分布式系統等理論問題。
2、分布式系統理論
實際上在區塊鏈誕生以前，計算機科學就對一致性問題已經有了較多的研究，形成了經過嚴格證明的分布式系統理論。其中較為經典的理論包括FLP和CAP等。
FLP不可能性原理為：“在網絡可靠，存在節點失效（即便只有一個）的最小化異步模型系統中，不存在一個可以解決一致性問題的確定性算法。“即一致性問題的理論下限是無解的。異步分布式系統中不存在一個任意場景下都能實現的共識算法。
CAP原理稱為CAP不可能三角，即一致性（Consistency）、可用性（Availablity）和分區容忍性（Partition）三者無法同時滿足，需要弱化某個特性來設計分布式系統。所以在FLP不可能性原理前提下，CAP原理為工程實踐提供了理論指導。
比CAP更一般的，分布式系統理論中還有對于網絡環境特性的定義：包括安全性（Safety）、活性（Liveness）、通訊不可靠性（Unreliable）。通過這些特性我們可以對CAP進行更為一般和直觀的定義：
由此可見，一般來說網絡分區容忍性P并不是一個可選項，而是必須要在算法中去考慮的因素。這也是為什么分布式系統一般都會在安全性（Safety）和可用性(Liveness)之間進行權衡。
其中，最后一個任意類型的錯誤是最為嚴重和棘手的。在這種任意類型錯誤都可能發生的場景中，服務器有可能產生原本不應該輸出的內容，系統要做好最壞情況的準備。例如，當一個服務器向不同的服務器發送截然相反的消息時。這種類型錯誤，就是拜占庭錯誤，最早由Pease和Lamport等在上世紀80年代初通過拜占庭將軍問題進行描述和分析。
因此相較于分布式數據庫，區塊鏈的對于一致性問題的設計和實現要更為復雜，這也是為什么區塊鏈不只是一個簡單的分布式數據庫的原因之一。
3、 拜占庭將軍問題的經典解法
關于BFT問題本身的描述，本文不再贅述。而Lamport等人在其經典論文中除了提出拜占庭將軍問題外，也提供了兩種解決辦法。
第一種為“口頭消息”的OM(m)協議，即除了鏈路上可使用加密安全保障外，不允許使用任何的加密算法。該協議需要兩兩之間遞歸的傳遞大量消息，因此消息復雜度很高，為指數級，不太具有可實際操作性。但這一算法仍有其很高的價值，首先是為“實用拜占庭容錯”（Practical Byzantine Fault Tolerance）這一多項式級別復雜度協議的誕生做了一個鋪墊；另外，其1/3容錯節點數量也被證明為是該類算法的理論上限。
而第二種為“加密消息”的SM(m)協議。該算法與第一種不同之處在于使用簽名算法。每個節點都能產生一個不可偽造的簽名，并可由其他節點進行驗證。當收到消息后，節點會通過簽名來判斷及驗證該消息是否已收到過。最終不再收到消息后，消息共識結束。
該論文已證明該第二種算法可對任意多個節點實現容錯（當然網絡中至少還應包括2個正常節點，否則無意義）。具體過程可參考論文原文。
然而這一算法也存在其局限性：與許多拜占庭算法在一個異步或者半同步網絡環境的假設不同，它假設是在一個“同步”網絡內進行，忽略網絡節點間通訊延遲；另外，簽名身份體系信息需要在網絡運行前確定，較難實現擴展。因此，根據CAP理論可以說，這種方式是在不考慮對網絡分區（P）等情況容忍的情況下，實現一個很高的一致性（C）與可用性（A）。
4、“99%容錯共識算法”及對比分析
作為對比，我們再繼續來看一下Vitalik所說的“由Lamport發明而自己進行了描述與簡化實現”的共識算法（以下簡稱“實現版本”；Lamport論文中的版本成為“原版本”）。
該實現版本仍然保留了原有的數字簽名體系，即每個節點都能產生一個不可偽造的簽名，并可由其他節點進行驗證。
與原版本不同的是，為了實現節點間的消息傳遞，實現版本的算法指定了消息的超時時間，即節點接收到一個消息后，對于消息的檢查除了查看簽名是否已收到過并且在集合當中以外，還要檢查收到消息的時間不應晚于簽名對應的時間節點。
在經過確定好的時間（根據輪次計算得出）后，節點將停止監聽，并按照某種確定好的規則來從檢查合法的消息中選擇一個值來作為共識的結果。
我們對比即可發現，兩種算法并沒有太本質上的不同，其算法本質都是需要基于簽名體系進行。而Vitalik實現版本的共識算法增加的延遲時間要求。這一設計實現在共識協議的具體編寫實現時會經常遇到，可確定消息的傳播輪次、確保消息傳播可在一個指定的時間內結束。
另外，實現版本還討論了觀察者(Observer)作為一個獨立角色在網絡中傳遞消息。觀察者作為網絡中一個被動查看的角色，可接收、檢查消息并直接轉發（不簽名）給其他節點。這需要對觀察者引入一個不一樣的延遲時間，以解決惡意節點故意給觀察者晚發消息使得正常消息超時的問題。
5、應用及啟發
正如上述討論的那樣，該類共識方法的主要問題在于對于網絡的同步要求較高、可擴展性較差。另外一個實現版本的缺點在于消息量也較大（需要進行N-1輪的N個節點向其他N-1個節點發消息的過程，即消息復雜度為），所以在實際場景中，該類共識方法較難直接應用。
為了更能適用于區塊鏈領域，Vitalik在其文章中也提到該方法可以與目前的其他共識算法（例如PBFT、PoS等）進行結合，例如可間隔一些特定時間運行該算法采用上述討論的觀察者模式隨機選擇出一些節點運行上述共識進行檢查。但如果在兩種共識算法相關前提假設都不能滿足的情況下，那么共識算法也將失效，即這種改進優化并不能違背原有理論體系。
不過，我們仍可獲得不少啟發：充分挖掘分布式系統領域的經典理論，并將其改造為適用于區塊鏈領域的共識算法可獲得出人意料的效果。例如，PBFT與中本聰類共識結合、Vitalik提出的BFT論文中的SM(m)算法與現有區塊鏈共識結合等等。
此外，嘗試應用安全領域內的各種加密算法也可能會獲得不錯的效果。例如，ByzCoin等也在嘗試使用聚合簽名等加密算法來對共識機制進行優化改造，可大幅度降低通訊復雜度。
6. 總結
共識算法的研究與創新仍需要遵循CAP等已經被證明過的理論。
在這些理論基礎上，可將計算機分布式理論中各類經典算法、安全領域內的各種加密算法加以適應性改造，以應用于區塊鏈領域內，將有可能獲得不錯的效果。
1.TMT觀察網遵循行業規范，任何轉載的稿件都會明確標注作者和來源；
2.TMT觀察網的原創文章，請轉載時務必注明文章作者和"來源：TMT觀察網"，不尊重原創的行為TMT觀察網或將追究責任；
3.作者投稿可能會經TMT觀察網編輯修改或補充。
