今天北京车牌摇号开奖,如果只有一倍概率,中签概率只有万分之四,估计这一辈子都中不了吧。北京车牌目前有巨大的利益,组织者如何保证其中没有猫腻呢?
在机器统计的世界里,随机抽奖也是重要的协议。比如陪审团人员的随机选取等等,就需要用到该协议,来确保其中没有被操纵。
1、北京车牌摇号算法
北京车牌摇号使用了公平可验证的抽奖协议,其程序和备选号名单是公开的。每个人都可以下载程序和数据,对抽奖进行验证。极大地缓解了公众的质疑。
1.1、抽奖程序
- 把所有当月审核通过的申请码( 13 位数)按照从小达大排列,并从 1 开始编号,设最大编号为$N$( 2019 年 2 月$N$为 15175162 )。在这一步中,有多个中签几率的申请码,会相应得到多个不同的编号。
- 在公证员的公正下,由 6 个人随机摇出 6 个小球,得到 6 位随机种子。
- 计算机用 .NET Framework 2.0 的
System.Random
类新建一个实例,输入上述 6 位随机种子。4. 每次调用Random.Next(int maxValue)
函数产生一个$[0,N)$的整数,对应于上述$[1,N]$的编号,查出相应的申请码。验证这个申请码是否已经抽到过,以次避免重复抽到一个编号,或者抽到同一申请码的多个编号。如果这个申请码未被抽到过,则保存到抽中的结果中。 - 重复执行 4 ,直到抽中了当月所有指标为止。
.NET Framework 中的随机数属于伪随机数,即给定相同的随机种子,可以得到相同的抽签结果,这就是为什么大伙可以自己在家用电脑验证抽签结果。
程序用到的随机数种子只有 100 万中可能性。用户在抽奖前,即可运行程序,枚举随机数种子,统计自己的中奖概率,可能和平均值会略有差异(不过差异极小)。
1.2、北京车牌摇号的瑕疵
上面的协议里有个巨大的依赖性,最核心的 6 位随机数种子依赖于乒乓球的随机性和公证员的公正,破坏了公平性。因为乒乓球可能会有猫腻,公证员可能被买通。
1.3、改进的随机数种子获取方式
事实上,有一些更简单的随机数种子的获取方式,只需要依赖于还未发生的指定事件的结果即可,比如:
- 股市点位以及成交额。尤其是成交额,完全没有操作的可能性。
- 多个城市气温等数据。
- 更复杂的可以用数字货币比如比特币的 HASH 值。这个的好处是很短时间就会有更新。
这些方式比起乒乓球摇号,更简单,更容易被验证,而且被操纵的可能性更小。
2、用户生成的抽奖
用户生成的抽奖很简单,每个用户给出一个数,然后将所有数加起来作为中奖数或者随机数种子即可。
这依赖于一个简单的数学事实:如果$x$为随机数,无论$y$是任何形式(只要与$x$无关),那么$x+y$也是一个随机数。
但每个用户必须确保自己的随机数不能被别人知道,否则别人可以根据它的随机数据生成自己的随机数,从而操纵最终的结果。因此我们需要有一个协议,确保别人无法依赖自己的随机数,也不能修改自己的随机数。
要达成这一点并不难:
- 在指定的第一阶段截止时间之前,每个用户公布自己的随机数的 HASH 值。如果随机数比较小,可以后面加一些冗余信息再计算 HASH 值。
- 第一阶段截止之后进入第二阶段。在第二阶段截止时间之前,用户公布自己的随机数(以及冗余信息,若有)。
- 第二阶段截止之后,收集所有合法的随机数,综合起来得到单个随机数种子,用事先确定的随机数发生器,计算最终的抽奖结果。
不过这个方法也有一些瑕疵,第二阶段里有用户可以根据目前公布的随机数,来决定自己是否公布随机数,来操纵最终的结果。唯一的解决方法是强制第一阶段公布了随机数 HASH 值的用户,必须在第二阶段公布原始随机值。
Q. E. D.