隨機數的生成在計算中一直很重要。儘管本地和雲端計算已經有了可靠的偽隨機數生成器(PRNG)，但帶來了新的挑戰。總的來說，區塊鏈和Web 3的目標之一是網路中的計算機不需要彼此信任。從基本的意義上說，網路中的計算機在沒有相互信任的情況下執行的方式是讓多臺計算機執行相同的軟體，並且只有在某些多數(通常但不總是1/2或2/3，出於超出本文範圍的原因)同意執行的結果的情況下，才接受結果。對於更新帳戶餘額這樣的程式來說，這並不太難。從賬戶a的餘額中減去一個數字，再加上相同的數字減去賬戶b的交易費用就可以了。但如果存在隨機性呢?為什麼這很重要?1. 協議: 大多數權益證明演算法使用隨機函式來選擇下一個驗證器。如果隨機性是可預測的或可偏置的(稍後會詳細討論)，則驗證器集可能會損壞。2. 應用: 幾乎所有的應用(遊戲、投票(候選順序)等)都使用隨機數生成，使用者不能依賴有偏見的應用。首先，簡單介紹偽隨機數的產生。雖然有許多演算法，但大多數PRNG都是以“種子”開始的——一個基於某種值的0和1選擇的序列，例如，如何在螢幕上移動滑鼠。PRNG將種子作為一個特殊曲線上的起始點，而裡面的演算法會繞著曲線彈跳，輸出一系列確定性的但看起來是隨機的數字（即根據最後的n個值的知識，除了曲線的概率分佈函式外，沒有辦法可靠地預測n+1值）。本文將不討論特定的曲線或演算法，而是重點討論隨機數生成的期望屬性、區塊鏈的特定挑戰以及計算隨機數的最佳時間和位置。我們想要滿足兩個性質的隨機性:不可預測——被動的對手無法透過觀察系統提前預測結果。不可偏頗——積極的對手不能透過操縱或隱瞞結果來偏頗系統。因為計算機不能生成真正的隨機數，我們要麼需要一種方法來同意PRNG種子數，要麼需要某種外部形式值來滿足不可預測性和不可偏性。已經使用的一種方法是使用雜湊函式的輸出。它們是確定的，但是在實際執行之前，無法判斷輸出是基於輸入的。為什麼我們不同意使用當前或未來塊頭的雜湊值中的一些位作為隨機數呢?假設你進行了拋硬幣遊戲。您可以只取塊頭雜湊的最小有效位(LSB)，然後使用0或1作為結果。既然所有的電力都花在雜湊值上了，為什麼不充分利用雜湊值呢?但是，如何讓塊雜湊值生成器釋出這個塊呢?在工作證明區塊鏈中，釋出有效塊的動機是塊獎勵。例如，如果雜湊的LSB是1，那麼塊生成器將贏得1000美元，但是他的有效塊以0結束，而當前塊的獎勵等於300美元。在這種情況下，他可以選擇不傳播這個塊，因為如果他讓另一個礦商找到這個塊，那麼期望值就是500美元。因此，在這裡，挖掘人員贏得賭注的概率大於50%(即從他的網路雜湊功率百分比到1的跨度的50%)。這可能只會產生50.001%的最終概率，但在高頻交易和其他概率活動中，這種規模的優勢可以比競爭對手帶來數百萬美元的利潤(我要進一步說明，任何與協商共識意見有關的資料都應專門用於協商共識意見。工作證明經常被批評為“浪費”能量，一些解決方案是將這些CPU週期用於雙重且通常是利他的目的，例如protein folding。浪費的能量實際上是保證鏈安全的因素:如果protein folding突然變得有價值，那麼鏈安全將是第二優先考慮的問題。一旦您將其他激勵措施(如將應用程式的輸出引入協商共識引數)引入，其中一個(協商共識或應用程式)將被操縱。我們的第一個目標(不可預測性)是一個更容易實現的目標，並且已經在分散式計算中得到了解決。多玩家遊戲就是這樣一種應用:你希望遊戲具有不可預測性，但它需要在許多本地機器上執行，並且遊戲的整體狀態需要在參與者之間保持一致。第二種比較困難，因為你怎麼能強迫別人說出他們不喜歡的結果呢?理想情況下，我們應該有一個可驗證的PRNG(我們假設PRNG是不可預測的)。可驗證函式的計算時間和驗證時間分別為p和np。這本質上意味著計算解決方案可能是高度密集的，但是驗證它是否正確是很容易的。一個很好的應用是驗證器選擇方案，每個人都檢查她是否是驗證器，如果是，她就可以計算並提出一個塊。每個人都可以檢查自己的驗證器狀態並驗證實際驗證器的合法性，這比任何人從頭開始計算驗證器是誰都要快(並在驗證器提出塊之前嘗試賄賂或攻擊驗證器)。
最近，Dan Boneh在一篇關於可驗證延遲函式的論文中提出瞭解決這個問題的方法。VDF提出了一些只能在單個CPU執行緒上計算的函式(通常基於多次平方數)，以防止擁有更多CPU的對手使用並行處理來計算解決方案。使用nsteps進行計算的VDF的解決方案可以在log(n)步驟中驗證，因此誠實的節點可以比對手計算新解決方案的速度更快地驗證解決方案是正確的。Boneh關於VDF的論文直到2018年才發表，甚至他們也承認他們的示例函式需要改進。這是最前沿的工作，我們可以期待許多進步。解決第二個特徵(不可偏性)是困難的，因為您不能強迫某人執行計算或顯示結果。目前最主要的方法是提交公開方案。我們的目標是公開地就PRNG種子達成一致，這樣就沒有人可以透過秘密地改變種子或拒絕傳播解決方案來對結果產生偏見。首先，每個人都同意使用偽隨機函式。稍後，很容易驗證每個人都使用了正確的函式，因為我們都可以自己執行函式並驗證結果。現在我們需要同意使用什麼種子,但是我們不希望任何人提前知道種子。舉個例子，讓我們做一個有三方參與的提交-顯示方案:應用程式所有者(例如線上賭博站點)、使用者和執行計算的節點。每一方都能產生一顆種子，但不會透露出來。相反，每一方都顯示了種子的雜湊值。此時，每一方都有自己的種子和另一方種子的雜湊值。接下來，每個人都展示他或她真正的種子。偽隨機函式的最終種子是 S = S1 XOR S2 XOR S3如果你是S3，你接收S1和S2，你現在可以建立一個新的S3 '，它可以翻轉任何需要的位來得到你想要的最終種子。但是您已經傳送了S3的雜湊值，如果您嘗試在事後更改S3，那麼所有人都會知道!每個人都致力於在知道其他種子之前建立的種子，即使一方不透露計算結果，其他人也有必要的資訊來計算函式輸出並達成一致。委員會披露方案仍然有一個缺陷:最後一個披露的人可以比其他人先看到最終結果，如果結果不好就決定不披露。原則上，有兩種方法可以解決這個問題:技術上的和經濟上的。例如，一個技術解決方案可以使用一個智慧合約來儲存單個種子，然後在雙方確認各自收到了每個種子的雜湊值後顯示所有種子。從經濟上講，你可以對那些不公開身份的進行懲罰。這都是相當高的水平，這仍然是一個開放的問題;新的解決方案可能有弱點。隨機性和決定論是對立的，因此說服人們相信由他們不信任的人產生的隨機數將是分散計算中一個不斷髮展的挑戰。[1]在集中式計算中，我們依靠監管機構和國家來懲罰不公平的行為，但我們的目標是透過計算來完成這一任務，因為攻擊要麼是不可能的，要麼代價高昂。[2]一些應用程式實際上是這樣做的，不要使用它們![3]人類可能會糾結於這樣一個問題:“300美元肯定比1000美元的50%機會更有價值嗎?”但對於一臺可能押注數千次的電腦來說，答案是顯而易見的。[4]在權益關係證明中攻擊更加容易。更改任何引數都會更改輸出的雜湊值。例如，將時間戳更改1毫秒。現在您需要做的就是賄賂驗證器。 [5]如果將電子遊戲看作分散式狀態機，那麼它就是一個很好的例子。狀態可以由每個角色的座標、狀態、健康狀況、財富、武器收藏等來表示。儘管所有使用者都有不同的硬體和不同的連線速度，但這種狀態需要儘可能接近實時地由所有使用者計算和商定。這或多或少是透過一箇中央遊戲伺服器作為某種管絃樂隊指揮來完成的，以確保每個人都在執行適當的軟體。將狀態設定為帳戶的鍵值儲存，並將導體替換為使用資源證明，這樣基本上就可以利用以太坊了。{6}將一個數多次提升到指數的原因是每一步都依賴於前一步的結果，這在普通代數中不是這樣，但在具有溢位或模運算的固定大小的位陣列中是這樣。[7]XOR本質上是一個開關。0不做任何事情，1切換開關。即0 XOR 0 = 0, 0 XOR 1 = 1, 1 XOR 0 = 1, 1 XOR 1 = 0。假設應用程式將使用前100個隨機數，攻擊者想透過操縱S來獲得優勢。要選擇這個S，攻擊者需嘗試數十億個種子，然後使用前100個輸出最有利的那個。要選擇S3 '，將所需的S與S1 XOR S2進行比較，S3 '在它們一致的地方為0，在它們不一致的地方為1。更多區塊鏈資訊：www.qukuaiwang.com.cn/news
