可证明的可信彩票模型 | 余兴镐

导读

生活中有很多随机现象：经典的物理碰撞、体育大赛的比分、热噪声、太阳的耀斑、遥远的星光、量子随机数芯片……是否可以把这些用作彩票开奖号码的依据？有两个问题：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/