隨機數(shù)的生成在計算中一直很重要。盡管本地和云計算已經(jīng)有了可靠的偽隨機數(shù)生成器（PRNG），但區(qū)塊鏈帶來了新的挑戰(zhàn)?？偟膩碚f，區(qū)塊鏈和Web 3的目標之一是網(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ù)測的或可偏置的（稍后會詳細討論），則驗證器集可能會損壞。

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

首先，簡單介紹偽隨機數(shù)的產(chǎn)生。雖然有許多算法，但大多數(shù)PRNG都是以“種子”開始的——一個基于某種值的0和1選擇的序列，例如，如何在屏幕上移動鼠標。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í)行之前，無法判斷輸出是基于輸入的。為什么我們不同意使用當前或未來塊頭的哈希值中的一些位作為隨機數(shù)呢？假設(shè)你進行了拋硬幣游戲。您可以只取塊頭哈希的最小有效位（LSB），然后使用0或1作為結(jié)果。既然所有的電力都花在哈希值上了，為什么不充分利用哈希值呢？

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

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

這可能只會產(chǎn)生50.001%的最終概率，但在高頻交易和其他概率活動中，這種規(guī)模的優(yōu)勢可以比競爭對手帶來數(shù)百萬美元的利潤（我要進一步說明，任何與協(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)用程序）將被操縱。

我們的第一個目標（不可預(yù)測性）是一個更容易實現(xiàn)的目標，并且已經(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進行計算的VDF的解決方案可以在log（n）步驟中驗證，因此誠實的節(jié)點可以比對手計算新解決方案的速度更快地驗證解決方案是正確的。

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

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

首先，每個人都同意使用偽隨機函數(shù)。稍后，很容易驗證每個人都使用了正確的函數(shù)，因為我們都可以自己運行函數(shù)并驗證結(jié)果。現(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ù)輸出并達成一致。

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

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

［1］在集中式計算中，我們依靠監(jiān)管機構(gòu)和國家來懲罰不公平的行為，但我們的目標是通過計算來完成這一任務(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)可以由每個角色的坐標、狀態(tài)、健康狀況、財富、武器收藏等來表示。盡管所有用戶都有不同的硬件和不同的連接速度，但這種狀態(tài)需要盡可能接近實時地由所有用戶計算和商定。這或多或少是通過一個中央游戲服務(wù)器作為某種管弦樂隊指揮來完成的，以確保每個人都在運行適當?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進行比較，S3 ‘在它們一致的地方為0，在它們不一致的地方為1。