新しい手法を開発しました。
僕が（ほとんどを考えた）公平なガチャシステム

はじめに

ソーシャルゲームのガチャは、あらかじめ運営からSSRなどのレアリティに基づいた出現確率が公表されているが、それはあくまで運営が公表した値でしかなく、本当にその通りなのか疑う余地があった。そこでこの記事では前回の記事で紹介したハッシュの衝突に基いて、ユーザーにとっても運営にとってもガチャによるカードの出現確率が明らかな方法を提案する。何か質問や意見などがあれば、気軽にコメントして欲しい。

プロトコル

この計算量を利用した方法はどこかのCTFで出題されたと友人から聞いて、それを使っている。

日本語による手順

運営はカードとそれに対応するマスクを公開する。このマスクは$n$ビットで構成されていて、カードの種類と一対一に対応している。このマスクはSSRなど希少なカードほど1のビットが多く、Nなどありがちなカードほど0が多くなるようにしておく。
ユーザーがガチャを引こうとすると、アプリケーションがサーバーへそのことを通知する
サーバーは、無作為な文字列Aと$n$ビットのデータBをデータベースへ書き込み、AとBをアプリケーションへ送信する
アプリケーションはAに任意の文字列を追加して、文字列Cを生成する
アプリケーションは文字列Cのハッシュ値を計算し、BとのAND（論理積）を計算し、それをDとする
- $D = B, \&, hash(C)$
アプリケーションはDに対応するマスクを持つカードを表示し、AとBとCをサーバーへ送信する
- もしDに対応するマスクが一つもない場合は（4）からやりなおす
サーバーは次のことを検証する
- サーバー側のデータベースにAとBが記録されているか
- 文字列Cの中にAが含まれているか
サーバーはCからアプリケーションと同じようにDを計算する
- $D = B, \&, hash(C)$
サーバーはDと同じマスクを持つカードをユーザーに与える
- もしDに対応するマスクが一つもない場合はエラーを返す
データベースからAとBを削除

シーケンス図

https://gist.github.com/yoshimuraYuu/95b4d8134e283ddeb920

レアリティの操作

ソーシャルゲームの多くはレアリティがSSRだと1%、Nだと50%などと決められている。このような確率を表現する手段として、マスクの立っているビットの量を使う。例えばマスクで立っているビット数が1つであれば、ユーザーにとってCを求めるのが容易になるし、一方で$n$に近い数であればCを求めるのは困難になる。このように、ハッシュ値を計算する試行回数を利用して、レアリティを操作することができる。

公平性

これのポイントは、ガチャをサーバーが生成した（と思われる）乱数からハッシュ値の衝突確率という問題に切り替えたことだと思う。こうすることで、不透明なサーバー内でのガチャ処理を行わずに、透明なハッシュ値によるガチャを行うことができる。ユーザーは、サーバーにデータを送る前に自分が引いたガチャの結果を知ることができるし、もしサーバーで検証して自分で確かめた結果と異なる場合は、どちらが悪いのか確かめることができる。
また、これは計算の直前にAを与えている。これがソルトのような役割を果すので、あらかじめ大量に計算するのは無駄と思われる。

課金

ユーザーが課金した場合、多くのゲームは無課金のガチャに比べてレアカードの出現率が高くなる。このような処理は、ユーザーのIDに課金情報を持っておいて、課金状態やガチャの種類によってマスクの一覧を変えればいい。ただし、これらマスクは全てユーザーに公開されている必要がある。

データCの販売

業者などが介入した場合、業者はAとBを入手した後、ハッシュ値を求めるための高性能なコンピューターやハードウェアを用いて、高速にCを計算し、それをオークションなどで売りさばく可能性がある。これを防ぐためには次の手順を実行すればよい。

AとBをサーバーが発行する際に、データベースへユーザー情報を保存する
アプリケーションがCを送る際、ユーザー情報をともに送信する
サーバーはデータベースからユーザー情報を取得し、それと送信されたユーザー情報を検証する