星系共識節(jié)點組建成兩大星群 Wanchain出塊者選擇ULS算法

2019-05-25 10:00:21 來源： WanFans

之前，我們介紹了星系共識的整體架構(gòu)和流程以及星系共識的隨機數(shù)生成算法。在共識過程中，節(jié)點會組建成兩大星群——RNP星群和EL星群，前者負(fù)責(zé)

之前，我們介紹了星系共識的整體架構(gòu)和流程以及星系共識的隨機數(shù)生成算法。在共識過程中，節(jié)點會組建成兩大星群——RNP星群和EL星群，前者負(fù)責(zé)隨機數(shù)的生成，在上一篇文章中已進(jìn)行了詳細(xì)而形象化的介紹，后者負(fù)責(zé)打包交易提出區(qū)塊，而這一工作的核心難點就是解決出塊者選擇問題，本文將深入介紹EL星群中出塊者選擇的流程原理和重要作用。

1. 合理出塊者選擇的重要意義

在我們第一篇文章中講述到，在區(qū)塊鏈共識協(xié)議中要解決的兩個核心問題是出塊者選擇(Leader selection)和合法鏈選擇(Chain selection)，無論在哪種共識協(xié)議中，合理的出塊者選擇都是重中之重，我們設(shè)計隨機數(shù)生成算法引入熵的一個關(guān)鍵作用就是要用于出塊者選擇。

合理的出塊者選擇對保證鏈的安全性和活性至關(guān)重要，一個好的出塊者選擇算法是共識健康運行的基石。我們先說說出塊者選擇對鏈安全性的意義，鏈的發(fā)展延長本質(zhì)上就是塊的不斷接續(xù)，而完成打包提出區(qū)塊的就是這些出塊者，他們一方面決定哪些交易寫入?yún)^(qū)塊進(jìn)而上鏈確認(rèn)。

另一方面也通過選擇接入的父區(qū)塊決定著鏈的發(fā)展走向，在網(wǎng)絡(luò)中共識節(jié)點善惡并存的環(huán)境下，一個好的出塊者選擇算法就是要保證誠實節(jié)點能夠獲得更多的出塊權(quán)，進(jìn)而主導(dǎo)鏈的發(fā)展。當(dāng)然，不同的共識協(xié)議在不同的安全假設(shè)之下，出塊者選擇算法的設(shè)計也是不同的。

· 工作量證明(PoW)的安全假設(shè)：50%以上算力安全

在這一安全假設(shè)下，PoW采用hash運算的方式進(jìn)行出塊者選擇，即節(jié)點通過大量hash試算來尋找解決難題的隨機數(shù)據(jù)，也就是挖礦，這一過程中由于hash函數(shù)運行結(jié)果的不可預(yù)測性，任何節(jié)點在hash試算上不存在優(yōu)勢，是純粹算力的競爭，而50%以上安全算力就保證了出塊者中大部分是誠實節(jié)點，進(jìn)而保證了鏈的安全性。

· 類BFT協(xié)議的安全假設(shè)：2/3以上節(jié)點安全

在這一安全假設(shè)下，類BFT協(xié)議通常采用輪流坐莊或概率選擇的方式進(jìn)行出塊者選擇，無論采用哪種方式，都必然能夠保證誠實節(jié)點獲得多數(shù)出塊權(quán)，同時要求共識網(wǎng)絡(luò)中節(jié)點必須對提議的區(qū)塊進(jìn)行投票，只有獲得了2/3以上投票的區(qū)塊才算最終合法區(qū)塊，進(jìn)而保證了鏈的安全性。

· 權(quán)益證明(PoS)的安全假設(shè)：50%以上權(quán)益安全

在這一安全假設(shè)下，PoS協(xié)議通過依據(jù)節(jié)點權(quán)益持有量比例隨機選取出塊者，而這一選擇的關(guān)鍵就在于隨機性的安全性，保證了隨機源的安全就保證了在大量出塊者選擇過程中誠實節(jié)點能夠獲得多數(shù)出塊權(quán)，進(jìn)而主導(dǎo)鏈的發(fā)展，保證了鏈的安全性。

上面通過介紹常見共識協(xié)議在不同安全假設(shè)下出塊者選擇的設(shè)計方法，當(dāng)然也有特殊的混合模式，這里不進(jìn)行詳細(xì)論述。由上可見，合理的出塊者選擇對保證鏈的安全是極其重要的，我們可以用一個簡單的反向例子來直觀理解，如果在比特幣挖礦中，某個惡意節(jié)點找到了挖礦的竅門進(jìn)而獲得了半數(shù)以上的出塊權(quán)，那么他就可以任意的重構(gòu)鏈來實現(xiàn)雙花等攻擊，任何一筆交易都將不再可信，這將是對比特幣生態(tài)系統(tǒng)的毀滅性打擊。

我們再來簡單說說出塊者選擇對保證鏈活性的重要意義。對于活性的定義在不同的解讀文章中都有論述參考，我們簡而言之，就是鏈可以持續(xù)穩(wěn)定的發(fā)展延長，有效合法的交易經(jīng)過一段時間可以得到確認(rèn)。出塊者本就擔(dān)負(fù)著鏈發(fā)展建設(shè)的重任，很顯然他們就是保證鏈活性的主體，有很多共識模型(如Snow White)對于如何保證鏈活性都有深入的研究和探索。

總體來說，要保證鏈活性，需要解決兩個問題：

一是保證出塊者活性，被選中的出塊者要是活躍的，積極參與共識過程的，而不能是離線或者休眠狀態(tài)，進(jìn)而導(dǎo)致大量區(qū)塊的缺失，影響鏈的正常發(fā)展;

二是保證節(jié)點間數(shù)據(jù)一致性，誠實節(jié)點必然能夠接收到有效合法交易，并誠實的將其打包進(jìn)入?yún)^(qū)塊上鏈確認(rèn)。加上上面對安全性的論述就能保證鏈的活性。而出塊者的活性就要由出塊者選擇來保證，這一選擇是一個廣義的概念，并不一定狹義的體現(xiàn)在具體選擇算法之中，而是在整體的設(shè)計理念里加以考慮，Wanchain的星系共識中對此進(jìn)行了著重思考，并通過權(quán)益概念的全新定義、委托機制的設(shè)計和獎懲機制的刺激妥善解決，我們在此不做詳細(xì)說明，后續(xù)解讀文章將具體解釋。

2. 出塊者選擇算法需要考慮的幾個問題

上面介紹了出塊者選擇算法的重要性，那在設(shè)計一個出塊者選擇算法時應(yīng)該重點考慮哪些問題呢，或者哪些性質(zhì)才是評定一個出塊者選擇算法好壞的衡量標(biāo)準(zhǔn)呢?

1.公平性：出塊權(quán)是依據(jù)共識節(jié)點資質(zhì)均衡分配的。例如PoW中算力越高，獲得出塊權(quán)的機會越大，而PoS中權(quán)益持有量越大，獲得出塊權(quán)的機會越大。這是一個很自然合理的性質(zhì)，但它的外延很廣，出塊者選擇就像博彩，想要實現(xiàn)真正的公平性也需要規(guī)避很多問題。

我們以一個例子來說明：假設(shè)A和B是兩個共識節(jié)點，通過擲骰子的方式?jīng)Q定誰是出塊者，點數(shù)為奇數(shù)則A獲得出塊權(quán)，為偶數(shù)則B獲得出塊權(quán)，公平條件下，骰子是被“上帝”擲出，A和B的機會各一半，而如果A獲得了擲骰子的權(quán)利，那么公平性就被打破了，他可以多次試驗甚至直接擺出奇數(shù)點數(shù)來霸占出塊權(quán)，進(jìn)而獨自決定鏈的發(fā)展甚至肆意進(jìn)行攻擊，這是十分可怕的。

2.可驗證性：出塊權(quán)的合法性是可以被公開驗證的。例如PoW中區(qū)塊頭hash值小于難度值可以被全網(wǎng)運算驗證。這條性質(zhì)是顯而易見的必然要求，區(qū)塊鏈作為去中心化的系統(tǒng)，其運行必然是接受全網(wǎng)監(jiān)督認(rèn)可的，區(qū)塊的合法性驗證是基本要求之一，而區(qū)塊合法性除了交易合法性和結(jié)構(gòu)的合法性外，出塊者的合法性也是必須要被驗證的一點，所以任何的出塊者選擇算法都必須保證出塊權(quán)的歸屬是可以被正確驗證的。

3.匿名性：出塊者通過匿名方式隱私參與共識。這條性質(zhì)并不是必然要求，之所以提出是因為匿名性可以解決共識中可能出現(xiàn)的安全風(fēng)險，如腐蝕攻擊。具體來說，如果出塊者在其出塊權(quán)歸屬時間之間被全網(wǎng)所知，那么惡意節(jié)點有可能通過賄賂等方式將其腐蝕，把原本的誠實節(jié)點變成惡意節(jié)點，進(jìn)而進(jìn)行攻擊，甚至直接進(jìn)行網(wǎng)絡(luò)攻擊導(dǎo)致出塊者掉線，這就增強了惡意節(jié)點的攻擊能力或削減了誠實節(jié)點獲得的出塊權(quán)，所以實現(xiàn)匿名性對于共識協(xié)議來說也是一個需要考慮的問題，很多項目(如Dfinity、Algorand)大多采用VRF算法來實現(xiàn)匿名性，但VRF也存在其自身的缺陷和弊端，現(xiàn)在也有項目(如Ouroboros Crypsinous)提出使用零知識證明進(jìn)行匿名共識，但還沒有具體實現(xiàn)。

3. 常見的出塊者選擇算法

介紹過出塊者選擇算法的重要意義和衡量標(biāo)準(zhǔn)，我們簡單列舉三個典型的算法來具體了解一下當(dāng)前常用的出塊者選擇方式：

· 算力競爭

算力競爭的方式是區(qū)塊鏈系統(tǒng)里最早使用的出塊者選擇算法，最典型的就是比特幣系統(tǒng)，是比較簡單粗暴又直接有效的方式。共識節(jié)點打包交易后，通過不斷調(diào)整區(qū)塊頭中的隨機數(shù)來反復(fù)運算區(qū)塊頭的hash值，當(dāng)hash值小于當(dāng)前區(qū)塊要求的難度值時就形成了符合要求的合法區(qū)塊，此時就獲得了出塊權(quán)，成為一名合法的出塊者，也就是完成了整個挖礦過程。

這種方式的好處就是對于所有參與節(jié)點都是公平的，任何節(jié)點不會在hash運算上取得優(yōu)勢，只要總體算力超過一半是安全的，那么鏈就是安全的。同時，這種方式在同一區(qū)塊高度可能存在多個合法區(qū)塊和合法出塊者，會出現(xiàn)短暫分叉，這也是比特幣系統(tǒng)需要等待確認(rèn)時間的原因。目前來看這種出塊者選擇算法是共識協(xié)議中去中心化程度最高的，當(dāng)然隨著技術(shù)的發(fā)展和研究的深入，挖礦也從最初的CPU挖礦逐步發(fā)展到GPU、ASIC挖礦，算力增長迅速，很多項目為抵抗芯片挖礦通過增加存儲要求設(shè)計了新的共識協(xié)議，如Zcash的Equihash。

· Verifiable Random Function(VRF)

VRF用于出塊者選擇算法是為了解決匿名性而提出，具體方式是先設(shè)置一個合理的閾值，節(jié)點利用自身的私鑰對某一隨機數(shù)據(jù)進(jìn)行運算(如簽名)，得到的結(jié)果小于設(shè)置的閾值則為合法出塊者，獲得出塊權(quán)。這一過程中由于私鑰運算只能節(jié)點自身進(jìn)行，保證了其他節(jié)點不能獲知出塊權(quán)歸屬，而計算結(jié)果如簽名結(jié)果可以被公開驗證，確保了出塊權(quán)合法性可以被驗證，形成了完整的出塊者選擇過程。

顯然，這種方式是概率性的，若想某一區(qū)塊高度可以有盡量多的合法出塊者，就需要盡量提高閾值，反之想要某一區(qū)塊高度可以有盡量少的合法出塊者，就需要盡量降低閾值，這對閾值的設(shè)置就有極高的要求，同時對私鑰運算結(jié)果的分布也要有較好的預(yù)期，這往往是很難做到的，就容易出現(xiàn)某一區(qū)塊高度有大量合法出塊者而形成密集分叉，某一區(qū)塊高度沒有合法出塊者而形成空白，所以VRF算法雖然解決了匿名性問題，但在具體使用中仍然存在難以避免的問題。

· follow-the-satoshi

follow-the-satoshi是PoS中常見的一種出塊者選擇算法，具體方式是將所有的代幣進(jìn)行排序編號，通過一個隨機源產(chǎn)生一個隨機數(shù)，這個隨機數(shù)落到了哪個代幣的編號上，那么這枚代幣的持有者就是合法的出塊者，獲得了出塊權(quán)。這種方式顯然是唯一確定性的，難點就在于如何找到一個安全的隨機源來產(chǎn)生真隨機數(shù)。Cardano項目當(dāng)前就采用了follow-the-satoshi的方式進(jìn)行出塊者選擇，其隨機數(shù)的生成使用了多方計算、門限秘密分享等多種密碼學(xué)技術(shù)，保證了隨機源的安全性，但在出塊者選擇的匿名性上還沒有實現(xiàn)。

但就隨機數(shù)生成而言，另一種方式就是使用鏈上的某段歷史數(shù)據(jù)的hash值，其中以Algorand為代表，將之前某個區(qū)塊的數(shù)據(jù)和當(dāng)前區(qū)塊高度進(jìn)行混合運算hash值作為隨機數(shù)，算是一個較好的偽隨機源，但仍有被刻意控制的風(fēng)險。關(guān)于隨機數(shù)的生成和相關(guān)性質(zhì)這里不再過多論述，感興趣的讀者可以參考上一篇解讀文章。

4. Galaxy ULS算法原理流程

兜兜轉(zhuǎn)轉(zhuǎn)介紹了這么多，最后還是要回到我們的主題，Wanchain星系共識的出塊者選擇算法——ULS算法，ULS代表的是uniqueleader selection，即唯一出塊者選擇，ULS算法在設(shè)計之初就考慮到了公平性、可驗證性和匿名性，采用了秘密分享、零知識證明等多種密碼學(xué)手段，實現(xiàn)了固定時間窗口內(nèi)的唯一合法出塊者的匿名選擇，在保證鏈安全性的基礎(chǔ)上，盡量降低短分叉幾率，提升共識效率，下面我們就形象化介紹星系共識ULS算法的整體原理流程。

a. EL星群選擇

EL星群節(jié)點是運行ULS算法的主體，那我們就從EL星群的來源說起，在星系共識的第一篇解讀中有簡短介紹，這里我們再進(jìn)行一次詳細(xì)說明。在PoS協(xié)議中，話語權(quán)由權(quán)益持有量決定，而我們將這一對應(yīng)關(guān)系在EL星群的選擇過程中進(jìn)行實現(xiàn)。

基于Wanchain共識合約中當(dāng)前Committee的質(zhì)押狀態(tài)，可計算每個節(jié)點的權(quán)益值和其權(quán)益比例，利用RandomBeacon提供的隨機數(shù)，運行follow-the-stake-ratio算法，類似于follow-the-satoshi的過程，形象地說，就是Committee中節(jié)點按照其權(quán)益比例劃分了一塊鐘表的表盤，每個節(jié)點擁有一段與其權(quán)益占比相同的時間窗格，然后隨機數(shù)就是撥動時間指針的上帝之手，指針落到哪個時間窗格，此窗格的擁有者就被選入EL星群，每輪選擇獨立進(jìn)行，某一節(jié)點有可能被多次選入，所以最后EL星群有可能是一個多重集，選出的EL星群將肩負(fù)起運行ULS算法的責(zé)任。

b. 秘密消息序列(Secret MessageArray)生成

EL星群被選擇組建之后，需要先進(jìn)行一次鏈上的通信協(xié)商，這一過程是為了在星群內(nèi)部生成一個秘密消息序列，用于后續(xù)出塊權(quán)分配，是我們實現(xiàn)匿名性的關(guān)鍵一步。為保證秘密消息序列不會被某些惡意節(jié)點控制，進(jìn)而影響到后續(xù)算法運行，我們將這一過程拆分成兩個階段，也就是SMA1和SMA2。

在SMA1階段，星群中每個節(jié)點選擇一個隨機數(shù)，將其利用自身公鑰加密后發(fā)送到鏈上，完成對隨機數(shù)選擇的承諾，保證任何節(jié)點選定的隨機數(shù)在后續(xù)階段不可更改。在SMA2階段，星群中每個節(jié)點將自己選擇的隨機數(shù)用所有節(jié)點(包括自身)的公鑰加密發(fā)送到鏈上，同時提供協(xié)調(diào)性證明(DLEQ proof)，這里對照在SMA1階段利用自身公鑰加密的數(shù)據(jù)就可確保隨機數(shù)并未更改，同時協(xié)調(diào)性證明保證了所有公鑰加密的都是同一個隨機數(shù)。這一階段完成后，所有EL星群節(jié)點都可以自行解密，得到隨機數(shù)據(jù)序列，也就是我們的秘密消息序列，準(zhǔn)備運行出塊權(quán)分配算法。

c. EL星群節(jié)點排序

秘密消息序列生成后，隨機數(shù)進(jìn)行更新，新產(chǎn)生的隨機數(shù)將作為種子對EL星群節(jié)點進(jìn)行排序，具體方式就是將星群節(jié)點公鑰與隨機數(shù)接續(xù)進(jìn)行hash運算，基于運算結(jié)果進(jìn)行升序排列，這一排序結(jié)果將用于后續(xù)出塊權(quán)分配。顯然，排序是在秘密消息序列后基于新隨機數(shù)進(jìn)行的，任何節(jié)點無法影響，完全是隨機的排序結(jié)果。

d.出塊權(quán)分配

在上述三項工作完成后，就可以為EL星群節(jié)點進(jìn)行出塊權(quán)分配。在之前的解讀中我們說過，一組EL星群負(fù)責(zé)一個epoch內(nèi)區(qū)塊的生成，那么這個epoch內(nèi)每個slot的出塊權(quán)如何決定呢?首先將當(dāng)前隨機數(shù)和epoch編號和slot編號進(jìn)行hash運算，運算結(jié)果取EL星群節(jié)點數(shù)量的模結(jié)果，如hash值是2019，目前EL星群節(jié)點數(shù)量50，取模結(jié)果就是19，那么EL星群節(jié)點排序中的第19位即被選為合法出塊者，獲得出塊權(quán)。

這一選擇過程是等概率進(jìn)行的，結(jié)合EL星群節(jié)點選擇時的按權(quán)益比例進(jìn)行，確保了出塊者選擇是按權(quán)益持有量合理進(jìn)行的，確保了公平性;合法出塊者在提出區(qū)塊時需要提供合法性憑證，這一憑證可被公開驗證，確保出塊合法性的可驗證性;合法出塊者選擇中使用了秘密消息序列，而這一消息序列只在EL星群內(nèi)部共享，其他節(jié)點不可知，就保證了選擇過程的匿名性。由此可見，ULS算法的是全面考慮了公平性、可驗證性和匿名性的創(chuàng)新性設(shè)計，將對保證鏈的安全性和活性起到重要的積極作用。