隨機數(shù)的生成在計算中一直很重要。盡管本地和云計算已經(jīng)有了可靠的偽隨機數(shù)生成器（PRNG），但區(qū)塊鏈帶來了新的挑戰(zhàn)?？偟膩碚f，區(qū)塊鏈和Web 3的目標(biāo)之一是網(wǎng)絡(luò)中的計算機不需要彼此信任。

從基本的意義上說，網(wǎng)絡(luò)中的計算機在沒有相互信任的情況下運行的方式是讓多臺計算機執(zhí)行相同的軟件，并且只有在某些多數(shù)（通常但不總是1/2或2/3，出于超出本文范圍的原因）同意執(zhí)行的結(jié)果的情況下，才接受結(jié)果。

對于更新帳戶余額這樣的程序來說，這并不太難。從賬戶a的余額中減去一個數(shù)字，再加上相同的數(shù)字減去賬戶b的交易費用就可以了。但如果存在隨機性呢？

為什么這很重要？

1. 協(xié)議： 大多數(shù)權(quán)益證明算法使用隨機函數(shù)來選擇下一個驗證器。如果隨機性是可預(yù)測的或可偏置的（稍后會詳細(xì)討論），則驗證器集可能會損壞。

2. 應(yīng)用： 幾乎所有的應(yīng)用（游戲、投票（候選順序）等）都使用隨機數(shù)生成，用戶不能依賴有偏見的應(yīng)用。

首先，簡單介紹偽隨機數(shù)的產(chǎn)生。雖然有許多算法，但大多數(shù)PRNG都是以“種子”開始的——一個基于某種值的0和1選擇的序列，例如，如何在屏幕上移動鼠標(biāo)。PRNG將種子作為一個特殊曲線上的起始點，而里面的算法會繞著曲線彈跳，輸出一系列確定性的但看起來是隨機的數(shù)字（即根據(jù)最后的n個值的知識，除了曲線的概率分布函數(shù)外，沒有辦法可靠地預(yù)測n+1值）。

我們想要滿足兩個性質(zhì)的隨機性：

不可預(yù)測——被動的對手無法通過觀察系統(tǒng)提前預(yù)測結(jié)果。

不可偏頗——積極的對手不能通過操縱或隱瞞結(jié)果來偏頗系統(tǒng)。

因為計算機不能生成真正的隨機數(shù)，我們要么需要一種方法來同意PRNG種子數(shù)，要么需要某種外部形式值來滿足不可預(yù)測性和不可偏性。

已經(jīng)使用的一種方法是使用哈希函數(shù)的輸出。它們是確定的，但是在實際執(zhí)行之前，無法判斷輸出是基于輸入的。為什么我們不同意使用當(dāng)前或未來塊頭的哈希值中的一些位作為隨機數(shù)呢？假設(shè)你進(jìn)行了拋硬幣游戲。您可以只取塊頭哈希的最小有效位（LSB），然后使用0或1作為結(jié)果。既然所有的電力都花在哈希值上了，為什么不充分利用哈希值呢？

但是，如何讓塊哈希值生成器發(fā)布這個塊呢？在工作證明區(qū)塊鏈中，發(fā)布有效塊的動機是塊獎勵。例如，如果哈希的LSB是1，那么塊生成器將贏得1000美元，但是他的有效塊以0結(jié)束，而當(dāng)前塊的獎勵等于300美元。在這種情況下，他可以選擇不傳播這個塊，因為如果他讓另一個礦商找到這個塊，那么期望值就是500美元。

因此，在這里，挖掘人員贏得賭注的概率大于50%（即從他的網(wǎng)絡(luò)哈希功率百分比到1的跨度的50%）。

這可能只會產(chǎn)生50.001%的最終概率，但在高頻交易和其他概率活動中，這種規(guī)模的優(yōu)勢可以比競爭對手帶來數(shù)百萬美元的利潤（我要進(jìn)一步說明，任何與協(xié)商共識意見有關(guān)的資料都應(yīng)專門用于協(xié)商共識意見。工作證明經(jīng)常被批評為“浪費”能量，一些解決方案是將這些CPU周期用于雙重且通常是利他的目的，例如protein folding。浪費的能量實際上是保證鏈安全的因素：如果protein folding突然變得有價值，那么鏈安全將是第二優(yōu)先考慮的問題。一旦您將其他激勵措施（如將應(yīng)用程序的輸出引入?yún)f(xié)商共識參數(shù)）引入，其中一個（協(xié)商共識或應(yīng)用程序）將被操縱。

我們的第一個目標(biāo)（不可預(yù)測性）是一個更容易實現(xiàn)的目標(biāo)，并且已經(jīng)在分布式計算中得到了解決。多玩家游戲就是這樣一種應(yīng)用：你希望游戲具有不可預(yù)測性，但它需要在許多本地機器上執(zhí)行，并且游戲的整體狀態(tài)需要在參與者之間保持一致。第二種比較困難，因為你怎么能強迫別人說出他們不喜歡的結(jié)果呢？

理想情況下，我們應(yīng)該有一個可驗證的PRNG（我們假設(shè)PRNG是不可預(yù)測的）?？沈炞C函數(shù)的計算時間和驗證時間分別為p和np。這本質(zhì)上意味著計算解決方案可能是高度密集的，但是驗證它是否正確是很容易的。

一個很好的應(yīng)用是驗證器選擇方案，每個人都檢查她是否是驗證器，如果是，她就可以計算并提出一個塊。每個人都可以檢查自己的驗證器狀態(tài)并驗證實際驗證器的合法性，這比任何人從頭開始計算驗證器是誰都要快（并在驗證器提出塊之前嘗試賄賂或攻擊驗證器）。

最近，Dan Boneh在一篇關(guān)于可驗證延遲函數(shù)的論文中提出了解決這個問題的方法。VDF提出了一些只能在單個CPU線程上計算的函數(shù)（通常基于多次平方數(shù)），以防止擁有更多CPU的對手使用并行處理來計算解決方案。使用nsteps進(jìn)行計算的VDF的解決方案可以在log（n）步驟中驗證，因此誠實的節(jié)點可以比對手計算新解決方案的速度更快地驗證解決方案是正確的。

Boneh關(guān)于VDF的論文直到2018年才發(fā)表，甚至他們也承認(rèn)他們的示例函數(shù)需要改進(jìn)。這是最前沿的工作，我們可以期待許多進(jìn)步。

解決第二個特征（不可偏性）是困難的，因為您不能強迫某人執(zhí)行計算或顯示結(jié)果。目前最主要的方法是提交公開方案。我們的目標(biāo)是公開地就PRNG種子達(dá)成一致，這樣就沒有人可以通過秘密地改變種子或拒絕傳播解決方案來對結(jié)果產(chǎn)生偏見。

首先，每個人都同意使用偽隨機函數(shù)。稍后，很容易驗證每個人都使用了正確的函數(shù)，因為我們都可以自己運行函數(shù)并驗證結(jié)果?，F(xiàn)在我們需要同意使用什么種子，但是我們不希望任何人提前知道種子。

舉個例子，讓我們做一個有三方參與的提交-顯示方案：應(yīng)用程序所有者（例如在線賭博站點）、用戶和執(zhí)行計算的節(jié)點。每一方都能產(chǎn)生一顆種子，但不會透露出來。相反，每一方都顯示了種子的哈希值。

此時，每一方都有自己的種子和另一方種子的哈希值。接下來，每個人都展示他或她真正的種子。偽隨機函數(shù)的最終種子是 S = S1 XOR S2 XOR S3

如果你是S3，你接收S1和S2，你現(xiàn)在可以創(chuàng)建一個新的S3 ‘，它可以翻轉(zhuǎn)任何需要的位來得到你想要的最終種子。但是您已經(jīng)發(fā)送了S3的哈希值，如果您嘗試在事后更改S3，那么所有人都會知道！每個人都致力于在知道其他種子之前創(chuàng)建的種子，即使一方不透露計算結(jié)果，其他人也有必要的信息來計算函數(shù)輸出并達(dá)成一致。

委員會披露方案仍然有一個缺陷：最后一個披露的人可以比其他人先看到最終結(jié)果，如果結(jié)果不好就決定不披露。原則上，有兩種方法可以解決這個問題：技術(shù)上的和經(jīng)濟上的。例如，一個技術(shù)解決方案可以使用一個智能合約來保存單個種子，然后在雙方確認(rèn)各自收到了每個種子的哈希值后顯示所有種子。從經(jīng)濟上講，你可以對那些不公開身份的進(jìn)行懲罰。

這都是相當(dāng)高的水平，這仍然是一個開放的問題;新的解決方案可能有弱點。隨機性和決定論是對立的，因此說服人們相信由他們不信任的人產(chǎn)生的隨機數(shù)將是分散計算中一個不斷發(fā)展的挑戰(zhàn)。

［1］在集中式計算中，我們依靠監(jiān)管機構(gòu)和國家來懲罰不公平的行為，但我們的目標(biāo)是通過計算來完成這一任務(wù)，因為攻擊要么是不可能的，要么代價高昂。

［2］一些應(yīng)用程序?qū)嶋H上是這樣做的，不要使用它們！

［3］人類可能會糾結(jié)于這樣一個問題：“300美元肯定比1000美元的50%機會更有價值嗎？”但對于一臺可能押注數(shù)千次的電腦來說，答案是顯而易見的。

［4］在權(quán)益關(guān)系證明中攻擊更加容易。更改任何參數(shù)都會更改輸出的哈希值。例如，將時間戳更改1毫秒?，F(xiàn)在您需要做的就是賄賂驗證器。

［5］如果將電子游戲看作分布式狀態(tài)機，那么它就是一個很好的例子。狀態(tài)可以由每個角色的坐標(biāo)、狀態(tài)、健康狀況、財富、武器收藏等來表示。盡管所有用戶都有不同的硬件和不同的連接速度，但這種狀態(tài)需要盡可能接近實時地由所有用戶計算和商定。這或多或少是通過一個中央游戲服務(wù)器作為某種管弦樂隊指揮來完成的，以確保每個人都在運行適當(dāng)?shù)能浖?。將狀態(tài)設(shè)置為帳戶的鍵值存儲，并將導(dǎo)體替換為使用資源證明，這樣基本上就可以利用以太坊了。

{6}將一個數(shù)多次提升到指數(shù)的原因是每一步都依賴于前一步的結(jié)果，這在普通代數(shù)中不是這樣，但在具有溢出或模運算的固定大小的位數(shù)組中是這樣。

［7］XOR本質(zhì)上是一個開關(guān)。0不做任何事情，1切換開關(guān)。即0 XOR 0 = 0， 0 XOR 1 = 1， 1 XOR 0 = 1， 1 XOR 1 = 0。假設(shè)應(yīng)用程序?qū)⑹褂们?00個隨機數(shù)，攻擊者想通過操縱S來獲得優(yōu)勢。要選擇這個S，攻擊者需嘗試數(shù)十億個種子，然后使用前100個輸出最有利的那個。要選擇S3 ’，將所需的S與S1 XOR S2進(jìn)行比較，S3 ‘在它們一致的地方為0，在它們不一致的地方為1。