LeanCloud 又在  招募新的小伙伴  了,来和精子一起工作吧。
归档 2017 年 2 月

Rollup: 去中心化随机抽奖程序

在春节前后,经常在社区中看到有关年会抽奖程序的讨论,其中抽奖的公平性是被大家讨论得最多的点。可能有的人会说可以用 random.org 来取随机数,的确这个网站可以保证数字的随机性,但如果访问 random.org 的浏览器位于一台计算机上,如何证明这个随机数确实来自 random.org 呢?如何确定这台计算机从软件到硬件、从操作系统到网络接口都没有被动过手脚呢

所以我们需要一种「可验证」的随机数生成算法,即 这个算法不应该是运行在单个设备上的,而是可以在不同的设备上多次运行,并且总是得到相同的结果,这样才能被大家信服 —— 每个人都可以在自己的设备上进行验算。

其实说来直接使用比特币下一个区块的 hash,或者股市收盘价格作为随机数是最简单、最具有可行性的做法了。但这并不是说比特币(矿工可以有选择性地提交区块来影响随机数)或股市不能被操控,而只是相对于我们的年会抽奖来说,他们的体量都太大了,去操控比特币或股市是不划算的。

于是我想能否利用之前了解到的去中心化和区块链的知识,来实现一个去中心化的、可验算的、难以操控的抽奖程序,让这个抽奖程序以分布式的方式运行在所有参与者的设备上,会有一个后端服务器帮助客户端进行广播,但本身没有特权,客户端会对随机数的产生过程进行验算,确保没有人作弊。

其实在 Ethereum(一个类似比特币的区块链)上已经有了非常成熟的 随机数生成器,它基于「两阶段提交」来实现,在第一阶段每个人生成一个随机数,并将这个随机数的 hash 广播出去;然后在第二阶段之前的参与者再广播随机数的明文,然后将所有参与者的随机数加到一起,形成一个无法被任何操纵的随机数。

这个算法的要点在于,在第一阶段中每个人都选定了一个数字,但广播的却是数字的 hash,也就是说你没办法知道其他人选定的数字,也就无法去构造特定的数字来影响结果;而在第二阶段大家才开始广播真正的数字,同时每个人都会使用之前的 hash 进行验算,保证这时的数字与第一阶段相同。

我将这个算法进行了细化,在浏览器中用 React 实现了客户端,再用 Node.js 实现了一个基于 WebSocket 的服务器来辅助广播。大家可以在 rollup.leanapp.cn 访问到这个原型(源代码和详细算法位于 jysperm/rollup),可以自己开多个浏览器窗口进行测试:

screenshot

如果有人捣乱会怎么样,比如在第二阶段广播了错误的数字或者根本没有广播呢?在 Ethereum 上这会给参与者带来经济上的惩罚。而在我们的原型中,我们只能做到感知到这些作弊的情况,然后中止抽奖,如果有人执意捣乱,就会导致抽奖一直无法完成了。

那是不是说这个原型已经做到无懈可击了呢?并不是,目前是使用单一的后端来实现广播,如果这个后端有选择性地不对特定的客户端广播一些消息,就会导致这个特定的客户端被孤立,和其他人产生不同的抽奖结果,而且这个被孤立的客户端也无从证明究竟是后端没有广播,还是自己忽略了广播。

更好的设计可能是通过真正 P2P 的方式进行广播,这样除非其他所有参与者联合起来孤立一部分人,否则其他参与者就可以从未参与攻击的人哪里得到正确的广播。然而真正的 P2P 其实是没办法实现的 —— 你总是需要一个用作服务发现的节点,同时也要考虑通讯信道的安全性,当前的密码学技术虽然可能保证消息不被篡改,但却无法保证消息不丢失。

关于区块链的更多知识可参考我之前的文章 BlockChain 与 Ethereum 介绍,其中也有对 Ethereum 上的随机数生成器的详细讨论。

1

精子生于 1995.11.25, 21 岁,英文 ID jysperm.

订阅推送

通过邮件订阅精子的博客日志、产品和项目的最新动态,精子承诺每一封邮件都会认真撰写(历史邮件),有想和精子说的话也可以直接回复邮件。

该博客使用基于  Hexo  的  simpleblock  主题。博客内容使用  CC BY-NC-SA 3.0  授权发布。最后生成于 2017-07-18.