譯者按：原文作者Emin Gün Sirer是康奈爾大學計算機科學副教授，IC3密碼貨幣和合約倡議的聯合主任，在這篇文章當中，他通過具體的實例分析了為什麼從區塊鏈中導出公平的、不可操縱的的隨機數是困難的，因而像福利彩票這樣的彩票並不適合用區塊鏈來實現。
(圖片來自：MyRichFuture.com)
今天的文章，我通過一個警示性的故事，來解釋為什麼在區塊鏈上運行彩票是一個糟糕的主意[1]。
場景是這樣的：Bitcoin Core開發者 Eric Lombrozo昨天秉著聖誕節的精神，決定贈送出1個BTC，他將其分成了10份，每份為0.1BTC，規則是：轉發他的推文，就有機會得到這筆獎金。每份禮物的價值大約為1500美元[2]（譯者注：文章創作時間為2017年12月25日）
為了證明這次贈送活動是公平的，他在推文中描述了自己提出的算法。我不會去討論其具體的技術細節，你只需要明白，本質上，他想要選擇一個隨機數，比如說17，然後他會把這10份獎勵分發給每一位得到隨機數17的人。為此，他組合了其預先確定的區塊高度的兩個區塊哈希，並導出與轉發數量相互質的16位（bit）數字(H)，所謂的互質數，僅僅意味著中獎彩票號碼H和轉推文的數量沒有除1之外的公因數。然後，他索引操作了轉發列表10次，然後獎勵每一個第 (H)的轉發推文。
現在，這個計劃是非常華麗和複雜的。但是，下面發生的關鍵操作很簡單：他從兩個區塊哈希中導出了一個隨機數。我至少看到過十幾個以太坊Dapp使用了這種模式，如果你覺得自己已經理解了這個問題，你可能會選擇停止閱讀。但請繼續，因為這裡面存在著多個問題，並且實際的漏洞並不是顯而易見的，即使一開始看起來是這樣的。
讓我們深入研究這個方案，並記錄下有趣的觀察和思考：
關於礦工攻擊的擔憂
這個計劃，表明上需要相當擔心礦工對彩票操縱的可能。
每一個從區塊哈希導出隨機數的人，都應該擔心礦工攻擊的問題。假想一下，一名礦工希望讓這個彩票變得不公平，他可以通過計算一個區塊並查看其哈希是否會給礦工帶來好的結果。如果不是好結果，這名礦工可以丟棄掉區塊，選擇不去公開。
但實際上，礦工攻擊並不是問題
但在這種情況下，對礦工的擔憂完全被誇大了，假設一名礦工為了這個特別的彩票，他必須放棄一個完好的比特幣區塊，因此他要失去超過20BTC （約合30萬美元）的獎勵，而得到的彩頭卻只有0.1BTC（1500美元）。
無論如何，有些人會過於偏執於那些不會發生的事情。我們聽到過不少關於"中國礦工"[3]的消息，還有專門詆譭他們的紅迪子版塊。Core開發者總是不斷提醒我們要警惕中國礦工。也許額外的偏執是被要求的。但至少，中國礦工們可能是無害的。
當我們試圖關注礦工的時候，我們可能完全錯過了其他更大的問題，對吧？
在這一點上，事情變得非常哲學，所以我會放棄這一思路，我不認為礦工是邪惡的。這裡有一個充滿信息和模因的subreddit。
那麼，這種方法能夠很好地牽制住礦工嗎？一點也不。該方案從兩個哈希的組合中導出隨機數，分別在高度H和H + 5。它無法確保這些區塊來自兩個獨立的礦工。如果兩個數字來自同一個礦工的話，那麼挑選它們有什麼意義嗎？
即使區塊H和區塊H+ 5來自不同的礦工，我們怎麼知道它們不是一夥的？這似乎是一個不可逾越的問題。
好吧，無論如何它都是有問題的
但不管怎樣，這個方案都可以通過可預測的方式進行破壞。挖掘第二個區塊的礦工，會知道第一個區塊是被誰挖到的，所以他完全控制了彩票的結果。所以，兩個礦工之間甚至不需要串通，因為第二個礦工已經控制了結果。如果挑選了N個區塊的哈希，那麼挖到最後一個區塊的礦工，依然可以控制結果。
但這並不重要
但是等等，在隨機性計算中的缺陷並不重要，因為理性的礦工不會發動攻擊，因為成本遠遠高於潛在的獎金。可是，假設是把一個國家級的彩票（例如福彩）放到區塊鏈上，那就是另外一回事了，但這個案例顯然不是，所以讓我們繼續前進。
另外存在的漏洞
這就引出了一個更為根本的問題所在。這個特殊的方案選擇了一個隨機獲勝的數字，並給得到這個數字的人頒發獎勵。其選取的隨機數僅受限於群體大小的互質。組合H的選擇，並選擇H*j mod N的算法限制了贏家的集合。
因此，一些數字較其它數字會更容易地被選為H。簡單舉個例子來說明原因。想象一下， Eric的推文被轉發了1000次，那麼與1000 互質的潛在數字就有65534個。例如，2, 4, 5、6, 8和10不是互質的，所以它們不是第一個被選取的數字。它們的倍數也不會被選擇。
現在，被選擇的數字可能是較小的，比如1，然後覆蓋前10個數字，包括2、4、5、6、8和10。
也可能會選中較大的數字，它環繞並覆蓋那些不會被覆蓋的數字。
但是，很可能有一些數字既沒有被選中的數覆蓋（即N的互質數），也沒有被環繞的大數字所覆蓋（即mod N 互質數的倍數）。讓我們來看看這些不幸運的數字。
有這麼不幸的數字嗎？是的，事實證明，如果轉發了1000次，那麼第20、25、40、50、60、75條轉發絕不可能獲勝！
更多的麻煩
我們不知道會發生多少轉發，所以或許1000次轉發的不幸數字，和1001次轉發的不幸數字可能差別很大。
在這一點上，我們可以做一些理論分析，而現在是平安夜，要計算和檢驗數字要容易得多。我們所能做的，就是對轉發的可能數量進行迭代，看看是否有任何有利的位置和不利的數字，然後我們可以看出有多少佔據優勢的人，以及多少不幸的人。
我寫了一個小模擬器，檢查每一次轉發的結果，我把它放到了github上，任何人都可以查看，如果我錯過了什麼的話。
這裡是圖形結果，用於模擬1000-4000範圍的推文轉發數。
我們可以看到，在已轉發 Eric推文的1000人中，10號的轉發者中獎率極高！他有641486種不同的獲勝方式。第二個有利位置是970號，他有632404種獲勝的方式。而2號, 8號和9號推文轉發也在前25之列。
<code>
Winners Losers
------- ------
10 641486 143 475215
970 632404 336 473269
890 632321 672 472628
830 631763 756 470375
790 631226 528 468487
730 630904 840 464022
710 630818 780 461876
670 630004 660 455016
610 629438 420 454108
590 628902 924 440952
/<code>
將高概率數字和尾部的低概率數字進行比較，例如，第924次轉發，它只有440952種獲勝的方式！ 而第10次轉發的獲勝概率是第924次轉發的1.5倍！其它較低概率的數字，分別為420, 660, 780、840以及528。
更大的誤差
這一切看起來都很聰明。起初看這個機制是可以由礦工操縱的，但後來發現它們完全是不相關的，並且這個方案本身也有缺陷。其分佈並不均勻，某些人獲勝的概率會大於其他人。
但是，這裡還有一個更大，更明顯的錯誤。我會給你一段時間思考。
這種彩票實際上更有利於運行社交媒體操縱服務的人，如果你有一堆Twitter 馬甲賬號，你就可以比誠實的參與者擁有更多的機會。如果你有1000個馬甲賬號，並且實際轉發數只有1000條，那麼上面這些花哨的數學和模擬實際上並不重要，你獲勝的幾率就是50％ 。
更好的方法
那有什麼更好的辦法嗎？均勻分佈實際上是很難實現的。通常情況下，最簡單的解決方案是最好的：獲取轉發列表，並基於區塊哈希導出的隨機數種子進行洗牌操縱（使用Knuth shuffle工具[4]）然後你再把獎頒給前10的人。洗牌算法必須事先公佈，那樣人們才不會認為從中作弊。當然，即使你使用了這個計劃，你仍然可能會遭受女巫攻擊（ Sybil attack）。
可Eric已經宣佈了這個特別的彩票計劃，他能夠立即改變規則嗎？如果這是一個智能合約，那就意味著一次硬分叉！
那麼，我們能從這個案例中學到了什麼？
- 從區塊鏈中導出公平的、不可操縱的的隨機數是困難的；
- 組合多個區塊哈希值無法免疫礦工攻擊，最後一名礦工可以完全控制結果；
- 如果你專注於不太可能的結果，你可能會錯過更多可能的問題；
- 事實上，這個方案表現出了令人難以置信的不公平性，如果你能選擇好轉發的時機，你可以擁有比其他人更大的優勢。
- 這個遊戲，仍然掌握在社交媒體巨魔（擁有大量馬甲賬號）的手中。
1.事實上，就像現在每一個和比特幣相關的故事一樣，這次討論，也涉及到了區塊大小的爭論；↵
2.具體來說，在撰寫本文的時候，價值是1340美元，接受這筆資金要減去40美元的交易費，如果要使用的話，還需要花費40美元的比特幣。↵
3.“中國礦工”幾乎總是被拿來和他們的國籍聯繫在一起，彷佛他們都是來自同一個模子。是的，這並不合適。↵
4.非常感謝Nick Johnson所指出的，之前使用數百萬次交換的建議是低效的，並且只能漸進地實現均勻分佈。Knuth在這個主題上花費了相當多的時間，並提出了一個有效的解決方案。↵
閱讀更多 巴比特 的文章
