HotStuff共識算法詳解

1. 前言

HotStuff提出了一個三階段投票的BFT類共識協議,該協議實現了safety、liveness、responsiveness特性。通過在投票過程中引入門限簽名實現了O(n的消息驗證復雜度。Hotstuff總結出對比了目前主流的BFT共識協議,構建了基于經典BFT共識實現pipeline BFT共識的模式。

HotStuff是基于View的的共識協議,View表示一個共識單元,共識過程是由一個接一個的View組成。在一個View中,存在一個確定Leader來主導共識協議,并經過三階段投票達成共識,然后切換到下一個View繼續進行共識。假如遇到異常狀況,某個View超時未能達成共識,也是切換到下一個View繼續進行共識。

Basic hotStuff基礎版本的共識協議,一個區塊的確認需要三階段投票達成后再進入下一個區塊的共識。pipeline hotStuff是流水線的共識協議,提高了共識的效率。

2. 協議內容

2.1. 協議基礎

2.1.1. 名詞解釋

  • BFT: 全稱是Byzantine Fault tolerance, 表示系統可以容納任意類型的錯誤,包括宕機、作惡等等
  • SMR: 全稱是State Machine Replication, 一個狀態機系統,系統的每個節點都有著相同的狀態副本
  • BFT SMR protocol: 用來保證SMR中的各個正常節點都按照相同的順序執行命令的一套協議
  • View: 表示一個共識單元,共識過程是由一個接一個的View組成的,每個View中都有一個ViewNumber表示,每個ViewNumber對應一個Leader
  • QC(quorum certificate): 表示一個被(nf)個節點簽名確認的數據包及viewNumber。比如,對某個區塊的(nf)個投票集合。
  • prepareQC: 對于某個prepare消息,Leader收集齊(nf)個節點簽名所生成的證據(聚合簽名或者是消息集合),可以視為第一輪投票達成的證據
  • lockedQC: 對于某個precommit消息,Leader收集齊(nf)個節點簽名所生成的證據(聚合簽名或者是消息集合),可以視為第二輪投票達成的證據。

2.1.2. 副本狀態機 | State Machine Replication

副本狀態機(SMR, State Machine Replication)指的是狀態機由多個副本組成,在執行命令時,各個副本上的狀態通過共識達成一致。

假如各個副本的初始狀態是一致的,那么通過共識機制使得輸入命令的順序達成全局一致,就可以實現各個副本上狀態的一致。

在SMR中,存在一個Leader節點發送proposal,然后各個節點參與投票達成共識。

系統輸入為tx,網絡節點負責將這些tx,打包成一個block,每個block都包含其父block的哈希索引。

2.1.3. 網絡假設

在實際的分布式系統中,由于網絡延時、分區等因素,系統不是同步的系統。

在異步的網絡系統,由FLP原理可知,各個節點不可能達成共識,因此對于分布式系統的分析,一般是基于部分同步假設的。

  • 同步(synchrony):正常節點發出的消息,在已知的時間間隔內可以送達目標節點,即最大消息延遲是確定。
  • 異步(asynchrony):正常節點發出消息,在一個時間間隔內可以送達目標節點,但是該時間間隔未知,即最大消息延遲未知。
  • 部分同步(partially synchrony): 系統存在一個不確定的GST(global stable time)和一個Δ,使得在GST結束后的Δ時間內,系統處于一個同步狀態。

2.2. basic HotStuff 三階段流程

2.2.1. Prepare階段

每個View開始時,新的Leader收集由(nf)個副本節點發送的NEW-VIEW消息,每個NEW-VIEW消息中包含了發送節點上高度最高的prepareQC(如果沒有則設為空)。

prepareQC可以看做是對于某個區塊(nf)個節點的投票集合,共識共識過程中第一輪投票達成的證據

Leader從收到的NewView消息中,選取高度最高的preparedQC作為highQC。因為highQC是viewNumber最大的,所以不會有比它更高的區塊得到確認,該區塊所在的分支是安全的。

下圖是Leader節點本地的區塊樹, #71是Leader節點收到的highQC, 那么陰影所表示的分支就是一個安全分支,基于該分支創建新的區塊不會產生沖突。

Leader節點會在highQC所在的安全分支來創建一個新的區塊,并廣播proposal,proposal中包含了新的區塊和highQC,其中highQC作為proposal的安全性驗證。

其他節點(replica)一旦收到當前View對應Leader的Proposal消息,Replica會根據會safeNode-predicate規則檢查Proposal是否合法。如果Proposal合法,Replica會向Leader發送一個Prepare-vote(根據自己私鑰份額對Proposal的簽名)。

Replica對于Proposal的驗證遵循如下的規則:

1). Proposal消息中的區塊是從本機lockQC的區塊擴展產生(即m.block是lockQC.block的子孫區塊)

2). 為了保證liveness, 除了上一條之外,當Proposal.highQC高于本地lockQC中的view_number時也會接收該proposal。

 

safety判斷規則對比的是lockQC,而不是第一輪投票的結果,所以即使在上一輪針對A投了prepare票,假如A沒有commit,那么下一輪依然可以對A’投票,所以說第一輪投票可以反悔。

2.2.2. Precommit

Leader發出proposal消息以后,等待(nf)個節點對于該proposal的簽名,集齊簽名后會將這些簽名組合成一個新的簽名,以生成prepare-QC保存在本地,然后將其放入PRECOMMIT消息中廣播給Replica節點。

prepare-QC可以表明有(nf)個節點對相應的proposal進行了簽名確認。

digraph prepare {
    rankdir=LR;

    Leader -> Replica1 [label="PRECOMMIT"]
    Leader -> Replica2 
    Leader -> Replica3 
    Leader -> Replica4 
}
  • 在PBFT、Tendermint中,簽名(投票)消息是節點間相互廣播,各個節點都要做投票收集工作,所以對于每輪投票,Replica都需要至少驗證(nf)個簽名。

  • 在HotStuff中引入了閾值簽名方案,Replica利用各自的私鑰份額簽名,由Leader收集簽名,Replica只需要將簽名消息發送給Leader就可以。Leader將Replica的簽名組裝后,廣播給Replica。這樣HotStuff的一輪投票每個Replica只需要驗證一次簽名。

  • 在HotStuff中,一輪投票的過程,是通過replica與Leader的交互完成

    • replica收到proposal,對其簽名后,發送給Leader
    • Leader集齊簽名(投票)后,將簽名(投票)組裝,廣播precommit消息
    • replica收到Precommit,驗證其中簽名,驗證通過則表示第一輪投票成功。

LibraBFT是基于hotStuff的共識協議,但是并沒有采用hotStuff中的閾值簽名方案

當Replica收到Precommit消息時,會對其簽名,然后回復給leader。

2.2.3. Commit

commit階段與precommit階段類似,也是Leader先收集(n-f)個precommit-vote,然后將其組合為precommit-QC,并將其放在COMMIT消息中廣播。

當Leader收到當前Proposal的(n-f)個precommit-vote時,會將這些投票組合成precommit-QC,然后將其放入COMMIT消息中廣播。

當Replica收到COMMIT消息時,會對其簽名commit-vote,然后回復給leader。更為重要的是,在此時,replica鎖定在precommitQC上,將本地的lockQC更新成收到的precommitQC.

  • 從Replica發出precommit-vote到Leader集齊消息并發出commit消息,這個過程相當于pbft、tendermint中的第二輪投票。
  • Replica收到了commit消息,驗證成功后,表示第二輪投票達成。此時Replica回復給Leader,并且保存precommitQC到lockedQC.

2.2.4. Decide

當Leader收到了(n-f)個commit-vote投票,將他們組合成commitQC,廣播DECIDE消息。

Replica收到DECIDE消息中的commitQC后,認為當前proposal是一個確定的消息,然后執行已經確定的分支上的tx。Viewnumber加1,開始新的階段。

  • Note: 這里也是針對輸入做共識,共識后再執行已經確定共識分支上的交易。

2.3. Safety

2.3.1. Safety性證明

2.3.1.1. 同一個View下,不會對沖突的區塊,產生相同類型的QC

證明思路: 反證法,假如在同一個view下,產生了相同類型的QC,而且最多存在f個作惡節點,那么就會有一個誠實節點雙投了,這與前提假設矛盾。

  • Lemma1: 對于任意兩個有效的qc1qc2,假如qc1.type==qc2.type,且qc1.blockqc2.block沖突,那么必然有qc1.viewNumber!=qc2.viewNumber.

證明(反證法):

假設qc1.viewNumber==qc2.viewNumber

那么,在相同的view中,有2f+1個replica對qc1.block進行簽名投票,同樣有2f+1qc2.block投票,這樣的話,就存在一個正常節點在算法流程中投了針對某個消息投了兩票,這與算法流程沖突。

2.3.1.2. 正常Replica不會commit沖突的區塊

證明思路: 反證法,假如正常節點commit了沖突的區塊,我們追蹤到最早出現的沖突區塊的位置,則這個沖突的位置肯定與兩條safety規則相矛盾。

證明:

1. 根據**Lemma1**, 在相同的view下,正常的replica不會對沖突的區塊產生commitQC,所以不會commit沖突的區塊。
2. 下面證明在不同的view下,正常的replica也不會對沖突的區塊產生commit

證明(反證法):

假設viewNumber在v1和v2時(v1 < v2),commit了沖突的區塊,即存在commitQC_1 = {block1, v1}, commitQC_2={block2, v2},且block1與block2沖突。為了簡化證明,我們同時假設v1與v2之間不存在其他的commitQC了,即commitQC_2是commit_1之后的第一個commitQC.

在v1和v2之間,肯定存在一個最小的v_s(v1 < v_s <= v2),使得v_s下存在有效的prepareQC_s{block_s, v_s},其中block_s與block1沖突.

當含有block_s的prepare被廣播后,節點會對該消息做safety驗證,由于block_s與block1沖突,所以顯然,不符合safety規則1.

那么是否會符合規則2呢?
假如block_s.parent.viewNumber > block_1.viewNumber,那么顯然block_s.parent與block_1沖突,所以block_s.parent是更早的與block1沖突的,這與v_s最小矛盾。

有2f+1個節點對于block_s的prepare消息投了票,那么這些節點在收到Prepare_s時,會進行safeNode驗證,正常情況下,由于block_s與block1沖突,那么正常節點不會投出prepare_vote票,故而根本不會產生prepareQC_s, v_s根本不會存在. 這與上述假定沖突,因此在不同的view下,不可能對相同的block產生commit.

2.4. chained hotStuff

在basic hotStuff中,三階段投票每一階段無非都是發出消息然后收集投票,那么可以使用如下的方式簡化協議。

在Prepare階段的投票由當前view對應的leader1收集,集齊后生成prepareQC。然后將prepareQC發送到下一個view的leader2那里,leader2基于prepareQC開始新的prepare階段,這是leader2的prepare階段,同時也是leader1的precommit階段。以此類推,leader2產生新的prepareQC,然后發送給下一個view的leader3,leader3開始自己的prepare階段,同時也是leader1的commit階段、leader2的precommit階段。

協議簡化為如下過程:

  • Leader節點
    • 等待NewView消息,然后發出Proposal
    • 發出Proposal后,等待其他節點的投票
    • 向下一個Leader發出NewView消息
  • 非Leader節點
    • 等待來自Leader的Proposal消息
    • 收到Leader的Proposal消息后,檢查消息中的QC,更新本地的prepareQC、lockedQC等變量,發出投票
    • 向下一Leader發出NewView消息

2.4.1. Dummy block

正常情況下,每個View中都有一個區塊產生并集齊簽名,但是情況不會總是這么完美,有時不會有新的區塊產生。為了保持區塊高度與viewNumber的一致,hotStuff中引入了Dummy block的概念。假如在一個View中,不能達成共識,那么就在為該View添加一個Dummy block

2.4.2. k-chain

一個區塊中的QC是對其直接父區塊的確認,那么我們稱之為1-chain。同理,一個區塊b后面沒有Dummy block的情況下,連續產生了k個區塊,則稱這段區塊鏈分支是對區塊b的k-chain。

如果b’對b形成了1-chain,那么b’相當于b的prepare階段達成(第一輪投票成功),節點會將本地的prepareQC更新。

每當一個新的區塊形成,節點都會檢查是否會形成1-chain,2-chian,3-chain.

  • 1-chain: 有新的prepareQC形成,更新本地的prepareQC
  • 2-chain: 有新的precommitQC形成,更新本地的lockedQC
  • 3-chian: 有新的commitQC形成,有新的區塊分支進入commit狀態,執行確認的區塊分支

2.4.3. Pacemaker

把hotstuff抽象成一個事件驅動的協議,可以將liveness相關的功能抽離出來,成為單獨的pacemaker模塊。safety與liveness在實現上解耦,safety是協議的核心保證安全性,liveness由pacemaker保證。

  • Pacemaker實現如下幾部分功能
    • Leader檢查
    • 收集NewView消息,對齊View并更新highQC

3. Q&A

  • BFT類共識算法研究對比: PBFT - Tendermint - hosStuff - Casper - GRANDPA

    • PBFT: 兩階段投票,每個view有超時,viewchange通過一輪投票來完成,viewchange消息中包含了prepared消息(即達成了第一階段投票的消息)。
    • Tendermint: 兩階段投票,一個round中的各個階段都有超時時間,roundchange通過超時觸發(而不是投票),網絡節點保存自己已經達成第一階段投票的消息(即polka消息)。
    • hotStuff: 三階段投票,每個view有超時,采用閾值簽名減小消息復雜度。liveness與safety解耦為兩個部分
    • GRANDPA: 將出塊與共識確認分離,用來對已經產生的區塊鏈進行投票確認,兩階段投票,但是投票是針對區塊分支(對一個區塊投票也相當于對其所有父區塊投票),而不是特定區塊,各個節點可以針對不同高度的區塊投票
  • 第三階段投票的意義?(對比pbft、tendermint)
    • 表面上看,第三輪投票是為了在確認大多數節點(2f+1)達成前兩輪投票后,再發出NewView消息。這是為了通過用一輪投票來保證大多數節點都可以進入下一個高度,通過一輪投票讓各個節點保持視圖對齊。

    • 反過來看,假如去掉第三輪投票,達成第二輪投票后就發出NewView消息,會出現各個節點步調不一致,如果新的Leader自身運行的慢一點,第二輪投票還沒有達成,那么收到NewView時,校驗時會通不過。(但是通過幾輪超時切換,共識流程依然會正常進行)

    • 我認為,假如沒有第三階段,不會影響節點的liveness和safety特性。

    • 在PBFT中的view change也是通過一輪投票實現的,與hotstuff中一樣,只是pbft中只有在leader不能工作時候才會啟動view change,在hotstuff中每個區塊都會切換leader。加入pbft也是每次都切換Leader,那么pbft算上view change的話,也是三階段投票。

    • 在tendermint中,視圖切換沒有通過投票來完成,而是通過固定的時間間隔來實現的,即使集齊了兩輪投票也需要等待本輪view的時間耗盡才會進入下一個view,通過時間的等待,確保節點的視圖對齊。tendermint這樣的優點是少了一輪投票,但是犧牲了responsiveness。responsiveness指的是一個區塊被leader發出后,到達成共識的時間間隔只與實際的網絡延時有關。而Tendermint中,即使網絡狀態完好,依然需要等待6秒左右的時間才能達成共識。hotstuff使用一輪投票,保持了responsive特性。

  • 達成第二階段投票后,區塊就不可逆轉了,假如在此時執行交易是否有問題?
    • 我認為可以,但是會造成各個節點的臨時狀態新舊不一,而放在第三階段投票后執行,可以保證大多數節點的狀態一致性,與視圖對齊的效果差不多。
  • 相比于Tendermint, NewView消息的意義是什么?
    • NewView消息中包含了Replica節點的prepareQC,這可以保證,新的Leader能夠基于全局最新狀態進行下一輪共識(而不是只根據自己本地的狀態)。
      • hotStuff新區塊不是在已經commit的區塊上添加,而是在highQC所在的安全分支上添加新區塊,所以NewView消息是有必要的,否則會廣播沖突或者無效的prepare。
      • 在Tendermint中,新的Leader可能是不知道其他節點存在鎖定的區塊,所以只根據節點本地的狀態打包新的區塊,這可能造成不同節點鎖定在不同區塊上。而為了保證Liveness,又引入了解鎖機制(Istanbul中也采用了類似的解鎖方案)。
  • Responsiveness: block的確認時間,只取決于網絡的實際延時,而不是取決于某個預先確定的時間限制。
    • Tendermint在網絡正常情況下,也是6秒左右一個塊
    • hotStuff中區塊的確認時間只與實際的網絡延遲有關
  • Responsiveness在區塊鏈的世界中是否重要?
posted @ 2019-12-12 22:06  gexin1023  閱讀(...)  評論(...編輯  收藏
四川金7乐历史开奖号码查询