背景
狀態機復制 (State machine Replication, SMR)是人們為了解決分布式系統同步問題提出的一種理論框架。為了讓一個系統擁有較強的容錯能力，人們通常會部署多個完全相同的副本節點，任意一個節點的崩潰都不會影響整個系統的正常工作。在工程上，這些副本節點通常使用狀態機復制理論進行同步。
狀態機復制的核心思想是在所有副本上面運行一套相同的狀態機，只要所有副本都有相同的初始狀態，并且對于初始狀態賦予相同的一組操作，那么所有副本的最終狀態一定是相同的。
如何確定這一組操作的順序，就需要系統中所有未出錯的節點，對于某一個待提交操作序列達成共識，這就類似于著名的拜占庭將軍問題中，軍官們面臨的困境。在拜占庭問題的諸多解決方案中，都會保證個節點中，只要有個未出錯的副本，這些未出錯的副本就可以不受其他出錯（甚至惡意）的副本影響而達成共識。
HotStuff是尹茂帆等人提出的分布性一致性協議，在該算法中，最多出錯節點個數為。該算法有兩個優點，第一個優點是，相比于之前的算法，HotStuff是基于leader節點的，擁有線性復雜度，可以極大地降低節點出錯時，系統的共識消耗。同時，更替leader的低復雜度，鼓勵網絡頻繁更迭leader節點，對于區塊鏈等領域非常有用。第二個優點是該模型隔離了安全性與活躍性，安全性通過節點投票保證，而活躍性則通過 Pacemaker 保證。
學習HotStuff除了閱讀本文，還可以閱讀原論文 《HotStuff : BFT Consensus in the Lens of Blockchain》 ，或是原論文的中文翻譯。Facebook的Libra數字貨幣也使用的該算法的變種 LibraBFT 。
算法
原論文提出了HotStuff的三種實現形式，分別為簡易的HotStuff算法(Basic HotStuff)，鏈狀HotStuff算法(Chained HotStuff)和事件驅動的HotStuff算法(Event-driven HotStuff)。工程上，人們通常使用Event-driven HotStuff算法，但是如果直接去閱讀Event-driven HotStuff算法的源代碼會不知所云。
Event-driven HotStuff算法之所以比較難以理解，是因為它——
- 使用了Basic HotStuff算法的共識邏輯，特別的，包括leader如何與replica交互形成共識；
- 運用了Chained HotStuff提出的流水線優化思想，特別的，如何使用流水線并行優化原算法中相似的階段；
- 最后Event-driven HotStuff是Chained HotStuff事件驅動形式，特別的，將原始實現中輪詢產生的驅動改為由leader節點發出的事件驅動。
一方面，從論文的結構上來看，先介紹了前兩者，最后才在Implementation章節介紹了Event-driven HotStuff。但另一方面，Event-driven HotStuff又是三者中代碼最簡單的，也是三者中唯一一個可以在網上找到 大量源碼 進行對照的實現。因此直接上手閱讀源碼，在遇到困難時再去查閱簡單版本的實現也是一個很好地做法（事實上論文作者也推薦直接閱讀Event-driven HotStuff）。
簡單HotStuff算法
如果本節下面的內容理解上有困難可以參考原文對應章節。
視圖
狀態機復制中單次狀態轉移在HotStuff中以視圖(View)的形式出現，leader節點收集網絡中其他節點的信息，發送提案并取得共識的整個過程可以看做是一個視圖，視圖實際上可以類比于狀態機的一次轉移，其中包含了這次轉移需要執行的用戶命令。而整個分布式系統，正是通過一次又一次的視圖變換(View-Change)，得以逐輪推進運作。
分支
直觀地看，HotStuff中，每一個副本節點都會在自己的內存中維護一個待提交指令的樹狀結構。每個樹葉子節點都包含了一個待提交的指令，樹節點到根節點組成了一個分支。未提交的分支之間互相是競爭關系，一輪中只會有一個分支被節點所共識。
系統中存在一個唯一的leader被其他所有節點所公認，這個leader會嘗試將包含“待執行指令”的提議附加到一個已經被個副本投票支持的分支。并嘗試就新的分支與其他副本達成共識，共識成功后，整個系統所有節點都會提交并執行這些新的附加操作指令。
【值得注意的是HotStuff并不關心leader的選取過程，因此在后續算法中，我們需要默認leader已經由其他模塊指定。】
仲裁證書
HotStuff中的投票使用密碼學中的仲裁證書(Quorum Certificate, QC)，每一個視圖都會關聯一個仲裁證書，仲裁證書表明該視圖是否獲得了足夠多副本的認可。仲裁證書本質是副本節點通過自己的私鑰簽名的一種憑證。
如果一個副本節點認同某一個分支，它會使用自己的私鑰對該分支簽名，創建一個部分證書發送給leader。leader收集到個部分證書，可以合成一個仲裁證書，一個擁有仲裁證書的視圖意味著獲得了多數節點的投票支持。
視圖的投票總共分為三個步驟，準備階段prepare, 預提交階段pre-commit，提交階段commit。每一次投票都會合成一個仲裁證書，不同階段的證書從含義上稍微有些區別，在后續章節的閱讀時需要注意。
算法
下面是HotStuff的偽代碼，其中算法1是重要函數的偽代碼，涉及到到消息創建、投票創建、葉節點創建、仲裁證書創建、消息驗證、仲裁證書驗證、節點安全性判斷這些功能。算法2則是HotStuff的運行流程，在每一個階段，領導節點leader和所有副本replica（包括leader)都會等待特定類型的消息，并進行處理。下面，我會依次講解每一個階段究竟做了什么事情。
簡單HotStuff涉及函數
簡單HotStuff算法流程
prepare階段
在視圖編號增加時，所有節點都會發送New-View類別的消息給leader節點，消息中捎帶當前節點的prepareQC值（這里偽代碼沒寫），leader節點在接收到個New-View消息即可以默認已經有足夠多的副本等待接收新的提案。
prepareQC是一個仲裁證書，記錄了一個最后獲得了個節點投票的已提交分支，leader節點從所有New-View消息捎帶的仲裁證書中，選擇了一個擁有視圖編號最大的仲裁證書highQC，基于highQC對應的節點，創建葉節點拓展待提交的指令curProposal，這樣對于leader來說是最安全的。
最后leader節點會將curProposal、highQC封裝到prepare類型的消息中發送給副本節點，而副本節點對于接收到的prepare類型消息，進行安全性檢測safeNode。
從算法1中，我們可以看到，安全性判定分為兩個規則，安全性規則和活躍性規則。安全性規則檢測消息對應的節點是否是仲裁證書的直接子節點，如果是的話，說明副本節點的待提交節點和leader的待提交節點都是同步，中間沒有任何步驟缺失。活躍性規則則檢測自身的lockedQC的視圖編號是否小于仲裁證書的的視圖編號，如果小于的話，就說明自己被卡在了一個其他節點早已達成共識的視圖，因此可以忽略自身的lockedQC，直接嘗試與leader重新同步。
pre-commit預提交階段
當leader節點收到個為當前提案curProposal投票時，將他們合并為prepareQC，此時的prepareQC已經獲得了這個副本的投票。而對于副本節點，prepareQC則被賦值為prepare階段中leader節點的highQC，即最近已提交分支。
commit提交階段
commit階段類似于pre-commit階段。當leader接收到個pre-commit投票時，它將它們組合成一個precommitQC，并在commit類型消息中廣播它；副本用commit投票來響應它。重要的是，此時通過將副本的lockedQC設置為precommitQC（算法2的第25行），副本將被鎖定在precommitQC上。這對于保護提案的安全至關重要，以防提案成為一項協商一致的決定。
decide決定階段
當leader節點收到個commit的選票時，它將它們合并成一個commitQC。一旦leader節點獲得了commitQC，它就會以decide消息的形式將其發送給所有其他副本。在接收到decide消息時，副本將commitQC中包含的提案視圖視為已提交的決策，并在已提交的分支中執行命令。副本將增加viewNumber并啟動下一個視圖。
下一個視圖(nextView)中斷
在所有階段中，副本都會在viewNumber視圖處等待由函數確定的超時時間段。如果中斷等待，副本也會增加viewNumber并開始下一個視圖。
理解
正如代碼中藍色部分所強調的，系統的replica在每一階段都會維護一個量：
- prepareQC，表示該仲裁證書曾經獲得過一次majority投票
- lockedQC，是一個用于保證安全性的中間量
- commitQC，是個表示決策已經成了的憑證，不論之后發生什么樣的問題（網絡延遲、節點崩潰），只要有個正確節點，這個決定都是會被繼續尊重
為什么上述算法是安全的，核心就是證明下面的命題：
如果和是沖突的節點，那么他們不能夠同時被某個正確的副本所提交(commit)。
該命題的證明在文末附錄1，如果想要搞清楚lockedQC具體的含義，可以嘗試閱讀一下證明。 接著證明上述算法的活躍性，活躍性的核心是證明下面的命題：
我們首先定義全局穩定時間GST之后，存在一個有界的持續時間，滿足如果所有副本在期間仍然在視圖中，且視圖的leader節點正常運行，那么決定(decision)可以到達。
該命題的證明在文末附錄2.
鏈狀HotStuff算法
如果本節對應的內容理解有難度，可以參考 原文對應章節
。 在Basic HotStuff中，不難發現每個階段都是極其同構且獨立的，因此可以進行流水線優化。
圖1 Chained HotStuff是Basic HotStuff的流水線版本，QC可以同時處于多個階段。 對于節點b，單箭頭表示b.parent字段，雙箭頭表示b.justify.node。
更具體地說，在Chained HotStuff協議中，prepare階段的副本的投票由leader節點加以收集，并且儲存在狀態變量genericQC里。接下來，genericQC被轉發給下一個視圖的leader，實質上是將下一階段的職責（這曾經由pre-commit階段負責的）委托給下一個leader節點。然而，下一位leader實際上并不單獨進行pre-commit階段，而是啟動一個新的prepare階段，添加自己的提議。視圖的prepare階段同時充當視圖的pre-commit階段。視圖的prepare階段同時充當視圖的pre-commit階段和視圖
的commit階段。 在實際的實現中，還有一些細節，比如說，當一個leader沒有成功獲得足夠的仲裁證書，那么就可能出現一個節點的justify的視圖編號并不連續，如圖2所示，這種情況需要通過添加啞結點補齊。
圖2 v8的父節點沒有成功獲得仲裁證書
我們按照節點的依次向上訪問，可以獲得流水線中各個階段的節點。令,,
。
- 如果，說明的prepare階段成功完成，當副本投票給時，還需要執行。需要注意的是，即使，執行上述賦值也是安全的，我們在下一節Event-driven HotStuff中會使用后者。
- 如果，說明的pre-commit階段成功完成，需要同步更新。
- 如果，說明的commit階段完成，就變成一個已提交的決策。
下面是Chained HotStuff的偽代碼，其中略去了很多特殊情況的判斷。
事件驅動的HotStuff
從Chained HotStuff到Event-driven HotStuff也并不困難。最終偽代碼涉及了如下的數據結構——
- 將節點映射到投票
- 最近投票節點的高度
- 被鎖定的節點（和lockedQC相似）
- 最后執行的節點
- 由Pacemaker維護的最高的已知QC（與genericQC相似）
- 由Pacemaker維護的葉節點
下面兩個代碼共同組成了一個工程上實現高效的Event-driven HotStuff算法，他們分別描述了安全性相關模塊和活躍性相關模塊。和Chained HotStuff源碼進行對比，不難理解其中各個函數的功能，同時，讀者也可以結合 網絡上公開的實現
進行理解。
上述的HotStuff是三階段的，而論文中還介紹了一個兩階段的HotStuff變種算法，其優勢是更少的階段，更快的效率，而劣勢則是樂觀響應性的損失。
附錄1. 證明HotStuff安全性
證明： 如果和是沖突的節點，那么他們不能夠同時被某個正確的副本所提交(commit) .
先證明一個特殊情況，假設和的高度相同，上述命題不成立。這其實是很顯然的，畢竟副本的提交需要多數節點的投票，而每個副本每個階段只會投一個提案，不可能出現兩個同樣深度樹節點得票數同時過半的情況。
w和b高度不同的情況
假設和高度不同，不妨設，，是高度 大于 且與 沖突 的， 高度最小 的那個 合法的 prepareQC仲裁證書。 即
和都是合法的commitQC仲裁證書，是一個合法的prepareQC證書。算法29行說明一個commitQC是由個lockedQC組成，而算法13行則說明一個prepareQC需要個副本同時通過safeNode檢驗。 而一個commitQC需要由個lockedQC組成，和一個prepareQC需要的次safeNode檢驗，一定存在一個公有的，在視圖的時候，會設置lockedQC為precommitQC（），當嘗試檢驗safeNode謂詞時，就會發現既不滿足“extends from”，也不滿足“”。這意味著
甚至根本無法生成，與假設矛盾。 反證法的結論就是不可能存在兩個沖突的commitQC。
附錄2. 活躍性證明
我們首先定義全局穩定時間GST之后，存在一個有界的持續時間，滿足如果所有副本在期間仍然在視圖中，且視圖的leader節點正常運行，那么決定(decision)可以到達。 引理 如果一個正常運行的副本已經鎖定了，且鎖定在了，那么至少個副本投票了與匹配的。 引理證明 如果一些副本鎖定了，那么在prepare階段一定獲得了個投票(算法2的第10行)，由于，所以其中至少個是正常運行的副本。 活躍性證明 從一個新的視圖開始，leader節點收集個newView消息，并計算出他們的highQC，最后廣播prepare消息。假設在所有副本中（包括leader本身），最高的鎖定QC是，通過引理， 我們知道了，至少有個正確的副本曾經向一個匹配的投票，并且該值已經被附在NewView消息中，傳送給leader節點。在這些New-View消息中，至少有一個會被leader接受，并賦值到highQC中。基于假設條件，所有正確的副本在該視圖中處于同步狀態(synchronized)，且leader節點是無缺陷的。因此，所有正確的副本都會在prepare階段投票，由于在函數里面，算法1第27行的條件被滿足了（即使節點的消息和副本的沖突，即26行條件不滿足）。然后，在leader為這個視圖聚合出有效的prepareQC之后，所有副本將在接下來的所有階段進行投票，從而產生一個新的決策。在GST之后，這些階段完成的持續時間是有界的。
