polkadot共識主要有三種：npos, babe, grandpa
接下來我們對這三種共識進行逐一的解釋
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: 給定，能夠給出一個 ，使得最大
fair representation: proportional justified representation(pjr)規則
· 任意一個 ,都不會存在一個提名者的子集，導致出現下面的情況：
用較為通俗的話來說就是不允許出現：存在某些中的提名者的stake 超過了總的staking的的比重，並且他們支援的人選有交集的超過個，但是他們支援的validator的數量入選卻沒有超過個。上述的問題在數學上就是一個最最佳化問題，很可惜這個選舉在數學上已經被證明是 np完全問題，並不能在多項式時間內給出最優解。所以polkadot給出了自己的一套解決方案，來繞過這個難解問題。npos流程上述推導的數學模型中，由於是np完全問題，也就是說給出最優解的計算時間複雜度是無法確定在多項式時間內的。polkadot給出了一個相對來說可行的方案。不追求最優解，達到相對最優即可np完全問題中給出可行解是很困難的，但是驗證已有解是簡單的，能在多項式時間內完全。所以驗證可行解的部分放在鏈上進行。▲ 完整的流程如下：
在提名者給出自己的投票之後，每一個候選者都可以給出自己對於上述選舉問題的一個可行解。
在上述這些可行解的集合中，利用鏈上的方案比較方案，按照之前的“三大原則”來比較這些方案，選取其中最優的方案最為最後驗證人選舉結果，這樣就完成了一輪選舉。
babe
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
grandpa則是用來做區塊確認的，在文章的第二部分我們有提到babe將會對polkadot的交易進行出塊，那麼這些出塊最終就是由grandpa來確定的。
像其他pbft的衍生演算法一樣，grandpa的時間複雜度也是o(n?)。但是polkadot之所以採用grandpa是因為grandpa並不是每次只確認一個區塊，它每一次都會確定好幾個區塊來做確認。
idle (24 peers), best: #664257 (0x706c…76b7), finalized #664253 (0xe4ab…4d2a)imported #664258 (0xee71…6321)idle (24 peers), best: #664258 (0xee71…6321), finalized #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上區塊鏈的共識演算法。
