公平可验证的抽奖协议

今天北京车牌摇号开奖，如果只有一倍概率，中签概率只有万分之四，估计这一辈子都中不了吧。北京车牌目前有巨大的利益，组织者如何保证其中没有猫腻呢？

在机器统计的世界里，随机抽奖也是重要的协议。比如陪审团人员的随机选取等等，就需要用到该协议，来确保其中没有被操纵。

1. 北京车牌摇号算法

北京车牌摇号使用了公平可验证的抽奖协议，其程序和备选号名单是公开的。每个人都可以下载程序和数据，对抽奖进行验证。极大地缓解了公众的质疑。

1.1. 抽奖程序

其抽奖程序为：

1. 把所有当月审核通过的申请码（ 13 位数）按照从小达大排列，并从 1 开始编号，设最大编号为NN（ 2019 年 2 月NN为 15175162 ）。在这一步中，有多个中签几率的申请码，会相应得到多个不同的编号。
2. 在公证员的公正下，由 6 个人随机摇出 6 个小球，得到 6 位随机种子。
3. 计算机用 .NET Framework 2.0 的 System.Random 类新建一个实例，输入上述 6 位随机种子。4. 每次调用Random.Next(int maxValue)函数产生一个[0,N)[0,N)的整数，对应于上述[1,N][1,N]的编号，查出相应的申请码。验证这个申请码是否已经抽到过，以次避免重复抽到一个编号，或者抽到同一申请码的多个编号。如果这个申请码未被抽到过，则保存到抽中的结果中。
4. 重复执行 4 ，直到抽中了当月所有指标为止。

.NET Framework 中的随机数属于伪随机数，即给定相同的随机种子，可以得到相同的抽签结果，这就是为什么大伙可以自己在家用电脑验证抽签结果。

程序用到的随机数种子只有 100 万中可能性。用户在抽奖前，即可运行程序，枚举随机数种子，统计自己的中奖概率，可能和平均值会略有差异（不过差异极小）。

1.2. 北京车牌摇号的瑕疵

上面的协议里有个巨大的依赖性，最核心的 6 位随机数种子依赖于乒乓球的随机性和公证员的公正，破坏了公平性。因为乒乓球可能会有猫腻，公证员可能被买通。

1.3. 改进的随机数种子获取方式

事实上，有一些更简单的随机数种子的获取方式，只需要依赖于还未发生的指定事件的结果即可，比如：

1. 股市点位以及成交额。尤其是成交额，完全没有操作的可能性。
2. 多个城市气温等数据。
3. 更复杂的可以用数字货币比如比特币的 HASH 值。这个的好处是很短时间就会有更新。

这些方式比起乒乓球摇号，更简单，更容易被验证，而且被操纵的可能性更小。

2. 用户生成的抽奖

用户生成的抽奖很简单，每个用户给出一个数，然后将所有数加起来作为中奖数或者随机数种子即可。

这依赖于一个简单的数学事实：如果xx为随机数，无论yy是任何形式（只要与xx无关），那么x+yx+y也是一个随机数。

但每个用户必须确保自己的随机数不能被别人知道，否则别人可以根据它的随机数据生成自己的随机数，从而操纵最终的结果。因此我们需要有一个协议，确保别人无法依赖自己的随机数，也不能修改自己的随机数。

要达成这一点并不难：

1. 在指定的第一阶段截止时间之前，每个用户公布自己的随机数的 HASH 值。如果随机数比较小，可以后面加一些冗余信息再计算 HASH 值。
2. 第一阶段截止之后进入第二阶段。在第二阶段截止时间之前，用户公布自己的随机数（以及冗余信息，若有）。
3. 第二阶段截止之后，收集所有合法的随机数，综合起来得到单个随机数种子，用事先确定的随机数发生器，计算最终的抽奖结果。

不过这个方法也有一些瑕疵，第二阶段里有用户可以根据目前公布的随机数，来决定自己是否公布随机数，来操纵最终的结果。唯一的解决方法是强制第一阶段公布了随机数 HASH 值的用户，必须在第二阶段公布原始随机值。

Q. E. D.