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