我們是如何用科學的方法盡量保證抽獎的公平性的【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.