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