続編
この記事で指摘した課題を解決した新しいガチャをつくりました。
はじめに
僕が（ほとんどを）考えた公平なガチャシステムをtodeskingさんにとりあげていただいた。
安全ガチャだ https://t.co/0wQZ5WzwjT
— トデス子'\ (@todesking) 2016, 1月 3
そうしたところ、malaさんが次のようなガチャシステムを考えてくださった。
@todesking ものすごく単純化した。ハッシュ云々とかイランと思う https://t.co/A2U1G8Re8a
— mala (@bulkneets) 2016, 1月 3
これを僕も読んでみて、考えられる限り色々考えてみた結果をここにまとめる。
malaさんのガチャシステム
malaさんが考えたガチャシステムの全文は次のGistにアップロードされている。
プロトコル
上記の文章を僕なりに説明すると次のようになる。
-
運営は、$n$種類のカード$K_1 \dots K_n$に番号を割り当てる
カード 番号 $K_1$ $1$ $K_2$ $2$ $\vdots$ $\vdots$ $K_n$ $n$ 運営は割り当てた番号をシャッフルし、シャッフルした結果をユーザーへ公開する
運営はキーと呼ばれる数値を用意する（ただし、キーは$n$より小さい）
運営はキーを対称鍵暗号で暗号化してユーザーへ送信する
ユーザーは暗号化されたキーを受けとり、(2)でシャッフルされた番号の中から一枚を選択する
運営はキーを暗号化する際に用いた対称鍵をユーザーに公開する
ユーザーは暗号化されたキーを復号し、選択した番号にその数を足して$n$で割った剰余を求める
ユーザーは(7)で求めた剰余に対応するカードを得る
この方法で大丈夫なのかどうかについて議論を進めていく。
改良案
これを聞いて僕が考えたところ、改良点を思いついたのでそれについて説明する。
マリシャスな運営による不公平な暗号鍵の送信
@_yyu_ @todesking 暗号化データから複数の復号結果が得られうるようなアルゴリズムだとサーバー側で運営者にのみ有利な結果が選択されるような(レア度が低い) 別の鍵を作れますね。よく知られてるアルゴリズム使うだけで十分なのでは、と思ってその辺りは端折りました
— mala (@bulkneets) 2016, 1月 3
malaさんが仰るように、キーを暗号化する際に用いた秘密鍵と全然関係のないデータを運営はさも対称鍵であるかのように偽ってユーザーへ公表する可能性がある。こうした可能性を排除するために、ゼロ知識証明を用いるなどして、暗号化の際に用いた対称鍵と公開した秘密鍵が同じであることをユーザーに対して証明する手続きが必要であると思われる。
まとめ
確率操作されてるって騒ぐ層にも理解できるアルゴリズムであることが必要だと思う
— mala (@bulkneets) 2016, 1月 3
malaさんの言い方はややキツいが、僕の考えたアルゴリズムはやや複雑すぎたと思うところはある。一方でmalaさんのガチャシステムは非常に簡潔でよいと思う。また、malaさんやtodeskingさんには、公平なガチャシステムに関する議論に参加していただけたことに大変感謝している。
P.S
ユーザが運営をまったく信頼しないことを前提とする公平性証明ガチャを導入したところで、ガチャ以外のロジックの妥当性が問題になるだけだし思いやりと信頼でやっていくほうがマシなのではという気もしてきた……
— トデス子'\ (@todesking) 2016, 1月 3
ガチャ以外にも、ソーシャルゲームのありとあらゆる確率が絡む局面を秘密計算で実装すれば、ユーザーはアプリケーションをリバースエンジニアリングして公平性を確かめることができる。
— 吉村 優 (@_yyu_) 2016, 1月 3