Facebook Libra 採用的 HotStuff 算法，究竟是怎樣一隻尤物？
為什麼選這篇文章？ Libra 技術白皮書提到選擇 Hotstuff 作為 LibraBFT 的基礎由於三項理由：（1）安全引數的簡單與模組化（2）易於執行（3）在早期試驗中有較佳效能。到底 Hotstuff 是什麼樣的 protocol ？聽聽 「HotStuff 算法論文」的第一作者尹茂帆（Ted Yin）怎麼解釋。
《本文由鏈聞授權 Libra 中文社群轉載，原文請見此》
鏈聞 Facebook 近日公佈的 Libra 白皮書引起各界持續關注，其網站公開的技術文檔也被諸多專家審視。文檔提到，Libra 區塊鏈將使用基於拜占庭容錯共識的「LibraBFT」共識算法，而 LibraBFT 則是「HotStuff」的一個變種。
這個名為 HotStuff 的算法，究竟是怎樣一種「尤物」呢？ 順藤摸瓜，我們發現，HotStuff 算法論文由雲計算公司 VMWare 的研究團隊發表，其安全性及可用性已經過完整的數學證明。論文作者有 5 人，分別為 Maofan Yin、Dahlia Malkhi、Michael K. Reiter、Guy Golan Gueta、Ittai Abraham。
其實「HotStuff」算法論文的第一作者尹茂帆（Ted Yin）是鏈聞的老朋友。今年僅僅 25 歲的尹茂帆本科畢業於上海交大，目前在美國康奈爾大學（Cornell）大學讀博士學位，當前的主攻方向是分布式系統的基礎研究，導師是著名計算機科學家 Emin Gun Sirer，另一導師是 Robbert van Renesse。尹茂帆也是另一個市場頗為矚目的新項目 Ava Labs 的聯合創始人和首席系統架構師。
在 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）。兩者在應用條件和性能方面，有哪些大的差異和優劣？
尹茂帆：兩者的區別大致可以分為五個方面：
- 成員信息
- 性能，包括吞吐量、延遲等
- 抗女巫攻擊 (Sybil attack) — — 中本聰共識自帶抗女巫攻擊，而經典的 BFT 需要額外的 PoS 或者 PoW
- 可擴容性
- 安全性，即概率 vs 確定性
中本聰共識的優點是，無需提前知道共識的所有參與者，不要求精確的成員信息。因為共識的一部分採用了 PoW （工作量證明），所以天生就對女巫攻擊具有一定免疫。而且，中本聰共識的算法十分簡單，普通人稍具數學基礎，就可以理解。中本聰共識也容易擴容，在 10 個結點和 1000 個結點上受到的性能損失較小（一方面是因為不需要廣播投票，另一方面是因為它本來就很慢，見以下解釋。）
中本聰共識的缺點也很明顯。因為 PoW 的難度和等待鏈長度跟安全性有關，從根本上說性能很差，交易確認延遲大也無法改變。現有的所有基於中本聰共識的「魔改」（換湯不換藥的擴容）協議，其實只能增加吞吐量。而拋開延遲談吞吐量，意義不大。好比我可以開一個卡車運一車硬盤來運送數據，雖然是超高吞吐量，但也是超高延遲。
在安全性方面，和傳統 BFT 共識相比，中本聰共識只提供概率的安全保證，而 BFT 則是 100% 安全。這裡說的安全，或者稱為一致性，就是能否避免雙花。其實，比特幣出六個塊能發生雙花的概率並不像大家想的那麼低，有高達 13% 的概率出現共識失敗 (即 BFT 中的 30% 節點的情況)。以此來看，如果要公平比較的話，中本聰共識的效率非常之低。（六個塊已經耗時一個小時了。）
再來看經典 BFT 共識，其前提或者說缺點是，需要知道所有參與者，要求 100% 精確的成員信息。另外，經典 BFT 共識相對較難擴容。在 HotStuff 前，大部分經典 BFT 都需要所有結點廣播，這帶來了平方級別的複雜度（包括 Tendermint 論文裡面描述的算法）。增加大量結點會導致網絡擁塞。而且，其中的 Leader 結點會承受整個網絡的負載（負載極其不均衡），導致難以擴容到成千上萬個結點而沒有太大性能損失。
BFT 共識的優點則在於，因為共識沒有使用無意義的 PoW，所以，經典 BFT 共識的協議速度跟網絡發送大量短消息的速度相關，沒有中本聰共識那種額外的能源消耗和等待時間。交易延遲非常小，如果不考慮網絡延遲，交易在數十至數百毫秒級別，如果考慮網絡延遲，就跟網絡延遲同數量級。
鏈聞：你們論文在開篇聲稱，HotStuff 基於一個新的框架，這個框架在經典 BFT 基礎和區塊鏈之間搭建了一座橋梁。如何理解這句話？
Ted Yin：我們的論文名為《尤物協議：透過區塊鏈看拜占庭容錯共識》（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 的進入機制來開放系統。
HotStuff 共識的其他實施
除了 Facebook，其他一些區塊鏈項目也已經決定使用 HotStuff 共識。其中一個是公鏈項目 Cypherium，該項目早在 Facebook 正式公佈 Libra 白皮書之前已經實現 HotStuff 算法。
Cypherium 首席執行官 Sky Guo 接受鏈聞採訪中解釋了這裡面的要點：
他說，與 Libra 未來計劃轉型為 PoS 不同的是，Cypherium 的主網將設計成 PoW+HotStuff 的混合共識機制。 通常來講，區塊鏈共識分為兩個過程：選舉領導者、打包與驗證區塊。
傳統項目里這兩個過程由同一種共識機制實現。而 Cypherium 在第一個過程中選用了 PoW 共識，用於選擇領導者節點。任何計算設備均可以通過挖礦的方式成為 Cypherium 的驗證節點而不依賴於受信任的第三方。
每當有礦工成功挖到 PoW 時，驗證委員會當中時間最老的節點離開委員會，新的礦工成為驗證委員，實現永久性的動態輪換。而第二個過程，則選用了效率較高的 HotStuff 共識來打包和驗證區塊。相應地，Cypherium 設計了選舉鏈+交易鏈的雙鏈架構。Sky Guo 聲稱，Cypherium 共識 CypherBFT 可以做到完全去中心化、交易順時最終確認、支持億級用戶的應用場景。
