金色觀察|共識演算法的進步方式

語言: CN / TW / HK

近兩年,隨著 以太坊 等公鏈的生態發展,應用已經非常之多了,Defi、NFT這些應用雖然比較“簡易”,但鏈上整體操作量之大,讓使用者和開發者還是很相信以太坊的處理能力和其他公鏈的處理能力的。

不過,其他公鏈目前和以太坊相比,一個重要的優勢就是以太坊gas費太高,其他公鏈的gas費極低。

主要原因在於共識演算法,以太坊仍是在用1.0鏈做交易驗證,也就是使用PoW演算法,而其他公鏈大部分都使用了PoS或者改進的PoS、PoW。

本文中我們將分析幾種共識演算法,來展現不同演算法的區別。

一個分散式系統是由多個節點組成,節點之間需要網路傳送訊息通訊,根據它們遵循的協議在某個任務訊息達成共識並一致執行。這個過程中會出現很多型別的錯誤,

第一類錯誤是節點崩潰、網路故障、丟包等,這種錯誤型別的節點是沒有惡意的,屬於非拜占庭錯誤。

第二類錯誤是節點可能是惡意的,不遵守協議規則。例如驗證者節點可以延遲或拒絕網路中的訊息、可以提出無效塊、可以向不同的對等體傳送不同的訊息。在最壞的情況下,惡意節點可能會相互協作。這些被稱為拜占庭錯誤。

考慮到這兩種錯誤,系統始終徐亞保持兩個屬性:安全性(safety)和活躍性(liveness)。

安全性:在以上兩類錯誤發生時,共識系統不能產生錯誤的結果。在區塊鏈的語義下,指的是不會產生雙重花費和分叉。

活躍性:系統一直能持續產生提交,在區塊鏈的語義下,指的是共識會持續進行,不會卡住。假如一個區塊鏈系統的共識卡在了某個高度,那麼新的交易是沒有迴應的,也就是不滿足liveness。

BFT

BFT(拜占庭容錯協議)是一種即使系統中存在惡意節點也能保證分散式系統的安全性和活躍性的協議。根據Lamport論文,所有BFT協議都有一個基本假設:節點總數大於 3f 時,惡意節點最大為 f ,誠實節點可以達成一致的正確結果。

PBFT

實用拜占庭容錯演算法(PBFT)是現實世界裡首批能夠同時處理第一類和第二類錯誤的拜占庭容錯協議之一,基於部分同步模型,解決了之前BFT類演算法效率不高的問題,將演算法複雜度由節點數的指數級降低到節點數的平方級,使得拜占庭容錯演算法在實際系統應用中變得可行。

PBFT正常流程為3階段協議:

pre-prepare:主節點(Primary)廣播預準備訊息(Preprepare)到各副本節點(Replica)

prepare:該階段是各個節點告訴其他節點我已經知道了這個訊息,一旦某個節點收到了包含n-f 個prepare訊息(我們將使用QC也就是Quorum Certificate來指代,下同)則進入prepared狀態

commit:該階段是各個節點以及知道其他節點知道了這個訊息,一旦某個節點收到了n-f 個commit訊息(QC)則進入committed狀態

檢視切換(viewchange)是PBFT最為關鍵的設計,當主節點掛了(超時無響應)或者副本節點集體認為主節點是問題節點時,就會觸發ViewChange事件,開始viewchange階段。

通訊複雜度給PBFT的共識效率帶來了嚴重的影響,極大地制約了PBFT的可擴充套件性。

如何把通訊複雜度降低提高共識效率,是BFT共識協議在區塊鏈場景中面臨的挑戰。針對BFT共識效率的優化方法,具有以下幾類:聚合簽名、通訊機制優化、view-change流程優化。

PBFT,SBFT等協議具有獨立的view-change流程,當主節點出問題後才觸發。而在Tendermint、HostStuff等協議中沒有顯式的view-change流程,view-change流程合入正常流程中,因此提高了view-change的效率,將view-change的通訊複雜度降低。

Tendermint 將roundchange(和viewchange類似)合入正常流程中,因此roundchange和正常的區塊訊息commit流程一樣,不像PBFT一樣有單獨的viewchange流程,因此通訊複雜度也就降低。

HotStuff參考Tendermint,也將檢視切換流程和正常流程進行合併,即不再有單獨的檢視切換流程。通過引入二階段投票鎖定區塊,並採用leader節點集合BLS聚合簽名的方式,

Hotstuff將傳統BFT的兩輪的同步BFT改為三輪的鏈式BFT,沒有明確的prepare,commit共識階段,每個區塊只需要進行一輪QC,後一個區塊的 prepare 階段為前一個區塊的 pre-commit 階段,後一個區塊的 pre-commit 階段為前一個區塊的 commit 階段。每次出塊的時候都只需要低通訊複雜度,通過兩輪的通訊複雜度,達到了之前的效果。

PBFT、Tendermint等協議具有即時確定(Instant Finality)的特性,幾乎不可能出現分叉。在PBFT中,每個區塊被確認後才能出下一個區塊,Tendermint還提出區塊鎖定的概念,進一步確保了區塊的即時確定性,即在某個round階段,節點對區塊訊息投了pre-commit票,則在下一個round中,該節點也只能給該區塊訊息投pre-commit票,除非收到新proposer的針對某個區塊訊息的解鎖證明。

這類BFT共識協議本質上是一個同步系統,將區塊的生產和確認緊密耦合,一個區塊確認後才能生產下一個區塊,需要在塊與塊間等待最大的可能網路延遲,共識效率受到很大的限制。

PlatON:CBFT

CBFT基於部分同步網狀通訊模型,提出了一個三階段共識的並行拜占庭容錯協議。網狀的通訊模型更適合公網的弱網環境。

CBFT 的正常流程和Hotstuff類似,分為prepare,pre-comit,commit 和 decide幾個階段。但 CBFT 還作了關鍵的改進:在一個檢視視窗內可以連續提議多個區塊,下一個區塊的產生不用等上一個區塊達到QC;而且各個節點可以在接收上一個區塊投票的同時,並行執行下個區塊的交易,以 pipeline 的方式對區塊進行投票確認, 從而極大提高了出塊速度。

CBFT 有自適配的檢視切換機制:在一個檢視視窗內,節點接收到足夠多的區塊以及贊成票(超過2/3的節點投票,也就是 QC)時,會自動進行視窗切換,切換到下一個視窗,無需進行 viewchange 投票。除此之外,節點會啟動 viewchange 流程,並且在 viewchange 階段引入了和 Hotstuff 一樣的二階段鎖定投票規則,同時使用 BLS 聚合簽名,可以在低的通訊複雜度內完成檢視視窗切換。

CBFT 只在正常流程之外才會進行 viewchange,因此相比 HotStuff 會有更少的檢視切換開銷。

CBFT共識中,每430個區塊(稱為一個 Epoch)就會更新驗證人集合,更新規則如下:

新驗證人可能由於網路連線或區塊不同步等原因不能參與共識,因此我們每次替換不超過14個節點,如果候選驗證人不足14個,替換的數量為候選驗證人的總數。使用VRF從候選驗證人中隨機選出新驗證人。

Conflux :GHAST

Conflux 可以實現與 比特幣 和以太坊相同水平的去中心化和安全性,但在交易吞吐量(TPS)和最終延遲方面提供了兩個數量級以上的改進。

主要優勢在於共識協議、認證儲存和交易中繼協議。在 Conflux 分類帳中,塊被組織為樹形圖,其中每個塊引用一些其他塊,其中一個是其父塊。僅檢視與父邊連結的塊,賬本似乎是一個樹結構(父樹),而檢視所有塊,它似乎是一個有向無環圖。這也是將 Conflux 的賬本結構稱為 Tree-Graph 的原因。

Conflux 的共識演算法,稱為 Greedy-Heaviest-Adaptive- SubTree (GHAST),通過在賬本中的父樹上應用最重子樹規則,使區塊鏈網路中的所有節點能夠一致地就區塊的樞軸鏈達成一致,進而基於樞軸鏈就所有區塊的總順序達成共識。GHAST 還允許 Conflux 節點檢測一些可能損害活躍性的攻擊(例如,嘗試生成兩個平衡子樹的平衡攻擊),即確認交易的能力,並通過自適應調整塊的權重來阻止這些攻擊。

Tree-Graph 賬本和 GHAST 共識演算法使 Conflux 節點能夠快速生成新塊,而不必擔心賬本中存在分叉可能會損害網路的安全性,從而使系統能夠同時實現高吞吐量以及低交易確認延遲。

其他思路

Dfinity

Dfinity更改共識演算法上,將傳統的共識節點全部參與共識計算修改為通過計算隨機數選取部分節點完成共識計算,這是加快共識驗證的一個步驟。而更核心的是選中的共識節點是通過非互動式的BSL演算法(節點確認資料簽名反饋是獨立進行的,不是組合進行的)確認交易,意味著不會經歷BFT類共識的節點間反覆互動的過程,而達到類似“並行”加速的效果。

IOTA

IOTA對演算法的修改比較徹底,對比區塊鏈,IOTA使用Tangle資料結構形成總帳本Tangle特點是每個事務都附加到兩個先前的事務裡,所以要完全消除了原有區塊鏈鏈式結構對確認時間的依賴。這就形成了交易的無限關聯確認結構,可以達到並行效果。

Filecoin

Filecoin在並行上的修訂,是在對儲存任務的並行處理,因為Filecoin的儲存部分,會對儲存資料完全進行計算,這個過程極為漫長(對比來說)。所以並行和提速非常之重要,目前,其採用的是更新後的NSE演算法。

拆分NSE演算法可以看到的是,當處理資料時,會對資料進行分window(可以理解為一個單元)和分layer層的處理,處理完成後才會進行下一步資料儲存以及後續的Post證明打包。採用NSE後,在layer的處理部分,layer間沒有過多依賴,所以可以形成並行處理效果,可以總結為並行提速的調整。