V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
jybox
V2EX  ›  分享创造

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

  •  
  •   jybox ·
    jysperm · 2017-01-24 20:11:18 +08:00 · 9592 次点击
    这是一个创建于 2620 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

    关于两阶段广播:

    第 1 条附言  ·  2017-02-19 16:33:23 +08:00
    我又写了一篇更加详细的介绍 https://jysperm.me/2017/02/distributed-random-rollup/
    38 条回复    2017-02-03 17:45:14 +08:00
    HLT
        1
    HLT  
       2017-01-24 20:20:17 +08:00
    shiny
        2
    shiny  
       2017-01-24 20:26:43 +08:00
    难度在于让大家相信你是公正的
    MOxFIVE
        3
    MOxFIVE  
       2017-01-24 20:39:09 +08:00   ❤️ 1
    参考各类 1 元夺宝抽奖,把下期福彩结果当变量
    loading
        4
    loading  
       2017-01-24 21:14:53 +08:00 via Android
    每人预先分配一个号码,然后用你们公司主要语言的 random 函数,现场跑。
    lhbc
        5
    lhbc  
       2017-01-24 21:19:23 +08:00
    算法和代码公开,随机数现场获取。
    h4x3rotab
        6
    h4x3rotab  
       2017-01-24 21:22:24 +08:00 via iPhone   ❤️ 1
    看来能理解 blockchain 的人还是太少了
    takashiki
        7
    takashiki  
       2017-01-24 21:22:37 +08:00
    先抽了一拨小奖之后有其他人加入的情况下,每个人抽到大奖的概率相等么?
    cunkouwdy007
        8
    cunkouwdy007  
       2017-01-24 21:51:09 +08:00 via Android
    记得国外有个专业研究真随机数的机构做了个生成真随机数的网站,也许可以用那个?
    ykrl089
        9
    ykrl089  
       2017-01-24 21:56:34 +08:00
    类似彩票,弄一堆球滚下, 估计算是目前来说最公平的了。
    just4test
        10
    just4test  
       2017-01-24 22:21:05 +08:00
    我曾经设想过如何构建绝对公平的赌博程序。原理跟楼主的一样。
    jybox
        11
    jybox  
    OP
       2017-01-24 23:18:36 +08:00   ❤️ 1
    @takashiki 我这个算法是要等人齐了才会开始抽的。

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

    @MOxFIVE 使用股票、比特币、福利彩票的结果应该算是实践上最简单可行的了。不过我们之所以认为他们可以信任,其实还是因为相比于一个年会抽奖,他们的体量太大了,去操纵的难度太大了,而不是说他们从理论上不可能被操纵。
    lydasia
        12
    lydasia  
       2017-01-24 23:20:43 +08:00   ❤️ 1
    RqPS6rhmP3Nyn3Tm
        13
    RqPS6rhmP3Nyn3Tm  
       2017-01-25 00:22:09 +08:00 via iPhone
    @lydasia 虽然笑出声,但的确是正解
    程序员就是容易把简单问题复杂化
    Marfal
        14
    Marfal  
       2017-01-25 00:46:49 +08:00
    现场大屏幕手写
    Arnie97
        15
    Arnie97  
       2017-01-25 01:08:42 +08:00
    如果你只是想找个没被做过手脚的随机数发生器,我经常能捡到这个东西:

    http://ww4.sinaimg.cn/large/a15b4afegy1fc27sh1prpj208w06oglj
    lydasia
        16
    lydasia  
       2017-01-25 01:13:23 +08:00
    @Arnie97 这个哪是随机数,不过对咱来说可以当作是随机数。。
    kslr
        17
    kslr  
       2017-01-25 01:52:54 +08:00
    最无法伪造的随机数当然是 Random.org 了 利用大气噪音来生成随机数,而大气噪音是空气中的雷暴所产生的
    param
        18
    param  
       2017-01-25 03:10:43 +08:00 via Android
    用不可控的產生方式不就可以了嗎。。。比如說用第三方的服務來產生,而不是自家的程序。
    herozhang
        19
    herozhang  
       2017-01-25 07:21:57 +08:00 via iPhone
    @kslr 问题在于如何让人相信你真的访问了这个网站
    nightv2
        20
    nightv2  
       2017-01-25 08:17:09 +08:00 via Android
    每个人发一样的奖品 不就是 绝对公平么
    whale
        21
    whale  
       2017-01-25 09:22:00 +08:00
    @nightv2 仔细一想:每人发一样的,相对于会抽到大奖的那几位就不公平了。

    那么,歪楼问下:世界上真有绝对么?
    alexgor
        22
    alexgor  
       2017-01-25 09:26:51 +08:00
    绝对的公平在这个世界上不存在。
    griffinqiu
        23
    griffinqiu  
       2017-01-25 09:29:40 +08:00
    kslr
        24
    kslr  
       2017-01-25 15:11:08 +08:00 via Android
    @herozhang 算法和数据是公开的的啊?个人也可以去对比啊
    ryd994
        25
    ryd994  
       2017-01-25 16:03:58 +08:00 via Android
    hash 多个随机量
    比如领导敲时间,这一时刻的现场测得的温度,到场人数,噪音等等,
    事先审查设备,事后可以记录重放
    然后再把 hash 值域投射到票上(取模?还是其他?)
    只要有足够的熵,就算有人操纵其中有一两个,剩下的熵会把效果盖掉,这就是 linux 下 /dev/random
    ryd994
        26
    ryd994  
       2017-01-25 16:07:42 +08:00 via Android
    hash 多个随机量
    比如领导敲时间,这一时刻的现场测得的温度,到场人数,噪音等等,
    事先审查设备,事后重放记录
    然后再把 hash 值域投射到票上(取模?还是其他?)
    只要有足够的熵,就算有人操纵其中有一两个,剩下的熵会把效果盖掉,这就是 linux 下 /dev/random 的设计思想
    Intel 处理器有个黑盒随机数发生器,当时有人质疑并希望内核拒绝使用。后来也是用了,解释是,反正一样进熵池,就算有猫腻,其他熵源一样盖掉

    不过讲真,把年会搞成随机数据生成器审计大会,领导不会打死你?
    maomo
        27
    maomo  
       2017-01-25 16:18:15 +08:00
    现场抽签不好吗。。。
    maomo
        28
    maomo  
       2017-01-25 16:32:45 +08:00
    你这个问题在数学上等同于多方如何共同生成一个随机数 http://crypto.stackexchange.com/a/465
    herozhang
        29
    herozhang  
       2017-01-25 18:56:57 +08:00
    @kslr 例如,我部署一个 DNS 服务器,把 random.org 的解析指向我自己假设的这个假服务器,看代码和数据是不能发现作弊的。
    CRVV
        30
    CRVV  
       2017-01-25 19:14:08 +08:00
    @herozhang
    random.org 有 DigiCert 签的证书
    我觉得如果能信任浏览器和操作系统是正经的,通过证书就能确定不是假网站
    kslr
        31
    kslr  
       2017-01-25 19:25:52 +08:00
    @herozhang #29 哥们,我觉得你进入了一个误区。首先回到题目上,公平的抽奖。
    首先通过公开的随机数种子来产生结果,如果用户不接受就可以用种子重新走一遍算法来验证。
    那么不管你在程序中是如何的作弊,都无法逃避结果不一致的问题。

    把过程透明化足以!

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

    至于程序那只不过代替人工做一道题而已。
    zingl
        32
    zingl  
       2017-01-25 23:36:29 +08:00
    程序员就是矫情,我是领导我就给你们分发机选双色球
    byuc
        33
    byuc  
       2017-01-26 16:47:10 +08:00
    这个的难点不在于技术,只在于没有抽中的人,永远都是不会相信这是公正、机会均等的。
    nomorelie
        34
    nomorelie  
       2017-01-26 17:40:07 +08:00 via Android
    请相关个部门公证啊,设备物理隔离印章封条
    ranleng
        35
    ranleng  
       2017-01-26 19:00:33 +08:00 via Android
    微信红包 手气最佳?
    maplerecall
        36
    maplerecall  
       2017-01-26 19:37:50 +08:00 via Android
    说到年会抽奖…我特么年会前一周接到需求要做个抽奖需求,设计稿还拖了两天,年会前两天还突然改需求,结果最后一周什么正经事都没做就撸抽奖了……

    由于要放到大屏幕上两千人看抽奖页加了各种特效,活生生做成个烤机页面,啥手脚都没动最后自己啥都没中,简直 sad ……
    MrFireAwayH
        37
    MrFireAwayH  
       2017-01-27 13:45:27 +08:00 via Android
    我们公司是自己先选喜欢的实体扑克牌……抽奖的时候去另一个新的那里抽……抽出来和自己选的一样就中奖……

    奖品是抽之前就确定了的

    每个等级的抽奖都参与
    appstore001
        38
    appstore001  
       2017-02-03 17:45:14 +08:00
    开奖部分开源,代码 MD5 等多种方式检验,确保运行的 EXE 或网站源码未经修改。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1343 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 23:38 · PVG 07:38 · LAX 16:38 · JFK 19:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.