【共識專欄】HotStuff共識

我們已經了解到分佈式系統一般通過狀態復制機[1]原理來實現一致性。其核心思想是系統中所有副本運行著相同的狀態機，只要所有副本都以相同的初識狀態開始，並基於相同的初識狀態執行一組相同順序的操作，那麼所有的狀態最終會收斂一致，即整個系統對外表現出一致性。而確定這一組相同順序的操作需要係統達成共識，進一步說即所有誠實節點對執行順序達成共識，這便是著名的拜占庭將軍[2]問題。

我們已經了解到分佈式系統一般通過狀態復制機[1]原理來實現一致性。其核心思想是系統中所有副本運行著相同的狀態機，只要所有副本都以相同的初識狀態開始，並基於相同的初識狀態執行一組相同順序的操作，那麼所有的狀態最終會收斂一致，即整個系統對外表現出一致性。而確定這一組相同順序的操作需要係統達成共識，進一步說即所有誠實節點對執行順序達成共識，這便是著名的拜占庭將軍[2]問題。

我們已經了解到分佈式系統一般通過狀態復制機[1]原理來實現一致性。其核心思想是系統中所有副本運行著相同的狀態機，只要所有副本都以相同的初識狀態開始，並基於相同的初識狀態執行一組相同順序的操作，那麼所有的狀態最終會收斂一致，即整個系統對外表現出一致性。而確定這一組相同順序的操作需要係統達成共識，進一步說即所有誠實節點對執行順序達成共識，這便是著名的拜占庭將軍[2]問題。

• 我們已經了解到分佈式系統一般通過狀態復制機[1]原理來實現一致性。其核心思想是系統中所有副本運行著相同的狀態機，只要所有副本都以相同的初識狀態開始，並基於相同的初識狀態執行一組相同順序的操作，那麼所有的狀態最終會收斂一致，即整個系統對外表現出一致性。而確定這一組相同順序的操作需要係統達成共識，進一步說即所有誠實節點對執行順序達成共識，這便是著名的拜占庭將軍[2]問題。

• 拜占庭類共識算法的理論安全保證，即n>3f，n為總的節點數量，f為惡意節點數量。一個拜占庭共識算法需要保證兩個性質：

安全性：所有誠實節點都認為某一時刻系統狀態為s

活性：所有誠實節點最終能確定s為系統狀態

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

以往，在分佈式系統的研究中，拜占庭類共識往往都伴隨著較高的通信複雜度，對網絡造成的消耗極大，系統規模不易擴大。如經典的PBFT算法，其達成共識需要經過三個階段，PRE-PREPARE階段主節點將請求消息發送給其他節點，其他節點對該消息驗證過後，各自發送prepare消息給其他節點，這個階段產生了n ^2條消息。為了保證跨視圖上的一致性，節點在收到至少quorum的prepare消息後再發送commit消息給其他節點。當節點最終收到至少quorum的commit消息時，再最終對該請求進行提交。而網絡異常節點超時觸發視圖切換時，則需要o(n^3)的通信複雜度

理解PBFT中每個階段的工作是HotStuff的基礎，PBFT中每個階段都目標都是為保證安全性和活性。

• 假設系統某時刻收到指令S'=S+1，主節點將這條指令S'=S+1發送給非主節點（這是pre-prepare消息），因為是拜占庭問題，誠實節點不確定自己收到的是否和其他誠實節點一致（主節點發送不一致消息），節點之間需要進行一次相互通信，確定自己和其他誠實節點收到的消息一致（確定主節點沒有發送不一致消息），每個節點發送prepare消息給其他所有節點，之後若收到quorum個數量的prepare消息，且通過驗證（驗證prepare中指向的指令與自己一致），達成第一輪共識（這是PREPARE階段）。此時，似乎可以確定了誠實節點收到的消息一致。但是這裡隱含條件是，達到共識的節點只是在自己的視角看到：我收到並驗證了quorum個一致的消息。但其他節點不一定和自己一樣收到quorum個prepare消息達成共識，如果此時進行提交，出現了網絡故障，提交了的節點知道已經達成共識，只要等網絡恢復，這條指令一定會被整個系統提交。但其他節點可能由於網絡故障還未達成共識，他們無法確定一直等下去能否提交。為了讓系統保持活性，進行視圖切換，此時新的主節點需要確定是在S'還是S的基礎上執行新的指令。如果沒有發現部分節點已經提交了該指令，且對另一條指令S''=S+2進行了共識並提交，系統對變量S的取值產生了不一致。因此，在此時提交有安全性的問題。

• 如果再進行一個階段的共識，在達成PREPARE共識之後，各自再發送一個commit消息，各自節點等待接受並驗證quorum個commit消息之後再提交。會遇到同樣的問題，達成COMMIT共識的節點提交了，他們知道如果網絡正常，系統遲早都會提交，但是其他未達成COMMIT共識的節點不確定最後能否提交。網絡發生故障後新視圖中的主節點如果沒有發現已經提交了的節點，依然會造成不一致。這裡的矛盾是我們為了活性需要切換視圖繼續共識；為了安全性還要確保新視圖開始共識前S的取值一致，已經提交了的指令在新視圖中也一定需要被提交。而在PBFT中採用視圖切換時向其他節點發送消息證明自己S的狀態的方法，即發送自己最新的S的一條pre-prepare消息和對應的quorum條prepare消息。視圖切換時，新主節點共識前就能判斷S'=S+1是否需要提交。

如果沒有任何一個節點就S'=S+1達成PREPARE階段共識，則不會繼續對S'=S+1進行提交。

如果存在一個節點對達成了S'=S+1達成了PREPARE階段共識，則不可能對一條衝突的指令S''=S+2達成共識並提交，

按照這種規則安全性和活性就得到了保證，而這種方法帶來的複雜度卻是o(n^3)。因此該算法依然不能夠運用在大規模的網絡當中。尹茂帆等人提出的HotStuff共識算法[4]具有線性視圖變更的特性，解決了經典的PBFT甚至BFT類共識的瓶頸，主節點的切換無需增加其他協議和代價，系統仍能對外工作表現一致性，使得共識流程通信複雜度降低至o(n)。

—— HotStuff 基本概念——

了解hotstuff算法需要介紹幾個與共識流程相關的概念：

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

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

—— HotStuff 共識流程——

正文

▲ Basic Hotstuff

正文

正文

Basic HotStuff是共識的基本過程。其中，視圖以單調遞增的方式不斷切換。每個視圖內都有一個唯一的主節點負責提案、收集和轉發消息並生成QC，整個過程包括4個階段：準備階段（PREPARE）、預提交階段（PRE-COMMIT）、提交階段（COMMIT）、決定階段（DECIDE），主節點提交（達成共識）某個分支，在PREPARE、PRE-COMMIT、COMMIT三個階段收集quorum個共識節點帶簽名的投票消息，利用門限簽名合成一個QC，然後廣播給其他節點。

HotStuff 結合門限簽名可以將之前互相廣播共識消息的方式，轉為由主節點處理、合併轉發，通信複雜度可以降低到o(n)，簡而言之就是HotStuff用門限簽名+兩輪通信達到了PBFT一輪通信的共識效果。

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

PREPARE階段：

主節點：1）根據收到的quorum條New-View消息，該消息中包含了發送方的狀態樹中高度最高的prepareQC，主節點在收到的prepareQC中計算出高度最高的QC，記為highQC ；

2）根據這個highQC的節點所指向的分支，打包區塊創建新的樹節點，其父節點為highQC指向的節點；

3）將生成的提案附帶在prepare消息中發送給其他從節點，且當前提案包含highQC。

從節點：1）收到該prepare消息之後，對prepare中的信息進行驗證，包括qc中籤名的合法性；是否當前視圖的提案；

2）prepare消息中的節點是否擴展自lockedQC的分支（即孩子節點）或者prepare消息中的highQC的視圖號大於lockedQC（前者為安全條件，後者為活性條件保證節點落後時及時同步）；

3）生成prepare-vote消息並附帶一個簽名發送給主節點。

PRE-COMMIT階段：

主節點收到quorum個當前提案的prepare-vote消息時，通過聚合quorum個部分簽名得到prepareQC；然後主節點廣播pre-commit消息附帶聚合得到的prepareQC。

從節點：其他節點收到pre-commit消息，驗證之後，發送pre-commit vote消息給主節點。

⚠️注意此時，在主節點發送的pre-commit中的prepareQC就表明了prepare消息中的提案消息，所有節點投票成功達成了共識，這一時刻與PBFT中PREPARE階段達成共識類似。

Commit階段：

主節點：與pre-commit階段類似。 1）主節點先收集quorum個pre-commit vote消息，然後聚合出這一階段的pre-commitQC，附帶在commit消息中發送給其他節點。 2）設置本地lockedQC為pre-commitQC。

從節點：收到commit消息時，消息驗證通過同樣更新本地的lockedQC為commit消息中的pre-commitQC，對其簽名並生成commit vote並發送給主節點

⚠️注意此時，主節點發送的commit消息附帶的pre-commitQC即與PBFT中的第二輪COMMIT階段共識類似，其中PBFT中該階段共識表明了節點對的第一階段達成共識這件事的共識，即確保了至少quorum個節點已經完成PREPARE階段，在發生視圖切換時，有足夠多的節點能夠證明對該提案達成了PREPARE共識，在新視圖中提案內容需要被提交。

DECIDE階段：

主節點：1）收集到quorum個commit vote消息時，聚合得到commitQC，並且附帶在decide消息中發送給其他節點；

2）當其他節點收到decide消息時，其中commitQC指向的提案中的交易就會被執行；

nextView interrupt階段：在共識中任何其他階段發生了超時事件，發送新視圖的new-view消息，都會直接開啟下一輪新的共識。

正文

▲ Chained HotStuff

正文

正文

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

Chained HotStuff的流程如圖：

從圖中可以看出，每個階段都會切換視圖，因此每個提案都有自己的視圖。節點對於不同的提案來說處在不同的視圖上，PREPARE階段的投票被當前視圖的主節點合成QC，並轉發給下一個視圖的主節點，即下一視圖在進行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提案產生將會附帶上一階段投票產生的QC。經過流水線簡化版本的HotStuff工作過程如下：

主節點：1）等待NEW-VIEW消息，發出自己的提案；

2）等待其他節點進行投票；

3）向下一個主節點發送NEW-VIEW消息。

從節點：1）等待主節點的提案消息；

▲ Event-driven HotStuff

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

• 3）向下一個主節點發出NEW-VIEW消息。

• 從Chained HotStuff到Event-driven HotStuff，實現原論文中將整個協議的安全性（safety）和活性（liveness）解耦開，活性成為單獨的pacemaker模塊。 pacemaker模塊保證了在全局穩定時間（GST）之後的活性。提供兩個功能：

選擇、校驗每個視圖的主節點。

Event-driven Hotstuff與其他版本原理還是核心的三階段共識，區別只是工程實現上的便利，具體可見論文偽代碼[4]

二級標題

二級標題

活性機制是共識能夠持續推進的關鍵。在原HotStuff論文中活性機制使用了一個全局一致的超時時間確定了視圖超時。在NoxBFT中，我們設計了更靈活的機制應對網絡環境的不穩定。

二級標題

二級標題

二級標題

交易緩存池

在區塊鏈的應用中，為避免交易丟失，我們設計了交易緩存池緩存客戶端交易。共識模塊主動拉取交易進行打包。交易池也可以減輕共識工作量，進行交易去重，我們通過交易內容hash標識交易，將已經執行的交易寫入布隆過濾器，防止雙花攻擊，提升共識算法的穩定性。

快速恢復機制

不穩定的網絡環境可能使共識節點丟失共識消息，導致節點落後。在HotStuff原論文中，作者將此部分具體實現留給了開發者。我們實現了工程可用的同步算法，讓落後共識節點恢復定序功能，分為兩步：

1）節點落後較多，直接向其他節點拉取區塊執行恢復到最新檢查點。

參考文獻

總結

總結

作者簡介

作者簡介

程泰宁

參考文獻

參考文獻

[1] Schneider F B . The state machine approach: A tutorial[J]. Springer New York, 1990.

[2] Lamport L ,  Shostak R ,  Pease M . The Byzantine Generals Problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3).

[3] Castro M, Liskov B. Practical Byzantine fault tolerance[C]. OSDI.1999, 99(1999): 173-186.

[4] Yin M ,  Malkhi D ,  Reiter M K , et al. HotStuff: BFT Consensus in the Lens of Blockchain[J].  2018.

[5] Shoup V . Practical Threshold Signatures[C]// International Conference on Theory & Application of Cryptographic Techniques. Springer-Verlag, 2000.