注：原文 2019.6.26年發佈在medium上
最近，Facebook的加密貨幣項目Libra發佈了白皮書，在Github上開源了測試網代碼。在白皮書中，我們可以看到Libra使用了LibraBFT，一種拜占庭容錯共識協議。因為這個協議來源於Hotstuff協議，因此學習後者可以幫助我們理解LibraBFT。
1、Hotstuff是什麼？
Hotstuff是一種基於leader的拜占庭容錯協議，由VMware實驗室在2018年3月提出。該論文將發佈在PODC 2019上。類似於許多共識協議，假設網絡是一個可靠和安全的P2P網絡，通訊模型採用部分同步模型，這意味着網絡存在一個消息傳輸延遲上限。
本文，將簡要介紹Hotstuff的工作原理，以及通過先介紹PBFT來逐漸説明Hotstuff如果打到目的。
2、PBFT是什麼？
一般來説，共識協議用來在去中心化網絡當中對系統狀態達到共識，然後所有誠實的節點可以從一個狀態轉移到另一個狀態。
一般來説，PBFT採用二階段的P2P消息交換來實現這個目的。
當leader廣播它提出的（合法的）狀態變化請求給其他節點，一個系統裏的誠實節點，首先需要知道有足夠多的節點收到了這個請求，這樣它可以確認這個請求是合法的。基於這一點，它還需要知道有足夠多的節點也確認了這個請求是合法的，因此確認這是一個在足夠多的節點間關於狀態變化的共識。
當leader在運行協議過程中失敗了，比如節點發現無法與leader節點通信，然後需要替換leader，這意味着需要修改view。這時，系統中的節點發出改變view的請求。當一個節點收到足夠多的改變view的請求時，發出確認改變view的消息給新的leader。當新的leader收到足夠多的確認改變view的消息時，新的view開始產生。
3、Basic HotStuff是什麼？
我們相信HotStuff第一個也是最重要的改變是將PBFT的網狀通信網絡編程星型通信模型，這意味着每次通信只需要依賴leader。節點不再通過P2P網絡將信息廣播給其他節點，而是發送給leader，由leader處理併發送給其他節點。歸功於星型網絡模型，系統通信複雜度
大大下降。類似於PBFT，leader提出狀態改變請求，其他節點接收到請求後校驗請求合法性。
圖1 網狀網絡模型到星型網絡模型
HotStuff第二個重要的改變將改變view的過程合併到正常執行過程，這意味着不需要單獨的改變view的過程，因此降低了改變view的複雜度。可以看到，在HotStuff裏，在改變view過程中，節點不需要在通知新leader以前，確認消息“有足夠多的節點想要改變view”，取而代之的是，直接切換到新的view，然後通知新的leader。Hotstuff將確認“有足夠多的節點想要改變view”的消息放到正常執行中。這是一個新的方法，但是不可避免的導致對於正常處理過程引入一個新的新的確認階段。因此，HotStuff擴展PBFT的二階段到三階段。
介紹完這兩個改變，現在讓我們看一下HotStuff的階段。這個協議中，leader首先收集replica發出的新view的消息。當leader收集到足夠多的新view的消息，它開始新的view，提出狀態改變請求，然後發送prepare消息給其他節點。接收到prepare消息後，節點校驗消息的合法心，然後通過一下三個階段確認消息：
- PRE-COMMIT階段
當leader接收到當前提案的prepare投票時，組合這些投票到prepare quorum certificate（qc）中，然後在放到precommit消息中，廣播給其他節點，這意味着有足夠多的節點確認這個狀態改變請求。 - COMMIT階段
當leader接收到當前提案的precommit投票時，組合這些投票到precommit quorum certificate（qc）中，然後在放到commit消息中，廣播給其他節點。其他replica可以鎖定當前狀態改變請求，所以可以達到共識結論，即使在一次view改變過程中（？？）。 - DECIDE階段
當leader接收到當前提案的commit投票時，組合這些投票到commit quorum certificate（qc）中，然後在放到decide消息中，廣播給其他節點。收到decide消息後，replica可以在已提交分支上執行狀態改變，並且開始新的view。
圖2 basic HotStuff
什麼是門限簽名？
為了進一步降低通信複雜度，HotStuff做的第三個改變是引入了一個新的密碼學原語：門限簽名。
假設在一個(k,n)的門限簽名框架裏，n個replica共同擁有一個公鑰，每個replica擁有一部分的私鑰（分片）。只要有k個replica對消息進行了簽名，這k個簽名就能構造出一個完整的簽名，並且可以被公鑰驗證。
一般來説，完整的簽名和replica的數量無關。Hotstuff使用門限簽名來降低在共識協議中的簽名個數。
我們可以看到在Hotstuff的三階段確認中，投票就是replica的門限簽名過程，然後發送給leader。leader收集到足夠多個投票，就生成完整的簽名。leader會將簽名發到下一個階段的消息裏，發送給replica，並被校驗簽名。
圖3 門限簽名
HotStuff的流水線
可以看到Basic HotStuff的三個確認階段都有相同的結構，節點對消息投票，leader聚合投票，併發送給其他節點。這些階段可以用通用的方式標識並流水線化。這也是HotStuff的第四個改變，共識階段的流水線化。
圖4 流水線
pipelined HotStuff在Basic HotStuff上做了改進，在每次prepare階段都改變view。事實上，我們可以看到下一個view的prepare對當前的view的prepare進行確認，就是下一個view的prepare消息裏包含了當前view的prepare-commit消息。由於所有階段的結構都是一致的，所以流水線化可以實現。
問題
- 為什麼需要增加一個階段？
- 流水線代碼怎麼實現？
