區塊鏈上的隨機性（一）概述與構造_區塊鏈:RAN

編者按：本文來自NPC源計劃，作者：邱飛旸，Odaily星球日報經授權轉載。"Randomnessissomethingbeyondhumanbeings."——TheBigQiu序言：

隨機是不確定性，而依賴確定性是人的天性。程序本是確定的，而引入隨機數這個不確定因素之后，帶來了更多的可能性。而隨機數在區塊鏈中則更為重要。在區塊鏈的透明之下，隨機數生成機制被徹底暴露；而貨幣成為原生屬性之后，所有人都更有激勵希望去操作隨機的天平導向自己。在應用層，隨機數決定游戲規則是否公平，在EOS各類Dapp出現隨機數漏洞屢次遭受損失之后，愈加受到重視；而在協議層，隨機數能夠提升整體的性能，可以決定一條鏈是否可信，對于如Dfinity、Algorand等以隨機數為賣點的項目，甚至決定其生死。不久之前，全國區塊鏈大賽一等獎作品為“DnaRand一個公平的去中心化隨機數基礎設施”，實現在作惡節點不超過一半的情況下提供去中心化、不可操縱、不可預測的隨機數。其設計者即為本文作者。本文為NPC隨機數專題第一篇《概述與構造》，enjoy。——Ryan作者介紹：隨機性(Randomness)的獲取是區塊鏈中非常重要的一個課題。這里的隨機性的獲取包括但不僅限于：如何在智能合約中引入不可預測的隨機數；如何在共識協議中安全地進行隨機抽簽。顯然，上述對于隨機性獲取的問題描述已經說明了為何這個課題十分重要。而在區塊鏈中獲取隨機數非常困難，這一方面來自于區塊鏈系統的透明性——從通常意義上來講，該特性會使得一切算法的輸入，輸出以及算法本身暴露給所有的系統參與者——因此，在密碼學中廣泛使用的偽隨機數發生器不可以被直接以硬編碼的方式或者是智能合約代碼的方式應用在區塊鏈系統中來獲取安全的隨機數，因為透明性，系統參與者能夠根據代碼預測到隨機數甚至操縱隨機數，從而讓隨機源不“隨機”。另一方面，隨機數獲取協議作為區塊鏈系統的一個子協議常常與該系統下的其他協議有緊密的關系，如共識協議，這意味著其他協議很有可能會影響隨機數獲取協議的安全性。從而使隨機數獲取協議的設計變得非常復雜，常常需要具體問題具體分析。本篇文章總結了目前主要的應用在區塊鏈的不可預測隨機數獲取協議，并提煉出它們的設計思想，方法論以及依賴的假設，然后對他們進行比較。本文分為兩部分：第一部分介紹基本概念，并從零開始解釋構造適用于分布式系統的隨機數協議核心；第二部分介紹目前主流的應用在區塊鏈項目中的隨機數協議，并分析他們是如何使用第一部分所介紹的某類或者某幾類協議核心。本文假設讀者已經具有基本的區塊鏈知識，并對以太坊智能合約的基本原理和比特幣共識協議的基本原理有大致的了解。隨機性的定義

俄羅斯基于區塊鏈的憲法修正案投票系統今日上線后故障頻出:當地媒體報道，俄羅斯基于區塊鏈的憲法修正案投票系統在今天早些時候上線后開局不順。基于Bitfury開發的Exonum區塊鏈平臺的電子投票，定于6月25日至6月30日在莫斯科和下諾夫哥羅德舉行。

據稱，區塊鏈將幫助對投票進行加密，以提供安全且不可變的數據。俄新社報道稱，該網站在上線后的幾個小時內無法訪問。根據俄中央選舉委員會(CEC)的官方說法，停電是因為選民的“需求高峰”。

與此同時，媒體報道，在第一個小時內，只有494名莫斯科居民在網上投票，當時共發布了6.5萬份電子公告。當地新聞媒體Meduza報道，電子投票在某些地區顯示出不正常的結果。例如，根據2020年1月的數據，在特羅利茨基行政中心的一個投票站，有近7300人已經在網上注冊投票，盡管該投票站只有2358名有資格投票的居民。當地選舉委員會稱這是“技術故障”。（Cointelegraph）[2020/6/26]

在日常生活中，我們經常會聽到諸如“隨機選擇”，“偽隨機數”，“隨機模型”，“隨機序列”之類的詞匯，以及“偽隨機數”、“真隨機數”這樣的概念。想要理解這些詞匯和概念，必須要搞清楚隨機是什么。事實上，與“隨機”相對的是“確定”。因此，我們可以將“隨機”直觀上理解為“不確定”——無論是隨機數，還是隨機選擇，我們都希望這個數或者選擇的結果從某種程度上來講是不確定的。因此，如果直接給出一個數，而不給出這個數的產生方式，它不能被稱之為隨機數，比如直接給出一個數字1，我們不能說1是隨機數，但是如果這個1是通過擲骰子決定的，則可以說這個1是隨機的。當然，這些都是非常直觀而寬泛的理解。更精確地講，“隨機”，或者我們說“隨機數”、“隨機序列”，在不同的領域有不同的定義。在數學上，隨機數的定義和概率論相關；在計算復雜性理論中，使用描述隨機序列的程序長度來定義；密碼學會結合統計特性和密碼攻擊來描述隨機數。我們這里先給出隨機序列的描述性定義，我們可以稱一個序列為隨機序列，當它滿足：均勻性：該序列服從均勻分布。獨立性：該序列的各個元素相互獨立。不可預測性：依據該序列的任意片段，不能預測該序列余下的部分。展開來講，我們可以先考慮如下問題：1、考慮一個每一項要么取1要么取0的數列。假設它的每一項均為1，它顯然不是隨機序列，因為違反了均勻性。均勻性要求0和1出現的概率相同。2、假設它的每一項都和前一項不相等。比如“0101010101”，它滿足了均勻性，但是仍然不是隨機序列，因為違反了獨立性。3、對于一個滿足獨立性和均勻性的隨機序列。比如從常數e的小數點后第10位開始依次選取數碼組成序列。這樣的序列在統計上滿足獨立性和均勻性，但是它的序列是可以被預測的。我們說過，不同的領域對隨機性有不同的定義。比如，在仿真當中我們想要模擬顧客到達的間隔時間，用只滿足前兩條的隨機序列是足夠的。但是在密碼學中，比如生成隨機的密鑰，僅滿足前兩條的隨機序列是不夠的，一個有可能被預測的隨機序列用在密鑰生成中當然是有安全問題的。比如我們用自然對數的底e的數碼作為隨機序列。e確實可以被認為在統計上是均勻分布和獨立的，用來做仿真是足夠的，但是不能用作密碼學中的隨機種子。因為對手有可能通過一定長度的已知序列猜測到是在使用e。同理，在抽獎、游戲當中使用的隨機數也通常是要求不可預測的。鑒于區塊鏈領域中涉及的多是密碼學和游戲的場景，接下來的內容都是滿足全部三條性質的隨機序列。隨機序列又可以被分為真隨機(TrueRandom)序列和偽隨機(Pseudorandom)序列。偽隨機序列，顧名思義，就是“不是真的隨機，只是看起來是隨機的”。因此，根據圖靈獎得主姚期智提出的概念，粗略地講，偽隨機序列就是指一個與真隨機序列在計算上不可區分的序列。而真隨機序列，指的是不可被重現的隨機序列，比如通過拋硬幣產生的隨機序列。我們可以看出來，在這樣的定義下，偽隨機序列的統計特性應當和真隨機序列無法區分，也就是說，偽隨機序列同樣是滿足全部三條性質的隨機序列。當然，這樣的定義通常用在計算復雜性理論以及密碼學當中，在其他領域，只滿足前兩條性質的隨機序列也可以被稱作偽隨機序列。產生隨機序列的發生器叫做隨機數發生器(RandomNumberGenerator,RNG)。按照產生的序列的性質，我們可以將其分為真隨機數發生器(TrueRandomNumberGenerator,TRNG)和偽隨機數發生器(PseudorandomNumberGenerator,PRNG)。此外，還有一種與之正交的分類方法是從隨機數發生器的實現方法來分類，可以將隨機數發生器分為硬件隨機數發生器和軟件隨機數發生器，它們之間的關系如圖1所示：真隨機數發生器通常利用一些非確定現象，通過物理手段將其轉換為真隨機序列。通常的非確定現象包括混沌效應和量子隨機過程。其中混沌效應的特點是目前物理學能夠明確解釋其因果，但是由于結果對于初始值過于敏感，導致無法精確預測其結果。比如，通過收集大氣噪聲而產生的隨機數就是利用混沌效應產生的隨機數的例子。而量子隨機過程則是利用微觀量子態的不確定性，這個不確定性已經被目前物理學理論承認，它能夠保證即使輸入值完全相同，輸出值也是可能完全不同的。比如利用激光器的相位噪聲來生成隨機數。硬件真隨機數發生器，通常使用芯片實現；而軟件真隨機數發生器，通常利用系統自帶的一些非確定現象，譬如硬盤尋道時間、RAM中的內容或者是用戶的輸入，Linux系統里的/dev/random就是一種軟件真隨機數發生器，它通過采集機器運行過程中的硬件噪音數據來獲取足夠的隨機性來源，并依此生成隨機數。而偽隨機數發生器是一段程序，是一種確定性的算法，通常以短的真隨機數作為輸入，進行擴充，生成更長的和真隨機序列非常接近的隨機數序列。它的輸入被稱作種子(Seed)。它同樣也有硬件實現和軟件實現。如何從區塊鏈上取得隨機數

環球印務：公司將推進區塊鏈技術在醫藥溯源等領域的開發和應用:金色財經報道，環球印務（002799.SZ）在2019年報中指出，公司順應國家科技發展戰略，探索“區塊鏈”領域。目前區塊鏈產業發展的政策體系逐步完善，各地政府積極從產業高度定位區塊鏈技術，區塊鏈技術已經上升到國家科技戰略層面。隨著藥品溯源制度的全面深入推進，公司與北京愛斯瑞特合作成立新公司，旨在充分利用雙方股東在專業制造和區塊鏈技術的平臺優勢、資源優勢、技術優勢和經驗優勢，促成區塊鏈技術在醫藥溯源、醫藥物流、消費者安全用藥、醫保控費、供應鏈平臺等領域的開發和應用，共同培育和打造新一代區塊鏈技術產品和服務。[2020/4/11]

上一節中我們給出了隨機性的一個定義，這樣的定義也將用于本文余下的部分。并且，我們還給出了偽隨機性以及偽隨機數發生器的概念。在實際應用中，可用于密碼學的偽隨機數發生器有很多并且也已經很成熟了，那么我們很自然地想到，能否將偽隨機數發生器直接用在區塊鏈，在區塊鏈的共識過程或者應用上面加入隨機性，使得這樣的隨機性滿足我們上面提到的三條性質？很遺憾的是，答案是否定的。偽隨機數發生器產生的隨機序列的不可預測性的前提是偽隨機數發生器作為一個黑盒，除了它的輸出，外界無法得知其他一切信息。但是區塊鏈上的一切都是公開透明的，包括使用的偽隨機數發生器及輸入到偽隨機數發生器里面的種子也是一樣公開透明的。在這樣的情況下，所有傳統的偽隨機數發生器都無法在區塊鏈的環境下產出具有不可預測性的隨機數序列。而至于真隨機數發生器，的確存在將真隨機數發生器的結果通過可驗證的不可篡改的通道引入區塊鏈系統內部，這樣的通道又被稱作Oracle。以太坊現在常用的隨機數發生器就是通過Oracle，引入random.org提供的隨機數。但是這種方法的問題在于，所謂的“真隨機數發生器”往往是中心化的，擁有這樣的硬件或者軟件的人或者組織擁有篡改隨機數發生器結果并且不讓用戶發覺的能力。這對于主打“去中心化”的區塊鏈系統來說，無疑如鯁在喉。除了偽隨機數發生器和真隨機數發生器，還有一類隨機數發生器會直接利用區塊鏈系統中共識過程所天然產生的隨機性。比如，使用未來某個塊或者之前某個塊的Hash值來作為種子之一生成隨機數。這種做法也常見于各種區塊鏈類游戲以及資金盤游戲當中，但是這樣的隨機數獲取過程有著致命的漏洞——用戶有可能通過仔細選擇交易時間來控制隨機數向有利于自己的方向生成；即使用戶無法控制，礦工也可以控制隨機數的生成，并且這樣的攻擊成立并不需要太多算力的參與。只要最終隨機數牽涉的金額足夠，完全可以使用租用算力或者賄賂礦工的方式進行攻擊。那么歸根結底，在區塊鏈這樣的一個系統當中隨機性可以來自哪里呢？也就是說，通過上面的分析，我們發現，對于如上做法的隨機數發生器，無論規則或者程序設計得如何復雜，它都是確定性的算法。對于一個確定性的算法，算法本身不會對輸出的隨機性有任何的影響，能夠影響最終輸出的隨機性的，只有算法的輸入。因此，在區塊鏈系統當中，我們需要在一個分布式的，公開透明的環境中去仔細選擇一個有足夠隨機性的輸入。那么符合要求的輸入存在嗎？答案是肯定的，這樣的輸入實際上來源于我們對于區塊鏈系統參與者之間不是一個整體的假設。隨機數生成協議模型

動態 | Enjin 區塊鏈生態系統適用于Titan Flight Studio的游戲設計:據bitcoinexchangeguide消息，Titan Flight Studios游戲公司將把區塊鏈整合到他們的現場街機游戲ReBounce、即將到來的電子競技冠軍和未來的零售游戲化項目中，使Titan Flight使用ERC-1155標準為其游戲生態系統創建Enjin支持的令牌。[2018/12/10]

我們現在從最簡單的情況開始去逐步構造一個區塊鏈上可以使用的公平的隨機數發生器。下文所涉及到的在分布式的環境下的協議都可以轉換為區塊鏈的環境，因此不對“分布式”和“區塊鏈”做區分。為了更清楚地說明構造分布式隨機數協議，也叫分布式隨機數信標DistributedRandomnessBeacon,DRB)，的方法論，我們首先引入一個隨機數協議的抽象模型：下面，我們考慮這樣的一個場景：Alice和Bob在網上湊錢一起買了一張彩票，結果中了神秘的頭獎，令他們吃驚的是，獎品竟然是一只皮卡丘，如圖3所示。但是皮卡丘不可分割，并且由于兩人相隔甚遠無法見面猜拳，所以他們倆決定設計一個對兩個人都公平的隨機數生成協議來確定誰能獲得這只皮卡丘。v1.0最簡單的隨機數生成協議

那么這樣的協議具體是怎么做的呢？為了構造這樣的一個協議，我們需要確定這樣的協議需要滿足什么樣的性質。考慮到每個人之間的輸入是相互獨立的，這樣的協議需要保證每個人自己的輸入也應當是和輸出相互獨立的，但是他們又共同對輸出做出了一定貢獻。只有這樣，才能確保每個人都無法光憑借改變自己的選擇來改變輸出。同時，協議也需要保證只要有一個人的輸入是均勻分布的，那么結果就是均勻分布的。現實中滿足這些條件的構造方式有很多，其中一種是異或操作，將兩人的輸入異或之后輸出：在給定Bob選1的情況下，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，就能拿走這只皮卡丘。事實上，同時輸入是很難保證的，而為了防止這種作弊行為，我們需要保證，協議中的來自其他人的輸入對于參與者來講應該是暫時機密的，不會透露任何他們的選擇的信息。與此相應的，應該多出一個去機密化的過程以計算出協議的輸出。為了實現這樣的需求，我們需要引入新的機制：承諾(Commitment)。這樣的協議保證了，在第一個階段里沒有任何人的選擇會被除自己以外的其他人獲知，并且在第二階段，即使Bob先知道了Alice揭示出來的選擇值然后在自己揭示之前計算出結果，他也無法改變自己的選擇了，因為第一個階段的簽名已經做出了“承諾”。這里，數字簽名能夠保證消息的不可篡改性，不可否認性以及暫時的機密性。如果該協議是運行于區塊鏈之上，由于通常區塊鏈協議都會對交易內容進行數字簽名，那么我們的協議也可以將使用數字簽名改為使用Hash函數。v3.0a：使用經濟懲罰v2.0的版本在對于兩個人的情況的時候看起來非常公平，但是對于兩人以上的情況，它仍然是有漏洞的。假設Alice、Bob、Clare三個人分一只皮卡丘，其他設定不變，采用v2.0協議。這時，Bob想到了個主意：“在最后的第二階段，我可以在輸入自己的選擇進行揭示之前先依據別人的揭示結果計算出輸出，如果不是對我有利的輸出，我就不進行揭示階段，假裝網線被挖斷了。”剛才的協議無法處理這種情況。是重新再來一遍，還是就取剩下兩個人的輸入呢？這兩種方法是都有問題的：如果重新再運行一遍協議，那么攻擊者就可以利用這種重新運行的機制在每次自己不利的情況下強行使得協議重新運行；如果只取剩下兩個人的輸入，攻擊者同樣可以利用這種機制選擇是否放棄輸入來趨利避害。因此，我們需要有一種機制來保證參與者不得隨意放棄，最簡單的方式就是利用經濟懲罰。如圖6所示，當參與者在第一階段承諾的時候，必須要向協議鎖定一個比特幣——如果是在帶有智能合約的區塊鏈的環境，這樣的操作十分容易。如果Bob不按時揭示他的選擇，那么就會沒收Bob的比特幣分給Alice和Clare，然后重啟協議。由于皮卡丘的價值通常并不會超過一個比特幣，Bob不會選擇這樣的方式進行作弊。這樣的一個懲罰機制，就是為了防止這樣的拒絕服務攻擊。需要注意的是，之所以本節一開始所述的攻擊對只有兩個參與者的協議不奏效，是因為兩個人的情況下，在僅剩一個人的時候，我們可以直接給出有利于剩下的參與者的結果，而在多于兩個人的情形下，我們仍舊無法保證在剩下的人當中做出選擇。這樣的規則是一種天然的對拒絕服務的參與者的懲罰。v3.0b：使用門限機制

印度14家銀行計劃利用區塊鏈加快國內貿易流程:據彭博社6月7日報道，負責印度國內近一半貿易業務的14家銀行加入了印度貿易連接（India Trade Connect）聯盟，旨在引入區塊鏈技術，以加快流程并減少批準新貸款的障礙。[2018/6/7]

除了經濟懲罰之外，還有另外一種方式，我們稱之為門限(Threshold)機制。門限機制指的是一種協議的某一個指標達到一定閾值就可以執行特定流程的機制。在這里我們引入門限機制，主要是為了使得在協議參與人數有缺失的時候仍然能夠給出正常的輸出。門限機制的作用在于增強協議的健壯性，使得它能夠容忍一定程度的拒絕服務攻擊。我們接下來討論的門限機制都是門限機制，意思就是對于n個參與者的協議，只需要t個參與者的輸入即可完成協議的輸出，注意這里的n不一定是協議預先規定好的，或者說是協議必須知道的，它也有可能是一個不確定的數字。如果協議必須規定了確切的n才能夠保證正確性，那么這樣的協議只能用于許可環境(PermissionedSetting)中；如果不需要規定確切的n，那么這樣的協議可以被用于非許可環境(PermissionlessSetting)中。如圖7和圖8所示，我們使用最基本的v1.0版本的Coin-Tossing協議，將門限機制的輸出作為Coin-Tossing協議的輸入。這樣的門限機制總的說來有三種。第一種門限機制是將輸入按照某種規則排序之后，簡單地取前t個輸入。但是這種方式不抗女巫攻擊(SybilAttack)——假如Bob是黑客帝國的復制人，他復制了一萬個自己，因此Bob通過控制這一萬個身份有很大的可能占有前t個輸入，從而控制隨機數的結果。因此，這種門限機制是無法用在沒有抗女巫攻擊機制的環境下——譬如，沒有身份驗證的非許可環境下，但它的優點在于，這樣的機制不需要知道n的確切值。女巫攻擊簡單來講，指的是一種網絡內的少數節點控制多重身份的攻擊方式第二種門限機制是無分發者的秘密分享系列的。這一系列協議均需要每產生一個隨機數輸出都進行一次秘密分享來保證門限機制，屬于有狀態(Stateful)協議。更直觀地講，比如有n個人，假設只需要有t個人提交了就能輸出我們想要的隨機數，同時，我們需要r個這樣的隨機數。那么如果采用無分發者的秘密分享系列的門限機制，我們需要這n個人相互交互至少r輪。另一個局限是，該方案需要在許可環境下實施，也就是說協議必須知道總人數n，才能確定合理的門限t。第三種方法是分布式密鑰生成(DistributedKeyGeneration)+門限簽名(ThresholdSignature)。門限簽名可以理解為秘密分享應用到了數字簽名方案中，但是它又不是單純將兩者相疊加。通常的數字簽名方案是，一個人用自己的私鑰加密了消息獲得簽名之后，簽名可以被公鑰等公開參數驗證。而該方案使用的門限簽名方案里同樣有一對公私鑰，但是每個參與者分別只有總私鑰的其中一個碎片以及相應的公鑰碎片；這些私鑰碎片集合起來可以恢復出完整的私鑰，公鑰碎片同理；每個人可以利用自己的私鑰碎片進行簽名獲得簽名碎片，這些簽名碎片可以被公鑰的相應碎片驗證；并且，這些簽名碎片中的任意t個合起來可以計算出一個總簽名，該總簽名相當于用總私鑰進行簽名，因此也能被總公鑰驗證。故而這樣的簽名過程并不需要所有人參與，只需要n個人中的t個人的有效簽名即可完成簽名過程。而且無論是哪t個人參與簽名，最后生成的簽名是一樣的。并且簽名過程中涉及到的私鑰不會被泄露，每個人分享的只有公鑰碎片和自己的簽名結果，這使得多輪無交互簽名成為可能。當然，這個總的公私鑰對以及相應碎片不是任意選取的，它的生成需要所有的n個人在協議第一次運行時運行分布式密鑰生成協議才能生成有這樣的密碼學特性的公私鑰對及其碎片。因此，這個方案同樣存在協議必須要知道總人數n的問題。參考文獻

NEM區塊鏈將推出房產應用平臺:NEM區塊鏈需要更多落地應用，以突出其作為以業務為中心的智能資產平臺的多樣性。MHub目標是基于NEM區塊鏈成為亞洲最好的房地產平臺。[2018/3/9]

Yao,AndrewC."Theoryandapplicationoftrapdoorfunctions."FoundationsofComputerScience,1982.SFCS'08.23rdAnnualSymposiumon.IEEE,1982.Boneh,Dan,etal."Verifiabledelayfunctions."AnnualInternationalCryptologyConference.Springer,Cham,2018.——————關于NPCNaissanceProjectCore源計劃簡稱NPC，是一個非盈利的分布式社區媒體，主要內容包括項目測評，加密經濟研究，區塊鏈前沿技術發展，所有內容均由社區成員完成。進入NPC社區群請加微信：luowei677329，備注標明NPC

Tags：區塊鏈BOBANDRAN區塊鏈TEC幣有這種幣嗎OBOBprivacyandprotectionTYRANT幣

芝麻開門交易所