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

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

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

隨機性的作用：

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

區塊鏈是幫助多方在全球層面上就某種程度的更新達成共識的完美例子。更新通常按照回合的方式完成，每個回合是一個周期性的離散時間段。

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

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

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

什么是理想的隨機源：

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

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

i）隨機性函數持續有輸出

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

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

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

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

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

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

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

1.不可篡改

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

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

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

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

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

現有隨機性生成機制：

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

Tendermint

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

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

Algorand

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

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

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

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

Dfinity：

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

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

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

Thunderella：

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

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

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

Casper FFG：

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

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

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

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