抛砖引玉：如何实现绝对公平的年会抽奖程序

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

爱意满满的作品展示区。

这是一个创建于 2859 天前的主题，其中的信息可能已经有所发展或是发生改变。

传统的抽奖系统都是运行在单机上，那么这台设备就可能被做过手脚，抽奖的结果也不能令所有人信服。如果能在每个人的设备上都运行一次抽奖的话，这样结果就可以令大家信服了 —— 但显然不能简单地这样做，因为每个人抽出的结果都是不一样的。

于是我想能否利用我在区块链中了解到的「两阶段广播」来产生去中心化的随机数？让这个抽奖程序以分布式的方式运行在所有人的设备上，会有一个后端服务器帮助客户端进行广播，但没有任何特权，每个客户端都会对抽奖过程进行验算，一旦有人作弊就会被发现。

于是我实现了这样一个原型（https://rollup.leanapp.cn，大家可以开两个窗口体验一下），源代码和更详细的算法描述在 https://github.com/jysperm/rollup，不过目前还有一些问题：

目前只要有人执意捣乱，那么抽奖将一直都无法完成
我还没彻底想清楚如果后端没有公正地进行广播，会有怎样的影响

关于两阶段广播：

Ethereum 中的随机数生成器 https://github.com/randao/randao
BlockChain 与 Ethereum 介绍 https://jysperm.me/2016/05/blockchain-slides/

第 1 条附言 · 2017-02-19 16:33:23 +08:00

我又写了一篇更加详细的介绍 https://jysperm.me/2017/02/distributed-random-rollup/

抽奖

ethereum

广播

后端

38 条回复 • 2017-02-03 17:45:14 +08:00

HLT

2017-01-24 20:20:17 +08:00

酷

shiny

2017-01-24 20:26:43 +08:00

难度在于让大家相信你是公正的

MOxFIVE

2017-01-24 20:39:09 +08:00

参考各类 1 元夺宝抽奖，把下期福彩结果当变量

loading

2017-01-24 21:14:53 +08:00 via Android

每人预先分配一个号码，然后用你们公司主要语言的 random 函数，现场跑。

lhbc

2017-01-24 21:19:23 +08:00

算法和代码公开，随机数现场获取。

h4x3rotab

2017-01-24 21:22:24 +08:00 via iPhone

看来能理解 blockchain 的人还是太少了

takashiki

2017-01-24 21:22:37 +08:00

先抽了一拨小奖之后有其他人加入的情况下，每个人抽到大奖的概率相等么？

cunkouwdy007

2017-01-24 21:51:09 +08:00 via Android

记得国外有个专业研究真随机数的机构做了个生成真随机数的网站，也许可以用那个？

ykrl089

2017-01-24 21:56:34 +08:00

类似彩票，弄一堆球滚下，估计算是目前来说最公平的了。

just4test

2017-01-24 22:21:05 +08:00

我曾经设想过如何构建绝对公平的赌博程序。原理跟楼主的一样。

jybox

2017-01-24 23:18:36 +08:00

@takashiki 我这个算法是要等人齐了才会开始抽的。

@cunkouwdy007 @loading @lhbc random.org 么？其实还是解决不了我一开始提出的问题：既然随机数是在一台设备上产生的，如何确定这个设备（编译器、浏览器、 HTTP Client ）没有被做过手脚呢。

@MOxFIVE 使用股票、比特币、福利彩票的结果应该算是实践上最简单可行的了。不过我们之所以认为他们可以信任，其实还是因为相比于一个年会抽奖，他们的体量太大了，去操纵的难度太大了，而不是说他们从理论上不可能被操纵。

lydasia

2017-01-24 23:20:43 +08:00

RqPS6rhmP3Nyn3Tm

2017-01-25 00:22:09 +08:00 via iPhone

@lydasia 虽然笑出声，但的确是正解
程序员就是容易把简单问题复杂化

Marfal

2017-01-25 00:46:49 +08:00

现场大屏幕手写

Arnie97

2017-01-25 01:08:42 +08:00

如果你只是想找个没被做过手脚的随机数发生器，我经常能捡到这个东西：

http://ww4.sinaimg.cn/large/a15b4afegy1fc27sh1prpj208w06oglj

lydasia

2017-01-25 01:13:23 +08:00

@Arnie97 这个哪是随机数，不过对咱来说可以当作是随机数。。

kslr

2017-01-25 01:52:54 +08:00

最无法伪造的随机数当然是 Random.org 了利用大气噪音来生成随机数,而大气噪音是空气中的雷暴所产生的

param

2017-01-25 03:10:43 +08:00 via Android

用不可控的產生方式不就可以了嗎。。。比如說用第三方的服務來產生，而不是自家的程序。

herozhang

2017-01-25 07:21:57 +08:00 via iPhone

@kslr 问题在于如何让人相信你真的访问了这个网站

nightv2

2017-01-25 08:17:09 +08:00 via Android

每个人发一样的奖品不就是绝对公平么

whale

2017-01-25 09:22:00 +08:00

@nightv2 仔细一想：每人发一样的，相对于会抽到大奖的那几位就不公平了。

那么，歪楼问下：世界上真有绝对么？

alexgor

2017-01-25 09:26:51 +08:00

绝对的公平在这个世界上不存在。

griffinqiu

2017-01-25 09:29:40 +08:00

https://jinshuju.net/apps/58660f6a4bf8fb44fcea35c4

用金数据现场抽奖应用呀

kslr

2017-01-25 15:11:08 +08:00 via Android

@herozhang 算法和数据是公开的的啊？个人也可以去对比啊

ryd994

2017-01-25 16:03:58 +08:00 via Android

hash 多个随机量
比如领导敲时间，这一时刻的现场测得的温度，到场人数，噪音等等，
事先审查设备，事后可以记录重放
然后再把 hash 值域投射到票上（取模？还是其他？）
只要有足够的熵，就算有人操纵其中有一两个，剩下的熵会把效果盖掉，这就是 linux 下 /dev/random

ryd994

2017-01-25 16:07:42 +08:00 via Android

hash 多个随机量
比如领导敲时间，这一时刻的现场测得的温度，到场人数，噪音等等，
事先审查设备，事后重放记录
然后再把 hash 值域投射到票上（取模？还是其他？）
只要有足够的熵，就算有人操纵其中有一两个，剩下的熵会把效果盖掉，这就是 linux 下 /dev/random 的设计思想
Intel 处理器有个黑盒随机数发生器，当时有人质疑并希望内核拒绝使用。后来也是用了，解释是，反正一样进熵池，就算有猫腻，其他熵源一样盖掉

不过讲真，把年会搞成随机数据生成器审计大会，领导不会打死你？

maomo

2017-01-25 16:18:15 +08:00

现场抽签不好吗。。。

maomo

2017-01-25 16:32:45 +08:00

你这个问题在数学上等同于多方如何共同生成一个随机数 http://crypto.stackexchange.com/a/465

herozhang

2017-01-25 18:56:57 +08:00

@kslr 例如，我部署一个 DNS 服务器，把 random.org 的解析指向我自己假设的这个假服务器，看代码和数据是不能发现作弊的。

CRVV

2017-01-25 19:14:08 +08:00

@herozhang
random.org 有 DigiCert 签的证书
我觉得如果能信任浏览器和操作系统是正经的，通过证书就能确定不是假网站

kslr

2017-01-25 19:25:52 +08:00

@herozhang #29 哥们，我觉得你进入了一个误区。首先回到题目上，公平的抽奖。
首先通过公开的随机数种子来产生结果，如果用户不接受就可以用种子重新走一遍算法来验证。
那么不管你在程序中是如何的作弊，都无法逃避结果不一致的问题。

把过程透明化足以！

暗箱操作？你能控制雷暴？对吧。

至于程序那只不过代替人工做一道题而已。