可證明的可信彩票模型 | 餘興鎬_風聞

導讀

生活中有很多隨機現象：經典的物理碰撞、體育大賽的比分、熱噪聲、太陽的耀斑、遙遠的星光、量子隨機數芯片……是否可以把這些用作彩票開獎號碼的依據？有兩個問題：1、它們或者由操作人員生產，或者測量儀器受人操控。2、隨機數過程一旦發生，不能被重複檢驗的。

是否存在一種不受操縱的隨機數，卻能被檢驗呢？

     我們以人類的自由意志作為隨機源，通過一個時間之閘的算法，一端隔絕篡改過去的罪惡之手，一端隔絕對未來不懷好意的窺視。以算法內稟的透明性要求，徹底杜絕彩票腐敗的可能性。得到一個具有真隨機性、透明性、完備性的可信彩票模型。

1、傳統彩票

以美國大樂透為例，它們具有以下優點：

開獎過程直觀。

具有極高的知名度。

缺點是：

開獎號碼不是真隨機數。

彩票中心貪腐案件層出不窮，名聲不佳。

參考資料：

菲律賓總統下令無限期關閉全國彩票店理由是涉嫌大規模腐敗

   1.http://finance.jrj.com.cn/2019/07/30100627902612.shtml

   2. Insiderwho scammed $14.3m lottery ‘win’ pleads guilty

https://nakedsecurity.sophos.com/2017/07/14/insider-who-scammed-14-3m-lottery-win-pleads-guilty/

彩票中心控制了幾乎所有方面，傳統的流程處處皆漏洞，可信度低。

參考資料：

互聯網彩票大起底：“黑彩”“吃票”“倍投”，三個黑幕讓你傾家蕩產！

http://www.sohu.com/a/273021811_100288264

吃票——彩票“銷售”的詐騙花樣

http://blog.sina.com.cn/s/blog_c204b0d50102yen4.html

     針對傳統彩票這些無可避免的缺陷，能否用密碼學方法，設計一個真正可信的彩票系統呢？在正式開始之前，我們需要先學習貫穿本文始終的一點點預備知識——哈希算法。

2、哈希算法簡介

       哈希算法即哈希函數（又稱散列函數或者雜湊函數），是把任意長度的輸入數據，通過該函數創建一個對應的固定長度的輸出，這個短輸出稱之為哈希值（又稱散列值、摘要或者數據指紋），哈希值相當於是對輸入數據的一種背書，它承諾了一個對應的原始數據。

   圖2-1哈希函數

哈希算法具有以下特點：

    根據輸入數據在有限的時間和資源內很容易計算出哈希值，這稱為正向快速。而根據哈希值，完全無法推斷出原始輸入數據，這稱之為不可逆（或者單向性）。輸入數據只需要發生最微小的改變，哈希值也會徹底不同，這稱之為雪崩效應（或輸入敏感）。

      對於同一個哈希函數，相同的輸入數據會有相同的哈希值，若哈希值不同，那麼輸入數據一定不同，這稱之為哈希函數的確定性。另一方面，若兩個不同的輸入數據，得到了相同的哈希值，這種情況稱為“雜湊碰撞（collision）”。只應選用當前還無法人為刻意製造出“雜湊碰撞”的哈希函數，目前MD5、SHA-1等函數已不再安全，本文示例中使用SHA3-256函數。

3、可信彩票模型簡介

       要使一個彩票系統真正可信，開獎號碼應該是真正意義上的隨機數；彩票涉及的所有數據和開獎方法應對所有人透明可查；透過公開的數據和算法，任何人都可以驗證最終開獎號碼，證明其不受任何秘密的隱藏因素的影響。

     可信彩票系統的操作流程如圖6-1彩票模型B所示，首先對彩票購買截止時間點內的所有售出的彩票號碼數據排序，立即公開和公證該數據的哈希值（參見2、哈希算法簡介），並在隨後提供原始數據的下載。

      然後，把上一步計算得到的哈希值作為輸入，使用一個可以消耗特定時間長度的公開算法（參見5、確定性時延算法），得到最終的開獎號碼。對於這個開獎算法來説，開獎號碼由彩票池原始數據唯一確定。

4、彩票模型A

4.1、對彩票池原始數據進行哈希

     所有彩票號碼的購買記錄構成了一個集合，為了防止二義性，對其排序可以得到唯一確定的結果，我們把排序後的彩票號碼交易記錄稱之為彩票池原始數據。為了及時固定彩票池原始數據，應立即計算其哈希值並公開和公證。（注意，需要確保在臨近截止時間點之前有彩票購買記錄。）

      為了方便演示，下面用模擬器生成了10條福彩雙色球銷售記錄並對其進行了排序（真實數據可能有上億條），每條記錄包含6個紅球號碼、1個籃球號碼和每張彩票對應的附加碼。其中第6、7條彩票號碼相同，附加碼不同，表示不同的人購買了同一個號碼。若彩票號碼不同但附加碼相同，表示這兩個號碼屬於同一張彩票（一張彩票上可以買多個號碼或者複式投注）。

      把lottery_model.data作為輸入數據，使用SHA3-256計算其哈希值（參見6.1公式①）。

      該示例計算時間不到2納秒，哈希函數SHA3-256輸出64個16進制數（等於256位二進制數），這裏的'7ee4d882……‘就是該輸入數據對應的哈希值，立即在網上公開這個值使人們可以查看，並在隨後提供lottery_model.data文件下載。

4.2、Alice的疑惑

      現在假設有彩民Alice對彩票中心並不信任，Alice通過網絡或者電視直播在第一時間查看到了'7ee4d882……‘這個值，並在晚些時候才下載lottery_model.data這個文件。通過標準的哈希算法她計算得到了'7ee4d882……‘這個值，經過對比發現這個值與之前彩票中心公開的那個值一致。在lottery_model.data文件中Alice根據她手上的彩票的附加碼找到了她購買的兩個彩票號碼：

      Alice因此可以推論她下載到的lottery_model.data確實是彩票中心之前公開申明的文件。在這個過程中，哈希值起到了對原始數據的承諾作用。

   Alice想了一下，把自己購買的號碼球08改成09，重新計算lottery_model.data的哈希值得到：

      她驚奇的發現，雖然僅僅只改變了一個號碼，其結果哈希值卻被徹底改變了，這是因為哈希算法的雪崩效應所致。因此Alice明白，每個彩民選擇的彩票號碼，都會徹底的影響最終的開獎號碼。

      （想一想）如果現在我們就把'7ee4d882……‘這個值立即映射到一組開獎號碼（參見6.1公式③），這就已經是一個具有內稟隨機性的彩票模型了——我們且稱之為彩票模型A。

圖4-1彩票模型A

但是——

4.3、Eve對彩票模型A的攻擊

     Eve是彩票中心的一名技術人員，他負責計算彩票池原始數據的哈希值以及向外公開這些數據的工作。設想Eve首先通過正常渠道購買了1000張號碼各不相同的彩票，當臨近彩票購買截止時間點12:00時，Eve已經收集到了所有彩票的銷售記錄，但他並不立即對外公開這些原始數據，而是在彩票池原始數據中新增加一條虛假的彩票號碼FakeNumber記錄。

     Eve用一個程序自動試算FakeNumber的值，因為哈希函數正向快速的特點，利用彩票模型A的開獎算法立即計算出了一個開獎號碼。程序會檢查這個開獎號碼是否在Eve事先購買的這1000個號碼之中，如果不在，就改變FakeNumber中的數字，再次重複以上過程。大約經過20000次這樣的嘗試計算之後，Eve幾乎必然可以找到一組特定的FakeNumber的值，能使最終的開獎號碼落入他事先購買的1000張彩票號碼之中。

      因為計算彩票模型A的開獎號碼非常簡單，速度很快，大約在不到0.01秒的時間之內，程序就可以計算好了這一切。現在時間為12:00，Eve把這個添加了FakeNumber號碼的彩票池數據，作為“原始數據”對外公開其哈希值以及提供數據下載。Eve通過精心的設計，修改了彩票池原始數據，最終以1001張彩票的代價，讓自己獲得了大獎。

5、確定性時延算法

      彩票模型A可以被操控的根本原因在於，從彩票池原始數據映射到開獎號碼的算法十分簡單。通過測試在原始數據中添加不同數字得到的開獎號碼，在極短時間之內就可以進行上億次這樣的試算，通過篡改彩票池原始數據，就可以讓自己中獎。

      幸運的是，有方法可以迫使在計算開獎之前，必須消耗一段符合我們期望長度的時間，我們把該算法稱之為確定性時延算法。

      根據哈希函數不可逆的特點，我們對任意數據進行哈希計算，可以得到一個無法事先預知的哈希值。比如，我們對字符串數據’something_1’進行哈希計算可以得到一個哈希值7c8bbe46d8aa1b364e2867f08f6c8f8d5bae8ce156610bad492629cd396f4921，如果我們想要找到一個字符串，要求它的哈希值是以'0’開頭，應該怎麼辦呢？只存在唯一的方法，就是計算不同輸入數據的哈希值，只要嘗試的次數足夠多，從概率上來説，在這些結果中就一定能找到滿足要求的值。為方便起見，下面的示例通過在’something_‘後面添加自然數n來改變輸入數據字符串。

      當輸入數據為’something_11’的時候，我們看到其哈希值'0996c9ed……’ 滿足我們之前設想的要求。如果要求是以'00’開頭的哈希值呢？我們就不得不進行更多次數的嘗試。

     當輸入數據為’something_540’的時候，發現其哈希值'0037891b……‘滿足要求。我們把要求的'0’的個數表示為DIFFICULTY值，隨着DIFFICULTY值減小，找到合適輸入值的計算量呈指數迅速增加，下面要求的DIFFICULTY值為'0000000F’，程序經過2505014次哈希計算才找到一個滿足要求的對應的輸入值，這在我的計算機上花了79秒。

      從以上演示我們可以看到，通過要求不同DIFFICULTY值，找到滿足要求的輸入值的過程就必須消耗對應長度的時間。即使計算機硬件能力提升，我們簡單的改變DIFFICULTY值也能消除由此帶來的影響。

6、彩票模型B

6.1、開獎步驟和算法

     我們把引入了確定性時延算法的開獎算法稱之為彩票模型B。如下圖所示，在計算得到彩票池原始數據的哈希值origin_hash_sum之後，並不立即把它映射到開獎號碼，而是要求找到一個最小的自然數n，使字符串origin_hash_sum+n的哈希值小於一個約定的DIFFICULTY值。尋找滿足要求的n值是一個確定性時延算法，它必須消耗一段符合我們期望長度的時間。最後，把找到的n值和origin_hash_sum作為參數，映射到最終開獎號碼。

圖6-1彩票模型B

詳細的開獎算法可以分為下面三步：

     Step1使用公式①計算彩票池原始數據的哈希值oringin_hash_sum，立即公開和公證這個值，並隨後提供對應的原始數據的下載。這一步與彩票模型A中對彩票池原始數據進行哈希完全相同。

     Step2使用公式②確定性時延算法，找到使oringin_hash_sum+n的哈希值小於DIFFICULTY值的最小的自然數n。該計算必然會消耗一段我們預期的時間。找到使下式成立的最小自然數n（n∈N）：

    Step3使用公式③利用第一步得到的origin_hash_sum和第二步得到的n值，計算開獎號碼。

      首先計算字符串n+origin_hash_sum的哈希值，把該哈希值作為16進制數，除以開獎號碼球的所有組合數，取其餘數，則該餘數值剛好可以與號碼球的一個組合相對應，該組合的號碼球即為當期的開獎號碼luck_number。這一步的計算其實很快，因此Step3幾乎與Step2同時完成。

      從以上的步驟可以看出，約定的DIFFICULTY值、哈希函數和MAP()映射函數共同構成了完整的開獎算法。雖然該算法中間引入了計算n值的難題，但n值由彩票池原始數據唯一確定，因此最終開獎號碼由彩票池原始數據唯一確定，即一個確定的彩票池原始數據輸入，對應一組確定的開獎號碼輸出。

      在當期彩票購買截止時間點12:00時，彩票中心必須立即公開彩票池原始數據的哈希值，而計算出開獎號碼必須消耗符合我們預期的時間（比如30分鐘），因此在公開彩票池原始數據之前，沒有人能夠預知開獎號碼，而公開之後，沒有人能更改彩票池原始數據。結合上面提到的“開獎號碼由彩票池原始數據唯一確定”，由此可證該算法確立了一個真正可信的彩票模型。

6.2、Bob的視角

      另一個彩民Bob在當期彩票臨近截止時間點的11:59購買了一張彩票，所選的紅球號碼是05 12 15 16 25 26，籃球號碼是07，這張彩票的附加碼是55617200。他在12:03的時候看了一眼手機，注意到了彩票中心公佈了一個文件的哈希值：

      午飯過後，Bob注意到彩票中心於12:35公佈了開獎號碼及相關信息（見下文）。下午14:00左右Bob有一段空閒時間，他打算驗證一下本期的開獎過程和結果。Bob從網上下載了lottery_model.data文件，根據自己所購買的彩票號碼及附加碼，他很快在這個文件裏第7行找到了自己所購彩票的記錄：

      隨後Bob用SHA3-256函數工具（這是一個標準哈希函數，可使用在線工具或其它含有該函數的軟件工具）計算了lottery_model.data的哈希值，發現得到的值跟彩票中心之前公佈的那個值相等。因為這個文件包含有他在11:59的彩票購買記錄，而他在12:03見到了這個文件的哈希值，於是Bob可以斷定這個文件的形成時間只可能介於11:59-12:03之間。我們看到4.2節 Alice也進行相同的驗證。

     Bob再次查看彩票中心在12:35公佈的開獎過程的信息：

     Bob把lottery_model.data文件的哈希值'7ee4d882……‘和彩票中心公佈的開獎過程中使用的n值'156229769’進行字符串拼接，算得該字符串的哈希值為'00000008……’，Bob發現該值的確小於約定的DIFFICULTY值'0000000F’，因此n值'156229769’是有效的。

      Bob繼續選取0-156229769範圍內的任意值作為n值，使用以上同樣的方法計算，發現其對應的哈希值都大於DIFFICULTY值'0000000F’。Bob知道其它人也可以選取這個區間的任意值甚至全部的值都進行類似的驗證，因此Bob可以相信'156229769’的確是滿足DIFFICULTY值要求的最小n值，這意味着在計算最終開獎號碼的過程中，確定性時延算法至少進行了156229769次這樣的哈希運算。在現實中的硬件條件下，這個運算量必然會消耗一定長度的時間（可能在30分鐘左右）。

     這使Bob可以斷定，彩票中心在收到最後一條彩票銷售記錄，到公佈lottery_model.data及其哈希值這段時間之內（Bob通過自己的行為，可以斷定這個時間段一定介於11:59-12:03之間，實際情況可能在毫秒級），絕無可能計算得到'156229769’這個值，也就是説絕無可能提前預知開獎號碼。

      最後，Bob把'156229769’和'7ee4d882……‘作為參數，使用開源算法中的MAP()映射函數，自己立即就計算出了開獎號碼是09 17 21 25 26 30|13，與彩票中心公佈的開獎號碼相同，Bob確信本次開獎是有效的。

6.3、Eve的再次出擊

      在彩票模型A中，Eve通過試算開獎號碼的方式，篡改原始數據從而讓自己獲得大獎。那麼在彩票模型B中，Eve是否還可以做到呢？

     像上次一樣，Eve事先通過正常渠道購買了1000張彩票。在11:59分，等彩民Bob購買了當期最後一張彩票之後，Eve並不對外公開彩票池數據，而是立即開始試算開獎號碼。回憶一下，在彩票模型A中，Eve可以在0.01秒的時間之內，數萬次的試算一個Fakenumber的值，從而在12:00之前就可以完成對原始數據的篡改。那麼這一次呢？

      在引入了確定性時延的彩票模型B中，Eve竭盡全力，調用他能調用的一切資源，滿頭大汗的Eve在13:00時才完成了一次開獎號碼的試算。在此之前的12:00，彩票中心就有義務必須公開彩票池原始數據的哈希值了，Eve只好在不能預知開獎號碼之前，不情願的公開了彩票池原始數據和對應的哈希值。

     在公開彩票池原始數據之前的12:00，Eve即使想要在彩票池原始數據中硬要再次添加一條Fakenumber號碼，這次因為無法試算開獎號碼，只能添加隨機的號碼。該號碼和他之前購買的1000張彩票號碼一樣，與其它正常彩票沒有任何區別，會被計入當期的彩票銷售總額，與其它正常彩票有同樣的中獎幾率。

     Eve發現自己雖然能夠在12:00之前篡改彩票池原始數據，但毫無價值。而彩票池原始數據的哈希值一旦公佈，則原文件再也無法篡改，無法添加任何記錄。開獎號碼也隨彩票池原始數據的哈希值的公開而唯一確定。Eve的投機行為完全失敗。

7、可信彩票模型的特點

7.1 隨機性

     我們人類擁有自由意志，每個彩民的自由意志賦予了他所選擇的彩票號碼的隨機性。開獎算法中的哈希函數，使得每一個被選擇的彩票號碼，都徹底的改變了最終的開獎號碼。這種原始數據內稟的隨機性，賦予了最終開獎號碼的真隨機性。

7.2 全透明

      開獎算法（即本文）是已知的，跟具體的代碼實現解耦合，附錄的Python示例代碼可以幫助理解，用其它語言來實現該算法，其開獎結果是一樣的。在實際運營中，這些代碼都必須要開源。

      彩票池原始數據，及完整的開獎過程和開獎結果，所有信息都在第一時間對外公開和公證。任何人都可以通過公開的渠道查詢或者下載這些數據。這種透明性是開獎算法的內在要求，這使任何人都能夠核查彩票的獎池金額和銷售總收入，徹底杜絕了彩票腐敗的可能性。

7.3 完備性

      任何人都可以把這些數據下載到本地，通過開源的開獎算法，獨立的對開獎結果進行驗證（參見6.2、Bob的視角）。利用以上透明公開的這些數據和算法，即可計算得到相同的開獎結果，全部過程不需要其它的秘密的隱藏因素的參與。與那些依賴於操作人員的行為、天文事件、熱噪聲、物理碰撞或者量子隨機數發生裝置相比，該模型實現了可驗證的隨機數，具有無可比擬的優勢。

8、確定性時延的改進算法

      通過對現實世界中硬件算力的測算，我們在確定性時延算法中約定的難度值期望30分鐘時間，在示例代碼中實際消耗時間為34分鐘，這是因為要找到滿足DIFFICULTY值要求所對應的輸入值這件事情本身固有的不可預測性所致。為了使確定性時延算法的預期時間更加平穩，改善開獎時的體驗（沒有改變安全性），可以對彩票模型B的Step2中的確定性時延算法作如下改進：“找到使oringin_hash_sum+n的哈希值小於DIFFICULTY值的最小的自然數n”改為“找到使oringin_hash_sum+n的哈希值小於DIFFICULTY值的前10個自然數n，取其最小的哈希值對應的n值”，其它算法保持不變。

      附錄的示例程序已支持該改進算法，默認為找到前10個滿足DIFFICULTY值為'00003’的自然數，取其最小哈希值對應的n值，因此下面兩個命令的結果是一樣的

9、與區塊鏈的關係

      如果瞭解區塊鏈技術原理，可以發現確定性時延算法與比特幣的挖礦算法在原理上具有相似之處，它們都是通過反向利用哈希算法人為製造一個“難題”。正因為如此，項目在實際運營中，可以租用高度優化了哈希計算的比特幣礦機來運行確定性時延算法，計算最終的開獎號碼。

      不同之處在於，區塊鏈用這個“難題”去阻止人們纂改過去，確定性時延算法用這個難題去阻止人們窺視未來。

10、參考資料

《MasteringBitcoin: Unlocking Digital Cryptocurrencies》Andreas M.Antonopoulos

《PythonCookbook》David Beazley, Brian K. Jones

《密碼學基礎教程：秘密與承諾》 [美]菲利普 N. 克萊因(Philip N. Klein)  機械工業出版社

《奇妙量子世界》墨子沙龍 人民郵電出版社

致謝

      感謝袁嵐峯老師對本文最核心的理論基礎的指導，陳經老師對於模型內在邏輯的梳理和討論，田輝老師於百忙之中對於本文的審閲，各位編輯專業且不辭辛勞的工作，當然，最重要的感謝是家人給予的全方位的支持。在我們所有人的共同努力下，本文才得以與讀者見面。

附錄示例代碼

詳見：https://github.com/grayloach1/lottery_model/tree/master/