2017-01-04 Jin Gao HoneyBadgerBFT：一個網絡環境無關的Byzantine容錯的分布式共識協議

作者介紹：

夏雨，麻省理工學院電子工程與計算作者機科學系博士一年級在讀，本科畢業于清華大學姚班。目前的研究興趣包括分布式系統與理論密碼學。

隨著密碼貨幣的流行，人們把越來越多的注意力放在大規模、Byzantine容錯的分布式協議上。這些協議可以用來執行一些“任務敏感”的應用，例如金融交易系統、能源維護系統、交通調度系統等。這樣的協議可以保證即使集群中的部分機器出現故障或者因遭受攻擊被敵手支配的情況下，剩下的大部分主機還可以使任務正常進行。在這樣的應用場景中，傳統的解決方案是使用弱同步(Weakly Synchronous)的分布式協議，例如PBFT。這類弱同步協議的活躍性(Liveness)仍然依賴于對于網絡延遲的假設，我們認為這樣的協議不適用于極端的網絡環境（在我們的論文中，我們給出了一個讓PBFT失敗的網絡環境）。

因此我們提出了HoneyBadgerBFT協議，這是據我們所知的第一個完全異步的共識協議，它不依賴于任何關于網絡環境的時間假設。

目前HoneyBadgerBFT僅支持封閉網絡，即在協議開始前，集群中的主機數量是已知的，并且在協議執行過程中沒有新的主機加入網絡。

HoneyBadgerBFT的核心部分由兩部分組成，分別是原子廣播(Atomic Broadcast)和異步公共子集協議(Asynchronous Common Subset)，這兩個協議的性質請參考論文的第4章 。

在協議開始以前，每個主機準備好各自的提案（即試圖寫入共識的數據），啟動N個原子廣播的實例（N為網絡中主機的個數）。在某一個原子廣播完成以后遂將該廣播對應的主機編號作為輸入啟動異步公共子集協議。異步公共子集協議在收集到足夠多的主機編號后終止，所有的非敵手主機得到一個關于子集的共識。根據這個子集這些主機將從原子廣播階段獲得的提案寫入共識。

我們的原子廣播取自Bracha在1987年提出的協議 [1]，如論文中圖2所示。我們在[1]的基礎之上進行了許多優化。例如，我們使用了消除碼來改善它的漸近通信復雜度 [2]。

我們使用的異步公共子集協議來自Ben-Or的構造[3]，如論文中圖4所示。直觀來講，它使用N個二進制共識協議實例并根據其結果來決定一個公共子集。在我們的工作中，我們使用了Mostefaoui等人的隨機二進制共識協議原型[4]。

這個隨機二進制共識協議中依賴于一個分布式公共隨機源，我們使用了一個簡單的閾值加密系統來設計這個隨機源。

在核心部分之外，我們還要考慮對手利用網絡延遲操縱提案選擇的可能性，完整的協議在論文中的圖1中描述。

HoneyBadgerBFT的容錯率為該模型下理論最優的 。

協議的期望運行時間為個異步時間單位（以公共隨機源為準）。N臺主機間的消息總和的通信復雜度為, 其中為各個主機的提案中最大的一個，為安全參數。如果我們每次投放大小的消息平攤到每個主機上，的額外開銷將被消除。通信復雜度將變為每臺主機。

我們在Amazon EC2服務上進行了大規模的實驗（104臺主機，容錯量為26，分布在EC2的8個區橫跨5個大洲），在論文中我們提供了消息大小(Batch Size)和通過量(Throughput)的折線圖（圖6），消息延時和通過量的折線圖（圖7），以及與PBFT的消息通過量的對比（圖8），當主機數目稍大的時候，PBFT處于劣勢。由于HoneybadgerBFT對網絡環境的要求很低，我們將其在Tor上也進行了實驗，最高達到了800Tx/sec的通過量。

image.pngimage.png

參考文獻

• [1] G. Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130–143, 1987.
• [2] C. Cachin and S. Tessaro. Asynchronous verifiable information dispersal. In Reliable Distributed Systems, 2005. SRDS 2005. 24th IEEE Symposium on, pages 191–201. IEEE, 2005.
• [3] M. Ben-Or, B. Kelmer, and T. Rabin. Asynchronous secure computations with optimal resilience. In Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, pages 183–192. ACM, 1994.
• [4] A. Mostefaoui, H. Moumen, and M. Raynal. Signature-free asynchronous byzantine consensus with t< n/3 and o (n 2) messages. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 2–9. ACM, 2014.

作者：大圣2017
鏈接：https://www.jianshu.com/p/425d7fde411a
來源：簡書

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

總結

以上是生活随笔為你收集整理的HoneyBadgerBFT：一个网络环境无关的Byzantine容错的分布式共识协议的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。