可PBFT共識演算法也有"軟肋",從其三階段共識流程得以一窺。
從上圖可看出,PBFT共識流程中,節點之間需要相互廣播共識訊息包,且網路複雜度與節點數目的平方成正比,嚴重限制了PBFT的可擴充套件性。
下圖整理自IBM研究員Marko調研,反映了採用不同共識演算法的區塊鏈系統節點規模與交易延遲之間的關係:
從中可看出,BFT類共識演算法效能很高,但其支撐的節點規模最多不超過1000。
2019年,HotStuff成為各區塊鏈平臺爭相研究的共識演算法,相對於PBFT,HotStuff具備演算法簡單、網路複雜度與節點規模成線性關係等多種優勢。下圖是HotStuff的核心流程:
由於HotStuff複雜度仍然與節點規模成正比,沒法從根本上解決共識演算法可擴充套件性問題,且HotStuff每個階段都依賴於Leader收集、廣播訊息包,Leader會成為每輪共識的瓶頸。
基於以上調研,FISCO BCOS團隊先後實現了PBFT分組共識演算法、HotStuff共識演算法。但隨著節點規模的增加,這些共識演算法的效能、吞吐率逐漸下降。因此,我們開始探索一種不會因節點數量增加而導致區塊鏈系統效能快速線性下降的共識機制,RPBFT共識演算法在這種情況下應運而生。
RPBFT共識演算法核心思想
RPBFT共識演算法的目標是在保障區塊鏈系統效能、安全性的前提下,將共識演算法網路複雜度與共識節點規模解耦,提升區塊鏈系統的可擴充套件性。
為實現這個目標,FISCO BCOS團隊參考DPOS思路,在大節點規模下,隨機選取部分節點作為“共識委員節點”參與每輪PBFT共識,由於共識委員節點數目固定、與節點規模無關,因此RPBFT共識演算法可擴充套件性更強。
此外,為了保障系統安全、防止共識委員節點聯合作惡,RPBFT演算法會週期性地替換共識委員節點,如下圖所示:
RPBFT共識演算法實現方案
RPBFT演算法主要包括2個系統引數:
· epoch_sealer_num:每輪共識過程中參與共識的節點數目,可透過控制檯發交易方式動態配置該引數。
· epoch_block_num: 共識節點替換週期,為防止選取的共識節點聯合作惡,RPBFT每出epoch_block_num個區塊,會替換若干個共識委員節點,可透過控制檯發交易的方式動態配置該引數。
這兩個配置項記錄在系統配置表中,配置表主要包括配置關鍵字、配置對應的值、生效塊高三個欄位,其中生效塊高記錄了配置最新值的最新生效塊高,例:在100塊發交易將epoch_sealer_num和epoch_block_num分別設定為4和10000,此時系統配置表如下:
RPBFT共識演算法核心演算法流程如下:
確定各共識節點編號IDX
對所有共識節點的NodeID進行排序,如下圖,節點排序後的NodeID索引即為該共識節點編號:
鏈初始化
鏈初始化時,RPBFT需要選取epoch_sealer_num個共識節點到共識委員中參與共識,目前初步實現是選取索引為0到epoch_sealer_num-1的節點參與前epoch_block_num個區塊共識。
共識委員節點執行PBFT共識演算法
選取的epoch_sealer_num個共識委員節點執行PBFT共識演算法,驗證節點同步並驗證這些驗證節點共識產生的區塊,驗證步驟包括:
· 校驗區塊簽名列表:每個區塊必須至少包含三分之二共識委員節點的簽名
· 校驗區塊執行結果:本地執行結果須與共識委員產生的區塊執行結果一致
動態替換共識委員節點列表
為保障系統安全性,RPBFT演算法每出epoch_block_num個區塊後,會在共識委員列表中剔除若干個節點,並加入若干個驗證節點,下面以每epoch_block_num個區塊剔除一個節點為例:
在目前的RPBFT演算法實現中,共識委員列表節點被輪流替換為驗證節點,設當前有序的共識委員會節點列表為CommitteeSealersList,共識節點總數為N,則共識epoch_block_num個區塊後,會將CommitteeSealersList[0]剔除出共識委員列表,並加入索引為(CommitteeSealersList[0].IDX + epoch_sealer_num) % N的驗證節點。第i輪替換週期,將CommitteeSealersList[i % epoch_sealer_num]剔除出共識委員列表,加入索引為(CommitteeSealersList[i%epoch_sealer_num].IDX + epoch_sealer_num) % N的驗證節點。
RPBFT網路最佳化
考慮到Prepare資料包較大,佔網路開銷大頭,為了進一步提升RPBFT共識演算法可擴充套件性,我們在FISCO BCOS 2.3引入了Prepare包廣播最佳化。將Leader因廣播Prepare包產生的出頻寬流量分攤給其下屬子節點,即:Leader產生Prepare包後,沿著樹狀拓撲將資料包傳播給其他節點,如下圖所示:
為保證在節點斷連情況下開啟樹狀廣播時,Prepare包仍能到達每個節點,RPBFT引入了基於狀態包的容錯機制,如下圖所示:
主要流程包括:
1. 節點A收到Prepare後,隨機選取33%節點廣播Prepare包狀態,記為prepareStatus,包括{blockNumber, blockHash, view, idx}。
2. 節點B收到節點A隨機廣播過來的prepareStatus後,判斷節點A的Prepare包狀態是否比節點B當前Prepare包localPrepare狀態新。主要判斷依據包括:
(1) prepareStatus.blockNumber是否大於當前塊高
(2) prepareStatus.blockNumber是否大於localPrepare.blockNumber
(3) prepareStatus.blockNumber等於localPrepare.blockNumber情況下,prepareStatus.view是否大於localPrepare.view
以上任意一個條件成立,都說明節點A的Prepare包狀態比節點B的狀態新。
3. 若節點B的狀態落後於節點A,且節點B與其父節點斷連,則節點B向節點A發出prepareRequest請求,請求相應的Prepare包。
4. 若節點B的狀態落後於節點A,但節點B與其父節點相連,若節點B最多等待100ms(可配)後,狀態仍然落後於節點A,則節點B向節點A發出prepareRequest請求,請求相應的Prepare包。
5. 節點B收到節點A的prepareRequest請求後,向其回覆相應的Prepare訊息包。
6. 節點A收到節點B的Prepare訊息包後,執行handlePrepare流程處理收到的Prepare包。
區塊落盤後,為降低多個驗證節點、觀察節點向共識委員節點同步區塊時,共識委員節點的網路出頻寬對網路可擴充套件性的影響,RPBFT採用了區塊狀態樹狀廣播策略,詳細可參考FISCO BCOS同步模組的最佳化策略。
RPBFT演算法最佳化展望
FISCO BCOS 2.3初步實現了RPBFT共識演算法,消除了節點規模對共識演算法複雜度的影響。但目前實現的RPBFT共識演算法,仍有待改進的地方,諸如:共識委員節點選取替換規則比較簡單等。
未來計劃引入VRF可驗證隨機數演算法來實現私密、隨機、非互動式的共識委員節點選取方法,歡迎大家體驗並反饋意見。
小結
本文介紹了BFT類演算法的挑戰以及FISCO BCOS團隊在共識演算法領域探索的初步成果。
分散式系統共識是大而複雜的領域,FISCO BCOS 2.3釋出的RPBFT演算法目前僅解耦了節點規模對網路複雜度的影響,是實現高安全、可擴充套件共識演算法的第一步,未來還會引入VRF演算法來保證共識委員節點選取的安全性,敬請期待。