星系共識的隨機(jī)數(shù)生成算法對共識協(xié)議的作用

一、隨機(jī)數(shù)對于區(qū)塊鏈系統(tǒng)的重要作用

在正式談隨機(jī)數(shù)的作用之前，我們需要了解一個概念，那就是“熵”（entropy）。熵對于物理學(xué)領(lǐng)域的朋友一定不會陌生，它是體系混亂程度的度量。在1948年，香農(nóng)（Claude Elwood Shannon）提出了信息熵的概念，去描述信源的不確信度。簡而言之，熵就是不確定性的度量。舉一個簡單的例子：“北京明天的天氣狀況”，可能是晴天，也可能是陰天或者下雨，結(jié)果是不確定的，因此熵為正數(shù)；“地球明天要毀滅”，我們知道地球明天不會毀滅，這是確定的結(jié)果，因此熵為零。

那么熵和區(qū)塊鏈系統(tǒng)有何關(guān)系呢？可以說，熵對于區(qū)塊鏈系統(tǒng)是至關(guān)重要的，是整個系統(tǒng)運(yùn)行的安全保障。以比特幣系統(tǒng)為例，它采取PoW作為共識算法，礦工進(jìn)行大量哈希計算去爭奪出塊權(quán)，任何高度區(qū)塊的出塊者身份都無法提前預(yù)測，這就是熵在比特幣系統(tǒng)中的體現(xiàn)。試想如果熵為0，即每個區(qū)塊的出塊者都是事先確定的或者人為可控，那么必然會出現(xiàn)合謀、分叉等攻擊。因此任何區(qū)塊鏈系統(tǒng)都需要一種安全有效的方式為系統(tǒng)引入熵。基于PoW共識的區(qū)塊鏈系統(tǒng)由于挖礦的隨機(jī)性，以天然的方式為系統(tǒng)引入了熵，然而對于PoS和DPoS共識的區(qū)塊鏈系統(tǒng)，就需要單獨設(shè)計一種方式去引入熵，那就是隨機(jī)數(shù)生成算法?？梢哉f隨機(jī)數(shù)生成算法是設(shè)計共識機(jī)制的主要挑戰(zhàn)之一，也是衡量共識機(jī)制優(yōu)劣的重要標(biāo)準(zhǔn)之一。

二、隨機(jī)數(shù)生成算法優(yōu)劣的衡量標(biāo)準(zhǔn)

既然隨機(jī)數(shù)生成算法這么重要，那么一個好的隨機(jī)數(shù)生成算法應(yīng)該是什么樣子呢？從安全和實用角度而言，它應(yīng)當(dāng)滿足以下六大性質(zhì)：

1. 去中心化（Distributed）：隨機(jī)數(shù)的生成過程要是去中心化的，不能依賴或者借助可信第三方完成。

2. 不可預(yù)測（Unpredictable）：根據(jù)歷史產(chǎn)生的隨機(jī)數(shù)或其他信息無法預(yù)測未來的隨機(jī)數(shù)，這是“隨機(jī)”的基本要求。

3. 無偏性（Unbiased）：任何人都無法通過計算能力或者后發(fā)優(yōu)勢去針對性左右隨機(jī)數(shù)的生成結(jié)果。

4. 均勻分布（Uniformity）：輸出的隨機(jī)數(shù)在其值域內(nèi)是均勻分布的。

5. 保證輸出（Guaranteed Output Delivery）：隨機(jī)數(shù)生成算法的參與者無法通過違背算法的方式使得無法輸出隨機(jī)數(shù)，即必然會有隨機(jī)數(shù)輸出。

6. 公開可驗證（Publicly Verifiable）：沒參與隨機(jī)數(shù)生成的節(jié)點可以以后驗的方式，監(jiān)督協(xié)議的執(zhí)行，驗證隨機(jī)數(shù)是可信和無偏的。

以上六大性質(zhì)對于隨機(jī)數(shù)生成算法至關(guān)重要，違背其中任意一條都可能會導(dǎo)致嚴(yán)重的安全漏洞。據(jù)區(qū)塊鏈安全公司PeckShield披露，EOS上有超過8個競猜項目遭受黑客攻擊并獲利幾百萬美元，嚴(yán)重威脅到了EOS正常生態(tài)秩序，而大部分攻擊成功的原因都與隨機(jī)數(shù)生成漏洞有關(guān)。我們以EOS.WIN項目為例，剖析其隨機(jī)數(shù)算法漏洞根源。

EOS.WIN支持的一個游戲是猜數(shù)字，即用戶輸入某個數(shù)字并壓大或者壓小，然后系統(tǒng)隨機(jī)生成一個數(shù)字，如果用戶壓對大小，則視為中獎并獲取收益。顯然如果能夠控制系統(tǒng)隨機(jī)生成的數(shù)字，就可以左右游戲的結(jié)果。而決定EOS.WIN系統(tǒng)隨機(jī)數(shù)生成的因素為交易哈希ID、成交區(qū)塊高度、成交區(qū)塊前綴、全局開獎序號等。其中成交區(qū)塊高度、成交區(qū)塊前綴雖然是未來某區(qū)塊信息，但是在實施過程系統(tǒng)指定使用當(dāng)前同步到的最新塊信息，因而是確定的；同時，交易哈希ID能夠通過交易內(nèi)action結(jié)合塊信息預(yù)先計算。于是隨機(jī)數(shù)的生成僅依賴于全局開獎序號了。攻擊者利用不斷制造錯誤交易，造成交易狀態(tài)回滾，控制全局開獎序號，從而控制隨機(jī)數(shù)的生成，直到中獎。顯而易見，EOS.WIN的隨機(jī)數(shù)生成算法不滿足上述的第二條性質(zhì)（不可預(yù)測性）和第三條性質(zhì)（無偏性），因此存在漏洞，最終被攻擊者有效攻擊。

三、星系共識隨機(jī)數(shù)生成算法

星系共識中的RNP星群借助承諾、零知識證明、門限秘密分享、門限簽名、橢圓曲線序?qū)Φ榷喾N密碼學(xué)手段，實現(xiàn)了安全高效的隨機(jī)數(shù)生成算法，為整個共識過程安全提供了數(shù)據(jù)基礎(chǔ)。為了能夠形象介紹隨機(jī)數(shù)生成算法的設(shè)計初衷以及其精妙之處，我們將其類比一個簡單的游戲：

紙牌游戲

Alice和Bob玩紙牌游戲，兩人分別秘密選一張撲克牌放在桌面下方，選定之后，同時將紙牌亮在桌面上。如果兩張紙牌的點數(shù)和為偶數(shù)，則Alice獲勝；否則，為Bob獲勝。

這個游戲看似簡單，但是在區(qū)塊鏈上公平的進(jìn)行并不容易，要通過多種手段防止Alice或者Bob作弊。我們接下來一步一步分析：

問題1：Alice和Bob選定之后就不能再更換撲克牌，否則就可以根據(jù)對方撲克牌的點數(shù)決定自己撲克牌點數(shù)，從而獲取勝利。例如，Alice如果可以更換撲克牌，那么只要保證自己所選撲克牌和Bob的撲克牌點數(shù)具有相同奇偶性，那么點數(shù)和總為偶數(shù)，Alice便可以獲勝。

星系共識通過使用“承諾”（Commitment，在配圖中用CM指代Commitment）的方式來保證不會發(fā)生以上作弊行為。“承諾”是一種密碼學(xué)工具，能夠保證在不暴露原始數(shù)據(jù)的基礎(chǔ)上，將其進(jìn)行“證據(jù)留存”，它和明文是一一對應(yīng)的，任何人都可以驗證二者的對應(yīng)關(guān)系是否成立。

結(jié)合我們的例子形象理解就是，Alice和Bob將自己選定撲克牌撕一個小角下來，放在桌面上，這個小角不會暴露撲克的點數(shù)，而且只與撕壞的另一部分才能夠拼接為一張完整的撲克牌。在星系共識協(xié)議中，這是Random Beacon的DKG1（Decentralized Key Generation）階段，每個RNP（Random Number Proposer）節(jié)點計算其所選數(shù)據(jù)的承諾并發(fā)送到鏈上進(jìn)行存證。

問題2：Alice和Bob在選好撲克牌之后，在正式亮牌之前要對自己的撲克牌保密，不能讓對方看到。同時在亮牌時候要證明這張牌確實是之前選定的牌，而不是新選的另一張牌。

星系共識通過公鑰加密算法加密原始數(shù)據(jù)，之后將加密結(jié)果發(fā)送到鏈上，保證了數(shù)據(jù)的機(jī)密性；同時使用零知識證明保證上鏈的加密數(shù)據(jù)與承諾完全匹配。結(jié)合我們的例子形象理解就是，Alice和Bob將被撕過角的牌從桌下取出，扣在桌面上，并且二者都驗證扣在桌面上的牌與之前放在桌上的小角能夠拼接為一張完整的紙牌。在星系共識協(xié)議中，這是Random Beacon的DKG2階段，每個RNP節(jié)點將其給其他節(jié)點的數(shù)據(jù)通過對方公鑰加密之后發(fā)送到鏈上（下圖中S1，S2，Sn為經(jīng)公鑰加密后的鏈上數(shù)據(jù)），同時發(fā)送到鏈上的還有DLEQ-Proof（非交互零知識證明），用于證明加密內(nèi)容與承諾CM是匹配的。這個階段之后，所有節(jié)點都可以從鏈上獲取其他節(jié)點發(fā)送的數(shù)據(jù)，并且在本地解密為明文。

問題3：開牌之后，需要計算兩張撲克牌的點數(shù)。我們要保證Alice和Bob都要計算出同一正確結(jié)果。這個問題看似很荒唐，但是卻非常重要。因為某位玩家可能會裝瘋賣傻，故意計算錯數(shù)字，從而降低游戲進(jìn)行的效率。

星系共識通過使用分布式密鑰生成的算法解決了問題3，即所有RNP節(jié)點通過交互生成一個共同的組密鑰（group secret key），這個密鑰不會完整出現(xiàn)，而是分割為密鑰碎片，每一個RNP節(jié)點掌握一個密鑰碎片。之后，RNP節(jié)點能夠合成組密鑰簽名，而簽名的哈希值即為最終的隨機(jī)數(shù)輸出。由于組密鑰是公共確定的，因此組密鑰簽名也是唯一固定的。結(jié)合我們的例子形象理解就是，Alice和Bob會計算得到共同的點數(shù)。

問題4：此時，無論是Alice還是Bob都不能夠終止游戲的進(jìn)行。也就是一旦游戲開始，就一定要正常結(jié)束，不能因為某一玩家拒絕配合游戲規(guī)則而導(dǎo)致游戲流產(chǎn)。

星系共識通過門限簽名的方式解決了問題4，即只要超過門限值數(shù)量的RNP節(jié)點參與計算，就能夠合成組密鑰簽名。個別RNP節(jié)點拒絕參與計算并不會影響結(jié)果的生成。結(jié)合我們的例子形象理解就是，即使Alice不想亮牌，Bob也有能力將兩張牌亮出，從而完成游戲。

以上過程對應(yīng)于星系共識協(xié)議中Random Beacon的SIGN階段，在這一階段中RNP節(jié)點合作生成組密鑰簽名并計算得到隨機(jī)數(shù)輸出。

現(xiàn)在我們把上述過程梳理一下：1. Alice和Bob撲克牌的點數(shù)之和是二者共同決定的；2. 每一局游戲的點數(shù)和都是獨立的，不存在相互依賴的關(guān)系，因此歷史游戲數(shù)據(jù)沒有預(yù)測作用；3. Alice和Bob都無法提前知道對方的撲克牌點數(shù)，因此沒有后發(fā)優(yōu)勢去左右點數(shù)之和；4. Alice和Bob可以選擇任何一張撲克牌，因此點數(shù)分布是均勻的；5. Alice和Bob都無法中斷游戲的進(jìn)行；6. 任何第三方都可以對游戲過程進(jìn)行審計，因為所有數(shù)據(jù)都在鏈上存證。

由以上分析可知，星系共識的隨機(jī)數(shù)算法滿足前文提到的六大性質(zhì)，是安全高效的隨機(jī)數(shù)生成算法。