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

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

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

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

隨機(jī)性的作用：

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

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

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

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

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

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

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

PoS協(xié)議中用于選擇委員會(huì)成員的理想隨機(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)下所有的委員會(huì)成員選舉協(xié)議，結(jié)論是沒(méi)有一個(gè)協(xié)議能同時(shí)實(shí)現(xiàn)高性能與不可篡改。我們的看法是，鑒于上述權(quán)衡，區(qū)塊鏈共識(shí)協(xié)議應(yīng)選擇一個(gè)始終有輸出的隨機(jī)源，而不是單單產(chǎn)生無(wú)篡改輸出的隨機(jī)源。這是因?yàn)閰^(qū)塊鏈協(xié)議需要確保鏈持續(xù)增長(zhǎng)且不能讓隨機(jī)源成為限制發(fā)展的因素。即使對(duì)于一致性協(xié)議，隨機(jī)源也不應(yīng)該是限制區(qū)塊鏈發(fā)展的原因?？傊?，隨機(jī)源應(yīng)該為協(xié)議減輕負(fù)擔(dān)，使協(xié)議能夠?qū)Ｗ⒂跍p輕其他攻擊，如針對(duì)委員會(huì)小組的DoS攻擊。

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

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

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

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

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

1.不可篡改

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

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

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

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

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

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

下面我們將詳細(xì)介紹各種隨機(jī)性生成機(jī)制。以下內(nèi)容基于我們?cè)凇短娲沧R(shí)協(xié)議的元分析》中分析的區(qū)塊鏈協(xié)議：

Tendermint

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

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

Algorand

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

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

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

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

Dfinity：

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

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

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

Thunderella：

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

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

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

Casper FFG：

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

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

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

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