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