我们是如何用科学的方法尽量保证抽奖的公平性的【2015版】

logo-vertical-zh

【2018年更新】因为此版本的抽奖算法其实还是依赖于一个第三方网站 (CoinDesk),不够优美,因此我们设计了新版的算法,请移步《我们是如何用科学的方法保证抽奖的公平性的【2018版】》。

抽奖的公平性向来是抽奖活动中最受人质疑的部分。由于涉及随机数的选取,网上的抽奖活动几乎无法保证公平性,因为很难保证中奖号码是随机生成而非人工选取的。为了解决这个问题,最大程度地保证抽奖活动的公平性,我们设计了如下的抽奖过程,用公开可验证的方式选取随机数,消除了随机数选取过程中暗箱操作的可能性。

什么样的抽奖是公平的

抽奖过程可以描述为从 1~N (奖券总数) 的整数中抽取一个或多个随机整数的过程。为了公平抽奖,消除暗箱操作的可能性,我们选取的随机数应具有如下的性质:

  1. 可验证的随机性,即中奖号码是均匀分布且不可控的随机数,并且任何人都可以验证。
  2. 可验证的唯一性,即只抽取一次随机数,并且任何人都可以验证。

如果不满足第一条性质,那么活动举办方即可通过指定随机数来指定中奖者,并且其他人无法验证这一点;如果不满足第二条性质,那么活动举办方即可通过多次抽取随机数,直到出现指定的中奖者为止来操纵中奖结果,并且其他人无法验证这一点。

抽奖步骤

我们的的抽奖步骤如下:

  1. 选取停止发放奖券当天的比特币 Closing Price Index,用字符串 BPI 来表示。
  2. 用 sha1 算法计算 BPI 的哈希值,并转换为长整数 L。
  3. M = L % N + 1 为中奖的奖券编号,其中 N 为总奖券数量,%为求余数。
  4. 如需抽出多个中奖者,则重复 2、3 两步,直到抽出指定数量且不重复的中奖者为止,其中第 k 个中奖者计算 k 个 BPI 拼接起来的字符串的哈希值。

上述抽奖步骤实际上是用完全公开可验证的方法生成了一个或多个不可控的随机数。只要知道了停止发放奖券的日期和发放的奖券总数,任何人都可以在奖券停止发放后得到一样的随机数,从而实现了随机数的可验证性和唯一性。有兴趣验证的读者可以查看附录中的源代码。下面我们分析下中奖号码的随机性~

中奖号码的随机性说明

上述抽奖步骤涉及比特币和哈希算法,因此中奖号码的随机性并不是很显而易见。下面我们对此加以说明。

首先,比特币的价格和股票类似,具有在一定范围内波动的特点。我们这里选取比特币,主要是出于他不分工作日和周末,价格一直在波动的特点。虽然它的价格不太可能在几小时内有几十几百刀的波动,但是在 1 cent 或更高的精度上,没有人能完美地预测其价格,更别说我们采用的数据精确到了 0.01 cent 的BPI (Bitcoin Price Index)。此外,不是所有的比特币交易都会改变BPI,而是只有满足一些条件的交易才会被统计到BPI中(详见这里),更加降低了人为精确操纵的可能性。因此,至少在 0.01 cent 的精度上,比特币的价格可以认为是不可预测的。下图是比特币价格在一天内的变化,可以看到价格一直在小幅波动。

Screen Shot 2015-09-29 at 3.17.05 PM

 

其次,我们用哈希函数计算比特币价格的哈希值,从而得到中奖号码。这一步相当于将比特币在 0.01 cent 精度上的不可预测性扩大为了全局的不可预测性。哈希函数的一个非常重要的性质就是,即使输入只有最细微的变化,输出也会有巨大的变化。下面是几个几乎一样的数字的sha1哈希值:

  • 123.4567: 9a29951d36afef712de11d2da0c6922c1ffead93
  • 123.4568: 009b4e194617bcacacbb169763a333f19e441af3
  • 123.4569: f473c31d6a63a9851a8bfdaf931b8a905af7eed2

可以看到,即使输入只有最微小的差距,输出都会有天壤之别。因此我们可以认为,哈希后的比特币价格是一个不可预测,但是任何人都可以验证的随机数。

 

下面我们来看看用上述方法得出的中奖号码的分布。由于比特币的历史较短,我们只有从2010年7月17日到现在的不到2000个历史BPI。假设每天进行一次抽奖,每次发放20张奖券,每次抽出一张,那么抽奖结果的分布如下

f1

可以看到,结果分布的还是很均匀的。如果我们改为每次发放100张奖券,每次抽出10张中奖奖券,抽奖结果分布如下:

f2

结果也是比较均匀的。因此哈希后的比特币价格可以认为是分布比较均匀的随机数。

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

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

虽然我们仍然无法完全证明抽奖活动的公平性,但至少我们已经无法操纵中奖号码了。剩下的一部分公平性,一半靠大家监督,一半靠我们的良心。虽然不能严谨地证明,但我们希望大家能看到我们在这方面的努力,给我们支持与信任,帮助我们做的更好。谢谢大家一直以来的支持~

附录:抽奖的技术细节和源代码

比特币的价格由 CoinDesk 提供。这里的 Closing Price 是以 UTC 时间计算的。例如,2015年9月29日的BPI,可以于2105年9月30日03:00 UTC之后通过如下的地址得到:http://api.coindesk.com/v1/bpi/historical/close.json?start=2015-09-29&end=2015-09-29

获取中奖号码的Python源代码如下:

1
2
3
4
5
6
7
def get_winners(min_n, max_n, num_win, key):
    sha1 = hashlib.sha1()
    winners = set()
    while len(winners) < num_win:
        sha1.update(str(key))
        winners.add(int(sha1.hexdigest(), 16) % (max_n-min_n+1) + min_n)
    return winners

其中四个参数分别为:奖券编号的最小值、奖券编号的最大值、中奖人数、BPI。


分享至社交网络

若喜欢本文,别忘了给个五星好评哦!

[Total: 2    Average: 5/5]
Disclaimer: The responses below are not provided or commissioned by the bank advertiser. Responses have not been reviewed, approved, or otherwise endorsed by the bank advertiser. It is not the bank advertiser's responsibility to ensure all posts and/or questions are answered.