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

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

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

隨機性的作用：

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

區(qū)塊鏈是幫助多方在全球?qū)用嫔暇湍撤N程度的更新達成共識的完美例子。更新通常按照回合的方式完成，每個回合是一個周期性的離散時間段。

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

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

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

什么是理想的隨機源：

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

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

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

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

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

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

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

不可篡改隨機源的重要性：

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

理想的委員會選舉方案須具備以下兩點：

1.不可篡改

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

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

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

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

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

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

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

Tendermint

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

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

Algorand

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

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

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

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

Dfinity：

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

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

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

Thunderella：

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

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

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

Casper FFG：

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

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

如果在回退機制中不具有隨機性，這似乎是比隨機性可預測或可偏差更嚴重的問題，因為那樣你不再需要1/3的惡意節(jié)點才能中止協(xié)議，而是1個人就足夠。只需要滿足，那個人驗證者當前是提議者，且下一輪的種子已經(jīng)公布，即可1個人中止協(xié)議。

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