一、菠菜類應用成了駭客的提款機
自去年EOS主網上線以來，菠菜類應用成了EOS平臺的“主流”應用。但是，因為EOS內在機制的缺陷，讓菠菜類應用紛紛淪為駭客的刀下肉，成了駭客的提款機。一個較為知名的案例是EOSDice兩度被駭客攻破。
駭客的攻擊手法暴露了一個非常底層而本質的問題：區塊鏈隨機數的安全性問題。
以EOSDice為例[1]。第一版本它是實時開獎，使用者在當前區塊下注時，它透過智慧合約程式碼把上一個區塊的資訊以及帳戶名、id、開獎時間、合約餘額資訊作為隨機數函式的種子，計算出隨機數生成結果作為中獎依據。
駭客發現：開獎程式碼所用的隨機數函式其實生成的是確定性序列，隨機性的來源是種子。而區塊鏈上一切資料都是公開透明的，程式碼也是開源的。因此，掌握了種子資訊和計算邏輯不就可以直接推算出來押注哪裡必贏了嗎？
駭客必贏手法：根據全部已知資訊進行模擬運算，推算出必贏押注。
EOSDice團隊迅速修改了程式碼，把實時開獎改成了延時開獎。也就是說，順延一個區塊，到下下個區塊再執行開獎程式碼，這樣就可以讓隨機數函式種子使用下個區塊的資訊——這個在當前下注時還不存在的資訊。看似無懈可擊了嗎？
駭客又一次發現：既然現在無法拿到資訊，但是可以現在寫個一模一樣的演算法程式碼，到未來資訊出現的時候再執行不就可以了嗎？
駭客必贏手法：提前寫一個和開獎程式碼一樣的伴娘程式碼，但是讓它和開獎程式碼一樣延時到下個區塊執行，這樣就可以算出來必贏的押注了，然後讓這個伴娘程式碼按照必贏押注進行注資。
EOSDice這次只好把餘額從種子計算的輸入中去掉，以免駭客隨意改變押注金額操縱種子，進而操縱看似“隨機”的開獎結果。
於是有安全研究人員大聲疾呼：“區塊鏈的世界沒有真正的隨機數”，甚至更進一步的，“計算機的世界沒有真隨機數”。
在筆者看來，上述命題的外延並不清晰，需要刨根問底、一探究竟：
1、僅僅是因為EOS的偽隨機函式被駭客攻擊，就可以擴大化到區塊鏈甚至計算機沒有真隨機嗎？
2、僅僅是因為偽隨機函式不能產生真隨機數，就可以如此輕易得出不含任何前提條件的“絕對命題”（categorical judgement）嗎？這意味著上述兩個命題應該在時空任意之處都絕對正確，也意味著只要找到一個反例就足以推翻。
同時，命題的內涵也具有相當的模糊性，這會導致不同讀者產生不同的概念聯想並被誤導：
1、存在性：怎麼定義一個東西在“區塊鏈世界”和“計算機世界”有或者無？“沒有”的意思是指無論透過任何方法也不能有嗎？如果不是，那“沒有”的具體內涵又是什麼？
2、真實性：怎麼定義“真隨機數”？什麼才是真隨機？真隨機可以被確證嗎？
下面我們就來看一看這些問題。
二、隨機數的定義和及其密碼學安全性
快速瞭解現代馮諾伊曼架構計算機中隨機數問題，可以翻閱美國電腦科學家、1974年圖靈獎獲得者高德納（Donald E. Knuth, 1938-）的堪稱電腦科學理論與技術的經典鉅著《計算機程式設計藝術》（TheArt of Computer Programming，縮寫TAOCP）的第二卷“不完全數值計算演算法”之第三章“隨機數”。
僅僅這一章就有著長達170頁的篇幅[2]。其中綜述了計算機隨機數問題的研究歷史和成果。筆者給各位讀者簡要概述一下，很有趣味：
首先，高老先生回顧了一下隨機數研究歷史，然後說，究竟什麼是隨機數，這其實是一個哲學問題，也就是得先搞清楚“我是誰”（怎麼定義）這個問題。
然後，高老先生就引述一個前人給出的定義，接著說，嗯，按照這個定義的話，我想，整個宇宙中可能就不存在真正的隨機數了！好吧，我們還是換個更“寬鬆”的定義吧！
再然後，高老先生換了一個“寬鬆”一些的定義，寫了一個演算法說，大家看我構造的這個隨機數演算法，其實根本就不能稱之為“演算法”！為什麼？因為這個“演算法”根本就不能保證輸出結果（計算機術語稱之為“停機問題”）！只好再弱化要求。
接下來，就是洋洋灑灑，給大家講解各種弱弱的“隨機數”演算法，這個好一點兒，那個差一點兒，等等。總之，高老先生就是不斷地在暗示同學們，這些演算法嘛，各有各的坑，大家小心點兒用。
最後，佈置習題。完。^_^
高老先生已經開門見山地告訴我們了，一個確定性的演算法所生成的“隨機數”是什麼隨機數？偽隨機數！也就是說，計算機那個叫做“random()”（隨機）的函式其實所生成的是一種大大弱化了的、看起來像隨機數的“隨機數”。
這些隨機數函式所產生的的結果的隨機性將取決於外部給它的隨機性，比如透過所謂的“種子”引數。一旦知道了種子，它所計算出來的隨機數序列就是確定性的。
是不是就可以下結論說，計算機就沒有辦法產生真隨機數了呢？如果這句話的意思是限定計算機的方法為偽隨機數演算法的話，那麼這就不啻為一個“分析命題”（analytical judgement）：
偽隨機數演算法沒有辦法產生真隨機數。
上面這個分析命題的正確性和下面這個分析命題是一樣的：
黑天鵝不是白的。
眾所周知，分析命題先驗為真[3]。並沒有討論的必要。
我們需要討論的，永遠是怎麼解決問題。就像中本聰克服“FLP不可能”解決拜占庭問題一樣。
在密碼學上，隨機性是非常重要的，無論是資產控制私鑰的安全性，還是橢圓曲線數字簽名演算法的簽名過程安全性，都需要良好的隨機數。當然，文初提到的菠菜，可能也需要良好的隨機數。
密碼學安全的隨機數，比用於統計模擬的隨機數，對隨機性的要求就要更高、更嚴格。考慮起來，其分佈需要均勻，且不可被操縱導致出現分佈偏差，其發生不可預測，每次發生之間保證良好的獨立性。
在密碼學裡，我們把這種隨機數（的來源）叫做“高階最小熵”（highmin-entropy）。其要求統計學上“均勻分佈”的“獨立同分布”（Independentand identically distributed, i.i.d.）。
比如扔一個兩面均勻的硬幣的最小熵是-log2(1/2)= 1位元，扔一個八面均勻骰子的最小熵是-log2(8)= 3位元，而大家知道的比特幣私鑰的長度是256位元，足夠強壯的私鑰其最小熵應該可以高達256位元，也就是駭客隨便猜一下只有2的256次方分之一的概率能猜中，這麼高的最小熵就叫做高階最小熵，意思就是非常非常不容易被猜中。
計算機隨機數函式的偽隨機數演算法是確定性演算法（受停機問題約束），因而並不能為結果增加最小熵，也就是說，其輸出結果的最小熵等於輸入的最小熵。
如果輸入被人為控制或猜中，那麼輸入的熵就減小到0，結果也就完全在駭客的預料之中了。
分析至此，我們就知道了，“區塊鏈的世界”或者“計算機的世界”裡可不可以有真隨機？當然可以有。怎麼有？給這個世界輸入熵。
怎麼給區塊鏈系統輸入熵？我們可能會考慮如下一些方法：
1、讓節點加裝特殊的隨機數硬體。這個方法是有問題的：（1）不是所有的節點都有這個硬體，輪到沒有這種硬體的節點出塊怎麼辦？（2）區塊鏈是開放的，如果節點故意作弊，使用假冒的、受控的硬體怎麼辦？（3）最大的問題是，出塊節點聲稱的真隨機數其他節點和使用者完全無法驗證，在這裡，“真隨機”和“可驗證”互相矛盾！如果不可驗證，就意味著其他節點和使用者需要無條件信任（trust）出塊節點的隨機數是真的，這又和區塊鏈非信任模型相矛盾！
2、使用外部的隨機數提供介面，也就是所謂的OracleAPI。這個方法同樣有一些無法忽視的問題：（1）依賴外部Oracle就是給區塊鏈系統帶來了“中心化”和“信任依賴”，外部Oracle可以被摧毀，也就是中本聰郵件裡說的“cutoff the head（斬首）”。（2）同上，最大問題也是，其他人只能無條件相信出塊節點沒有偽造這個結果，即使Oracle提供的是真隨機數，因為“真隨機”和“可驗證”矛盾。增加Oracle其實不僅沒有緩解“信任依賴”問題，反而把這個問題進一步擴大化了！
3、從使用者輸入中獲取熵。問題：區塊鏈是完全透明的，這意味著，系統知道的所有的使用者輸入的資訊，駭客也同樣可以知道，而且可以在同一個時間知道！理論上講，駭客完全可以利用同樣的資訊、同樣的演算法模擬出同樣的結果。
4、不公開程式程式碼，也就是隱藏隨機數生成邏輯。問題：封閉程式碼只會讓真實使用者懷疑其中是否有貓膩。沒有了“公開”，公平公正性就會受到質疑！正如中本聰在帖子裡寫的，比特幣這種系統必須開源，大家才能相信這些規則是按照聲稱的來實現的。而閉源這東西反而對真正的駭客高手沒什麼大用，各種分析技術輕而易舉就搞定了。
5、試圖發明“真隨機數”計算函式。問題：發明這種“演算法”的難度和解決“停機問題”應該是差不多的吧？哈哈哈哈。
6、給區塊鏈系統引入一個“中心的”隨機數發生器，要求大家都信任它。問題：如果這種中心化也能接受，那麼其實就可以不用區塊鏈了，直接全面改成中心化多節點資料庫技術一定更好。
看起來，道路千萬條，條條走不通呀！
真的沒有路了嗎？當然不是。如果真的是這樣，就不會有中本聰發明的比特幣了。
三、比特幣是如何實現內生的去中心化隨機性的
好了，讓我們仔細考察一下比特幣的全球一萬多個出塊節點的隨機選擇問題吧。我們會驚奇地發現：
1、比特幣系統沒有辦法禁止節點操縱任何它能夠操縱的輸入，包括但不限於時間戳惡意改寫、交易集刻意選擇、nonce是不是特意選擇的，等等。
2、比特幣系統不要求節點安裝特別的隨機數硬體。
3、比特幣系統不需要依賴外部的隨機數提供介面。
4、比特幣系統不需要一箇中心的、權威的隨機數發生節點。
5、比特幣系統的程式碼和資料完全公開，人人可見。
然後比特幣系統實現了對於出塊節點的公平公正公開的隨機選擇：
也就是說，如果我們把整個比特幣系統看作一個函式：B(區塊高度) = 出塊節點，那麼這個函式B有一個很奇妙的特點，那就是，在沒有被“看見”的時候，它的結果是真隨機的，而一旦被“看見”，隨機性就會迅速“坍縮”成為一個確定的結果，而且這個結果可以被其他節點驗證。瞭解過量子力學的朋友此刻腦海中可能會浮現出“薛定諤的貓”的場景哈？那麼這裡的“看見”，則是後續出塊節點透過新區塊不斷加持和見證的過程。
親愛的讀者朋友請回想一下前面說到的，“隨機性”和“可驗證”相矛盾的問題吧。這個矛盾怎麼化解？答案只能是，未產生時具有充分隨機性從而無人可以預測，一旦產生則可以公開記錄下來被任何人反覆確證，這種“薛定諤隨機性”才是最適合區塊鏈的隨機性。
並且這個隨機性是足夠“真”的。因為如果它可以被“拉偏”，那麼操縱者就可以獲得出塊的極大優勢，進而賺取超額的比特幣獎勵！顯然，比特幣已經如此值錢的情況下，這一情況並未發生。非不願也，實不能也。
比特幣是無許可的（permissionless），也就是惡意節點可自由加入網路並操縱輸入。在這種情況下，比特幣又是如何實現內生的、去中心化的真隨機性的呢？
這個隨機性的來源是工作量證明（Proof-of-work, PoW）嗎？PoW是兩層SHA-256雜湊運算，而輸入是駭客隨意操縱的，雜湊運算對於給定的輸入必然給出確定性的結果，不會增加任何隨機性。
那麼隨機性的來源到底在哪兒呢？
比特幣是這樣一種非常特別的系統，它對外消耗能量，形成內在的自發秩序（有序的區塊鏈賬本）。諾獎得主普利高津發明瞭一個術語來描述這種系統，稱之為“耗散結構”或者“耗散系統”[4]。生命有機體、公司組織、城市、國家，這些都是耗散系統。
一個耗散系統能夠形成自發秩序，有三個條件：
1、開放性。系統要保持開放。比特幣的無准入許可極大增加了其開放程度。
2、非平衡性。系統要有持續的內部競爭，以系統遠離平衡態。比特幣的記賬權競爭，也就是挖礦競爭，乃是比特幣區塊鏈賬本的有序之源。
3、漲落。系統中微小的擾動會透過系統的非線性迴路雪崩式放大，就像所謂的“蝴蝶效應”。比特幣的區塊鏈無時無刻不在分叉，又無時無刻不在選擇最長鏈作為主鏈，從而形成一個分形結構。
工作量證明把算力漲落引入系統，作為競爭依據，這種競爭，為系統帶來了隨機性。
接下來我們考察一下比特幣區塊鏈中的隨機性應用及其操縱可行性。
四、比特幣系統隨機性應用和作弊可行性分析
我們大家都知道，比特幣區塊鏈中的區塊頭雜湊是符合工作量證明要求的雜湊值。
毋庸置疑，根據密碼學安全雜湊演算法的要求，雜湊值的分佈是均勻的，而且，無論輸入是否有規律性，輸出值之間都是沒有規律可循的。這些是防碰撞攻擊、防第一原像攻擊和第二原像攻擊的基本要求。
密碼學安全意味著，作弊者只有一種方法來嘗試欺詐，就是不斷改變輸入，直到找到符合自己利益需要的雜湊值。
比如以猜大小為例。兩人打賭某個尚未生成的區塊的頭雜湊值的最後一位位元是0還是1。如果沒有操縱的情況，這是一個公平的均勻分佈。
現在讓我們假設有一個人試圖作弊。那麼他的方法是什麼呢？方法就是使用自己的算力去搶奪打賭的物件區塊的建立權，並按照按自己下注的結果去操縱雜湊值。
一個明顯的事實是，無論兩人打賭的區塊高度是下一個，還是若干個之後，作弊者都只能從所賭區塊的前一個區塊產生出來的時候開始計算，因為計算需要有賴於這前一個區塊的頭雜湊值作為輸入之一。
另外一個值得注意的是，這個問題和中本聰在白皮書裡計算透過隱藏區塊來實現雙花欺詐不同，打賭操縱的問題是一個搶跑問題。
具體的，作弊者和平常一樣計算符合工作量證明要求的雜湊，也即是開頭有若干個0。一旦找到一個，就再看一下雜湊值的最後一位。假設作弊者押的是0，那麼如果PoW雜湊最後一位正好是0，他就把區塊廣播出去；否則，如果PoW雜湊最後一位是1，他就丟棄這個區塊。
也就是說，作弊者一旦挖出來讓自己贏的區塊，他就會立刻放出來，一旦領先，就能把其他的中立算力吸引過來，見證自己操縱過的區塊進入主鏈。
令：
p = 誠實節點找到合格區塊的概率
q = 1 - p = 作弊節點找到合格區塊的概率
誠實節點只要找到符合要求的合格區塊就會出塊
作弊節點則在找到合格區塊後，根據是否符合自己押注（不符合的概率是r）選擇出塊還是丟棄
q_r = 作弊節點搶在誠實節點前面先出塊的概率
求q_r = ?
運用概率論的一些知識，我們可以計算出答案如下：
對於兩人使用區塊頭雜湊最後一位位元對賭大小的情況，r= 0.5，則作弊節點搶跑成功的概率q_r= 0.5 * q / (1 - 0.5 * q)。則其操縱勝率將是win= q_r * 1.0 + (1 - q_r) * 0.5。
一旦操縱成功，其收益會是對方下注bet_honest。一旦失敗，其損失將是自己下注bet_cheat加上區塊獎勵block_reward。收益期望：
E_cheat = win * bet_honest - (1 - win) * (bet_cheat +block_reward)
而如果作弊者誠實遊戲，那麼其勝率和敗率將是0.5、0.5。收益期望：
E_nocheat = 0.5 * bet_honest - 0.5 * bet_cheat + q *block_reward
因操縱所得的超額期望收益為：
作弊者的期望超額收益率為E_extra/ bet_cheat，等於：
要讓期望超額收益率大於0，需要滿足：
bet_honest + bet_cheat > 2 * (1 + q + 1/q) * block_reward
令miu = 2* (1 + q + 1/q)為“超額下注係數”。
並假設雙方下注金額相當，且遠遠大於miu* block_reward以至於區塊獎勵可以忽略不計，那麼ROR_max= 0.5 * q / (1 - 0.5 * q)。這恰好等於q_r。
試算作弊節點掌握算力的比例q、搶跑成功的概率q_r、操縱勝率win、超額下注係數miu、期望超額收益率ROR_max對照如下：
q=0.001 q_r=0.0005003 win=0.5002501 miu=2002.0020000 ROR_max=0.0005003
q=0.01q_r=0.0050251 win=0.5025126 miu=202.0200000 ROR_max=0.0050251
q=0.1 q_r=0.0526316 win=0.5263158 miu=22.2000000 ROR_max=0.0526316
q=0.3 q_r=0.1764706 win=0.5882353 miu=9.2666667 ROR_max=0.1764706
q=0.5 q_r=0.3333333 win=0.6666667 miu=7.0000000 ROR_max=0.3333333
q=0.8 q_r=0.6666667 win=0.8333333 miu=6.1000000 ROR_max=0.6666667
q=0.9 q_r=0.8181818 win=0.9090909 miu=6.0222222 ROR_max=0.8181818
可見，如果你的對手掌握了比特幣全球算力的10%，那麼你們的總下注金額需要大於22個區塊獎勵，今天而言也就是275個比特幣以上。假設你們各自下注200個比特幣好了。此時他冒著以47%的概率損失掉自己的200個比特幣的風險，博取5%也就是10個比特幣的超額收益（這還沒扣掉區塊獎勵的機會損失）。這對他而言不是一個非常理性的選擇。
而如果他掌握了超過一半的算力，理論上他就不需要靠操縱開大小取勝了。完全可以對比特幣網路發動雙花攻擊，謀取更大的利益。
五、弱化PoW乃至放棄PoW共識機制就是弱化和放棄安全隨機性
根據上面的分析，比特幣採用的PoW共識機制，實現了去中心化的安全隨機性。
任何對這一共識機制的弱化和放棄，都將減少熵的匯入，進而弱化安全隨機性，以及因此而帶來的中心化依賴程度的增加又會增加系統脆弱性。
這一必然性由計算機的停機問題所限定，並在數學上，最終由哥德爾不完備定理所約束。
任何試圖減少PoW對能量消耗的設計，都會給系統增加確定性，並節省駭客嘗試攻破隨機數的代價，從而給予駭客更多的時間和空間來完成破解。
PoW本質上是一個對映函式，把物理世界的熱力學過程對映成數字世界的位元過程，是一個連線兩個世界的“蟲洞”。
駭客無法逆轉物理世界的熱力學第二定律，也就無法逆轉數字世界的位元過程。只能重演，不能反演。這也正是時間之矢的單向性。
去中心化的隨機性，以及去中心化的時間之矢，這兩點正是比特幣系統中深藏不露的秘密武器。
因此，中本聰在比特幣白皮書第2頁第3節開頭第一句就這樣寫道[5]：
我們提出的解決方案從一個時間戳伺服器開始。
（全文完）
