· 任意一個 ,都不會存在一個提名者的子集，導致出現下面的情況：
用較為通俗的話來說就是不允許出現：存在某些中的提名者的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上區塊鏈的共識演算法。
參考文獻：
[1] Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain Bernardo David , Peter Gaˇzi , Aggelos Kiayias November 14, 2017
