Re: [情報]韓國轉蛋法實施 公開機率發現根本抽

※ 引述 《wei115》 之銘言：
: 標題：Re: [情報]韓國轉蛋法實施 公開機率發現根本抽不到
: 時間: Fri Apr 19 12:34:38 2024
:
: 有點好奇
:
: 不能設置一個第三方機構
:
: 每次有人抽卡後就廠商就必須把這筆資料上傳到伺服器，供大眾查詢
:
: 這樣不就可以確定機率嗎？
:
: 技術上也不是什麼問題
:
: --

「如何確定廠商有沒有修改轉蛋概率」這個問題滿有意思的

目前主流的解法不外乎：
（1）依賴政府或第三方機構直接監管
（2）建立公開資料庫做統計驗證

我來提一個基於零知識證明、比較複雜的解法
不依賴第三方機構、逐條檢驗抽卡結果
供大家參考

: 我不是研究網絡安全的，方向是計算複雜性

: 但我對這類問題滿感興趣的
: 這篇文章僅是非專業人士的心得
: 如果有誤煩請大神解惑、賜教

———————————————————————————————————————

科普：何謂零知識證明（zero-knowledge proof, ZKP）？

照抄維基百科的定義：

「一方（證明者）向另一方（檢驗者）證明某命題的方法，特點是過程中除『該命題為真』之外，不洩漏任何資訊」

例如：我有核彈的密碼，但你不信
當然我可以試射一枚核彈看看，或是直接把密碼發送給你檢驗
但這可是核彈啊！哪可以那麼輕忽！

如果我們採用零知識證明的協議
我（證明者）可以讓你（驗證者）相信我確實有核彈密碼，但你仍然完全不知道密碼的內容

: 維基百科裡山洞的例子非常經典，有興趣可以看看
: 每次組裡簡報有人需要介紹ZKP時基本上舉山洞的例子
: 但是為了簡化說明我採取這個不太精確的例子

———————————————————————————————————————

首先，嚴格定義轉蛋問題：

「廠商Ｃ傳送隨機串Ｓ給玩家Ｐ後，有沒有一種協議可以讓廠商Ｐ不需要公開代碼也可以證明Ｓ確實是隨機生成？」

1. 廠商傳送隨機串僅限一次
2. 隨機串的偽隨機數生成器的種子是廠商決定且不公開
3. 廠商和玩家都是不可信任的

說明一下為什麼這麼定義。

第(1)條是因為我認為之前丁特近千次轉蛋進行統計驗證的方法不好
一，很難保證有沒有廠商對於特定人士做動態概率調整
二，統計驗證不能進行逐條檢驗，誰知道廠商會不會根據有償石、無償石、呼符來調整概率三，抽卡很貴，驗證一次抽卡不應該需要大量財力 = =

第(2)條是確保隨機性

第(3)條為了提防廠商作弊或競爭對手故意誣陷

——————————————————————————————————————

回到零知識證明

所謂的核彈密碼就是隨機串Ｓ

廠商Ｃ持有核彈密碼的證明者

玩家Ｐ想要驗證核彈密碼為真的驗證者

你可能認為很怪
作為核彈密碼的隨機串Ｓ都給了玩家，還需要什麼零知識證明
這是因為這個問題裡重要的不是「密碼」本身
而是如何證明「核彈密碼是真的（Ｓ是隨機生成的）」
但玩家對於Ｓ生成過程所需的隨機數種子一無所知

或是
你也可以理解成廠商的代碼裡的種子才是真正的核彈密碼

——————————————————————————————————————

看到這裡有人可能會想「反正零知識證明套一套就可以了對吧？」

欸嘿，抱歉不是
其實我接下來要用的工具叫做可驗證隨機函數（verifiable random function, VRF）

嚴格來說VRF是獨立於零知識證明的議題
（據我所知）ZKP不太處理證明隨機性的東西
但兩者用法上很雷同
事實上1999 年最早提出VRF論文 [1] 其中一位作者
麻省理工教授、2012年圖靈獎得主 Silvio Micali
同時也是1985年提出ZKP概念的學者之一 [2]

我想大家對於ZKP可能比較有興趣
聽到VRF說不定就直接 END了
所以用ZKP先給大家有一個簡單的概念

好了，現在可以END了（Ｘ

——————————————————————————————————————

現在我們正式引入VRF的概念。

嚴格來說，
VRF是一種函數Ｆ，種子Ｓ輸入Ｘ，輸出Ｒ的同時生成一組證明Ｐ，滿足以下性質：
0. 驗證者只有輸入Ｘ、輸出Ｒ、證明Ｐ，不知道種子Ｓ
1. （完全可驗證性）如果Ｒ和Ｐ確實由Ｆ, Ｓ, Ｘ生成，則Ｆ持有者可以極高概率（1 -o(1)）通過驗證
2. （唯一可驗證性）對於固定輸入Ｘ，只有一組輸出Ｒ和證明Ｐ可以通過驗證，其餘以極高概率驗證失敗
3. （偽隨機性） 任何只知道輸出的算法無法分辨輸出來自Ｆ還是均勻分佈。

: 我省略了一些細節，比如種子Ｓ其實是證明者的私鑰，驗證者有對應的公鑰
: 不過可以粗略理解成公鑰是證明Ｐ的固定成分，不會隨著輸入Ｘ改變
: 我的定義是參考 Micali 論文 [1] ，後續文章 VRF 的定義不太相同
: 例如有些VRF完全可驗證性定義為以概率1通過驗證 [3,4]

——————————————————————————————————————

總之，你可以把VRF理解成一個黑盒
除了設定種子(不公開)還要設定輸入(公開)
VRF黑盒吐出輸出的時候，順便生成了一組輸出的證書
輸出什麼值幾乎就是均勻隨機（因為玩家不知道種子）
任何人可以拿著輸入、輸出、證書進行驗證

可以這麼理解VRF
我們沒有統計上驗證概率
而是驗證了「廠商確實執行了指定的偽隨機算法」
從而確保概率沒有做更改

——————————————————————————————————————

（1） 輸入

輸入Ｘ可以設置為玩家信息和抽卡時間的雜湊值
Ｘ是公開信息且由固定規則生成
廠商和玩家可以自己驗算，誰也不能在輸入上作弊

由於雜湊函數抗碰撞的特性
就算廠商不改種子Ｓ
就算我們知道有一組雜湊值Ｘ必定（或統計上高概率）出彩卡
玩家也無法預測這一組雜湊值下一次何時出現

有一些VRF科普文章 [6] 直接把它就當作一種RNG
不一定很準確
因為兩者區別在於一般RNG輸入是不公開的

(2) 驗證

雖然完全可驗證性不保證「如果廠商偷改種子或偷改Ｆ，我們一定抓得出來」
但驗證失敗表示廠商一定有鬼

唯一可驗證性保證了如果彩奈把你的彩卡偷換成藍卡（或更改證明）
他高機率通過不了驗證

(3) 隨機性

種子Ｓ是廠商私有
所以廠商不需要公布自己的代碼也可以證明自己沒有作弊
只需要事先和玩家約定好採用哪一種VRF作為協議
也可以說，廠商只公佈了偽隨機數怎麼抽取的
其餘具有商業價值的代碼或素材不需要公開

(4) 非交互性（non-interactive）

這可能是比較少人注意到的優點
就是廠商只要把結果和證書扔給玩家事情就結束了
驗證過程不需要廠商和玩家來來回回交換資訊

(5) 輸出

過去廠商因為不公開代碼所以玩家也不知RNG怎麼實作的
知道種子可能意義不大
反正玩家不知道RNG算法的選擇

如果採用VRF方案RNG算法就必須公開
因為玩家已知獎勵池和輸入雜湊值
如果玩家猜到種子，他就可以知道接下來所有值
從而推斷接下來什麼時候抽卡必出彩

不過這一點和所有RNG的問題一樣
過去怎麼解決就怎麼來
例如廠商定時更換種子之類的

(6) 轉蛋概率

可能有人注意到Ｆ輸出分佈是接近均勻分佈
如果我們想改成3%的中獎概率
只需要讓獎勵池（輸出空間）標記為中獎的輸出總量達到3%就可以了

注意，獎勵池（每一個輸出對應什麼獎品）必須是公開信息

(7) 種子

當然如果種子可以由輸入、輸出、證明逆算得到，VRF就廢了
所以一般來說VRF在各種密碼學假設下確保這種事情是做不到的
（[1] 這篇基於RSA不可破解，後量子時代需要其他VRF）

————————————————————————————————————

轉蛋手遊之前其實很早人們就關注過這類問題
像是電子樂透（e-lottery system）
早在2005年就有人應用VRF設計電子樂透系統 [5]
文章就有指出第三方機構監管系統的問題
基於VRF的系統相對而言就理想很多，幾乎所有現實要求都能滿足
在解決轉蛋問題上VRF應該是可行方案

VRF具體構造和代碼庫我沒找來看
如果實作上不切實際請不要罵我（逃

不過就算VRF不可行
學界早就對這種系統有很多研究
比如建立在分布式系統上的電子樂透系統 [7]
應該總有辦法不依靠第三方機構去驗證機率（保證廠商執行特定算法）

我讀了幾篇新聞了解一下修法內容
轉蛋法無非是廠商必須明訂中獎商品的概率和保留電磁紀錄以供檢視
其實還是廠商自律和第三方機構（政府）監管的混合

但正如這篇專欄 https://gnn.gamer.com.tw/detail.php?sn=265413 說的：

「回到轉蛋法上，首先在最為重要的轉蛋機率上，很遺憾目前仍然沒有相關配套的檢驗措施。在上述案件中，筆者認為有下列幾個因素才能促成這樣的結果：（1）丁特消費的金額、轉蛋樣本數到達一定數量。（2）實況主、名人身分較一般人更容易引起關注與話題。（3）遊戲橘子在廣告宣傳上的標語確實有造成廣告不實的疑慮。」

真正解決轉蛋業界的問題
最好還是有一種政府或業界制定的轉蛋協議標準
無論採用什麼方法
協議必須可以逐條檢查轉蛋結果且不傷害廠商正常商業利益
才能根本上解決問題

我看轉蛋法修法過程中有資工系教授參與
所以我不太確定有沒有什麼考量不採用這類的方法
可能我哪裡想錯了......？
或是殺雞用牛刀太麻煩了www
最有可能的原因還是擋人財路（小聲

不管如何，這篇文章僅供參考w

今天我本來應該繼續改論文
誰知道都在看VRF論文，我到底在幹嘛啊（

參考文獻：

[1] Micali, Silvio, Michael Rabin, and Salil Vadhan. "Verifiable random functions." 40th annual symposium on foundations of computer science (cat. No. 99CB37039). IEEE, 1999.
[2] S. Goldwasser, S. Micali, C. Rackoff, The Knowledge Complexity of Interactivc Proof-Systems, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985.
[3] Dodis, Yevgeniy, and Aleksandr Yampolskiy. "A verifiable random function with short proofs and keys." International Workshop on Public Key Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005.
[4] Dodis, Yevgeniy. "Efficient construction of (distributed) verifiable randomfunctions." Public Key Cryptography—PKC 2003: 6th International Workshop on Practice and Theory in Public Key Cryptography Miami, FL, USA, January 6–8, 2003 Proceedings 6. Springer Berlin Heidelberg, 2002.
[5] Chow, Sherman SM, et al. "An e-lottery scheme using verifiable random function." International Conference on Computational Science and its Applications. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005.
[6] https://chain.link/education-hub/verifiable-random-function-vrf
[7] Grumbach, Stéphane, and Robert Riemann. "Distributed random process for a large-scale peer-to-peer lottery." Distributed Applications and Interoperable Systems: 17th IFIP WG 6.1 International Conference, DAIS 2017, Held as Part of the12th International Federated Conference on Distributed Computing Techniques, DisCoTec 2017, Neuchâtel, Switzerland, June 19–22, 2017, Proceedings 17. Springer International Publishing, 2017.

--

做這方面的人壞習慣，習慣假定所有人（包含第三方機構）都有鬼w

不可能，因為獎勵池（Ｓ對應的獎品）要求公開

應該還好，我說了那麼多其實廠商只需要多計算出一個證明出來 玩家拿到證明進行檢驗那是玩家自己的事情

除了抽卡者就只有廠商，沒有第三方機構。 不考慮廠商對玩家做網絡攻擊（我猜中間人攻擊之類的?），是可以防止廠商作弊的