Skip to content

November 27, 2018

1

网络上的抽奖如何保证公平性

作者: physixfan

//这篇文章是美国信用卡指南近期搞的一个抽奖活动所使用的方案,原文在这里


抽奖的公平性向来是抽奖活动中最受人质疑的部分。由于涉及随机数的选取,网上的抽奖活动几乎无法保证公平性,因为很难保证中奖号码是随机生成而非平台人工选取的,也很难保证平台是否删掉了一部分用户的中奖资格而未告知用户。例如:前阵子支付宝锦鲤活动就有人怀疑中奖者是否是钦定的;前阵子王思聪在微博平台上的抽奖,中奖者男女比例为 1:112,甚为蹊跷。

为了解决抽奖公平性的问题,消除暗箱操作的可能性,我们特别设计了以下抽奖过程。

什么样的抽奖是公平的

抽奖过程可以描述为从 0~N-1 (N为奖券总数) 的整数中抽取一个或多个随机整数的过程。除了抽奖算法和抽奖过程需要公开透明之外,一个公平的抽奖过程所使用的随机数(其实是伪随机数)应具有如下的性质:

  1. 随机数的生成过程不需要依赖于用户对本网站或者任何第三方平台的信任。
  2. 事先无法预测。
  3. 事后公开可查。
  4. 概率上满足均匀分布。

为了保证性质1~3,我们选择使用比特币区块的哈希值来作为我们的随机数种子;性质4只要选取常用的哈希函数即可保证

我们的抽奖算法

假设奖券编号是连续发放的整数。我们的的抽奖算法如下:

  1. 选取指定时刻(即抽奖时间)后被挖出的第一个比特币区块的哈希值作为随机数种子,记作 S。
  2. 用 SHA-256 算法计算 S 的的哈希值 H,然后把 H 作为16进制数字转换为长整数 L。
  3. W = L % N 为中奖的奖券编号,其中 N 为总奖券数量,%为求余数。
  4. 如需抽出 M 个中奖者,则设新种子为 S = H 并且重复 2、3 两步,直到抽出 M 个不重复的中奖者为止。

上述抽奖步骤实际上是用完全公开可验证的方法生成了一个或多个不可控的随机数,其中最重要的随机数种子由比特币区块的性质来保证它满足我们所有的要求。只要知道了我们公布的抽奖时间和发放的奖券总数,任何人都可以在奖券停止发放后计算出一样的伪随机数,从而实现了可验证的公平抽奖结果。有兴趣验证的读者可以参考我们使用的源代码自行验证:

def get_winners(min_n, max_n, num_win, key):
    res = key
    winners = set()
    while len(winners) < num_win:
        res = hashlib.sha256(res).hexdigest()
        winners.add(int(res, 16) % (max_n-min_n+1) + min_n)
    return winners

此函数的输入参数分别是:min_n 为奖券编号中最小的(通常我们会把它设成0);max_n 为奖券编号中最大的(取决于参与抽奖的用户数);num_win 为指定的中奖人数;key 为指定的抽奖时间后被挖出的第一个比特币区块的哈希值。

其中的 key 值我们会在开奖后在这个这个页面公示几天,或者大家也自己可以去 blockchain.com/explorer 或者任何比特币信息查询网站查到相应的区块哈希值。

我们的抽奖结果能保证完全公平吗?

在使用了以上方法生成中奖号码后,暗箱操作的可能性已经大大降低了,但是我们仍然无法完全证明我们的抽奖结果是公平的,原因在于我们无法证明发放的奖券总数的正确性。出于保护用户隐私的目的,我们不能公开每一位参与抽奖的用户的信息,所以理论上来说,我们可以通过增发不存在的奖券来降低用户的中奖概率。为了增加这方面的透明度,我们制作了这个页面,可以即时查看每一张奖券的编号和发放时间。如果奖券的发放有什么异常,大家随时都可以发现。

还有一种改变中奖概率的方式,就是自己参与比特币挖矿,如果挖出了区块并且算出自己没有中奖,可以抛弃这个区块不上报,以期待在没有被其他人抢先的情况下下次挖出的区块可以让自己中奖。然而,挖出一个有效比特币区块的奖励是 12.5 BTC,价值约为 50k USD 以上,矿工间竞争激烈也没有人能保证不被其他矿工抢先,所以有点理智的人都不会干这么奇葩的事情。

Read more from Interesting Maths
1 Comment Post a comment
  1. MoonFruit
    Nov 27 2018

    建议楼主了解一下什么是可验证随机函数(VRF),这就是专门用于解决此类问题的数学工具。

    正如楼主所言,依赖比特币挖出的区块哈希来决定随机数还是有理论上的问题的。

    Reply

Share your thoughts, post a comment.

(required)
(required)

Note: HTML is allowed. Your email address will never be published.

Subscribe to comments