公平可验证的抽奖协议

作者: , 共 1530 字
系列:机器统治世界

查看该系列所有文章

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

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

1. 北京车牌摇号算法

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

1.1. 抽奖程序

其抽奖程序为

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

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

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

1.2. 北京车牌摇号的瑕疵

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

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

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

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

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

2. 用户生成的抽奖

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

这依赖于一个简单的数学事实:如果\(x\)为随机数,无论\(y\)是任何形式(只要与\(x\)无关),那么\(x+y\)也是一个随机数。

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

要达成这一点并不难:

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

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

Q. E. D.

系列: 机器统治世界 »
机器统治世界提到,随着科技的发展,我们可以直接用机器来替代政府。所谓机器统治世界,并不意味着机器是世界的主人。机器还是听命于人类,只不过以一种无法被干预的民主投票的方式。所以,机器统计世界的第一要解决的问题就是投票协议。
想起比多中心的匿名投票协议,有一种很简单的使用盲签名的投票协议,可以做到匿名投票。
类似文章:
碎碎念 » 车牌摇号
北京车牌摇号人数已经逼近 100 万,我之前测算「北京摇中号有多难」所设立场景的上界。现在看来我的估计还是有些保守。这个政策执行了一年多,争议比较大。我总结了一下比较流行的看法,大家可以对号入座:
今天一个朋友向我提起他参与北京买车摇号,他自己和周围十来人都没有摇中的事情,我关注了一下摇号的一些数据。
机器统治世界提到,随着科技的发展,我们可以直接用机器来替代政府。所谓机器统治世界,并不意味着机器是世界的主人。机器还是听命于人类,只不过以一种无法被干预的民主投票的方式。所以,机器统计世界的第一要解决的问题就是投票协议。
相似度: 0.083
最近《流浪地球》的热映,掀起了科幻热潮。很多人都在为电影和小说里的情节和逻辑争论不休。而我更感兴趣的是政府形态。
机器统治世界,其中一个重要的部分便是安全计算。而这一领域的开创性工作便是姚期智先生的「姚氏百万富翁问题」。相关的工作发表于 1982 年 FOCS 上的的《Protocols for secure computations》
风险管理 » VaR Primer
一个场景是所有风险因子的表现序列。历史场景是指风险因子在历史上某天的实际表现,随机场景则是计算机随机模拟生成的。通常蒙特卡洛模拟法需生成至少 1000 个随机场景,然后计算组合在每个场景下的损益,最后取 5%分位点得到组合的 VaR 值。
想起比多中心的匿名投票协议,有一种很简单的使用盲签名的投票协议,可以做到匿名投票。
IT » 比特币
最近 bitcoin 很火,我也是最先从云风那里了解到的,后来发现李笑来&霍炬对其都有涉及。不过他们对其具体技术原理的描述还是不够细致,所以我自己把bitcoin wiki又重新看了一遍。 看完之后,疑惑挺多,我对这个体系远没有前面三位这么乐观。诚然,它会成为"Geeks "手中的玩物甚至灰色交易的工具,但要说的达到「一出天下反」的程度,那还需要解决一些技术和金融方面的问题。
IT » 比特币, 数字货币
最近看到一篇文章Satoshi』s Genius: Unexpected Ways in which Bitcoin Dodged Some Cryptographic Bullets,国内有人翻译过(中本聪的天才:比特币以意想不到的方式躲开了一些密码学子弹)。里面说的第一个就是天才的中本聪并不是将公钥而是将公钥两次 HASH 之后作为比特币账户的地址,这可以让比特币系统抵抗量子计算机的攻击。
比特币协议里使用了 ECDSA (椭圆曲线签名算法),我之前以为它和基于大数分解的 RSA 公钥密码体系差不多。这两天看了下维基百科,才发现它们之间的差异挺大。
最近在知乎上看到一篇回答,提到中国的人才踩踏效应。我以前也有类似看法。其实不光人力资源上,在商业模式上也是如此,共享单车就是一个典型的例子。作者写得很清楚,复制过来保留一份备份。
数学 » 奥数
这次中国队在罗马尼亚数学大师赛败北,引起巨大的舆论论战,甚至上了人民日报的评论。以前从来没出现过这种情况。作为吃瓜群众,觉得特别有意思。