隨機(jī)性在區(qū)塊鏈中的作用

隨機(jī)事件在我們身邊無處不在。比如，運(yùn)氣、概率和命運(yùn)就與隨機(jī)性密不可分。人類不理解或無法預(yù)測的一切事物往往被歸類為隨機(jī)事件。物理世界中也有許多隨機(jī)事件，比如云的運(yùn)動、粒子和波的軌跡等。然而，盡管它是那么的令人熟悉，人類卻很難將周圍的隨機(jī)性轉(zhuǎn)化為計(jì)算機(jī)可以計(jì)算的東西。

當(dāng)我們談?wù)撚?jì)算機(jī)系統(tǒng)中的隨機(jī)性時，我們指的是偽隨機(jī)性，這是一種對現(xiàn)實(shí)世界隨機(jī)性的模擬產(chǎn)物。不過，這兩種隨機(jī)性很難區(qū)分。我們在這里要討論的是非常強(qiáng)大的模擬性隨機(jī)（偽隨機(jī)）。

隨機(jī)性在隱私技術(shù)和密碼學(xué)中發(fā)揮著重要作用。值得驚嘆的是通過一個隨機(jī)值與一條信息就能提供一種簡單而強(qiáng)大的加密方案。比如對稱密鑰加密技術(shù)，兩方進(jìn)行交流時需要事先共享一個保密密鑰，但即使是進(jìn)行最簡單的交流也需要確保共享密鑰是隨機(jī)的。如果此共享密鑰不隨機(jī)，則任何人都可以通過已知的密碼算法與信息內(nèi)容竊取保密密鑰，加密也就失去了意義。

隨機(jī)性的作用：

利用隨機(jī)性可以在兩個人之間構(gòu)建一個安全的通信渠道，也可以用來確認(rèn)通信雙方的身份。此外，如果同時有很多人想通過有限帶寬的通信渠道彼此通信，則可以使用隨機(jī)性來公平地確定消息傳遞的順序。隨機(jī)性也可以用來幫助一群人或計(jì)算機(jī)達(dá)成一致。隨機(jī)共識協(xié)議就是這樣一個例子。這篇文章將探討隨機(jī)性在區(qū)塊鏈中的作用。

區(qū)塊鏈?zhǔn)菐椭喾皆谌驅(qū)用嫔暇湍撤N程度的更新達(dá)成共識的完美例子。更新通常按照回合的方式完成，每個回合是一個周期性的離散時間段。

一般限制共識的的因素有兩個：吞吐量（在互聯(lián)網(wǎng)上的特定時間段內(nèi)可以發(fā)送的消息數(shù)量上限）以及延遲（消息通過互聯(lián)網(wǎng)發(fā)送所需的時間）。任何區(qū)塊鏈共識協(xié)議的目標(biāo)都是克服上述限制因素達(dá)成共識。在公鏈中，數(shù)千個節(jié)點(diǎn)參與維護(hù)區(qū)塊鏈，如果每個節(jié)點(diǎn)都需要向其他所有節(jié)點(diǎn)發(fā)送消息并等待來自所有其他節(jié)點(diǎn)的響應(yīng)，吞吐量與延遲將會讓達(dá)成共識的成本大幅增加。成本高昂是因?yàn)橐粋€回合中傳遞的信息數(shù)量太過龐大，因此為了達(dá)成共識而優(yōu)化網(wǎng)絡(luò)溝通方案的一個方式就是削減信息的數(shù)量。

比特幣達(dá)成共識的方式（中本聰共識）是使用工作量證明（PoW）作為隨機(jī)源確定每輪中哪一個區(qū)塊將被添加到區(qū)塊鏈中，從而減少消息傳遞的開銷。因?yàn)镻oW的計(jì)算非常復(fù)雜，且只有第一個解決難題的人擁有記賬的權(quán)利，再加之多人同時解答出難題的概率極低，PoW機(jī)制就通過這種方式限制了網(wǎng)絡(luò)中的信息數(shù)量。

當(dāng)然，任何試圖取代PoW的共識機(jī)制同樣需要一種方法來限制網(wǎng)絡(luò)傳遞的消息。大多數(shù)的權(quán)益證明協(xié)議（PoS）解決此問題的方法是選擇驗(yàn)證者（即維護(hù)/管理區(qū)塊鏈的節(jié)點(diǎn)），并根據(jù)他們抵押代幣的數(shù)量成立一個委員會小組。然后，該驗(yàn)證小組可以在網(wǎng)絡(luò)限制下合理地來回通信，最終高效地達(dá)成共識。

什么是理想的隨機(jī)源：

當(dāng)然，為了公平地選擇這個委員會小組的成員并且保證沒有人提前知道成員名單，算法必須要得到一些公平且不可篡改的隨機(jī)源。一旦該驗(yàn)證小組在新區(qū)塊上達(dá)成一致，該區(qū)塊就會被廣播給網(wǎng)絡(luò)中的其他所有節(jié)點(diǎn)。

PoS協(xié)議中用于選擇委員會成員的理想隨機(jī)源應(yīng)確保不可被篡改，隨機(jī)性協(xié)議則需要確保以下兩點(diǎn)：

i）隨機(jī)性函數(shù)持續(xù)有輸出

ii）隨機(jī)性函數(shù)的輸出尚未被操縱（注意：我們將在以后的文章中探討如何平衡第一第二點(diǎn)，以及這與網(wǎng)絡(luò)同步模型的關(guān)系）

我們機(jī)械實(shí)驗(yàn)室（Mechanism Labs）分析了當(dāng)下所有的委員會成員選舉協(xié)議，結(jié)論是沒有一個協(xié)議能同時實(shí)現(xiàn)高性能與不可篡改。我們的看法是，鑒于上述權(quán)衡，區(qū)塊鏈共識協(xié)議應(yīng)選擇一個始終有輸出的隨機(jī)源，而不是單單產(chǎn)生無篡改輸出的隨機(jī)源。這是因?yàn)閰^(qū)塊鏈協(xié)議需要確保鏈持續(xù)增長且不能讓隨機(jī)源成為限制發(fā)展的因素。即使對于一致性協(xié)議，隨機(jī)源也不應(yīng)該是限制區(qū)塊鏈發(fā)展的原因?？傊S機(jī)源應(yīng)該為協(xié)議減輕負(fù)擔(dān)，使協(xié)議能夠?qū)Ｗ⒂跍p輕其他攻擊，如針對委員會小組的DoS攻擊。

如果區(qū)塊鏈由于隨機(jī)性函數(shù)停止輸出而完全停止，在社會層面上將需要巨大的協(xié)調(diào)成本來重新啟動區(qū)塊鏈。社群需要花費(fèi)大量的時間通過外部社交媒體平臺就區(qū)塊鏈的形式達(dá)成一致，這樣做的成本與解決DAO黑客的成本相當(dāng)。這種巨額成本也會動搖社區(qū)對區(qū)塊鏈協(xié)議安全性的信心。

另一方面，只要偏差很小并且存在修正偏差的機(jī)制，僅僅幾輪的輕微偏差帶給區(qū)塊鏈安全性的影響也會很小。這是因?yàn)樵诿恳惠喒矃^(qū)塊鏈協(xié)議中給予驗(yàn)證者的協(xié)議內(nèi)獎勵相對較小。但是由于每輪或每個時期（一組輪次）都會選擇新的小組委員，因此在隨機(jī)性函數(shù)中總會存在某個顯著的偏差，讓驗(yàn)證者可以鉆空子賺錢并導(dǎo)致區(qū)塊鏈協(xié)議的安全性降低。此外，主打隨機(jī)性的彩票游戲需要確保隨機(jī)源不被操縱，因?yàn)榧词挂稽c(diǎn)偏差也會改變彩票的贏家。這是因?yàn)榇鄹牟势苯Y(jié)果的效果是巨大的，可以獲得了大量的即時獎勵。因此，這樣的游戲適合僅保證無篡改輸出的隨機(jī)性函數(shù)，即使這意味著隨機(jī)函數(shù)的輸出有時會停止。

不可篡改隨機(jī)源的重要性：

接下來我們將討論在設(shè)計(jì)區(qū)塊鏈協(xié)議時不可篡改的隨機(jī)源的重要性。下文開始，我們提到的協(xié)議默認(rèn)都是不會停止的協(xié)議。

理想的委員會選舉方案須具備以下兩點(diǎn)：

1.不可篡改

2.只在新一輪的開始時顯示隨機(jī)種子。

鑒于上述兩點(diǎn)，隨機(jī)函數(shù)也需要具有不可篡改性。如果隨機(jī)性可以被操縱（并且存在協(xié)議獎勵分配機(jī)制），就會導(dǎo)致獎勵的不公平分配。不公平的獎勵分配意味著一些人獲得更多的獎勵。由于只有那些有抵押的人才能成為驗(yàn)證者，并且投票權(quán)與驗(yàn)證者所擁有的權(quán)益資產(chǎn)成正比，結(jié)果將導(dǎo)致區(qū)塊鏈最終被某些人掌控。

可以說，哪個協(xié)議抗篡改的程度高，它就能在長遠(yuǎn)中獲得維持部分網(wǎng)絡(luò)的權(quán)力。另外，在新一輪回合開始之前公布種子的時間提前量決定了誰可以首先成為網(wǎng)絡(luò)的一部分。因此，上述兩個屬性將決定區(qū)塊鏈的去中心化程度。

用于選擇委員會小組的協(xié)議是每一輪或每幾輪運(yùn)行的，因此從該隨機(jī)函數(shù)的輸出發(fā)布的時間到回合開始的時間是至關(guān)重要的。在此時間范圍內(nèi)，攻擊者可以使用隨機(jī)函數(shù)的輸出來確定哪個驗(yàn)證節(jié)點(diǎn)會被選中。如果這個輸出被隱藏，則試圖攻擊區(qū)塊鏈協(xié)議的攻擊者將無法提前確定驗(yàn)證節(jié)點(diǎn)。此時間范圍的長度決定了協(xié)議可以承受的攻擊者的強(qiáng)度。強(qiáng)大的攻擊者（即具有更多算力和資源攻擊網(wǎng)絡(luò)的人）能夠在很短的時間內(nèi)算出驗(yàn)證節(jié)點(diǎn)。如果攻擊者有足夠的時間，通過委員會成員選擇算法和給定輪次的隨機(jī)種子，就能夠確定驗(yàn)證節(jié)點(diǎn)。確定驗(yàn)證節(jié)點(diǎn)后，攻擊者就能夠?qū)︱?yàn)證節(jié)點(diǎn)發(fā)起DoS攻擊，從而導(dǎo)致空塊以及步驟缺失。

區(qū)塊鏈即使只停止一輪也會有非?？膳碌暮蠊?。想想如果世界上所有人在幾個小時內(nèi)無法進(jìn)行任何交易，比特幣會發(fā)生什么！因此，應(yīng)該選擇抗DoS攻擊的節(jié)點(diǎn)成為驗(yàn)證節(jié)點(diǎn)。另一方面，提前揭示隨機(jī)種子意味著共識協(xié)議只能抵抗較弱的攻擊，這減弱了區(qū)塊鏈的去中心化屬性。

現(xiàn)有隨機(jī)性生成機(jī)制：

下面我們將詳細(xì)介紹各種隨機(jī)性生成機(jī)制。以下內(nèi)容基于我們在《替代共識協(xié)議的元分析》中分析的區(qū)塊鏈協(xié)議：

Tendermint

Tendermint共識機(jī)制使用確定性循環(huán)協(xié)議方案來選擇提議者; 協(xié)議不具有隨機(jī)性，提議者基于投票權(quán)和被選為驗(yàn)證者的次數(shù)確定。攻擊者只能通過綁定或解除綁定權(quán)益對協(xié)議施加影響，因?yàn)檫@是對于協(xié)議的唯一輸入手段。同時，協(xié)議不會在短時間內(nèi)出現(xiàn)偏差，因?yàn)轵?yàn)證者需要很長時間才能綁定（即向系統(tǒng)抵押保證金）或者解除綁定（即從系統(tǒng)中撤回保證金）。不過，在這種機(jī)制下攻擊者可以提早很久作出計(jì)劃，誤導(dǎo)提議者作出錯誤選擇。

使用確定性隨機(jī)算法意味著在每輪投票之前可以公開隨機(jī)種子，不過提議者也會被提前確定。

Algorand

Algorand共識機(jī)制中的隨機(jī)性方案如下：每輪被選為驗(yàn)證者的v會為回合r計(jì)算出種子，公式為《seedr， π 》 ← VRFskv （seedr?1||r），公式中skv是驗(yàn)證者v的密鑰，seedr?1是前一輪的隨機(jī)種子。

r-1輪接受的塊中包含VRF證明π和r輪的種子。如果給定的VRF證明未驗(yàn)證給定的種子，每個人將用加密哈希函數(shù)來計(jì)算新一輪的種子，公式為seedr=H （seedr-1） || r）。這意味著每位驗(yàn)證者必須選擇好自己的密鑰，以確保種子不會發(fā)生偏差。

當(dāng)網(wǎng)絡(luò)不是強(qiáng)同步時，如果攻擊者完全地控制住消息傳遞鏈接，進(jìn)而刪除區(qū)塊提議并強(qiáng)制用戶就空塊達(dá)成一致，就能借此計(jì)算出后續(xù)的隨機(jī)種子。因此，Algorand需要弱同步，即在每個長度為u的周期中，必須存在長度為s 《u的強(qiáng)同步周期，使協(xié)議具有抗偏差性。只要強(qiáng)同步時期s足夠長使得b時間段內(nèi)產(chǎn)生至少一個誠實(shí)的區(qū)塊，選擇密鑰的攻擊者v‘就不能使r輪的隨機(jī)性種子產(chǎn)生偏差。

只有當(dāng)一個塊被提出時，新種子和VRF證明才會去公開地驗(yàn)證它。這確保了提議者和隨機(jī)種子不會提前泄露。這確保Algorand能夠抵御針對提議者的DoS攻擊，并且在擦除與瞬時腐化中保持自適應(yīng)安全性。

Dfinity：

在幾個協(xié)議中，攻擊者通常會通過中止協(xié)議來調(diào)用回退機(jī)制，從而引入偏差。Dfinity使用的閾值方案是抗偏差的，因?yàn)殚撝档倪x擇是為了防止攻擊者通過阻止闕值簽名（闕值簽名是隨機(jī)種子的創(chuàng)造來源）來中止協(xié)議。這使得闕值需要符合以下公式：t∈［f + 1，n - f］ 其中f是攻擊者控制的簽名數(shù)，n是方案中的簽名總數(shù)，t是生成隨機(jī)性所需的簽名閾值。符合條件的閾值確保了攻擊者無法預(yù)測簽名創(chuàng)建的結(jié)果，更無法阻止簽名的創(chuàng)建。

需要注意的是，如果攻擊者擁有任何BLS方案中所有存款的50％以上，就能夠操縱最終的簽名和隨機(jī)性。但是，如果攻擊者真的擁有如此大的股權(quán)占比，他們也會有其他的攻擊選擇，這就打破了Dfinity協(xié)議的基本假設(shè)。

只要有誠實(shí)的驗(yàn)證者前進(jìn)到第r輪，隨機(jī)種子就會被公布。雖然誠實(shí)的驗(yàn)證者到達(dá)r輪與新一輪正式啟動之間的時間差距很小，但這個差距足以讓擁有大量算力的攻擊者找到提議者并發(fā)起DoS攻擊。這就是Dfinity只能承受輕度適應(yīng)性攻擊而不能承受瞬時腐化的原因。

Thunderella：

在哈希函數(shù)實(shí)例化的隨機(jī)預(yù)言方案中，提議者由以下公式確定：H_nonce（pk，q）《Dp 其中H是作為隨機(jī)預(yù)言的哈希函數(shù)，pk是驗(yàn)證者的公鑰，q是給定的時間步驟，而nonce是哈希函數(shù)的熵來源。nonce由前一個塊的提議者決定。設(shè)定難度參數(shù)D_p使得在單個時間步驟中，委員會成員被選為提議者的概率為w。

如果攻擊者提出了一個塊，他就可以影響下一輪哈希函數(shù)的熵來源（nonce），進(jìn)而影響下一個塊中選出的提議者。這種情況下，為了減少隨機(jī)性方案的偏差值，哈希函數(shù)會使用相同的熵來源選擇r輪的提議者而不是下一輪提議者。因此攻擊者很難暴力改變熵來源，也就無從成為下一輪的提議者。不過這種策略僅能保證多項(xiàng)式安全損失，它伴隨著對可預(yù)測的妥協(xié)，這一點(diǎn)將在后文討論?？傊?，該方案導(dǎo)致這個協(xié)議僅能夠承受慢速適應(yīng)攻擊。

在上述算法中，當(dāng)重復(fù)使用相同的熵來源為哈希函數(shù)提供種子時，會導(dǎo)致攻擊者能夠提前預(yù)測出提議者。在一個時期內(nèi)相同的熵來源被重新用作熵，會導(dǎo)致隨機(jī)種子在新一輪的開始之前被泄露。造成的后果為攻擊者可以腐化提議者或者發(fā)起DoS攻擊。

Casper FFG：

Casper FFG計(jì)劃使用的randao方案采用以下算法：

在輪次開始時每個驗(yàn)證者都提交H（H（H（。。。 Sv）））），其中S是驗(yàn)證者提交的種子。R：=R⊕雙層哈希表內(nèi)層的原像。在一個回合中，驗(yàn)證者可以生成或中止一個區(qū)塊。

如果在回退機(jī)制中不具有隨機(jī)性，這似乎是比隨機(jī)性可預(yù)測或可偏差更嚴(yán)重的問題，因?yàn)槟菢幽悴辉傩枰?/3的惡意節(jié)點(diǎn)才能中止協(xié)議，而是1個人就足夠。只需要滿足，那個人驗(yàn)證者當(dāng)前是提議者，且下一輪的種子已經(jīng)公布，即可1個人中止協(xié)議。

隨機(jī)性是密碼學(xué)和區(qū)塊鏈的關(guān)鍵部分。不良的隨機(jī)性方案造成的后果有兩個：1.中止區(qū)塊鏈協(xié)議2.導(dǎo)致中心化，這些后果可能顛覆區(qū)塊鏈的所有安全概念。因此，了解隨機(jī)性在區(qū)塊鏈協(xié)議中的作用有助于真正理解區(qū)塊鏈安全性的本質(zhì)。