Categories
程式開發

Polkadot系列(二)——混合共識詳解


本文作者

夏立偉,陶勇星

來自趣鏈科技數據網格實驗室BitXHub團隊,主要負責區塊鏈賬本互操作技術相關研究工作。

導讀:此文是Polkadot系列文章第2篇,Polkadot的混合共識詳解。當說到Polkadot的共識時,很多人的第一反應是Polkadot有很多的共識算法,有很多新鮮的名詞,由於Polkadot共識算法的數量較多、功能各異,很多人對Polkadot採用的共識算法有很多疑問,其中最容易混淆的是多種不同的共識算法之間如何協作的問題,本文接下來擬針對Polkadot的共識進行深度剖析。

Polkadot共識主要有三種

NPOS,寶貝,爺爺

接下來我們對這三種共識進行逐一的解釋

NPOS

什麼是NPOS共識

在Polkadot 中,中繼鏈上的驗證者需要分配到各個平行鏈,為它們提供區塊鏈驗證能力,是Polkadot 共享安全性的一部分,因此中繼鏈的驗證者對於整個Polkadot多鏈系統的安全性至關重要。

如何公平安全地選舉出中繼鏈上的驗證者也就成了保障整個系統共享安全性的第一步,是不可或缺的一步。

NPOS( Nominated Proof of Stake)共識算法就是用來選舉出能讓系統更安全,更高效的驗證者集合的。和傳統意義上的POS共識相比,NPOS算法結合了Polkadot鏈自身架構的一些特點,進行相應的優化。

下面看看NPOS是如何進行工作的。

在說明NPOS之前,我們需要先回顧一下Polkadot中重要的兩種角色。

▲ 驗證人

中繼鏈的全節點,中繼鏈會在驗證人池中通過隨機分組把驗證人指定給不同的平行鏈。驗證人會接受來自收集人打包的區塊並進行有效性驗證,然後結合共識算法對收集人提交的區塊進行確認。

▲ 提名人

Polkadot中數字貨幣DOT的持有人,它會選擇自己所信任的驗證人進行DOT質押,然後分享驗證人的收益。

Polkadot的選舉模型是建立在這兩種角色基礎上的。要成為驗證人,必須先成為驗證人候選人參加選舉的過程,而這個選舉過程中的“選民”就是提名人。

在Polkadot的設計中,提名人數量在理論是可以不設置上限的,如果能夠讓更多的提名者參與到投票階段,那麼參與到選舉的資金量也就越大,整個系統就更加的安全;而對於驗證者來說,為了區塊鏈的性能,不能太多(所有節點都能作為驗證者的話,那就是比特幣採用的模式了),驗證者的數量由系統確定的固定值,這一點來說和POS共識是一致的。

選舉模型

為了明確選舉問題,Polkadot中將選舉驗證者集合的問題抽象為一個數學的選舉問題:

▲ 問題:m 個選民對n 個候選者的情況下,選出最終的t 為當選者

(注:提名人可以有任意個,驗證者是有限個)

問題的描述很簡單,但是如何做到讓系統更安全,會有不同的策略。 Polkadot的設計哲學中,認為選舉策略需要滿足下面的“三大原則”:

Balance: 驗證者在出塊時候的比重相同,因此該策略在Stake分配需要盡量平均,保證網絡的安全;

Support: 該策略需要讓盡可能多的Stake 資金參與進來。因為提名者只負責選投哪些候選者,但是對於的Stake具體分配給多少到哪個驗證者是沒有決定權的,這部分是NPOS算法通過計算來決定的。這也是NPOS和普通的POS共識中很大的不同之處;

Fair representation: Stake 多的提名者選投的驗證人更可能出現在驗證者集合中。

輸入:給定,其中是Nominator集合,是Validator候選者集合,是邊的集合,表示提名者投了候選者一票。同時給定向量,表示各個提名者各自的Stake數量,是選出的最終驗證者集合的大小。輸出:給定解,其中是最終選定的Validator,大小為, 是提名者分配多少Stake 到最終的Validator。限制條件:Balance: 給定,能夠給出一個 ,使得最小Support: 給定,能夠給出一個 ,使得最大

公平表示:比例合理表示(PJR)規則

任意一個,都不會存在一個提名者的子集,導致出現下面的情況:

Polkadot系列(二)——混合共識詳解 1

用較為通俗的話來說就是不允許出現:存在某些中的提名者的stake 超過了總的staking的的比重,並且他們支持的人選有交集的超過個,但是他們支持的Validator的數量入選卻沒有超過個。

上述的問題在數學上就是一個最優化問題,很可惜這個選舉在數學上已經被證明是NP完全問題,並不能在多項式時間內給出最優解。

所以Polkadot給出了自己的一套解決方案,來繞過這個難解問題。

NPOS流程

上述推導的數學模型中,由於是NP完全問題,也就是說給出最優解的計算時間複雜度是無法確定在多項式時間內的。

Polkadot給出了一個相對來說可行的方案。

不追求最優解,達到相對最優即可NP完全問題中給出可行解是很困難的,但是驗證已有解是簡單的,能在多項式時間內完全。所以驗證可行解的部分放在鏈上進行。

▲ 完整的流程如下:

Polkadot系列(二)——混合共識詳解 2

在提名者給出自己的投票之後,每一個候選者都可以給出自己對於上述選舉問題的一個可行解。

在上述這些可行解的集合中,利用鏈上的方案比較方案,按照之前的“三大原則”來比較這些方案,選取其中最優的方案最為最後驗證人選舉結果,這樣就完成了一輪選舉。

寶貝

BABE的全稱是Blind Assignment for Blockchain Extension,BABE是一個用來出塊的引擎,類似於Ourobros Praos,一種PoS的協議。 BABE算法是基於slots的。

在Polkadot中每一個slot差不多6秒長的時間。

每個slot時間段中BABE會選出一個leader來出塊。

BABE中leader的選舉是通過一個隨機函數(VRF)來實現的,在每個slot階段,每一個節點會通過運算VRF函數來獲得一個數值,如果這個數值小於網絡中預先規定好的閾值,那麼節點就會認為自己就是這個時間段的leader,於是節點就開始出塊了。

值得注意的是在上述的過程中,由於VRF函數是隨機生成數字的,所以可能造成在某一slot中沒有leader或者有多個節點算出自己的VRF值小於閾值進而產生多個leader的情況。我們依次分析兩種情況:

當沒有leader產生時,Polkadot就規定按照順序來決定誰是leader,這個順序是預先確定好的。

當出現多個leader的時候,Polkadot允許多個節點都提交區塊,而最終區塊的確認則由GRANDPA來決定。

爺爺

GRANDPA則是用來做區塊確認的,在文章的第二部分我們有提到BABE將會對Polkadot的交易進行出塊,那麼這些出塊最終就是由GRANDPA來確定的。

像其他PBFT的衍生算法一樣,GRANDPA的時間複雜度也是O(n²)。但是Polkadot之所以採用GRANDPA是因為GRANDPA並不是每次只確認一個區塊,它每一次都會確定好幾個區塊來做確認

閒置(24個對等),最好:#664257(0x706c…76b7),已確定#664253

(0xe4ab…4d2a)

進口#664258(0xee7​​1…6321)

空閒(24個對等),最好:#664258(0xee7​​1…6321),已確定#664256

(0x809a…a5d8)

上面是Polkadot測試網絡的一段日誌,可以看到一次確認區塊高度從664253到了664256,所以GRANDPA一次性確認了三個區塊。這樣的話跟一次性只確認一個相比,GRANDPA的效率要比其他PBFT的衍生算法要高出很多。

▲ 下面介紹一下GRANDPA的具體流程:

1. 一個主節點廣播之前一輪確認後的區塊高度;

2. 等待網絡延遲以後,每個節點都廣播他們認為的可以被確認的最高的區塊(pre-vote);

3. 每個節點對步驟2接受到的區塊集進行計算,算出他們認為的能夠被確認的最高區塊,並且將結果廣播出去(pre-commit);

4. 當節點接收到足夠的pre-commit的消息能夠確認區塊後就會形成commit的消息,一般認為大於2/3就可以被確認了。

上述就是GRANDPA確認區塊的主要流程。

我們需要擔心的是在步驟2的pre-vote過程中可能會有作惡的節點投票了兩個區塊並且廣播出去,這樣的話就有可能產生鏈的分叉行為。

Polkadot為了防止這種情況的發生使用了一個叫做Account Safety的方式。

如果當網絡中出現了要分叉的commit信息時,Polkadot的節點會馬上採取Account Safety的機制。每個節點都會詢問其他節點他們所看到的pre-vote的情況,節點都會回复他們收到的信息,這樣就很容易檢查到有哪些惡意節點投了兩個區塊。最後這些被抓到的作惡節點將會被踢出共識網絡,永遠不能進入。

讓我們回到BABE,通過結合BABE和GRANDPA我們可以看到在出塊的時候Polkadot採用BABE出塊,此時節點之間只要發送一次塊信息即可,這樣的話時間複雜度僅僅是O(n) ,在出塊之後節點之間再採用GRANDPA進行塊確認,此時由於確認階段節點之間要通過二次確認來保證確認塊結果的一致性,時間複雜度是O(n²),不過由於是多個塊一次性進行確認,所以兩者結合的混合共識是非常高效的,比普通的PBFT共識要高效很多。

結語

上面三種就是我們向大家介紹的Polkadot的共識算法,可以看到NPOS主要是為了選取Polkadot的共識節點,BABE和GRANDPA通過混合來高效的進行區塊鏈的出塊和確認。

這樣的混合共識比傳統的PBFT共識速度更快,並且在速度更快的基礎上並沒有丟失掉安全性。將出塊和確認區塊兩個階段分開並且使用不同的算法是在區塊鏈共識中值得學習的地方。

通過這三種算法,Polkadot可以說在一定程度上高效的實現了Polkadot上區塊鏈的共識算法。

參考文獻:

[1] Ouroboros Praos:自適應安全的半同步權益證明區塊鏈Bernardo David,Peter Gaˇzi,Aggelos Kiayias 2017年11月14日