基于區(qū)塊鏈拜占庭容錯(cuò)共識(shí)的Libra共識(shí)算法介紹

Facebook 近日公布的 Libra 白皮書引起各界持續(xù)關(guān)注，其網(wǎng)站公開的技術(shù)文檔也被諸多專家審視。文檔提到，Libra 區(qū)塊鏈將使用基于拜占庭容錯(cuò)共識(shí)的「LibraBFT」共識(shí)算法，而 LibraBFT 則是「HotStuff」的一個(gè)變種。

Libra 區(qū)塊鏈所采用的 LibraBFT 共識(shí)協(xié)議的技術(shù)論文

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

順藤摸瓜，我們發(fā)現(xiàn)，HotStuff 算法論文由云計(jì)算公司 VMWare 的研究團(tuán)隊(duì)發(fā)表，其安全性及可用性已經(jīng)過完整的數(shù)學(xué)證明。論文作者有 5 人，分別為 Maofan Yin、Dahlia Malkhi、Michael K. Reite、Guy Golan Gueta、Ittai Abraham。

HotStuff 算法論文https://arxiv.org/pdf/1803.05069.pdf

其實(shí)「HotStuff」算法論文的第一作者尹茂帆（Ted Yin）是鏈聞的老朋友。今年僅僅 25 歲的尹茂帆本科畢業(yè)于上海交大，目前在美國(guó)康奈爾大學(xué)（Cornell）大學(xué)讀博士學(xué)位，當(dāng)前的主攻方向是分布式系統(tǒng)的基礎(chǔ)研究，導(dǎo)師是著名計(jì)算機(jī)科學(xué)家 Emin Gun Sirer，另一導(dǎo)師是 Robbert van Renesse。尹茂帆也是另一個(gè)市場(chǎng)頗為矚目的新項(xiàng)目 Ava Labs 的聯(lián)合創(chuàng)始人和首席系統(tǒng)架構(gòu)師。

在 Facebook 正式發(fā)布 Libra 白皮書之后，尹茂帆接受了鏈聞的專訪，他為我們?cè)斀饬?HotStuff 的奧妙。

首次進(jìn)入分布式共識(shí)算法領(lǐng)域的人，很容易被一大堆名詞繞暈。而深入鉆研，你會(huì)發(fā)現(xiàn)這些名詞背后有著各種各樣的命名故事。比如 DLS 算法就是三位作者的縮寫：Dwork、Lynch 和 Stockmeyer。而 PBFT 算法就是「實(shí)用拜占庭容錯(cuò)」的首字母縮寫（Practical Byzantine Fault Tolerance），BFT 自然就是「拜占庭容錯(cuò)」了（下文將統(tǒng)一使用 BFT）。那么，這個(gè)物種的新人 HotStuff 的名字到底怎么來的呢？

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

在接受鏈聞采訪時(shí)，尹茂帆靈機(jī)一動(dòng)，把這個(gè)詞的中文翻譯為尤物。所以本文標(biāo)題的尤物，可不是嘩眾取寵。尹茂帆說，尤物有兩層意思，一是絕世美女，一是奇珍異寶。HotStuff 翻譯成尤物，簡(jiǎn)直天造地設(shè)。

據(jù)介紹，HotStuff 已經(jīng)在一個(gè)具有 100 多個(gè)副本的網(wǎng)絡(luò)上進(jìn)行過部署，超過了 BFT-SMaRt 的吞吐量，同時(shí)保持著與之相當(dāng)?shù)难舆t，而在更為實(shí)際的測(cè)試中性能均超過后者。

和其他分布式系統(tǒng)的共識(shí)協(xié)議相比，HotStuff 到底有哪些優(yōu)點(diǎn)呢？以下是鏈聞?dòng)浾吆鸵?a target="_blank">問答：

鏈聞：關(guān)于分布式系統(tǒng)的共識(shí)協(xié)議，大致可分為兩類，一類是以比特幣為代表的區(qū)塊鏈算法（或者稱為中本聰共識(shí)），一類是經(jīng)典的 BFT 算法（如 DLS、PBFT）。兩者在應(yīng)用條件和性能方面，有哪些大的差異和優(yōu)劣？

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

中本聰共識(shí)的優(yōu)點(diǎn)是，無需提前知道共識(shí)的所有參與者，不要求精確的成員信息。因?yàn)楣沧R(shí)的一部分采用了 PoW （工作量證明），所以天生就對(duì)女巫攻擊具有一定免疫。而且，中本聰共識(shí)的算法十分簡(jiǎn)單，普通人稍具數(shù)學(xué)基礎(chǔ)，就可以理解。中本聰共識(shí)也容易擴(kuò)容，在 10 個(gè)結(jié)點(diǎn)和 1000 個(gè)結(jié)點(diǎn)上受到的性能損失較?。ㄒ环矫媸且?yàn)椴恍枰獜V播投票，另一方面是因?yàn)樗緛砭秃苈娨韵陆忉?。?/p>

中本聰共識(shí)的缺點(diǎn)也很明顯。因?yàn)?PoW 的難度和等待鏈長(zhǎng)度跟安全性有關(guān)，從根本上說性能很差，交易確認(rèn)延遲大也無法改變。現(xiàn)有的所有基于中本聰共識(shí)的「魔改」（換湯不換藥的擴(kuò)容）協(xié)議，其實(shí)只能增加吞吐量。而拋開延遲談吞吐量，意義不大。好比我可以開一個(gè)卡車運(yùn)一車硬盤來運(yùn)送數(shù)據(jù)，雖然是超高吞吐量，但也是超高延遲。

在安全性方面，和傳統(tǒng) BFT 共識(shí)相比，中本聰共識(shí)只提供概率的安全保證，而 BFT 則是 100% 安全。這里說的安全，或者稱為一致性，就是能否避免雙花。其實(shí)，比特幣出六個(gè)塊能發(fā)生雙花的概率并不像大家想的那么低，有高達(dá) 13% 的概率出現(xiàn)共識(shí)失敗 （即 BFT 中的 30% 節(jié)點(diǎn)的情況）。以此來看，如果要公平比較的話，中本聰共識(shí)的效率非常之低。（六個(gè)塊已經(jīng)耗時(shí)一個(gè)小時(shí)了。）

再來看經(jīng)典 BFT 共識(shí)，其前提或者說缺點(diǎn)是，需要知道所有參與者，要求 100% 精確的成員信息。另外，經(jīng)典 BFT 共識(shí)相對(duì)較難擴(kuò)容。在 HotStuff 前，大部分經(jīng)典 BFT 都需要所有結(jié)點(diǎn)廣播，這帶來了平方級(jí)別的復(fù)雜度（包括 Tendermint 論文里面描述的算法）。增加大量結(jié)點(diǎn)會(huì)導(dǎo)致網(wǎng)絡(luò)擁塞。而且，其中的 Leader 結(jié)點(diǎn)會(huì)承受整個(gè)網(wǎng)絡(luò)的負(fù)載（負(fù)載極其不均衡），導(dǎo)致難以擴(kuò)容到成千上萬個(gè)結(jié)點(diǎn)而沒有太大性能損失。

BFT 共識(shí)的優(yōu)點(diǎn)則在于，因?yàn)楣沧R(shí)沒有使用無意義的 PoW，所以，經(jīng)典 BFT 共識(shí)的協(xié)議速度跟網(wǎng)絡(luò)發(fā)送大量短消息的速度相關(guān)，沒有中本聰共識(shí)那種額外的能源消耗和等待時(shí)間。交易延遲非常小，如果不考慮網(wǎng)絡(luò)延遲，交易在數(shù)十至數(shù)百毫秒級(jí)別，如果考慮網(wǎng)絡(luò)延遲，就跟網(wǎng)絡(luò)延遲同數(shù)量級(jí)。

鏈聞：你們論文在開篇聲稱，HotStuff 基于一個(gè)新的框架，這個(gè)框架在經(jīng)典 BFT 基礎(chǔ)和區(qū)塊鏈之間搭建了一座橋梁。如何理解這句話？

尹茂帆：我們的論文名為《尤物協(xié)議：透過區(qū)塊鏈看拜占庭容錯(cuò)共識(shí)》（HotStuff： BFT Consensus in the Lens of Blockchain）。

之所以這么描述，是因?yàn)樗乃惴蚣埽梢哉Q生多個(gè)衍生算法）采用了樹 / 鏈?zhǔn)浇Y(jié)構(gòu)，十分類似區(qū)塊鏈。另外，和傳統(tǒng)區(qū)塊鏈類似，一個(gè)結(jié)點(diǎn)當(dāng)前也有被視作「主鏈」的一根鏈，投票只會(huì)投給當(dāng)前認(rèn)為主鏈上擴(kuò)展的新部分。和區(qū)塊鏈一樣，如果側(cè)鏈足夠「好」，那么它就會(huì)變成新的主鏈。在區(qū)塊鏈里面，這個(gè)是通過鏈長(zhǎng)度來判定的（長(zhǎng)者勝），而在 HotStuff 中，它通過最近一次成功獲得大部分投票的塊決定。

另一方面，HotStuff 又是傳統(tǒng) BFT 體系下的一員。用此算法框架可以很好地解釋 PBFT、DLS、Tendermint、Casper 等協(xié)議，達(dá)到了一定程度上的歸納和統(tǒng)一。另外，跟之前同類型算法最大區(qū)別也是最大貢獻(xiàn)的地方是——HotStuff 的核心換屆算法沒有特殊情況；不像 PBFT 那樣有「正?！沟膱?zhí)行流程以及「特殊」的換屆流程，HotStuff 統(tǒng)一了兩者，即沒有顯式的換屆特殊處理，也可以認(rèn)為是潛在地處處換屆。這使得編寫一個(gè)基于 HotStuff 的共識(shí)系統(tǒng)的基礎(chǔ)安全部分十分容易。對(duì)比 PBFT 的數(shù)千行換屆代碼，HotStuff 只需要幾十或百余行即可。

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

鏈聞：PBFT 算法可以在互聯(lián)網(wǎng)等異步環(huán)境中運(yùn)行，一些優(yōu)化也使它較以前的共識(shí)算法更快。但它也有一些問題，比如檢測(cè)不良主要節(jié)點(diǎn)和重新選擇新主要節(jié)點(diǎn)（view change）的過程非常低效。比如為了達(dá)成共識(shí)，PBFT 需要平方級(jí)別的消息交換，這意味著每臺(tái)計(jì)算機(jī)都必須與網(wǎng)絡(luò)中其他所有計(jì)算機(jī)進(jìn)行通信?？傊琍BFT 的擴(kuò)容性顯然不夠。HotStuff 對(duì)這些問題有哪些解決方案？

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

鏈聞：Facebook 的 Libra 白皮書提出，Libra 區(qū)塊鏈?zhǔn)菑摹霸S可型區(qū)塊鏈”起步的，未來目標(biāo)是成為非許可型網(wǎng)絡(luò)。由許可型轉(zhuǎn)向非許可型，目前有可行的技術(shù)路徑嗎？難點(diǎn)在于擴(kuò)容（從 100 個(gè)節(jié)點(diǎn)增加到成千上萬個(gè)節(jié)點(diǎn)）還是在于能否抗女巫攻擊？

尹茂帆：理論上來說，任何許可協(xié)議都可以轉(zhuǎn)化成非許可型協(xié)議。因?yàn)閭鹘y(tǒng)的共識(shí)協(xié)議（無論是 BFT 還是非 BFT），都可以通過共識(shí)本身來重新配置以增加 / 刪除結(jié)點(diǎn)。但是因?yàn)闈撛诘呐坠?，這種基于精確成員信息的協(xié)議，需要額外依賴一個(gè) PoS 或者 PoW 的進(jìn)入機(jī)制來開放系統(tǒng)。

HotStuff 共識(shí)的其他實(shí)施

除了 Facebook，其他一些區(qū)塊鏈項(xiàng)目也已經(jīng)決定使用 HotStuff 共識(shí)。其中一個(gè)是公鏈項(xiàng)目 Cypherium（cypherium.io）。有趣的是，Cypherium 項(xiàng)目聲稱可以實(shí)現(xiàn)非許可型的擴(kuò)展——如果這個(gè)嘗試成真，意味著這可以為 Facebook 提出的轉(zhuǎn)型路線圖，提供了一種解決方案。

Cypherium 首席執(zhí)行官 Sky Guo 接受鏈聞采訪中解釋了這里面的要點(diǎn)：

他說，與 Libra 未來計(jì)劃轉(zhuǎn)型為 PoS 不同的是，Cypherium 的主網(wǎng)將設(shè)計(jì)成 PoW+HotStuff 的混合共識(shí)機(jī)制。

通常來講，區(qū)塊鏈共識(shí)分為兩個(gè)過程：選舉領(lǐng)導(dǎo)者、打包與驗(yàn)證區(qū)塊。傳統(tǒng)項(xiàng)目里這兩個(gè)過程由同一種共識(shí)機(jī)制實(shí)現(xiàn)。而 Cypherium 在第一個(gè)過程中選用了 PoW 共識(shí)，用于選擇領(lǐng)導(dǎo)者節(jié)點(diǎn)。任何計(jì)算設(shè)備均可以通過挖礦的方式成為 Cypherium 的驗(yàn)證節(jié)點(diǎn)而不依賴于受信任的第三方。每當(dāng)有礦工成功挖到 PoW 時(shí)，驗(yàn)證委員會(huì)當(dāng)中時(shí)間最老的節(jié)點(diǎn)離開委員會(huì)，新的礦工成為驗(yàn)證委員，實(shí)現(xiàn)永久性的動(dòng)態(tài)輪換。而第二個(gè)過程，則選用了效率較高的 HotStuff 共識(shí)來打包和驗(yàn)證區(qū)塊。相應(yīng)地，Cypherium 設(shè)計(jì)了選舉鏈+交易鏈的雙鏈架構(gòu)。Sky Guo 聲稱，Cypherium 共識(shí) CypherBFT 可以做到完全去中心化、交易順時(shí)最終確認(rèn)、支持億級(jí)用戶的應(yīng)用場(chǎng)景。