是否存在通过算法保证公平的抽奖模式？

[LeeReamond]

如题，由彩票问题引发的思考，如今网络上各种抽奖、彩票等等，是否存在使用算法保证公平的方式？一定要用传统的迷之机器物理摇号+不公正的公证员吗？

想了想，感觉一个简单的想法是使用所有参与抽奖者的信息做总和哈希，生成一段指向唯一中奖者的秘钥。这样每当有新的参与者加入，总和哈希都会变化，使得秘钥不可控。

但是这种方式似乎无法防止枚举作弊，也就是比如如果我想让第 1001 号抽奖者中奖的话，如果我有足够的算力，我可以穷举哪种组合下哈希会指向 1001 ，然后得到结果后按图索骥，伪造一些虚拟身份参与抽奖。

老哥们有无看法？

贴个条总结一下目前为止的讨论：

PARTA-真随机数生成算法

1. 金融数据，例如大盘收盘价（在大多数情况下具有随机性。极端情况下但单一市场存在被操纵可能性，多市场的话由于收盘时间不同步，时间最晚的市场具有决定性话语权）
2. 需要传感器侦测的自然界数据：例如大气噪声，太阳黑子等，可以保证目前人类科技下无法预测。（绝大多数情况下具有随机性。缺点是数据采集依赖传感器，此过程大多数时候需要依赖第三方机构，极端情况下无法保证结果可信）
3. 区块链哈希值，原理为利用未来某一时间一定会出现但大家都无法预测的某一哈希，在广谱算力的支持下实用性良好，几分钟就可以开一次奖，不像上文大气数据那样比较难采集（绝大多数情况下具有随机性，但楼里有人说哈希攻击也很常见，其实我不是很理解攻击的原理）
4. 其他自然界数据，例如使用全国各城市温度湿度和pm2.5的字符串和做哈希。（绝大多数情况下具有随机性，现实生活中可用性良好，同样需要依赖第三方机构采集，唯一区别是采集机构可能是公有而非私营性质机构。）

PARTB-合同抽奖算法

1. 目前认为的可靠方式是由所有参与抽奖的用户各提供一段自定义秘钥，使用字符串总和做哈希而后选取中奖者。每当有新加入的抽奖候选人时结果都会被改变，使其不可控。
2. 这个方法的缺点在于信息对服务提供商本身单项透明，服务提供商在掌握全部信息的情况下可以通过预计算和添加伪造抽奖人的方式影响抽奖结果。
3. 一个可行的补救方案是，类似密码“加盐”方案，用户不向服务商提供自定义秘钥本身，而是提供秘钥的哈希值，而开奖时则公开本身秘钥并以此为基础计算总和哈希，提前提交的秘钥哈希类似一种预声明，后提交的本体类似一种验证，可以保证服务商本身无法掌握。
4. 但是上述抽奖需要用户交互两次，比较复杂，也不能实时开奖。有朋友提出用软件封装并简化服务，那么软件的可靠性又是新的安全隐患，也许需要配套开源+可自行编译的软件系统。

结论

目前为止OP认为技术上保证可靠的（没有人能操纵结果的）抽奖方式为：利用预先声明哈希+开奖时提交秘钥的抽奖方式。使用开源可自编译的程序封装该服务以简化操作。同时在开奖时，在计算总和哈希的结果时加入不可预测数据。具体操做上例如限定开奖时间到每天15点，在计算哈希时额外加入当天大盘收盘点数，同时该时间点在下午，一般全国各省市已经达到当日最高气温，可以额外加入所有地级市当日最高气温。

OP认为这个方法具有实际可行性，类似彩票这种具有重大利益相关的开奖使用这套方法应该也可以确保难以被操纵。而普通参与者检测结果是否可靠的方法是，由于抽奖结果和算法的信息都完全透明，普通参与者可以通过检查自己的参与信息是否被准确公示，来验证结果是否可靠。

[phpfpm]

找一些大家无法控制的数字，比如股市收盘

[zooo]

web3 应该已经有抽奖的智能合约了吧（个人猜测）

你找找

每增加一位抽奖人都会成为一个随机源，保证公平

[LeeReamond]

@phpfpm 金融行业从业人员似乎并不认为股市收盘无法控制。。。也许太阳黑子爆发之类的东西无法预测？但是不具备实用性啊

[tool2d]

随机数生成器不是挺好用的，好像 linux 有那种无法预测的真随机数。

[Deplay]

之前看过，实时大气数据作为随机数种子，考虑到地球是一个混沌系统，应该可以认为完全随机

[Deplay]

补充一下，还有通过 cpu 的噪音，温度，频率来实现的

[Ericcccccccc]

用股票指数当答案, 至少可以防止操纵结果.

[cmdOptionKana]

股市可以，如果单一市场怕操控，可以把多个国家的股市加在一起，我就不信有人能控制全球股市。

[phpfpm]

@LeeReamond 当然能控制，但是得花钱。。

[ffgrinder]

@LeeReamond 来，你告诉我怎么个控制法？

[chendy]

引入足够多的随机因子做随机即可

[myd]

确实有点难想，随机数需要公开（可观测）、不可控。类似于计算机生成随机数、太阳黑子、温度都存在观测设备被控制的可能

[hamsterbase]

挖矿。 工作量证明

[hamsterbase]

以拿比特币最新的 hash 作为随机因子。 这个是无法被控制，全球公开的。

[swulling]

上面的歪楼了，这个问题的关键不在于所谓的真随机数，而在于可以独立复现结果。

什么意思呢，假如真有一个真随机数，基于这个随机数设计了抽奖程序，那么谁知道你的程序里玩了什么猫腻？靠第三方审查代码又会陷入信任陷阱。

这个问题的关键是你开源一个抽奖程序，然后程序的种子必须是未来某个时刻产出的随机数，产出过程无法被控制，产出结果全网可看且不可篡改。

巧了，比特币挖的新块的 hash 值就符合这个要求。所以才有数字货币智能合约。

[LeeReamond]

@swulling 所以比特币是通过全网算力保证在未来某时刻一定会出现这样一个符合要求的 hash ，不过似乎无法普及到大部分抽奖都采用？

[rekulas]

总和哈希并不安全,有些区块链抽奖就用的这个方式,已经有多起攻击案例

目前我了解最为安全的应该是"承诺"的方式
例如随便想个简单模式,之前在知乎也回答过

用户 a 选择了一个号码比如 784516 ，再自己创建一个随机数例如 32 位的 de90fcea....，再将号码和当期期号和随机数一起进行 sha256 计算指纹，然后你将指纹提交给彩票中心购买该指纹的所有权，这样彩票中心只知道你的指纹没法知道你的号码。

开奖就简单了，开奖后彩票中心通知中奖号码是 784517 ，购买过彩票的用户都开始上传自己的原始信息-彩票号码、期号、随机数，(sha256 的计算复杂性也保证了用户没办法现场计算一个虚假的信息来冒充中奖信息-超算都没法)，彩票中心收到信息之后告知你的号码只错了一位得了一等奖。

有没有漏洞? 还是存在的,中心可以进行自我攻击创建多个中奖号码,但至少解决了中心知晓每个号码的问题-这样对平台来说没办法修改中奖率了,如果彩票敢这样玩,我也敢每期买.

要想彻底防范感觉还是引入三方随机数生成,或者基于多个可信分布式秘钥(或类似门限签名)来组合生成最终中奖结果,空了我再想想

[chenjia404]

很简单，未来某个比特币的区块哈希做随机数。

[louisxxx]

你说你公平 但没人信你啊

[LeeReamond]

@rekulas 合理，但是用作抽奖的话用户需要进行两次交互，太麻烦了，但是可能是目前为止的最优解了

[moioooo]

用开奖时间或者指定时间的区块链哈希来确定中奖者呀。这种方法已经用了很久了。
btc 网络保证了哈希数的公开、不可预测，剩下的只要保证智能合约的算法公开透明就行，而后者根本就不难

[rekulas]

@LeeReamond 这个只是技术上麻烦,但是算法应当公开,通过应用或 app 封装整套流程,对普通用户来说跟普通抽奖没有区别,而有技术的团队也可以验证和监督该过程

[rekulas]

@moioooo 区块链没法创造随机数,所以很容易被攻击
参考合约用 hash 开奖的,经常都有被攻击的新闻,这还是暴露出来的,没有暴露的不知道有多少

[gpt5]

除了随机，还要保证是均匀分布。
上面很多人说的那些随机数，可能确实是“真随机”，但也需要证明是均匀分布的。
比如你有 3 个人抽奖，即使是真随机，但如果 p(x=1)=.4, p(x=2)=.3, p(x=3)=.2 的话，就不公平了。

[xuanbg]

没有算法才是真的公平，譬如，直接给个无法被人为操控的随机数。

[swordmaster]

彩票抽奖一定要使用传统的机器物理摇号+公证员这套系统，原因很简单，就是因为彩票的主要受众群体的认知基本都能理解物理随机摇号，却理解不了复杂算法是否能保证公平，你使用算法计算出来的中奖号码反而会被认为会不会存在暗箱操作。物理摇号机至少是透明材质的，大家能看到号码是怎么出来的。因为彩票系统设计的时候已经预留了利润空间，就算不作弊也能获得很高的利润，没必要故意设计一个方便作弊的系统。只不过人性是贪婪的，利益相关方不满足于被分配的利益，开始把手伸向奖金池。。。

[Mohanson]

彩票中心是否是真随机对于解决这个问题意义很小, 有密码学手段, 即使彩票中心手动控制中奖号码依然是安全的.

1. 用户选择彩票号码, 将该彩票号码视作多项式, 求该多项式的卡特承诺
2. 彩票开奖号码公开
3. 用户使用卡特证明, 证明开奖号码位于自己的多项式上.

结束.

[lingeo]

@phpfpm 区间太小了吧。

[sss15]

游戏抽卡一点都不公平

[huangqihong]

@swordmaster 说的很对啊，你搞系统，大家反而不懂，认为造假的概率更大；哈哈哈，谁知道，国内没有牛顿定律

[Cosmic4764]

你们都在纠结算法，就没人在意什么算公平么？

[c3de3f21]

@sss15 确实

[wwbfred]

@gpt5 算法上加权就行了。你没想明白随机的本质，实际上我们只需要 0 和 1 两个变量按照任意概率随机产生，剩下的都可以用算法搞定。

[huangqihong]

想到一个问题：你搞了一个公平算法的系统，突然有一天，领导要求你内定谁谁谁，你怎么说？不行还是拒绝？

[wwbfred]

@cmdOptionKana 不行，不是所有股市都是同时闭盘的。假设 h=f(x,y,z)，当其中任意两个变量固定下来时，只需要操作第三个变量即可控制函数的输出，这就意味着谁掌握了最晚闭盘的股市谁就赢了。

[rossroma]

其实保证公平的方式有千千万，之所以经常有不公的新闻报道，无非使抽奖平台自己不想公平。让抽奖平台自己来保障公平性，不就是既当裁判员又当运动员吗？
行之有效的办法绝对不是什么算法，即便算法绝对公平了，平台方也可能在其上下游做手脚。
我想到的方法是公证员不能由平台方聘请，而是由抽奖者聘请，代表消费者的利益。并且签下违约条款，一旦失职需要巨额赔偿消费者，并让保险公司来兜底。
实际执行层面，每一期彩票消费金额划出固定的比例给到公证处，公证处分出一部分用来购买保险，只要公证处恪守本分，这就是一笔稳赚不赔的买卖，而一旦有坏心思，后果将非常严重。
这里的关键点是：公证处由消费者来指派而非平台方、平台、公证处和保险方必须各种独立，不得有股权或利益关联。

[weeiy]

不是，真想这个“主要为了赚钱，次要以公益正名”的博彩行业以公平来对待你啊？

[chenjia404]

@LeeReamond #16 比特币不是保证未来某时刻一定会出现这样一个符合要求的 hash ，而是每个区块需要符合一个工作量证明即可，让这个区块哈希有多少 0 结尾。

[mcluyu]

算法公不公平普通人信吗？ 耳听为虚眼见为实， 盯着看的摇奖机都能造假， 更何况根本没几个买彩票的人能理解的各种看不见的算法了

[8520ccc]

多随机因子即可：
例如：
1. 区块哈希值
2. 彩票开奖号码
3. 开奖方提前公布随机因子的密文

还可以加入更多

……
得到全部信息后，使用加密算法再通过开奖方提供的随机因子进行一次加密

[snarkprayer]

挺难的，想起来机核关于投票机制的一期博客，https://www.gcores.com/radios/120273 在同样的投票结果下，不同的投票机制会导致完全不同的结果

[Shintaku]

北京小客车摇号科学吗

[NoOneNoBody]

你理解错了，用传统机器的原因是“可展示”，并非电子方式公平性更差
只要是“人”完成抽奖的某些步骤，就有作弊的可能，要完全防止，需要“足够多”的审视，这个“足够多”很难界定

[epicnoob]

单就彩票来说，买彩票的有多少懂“算法”，什么“股市收盘”也可能没接触过。小球掉下来是几就是几，简单易懂，谁觉得不公平不买就是了。

[iqoo]

《怎样的中奖算法能让人信服》 https://www.cnblogs.com/index-html/p/trusted-lottery-algorithm.html

[jybox]

我之前就这个话题写过一篇文章，也做了一个 Demo
https://jysperm.me/2017/02/distributed-random-rollup/

思路和楼主差不多，就是让每个参与者都贡献一个随机数来影响最终的随机数，只要把整个过程记录下来，那么结果就是复现的。

[blinue]

https://www.random.org/
用大气噪声生成随机数

[rekulas]

@8520ccc 多随机因子只适用于黑盒中运行的系统（例如 linux 的熵池，相对黑客它是不可见的）
对于抽奖这种需要公开的模式，反而更危险，因子越多被攻击可能性越大，因为只要有任何一个点被成功攻击，其他的都形同虚设

[LeeReamond]

@rekulas 使用 APP 封装的话又出现一个 APP 是否可靠的问题，比较无解，也许还要配一套开源+信用的系统。原理上来说当然是只有秘钥永远储存在用户大脑里是最可靠的，只有当用户在校验时才提供这部分信息

[Vraw5]

歪个楼，让我想起来一个视频 大学生抽奖，现场写了代码跑抽奖 https://www.bilibili.com/video/BV11s4y1T7Qy/

[013231]

@ffgrinder 了解一下 2012 年 6 月 4 日的上证指数？

[nothingistrue]

抽奖的公平，最看重的是不被少数人控制。所以不要相通过任何算法、编程、或者高科技的东西来搞。你搞得越高级，用得人越看不懂，而看不懂就等同于暗箱操作。就算用的人都是高级程序员都能看懂，但是越高级验证难度越高，最后还是等同于暗箱操作。

举个简单的例子。“迷之机器物理摇号+不公正的公证员”，这个证假的难度只是没法去现场验证，如果能去的话，那随便找个小学生就能证假。而如果你搞了高科技算法，那绝大多数人是无法证假的。

[moonrailgun]

@nothingistrue 不是很认可你的看法。只要算法是公开的可证的，那么所谓的高科技算法，只要结果是可复现的，那么就是可信的。就像有无数人可以监督你，对于试图造假的人来说这是一种不可控的监视。

当然如果你这所谓的高科技算法高到全球只有有限的几个人且哪怕原理告诉所有人也没人学会的水平那当我没说。

[LeeReamond]

@013231 与个人认知水平有关 ，认知水平局限在那里，这种人你跟他说什么他听不懂的

[r6cb]

真随机数还是要靠现实世界吧，比如 https://www.random.org

[rekulas]

@LeeReamond 不会,app 只是方便普通用户使用,但技术圈肯定会对数据做校验的,app 层没法作弊,因为算法都是开源的
就像区块链钱包一样,你可以用官方钱包,可以用开源钱包甚至可以直接网页钱包,只是方便普通人使用,但你要是敢乱来,只要一次产品就死了

[rus4db]

我的解决方案： https://github.com/bd4sur/HackRF-Lottery

[ffgrinder]

@LeeReamond #52 笑麻了，十一年前的，没有任何人有意控制指数的前提下，甚至没有人敢公开声明"我今天要把指数操纵到这个点位"的前提下，收盘搞了个数字，就是“可以控制了”。

轮子是这样的。

[ffgrinder]

@013231 #49 笑麻了，十一年前的，没有任何人有意控制指数的前提下，甚至没有人敢公开声明"我今天要把指数操纵到这个点位"的前提下，收盘搞了个数字，就是“可以控制了”。

轮子是这样的。

@LeeReamond 误点到你了

[Mastercvmo]

温度，湿度，这样的真正随机变量才可以。

[rickiey]

搜索分布式随机数 DRAND, 直接用其他熵联盟的

[uni]

股票收盘价是可以控制的，不难的
还是上区块链最稳妥，链上抽奖就行了

[8520ccc]

@LeeReamond 想多了 我说了 最终还是要通过随机因子进行加密的，即使部分人作弊，也没用，除非全部人一起作弊

（全部随机因子都被空值那就不必说啥了吧？）