創作內容

88 GP

[達人專欄] 如何舉辦公平又公開的抽獎？用雜湊函數來做吧！

作者：解凍豬腳│2020-06-21 13:06:02│巴幣：340│人氣：3614

　
　　最近在巴哈姆特動畫瘋的每日抽獎抽到了 30 天的付費會員序號。心裡想著反正最近也沒有天天看動畫，不如就把這組序號送出去給需要的人用。

　　但問題來了！一個抽獎程序最重要的就是公開、公平，如果這個抽獎過程又可以在事後受到眾人的重複檢驗，那不是更好嗎？

　　今天我們就來比較看看不同的抽獎方法之間有什麼差異吧！

。普通的隨機數抽獎法，有什麼弊端？

　　像個普通人一樣使用（或自製）一個隨機數產生器，在大家面前開實況把產生隨機數的過程播放出來，這樣會有一種作假的可能：「如果這個人早就已經產生了很多次抽獎結果，表面上是在開實況，其實只是把預錄好的、經過挑選而令他滿意的抽獎紀錄拿出來播放，那就不公平了吧？」

　　這種疑慮有沒有簡單的解決方法？有！

　　只要直播台的主人讓產生抽獎結果的電腦螢幕和正在播放的新聞台一起入鏡，那就可以向同時開著電視的網友們證明的確是在這個時間點抽出，證明他真的只有抽這麼一次。

　　然而，即使做到這樣，還有作假的可能嗎？有！

　　直播台的主人可以利用一些小手段，比如使用 JavaScript 腳本竄改網頁上的隨機數產生器程式碼，這樣便能使得每次抽出的數字都是讓他滿意的抽獎結果，只是你不知道。

。這裡就是死路了嗎？要怎麼解決這個問題？

　　在解決問題之前，先來看看「隨機」。

　　實際上，我們一般的電腦並沒有辦法實踐理論上的「真隨機」，科學家只能依賴量子方法來取得真正的隨機數。然而，量子方法往往耗時費工，你應該也不會為了抽獎而拿個精密儀器來偵測電子的狀態吧。

　　現代的電腦產生隨機數的方法，其實就只是利用當前的某些不固定、不易預測的數值作為素材，比如：「產生隨機數」那一瞬間的時間毫秒數、使用者當下的滑鼠座標位置、處理器的核心溫度……接著再搭配另外設計出來的一套數學方法，讓產生出來的結果可以達到統計意義上的隨機。

　　因為隨機數的產生過程通常都是在電腦裡面執行完就無法再重新得出相同結果的，於是在煩惱「到底要怎麼產生一個完全公開透明又可以被眾人重複檢驗的抽獎規則」這件事的時候，我想到了一樣東西——雜湊函數！

。雜湊函數是什麼？

　　你可以想像一下，如果我們設計一套通用的流程：
　　1. 先把一串中文字的所有文字筆劃數相乘得到 A
　　2. 把 A 乘以一個固定且夠大的質數 1073807359 得到 B
　　3. 把 B 加上每一個字的筆劃數得到 C
　　4. 把 C 除以 1000，取得餘數為 D

　　實作一次，我們把「解凍豬腳」四個字套用在這組流程會得到：
　　A = 13×10×15×13 = 25350
　　B = 25350×1073807359 = 27221016550650
　　B = 27221016550650+13+10+15+13 = 27221016550701
　　27221016550701÷1000 = 27221016550...701
　　C = 701

　　這樣我們就產生了一套有以下幾項優點的規則：
　　1. 不管原文的長度是多少，我都可以決定範圍並得到一個範圍內的整數
　　2. 接近隨機，有一定概率分佈在每一個數上面
　　3. 只要修改一點內容就會得到截然不同的計算結果，不容易被預測（註）
　　4. 每次用一樣的字串計算出來的結果一定都會一樣，而且算法公開可受檢驗

　　所謂的雜湊函數便是如此。我們知道，電腦裡的資料又可以稱為「數據」，因為它們終究是由一堆數字所組成的。市面上常見的 MD5、CRC32、SHA-256 設計得更完全，除了具備上面的特性以外，還可以用來計算更多種類型的數據（比如說包含數字、符號、英文的字串或檔案），而且產生結果範圍更大（比如 CRC32 是 0 ~ 16^8-1，而 MD5 是 0 ~ 16^32-1）。

　　既然對電腦而言「隨機數」跟「雜湊函數」的產生結果都是具有相近意義的偽隨機數，那何不直接把後者作為得獎者的產生工具呢？

　　註：你可以很輕易照著範例的步驟算出「解凍豬腳」是 701，但假如反過來要你找到一串中文字符合 888 還要符合種種條件，那就有點難了。

。如何實作？

　　夠聰明的你應該已經從上面「取餘數」這件事看出端倪了。

　　在本文開頭提到的當時抽出中獎者的方法，我的步驟如下：
　　1. 把每個參加者的帳號依照參加順序串起來，得到 A 字串
　　2. 把 A 字串後面接上最後一個人留言的日期時間，得到 B 字串
　　3. 把 B 字串做 CRC32 運算，得到一組 0 ~ 4294967295 之間的數字 C
　　4. 把這組數字除以參加人數，得到一組 0 ~ (參加人數-1) 之間的數字 D
　　5. 把數字 D+1，就是中獎者的次序了

　　比如今天有 5 個參加抽獎的巴友帳號依序為 sega、smartest、yunski、cpan、coolhero，而 coolhero 這位最後一個參加抽獎的巴友是在 2020-06-20 21:43:22 的時候參加，那我就會得到一個字串：
　　「segasmartestyunskicpancoolhero20200620214322」

　　這個字串拿去做 CRC32 運算會得到 0x83714995（注意這是十六進位的數字），先把它轉為十進位的數字得到 2205239701，再除以參加人數 5，得到餘數為 1。

　　除以參加人數 5 得到的餘數一定是 0~4，所以我們要把它 +1 才可以讓它對應到第 1 個參加者到第 5 個參加者——從餘數 1 得知結果是第 2 個參加者 smartest 中獎。

　　由於抽獎的時候已經先把計算規則公開了，參加的時候每個人也都看得到有哪些巴友參加這場抽獎，因此他們在事後也可以自己驗算這場抽獎結果是否正確。

　　這場抽獎的決定性因素就在於其中的最後一位巴友是在幾點幾分幾秒的時候參加，所以如果這位巴友想要作弊，他就得在他的上一位巴友參加以後，把截止日 23:59:59 以前的所有可能結果計算出來，從會讓他中獎的結果之中找到最晚的時間點，準確地在那一分那一秒參加抽獎，並且還要保證在截止日的 23:59:59 前絕對不會有其他人參加。

　　所以時間點越接近截止時分，作弊的難度就會越高；要是有一堆人都剛好在截止日當天的 23:59:59 那一秒參加抽獎，就絕對沒有人能夠保證抽獎結果為何了。

。這種抽獎方法有改善空間嗎？

　　我事後想了一下，上面的方法會有兩個問題：

　　1. 要是參加的人數過少，那麼用前面講到的方式作弊就會很容易成功，因為如此一來便不會有其他人來把你計算好的結果重新洗牌。

　　2. 把每一個人的帳號串起來，這樣的工作對於一個有寫程式能力的人來說很簡單，但是對於一般人來說會變得很麻煩。

　　第一個問題可以引入「預期會在未來產生出來而且不會變動的隨機內容」來解決，比如我可以規定以「參加時間截止之後第一期的威力彩第一區獎號」為材料。為了保證抽獎結果的唯一性，我們可以規定這個開獎號碼要由開獎順序排列。

　　假設參加時間截止後威力彩的第一區開出了 12、25、20、27、06、37 這六個號碼，我們按這個開獎順序可以得到一組字串 122520270637。然而單用這項素材還是嫌太少了，因為第一區獎號總共有 1987690320 種排列結果，這比 CRC32 計算結果的 4294967296 種可能還要少，恐怕會造成產生結果的不均勻，所以我們可以再放一些簡單的材料進去，比如再規定要和最後兩個參加者的帳號串起來，這樣也就同時解決了上述的第二個問題。

　　在這種場合，CRC32 算法已經很足夠。首先它的範圍只到 0xFFFFFFFF（即 16^8-1，也就是 4294967295），這使得你可以很輕易地透過電腦的小算盤來計算，而且只要摻入大樂透號碼這種絕對沒有人能夠預測的元素就已經很安全。

。改良後的抽獎方式

　　總結上面的考量，假設今天你想要抽出一位巴友作為得獎者，並且在 2020-06-14 23:59:59 過後截止參加，那你就可以在舉辦抽獎時預先設好規則：「這次抽獎方式為用『最後兩個參加者的帳號小寫串起來加上 2020-06-15 威力彩第一區依開獎順序的開獎號碼』做 CRC32 運算，然後再除以參加者數量取得餘數決定中獎者。」

　　截止時，參加者依序有 sega、smartest、...、yunski、cpan、coolhero 總共 2677 位巴友，接著隔天威力彩依序開出了 20、28、14、16、32、23。

　　於是你得到了決定得獎者的字串：
　　「cpancoolhero202814163223」

　　這裡要注意：英文的大小寫會影響到雜湊函式的計算結果，所以公告規則的時候要嘛事先規定全小寫或全大寫，要嘛就是以某頁面顯示的為主，總之這個大小寫一定要遵循一套標準，必須確保拿來做雜湊運算的字串有唯一性。

　　接著上 Google 隨便找一個線上 CRC32 計算工具（註），得到該字串的 CRC32 值為 0xCC43FD0D，再打開電腦的小算盤，轉為程式設計人員模式，在 HEX（十六進位）輸入 CC43FD0D 就可以得知它的 DEC（十進位）為 3427007757，然後再轉為工程型計算機，計算 3427007757 mod 2677 得到餘數為 698，因為餘數是 0~2676 而不是 1~2677，所以得到餘數 698 以後不要忘記 +1。

　　因此最後是這 2677 位參加者裡面的第 699 個人中獎了。

　　如果你是要從 2677 個人裡面抽出多個人而不是只有一個，那你更可以事前規定「抽出的第一個中獎者作為下一個中獎者的計算素材」。

　　比如你已經用上面的方法抽出了第一個中獎的人是帳號為 pansy 的巴友，那你就可以用「pansy202814163223」做 CRC32 運算得到 0x741A55AE，轉為十進位，計算 1947882926 mod 2676 得到 1118，再 +1 得到 1119，得到了第二位中獎者是剩下的 2676 人裡面的第 1119 位，以此類推重複下去就可以用同樣的方法抽出好幾個人。

　　只要是不可預測而且具有唯一性的數據，你都可以拿來當作決定得獎者的素材，並且在辦活動的時候就先把規則告訴所有人，如此一來就完成了一套公平、公開，又能受到所有人重複檢驗的抽獎流程了。

　　註：因為 CRC32 的計算方法是固定且公開的，所以只要這個計算工具沒有寫錯，大家得出來的結果一定都會一樣。

。雜談

　　以上是這次突然大開的腦洞，分享給大家。雖然發現了這樣的一套方法，但我好像也沒有什麼東西是可以常常送出去的，畢竟我窮（

）。

　　總之看看區塊鏈、open source、open data，現在凡事都提倡公開對等，如果能夠連同網路的抽獎活動都這麼做，那豈不是很棒嗎？

延伸閱讀：巴哈帳密可能外流？快來了解你的帳號風險！
　

喜歡 88 收藏 9 引用留言推上首頁檢舉

引用網址：https://home.gamer.com.tw/TrackBack.php?sn=4823753
All rights reserved. 版權所有，保留一切權利

相關創作

同標籤作品搜尋：MD5|CRC32|SHA-256|雜湊函數|冗餘函數|HASH|抽獎|樂透|中獎

[達人專欄] 上手 Go 語言的 map，實作簡單快取機制

朋友中獎了

顯卡少女插畫集&滑鼠墊抽獎活動結果公佈！

[達人專欄] 【前方低能】說不在乎的最要命!!

[達人專欄] 介我雜圖串58 - 心存僥倖

留言共 30 篇留言

雨丸✰“ReのLife”★：
佬

06-21 13:06

Sky：
佬...看完都想抽了

06-21 13:07

跳水坑：
佬

06-21 13:07

雪之王女‧F‧巧可奈：
雖然看不太懂但仍感謝分享

06-21 13:07

鄭曉麥：
懶人包： "隨機"與"偽隨機"的差異

06-21 13:13

鄭曉麥：
以及 hashcode 的用途其一

06-21 13:14

ㄇㄇ：
太複雜拉(._.)

06-21 13:15

搭啦：
除了量子電腦，還有熱學噪聲之類ㄉ電腦硬體真隨機生成器

06-21 13:16

游大星：
才華洋溢

06-21 13:17

哈哈你看看你：
不...不就excel 的random函數嗎

06-21 13:18

解凍豬腳：
本文意在建立一個「可以被人重複檢驗」的抽獎方式，如果直接用 random 函數的話就不叫做「可重複檢驗」了，因為出來的東西不一樣06-21 13:23

迷幻啾啾：
那個…抽到我再跟我說

06-21 13:31

千羽：
聽起來是個不錯的方法
還可以讓參加抽獎的人驗算
但如果抽完獎後有人將留言刪除了呢
畢竟除了自己
版主也有將發文刪除的權利
就算是先截圖也還是有造假的問題存在

06-21 13:34

解凍豬腳：
我的做法是「只要樓層蓋下去了就視同參加」，一般來說如果在巴哈的話建議用回文，即使該樓刪文了仍然可以看得到自刪的帳號，這樣就可以確定他在抽獎名單上面了06-21 13:49

赤炎o嵐喵：
隨機抽樣我一律推薦C78取63星爆法

06-21 13:37

鴨子ヽ(・×・´)ゞ：
好長

06-21 13:43

姆咪寶><：
佬

06-21 13:46

GNT-0000：
硬核

06-21 14:16

阿銀z：
所以我說那個抽獎網址呢（x）

06-21 14:18

小咪好可愛：
佬

06-21 14:28

Satania：
跟ㄐㄐ一樣又臭又長

06-21 14:29

北極熊：
怎麼有種離散對數的感覺

06-21 15:04

a990266a：
OCT不是八進位嗎？筆誤?

06-21 15:16

解凍豬腳：
是筆誤沒錯，感謝06-22 00:13

ᗜ‸ᗜ：
看不懂但還是推

06-21 18:33

熾心凝：
hash好像算比較普遍的隨機取樣的方法(除了用時間取random外

06-21 18:57

沼躍魚：
大佬...

06-21 20:35

梧優：
未看先推剛學過hash

06-21 22:34

霜星zz：
突然想到如果拿前一個中獎者當素材然後又抽到同一個人這樣就會陷入無限迴圈了耶如果人數不多發生的機率似乎不小

06-22 00:05

解凍豬腳：
抽到的中獎者要整個從列表抽掉，因為要保持連號才能用取餘數的方法抽，簡單來說如果從 1~500 抽到了 250，那 250 就要取出來，原先的 251~500 往前挪一位變成 250~49906-22 00:12

甘蔗原汁：
被外面的妮可圖騙進來....
妮可妮可妮~~

06-23 16:08

極雄-游泳模式：
恩恩，原來是這樣啊，我懂了

07-15 10:34

鄧董：
謝謝大大文章，寫得真好。不過我有個問題想問：CRC計算的目的是否是要讓隨機大數(不方便使用一般計算機輸入)能夠平均mapping到[0 , 2^32-1]? 在不考慮大數計算對硬體的消耗，我如果直接以原字串取得 (ascii碼 modulo 參加人數 + 1)，是不是結果也是足夠隨機，又或者像是，大樂透第一區開獎號碼既然已經是由某一演算法取出足夠平均的數字了，那直接取 (大樂透開獎號碼 modulo 參加人數 + 1)是否就足夠當作抽獎結果。我有查了CRC計算方法，看出它幾乎是bijection，不過CRC計算得到的結果，也是依賴大樂透號碼給出的數字。

11-11 04:20

解凍豬腳：
　
對，關於 mapping 可以這麼說

想像一下，如果今天不使用任何 hash 算法而是直接看 ASCII 碼，然後參加抽獎的人數就這麼剛好 256 個人，那就相當於直接取最後一個 byte

比如說樂透號碼是 27, 24, 17, 34, 31, 01，我把字串 "272417343101" 轉換成十六進位，直接連起來就會變成：0x323732343137333433313031

這時候除以抽獎人數 0x100，就會直接得到末兩數 0x31，我們透過 ASCII 表知道 0~9 的數字範圍在 0x30~0x39（十進位的 48~57），那就會導致「參加人數剛好 256 個人的時候，永遠是第 49 號~第 58 號的人中獎」的情況
　11-11 07:13

解凍豬腳：
光是這點，至少就會有一種特定情況可預測結果範圍，那就不符合公平的要求
hash 的好處一方面也是在這些結果不容易預測，畢竟算法太複雜了11-11 07:36

鄧董：
謝謝豬腳解答，我沒考慮到對參與人數做partition後的數字不會平均離散分布，透過CRC能過確保每一數字出現機會都平整映射到一區間；受益良多!

11-11 16:05

我要留言提醒：您尚未登入，請先登入再留言

88 喜歡★johnny860726 可決定是否刪除您的留言，請勿發表違反站規文字。

前一篇：原來是退休啊，我還以為是... 後一篇：場外女裝都市傳說...

追蹤私訊切換新版閱覽