本篇文章總結了目前主要的應用在區塊鏈的不可預測隨機數獲取協議，並提煉出它們的設計思想，方法論以及依賴的假設，然後對他們進行比較。本文分爲兩部分：第一部分介紹基本概念，並從零開始構造適用於分佈式系統的隨機數協議核心；第二部分介紹目前主流的應用在區塊鏈項目中的隨機數協議，並分析他們是如何使用第一部分所介紹的某類或者某幾類協議核心。

本文假設讀者已經具有基本的區塊鏈知識，並對以太坊智能合約的基本原理和比特幣共識協議的基本原理有大致的瞭解。

原文標題：《區塊鏈上的隨機性（一）概述與構造》
文章來源：公衆號 NPC 源計劃
作者：邱飛暘

隨機是不確定性，而依賴確定性是人的天性。程序本是確定的，而引入隨機數這個不確定因素之後，帶來了更多的可能性。而隨機數在區塊鏈中則更爲重要。在區塊鏈的透明之下，隨機數生成機制被徹底暴露；而貨幣成爲原生屬性之後，所有人都更有激勵希望去操作隨機的天平導向自己。

在應用層，隨機數決定遊戲規則是否公平；而在協議層，隨機數能夠提升整體的性能，可以決定一條鏈是否可信，對於如 Dfinity、Algorand 等以隨機數爲賣點的項目，甚至決定其生死。

不久之前，全國區塊鏈大賽一等獎作品爲「DnaRand 一個公平的去中心化隨機數基礎設施」，實現在作惡節點不超過一半的情況下提供去中心化、不可操縱、不可預測的隨機數。其設計者即爲本文作者。本文爲 NPC 隨機數專題第一篇《概述與構造》。

隨機性 (Randomness)的獲取是區塊鏈中非常重要的一個課題。這裏的隨機性的獲取包括但不僅限於：如何在智能合約中引入不可預測的隨機數；如何在共識協議中安全地進行隨機抽籤。顯然，上述對於隨機性獲取的問題描述已經說明了爲何這個課題十分重要。而在區塊鏈中獲取隨機數非常困難，這一方面來自於區塊鏈系統的透明性—— 從通常意義上來講，該特性會使得一切算法的輸入，輸出以及算法本身暴露給所有的系統參與者——因此，在密碼學中廣泛使用的僞隨機數發生器不可以被直接以硬編碼的方式或者是智能合約代碼的方式應用在區塊鏈系統中來獲取安全的隨機數，因爲透明性，系統參與者能夠根據代碼預測到隨機數甚至操縱隨機數，從而讓隨機源不「隨機」。另一方面，隨機數獲取協議作爲區塊鏈系統的一個子協議常常與該系統下的其他協議有緊密的關係，如共識協議，這意味着其他協議很有可能會影響隨機數獲取協議的安全性。從而使隨機數獲取協議的設計變得非常複雜，常常需要具體問題具體分析。

隨機性的定義

在日常生活中，我們經常會聽到諸如「隨機選擇」，「僞隨機數」，「隨機模型」，「隨機序列」之類的詞彙，以及「僞隨機數」、「真隨機數」這樣的概念。想要理解這些詞彙和概念，必須要搞清楚隨機是什麼。事實上，與「隨機」相對的是「確定」。因此，我們可以將「隨機」直觀上理解爲「不確定」 —— 無論是隨機數，還是隨機選擇，我們都希望這個數或者選擇的結果從某種程度上來講是不確定的。因此，如果直接給出一個數，而不給出這個數的產生方式，它不能被稱之爲隨機數，比如直接給出一個數字 1，我們不能說 1 是隨機數，但是如果這個 1 是通過擲骰子決定的，則可以說這個 1 是隨機的。當然，這些都是非常直觀而寬泛的理解。更精確地講，「隨機」，或者我們說「隨機數」、「隨機序列」，在不同的領域有不同的定義。在數學上，隨機數的定義和概率論相關；在計算複雜性理論中，使用描述隨機序列的程序長度來定義（即序列越隨機，描述它的程序的長度就越長）；密碼學會結合統計特性和密碼攻擊來描述隨機數。

我們這裏先給出隨機序列的描述性定義，我們可以稱一個序列爲隨機序列，當它滿足：

  • 均勻性：該序列服從均勻分佈；
  • 獨立性：該序列的各個元素相互獨立；
  • 不可預測性：依據該序列的任意片段，不能預測該序列餘下的部分。

展開來講，我們可以先考慮如下問題：

1、考慮一個每一項要麼取 1 要麼取 0 的數列。假設它的每一項均爲 1，它顯然不是隨機序列，因爲違反了均勻性。均勻性要求 0 和 1 出現的概率相同；
2、假設它的每一項都和前一項不相等。比如 「0101010101」，它滿足了均勻性，但是仍然不是隨機序列，因爲違反了獨立性；
3、對於一個滿足獨立性和均勻性的隨機序列。比如從常數 e 的小數點後第 10 位開始依次選取數碼組成序列。這樣的序列在統計上滿足獨立性和均勻性，但是它的序列是可以被預測的。

我們說過，不同的領域對隨機性有不同的定義。比如，在仿真當中我們想要模擬顧客到達的間隔時間，用只滿足前兩條的隨機序列是足夠的。但是在密碼學中，比如生成隨機的密鑰，僅滿足前兩條的隨機序列是不夠的，一個有可能被預測的隨機序列用在密鑰生成中當然是有安全問題的。比如我們用自然對數的底 e 的數碼作爲隨機序列。

e 確實可以被認爲在統計上是均勻分佈和獨立的（儘管沒有完全證明），用來做仿真是足夠的，但是不能用作密碼學中的隨機種子。因爲對手有可能通過一定長度的已知序列猜測到是在使用 e。同理，在抽獎、遊戲當中使用的隨機數也通常是要求不可預測的。鑑於區塊鏈領域中涉及的多是密碼學和遊戲的場景，接下來的內容都是滿足全部三條性質的隨機序列。

隨機序列又可以被分爲真隨機 (True Random)序列和僞隨機 (Pseudorandom)序列。僞隨機序列，顧名思義，就是「不是真的隨機，只是看起來是隨機的」。因此，根據圖靈獎得主姚期智提出的概念，粗略地講，僞隨機序列就是指一個與真隨機序列在計算上不可區分的序列。而真隨機序列，指的是不可被重現的隨機序列，比如通過拋硬幣產生的隨機序列。我們可以看出來，在這樣的定義下，僞隨機序列的統計特性應當和真隨機序列無法區分，也就是說，僞隨機序列同樣是滿足全部三條性質的隨機序列。當然，這樣的定義通常用在計算複雜性理論以及密碼學當中，在其他領域，只滿足前兩條性質的隨機序列也可以被稱作僞隨機序列。

產生隨機序列的發生器叫做隨機數發生器 (Random Number Generator, RNG)。按照產生的序列的性質，我們可以將其分爲真隨機數發生器(True Random Number Generator, TRNG)和僞隨機數發生器 (Pseudorandom Number Generator, PRNG)。此外，還有一種與之正交的分類方法是從隨機數發生器的實現方法來分類，可以將隨機數發生器分爲硬件隨機數發生器和軟件隨機數發生器，它們之間的關係如圖 1 所示

RNG (1).png圖 1：隨機數發生器的分類

真隨機數發生器通常利用一些非確定現象，通過物理手段將其轉換爲真隨機序列。通常的非確定現象包括混沌效應和量子隨機過程。其中混沌效應的特點是目前物理學能夠明確解釋其因果，但是由於結果對於初始值過於敏感，導致無法精確預測其結果。比如，通過收集大氣噪聲而產生的隨機數就是利用混沌效應產生的隨機數的例子。而量子隨機過程則是利用微觀量子態的不確定性，這個不確定性已經被目前物理學理論承認，它能夠保證即使輸入值完全相同，輸出值也是可能完全不同的。比如利用激光器的相位噪聲來生成隨機數。硬件真隨機數發生器，通常使用芯片實現；而軟件真隨機數發生器，通常利用系統自帶的一些非確定現象，譬如硬盤尋道時間、RAM 中的內容或者是用戶的輸入，Linux 系統裏的 /dev/random 就是一種軟件真隨機數發生器，它通過採集機器運行過程中的硬件噪音數據來獲取足夠的隨機性來源，並依此生成隨機數。

而僞隨機數發生器是一段程序，是一種確定性的算法，通常以短的真隨機數作爲輸入，進行擴充，生成更長的和真隨機序列非常接近的隨機數序列。它的輸入被稱作種子 (Seed)。它同樣也有硬件實現和軟件實現。

如何從區塊鏈上取得隨機數

上一節中我們給出了隨機性的一個定義，這樣的定義也將用於本文餘下的部分。並且，我們還給出了僞隨機性以及僞隨機數發生器的概念。在實際應用中，可用於密碼學的僞隨機數發生器有很多並且也已經很成熟了，那麼我們很自然地想到，能否將僞隨機數發生器直接用在區塊鏈，在區塊鏈的共識過程或者應用上面加入隨機性，使得這樣的隨機性滿足我們上面提到的三條性質？

很遺憾的是，答案是否定的。僞隨機數發生器產生的隨機序列的不可預測性的前提是僞隨機數發生器作爲一個黑盒，除了它的輸出，外界無法得知其他一切信息。但是區塊鏈上的一切都是公開透明的，包括使用的僞隨機數發生器及輸入到僞隨機數發生器裏面的種子也是一樣公開透明的。在這樣的情況下，所有傳統的僞隨機數發生器都無法在區塊鏈的環境下產出具有不可預測性的隨機數序列。而至於真隨機數發生器，的確存在將真隨機數發生器的結果通過可驗證的不可篡改的通道引入區塊鏈系統內部，這樣的通道又被稱作 Oracle。以太坊現在常用的隨機數發生器就是通過 Oracle，引入 random.org （random.org 是一個網站，它聲稱提供真隨機數）提供的隨機數。但是這種方法的問題在於，所謂的「真隨機數發生器」往往是中心化的，擁有這樣的硬件或者軟件的人或者組織擁有篡改隨機數發生器結果並且不讓用戶發覺的能力。這對於主打「去中心化」的區塊鏈系統來說，無疑如鯁在喉。

除了僞隨機數發生器和真隨機數發生器，還有一類隨機數發生器會直接利用區塊鏈系統中共識過程所天然產生的隨機性。比如，使用未來某個塊或者之前某個塊的 Hash 值來作爲種子之一生成隨機數（其他的種子可以是用戶的地址、用戶支付的以太幣數量等，但是這些是用戶可控的部分，沒有增加不可預測性的作用）。這種做法也常見於各種區塊鏈博彩類遊戲以及資金盤遊戲當中，但是這樣的隨機數獲取過程有着致命的漏洞——用戶有可能通過仔細選擇交易時間來控制隨機數向有利於自己的方向生成；即使用戶無法控制，礦工也可以控制隨機數的生成，並且這樣的攻擊成立並不需要太多算力的參與。只要最終隨機數牽涉的金額足夠，完全可以使用租用算力或者賄賂礦工的方式進行攻擊。

那麼歸根結底，在區塊鏈這樣的一個系統當中隨機性可以來自哪裏呢？也就是說，通過上面的分析，我們發現，對於如上做法的隨機數發生器，無論規則或者程序設計得如何複雜，它都是確定性的算法。對於一個確定性的算法，算法本身不會對輸出的隨機性有任何的影響，能夠影響最終輸出的隨機性的，只有算法的輸入。因此，在區塊鏈系統當中，我們需要在一個分佈式的，公開透明的環境中去仔細選擇一個有足夠隨機性的輸入。

那麼符合要求的輸入存在嗎？答案是肯定的，這樣的輸入實際上來源於我們對於區塊鏈系統參與者之間不是一個整體的假設。

隨機數生成協議模型

我們現在從最簡單的情況開始去逐步構造一個區塊鏈上可以使用的公平的隨機數發生器。下文所涉及到的在分佈式的環境下的協議都可以轉換爲區塊鏈的環境，因此不對「分佈式」和「區塊鏈」做區分。

「分佈式」和「區塊鏈」的區別

區塊鏈系統屬於分佈式系統，但是分佈式系統不僅僅是區塊鏈系統，還包括點對點文件傳輸系統，分佈式數據庫系統等等。「分佈式」只是對網絡的拓撲結構進行描述，表明網絡不是集中式的，而是分佈的多節點控制的。

爲了更清楚地說明構造分佈式隨機數協議，也叫分佈式隨機數信標 Distributed Randomness Beacon, DRB)，的方法論，我們首先引入一個隨機數協議的抽象模型：

DRB (2).jpg圖 2：隨機數協議的抽象模型

這個模型能夠完整地描述一個分佈式隨機數協議的輸入輸出與其節點之間的關係。如圖 2 所示，假設每個節點地位相同，不做區分，那麼每個節點都會運行同樣的協議。一個分佈式隨機數協議包含三部分的輸入：每個節點 i 自己的輸入 I iself，來自其他節點的輸入 I jinter, j ≠ i 以及一個公開的預先約定好的公共輸入 I common，這三部分輸入每一部分都可以包含多次的輸入。作爲一個分佈式隨機協議，其輸出隨機性的來源只能由輸入提供，我們先不考慮這三部分輸入進入協議的先後順序，那麼我們可以將協議分爲兩類，一類是採用 I self 與 I inter 作爲隨機性來源的協議，另一類是採用 I common 作爲隨機性來源的協議。大家可以發現，這兩類事實上已經涵蓋了所有的隨機性來源的可能，其他類別的協議都可以視爲這兩類協議的組合。文章後面的部分將主要對這兩類協議展開分析。

使用 I self 與 I inter 作爲隨機性來源

下面，我們考慮這樣的一個場景：Alice 和 Bob 在網上湊錢一起買了一張彩票，結果中了神祕的頭獎，令他們喫驚的是，獎品竟然是一隻皮卡丘，如圖 3 所示。但是皮卡丘不可分割，並且由於兩人相隔甚遠無法見面猜拳，所以他們倆決定設計一個對兩個人都公平的隨機數生成協議來確定誰能獲得這隻皮卡丘。

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信圖 3：獎品皮卡丘

v1.0 最簡單的隨機數生成協議

Alice 設計瞭如圖 4 所示的一個協議，這個協議又被稱作 Coin-Tossing Protocol 或是 Coin-Flipping Protocol。協議接收每位參與者的一次輸入，在該場景下是 ξA 和 ξB，輸入的取值只能是 0 或者 1。協議擁有唯一公共輸出 ξ，取值也是 0 或者 1，如果最後 ξ = 0，Alice 獲得皮卡丘；若 ξ = 1，Bob 獲得皮卡丘。而從每一位參與者的角度來講，這個協議接收自己的輸入以及其他運行這個協議的節點的輸入，經過算法運算之後，輸出一個一致的最終結果，其實就是上一節中我們提到的抽象模型中的，利用 I self 與 I inter 作爲隨機性來源的協議。

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信圖 4：Coin-Flipping 或 Coin-Tossing 協議

那麼這樣的協議具體是怎麼做的呢？爲了構造這樣的一個協議，我們需要確定這樣的協議需要滿足什麼樣的性質。考慮到每個人之間的輸入是相互獨立的，這樣的協議需要保證每個人自己的輸入也應當是和輸出相互獨立的，但是他們又共同對輸出做出了一定貢獻。只有這樣，才能確保每個人都無法光憑藉改變自己的選擇來改變輸出。同時，協議也需要保證只要有一個人的輸入是均勻分佈的，那麼結果就是均勻分佈的。現實中滿足這些條件的構造方式有很多，其中一種是異或操作，將兩人的輸入異或之後輸出：在給定 Bob 選 1 的情況下（Alice 不知道），Alice 不管選 0 還是 1，輸出結果都是 0 和 1 各一半的可能性；給定 Bob 選 0 的情況同理。

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信

另一種方法是利用 mod 加法，將兩人的輸入進行模 2 加法之後輸出，也能得到類似的結果。

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信

v2.0 帶有承諾的版本

v1.0 看似解決了我們的問題，實際上它有非常大的漏洞。這個漏洞在於，我們無法保證 Alice 和 Bob 「同時」 輸入。假如 Bob 等 Alice 向協議輸入她的選擇之後再進行選擇，那麼由於協議的交互對於兩人來講是公開的，Bob 可以根據 Alice 的選擇來調整自己的選擇。例如，如果 Alice 的選擇是 0，那 Bob 就輸入 0；如果 Alice 是 1，那他就輸入 1。這樣，無論 Alice 怎麼選擇，Bob 都可以使得異或的結果永遠是 1，就能拿走這隻皮卡丘。

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信圖 5：帶有承諾的 Coin-Tossing 協議

事實上，同時輸入是很難保證的，而爲了防止這種作弊行爲，我們需要保證，協議中的來自其他人的輸入對於參與者來講應該是暫時機密的，不會透露任何他們的選擇的信息。與此相應的，應該多出一個去機密化的過程以計算出協議的輸出。爲了實現這樣的需求，我們需要引入新的機制：承諾 (Commitment)。

如圖 5 所示，該機制包含兩個階段：承諾 (Commit)階段和揭示 (Reveal)階段。在第一個承諾階段，協議參與者不再直接輸入自己的選擇，而是對自己的選擇進行數字簽名，將簽名的結果，我們稱之爲承諾，輸入進協議。例如，Alice 會將她的選擇 ξA 用自己的私鑰 skA 進行簽名，獲得結果 sig skA(ξA) 輸入進協議。當所有參與者的簽名結果均輸入進協議中後，進入第二個揭示階段。該階段所有參與者將第一輪自己的選擇輸入進協議，例如 Alice 會輸入ξ\’A，協議會結合第一個階段的承諾進行驗證，確認輸入的 ξ\’A 和ξA 相等。如果所有的驗證都通過，則輸出最終結果 ξ，最終結果就是我們想要的隨機數。

這樣的協議保證了，在第一個階段裏沒有任何人的選擇會被除自己以外的其他人獲知，並且在第二階段，即使 Bob 先知道了 Alice 揭示出來的選擇值然後在自己揭示之前計算出結果，他也無法改變自己的選擇了，因爲第一個階段的簽名已經做出了「承諾」。這裏，數字簽名能夠保證消息的不可篡改性，不可否認性以及暫時的機密性。如果該協議是運行於區塊鏈之上，由於通常區塊鏈協議都會對交易內容進行數字簽名，那麼我們的協議也可以將使用數字簽名改爲使用 Hash 函數。

v3.0a 使用經濟懲罰

v2.0 的版本在對於兩個人的情況的時候看起來非常公平，但是對於兩人以上的情況，它仍然是有漏洞的。假設 Alice、Bob、Clare 三個人分一隻皮卡丘，其他設定不變，採用 v2.0 協議。這時，Bob 想到了個主意：「在最後的第二階段，我可以在輸入自己的選擇進行揭示之前先依據別人的揭示結果計算出輸出，如果不是對我有利的輸出，我就不進行揭示階段，假裝網線被挖斷了。」

剛纔的協議無法處理這種情況。是重新再來一遍，還是就取剩下兩個人的輸入呢？這兩種方法是都有問題的：如果重新再運行一遍協議，那麼攻擊者就可以利用這種重新運行的機制在每次自己不利的情況下強行使得協議重新運行；如果只取剩下兩個人的輸入，攻擊者同樣可以利用這種機制選擇是否放棄輸入來趨利避害。因此，我們需要有一種機制來保證參與者不得隨意放棄，最簡單的方式就是利用經濟懲罰。如圖 6 所示，當參與者在第一階段承諾的時候，必須要向協議鎖定一個比特幣（也可以是其他的數字貨幣）——如果是在帶有智能合約的區塊鏈的環境，這樣的操作十分容易。如果 Bob 不按時揭示他的選擇 ξB，那麼就會沒收 Bob 的比特幣分給 Alice 和 Clare，然後重啓協議。由於皮卡丘的價值（也許）通常並不會超過一個比特幣，Bob 不會選擇這樣的方式進行作弊。這樣的一個懲罰機制，就是爲了防止這樣的拒絕服務攻擊。

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信圖 6：帶有經濟懲罰的版本

需要注意的是，之所以本節一開始所述的攻擊對只有兩個參與者的協議不奏效，是因爲兩個人的情況下，在僅剩一個人的時候，我們可以直接給出有利於剩下的參與者的結果，而在多於兩個人的情形下，我們仍舊無法保證在剩下的人當中做出選擇。這樣的規則是一種天然的對拒絕服務的參與者的懲罰。

v3.0b 使用門限機制

除了經濟懲罰之外，還有另外一種方式，我們稱之爲門限 (Threshold)機制。門限機制指的是一種協議的某一個指標達到一定閾值就可以執行特定流程的機制。在這裏我們引入門限機制，主要是爲了使得在協議參與人數有缺失的時候仍然能夠給出正常的輸出。門限機制的作用在於增強協議的健壯性，使得它能夠容忍一定程度的拒絕服務攻擊。我們接下來討論的門限機制都是 (t, n) 門限機制，意思就是對於 n 個參與者的協議，只需要 t 個參與者的輸入即可完成協議的輸出，注意這裏的 n 不一定是協議預先規定好的，或者說是協議必須知道的，它也有可能是一個不確定的數字。如果協議必須規定了確切的 n 才能夠保證正確性，那麼這樣的協議只能用於許可環境 (Permissioned Setting)中；如果不需要規定確切的 n，那麼這樣的協議可以被用於非許可環境 (Permissionless Setting)中。如圖 7 和 圖 8 所示，我們使用最基本的 v1.0 版本的 Coin-Tossing 協議，將門限機制的輸出作爲 Coin-Tossing 協議的輸入。這樣的門限機制總的說來有三種。

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信圖 7：Coin Tossing 協議

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信圖 8：帶門限機制的 Coin Tossing 協議

第一種門限機制是將輸入按照某種規則排序之後，簡單地取前 t 個輸入。但是這種方式不抗女巫攻擊 (Sybil Attack)—— 假如 Bob 是黑客帝國的複製人，他複製了一萬個自己，因此 Bob 通過控制這一萬個身份有很大的可能佔有前 t 個輸入，從而控制隨機數的結果。因此，這種門限機制是無法用在沒有抗女巫攻擊機制的環境下 —— 譬如，沒有身份驗證的非許可環境下，但它的優點在於，這樣的機制不需要知道 n 的確切值。

女巫攻擊

簡單來講，指的是一種網絡內的少數節點控制多重身份的攻擊方式。

第二種門限機制是無分發者的祕密分享系列的。這一系列協議均需要每產生一個隨機數輸出都進行一次祕密分享來保證門限機制，屬於有狀態 (Stateful)協議。更直觀地講，比如有 n 個人，假設只需要有 t 個人提交了就能輸出我們想要的隨機數，同時，我們需要 r 個這樣的隨機數。那麼如果採用無分發者的祕密分享系列的門限機制，我們需要這 n 個人相互交互至少 r 輪。另一個侷限是，該方案需要在許可環境下實施，也就是說協議必須知道總人數 n，才能確定合理的門限 t。

這一系列協議包含很多種形式，其中最基本的形式是無分發者的祕密分享 (Secret Sharing)。祕密分享可以將一個祕密字符串分成多個碎片，又稱作份額 (Share)，只有集齊一定數量的碎片才能將該祕密恢復出來。通常，祕密分享需要有一個可信第三方充當分發者將祕密分成祕密碎片然後分發。而無分發者的含義則是祕密分享的過程不需要這樣的分發者，也就是說，更加去中心化了。如圖 9 所示，首先是分發階段，比如說 Bob 把他的選擇 ξB 分成三份：sξBA，sξBB，sξBC, 這三份中的任意兩份都可以恢復出完整的 ξB。上角標代表了這個份額髮送給的人，例如 SCξB 表示該份額髮送給 Clare。每個人都像 Bob 這樣做之後，每個人手上都有 3 份來自包括自己在內的不同的人的份額。例如，Clare 此時手上應該有：sξAC，sξBC，sξCC。此時，每個人再把這些份額拼成份額向量廣播給所有人。例如 Clare 會將份額向量：

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信

廣播給其他兩個人。這樣每個人只要手裏有包括自己在內的兩份這樣的向量就能恢復出 Alice、Bob 和 Clare 三人的選擇，然後就可以算出最終的隨機數，例如 Bob 擁有向量

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信

和

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信

下角標相同上角標不同的任意兩個份額都可以恢復出相應的祕密，例如 SBξB 和 SCξB 可以恢復出 ξB。由於這一點，我們可以得到 [ξA, ξB, ξC]，由此算出最終的結果 ξ。

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信圖 9：無分發者的祕密分享

但是這樣的祕密分享方案是有漏洞的，如果祕密分發者 —— 譬如 Bob —— 在分發份額 SAξB，SBξB，SCξB 的時候，將其中一份份額 SAξB 替換爲其他的一個任意值，那麼收到這個份額的 Alice 在使用該份額進行恢復的時候有可能恢復出錯誤的 ξB。爲了防止這樣的攻擊，我們需要保證使用的祕密分享方案中包含可以驗證祕密份額的步驟。

於是，如圖 10 所示，我們使用無分發者的公開可驗證祕密分享 (Publicly Verifiable Secret Sharing, PVSS) —— 與第一種相比則是在分發階段的時候多了一些額外的數據。這些數據就是「證明」，記作 ∏。「證明」 ∏可以被用來檢驗每個人收到的份額是否和其他人的一致。所有人都會使用這個公開的 ∏ 去驗證收到的份額，驗證通過就可以說明這個份額確實是和其他發出去的份額是一致的，都是按照正確的規則生成的。

硬核：區塊鏈上的隨機數，直接決定公鏈是否可信圖 10：無分發者的公開可驗證祕密分享

第三種方法是分佈式密鑰生成 (Distributed Key Generation)+門限簽名 (Threshold Signature)。門限簽名可以理解爲祕密分享應用到了數字簽名方案中，但是它又不是單純將兩者相疊加。通常的數字簽名方案是，一個人用自己的私鑰加密了消息獲得簽名之後，簽名可以被公鑰等公開參數驗證。而該方案使用的門限簽名方案裏同樣有一對公私鑰，但是每個參與者分別只有總私鑰的其中一個碎片以及相應的公鑰碎片；這些私鑰碎片集合起來可以恢復出完整的私鑰，公鑰碎片同理；每個人可以利用自己的私鑰碎片進行簽名獲得簽名碎片，這些簽名碎片可以被公鑰的相應碎片驗證；並且，這些簽名碎片中的任意 t 個合起來可以計算出一個總簽名，該總簽名相當於用總私鑰進行簽名，因此也能被總公鑰驗證。故而這樣的簽名過程並不需要所有人蔘與，只需要 n 個人中的 t 個人的有效簽名即可完成簽名過程。而且無論是哪 t 個人參與簽名，最後生成的簽名是一樣的。並且簽名過程中涉及到的私鑰不會被泄露，每個人分享的只有公鑰碎片和自己的簽名結果，這使得多輪無交互簽名成爲可能。當然，這個總的公私鑰對以及相應碎片不是任意選取的，它的生成需要所有的 n 個人在協議第一次運行時運行分佈式密鑰生成協議才能生成有這樣的密碼學特性的公私鑰對及其碎片。因此，這個方案同樣存在協議必須要知道總人數 n 的問題。

使用 Icommon 作爲隨機性來源

使用 Icommon 作爲隨機性來源，最常見的方法是採用比特幣鏈上未來某一個塊的 Hash 值作爲 Icommon，或者使用當日股票市場上某一支股票的收盤價。但是這個方法的問題在於，輸出 O 完全由 Icommon 計算得來，攻擊者有可能通過操縱 Icommon 的值來使得 O 變爲他想要的值。如果從 Icommon 計算 O 的過程沒有那麼容易，比如說有可能要耗上一整天，那麼攻擊者將沒有足夠的時間去提前預測 O 的值。爲了實現這樣的需求，我們引入了一個新的密碼學工具：可驗證延遲函數 (Verifiable Delay Function, VDF)。這樣的工具能夠使得輸出 O 在給定時間 t 內是很難通過輸入 Icommon 計算出的，即使擁有任意的並行處理器以及多項式級別的提前計算量。同時，輸出 O 是唯一的並且可以被公開驗證是由 Icommon 正確計算得來的。它很像 PoW，但是 PoW 不抗並行處理器及多項式級別的提前計算攻擊，也就是說，使用並行處理器能夠顯著縮小 PoW 的計算時間到遠遠小於 t。使用 VDF 可以保證在給定時間內全世界沒有任何一個人可以預測與給定輸入相匹配的輸出。以太坊 2.0 已經計劃使用 VDF 作爲隨機數信標。

參考文獻

[1] Yao, Andrew C. 「Theory and application of trapdoor functions.」Foundations of Computer Science, 1982. SFCS\’08. 23rd Annual Symposium on.IEEE, 1982.

[2] Boneh, Dan, et al. 「Verifiable delay functions.」Annual International Cryptology Conference. Springer, Cham, 2018.