malaさんが考えた公平なガチャシステムとその改良案


続編

この記事で指摘した課題を解決した新しいガチャをつくりました。

コミットメントを用いた公平なガチャシステム

はじめに

僕が(ほとんどを)考えた公平なガチャシステムtodeskingさんにとりあげていただいた。

そうしたところ、malaさんが次のようなガチャシステムを考えてくださった。

これを僕も読んでみて、考えられる限り色々考えてみた結果をここにまとめる。

malaさんのガチャシステム

malaさんが考えたガチャシステムの全文は次のGistにアップロードされている。

https://gist.github.com/mala/f33c9654af5e06e8bca9

プロトコル

上記の文章を僕なりに説明すると次のようになる。

  1. 運営は、$n$種類のカード$K_1 \dots K_n$に番号を割り当てる

    カード 番号
    $K_1$ $1$
    $K_2$ $2$
    $\vdots$ $\vdots$
    $K_n$ $n$
  2. 運営は割り当てた番号をシャッフルし、シャッフルした結果をユーザーへ公開する

  3. 運営はキーと呼ばれる数値を用意する(ただし、キーは$n$より小さい)

  4. 運営はキーを対称鍵暗号で暗号化してユーザーへ送信する

  5. ユーザーは暗号化されたキーを受けとり、(2)でシャッフルされた番号の中から一枚を選択する

  6. 運営はキーを暗号化する際に用いた対称鍵をユーザーに公開する

  7. ユーザーは暗号化されたキーを復号し、選択した番号にその数を足して$n$で割った剰余を求める

  8. ユーザーは(7)で求めた剰余に対応するカードを得る

この方法で大丈夫なのかどうかについて議論を進めていく。

改良案

これを聞いて僕が考えたところ、改良点を思いついたのでそれについて説明する。

マリシャスな運営による不公平な暗号鍵の送信

malaさんが仰るように、キーを暗号化する際に用いた秘密鍵と全然関係のないデータを運営はさも対称鍵であるかのように偽ってユーザーへ公表する可能性がある。こうした可能性を排除するために、ゼロ知識証明を用いるなどして、暗号化の際に用いた対称鍵と公開した秘密鍵が同じであることをユーザーに対して証明する手続きが必要であると思われる。

まとめ

malaさんの言い方はややキツいが、僕の考えたアルゴリズムはやや複雑すぎたと思うところはある。一方でmalaさんのガチャシステムは非常に簡潔でよいと思う。また、malaさんやtodeskingさんには、公平なガチャシステムに関する議論に参加していただけたことに大変感謝している。

P.S