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 可以做到完全去中心化、交易順時最終確認、支持億級用戶的應用場景。