Facebook Libra 採用的 HotStuff 演算法，究竟是怎樣一種尤物

鏈聞專訪 HotStuff 論文第一作者尹茂帆。

Facebook 近日公布的 Libra 白皮書引起各界持續關注，其網站公開的技術文檔也被諸多專家審視。文檔提到，Libra 區塊鏈將使用基於拜占庭容錯共識的「LibraBFT」共識演算法，而 LibraBFT 則是「HotStuff」的一個變種。

Libra 區塊鏈所採用的 LibraBFT 共識協議的技術論文

這個名為 HotStuff 的演算法，究竟是怎樣一種「尤物」呢？

順藤摸瓜，我們發現，HotStuff 演算法論文由雲計算公司 VMWare 的研究團隊發表，其安全性及可用性已經過完整的數學證明。論文作者有 5 人，分別為 Maofan Yin、Dahlia Malkhi、Michael K. Reite、Guy Golan Gueta、Ittai Abraham。

HotStuff 演算法論文

https://arxiv.org/pdf/1803.05069.pdf

其實「HotStuff」演算法論文的第一作者尹茂帆（Ted Yin）是鏈聞的老朋友。今年僅僅 25 歲的尹茂帆本科畢業於上海交大，目前在美國康奈爾大學（Cornell）大學讀博士學位，當前的主攻方向是分散式系統的基礎研究，導師是著名計算機科學家 Emin Gun Sirer，另一導師是 Robbert van Renesse。

在 Facebook 正式發布 Libra 白皮書之後，尹茂帆接受了鏈聞的專訪，他為我們詳解了 HotStuff 的奧妙。

首次進入分散式共識演算法領域的人，很容易被一大堆名詞繞暈。而深入鑽研，你會發現這些名詞背後有著各種各樣的命名故事。比如 DLS 演算法就是三位作者的縮寫：Dwork、Lynch 和 Stockmeyer。而 PBFT 演算法就是「實用拜占庭容錯」的首字母縮寫（Practical Byzantine Fault Tolerance），BFT 自然就是「拜占庭容錯」了（下文將統一使用 BFT）。那麼，這個物種的新人 HotStuff 的名字到底怎麼來的呢？

尹茂帆解釋說，之所以取名為 HotStuff，是因為這個單詞在英文里有三重意思：一是性感的人，一是炙手可熱的好東西，一是某個動畫里的小惡魔的名字。大家都知道，以太坊下一代共識演算法 Casper 之名，也是來自一個動畫角色。所以，HotStuff 可以和它相映成趣了。

在接受鏈聞採訪時，尹茂帆靈機一動，把這個詞的中文翻譯為尤物。所以本文標題的尤物，可不是嘩眾取寵。尹茂帆說，尤物有兩層意思，一是絕世美女，一是奇珍異寶。HotStuff 翻譯成尤物，簡直天造地設。

據介紹，HotStuff 已經在一個具有 100 多個副本的網路上進行過部署，超過了 BFT-SMaRt 的吞吐量，同時保持著與之相當的延遲，而在更為實際的測試中性能均超過後者。

和其他分散式系統的共識協議相比，HotStuff 到底有哪些優點呢？以下是鏈聞記者和尹茂帆的問答：

鏈聞：關於分散式系統的共識協議，大致可分為兩類，一類是以比特幣為代表的區塊鏈演算法（或者稱為中本聰共識），一類是經典的 BFT 演算法（如 DLS、PBFT）。兩者在應用條件和性能方面，有哪些大的差異和優劣？

尹茂帆：兩者的區別大致可以分為五個方面：1）成員信息；2）性能，包括吞吐量，延遲等；3）抗女巫攻擊 (Sybil attack)——中本聰共識自帶抗女巫攻擊，而經典的 BFT 需要額外的 PoS 或者 PoW；4）可擴容性；5）安全性，即概率 vs 確定性。

中本聰共識的優點是，無需提前知道共識的所有參與者，不要求精確的成員信息。因為共識的一部分採用了 PoW （工作量證明），所以天生就對女巫攻擊具有一定免疫。而且，中本聰共識的演算法十分簡單，普通人稍具數學基礎，就可以理解。中本聰共識也容易擴容，在 10 個結點和 1000 個結點上受到的性能損失較小（一方面是因為不需要廣播投票，另一方面是因為它本來就很慢，見以下解釋。）

中本聰共識的缺點也很明顯。因為 PoW 的難度和等待鏈長度跟安全性有關，從根本上說性能很差，交易確認延遲大也無法改變。現有的所有基於中本聰共識的「魔改」（換湯不換藥的擴容）協議，其實只能增加吞吐量。而拋開延遲談吞吐量，意義不大。好比我可以開一個卡車運一車硬碟來運送數據，雖然是超高吞吐量，但也是超高延遲。

在安全性方面，和傳統 BFT 共識相比，中本聰共識只提供概率的安全保證，而 BFT 則是 100% 安全。這裡說的安全，或者稱為一致性，就是能否避免雙花。其實，比特幣出六個塊能發生雙花的概率並不像大家想的那麼低，有高達 13% 的概率出現共識失敗 (即 BFT 中的 30% 節點的情況)。以此來看，如果要公平比較的話，中本聰共識的效率非常之低。（六個塊已經耗時一個小時了。）

再來看經典 BFT 共識，其前提或者說缺點是，需要知道所有參與者，要求 100% 精確的成員信息。另外，經典 BFT 共識相對較難擴容。在 HotStuff 前，大部分經典 BFT 都需要所有結點廣播，這帶來了平方級別的複雜度（包括 Tendermint 論文裡面描述的演算法）。增加大量結點會導致網路擁塞。而且，其中的 Leader 結點會承受整個網路的負載（負載極其不均衡），導致難以擴容到成千上萬個結點而沒有太大性能損失。

BFT 共識的優點則在於，因為共識沒有使用無意義的 PoW，所以，經典 BFT 共識的協議速度跟網路發送大量短消息的速度相關，沒有中本聰共識那種額外的能源消耗和等待時間。交易延遲非常小，如果不考慮網路延遲，交易在數十至數百毫秒級別，如果考慮網路延遲，就跟網路延遲同數量級。

鏈聞：你們論文在開篇聲稱，HotStuff 基於一個新的框架，這個框架在經典 BFT 基礎和區塊鏈之間搭建了一座橋樑。如何理解這句話？

尹茂帆：我們的論文名為《尤物協議：透過區塊鏈看拜占庭容錯共識》（HotStuff: BFT Consensus in the Lens of Blockchain）。

之所以這麼描述，是因為它的演算法框架（可以誕生多個衍生演算法）採用了樹 / 鏈式結構，十分類似區塊鏈。另外，和傳統區塊鏈類似，一個結點當前也有被視作「主鏈」的一根鏈，投票只會投給當前認為主鏈上擴展的新部分。和區塊鏈一樣，如果側鏈足夠「好」，那麼它就會變成新的主鏈。在區塊鏈裡面，這個是通過鏈長度來判定的（長者勝），而在 HotStuff 中，它通過最近一次成功獲得大部分投票的塊決定。

另一方面，HotStuff 又是傳統 BFT 體系下的一員。用此演算法框架可以很好地解釋 PBFT、DLS、Tendermint、Casper 等協議，達到了一定程度上的歸納和統一。另外，跟之前同類型演算法最大區別也是最大貢獻的地方是——HotStuff 的核心換屆演算法沒有特殊情況；不像 PBFT 那樣有「正常」的執行流程以及「特殊」的換屆流程，HotStuff 統一了兩者，即沒有顯式的換屆特殊處理，也可以認為是潛在地處處換屆。這使得編寫一個基於 HotStuff 的共識系統的基礎安全部分十分容易。對比 PBFT 的數千行換屆代碼，HotStuff 只需要幾十或百餘行即可。

另一個它較同類型演算法更優異的特點是，它對工程師們十分友好。它將保證正確性和保證性能的邏輯從演算法層面上就進行了解耦合。一旦安全性保證的幾十行代碼完成，剩下的根據具體應用場景的優化（包括換屆機制，政策）都不會再觸及這部分，使得系統始終安全。

鏈聞：PBFT 演算法可以在互聯網等非同步環境中運行，一些優化也使它較以前的共識演算法更快。但它也有一些問題，比如檢測不良主要節點和重新選擇新主要節點（view change）的過程非常低效。比如為了達成共識，PBFT 需要平方級別的消息交換，這意味著每台計算機都必須與網路中其他所有計算機進行通信。總之，PBFT 的擴容性顯然不夠。HotStuff 對這些問題有哪些解決方案？

尹茂帆：首先，HotStuff 將換屆的代價首次從平方級降低至線性複雜度，這意味著它和 Paxos/Raft 這些在 IT 行業廣泛使用的非 BFT 協議一樣，擁有一致的複雜度。另外，雖然理論上 Tendermint 等協議可以通過結合數字簽名來降低到同樣複雜度，但是，這些協議本質上需要在塊與塊間等待最大的可能網路延遲，使得實際實現出來的系統變成了一個同步系統。而 HotStuff 思路跳出了原有的框架，提出了一個極簡的演算法體系，使得它可以很容易地打破這個傳統 BFT 的魔咒。經過測試，它可以在保證簡單代碼實現、低理論複雜度的情況下打敗現有的最快的傳統 BFT 實現，在商用系統方面具有無限潛力。

鏈聞：Facebook 的 Libra 白皮書提出，Libra 區塊鏈是從「許可型區塊鏈」起步的，未來目標是成為非許可型網路。由許可型轉向非許可型，目前有可行的技術路徑嗎？難點在於擴容（從 100 個節點增加到成千上萬個節點）還是在於能否抗女巫攻擊？

尹茂帆：理論上來說，任何許可協議都可以轉化成非許可型協議。因為傳統的共識協議（無論是 BFT 還是非 BFT），都可以通過共識本身來重新配置以增加 / 刪除結點。但是因為潛在的女巫攻擊，這種基於精確成員信息的協議，需要額外依賴一個 PoS 或者 PoW 的進入機制來開放系統。