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

HotStuff的論文由云計算公司 VMWare 的研究團隊發(fā)表，第一作者尹茂帆，在美國康奈爾大學（Cornell）大學讀博士學位，當前的主攻方向是分布式系統(tǒng)的基礎研究，導師是著名計算機科學家 Emin Gun Sirer，另一導師是 Robbert van Renesse。

尹茂帆解釋說，取名為 HotStuff，是因為這個單詞在英文里有三重意思：一是性感的人，一是炙手可熱的好東西，一是某個動畫里的小惡魔的名字。

摘要

由于惡意攻擊和軟件錯誤會導致故障節(jié)點表現(xiàn)出拜占庭行為，拜占庭容錯的算法變得越來越重要，本文提出了一種用于部分同步模型的基于Leader的拜占庭容錯協(xié)議HotStuff：一旦網(wǎng)絡通信變得同步，HotStuff就能讓正確的Leader以實際的網(wǎng)絡延遲的速度驅(qū)動協(xié)議達成一致，通信的復雜性和副本數(shù)量呈線性關系。

引言

分布式系統(tǒng)一般是通過狀態(tài)復制機(State Machine Replication)原理實現(xiàn)一致性，核心思想是系統(tǒng)中所有副本運行著相同的狀態(tài)機，只要所有副本都已相同的初始狀態(tài)開始，并基于相同的初始狀態(tài)執(zhí)行一組相同順序的操作，那么所有的狀態(tài)最終都會收斂一致，即整個系統(tǒng)對外表現(xiàn)出一致性。而確定一組相同順序的操作需要系統(tǒng)達成共識，即所有誠實節(jié)點對執(zhí)行順序達成共識，這就是著名的拜占庭將軍問題。
拜占庭類共識算法的理論安全保證，即n>3f，n為總的節(jié)點數(shù)量，f為惡意節(jié)點數(shù)量。一個拜占庭共識算法需要保證兩個性質(zhì)：
Safety 所有誠實的節(jié)點都認為某一時刻系統(tǒng)狀態(tài)為s
Liveness 所有誠實節(jié)點最終能確定s為系統(tǒng)狀態(tài)

其中s是一個抽象的概念，可以理解為系統(tǒng)內(nèi)存在一個變量S，這個變量S的取值為系統(tǒng)狀態(tài)，系統(tǒng)內(nèi)節(jié)點接收一系列關于S的操作指令，某時刻（假設每個節(jié)點時鐘沒有誤差）就S的取值進行共識，所有誠實節(jié)點確定變量S=s則滿足安全性，所有誠實節(jié)點對變量S的取值必須做出決定且終止則滿足活性。

在這篇文章中，系統(tǒng)作為一個整體提供了一個復制服務，狀態(tài)是跨n個確定性鏡像副本的，BFT SMR協(xié)議用于確保非錯誤副本對客戶端發(fā)起的服務命令的執(zhí)行順序一致，盡管受到f的影響，但仍能夠確保n-f個誠實節(jié)點可以按照相同的方式運行命令，從而為每個命令產(chǎn)生相應的響應。通常在半同步網(wǎng)絡模型中，消息傳輸?shù)囊阎吔?在某個未知的全局穩(wěn)定時間(GST)后保持的。

可擴展性挑戰(zhàn)

PBFT包含了兩個主要的工作流
1.網(wǎng)絡環(huán)境良好情況下的正常工作模式（網(wǎng)絡節(jié)點都同步，并且Leader運行正常）
2.用于更換崩潰的Leader的view-change模式

工作流1包含三階段（pre-prepare，prepare，commit），
當Leader收到客戶端的交易，根據(jù)交易廣播pre-prepare消息，
收到pre-prepare消息的節(jié)點廣播prepare消息，
當節(jié)點收到2f個preparep消息，廣播commit消息，
當節(jié)點收到2f+1個commit消息后，處理交易。

當正常工作模式出現(xiàn)超時，共識發(fā)生停滯的時候，節(jié)點會更換到view-change模式，并將節(jié)點本地的view-number++，同時廣播view-change消息；
如果節(jié)點的正常工作模式?jīng)]有出現(xiàn)超時，但收到了f+1個view-change消息，也會切換到view-change模式，并將節(jié)點本地的view-number++，同時廣播view-change消息；
view-change模式規(guī)定新Leader為view-change消息的height mod 節(jié)點總數(shù)N，因此新的Leader的轉(zhuǎn)換過程是在節(jié)點集合中循環(huán)的。
當節(jié)點發(fā)現(xiàn)自己是新view的Leader，并收到2f+1個view-change消息，廣播new-view消息，收到的2f+1個view-change消息被組合起來作為new-view消息的proof；當節(jié)點接收到一個number>=自己當前view-number的new-view消息，更新自己的view-number到new-view的number，如果收到的小于就忽略。
節(jié)點進入view-change模式后，維護一個timeout計時器，每一次view-change工作模式的失敗都會是計時器的超時時間翻倍。

HotStuff圍繞著一個三相核心，允許一個新的領導者簡單地選擇它所知道的最高QC，引入了第二個階段，允許復制人在該階段投票后“改變他們的想法”，根本不需要領導者的證明。這減輕了上述復雜性，同時大大簡化了leader替換協(xié)議。最后，把所有階段都規(guī)范化之后，就可以很容易地將HotStuff流水線化，并頻繁地輪換領導者。

目前來說，區(qū)塊鏈中的BFT協(xié)議想Tendermint和Csaper能夠如此更迭Leader。但這些系統(tǒng)都建立在同步核心的基礎上，其中的提議是在預先確定的時間間隔內(nèi)提出的，需要適應一個P2P gossip network的傳播的最差情況時間，在這個過程中放棄了大多數(shù)可用的BFT SMR解決方案，因為響應要求一個沒有錯誤的Leader。

我們的貢獻

提出了第一個BFT SMR協(xié)議，稱為HotStuff，實現(xiàn)了兩個屬性
1.線性視圖變換：在GST之后，任何正確的Leader，一旦被指定，只發(fā)送O(n)個驗證器來驅(qū)動共識決策，包括Leader被替換的情況，因此在級聯(lián)Leader失敗的最差情況下，GST后達成共識的通信成本為O($n^2$)
2.樂觀響應：在GST之后，任何正確的Leader，一旦被指定，需要等到一個n-f個響應，來保證能夠生成一個提議做出決定，包含Leader被取代的情況。
HotStuff中一個新的Leader推動協(xié)議達成共識的成本不會超出現(xiàn)在的Leader，因此HotStuff支持頻繁迭代Leader，這在區(qū)塊鏈環(huán)境中可以確保鏈的質(zhì)量。
HotStuff通過為每個視圖添加另一個階段來實現(xiàn)這些屬性，以較小的延遲代價換取了協(xié)議的簡化，延遲在實際中通常小于?。我們希望這種增加的延遲比以前的協(xié)議通過放棄響應來實現(xiàn)view-change而產(chǎn)生的延遲要小得多。
HotStuff的安全性是依賴節(jié)點view的投票和提交規(guī)則來指定的，實現(xiàn)Pacemaker活性所需的機制被封裝在內(nèi)，和安全性相關的機制是完全分離的。

相關工作

拜占庭問題下的共識達成的解決方案，歸結為兩個解決方案：

1.增加隨機選舉領導節(jié)點
2.依賴部分同步的網(wǎng)絡，即在異步期間保持安全性

模型

我們考慮一個由n=3f+1副本組成的固定集合系統(tǒng)，索引為i ∈ [n] where [n] = {1, . . . , n}，拜占庭集合F ? [n] of up to f = |F |。
我們的模型采用部分同步模型，已知延遲界限?和位置的全局穩(wěn)定時間GST，在GST之后，兩個副本之間得到所有傳輸都在時間?內(nèi)達到。HotStuff協(xié)議將確保始終安全，并在GST之后的有限時間內(nèi)的進展。

知識儲備

門限簽名Threshold signatures

一個（k，n）門限簽名方案指由n個成員組成的簽名群體，所有成員共同擁有一個公共密鑰，每個成員擁有各自的私鑰。只要收集到k個成員的簽名，且生成一個完整的簽名，該簽名可以通過公鑰進行驗證。

證書Quorum Certificate，QC

主節(jié)點收到至少quorum個節(jié)點對用一個提案的投票消息（帶簽名）后，利用門限簽名將其合成一個QC，這個QC可以理解為門限簽名生成的完整簽名，表示對該次提案達成一次共識。

視圖View

視圖是共識的基本單元，一個視圖至多達成一次共識，并且單調(diào)遞增，每個視圖逐漸輪換推進共識。

共識狀態(tài)樹

每個共識區(qū)塊可以看做是一個樹節(jié)點，每個樹節(jié)點內(nèi)包含對應的提案內(nèi)容（前文的操作指令）和相對應的QC，每個樹節(jié)點包含一個父親樹節(jié)點的哈希，形成一棵樹狀結構，主節(jié)點基于本地最長的分支生成新的樹節(jié)點。落后節(jié)點根據(jù)其他節(jié)點的最長分支上的最新樹節(jié)點來同步中間缺失的樹節(jié)點。

復雜度衡量

這個復雜度指代驗證者復雜度，在這個共識協(xié)議中副本在GST之后達成共識決策所接收到的驗證者數(shù)量的總和。
在這個反復達成共識的協(xié)議中，每個決策都有一個單調(diào)遞增的計數(shù)器來表示。

prepareQC

對于某個prepare消息，Leader收集齊n-f個節(jié)點簽名所生成的證據(jù)（聚合簽名或者消息集合），可視為第1輪投票達成共識的證據(jù)。

lockedQC

對于某個commit消息，Leader收集齊n-f個節(jié)點簽名所生成的證據(jù)（聚合簽名或者消息集合），可視為第2輪投票達成共識的證據(jù)。

Basic HotStuff

HotStuff解決了狀態(tài)機復制(SMR)問題。SMR的核心是一種協(xié)議，用于確定客戶端不斷增長的命令請求日志，一組狀態(tài)機副本以一致的順序應用命令?？蛻舳讼蛩懈北景l(fā)送命令請求，并等待其中(f + 1)個副本的響應。在大多數(shù)情況下，我們在討論中省略了客戶端，并參考標準文獻中關于客戶端請求的編號和重復刪除的問題。

基本HotStuff解決方案在算法2中給出。Basic HotStuff是共識的基本過程。其中，視圖以單調(diào)遞增的方式不斷切換。每個視圖內(nèi)都有一個唯一的主節(jié)點負責提案、收集和轉(zhuǎn)發(fā)消息并生成QC，整個過程包括4個階段：準備階段（PREPARE）、預提交階段（PRE-COMMIT）、提交階段（COMMIT）、決定階段（DECIDE），主節(jié)點提交（達成共識）某個分支，在PREPARE、PRE-COMMIT、COMMIT三個階段收集quorum個共識節(jié)點帶簽名的投票消息，利用門限簽名合成一個QC，然后廣播給其他節(jié)點。
HotStuff 結合門限簽名可以將之前互相廣播共識消息的方式，轉(zhuǎn)為由主節(jié)點處理、合并轉(zhuǎn)發(fā)，通信復雜度可以降低到o(n)，簡而言之就是HotStuff用門限簽名+兩輪通信達到了PBFT一輪通信的共識效果。

對比PBFT算法，共識開啟于主節(jié)點將請求附帶在pre-prepare中發(fā)送給其他節(jié)點，主節(jié)點即履行完了該輪共識的職責，接下來和其他節(jié)點一樣。整個共識過程包括一個廣播提案階段（PRE-PREPARE階段），兩個共識階段（PREPARE階段、COMMIT階段）。

Prepare階段

主節(jié)點：
1 根據(jù)收到的quorum條new-view消息，該消息中包含了發(fā)送方的狀態(tài)樹中高度最高的prepareQC，主節(jié)點在收到的prepareQC中計算出高度最高的QC，記為highQC；
2 根據(jù)這個highQC的節(jié)點所指向的分支，打包區(qū)塊創(chuàng)建新的樹節(jié)點，其父節(jié)點為highQC指向的節(jié)點；
3 將生成的提案附帶在prepare消息中發(fā)送給其他從節(jié)點，且當前提案包含highQC.

從節(jié)點：
1 收到該prepare消息之后，對prepare中的信息進行驗證，包括qc中簽名的合法性；是否當前視圖的提案；
2 prepare消息中的節(jié)點是否擴展自lockedQC的分支（即孩子節(jié)點）或者prepare消息中的highQC的視圖號大于lockedQC（前者為安全條件，后者為活性條件保證節(jié)點落后時及時同步）；
3 生成prepare-vote消息并附帶一個簽名發(fā)送給主節(jié)點。

Pre-commit階段

主節(jié)點：收到quorum個當前提案的prepare-vote消息時，通過聚合quorum個部分簽名得到prepareQC；然后主節(jié)點廣播pre-commit消息附帶聚合得到的prepareQC。
從節(jié)點：其他節(jié)點收到pre-commit消息，驗證完成后發(fā)送pre-commit vote消息給主節(jié)點。
在主節(jié)點發(fā)送的pre-commit中的prepareQC就表明了prepare消息中的提案消息，所有節(jié)點投票成功達成了共識，這一時刻與PBFT中PREPARE階段達成共識類似。

Commit階段

主節(jié)點：
1 類似于Pre-commit階段，主節(jié)點收集到quorum個pre-commit vote消息，聚合出這一階段的pre-commit QC，附帶在commit消息中發(fā)送給其他節(jié)點
2 設置本地lockedQC為pre-commitQC
從節(jié)點：
收到commit消息時，消息驗證通過同樣更新本地的lockedQC為commit消息中的pre-commitQC，對其簽名并生成commit vote并發(fā)送給主節(jié)點。
注意此時，主節(jié)點發(fā)送的commit消息附帶的pre-commitQC即與PBFT中的第二輪COMMIT階段共識類似，其中PBFT中該階段共識表明了節(jié)點對的第一階段達成共識這件事的共識，即確保了至少quorum個節(jié)點已經(jīng)完成PREPARE階段，在發(fā)生視圖切換時，有足夠多的節(jié)點能夠證明對該提案達成了PREPARE共識，在新視圖中提案內(nèi)容需要被提交。

Decide階段

主節(jié)點：
1 收集到quorum個commit vote消息時，聚合得到commitQC，并且附帶在decide消息中發(fā)送給其他節(jié)點；
2 當其他節(jié)點收到decide消息時，其中commitQC指向的提案中的交易就會被執(zhí)行；
3 之后增加視圖號view-number，開啟下一輪共識，根據(jù)prepareQC構造New-View消息。
從節(jié)點：
驗證消息后執(zhí)行decide消息中commitQC指向的樹節(jié)點的交易。
next-View interrupt階段：在共識中任何其他階段發(fā)生了超時事件，發(fā)送新視圖的new-view消息，都會直接開啟下一輪新的共識。

注意，HotStuff中一筆交易從開始到提交進行了三輪共識，第三輪共識的加入，克服了經(jīng)典兩階段范式的共識算法擴展的瓶頸。PBFT中為了保證系統(tǒng)在遇到惡意節(jié)點時能繼續(xù)工作（活性），需要進行視圖切換，而新視圖中為了確定上一個視圖中的區(qū)塊是否達成共識，需要在view-change消息中附帶自己收集到的quorum個prepare消息和相對應的一個pre-prepare消息作為證明，然后每個節(jié)點廣播view-change消息請求視圖切換，此時廣播的消息復雜度o(n^{2)，消息的量級為o(n)，因此視圖切換的復雜度為o(n}3)。安全性和活性讓PBFT需要o(n^3)的通信復雜度，對于網(wǎng)絡的負載極大，限制了其向大規(guī)模網(wǎng)絡的擴展。而HotStuff中如果我們對某一區(qū)塊達成了兩輪共識，在更換主節(jié)點時便能確定，主節(jié)點只需要基于最新的兩輪共識節(jié)點產(chǎn)生新節(jié)點是安全的。換句話說，只需要根據(jù)區(qū)塊自身的狀態(tài)（經(jīng)過幾輪共識）就可以確定是否在新的視圖中基于該區(qū)塊打包塊新區(qū)塊，降低了在視圖切換時候的通信復雜度。

Chained HotStuff

可以發(fā)現(xiàn)在Basic HotStuff中的各個階段流程都高度的相似，HotStuff的作者便提出了Chained HotStuff來簡化Basic HotStuff的消息類型，并允許Basic HotStuff的各個階段以流水線方式進行處理交易。

從圖中可以看出，每個階段都會切換視圖，因此每個提案都有自己的視圖。節(jié)點對于不同的提案來說處在不同的視圖上，PREPARE階段的投票被當前視圖的主節(jié)點合成QC，并轉(zhuǎn)發(fā)給下一個視圖的主節(jié)點，即下一視圖在進行PREAPRE階段的同時，也在進行上一個視圖的PRE-COMMIT階段。每個階段具有類似的結構，視圖v+1的PREPARE階段可以看作是視圖v的PRE-COMMIT階段。視圖v+2的的PREPARE階段看作是視圖v+1的PRE-COMMIT階段和視圖v的COMMIT階段。v1中的cmd1將在視圖v1，v2，v3中分別進行PREPARE、PRE-COMMIT、COMMIT階段，在v4中就進行提交。cmd2以此類推。每個階段的cmd提案產(chǎn)生將會附帶上一階段投票產(chǎn)生的QC。經(jīng)過流水線簡化版本的Chained-HotStuff工作過程如下：

主節(jié)點：
1）等待new-view消息，發(fā)出自己的proposal；

2）等待其他節(jié)點進行投票；

3）向下一個主節(jié)點發(fā)送NEW-VIEW消息。

從節(jié)點：
1）等待主節(jié)點的提案消息；

2）檢查提案中的QC，更新本地highQC，lockedQC，發(fā)送投票；

3）向下一個主節(jié)點發(fā)出NEW-VIEW消息。

Dummy nodes
為了簡化樹結構，生成葉子節(jié)點來自通用的QC.node和未知節(jié)點到提案view的高度，需要保持view-number和節(jié)點高度能夠一致，如果在一個view中不能達成共識，就在這個view里添加一個dummy block。

One-Chain，Two-Chai，and Three-Chain
當節(jié)點$b^{?}$攜帶一個指向父節(jié)點的QC即$b^{?}$.justify.node = $b^{?}$.parent，我們可以說它形成了一個單鏈。用 b′′ =$b^{?}$.justify.node 表示表示節(jié)點 $b^{?}$形成一個雙鏈，如果除了形成一個單鏈，b′′.justify.node = b′′.parent。如果 b′′ 形成雙鏈，則它形成三鏈。查看鏈 b = b’.justify.node, b’ = b’‘.justify.node, b’’ = b?.justify.node，任何一個節(jié)點都可能出現(xiàn)祖先差距。這些情況類似于 Basic HotStuff 的領導者未能完成三個階段中的任何一個，并被 next view 打斷到下一個視圖。如果 $b^{?}$形成一個單鏈，則 b′′ 的準備階段已經(jīng)成功。因此，當一個副本為 $b^{?}$投票時，它應該記住 genericQC ← $b^{?}$.justify，我們注意到即使 One-Chain 不是直接的，更新 genericQC 也是安全的，只要它高于當前的 genericQC 即可。在第 6 節(jié)描述的實現(xiàn)代碼中，我們確實在這種情況下更新了 genericQC。
這么理解吧，就是一個區(qū)塊中的QC是對其直接父區(qū)塊的確認，稱之為1-chain；同理，一個區(qū)塊b后面沒有Dummy block的情況下，連續(xù)產(chǎn)生了k個區(qū)塊，那么稱這段區(qū)塊鏈分支是區(qū)塊b的k-chain。
如果b’對b形成了1-chain，那么b’相當于b的prepare階段達成（第一輪投票成功），節(jié)點會將本地的prepareQC更新。

每當一個新的區(qū)塊形成，節(jié)點都會檢查是否會形成1-chain，2-chian，3-chain.
1-chain: 有新的prepareQC形成，更新本地的prepareQC
2-chain: 有新的precommitQC形成，更新本地的lockedQC
3-chian: 有新的commitQC形成，有新的區(qū)塊分支進入commit狀態(tài)，執(zhí)行確認的區(qū)塊分支

實現(xiàn)

對于高效的狀態(tài)復制機系統(tǒng)的構建，HotStuff是很實用的協(xié)議。因為HotStuff簡單明里哦啊，我們可以很容易將Algorithm3轉(zhuǎn)變?yōu)槭录?qū)動機制的HotStuff。

如Algorithm 4所示，通過將事件驅(qū)動機制從主體中提取到一個名為 Pacemaker 的模塊中，進一步簡化和概括了代碼。 與下一個Leader在開始其統(tǒng)治之前總是在通用階段結束時等待通用QC不同，這個邏輯被委托給了Pacemaker。 一個穩(wěn)定的Leader可以跳過這一步，并在多個高度上簡化提案。 此外，我們放寬了 1 的直接父約束。保持最高的 genericQC 和鎖定的 QC ，同時仍然保留有效節(jié)點中的 QC 始終引用其祖先的要求。 正確性證明類似于 Chained HotStuff，我們也將其推遲到 [50] 的附錄中。

Data structures

每個副本u保持對主狀態(tài)變量的追蹤

它還保持一個常數(shù) b0，即所有正確副本都知道的同一創(chuàng)世節(jié)點。 為了引導，b0 包含自己的硬編碼 QC，block、bexec、bleaf 都初始化為 b0，qchigh 包含 b0 的 QC。

Pacemaker

Pacemaker是一種保證GST之后進展的機制，它通過兩種成分來實現(xiàn)這一點。
第一個是“同步”，將所有正確的副本和唯一的領導者帶入一個足夠長的時期內(nèi)的共同高度。文獻 [25, 20, 15] 中通常的同步機制是讓副本增加他們在更大高度上花費的 Δ 的數(shù)量，直到取得進展。確定性選舉領導者的一種常見方法是使用輪換領導者方案，其中所有正確的副本都保持預先定義的領導者計劃，并在領導者降級時輪換到下一個。
其次，Pacemaker 需要為領導者提供一種方法來選擇將由正確副本支持的提案。

如算法5所示，視圖改變后，在onReceiveNewView中，新的leader通過onNextSyncView收集replica發(fā)送的new-view消息，發(fā)現(xiàn)滿足onReceiveProposal中第二部分條件的最高QC（算法4第18行） ）。然而，在同一個視圖中，現(xiàn)任領導者會將新節(jié)點鏈接到它自己最后提出的葉子的末尾，在那里不需要新視圖消息?；谝恍┨囟ㄓ趹贸绦虻膯l(fā)式方法（例如，等到先前提議的節(jié)點獲??得 QC），當前領導者調(diào)用 onBeat 來提議一個攜帶要執(zhí)行的命令的新節(jié)點。值得注意的是，即使一個糟糕的 Pacemaker 任意調(diào)用 onPropose，或者反復選擇父級和 QC，并且針對任何調(diào)度延遲，始終可以保證安全。因此，僅由算法 4 保證的安全性與算法 5 的任何潛在實例化完全解耦。
Pacemaker實現(xiàn)如下幾部分功能
Leader檢查
收集NewView消息，對齊View并更新highQC

Two-phase HotStuff variant

為了展現(xiàn)HotStuff框架的靈活性，算法6展示了兩階段HotStuff。

只有有效更新步驟之后，雙鏈做出提交決定，單鏈鎖定。4.4節(jié)討論了兩階段之后會求實積極的響應，和Tendermin/Casper類似。好處是階段更少，而活躍度可以通過在 Pacemaker 中結合基于最大網(wǎng)絡延遲的等待來解決。 進一步討論見第 7.3 節(jié)。

One-Chain and Two-Chain BFT Protocols

在本節(jié)中，我們研究了四個 BFT 復制協(xié)議，這些協(xié)議跨越了拜占庭容錯的 40 年研究，將它們轉(zhuǎn)換為類似于 Chained HotStuff 的鏈式框架。 圖 3 提供了我們考慮的協(xié)議的提交規(guī)則的鳥瞰圖，包括 HotStuff。 簡而言之，DLS [25] 中的提交規(guī)則是單鏈，允許節(jié)點僅由其自己的領導者提交。 PBFT [20]、Tendermint [15, 16] 和 Casper [17] 中的提交規(guī)則幾乎相同，并且由兩條鏈組成。 它們在為活性引入的機制上有所不同，PBFT 具有二次大小的領導者“證明”（無線性），Tendermint 和 Casper 在每個領導者提議之前引入了強制性的 Δ 延遲（沒有樂觀響應）。 HotStuff 使用三鏈規(guī)則，并且具有無延遲的線性領導者協(xié)議。

DLS

單鏈的提交規(guī)則最簡單，該規(guī)則以第一個已知的異步拜占庭共識解決方案 Dwork、Lynch 和 Stockmeyer (DLS) 為模型，如圖 3(a) 所示。副本在其投票支持的最高節(jié)點上被鎖定在 DLS 中。不幸的是，如果在某個高度，一個領導者模棱兩可，并且兩個正確的副本被鎖定在那個高度的沖突提案上，這條規(guī)則很容易導致僵局。放棄任何一個鎖都是不安全的，除非有 2f + 1 表明他們沒有投票支持鎖定的值。事實上，在 DLS 中，只有每個高度的領導者自己才能通過單鏈提交規(guī)則做出提交決定。因此，如果它模棱兩可，只有領導者本身會受到傷害；如果 2f + 1 個副本沒有投票支持，或者存在沖突的提案（由領導者簽名），副本可以放棄鎖；在 DLS 中每個高度末端發(fā)生的解鎖協(xié)議被證明是相當復雜和昂貴的。再加上只有一個高度的領導者可以決定，在沒有發(fā)生故障且網(wǎng)絡及時的最佳情況下，DLS 需要 n 次領導者輪換，并且每個決策需要 O(n4) 次消息傳輸。雖然它在展示安全異步協(xié)議方面開辟了新天地，但 DLS 并非設計為實用的解決方案。

PBFT

兩階段投票，每個view有超時，view-change通過第一輪投票來完成，view-change消息中包含了prepared消息即達成了第一階段投票的消息。

Tendermit Casper

兩階段投票，第一個回合中的各個階段都有超時時間，round-change通過超時觸發(fā)（而不是投票），網(wǎng)絡節(jié)點保存自己已經(jīng)達成第一階段投票的消息（即polka消息）

HotStuff

三階段投票，每個view有超時，采用閾值簽名減小消息復雜度，liveness和safety解耦為兩個部分。

Grandpa

將出塊和共識確認分離，用來對已經(jīng)產(chǎn)生的區(qū)塊鏈進行投票確認，兩階段投票，但投票是針對區(qū)塊分支（對一個區(qū)塊投票也相當于對其所有父區(qū)塊投票），而不是特定區(qū)塊，各個節(jié)點可以針對不同高度的區(qū)塊投票。

總結

在BFT類的共識研究中，安全性的要求需要在視圖切換時，主節(jié)點確保自己是基于最新的系統(tǒng)狀態(tài)工作的，視圖切換與系統(tǒng)狀態(tài)的共識產(chǎn)生了o(n^3)的通信復雜度。而HotStuff通過增加一輪共識來解決，再結合門限簽名降低了通信復雜度。不僅如此，流水線的工作方式，讓算法變得足夠簡潔優(yōu)雅，這與raft的工作方式相似，采取了先上鏈再共識，通過三輪共識之后再執(zhí)行。這種鏈式的結構，不再區(qū)分每個階段通信的意義（PBFT中prepare、commit），靈活的主節(jié)點更換的機制，在節(jié)點更換時不需要通信來確定最新共識的狀態(tài)，對安全性與活性進行隔離，投票保證了安全性，pacemaker保證了其在網(wǎng)絡異步時的活性。文章來源地址http://www.zghlxwxcb.cn/news/detail-488131.html

到了這里，關于HotStuff: BFT Consensus in the Lens of Blockchain的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！