公平なガチャの私考と、コミットメントを用いた、確率に範囲を持たせることでより射幸心を煽る公平なガチャ

3行でまとめると:

* 公平なガチャを実現するのに必要な技術を、コミットメントを中心に解説します
* 先行研究の公平なガチャのプロトコルを紹介します
* 数値の代わりに景品表そのものをコミットメントに入れるという簡単な工夫で、確率に範囲を持たせた公平なガチャのプロトコルができます

本稿は次稿「[次稿のサクラ耐性と妨害耐性のあるコミットメントを用いた公平な抽選](https://qiita.com/xyx_is/items/e427f707f86c64ba8883)」を考えた際に、公平なガチャのプロトコルについてまとめたものです。

# 背景
近年のソーシャルゲームの隆盛により、ゲームがユーザの手元端末で実行されるだけでなく、ゲーム運営者のサーバとユーザの通信によって実行されるようになってきています。ソーシャルゲームの中でも、ガチャと呼ばれる、確率的にユーザが景品を入手する形式のゲームは、ユーザの射幸心を強く煽ることが知られており、高収益コンテンツとして企業各社によって盛んに開発されています。
しかし、ゲームのユーザは一般的に確率について心理的な理解を持っているとは限らず[^ref1]、「自分の欲しい景品に限って、出にくくなっているのではないか」という妄執にとりつかれがちです。これは、ユーザの手元端末で実行するゲームであっても、「物欲センサー」[^1]という俗語が生まれていることからも伺えます。
特にソーシャルゲームにおいては、ユーザにとってサーバの中身はブラックボックスであるため、ガチャを実行するためにサーバで乱数生成を行うと、ユーザは「実際は乱数生成を行っておらず、景品を出しにくくしているのではないか」という疑念を抱えやすくなります。

一方で、暗号プロトコルの研究では、公平なコイントスに代表されるように、従来乱数を用いて行われたゲームを、プロトコルによって公平性を保証する技術が知られています。
暗号プロトコル技術により公平なガチャが実現できれば、クライアントの通信部分をオープンソースで実装することでゲームの公平性をユーザに証明でき、ユーザに安心感を与え、ガチャという高収益産業をより活性化することができます。

[^ref1]: 西條由起、遠藤雅伸 (2015) [数学的確率に対する主観確率の誤認知に関する研究](http://endohlab.org/paper/probabilitydifference.pdf) 日本デジタルゲーム学会
[^1]: [物欲センサー - ニコニコ大百科](http://dic.nicovideo.jp/a/%E7%89%A9%E6%AC%B2%E3%82%BB%E3%83%B3%E3%82%B5%E3%83%BC), [物欲センサー 【ピクシブ百科事典】](https://dic.pixiv.net/a/%E7%89%A9%E6%AC%B2%E3%82%BB%E3%83%B3%E3%82%B5%E3%83%BC)

## 先行研究
暗号プロトコル技術による公平なガチャ・抽選の先行研究には以下のようなものが挙げられます。

* [公平なガチャシステムのまとめ](https://qiita.com/yyu/items/ffa5960a721a0b36a354)
* [利用者が検証可能なガチャの実装](https://qiita.com/mikage/items/8bd7afbe3300d9e39f90)
* [Ethereumで賭博場ルールを考えてみた](https://qiita.com/s0sasaki/items/fce1da65b3dcad35c1ed)
* [ブロックチェーンとスマートコントラクトで、抽選の公正性を証明する](https://qiita.com/yaiwase/items/335b7a52186130df4ec5)
* [Solidityで作る公平なガチャ - lotzの日記](http://lotz84.hatenablog.com/entry/2018/01/07/030223)

最近はブロックチェーンを用いたプロトコルや、量子コンピュータを用いた研究の方が隆盛のようですが、ここでは、特に[公平なガチャシステムのまとめ](https://qiita.com/yyu/items/ffa5960a721a0b36a354)の3から6に示された、コミットメントという古典的技術を用いたプロトコルについて考えます。

# 公平なガチャ私考
## 「公平」とは？
背景に基づけば、運営が提示した確率で、本当に景品がもらえることをユーザが検証できるということが解決したい問題となります。[量子コンピュータを利用した公平なガチャ](https://qiita.com/yyu/items/efcf471ce9b97e885957)には「公平に不正ができる」という表現が登場していますが、筆者には難しいことがわからぬので、この記事では以下を「公平」ということにします。

1. ユーザは、景品がもらえる確率が提示された通りであることを検証できる
2. プロトコルが正しく実行された時、ユーザと運営は、自分の通信履歴を提示することで、プロトコルが正しく実行されたことと、ユーザが受け取る景品は何かを司法機関に証明できる
3. プロトコルが正しく実行されなかったとき、ユーザと運営は、自分の通信履歴を提示することで、正しく実行されなかったことを司法機関に証明できる
4. プロトコルが途中で中断された場合は、司法機関の立会いの下、プロトコルを継続するものとする

プロトコルが正しく実行されたにも関わらず、ユーザが景品をもらえない事態や、ユーザがもらえないはずの景品をもらえると偽る事態は、2の性質を利用して、司法機関に証明を行うことで防ぐことができます。

ユーザと運営しかいない状態で、何も前提知識のない第三者に証明を行うことは不可能（何も前提知識がないと、ユーザ・運営の提示した通信履歴全体が偽造かどうか判別できない）なので、2と3で第三者に証明をするには、最低限、公開鍵基盤のような機関が必要になります。

また、プロトコルが途中で中断された場合、「送信者が意図的に送らなかった」「送信したが通信途中で何かあって受信できなかった」「受信したが受信者が受信しなかったと偽っている」は第三者に区別できません。プロトコルの中断の扱いについては、様々な研究がなされている難しい問題ですが、ここでは簡単のため、4のように、司法機関の立会いの下プロトコルを継続するものとします。

## 要素技術
### 電子署名
Aliceは情報mに電子署名をすることができます。Alice以外は、電子署名された情報を検証することで、確かにAliceが情報mに電子署名したと確認することができます（正当性）。また、Alice以外がAliceが電子署名したように装うことはできません（安全性）。
RSA公開鍵暗号方式やDSA署名などで電子署名が実現できることが知られています。

上記の「安全性」により、電子署名を付けては、偽造防止（悪意ある第三者が偽装した通信を偽物だと区別できる）に使用できるだけでなく、否認防止（第三者にAliceの電子署名を見せることで、その通信がAliceによるものだと証明できる）にも使用することができます。さらに、通信相手が情報を送信する際に、相手が送信したい情報に加えて、プロトコル開始時から現在までの（自分が相手に送信した情報を含めた）通信履歴全て（のハッシュ値）を付けて、電子署名付きで送信させることで、自分が相手に送信した情報を相手が受信したことの否認防止を実現でき、一つのプロトコルの中での通信であることを明確にすることが出来ます。

### コミットメント
コミットメントは、（暗号文など）受信者に読めない情報を送信し、さらに後から付加的な情報（暗号文の鍵など）を送信することで受信者に読めるようにする技術です。コミットメントにより、最初に情報を送信してから、受信者がその情報を読めるようになるまでに時間差を持たせることができるため、様々な通信プロトコル技術に応用ができます。

#### 定義
コミットメントは、「コミット」と「公開」という2つの通信のフェーズからなります。最初に「準備」というオプショナルなフェーズがつく場合があります。

<dl>
  <dt>前準備(Setup)</dt>
  <dd>通信に必要なメッセージを準備するオプショナルなフェーズです。</dd>
  <dt>コミット(Commit)</dt>
  <dd>Aliceは送りたいメッセージ$m$を暗号化した情報$C$をBobに送信します。$m$自体はAliceが秘匿します。</dd>
  <dt>公開(Open)</dt>
  <dd>Aliceは$C$に対する付加的な情報$r$と送りたいメッセージ$m$をBobに送信します。Bobは$C$と$r$により、$m$が正しいかどうかを検証します。</dd>
</dl>

#### 性質
コミットメントは、以下の性質を持ちます。

<dl>
  <dt>秘匿性(hinding)</dt>
  <dd>
    Bobは、公開のフェーズより前に$m$を知りえないという性質です。
    <dl>
      <dt>完全秘匿</dt>
      <dd>Bobに無限の計算能力があっても$m$を知ることができない場合を完全秘匿といいます。すなわち、Bobがコミットフェーズまでに保持・受信するすべての情報を使用しても、Aliceの送りたいメッセージが一意に定まらず、$m$を推測できないことをいいます。</dd>
      <dt>計算量秘匿</dt>
      <dd>Bobが$m$を知りえないことが計算量に依存する場合を計算量秘匿といいます。</dd>
    </dl>
  </dd>
  <dt>拘束性(binding)</dt>
  <dd>
    Aliceが$m$以外の$m'$と、$m'$に対応する付加的な情報$r'$を公開のフェーズで偽って送信しても、Bobの検証を通過しないという性質です。
    <dl>
      <dt>完全拘束</dt>
      <dd>Aliceに無限の計算能力があっても、Bobの検証を通過する$m'$と$r'$が存在しない場合を完全拘束といいます。すなわち、Bobがコミットフェーズまでに保持・受信するすべての情報に対して、Aliceの送りたいメッセージが一意に定まることをいいます。</dd>
      <dt>計算量拘束</dt>
      <dd>Aliceが$m'$と$r'$の組を見つけられないことが計算量に依存する場合を計算量拘束といいます。</dd>
    </dl>
  </dd>
</dl>

完全秘匿で完全拘束なコミットメントは存在しません。上記の通り、「Bobがコミットフェーズまでに保持・受信するすべての情報」に対して、「Aliceの送りたいメッセージ」が一意に定まるか定まらないかで、完全秘匿か完全拘束かが決まってしまいます。

#### 簡単なコミットメントの作り方
##### 完全秘匿・計算量拘束なコミットメント
[Wikipediaのビットコミットメントで説明されている離散対数問題を用いた方式](https://ja.wikipedia.org/wiki/%E3%83%93%E3%83%83%E3%83%88%E3%82%B3%E3%83%9F%E3%83%83%E3%83%88%E3%83%A1%E3%83%B3%E3%83%88#%E9%9B%A2%E6%95%A3%E5%AF%BE%E6%95%B0%E5%95%8F%E9%A1%8C%E3%81%AB%E5%9F%BA%E3%81%A5%E3%81%84%E3%81%9F%E5%AE%8C%E5%85%A8%E7%A7%98%E5%8C%BF%E3%81%8B%E3%81%A4%E8%A8%88%E7%AE%97%E9%87%8F%E7%9A%84%E6%8B%98%E6%9D%9F%E3%81%AA%E6%96%B9%E5%BC%8F)を、説明のために簡略化した方式を紹介します。

###### 通信内容
1bitのメッセージ$m \in \\{0, 1\\}$を送ることを考えます。

1. **前準備**: Bobは離散対数問題 $y=a^x \bmod p$ の条件を満たす$a$, $p$, $x$, $y$（$p$は素数、$0 < x < p-1$）の組をランダムに生成します。Bobは$a$, $p$, $y$をAliceに送信し、$x$は秘匿します。
    * 離散対数問題の性質より、$a$, $p$, $y$から$x$を求めることは計算量的に困難です。
2. **コミット**: Aliceは$r$ ($0 \le r < p-1$)をランダムに生成し、$C = a^r y^m \bmod p$をBobに送信します。
    * すなわち、 $m = 0$ の時 $C = a^r \bmod p$ 、 $m = 1$ の時 $C = a^r y \bmod p$
3. **公開**: Aliceは$r$, $m$をBobに送信し、Bobは$C = a^r y^m \bmod p$を検証します。

###### 完全秘匿
Bobは$C = a^r y^m \bmod p$を受け取り、無限の計算能力で、$C = a^d \bmod p$である$d$を求めても、

```math
a^r * y^m = a^{(r + x * m)} \\
C = a^{(r + x * m)} \bmod p \\
r + x * m \equiv d \pmod{p-1}
```

より、 $m = 0$ で $r = d$ なのか、 $m = 1$ で $r = d - x$ なのかは区別がつかないため、完全秘匿であると言えます。

###### 計算量拘束
Aliceは、 $m=0$ と $r$ 、 $m'=1$ と $r'$ で、同一の$C$を生成できるような$(r, r')$の組を見つけることが計算量的に困難であることを示せば、計算量拘束であることが言えます。
これを、離散対数問題に矛盾させる形で背理法で示します。すなわち、$(r, r')$の組を現実的な計算量で見つけた場合、離散対数問題が解けてしまうことを示します。見つけた$(r, r')$に対して、以下が成立します。

```math
C = a^r \bmod p = a^{r'} y \bmod p \\
a^r \equiv a^{r'} y \pmod{p} \\
a^r \equiv a^{r'} a^x \pmod{p} \\
a^r \equiv a^{(r' + x)} \pmod{p} \\
r \equiv r' + x \pmod{p-1} \\
x \equiv r - r' \pmod{p-1}
```

これにより、前準備で用意した離散対数問題が解けてしまったため、矛盾が発生し、計算量拘束であることが言えます。


##### 計算量秘匿・完全拘束なコミットメント
公開鍵に対して、秘密鍵が一意に定まる公開鍵暗号方式（[原理的なRSA公開鍵暗号方式](https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7)など）を使用すれば、計算量秘匿・完全拘束なコミットメントが簡単に作成できます。

###### 通信内容
十分に情報量の多い[^2]メッセージ$m$を送ることを考えます。

1. **コミット**: Aliceはランダムに公開鍵$n$と秘密鍵$p$を生成します。Aliceは公開鍵$n$を使用して$m$を暗号化し、暗号文$C$と公開鍵$n$をBobに送信します。
2. **公開**: Aliceは秘密鍵$p$をBobに送信します。Bobは$m$を$C$と$p$に復号できるため、送信する必要はありません。Bobは$p$が$n$の秘密鍵であることを検証します。

[^2]: $m$の情報量が少なく、Bobがブルートフォースで$m$の全パターンに対して$C$が生成されるか試行できる場合は、ノンスを結合するか、共通鍵暗号方式などを用いてランダムな鍵を生成し$m$を暗号化、鍵をコミットメントに入れて、共通鍵暗号で暗号化された$m$と一緒に送ることを考えます。

###### 計算量秘匿
暗号文$C$と公開鍵$n$から平文である$m$を求めることは、公開鍵暗号方式の性質より計算量的に困難です。

###### 完全拘束
定義より、秘密鍵$p$は公開鍵$n$に対して一意なので、Aliceが公開時に送りうる内容は一意に定まるため、完全拘束です。

##### 計算量秘匿・計算量拘束なコミットメント
もっと一般的には、メッセージ$m$を送る際に、$m$にノンス[^3]$r$を結合したハッシュ値をコミットで送信、$m$と$r$を公開時に送信するという手法が行われています。
ハッシュの衝突性について、メッセージ$m$に対してハッシュ値を衝突させられるようなノンスが常に存在すれば完全秘匿、逆にメッセージとノンスの取り方によってハッシュ値が衝突しえないことを保証できれば完全拘束であると言えます。

[^3]: ハッシュにランダム性を持たせるためのランダムな文字列、パスワード保存のSALTのようなもの

##### コミットメントについての参考文献
* [調布市公開講座の資料 - 電気通信大学](http://www.quest.is.uec.ac.jp/ogawa/index/chofukoukai.pdf)
* [電子情報通信学会知識ベース 1群（信号・システム） 3編（暗号理論） 9章 暗号プロトコル](http://www.ieice-hbkb.org/files/01/01gun_03hen_09.pdf)
* [Introduction to Cryptography Lecture 14](https://cs.nyu.edu/courses/spring12/CSCI-GA.3210-001/lect/lecture14.pdf)

### 総和の剰余
m人のユーザが0以上N未満の整数を乱数として生成するには、各ユーザに0以上N未満の整数を送信させ、その総和をNで割った数を乱数とするという手法がよく用いられます。Nが2の場合は、この操作は排他的論理和xorと同じ操作となります。

m人のユーザの内、少なくとも1人でも他のユーザと非協力関係にあり、そのユーザは他ユーザの送信する整数を知らず、他ユーザもそのユーザの送信する整数を知らない場合、この操作の結果は1/Nの等確率で0以上N未満の整数を一様乱数として生成できるとみなすことができます。

ただ、筆者はその証明を知らないため、ご存知の方は教えてください[^4]。

[^4]: おそらく、各ユーザと操作結果にv(0, 0)からv(m-1, n-1)までの利得を割り当てた（v(u, r)はu番目のユーザがrの利得を得ることを表す）非協力ゲームの混合戦略ゲームを考えた時に、各ユーザが1/Nの等確率で0以上N未満の整数を出すのがナッシュ均衡であるのが示せるのではないかと予想しています。

## プロトコルへの応用例
### 電話越しのコイントス
コミットメントと総和の剰余のもっとも古典的で有名な応用例は、Manuel Blumの[電話越しのコイントス](http://www.cs.cmu.edu/~mblum/research/pdf/coin/in4.html)でしょう。

AliceとBobが電話越しにコイントスをするには、以下のようなプロトコルを、電子署名つきで実行すればよいことが知られています。
1. AliceとBobはそれぞれランダムなビットa, bを生成
2. AliceとBobは、それぞれa, bをコミットメントに入れて、互いにコミット
3. 互いに、上ステップを受信してから、自分のコミットメントの公開を送信、AliceとBobはaとbの両方を得る[^5]
4. AliceとBobは、aとbの総和の剰余（すなわちxor）を取り、0なら表、1なら裏とする

このプロトコルにより、AliceとBobは1/2の確率で表と裏のコイントスの結果を得ることが出来ます。

AliceとBobの通信の順序が決まっている場合は、以下のように後者がビットをコミットメントに入れずに直接送信することも可能です。

1. AliceとBobはそれぞれランダムなビットa, bを生成
2. Aliceは、aをコミットメントに入れて、コミットをBobに送信
3. Bobはaのコミットを受信してから、bをAliceに送信
4. Aliceは、bを受信（この時点でAliceはaとbの両方を得る[^5]）してから、aのコミットメントの公開をBobに送信
5. Bobはaとbの両方を得る
6. AliceとBobは、aとbの総和の剰余（すなわちxor）を取り、0なら表、1なら裏とする

[^5]: 通信相手に悪意がある場合は、コミットメント公開のステップで、相手に先に公開させることで、相手のビットを受信して結果が自分より不利になったことが分かった場合に通信を中断することが考えられます。本稿では、各通信に電子署名などを付することで、通信が中止された場合でも第三者に通信が正しく行われなかったことを証明できることを以って公平としていますが、通信中断の場合まで考慮した研究もあるようです。 [Protocols for Multiparty Coin Toss With Dishonest Majority](https://eprint.iacr.org/2012/643.pdf)

### 確率付きコイントス
上記「電話越しのコイントス」では、表と裏の結果が1/2と1/2の確率でしたが、以下のように改変することで、$\frac{m}{N}$と$1-\frac{m}{N}$の確率で結果が得られるように簡単に拡張できます。

1. AliceとBobはそれぞれランダムな整数a, b($0 \le a, b < N$)を生成
2. AliceとBobは、それぞれa, bをコミットメントに入れて、互いにコミット
3. 互いに、上ステップを受信してから、自分のコミットメントの公開を送信、AliceとBobはaとbの両方を得る
4. AliceとBobは、aとbの総和の剰余($a + b \bmod N$)を取り、m未満なら表、m以上なら裏とする

mが1の場合は、総和の剰余の代わりに、$a = b$が成立するかどうかを使ったほうが簡単かもしれません。

# コミットメントを用いた公平なガチャ
## 問題の定義
### 登場人物
* **ユーザ**: 景品が欲しい
* **運営**: ユーザから料金が欲しい

### 信頼できる第三者
* **公開鍵基盤**: ユーザと運営の公開鍵を公開し、それがユーザと運営の公開鍵であることを証明します。
* **司法機関**: ユーザや運営からの訴えを受け、訴えた人がその主張を証明した時、然るべき処置をします。

### 行いたいこと
* 運営は、ガチャの各景品が出る確率を提示する
* ユーザは運営に料金を支払うことで、ガチャを行う権利を得る
* ユーザは、ガチャを行うことで、運営が提示した確率で景品をもらう

### 満たすべき性質
1. ユーザは、景品がもらえる確率が提示された通りであることを検証できる
2. プロトコルが正しく実行された時、ユーザと運営は、自分の通信履歴を提示することで、プロトコルが正しく実行されたことと、ユーザが受け取る景品は何かを司法機関に証明できる
3. プロトコルが正しく実行されなかったとき、ユーザと運営は、自分の通信履歴を提示することで、正しく実行されなかったことを司法機関に証明できる
4. プロトコルが途中で中断された場合は、司法機関の立会いの下、プロトコルを継続するものとする

## コミットメントを用いた公平なガチャのプロトコル
先行研究の[コミットメントを用いた公平なガチャシステム](https://qiita.com/yyu/items/fce9b33c784e0631ddf6#%E3%82%B3%E3%83%9F%E3%83%83%E3%83%88%E3%83%A1%E3%83%B3%E3%83%88%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E5%85%AC%E5%B9%B3%E3%81%AA%E3%82%AC%E3%83%81%E3%83%A3%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0%E3%81%AE%E3%83%97%E3%83%AD%E3%83%88%E3%82%B3%E3%83%AB) に示されたプロトコルを、本稿の説明に沿う形で記載します。

以下のプロトコルでは、情報を送信する際に、プロトコル開始時からの通信履歴（のハッシュ値）を付けた、電子署名付きの情報を送信するものとします。

1. 運営は、確率に応じて整数Nを用意し、0以上N未満の各整数に対して、対応する景品を記載した景品表を提示する。同じ景品が複数の整数に対応しており、対応する整数の数がkであることが、景品を受け取る確率が$\frac{k}{N}$であることを表している。

    |整数|景品 |
    |---:|:----|
    |   0|景品A|
    |   1|景品B|
    |   2|景品B|
    |$\vdots$|$\vdots$|
    | N-1|景品X|
2. ユーザは、
    1. 提示された景品表を見て、自分の欲しい景品が出る確率を確認し、
    2. ガチャに参加表明する
3. 運営は、
    1. 0以上N未満の整数mをランダムに生成し、
    2. mのコミットメントのコミットの情報をユーザに送信する
4. ユーザは、
    1. mのコミットメントを受信してから、
    2. 0以上N未満の整数nをランダムに生成し、
    3. nを運営に送信する
5. 運営は、
    1. ユーザの入金を確認・nを受信してから、
    2. mのコミットメントの公開の情報をユーザに送信、
    3. 景品表に従って、mとnの総和の剰余($m + n \bmod N$)に対応した景品をユーザに与える
6. ユーザは、mのコミットメントを検証し、与えられた景品が正しいかを検証する

ユーザは、ステップ1で提示された景品表に、自分の欲しい景品がいくつ入っているかを確認することで、景品をもらえる確率を検証することができます。
プロトコルが正しく実行された場合、運営とユーザは互いに履歴付き・電子署名付きで通信を行っているため、自らの通信履歴に含まれる相手の電子署名を提示することで、司法機関に受け取るべき景品を証明することができます。
このプロトコルが正しく実行されなかった場合は、ステップ6でユーザが検証を行うため、この検証結果をもって正しく実行されなかったことを司法機関に証明することができます。
ステップ4でユーザがnを送信してから、ステップ5で運営がmを公開しない・景品を与えない可能性がありますが、その場合はユーザが司法機関に自分の選んだnを伝え、司法機関立会いの下、運営がmを公開・景品を与えるものとします。

より安全性を高めたい場合は、信頼できる第三者として、料金預託機関と配達証明機関を想定し、ユーザは参加する際に料金預託機関に料金を預託して、運営は通信履歴と景品の配達証明を料金預託機関に提示することで料金を受け取れるようにすれば、ユーザ・運営が損をしないプロトコルを作成できるでしょう。

# 確率に範囲を持たせた公平なガチャ
上記のプロトコルでは、景品表が予め公表されていたため、全ての景品が貰える確率は予め決まっていました。これを、景品表そのものをシャッフルしてコミットメントに入れることで、確率に範囲を持たせることが可能になります。

## プロトコル
1. 運営は、確率に応じて整数Nを用意し、各景品が出る確率を表わす景品確率表を提示する。以下に例を示す:

    |景品 |最低確率|最高確率|
    |:----|:------:|:------:|
    |景品A|   1/N  |  10/N  |
    |景品B|   2/N  |   N/N  |
    |景品C|   0/N  |  10/N  |
    |$\vdots$|$\vdots$|$\vdots$|
    |景品X|   5/N  |  15/N  |
2. ユーザは、ガチャに参加表明する
3. 運営は、
    1. 0以上N未満の各整数に対して、対応する景品を記載した景品表をランダムに作成する。景品表に登場する各景品の出現回数は、事前に提示した景品確率表の範囲に従う。

        |整数|景品 |
        |---:|:----|
        |   0|景品C|
        |   1|景品A|
        |   2|景品B|
        |$\vdots$|$\vdots$|
        | N-1|景品C|
    2. 景品表のコミットメントのコミットの情報をユーザに送信する
4. ユーザは、
    1. 景品表のコミットメントを受信してから、
    2. 0以上N未満の整数nをランダムに生成し、
    3. nを運営に送信する
5. 運営は、
    1. ユーザの入金を確認・nを受信してから、
    2. 景品表のコミットメントの公開の情報をユーザに送信、
    3. 景品表に従って、nに対応した景品をユーザに与える
6. ユーザは、
    1. 景品表のコミットメントを検証し、
    2. 景品表の確率が提示された範囲内かを検証し、
    3. 与えられた景品が正しいかを検証する

## 確率が固定されたプロトコルとの比較
先の章で紹介した「コミットメントを用いた公平なガチャのプロトコル」、すなわち確率が固定されたプロトコルと、本章の確率が固定されていないプロトコルを比較します。

* 確率が固定されたプロトコルは、景品表を最初に検証するため、確率を変動させることができません。確率が固定されていないプロトコルは、景品確率表が正しいことを事後的に検証を行うことで証明しているため、逆に言えばユーザは事前に景品確率表が正しいことを検証することができません。
* 通信容量の観点から考えると、確率が固定されたプロトコルではmは$\log{N}$の情報量ですが、確率が固定されていないプロトコルでは景品表は$\log{N!}$の情報量を持つため、固定されていないプロトコルは通信容量が大幅に増えます。
* 確率が固定されていないプロトコルは、ユーザがガチャを行った後に実際の確率を知ることができるため、より射幸心を煽ることができる可能性があります。
    * ユーザが欲しい景品がより高い確率で出ているときに外した方が、ユーザにとってより悔しい結果となるでしょう。
    * 運営は実際の確率を隠すことができるため、[パチンコの確率変動や潜伏確変](https://ja.wikipedia.org/wiki/%E7%A2%BA%E7%8E%87%E5%A4%89%E5%8B%95#%E6%BD%9C%E4%BC%8F%E7%A2%BA%E5%A4%89%EF%BC%88%E6%BD%9C%E7%A2%BA%E3%80%81%E9%9A%A0%E3%82%8C%E7%A2%BA%E5%A4%89%EF%BC%89)に相当するような確率の変化を派手な演出とともに行うことで、ユーザに「今は実際の確率が上がっているのではないか」という思いを抱かせ、より射幸心を煽ることができる可能性があります。（ちなみにパチンコの確率変動は法律などで規制されているそうです。）

# まとめ
本稿では、公平なガチャのプロトコルを実現するのに必要な技術をコミットメントを中心に解説し、コミットメントを用いた確率が固定された公平なガチャのプロトコルを紹介しました。そして、景品表そのものをコミットメントに入れるという簡単な工夫で、確率を範囲で表わした、確率が固定されていない公平なガチャのプロトコルが実現できることを示しました。

次稿「[次稿のサクラ耐性と妨害耐性のあるコミットメントを用いた公平な抽選](https://qiita.com/xyx_is/items/e427f707f86c64ba8883)」もよろしくおねがいします。