在當前眾多區塊鏈系統百家爭鳴的形勢下，安全高效的共識協議已經成為大家主要的研究方向之一，PoS、PoA、PoI等眾多共識模型被相繼提出，引發了業界關注。
萬維鏈認為，“權益”才是左右鏈上治理和發展的根本因素，因此費心打造了PoS星系共識（Galaxy Consensus）協議，在眾多共識模型中脫穎而出。
星系共識是萬維鏈理論研發團隊新近提出的高效、安全的實用型PoS共識協議，旨在替代此前的PPoW（permission proof-of-work），在降低能耗的同時，也將其共識系統正式開放給廣大社羣，邁出完全去中心化的關鍵一步。在群星璀璨的共識節點運轉下，打造專屬的共識星系。
本文由加密谷獨家釋出，系列文章將陸續刊出，敬請期待。此前文章請見：
《深度研討之一 | 星系共識：擁有完整委託機制的實用PoS共識協議》
《深度研討之二 | 星系共識：擁有完整委託機制的實用PoS共識協議》
在上篇文章中，我們介紹了星系共識的隨機數生成演算法。在共識過程中，節點會組建成兩大星群——RNP星群和EL星群，前者負責隨機數的生成，後者負責打包交易提出區塊，而這一工作的核心難點就是解決出塊者選擇問題。本文將深入介紹EL星群中出塊者選擇的流程原理和重要作用。
合理出塊者選擇的重要意義
在我們第一篇文章中講到，在區塊鏈共識協議中要解決的兩個核心問題是出塊者選擇（Leader selection）和合法鏈選擇（Chain selection）。
無論在哪種共識協議中，合理的出塊者選擇都是重中之重，我們設計隨機數生成演算法引入熵的一個關鍵作用就是要用於出塊者選擇。
合理的出塊者選擇對保證鏈的安全性和活性至關重要，一個好的出塊者選擇演算法是共識健康執行的基石。出塊者選擇對鏈的安全非常重要。鏈的發展延長本質上就是塊的不斷接續，而完成打包提出區塊的就是這些出塊者。他們一方面決定哪些交易寫入區塊進而上鍊確認，另一方面也透過選擇接入的父區塊決定著鏈的發展走向。
在網路中共識節點善惡並存的環境下，一個好的出塊者選擇演算法就是要保證誠實節點能夠獲得更多的出塊權，進而主導鏈的發展。
當然，不同的共識協議在不同的安全假設之下，出塊者選擇演算法的設計也是不同的。
工作量證明（PoW）的安全假設：50%以上算力安全
在這一安全假設下，PoW採用hash運算的方式進行出塊者選擇，即節點透過大量hash試算來尋找解決難題的隨機資料，也就是挖礦。
這一過程中由於hash函式執行結果的不可預測性，任何節點在hash試算上不存在優勢，是純粹算力的競爭，而50%以上安全算力就保證了出塊者中大部分是誠實節點，進而保證了鏈的安全性。
類BFT協議的安全假設：2/3以上節點安全
在這一安全假設下，類BFT協議通常採用輪流坐莊或概率選擇的方式進行出塊者選擇。無論採用哪種方式，都必然能夠保證誠實節點獲得多數出塊權，同時要求共識網路中節點必須對提議的區塊進行投票，只有獲得了2/3以上投票的區塊才算最終合法區塊，進而保證了鏈的安全性。
權益證明（PoS）的安全假設：50%以上權益安全
在這一安全假設下，PoS協議透過依據節點權益持有量比例隨機選取出塊者，而這一選擇的關鍵就在於隨機性的安全性，保證了隨機源的安全就保證了在大量出塊者選擇過程中誠實節點能夠獲得多數出塊權，進而主導鏈的發展，保證了鏈的安全性。
上面透過介紹了常見共識協議在不同安全假設下出塊者選擇的設計方法，當然也有特殊的混合模式，這裡不進行詳細論述。
由此可見，合理的出塊者選擇對保證鏈的安全極其重要。我們可以用一個簡單的反向例子來直觀理解，如果在BTC挖礦中，某個惡意節點找到了挖礦的竅門進而獲得了半數以上的出塊權，那麼他就可以任意的重構鏈來實現雙花等攻擊，任何一筆交易都將不再可信，這將是對BTC生態系統的毀滅性打擊。
我們再來簡單說說出塊者選擇對保證鏈活性的重要意義。對於“活性”的定義，在不同的解讀文章中都有論述參考，簡言之，就是鏈可以持續穩定的發展延長，有效合法的交易經過一段時間可以得到確認。出塊者本就擔負著鏈發展建設的重任。顯然，他們就是保證鏈活性的主體。有很多共識模型（如Snow White）對於如何保證鏈活性都有深入的研究和探索。
總體來說，要保證鏈活性，需要解決兩個問題：
一是，保證出塊者活性，被選中的出塊者要是活躍的，積極參與共識過程的，而不能是離線或者休眠狀態，進而導致大量區塊的缺失，影響鏈的正常發展；
二是，保證節點間資料一致性，誠實節點必然能夠接收到有效合法交易，並誠實的將其打包進入區塊上鍊確認。加上上面對安全性的論述就能保證鏈的活性。而出塊者的活性就要由出塊者選擇來保證。
這一選擇是一個廣義的概念，並不一定狹義的體現在具體選擇演算法之中，而是在整體的設計理念里加以考慮。Wanchain的星系共識中對此進行了著重思考，並透過權益概念的全新定義、委託機制的設計和獎懲機制的刺激妥善解決，我們在此不再闡述，後續解讀文章將具體解釋。
出塊者選擇演算法需要考慮的幾個問題
上面介紹了出塊者選擇演算法的重要性，那麼，在設計一個出塊者選擇演算法時應該重點考慮哪些問題呢？或者，哪些性質才是評定一個出塊者選擇演算法好壞的衡量標準呢？
公平性：出塊權是依據共識節點資質均衡分配的。例如，PoW中算力越高，獲得出塊權的機會越大；而PoS中權益持有量越大，獲得出塊權的機會越大。這是一個很自然合理的性質，但它的外延很廣，出塊者選擇就像博彩，想要實現真正的公平性也需要規避很多問題。
我們以一個例子來說明：假設A和B是兩個共識節點，透過擲骰子的方式決定誰是出塊者，點數為奇數則A獲得出塊權，為偶數則B獲得出塊權。公平條件下，骰子是被“上帝”擲出，A和B的機會各一半，而如果A獲得了擲骰子的權利，公平性就被打破了，他可以多次試驗甚至直接擺出奇數點數來霸佔出塊權，進而獨自決定鏈的發展甚至肆意進行攻擊，這是十分可怕的。
可驗證性：出塊權的合法性是可以被公開驗證的。例如PoW中區塊頭hash值小於難度值可以被全網運算驗證。這條是顯而易見的必然要求。區塊鏈作為去中心化的系統，其執行必然是接受全網監督認可的，區塊的合法性驗證是基本要求之一，而區塊合法性除了交易合法性和結構的合法性外，出塊者的合法性也是必須要被驗證的一點。所以，任何的出塊者選擇演算法都必須保證出塊權的歸屬是可以被正確驗證的。
匿名性：出塊者透過匿名方式隱私參與共識。這條並不是必然要求。之所以提出是因為匿名性可以解決共識中可能出現的安全風險，如腐蝕攻擊。
具體來說，如果出塊者在其出塊權歸屬時間之間被全網所知，那麼惡意節點有可能透過賄賂等方式將其腐蝕，把原本的誠實節點變成惡意節點，進而進行攻擊，甚至直接進行網路攻擊導致出塊者掉線，這就增強了惡意節點的攻擊能力或削減了誠實節點獲得的出塊權。所以，實現匿名性對於共識協議來說也是一個需要考慮的問題。
很多專案（如Dfinity、Algorand）採用VRF演算法來實現匿名性，但VRF也存在其自身的缺陷和弊端。現在也有專案（如Ouroboros Crypsinous）提出使用零知識證明進行匿名共識，但還沒有具體實現。
常見的出塊者選擇演算法
介紹過出塊者選擇演算法的重要意義和衡量標準，我們簡單列舉三個典型的演算法來具體瞭解一下當前常用的出塊者選擇方式：
算力競爭
算力競爭的方式是區塊鏈系統裡最早使用的出塊者選擇演算法，最典型的就是BTC系統，是比較簡單粗暴又直接有效的方式。
共識節點打包交易後，透過不斷調整區塊頭中的隨機數來反覆運算區塊頭的hash值，當hash值小於當前區塊要求的難度值時就形成了符合要求的合法區塊，此時就獲得了出塊權，成為一名合法的出塊者，也就是完成了整個挖礦過程。
這種方式的好處就是對於所有參與節點都是公平的，任何節點不會在hash運算上取得優勢，只要總體算力超過一半是安全的，那麼鏈就是安全的。同時，這種方式在同一區塊高度可能存在多個合法區塊和合法出塊者，會出現短暫分叉，這也是BTC系統需要等待確認時間的原因。
目前來看，這種出塊者選擇演算法是共識協議中去中心化程度最高的。當然，隨著技術的發展和研究的深入，挖礦也從最初的CPU挖礦逐步發展到GPU、ASIC挖礦，算力增長迅速。很多專案為抵抗晶片挖礦透過增加儲存要求設計了新的共識協議，如Zcash的Equihash。
Verifiable Random Function（VRF）
VRF用於出塊者選擇演算法是為了解決匿名性而提出，具體方式是先設定一個合理的閾值，節點利用自身的私鑰對某一隨機資料進行運算（如簽名），得到的結果小於設定的閾值則為合法出塊者，獲得出塊權。
這一過程中，由於私鑰運算只能節點自身進行，保證了其他節點不能獲知出塊權歸屬。而計算結果如簽名結果可以被公開驗證，確保了出塊權合法性可以被驗證，形成了完整的出塊者選擇過程。
顯然，這種方式是概率性的，若想某一區塊高度可以有儘量多的合法出塊者，就需要儘量提高閾值；反之，想要某一區塊高度可以有儘量少的合法出塊者，就需要儘量降低閾值，這對閾值的設定就有極高的要求，同時對私鑰運算結果的分佈也要有較好的預期，這往往是很難做到的。就容易出現某一區塊高度有大量合法出塊者而形成密集分叉，某一區塊高度沒有合法出塊者而形成空白。所以，VRF演算法雖然解決了匿名性問題，但在具體使用中仍然存在難以避免的問題。
follow-the-satoshi
follow-the-satoshi是PoS中常見的一種出塊者選擇演算法。具體方式是，將所有的代幣進行排序編號，透過一個隨機源產生一個隨機數，這個隨機數落到了哪個代幣的編號上，那麼這枚代幣的持有者就是合法的出塊者，獲得了出塊權。
這種方式顯然是唯一確定性的，難點就在於如何找到一個安全的隨機源來產生真隨機數。Cardano專案當前就採用了follow-the-satoshi的方式進行出塊者選擇，其隨機數的生成使用了多方計算、門限秘密分享等多種密碼學技術，保證了隨機源的安全性，但在出塊者選擇的匿名性上還沒有實現。
但就隨機數生成而言，另一種方式就是使用鏈上的某段歷史資料的hash值，其中以Algorand為代表，將之前某個區塊的資料和當前區塊高度進行混合運算。
Hash值作為隨機數，算是一個較好的偽隨機源，但仍有被刻意控制的風險。關於隨機數的生成和相關性質這裡不再過多論述，感興趣的讀者可以參考上一篇解讀文章。
Galaxy ULS 演算法原理流程
最後回到我們的主題，Wanchain星系共識的出塊者選擇演算法——ULS演算法。ULS代表的是unique leader selection，即唯一出塊者選擇。該演算法在設計之初就考慮到了公平性、可驗證性和匿名性，採用了秘密分享、零知識證明等多種密碼學手段，實現了固定時間視窗內的唯一合法出塊者的匿名選擇，在保證鏈安全性的基礎上，儘量降低短分叉機率，提升共識效率。
下面我們就形象化介紹星系共識ULS演算法的整體原理流程。
EL星群選擇
EL星群節點是執行ULS演算法的主體，我們就從EL星群的來源說起。在星系共識的第一篇解讀中有簡短介紹，這裡我們再進行一次詳細說明。
在PoS協議中，話語權由權益持有量決定，而我們將這一對應關係在EL星群的選擇過程中進行實現。基於Wanchain共識合約中當前Committee的質押狀態，可計算每個節點的權益值和其權益比例，利用Random Beacon提供的隨機數，執行follow-the-stake-ratio演算法，類似於follow-the-satoshi的過程。
形象地說，就是Committee中節點按照其權益比例劃分了一塊鐘錶的錶盤，每個節點擁有一段與其權益佔比相同的時間窗格。隨機數就是撥動時間指標的上帝之手，指標落到哪個時間窗格，此窗格的擁有者就被選入EL星群，每輪選擇獨立進行，某一節點有可能被多次選入，所以最後EL星群有可能是一個多重集，選出的EL星群將肩負起執行ULS演算法的責任。
秘密訊息序列（Secret Message Array）生成
EL星群被選擇組建之後，需要先進行一次鏈上的通訊協商。這一過程是為了在星群內部生成一個秘密訊息序列，用於後續出塊權分配，是我們實現匿名性的關鍵一步。
為保證秘密訊息序列不會被某些惡意節點控制，影響後續演算法執行，我們將這一過程拆分成兩個階段，也就是SMA1和SMA2。
在SMA1階段，星群中每個節點選擇一個隨機數，將其利用自身公鑰加密後傳送到鏈上，完成對隨機數選擇的承諾，保證任何節點選定的隨機數在後續階段不可更改。
在SMA2階段，星群中每個節點將自己選擇的隨機數用所有節點（包括自身）的公鑰加密傳送到鏈上，同時提供協調性證明（DLEQ proof）。對照在SMA1階段利用自身公鑰加密的資料，就可確保隨機數並未更改，同時協調性證明保證了所有公鑰加密的都是同一個隨機數。
這一階段完成後，所有EL星群節點都可以自行解密，得到隨機資料序列，也就是我們的秘密訊息序列，準備執行出塊權分配演算法。
EL星群節點排序
秘密訊息序列生成後，隨機數進行更新，新產生的隨機數將作為種子對EL星群節點進行排序。具體方式就是將星群節點公鑰與隨機數接續進行hash運算，基於運算結果進行升序排列，這一排序結果將用於後續出塊權分配。
顯然，排序是在秘密訊息序列後基於新隨機數進行的，任何節點無法影響，完全是隨機的排序結果。
出塊權分配
在上述三項工作完成後，就可以為EL星群節點進行出塊權分配。
如前所述，一組EL星群負責一個epoch內區塊的生成，那麼這個epoch內每個slot的出塊權如何決定呢？首先將當前隨機數和epoch編號和slot編號進行hash運算，運算結果取EL星群節點數量的模結果，如hash值是2019，目前EL星群節點數量50，取模結果就是19，那麼EL星群節點排序中的第19位即被選為合法出塊者，獲得出塊權。
這一選擇過程是等概率進行的，結合EL星群節點選擇時的按權益比例進行，確保了出塊者選擇是按權益持有量合理進行的，確保了公平性。合法出塊者在提出區塊時需要提供合法性憑證，這一憑證可被公開驗證，確保出塊合法性的可驗證性。
合法出塊者選擇中使用了秘密訊息序列，而這一訊息序列只在EL星群內部共享，其他節點不可知，就保證了選擇過程的匿名性。由此可見，ULS演算法的是全面考慮了公平性、可驗證性和匿名性的創新性設計，將對保證鏈的安全性和活性起到重要作用。
以上簡單介紹了星系共識的出塊者選擇演算法——ULS演算法，詳細內容在星系共識論文中有著具體的描述。在後續的星系共識探索中，我們會再深入介紹星系共識設計中其他的精彩內容，敬請期待。
