レディ・プレイヤー１の世界を実現したい

自宅にいることが増えた影響で、よく映画を見るようになりました。最近は「レディー・プレイヤー１」という映画を見ました。公開されたのは2年前で、劇中にガンダムやメカゴジラなど日本のキャラクターが出てくるということで、当時話題になったのを覚えています。

レディー・プレイヤー１にはOasisというバーチャルリアリティーゲームが登場します。亡くなってしまったOasisの作者がゲーム世界の中に特別なアイテムを隠し、それを見つけた人に自分の莫大な遺産を譲り渡すという遺言を残しました。主人公たちは彼が残したアイテムを目指し、汚い手を使って邪魔をしてくる敵達と戦うというストーリーです。

そこでふと、レディー・プレイヤー１のようなゲームを現実に作ることはできないのかと思ったわけです。そこで今回は、レディー・プレイヤー１の世界を実現する方法について考えてみました。こんなことあったらいいな、というおとぎ話と思って聞いてください。

実はレディー・プレイヤー１のような話が現実にも起こっていました。
Satoshi’s Treasureというプロジェクトで、隠された1000個のkeyのうち400個のkeyを見つけることでロックされた100万ドル分のビットコインを手に入れることができるというものです。

keyを見つけるためのヒントが1つずつ公開され、そのヒントを元にkeyを見つけるという謎解きゲームのような仕組みです。

もし、我々が普段遊ぶようなRPGやシューティングゲームの中にそんな賞金が隠されていたらとても面白いと思います。

映画に登場するゲームであるOasisは劇中では企業によって運営されているようだったので、ブロックチェーンの話とは少し違います。
しかし、企業が運営するとなると利益を出さなければならないため、継続的に参加者を集めるような形式にしなければなりません。1回限りで莫大な賞金を出すというのはなかなか難しいのではないでしょうか。

# ブロックチェーンゲーム

であれば、ブロックチェーンをつかってゲームと報酬を紐づけることはできないでしょうか。ブロックチェーン上に作る分散アプリケーションであればそのブロックチェーン自体が動いている限りはサービスが終了することも無いでしょう。物好きな誰かが、死ぬ間際ブロックチェーン上に大金を残していくなどということもあるかもしれません。それこそまさにレディー・プレイヤー１の世界です。

では、分散アプリケーションを使ってどのようにゲームを動かすのでしょうか。
カードゲームやボードゲームなど、ターンベースのゲームであれば案外簡単に実現できるのではないでしょうか。単にスマートコントラクトで処理を行えば可能だと思います。
処理の遅延の問題が考えられますが、トランザクションを1.5秒ほどで処理が可能なEOSやサイドチェーンを使った高速処理を行うことができるPlasmaなども存在するので、大きな問題では無いでしょう。
ブロックチェーンを使ったゲームは実際に多く存在し、カードゲームなどもあります。

Plasmaチェーンを使ったRelentlessというカードゲームは100% on Blockchainで動いていることを謳っています。
https://loom.games/en/


# 分散アプリケーションにおけるリアルタイム通信

カードゲームのようなターンベースのゲームではある位程度の遅延は許容できますが、リアルタイム通信が発生するゲームでは遅延が問題になってきます。

そこで今回は分散アプリケーションにおいてリアルタイム通信を実現する方法はないかということを考えました。

分散ゲームの中にはすべてがブロックチェーン上で動いているわけではないものも多くありますが、今回私は中央管理サーバー抜きでゲームを動かしたいと考えています。

分散アプリケーションのリアルタイム通信を考えるにあたって4人が同じフィールドで戦うバトルロイヤルゲームを考えます。各ユーザーはHPを持っており、0になると脱落していき、最後に残ったユーザーが優勝となり、賞金が与えられます。

各ユーザーは1フレームごとに自分の状況（押したボタンなど）を互いに送信し、オフチェーンでゲームの状況を同期します。また、ブロックチェーン上にも同時に書き込むことでブロックチェーン上でもゲームの状況を記録していきます。その結果に応じてブロックチェーン上で賞金が付与されます。

![broadcast.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/914937/63a1276d-6820-18a6-0742-de002776eb24.png)

各ノードについては以下のようなものを想定します。

###ブロックチェーン
ブロックチェーンは内部にデータベースを保持しており、スマートコントラクトを実行できる。
###ユーザークライアント
対戦に参加するユーザーが操作するコンピュータ。ブロックチェーンネットワークに接続しており、識別子としてブロックチェーン上に記録されたユーザーIDをもっている。今回は4台とする。

ユーザー同士のマッチングについてはここでは省略し、マッチング完了後の動作について考えます。ブロックチェーンではトランザクションの処理に時間がかかるのでそのようなリアルタイム通信には向きません。そこで、オフチェーンでのユーザー間通信によってリアルタイム通信を実現します。基本的な流れは以下の通りです。

### 通信の流れ

1. 各ユーザーは対戦相手とゲームの開始ブロック高を受け取る
2. ユーザーが同期しているブロックチェーンのブロック高が開始ブロック高に達すると、以下の同期メッセージをブロードキャストし、ブロックチェーンにも書き込みを行う。
3. 自分以外のユーザー全員からメッセージを受け取るまで待機
4. メッセージの検証を行う
5. メッセージに不正があれば、そのユーザーを排除した上でゲーム画面を描画
6. 直前に受け取ったメッセージおよび自分の押したボタンなどを含めたメッセージを自分以外のメンバーにブロードキャスト
7. ブロードキャストメッセージをブロックチェーンに書き込み
8. 3-7を繰り返す

| 同期メッセージ |
|:-:|
|  ユーザーID |
| ユーザーIDに紐づく秘密鍵による署名 |

| ブロードキャストメッセージ |
|:-:|
| ブロードキャストメッセージヘッダ  |
|  不正の証拠データ |
|  直前に受け取ったブロードキャストメッセージヘッダ*3 |
| ブロードキャストメッセージに対する署名 |

| ブロードキャストメッセージヘッダ |
|:-:|
| ユーザーID  |
| フレーム番号  |
|  押したボタンなど |
|  直前に受け取ったメッセージのハッシュ*3 |
| 不正の証拠データのハッシュ  |
|  ヘッダに対する署名 |

簡単に言うと、更新に全員の署名が必要な分散台帳でゲームデータの同期をとるようなものです。他ユーザーのメッセージに対する署名を返すと同時に次のメッセージを投げています。

# 通信の切断

また、もしユーザーが途中で通信を切断した場合、通信の流れにおけるステップ3の段階で止まってしまうことになります。それを防ぐために、以下のルールを追加します。

- あるフレーム番号K-1に関するメッセージが最後に書き込まれたブロック（スタートブロック）からNブロック以上フレーム番号Kに関するメッセージを書き込んでいないユーザーが存在すれば、そのユーザーの通信が切断されたとみなす。（Nはどれだけの遅延を許容するかによって決める）
- あるフレーム番号Kにおいてユーザーが切断された場合、スタートブロックからN+M先のブロックを次のスタートブロックとする。（Mはそれ以前のブロックが確定するための待機期間。PoWでは6ブロックで確定といわれている）
- ゲーム開始時は開始ブロック高のブロックがスタートブロックとして設定されている

各ユーザーは通信の流れのステップ3の待機段階でもし誰かがメッセージを送っていなかったら、スタートブロックからN+Mブロック生成されるまで待機します。
 
もし、それまでに遅れていたメッセージが届いた場合、通常通りにそのメッセージを処理してブロードキャストメッセージを送信します。

N+Mブロックたってもメッセージが届かなかった場合や、一度メッセージを処理したが、そのメッセージがN+Mブロックのラインに間に合っていなかったことが分かったとき、ブロードキャストメッセージに以下のような切断の証拠データを送信します。

| 切断の証拠データ |
|:-:|
|  切断対象のユーザーID |
|  不足しているメッセージのフレーム番号 |
|  スタートブロックおよびそれより後のN+Mブロックのデータ |


# 検証と不正ユーザーの排除

通信の流れの中にあったステップ4における検証について詳しく見ていきます。

参加ユーザーの中には悪意を持って不正なメッセージを送信しているユーザーがいる可能性があります。そんなユーザーを排除するために検証を行う必要があります。検証時に行われる処理は以下のようにいくつかあります。ただし、検証段階でユーザーを排除するのは他のユーザーから不正の証拠が提出されたときのみで、それ以外の場合は次回の検証時にユーザーを排除します。

### 署名が間違っていないかどうかの検証
電子署名を検証して、参加ユーザーのうちどのユーザーの署名にも当てはまらない場合は、どのユーザーが作成したメッセージか特定できないので単に破棄します。

### メッセージデータの構造が間違っていないかどうかの検証
本来乗せるべき情報が載せられていなかったりする場合は、明らかに不正なメッセージであるため、不正の証拠データとして次回のブロードキャストメッセージに乗せて送信する。

### 異なるブロードキャストメッセージを別々のユーザーに送信していないかどうかの検証
例えば、あるユーザーは下図のように他のユーザーからの3つのメッセージを受け取ります。そして、それぞれのメッセージの中にそのユーザーが直前に他のユーザーから受け取ったメッセージが入っています。つまり、メッセージを作成したユーザーが見ているゲーム世界に反映されたデータが入っていることになります。

自分を含め、全ユーザーを見比べてゲーム世界に矛盾が生じていないかを確認します。

もし矛盾があるとするならば、あるユーザーが異なる複数のメッセージを生成していることになります。

矛盾が生じている複数のメッセージを見つけた場合、不正の証拠データとしてブロードキャストメッセージに乗せて送信します。

![messagecompare.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/914937/370290d0-39b5-15a6-a003-4c08a097025e.png)


また、ブロードキャストメッセージは各ユーザーに加え、ブロックチェーン上にも書き込まれます。つまり、ブロックチェーン上に書き込まれたデータと各ユーザーが受け取ったデータとの間に矛盾が生じる可能性もあります。
そのような矛盾データを見つけた場合も上記と同じ手順でブロードキャストメッセージに不正の証拠として記録し、送信します。

### 他のユーザーから提出された不正の証拠の検証
他のユーザーから受け取ったブロードキャストメッセージの中に不正の証拠が入っていれば、その証拠データについて本当に不正なデータかどうかを確認します。もしその証拠が正しければ、該当ユーザーを不正ユーザーとしてゲームから排除します。

### 前回の検証で発見された不正ユーザーの排除
前回の検証で自身が発見し、証拠を提出した不正ユーザーをゲームから排除します。

### 矛盾がなくなるまで待機
同じユーザーによる異なるブロードキャストメッセージが複数発見された場合、そのユーザーは証拠が提出された時点でゲームから排除されますが、ゲーム内に矛盾が生じている可能性があります。そこで、ブロックチェーンに登録された該当のメッセージが到着するまで待機します。もしもブロックチェーンに登録されたメッセージと自分が受け取ったメッセージが異なっていたら、ブロックチェーンに登録されたメッセージの方を正しいメッセージとしてゲーム世界に反映し直し、矛盾を解消します。

# スマートコントラクト
ここまではユーザークライアント側での処理を見てきました。ではブロックチェーン側ではどのように処理を行うかを見ていきます。

例えばブロックチェーン上に以下のようなデータベースを想定します。ここでは簡単にユーザーの座標と向き、HPを管理します。アクションはユーザーが行った行動によって発生します。

| データベース |
|:-:|
| 参加中のユーザーデータ |
| 最新のフレーム番号 |
|  各ユーザーのゲームデータ（座標、向き、HP） |
|  アクション |
|  保留中のメッセージ |

### 実行の流れ

1. スマートコントラクトは実行時の引数として同期メッセージまたはブロードキャストメッセージを受け取ります。
2. 切断の検証
3. メッセージの検証
4. メッセージを保留メッセージとしてデータベースに登録
3. 保留メッセージのデータベースへの反映


# ブロックチェーンによる切断検証
メッセージを保留メッセージとしてデータベースに登録する際に、各フレーム番号のスタートブロックのブロック高を記録しておきます。スマートコントラクトが受け取ったあるメッセージが記録されるブロック高がスタートブロックのブロック高からNより離れている場合、データベース内にあるそのユーザーデータの欄に通信失敗フレームとしてそのメッセージのフレーム番号が記録されます。この時、切断されたユーザーとしてゲームから排除されることはありません。

# ブロックチェーンによる検証
ブロックチェーン上では、検証に関して以下の処理を行います。

- 署名の検証
- メッセージデータの構造が間違っていないかどうかの検証
- 提出された不正の証拠データの検証

不正ユーザーの排除を行うのは、証拠データが提出されそのデータが正しいと判断されたときだけです。それ以外の場合で検証失敗した場合は、単にメッセージを破棄します。不正ユーザーを排除する場合は、該当ユーザーを排除されたユーザーとしてデータベースに記録し、それ以降そのユーザーのブロードキャストメッセージを受け付けません。

# ブロックチェーンによる切断ユーザーの排除
前項の検証と同様に、切断に関しても証拠データが提出された場合のみ検証を行い、不正ユーザーの排除を行います。

切断に関する証拠データの検証において、まず証拠データが正しいものかどうかを判断します。
証拠データはスタートブロックからN+Mブロック分のブロックデータになるので、そのブロックが正しいものかどうかと、その中に排除の対象となるユーザーによるブロードキャストメッセージが含まれていないかどうかを確認します。

また、ブロックチェーン上のデータベースを確認し、証拠データ内の「不足しているメッセージのフレーム番号」が切断の対象となるユーザーのデータベース上に通信失敗フレームとして記録されているかどうかを確認します。

証拠データが正しく、通信失敗フレームの記録があれば該当ユーザーを排除されたユーザーとしてデータベースに記録し、それ以降そのユーザーのブロードキャストメッセージは受け付けません。

# メッセージのデータベースへの反映

あるフレームにおいて、メッセージが全員分集まっており、そのフレームより前のフレームの保留メッセージが存在しなければメッセージをデータベースに反映します。

例えば保留中のメッセージが下図のようになっていた場合、データベースへの反映を見送り、そのまま保留します。

この状態でフレーム番号1のブロードキャストメッセージ4が到着した場合、フレーム番号1と2のメッセージがすべてデータベースに反映されます。

![horyuu.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/914937/15388a4e-bd5d-56c0-0a80-913d10e1ea69.png)

データベースには押したボタンを元にアクションデータを書き込みます。例えばパンチアクションであれば以下のようなデータが保存されます。

| パンチアクション |
|:-:|
| アクションを起こしたユーザーID  |
| 位置  |
|  向き |
| フレーム番号 |



その後、データベースに存在するアクションを確認し、その位置と向きおよびフレーム番号からそのアクションが影響を与えるゲーム上の範囲を割り出します。
その範囲内に含まれるユーザーが存在すれば、そのユーザーにパンチなどが当たったことになり、そのユーザーのHPが減らされます。パンチアクションであれば誰かに当たった場合はデータベースから削除されることになります。

このようにしてユーザーが起こした行動がスマートコントラクト内のデータベースに反映されていきます。

HPが0になったユーザーは敗北者として記録されていき、最後の一人が残った時、そのユーザーに賞金が与えられます。



# まとめ
これまで述べてきたような方法を使えば、不正を排除しながらオフチェーンで高速に通信することができるかもしれません。ただ、完全同期で通信を行う都合上どうしてもユーザーの通信速度には依存してしまいます。完全な切断やブロック生成速度*Nよりも大きい遅延であれば排除できますが、それ以下の遅延に関しては対応できません。わざと遅延を起こす不正なユーザーが現れる可能性も排除できません。ブロック生成速度を速くすることができればある程度の遅延までは対応可能かもしれません。ブロック生成速度が遅くても、マイナーがトランザクションを受け取った時間を正確に記録できるような仕組みがあればこの問題は解決できます。

また、ボットの問題もあります。ユーザーが人間なのかロボットなのかを見分けるのは困難です。賞金などを用意してしまった場合は大量のロボットプレイヤーが現れるでしょう。特にアクションゲームなどでは人間がロボットの処理速度に追いつくのは困難です。我々の思惑とは裏腹にいかにして高性能なロボットをつくるかどうかの戦いになってしまうことでしょう。

手数料に関しても今回は考慮していませんが、ある程度考慮してより手数料がかからない方法を考える必要がありそうです。

ここまで長々と語ってきた割に、レディー・プレイヤー１の世界がまた遠のいてしまったように思われますが、賞金のない通常のゲームプレイであれば、実現できる可能性があります。遅延行為を行うプレイヤーは投票などによってキックすればいいですし、ロボットの大群が賞金目当てに押しかけてくることも無いでしょう。時間を正確に記録する特殊なブロックチェーンやロボット判定機能を組み込んだゲームなどがあればあのような世界も実現可能なのかもしれません。