公平なガチャシステムを利用した二分割可能な仮想通貨

# はじめに

[公平なガチャ](http://qiita.com/yyu/items/90db09c57514758bd68c)についてこれまで考えてきたが、どうやらこのシステムを用いると**二分割可能な仮想通貨**を構成できることが分った。ここで言う二分割可能とは、ある価値を持つ仮想通貨を二つのデータA, Bに分けたとき、それぞれのAやB単体では価値がないが、AとBを合せることで元の価値に戻るという仮想通貨である。さらにこの記事で紹介する方法は、片方のデータAを秘密にしたままデータBを他人に計算させるということも可能である。これまで考えていたガチャシステムに簡単な改造を施すだけで、このような性質を持つ仮想通貨となった。
この記事について分かりにくい部分や改善点、質問などがある場合は気軽にコメントなどで指摘して欲しい。

```math
\def\concat#1#2{#1 \, || \, #2}
\def\verify{\stackrel{?}{=}}
```

# 記号の意味

この記事では次のような記号を、次のような意味で利用する。

|記号|意味| 
|:-------------|:---------|
| $Sign_A(B)$ | 秘密鍵$A$で$B$に[署名](https://ja.wikipedia.org/wiki/%E3%83%87%E3%82%B8%E3%82%BF%E3%83%AB%E7%BD%B2%E5%90%8D) |
| $Extract_A(B)$ | 公開鍵$A$で署名されたデータ$B$を展開 |
| $Hash(A)$ | $A$のハッシュ値を計算 |
| $A := B $ | 変数$A$に$B$を代入 |
| $\concat{A}{B} $ | $A$と$B$を結合 |
| $A \, \\& \, B$ | $A$と$B$の論理積 |
| $A = B$ | $A$と$B$が等しい |
| $A \ne B$ | $A$と$B$が等しくない |
| $A \verify B$ | $A$と$B$が等しいかどうかを検証 |

# 公平なガチャの仕組み

アイディアだけを述べると、まずガチャを回したいユーザーは運営から**ソルト**のような乱数と$n$ビットの値を受け取り、それに適当なデータを足してハッシュ値を計算する。もしハッシュ値と$n$ビットの値との論理積がマスクと一致したら、カードが得られるというものである。詳細を以下に述べる。

## セットアップ

1. 運営は$n$ビットの値で構成される**マスク**とカードを対応付けるテーブルを用意する


    |マスク|対応するカード|
    |:----:|:-----------:|
    | $0000 \dots 1001$ | $K_1$ |
    | $0010 \dots 0010$ | $K_2$ |
    | $1110 \dots 0111$ | $K_3$ |
    | $1011 \dots 1011$ | $K_3$ |
    | $\vdots$ | $\vdots$ |
    | $1111 \dots 0100$ | $K_i$ |
2. 運営はSSH通信などと同じように[公開鍵暗号](https://ja.wikipedia.org/wiki/%E5%85%AC%E9%96%8B%E9%8D%B5%E6%9A%97%E5%8F%B7)の秘密鍵$d$と公開鍵$e$を用意し、公開鍵を全ユーザーに対して公開する
3. ユーザーは運営と同様に公開鍵暗号の秘密鍵$D$と公開鍵$E$を用意し、公開鍵をサーバーに公開する

## プロトコル

1. ユーザーがガチャを回そうとすると、運営はデータ$A$と呼ばれる乱数と$n$ビットの乱数データ$B$を返す。データ$X$はデータ$A$とデータ$B$を合せたデータに運営が署名したものである

    ```math
    X := Sign_d(\concat{A}{B})
    ```
2. ユーザーはランダムなデータ$C$を生成し、それにユーザーの鍵で署名する。そのデータを$Y$とする
    
    ```math
    Y := Sign_{D}(C)
    ```
3. 次のようなデータ$F$を計算する[^d_to_f]

    ```math
    F := B\, \& \, Hash(\concat{A}{Y})
    ```
4. データ$F$がマスクのいずれかと一致する場合、ユーザーは次のデータを運営に送信する（もしデータ$F$と一致するマスクがない場合は、(2)からやりなおす）
    - データ$A$とデータ$B$
    - 運営によって署名されたデータ$X$
    - データ$C$と、データ$C$にユーザーが署名したデータ$Y$
    - ユーザーの公開鍵$E$
5. 運営は次のことを検証する
    - $X$の署名を展開した結果と送信されたデータ$A$と$B$を結合した結果が一致するか
        
        ```math
        Extract_e(X) \verify \concat{A}{B}
        ```
    - $Y$の署名を展開した結果と送信されたデータ$C$が一致するか

        ```math
        Extract_E(Y) \verify C
        ```
6. 運営は送信された$Y$からアプリケーションと同様に$F'$を計算する

    ```math    
    F' := B\, \&\, Hash(\concat{A}{Y})
    ```
7. サーバーは$F'$に等しいマスクに対応するカードを公開鍵$E$に対応するユーザーに与える
    - もし$F'$に等しいマスクが一つもない場合はエラーを返す

[^d_to_f]: 前回の記事では記号$D$を使っていたが、これはユーザーの秘密鍵$D$と被っていたため、今回は記号を$F$とした。

# ガチャシステムと仮想通貨を繋ぐアイディア

公平なガチャは次のような特徴を持つ。

- 一般的なガチャはゲーム内通貨を入れてガチャを回しカードを得るのに対して、公平なガチャでは特殊なハッシュ値を計算してそれを入れてガチャを回しカードを得る

では、もしカードのかわりにお金が出てくるガチャがあるとしたら、公平なガチャシステムは銀行のような役割を持つことになり、ハッシュ値がそのままお金になるというアイディアである。

# 公平なガチャと二分割可能性

公平なガチャでは、次のようにユーザーがデータ$C$に署名をする。
    
> ```math
> Y := Sign_{D}(C)
> ```

ここで、なぜ署名をするのかというと、公平なガチャに業者が介入しないようにするためである。もしここで署名をしなければ、ユーザーはデータ$A$やデータ$B$を外部の業者に渡して、データ$C$を計算して貰うことができる。業者にはデータ$A$やデータ$B$からデータ$X$を求めることはできないから、結果を業者に横取りされることはない。
つまり、この公平なガチャから業者（第三者）が介入できるように署名する部分を取り除くと、冒頭で述べたような二分割可能な仮想通貨として利用できると考えられる。

# 二分割可能な仮想通貨の仕組み

例えば**アリス**と**ボブ**がこの二つの通貨を使う例を考える。なお、ここではガチャシステムのことを**銀行**という。銀行はカードのかわりにお金をユーザーへ渡すガチャである。

## セットアップ

1. 銀行は$n$ビットの値で構成される**マスク**とお金を対応付けるテーブルを用意する

    |マスク|対応するお金|
    |:----:|:-----------:|
    | $0000 \dots 1001$ | 10000円 |
    | $0010 \dots 0010$ | 20000円 |
    | $1110 \dots 0111$ | 100000円 |
    | $1011 \dots 1011$ | 100000円 |
    | $\vdots$ | $\vdots$ |
    | $1111 \dots 0100$ | 200000円 |
2. アリスは銀行に自分の公開鍵を登録する


## プロトコル

1. アリスは銀行から次のデータを受け取る
    - データ$A$とデータ$B$
    - データ$A$とデータ$B$に銀行が署名したデータ$X$
2. アリスはボブにデータ$A$とデータ$B$を送信する
3. ボブはアリスになんらかの仕事を依頼する
4. ボブは次を満すデータ$C$とデータ$F$を計算する
    
    ```math
    F := B\, \& \, Hash(\concat{A}{C})
    ```
5. データ$F$がマスクのいずれかと一致する場合、ボブはデータ$C$を保存する。（もしデータ$F$と一致するマスクがない場合は、(3)からやりなおす）
6. ボブはアリスに依頼した仕事が完了したら、データ$C$をアリスへ送信する
7. アリスは次のデータを銀行へ送信する
    - データ$A$とデータ$B$
    - データ$X$
    - データ$C$
    - アリスの公開鍵
8. 銀行は次のことを検証する
    - $X$の署名を展開した結果と送信されたデータ$A$と$B$を結合した結果が一致するか
9. 銀行は送信された$C$からアプリケーションと同様に$F'$を計算する

    ```math    
    F' := B\, \&\, Hash(\concat{A}{C})
    ```
10. 銀行は$F'$に等しいマスクに対応するお金をアリスに与える

# まとめ

今回は公平なガチャを使って二分割可能な仮想通貨を考えることができたと思う。もし改良する方法などを思いついた方がいらっしゃれば、気軽にコメントなどで教えて欲しいと思う。