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

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

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

為什么這很重要？

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

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

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

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

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

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

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

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

但是，如何讓塊哈希值生成器發(fā)布這個(gè)塊呢？在工作證明區(qū)塊鏈中，發(fā)布有效塊的動(dòng)機(jī)是塊獎(jiǎng)勵(lì)。例如，如果哈希的LSB是1，那么塊生成器將贏得1000美元，但是他的有效塊以0結(jié)束，而當(dāng)前塊的獎(jiǎng)勵(lì)等于300美元。在這種情況下，他可以選擇不傳播這個(gè)塊，因?yàn)槿绻屃硪粋€(gè)礦商找到這個(gè)塊，那么期望值就是500美元。

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

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

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

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

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

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

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

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

首先，每個(gè)人都同意使用偽隨機(jī)函數(shù)。稍后，很容易驗(yàn)證每個(gè)人都使用了正確的函數(shù)，因?yàn)槲覀兌伎梢宰约哼\(yùn)行函數(shù)并驗(yàn)證結(jié)果?，F(xiàn)在我們需要同意使用什么種子，但是我們不希望任何人提前知道種子。

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

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

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

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

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

［1］在集中式計(jì)算中，我們依靠監(jiān)管機(jī)構(gòu)和國家來懲罰不公平的行為，但我們的目標(biāo)是通過計(jì)算來完成這一任務(wù)，因?yàn)楣粢词遣豢赡艿模创鷥r(jià)高昂。

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

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

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

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

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

［7］XOR本質(zhì)上是一個(gè)開關(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個(gè)隨機(jī)數(shù)，攻擊者想通過操縱S來獲得優(yōu)勢(shì)。要選擇這個(gè)S，攻擊者需嘗試數(shù)十億個(gè)種子，然后使用前100個(gè)輸出最有利的那個(gè)。要選擇S3 ’，將所需的S與S1 XOR S2進(jìn)行比較，S3 ‘在它們一致的地方為0，在它們不一致的地方為1。