2018.12.11

Ethereum上の公平なガチャ（抽選）に対する攻撃

吉村優

この記事は RECRUIT MARKETING PARTNERS Advent Calendar 2018 の投稿記事です。

2018年12月14日: @closhiroutoさんの指摘を受けて攻撃が成功するケースについて追記しました。

はじめに

1年ほど前にブロックチェーンを利用した公平なガチャの中で、江原さんらによるEthereumを利用した公平なガチャ（抽選）について解説しました。また、このガチャを参考にして@lotzさんにEthereum（Solidity）で実装をしていただいたものが公開されています。江原さんはさらにSCIS2018にて有限回の試行で任意の景品を獲得できる抽選をブロックチェーンで構成できることを示しました。僕はこれらの成果から古典コンピュータ¹⁾量子コンピュータと対比して、チューリング完全な計算機をこのように呼びます。による最良の公平なガチャはブロックチェーンを利用したものであると確信していました。ところがCODEBLUE 2018において、Jonghyuk SongさんはEthereumで実装された公平なガチャに対して攻撃が可能であることを示し、ブロックチェーンのよく知られた実装の1つであるEthereumにおいては乱数生成が脆弱になる可能性があることを指摘しました。

この記事ではまずブロックチェーンの実装であるEthereumについて軽く説明し、そのうえで江原さんらの提案を解説します。そして最後にJonghyuk Songさんが提案した攻撃手法について解説し彼がCODEBLUE 2018で述べた対策について言及します。この記事について何か分からないことや間違い、改善すべき点がある場合はお気軽にコメントなどでお知らせください。

公平なガチャ

ソーシャルゲームなどに実装されたガチャシステムといった多くの抽選は運営のサーバーで確率を計算しています。運営が景品の出現確率を公表していることが多いですが、実装ミスや意図的な操作によって景品の出現率を公表とは異なる値にすることもできます。公平なガチャの目標は暗号技術などを利用することによって、ガチャシステムにおける景品の出現確率をユーザーが実装に基づいて確かめられるようなシステムを開発し、ガチャシステムの健全さの向上に貢献することです。暗号技術の1つであるコミットメントを利用する方法もありますが、これは僕のブロックチェーンを利用した公平なガチャにおいて問題が指摘されています。

Ethereum

EthereumはBitcoinのような暗号通貨とは異なり、暗号通貨の取引だけではなくマイナーに任意のチューリング完全なプログラムを実行してもらうことができます。BitcoinにもScriptというスタックマシーンベースのプログラムを入力できますが、BitcoinのScriptは非チューリング完全であったり、Bitcoinのリファレンス実装は送金の命令以外を受理しないといった大きな制約があります。一方でEthereum上ではチューリング完全なプログラムをマイナーに実行させるコントラクトという機能があり、さらにその結果をブロックチェーンに記録することができます。そのときプログラム全体の量と1命令あたりの料金などから最終的なコントラクトの実行料金がマイナーに提供されるという仕組みとなっています。

ブロックチェーンを利用した公平なガチャシステム

ブロックチェーンによる公平なガチャは次のように実装します。まず、ガチャの運営アリスとアリスのガチャに参加するボブがいるものとして、ボブのアドレスを\(\mathcal{B}\)とする。また関数\(H\)を適切なハッシュ関数であるとし、また記号\(\mid\mid\)はビットの結合として次のようにします。

ボブは乱数\(r_B\)を生成する
ボブはマイナーに次のような命令を持つコントラクト\(C_1\)を送信する。ただしこのコントラクトには乱数\(r_B\)が含まれている
1. マイナーはコントラクト\(C_1\)を実行するごとに一意な番号\(n\)を生成する
2. マイナーは組\((n, r_B)\)をブロックチェーンに書き込む
アリスはブロックチェーンから\(n\)を読み取り、\(n\)に対応する乱数\(r_A\)を生成する。
アリスはマイナーに次のような命令持つコントラクト\(C_2\)を送信する。ただしこのコントラクト\(C_2\)には乱数\(r_A\)が含まれている
1. このときのブロックチェーンの長さを\(i\)として、組\((r_A, i)\)をブロックチェーンに書き込む
\(i + 1\)ブロックのハッシュ値を\(h\)として、アリスは\(\alpha := H\left(r_A \mid\mid r_B \mid\mid n \mid\mid \mathcal{B} \mid\mid h\right)\)を計算し、それに対応する景品をボブに与える
- ただし、このときの値と景品の対応をボブは事前に知っているものとする
ボブは\(\alpha = H\left(r_A \mid\mid r_B \mid\mid n \mid\mid \mathcal{B} \mid\mid h\right)\)を検証する

この方法はどうして安全なのかについて簡単に解説します。それは（5）においてブロックのハッシュ値\(h\)を利用して景品を計算しているからです。Ethereumに限らずブロックチェーンとは、ブロックをブロックチェーンに投入するために手間のかかる計算を要求します。たとえばEthereumではブロックの中のトランザクションといったデータとそれに適当な値（ナンス）を混ぜたハッシュ値が特定の条件を満す必要があります。マイナーは報酬を得るために、ナンスを変えつつ何度もブロックのデータをハッシュ関数へ投入して条件を満すかどうかを検証し、最終的に欲しいハッシュ値\(h\)を得ます。このハッシュ値\(h\)をアリスやボブが予測することは難しいと考えられるので、この方法が安全であると考えられています。

これの実装を作ってくださった@lotzさんの記事²⁾記事は参考文献にあります。から具体的なコードの一部を引用すると下記のようになります。

function get() public {
  Capsule storage capsule = gachaMachine[msg.sender];
  require(capsule.count  != 0);
  require(capsule.height != 0);
  require(block.number >= capsule.height);
  bytes memory concatted = concat(
    bytes32(capsule.ra),
    bytes32(capsule.rb),
    bytes32(capsule.count),
    bytes32(msg.sender),
    block.blockhash(capsule.height)
  );
  uint alpha = uint(sha256(concatted));
  goods[msg.sender].push(alpha);
  delete gachaMachine[msg.sender];
}

さきほど言及したハッシュ値\(h\)はblock.blockhash(capsule.height)として取得されています。狙った景品が欲しかったとしてもハッシュ値\(h\)を狙った値にできないためこのガチャは一見するとよいと考えられていました。

インターナルトランザクションによる攻撃

Ethereumにはインターナルトランザクション（internal transaction）という機能があります。これはコントラクト（Ethereum上のプログラム）から他のコントラクトを呼び出す方法です。このときユーザーがコントラクトを起動するトランザクションと、そのコントラクトが発行したインターナルトランザクションは同じブロックに入ります。これにより次のような攻撃が可能となります。

ボブは次のような攻撃用のコントラクト\(C_3\)をデプロイする
1. 現在の\(i\)ブロックを取得し、それのハッシュ値\(h\)を計算する
2. \(\alpha := H\left(r_A \mid\mid r_B \mid\mid n \mid\mid \mathcal{B} \mid\mid h\right)\)がボブの狙った値の場合、インターナルトランザクションを利用してアリスのコントラクト\(C_1\)を起動する。そうでない場合revertによって直ちに終了する
ボブは（1）で作成したコントラクト\(C_3\)が成功するまで、起動トランザクションを送信し続ける

このようにすることで、ボブはアリスのコントラクトを狙った時だけ起動することができます。もちろん、ボブは（1）のコントラクトがrevertせずに成功するまで攻撃用のコントラクト\(C_3\)を何度か実行しなければなりません。ただ、もしアリスが用意している景品の価値が（1）を何度も実行するたびにマイナーへ支払う代金より少ない場合、ボブはこの攻撃を行うと思われます。

失敗とその原因

ところが、実はこの攻撃は成功ないということが指摘されました。

C3 は α := H(ra||rb||n||B||h) を計算して結果が所望の値なら C1 を実行する、そうでなければ revert という理解をしました。h は運営による C2 の実行 block の次の block の hash ならば、C1 の実行前に h を得ることができず α を計算できない気がしたのですが、何か見落としていますでしょうか？

— くろしろ (@closhirouto) 2018年12月14日

これはプロトコルの（5）において、ハッシュ値を取るブロックが現在のブロックではなく、現在のブロックの次のブロックであるからです。このためインターナルトランザクションを利用したとしても、次のブロックの情報は得られないのでこの攻撃は使えません。

ただ、@lotzさんは記事で「もっとシンプルなガチャ」として次のようなプロトコルを与えています。

ユーザーは次のようなコントラクトを実行する

コントラクトでは一意な番号\(n\)が生成される

この時のブロックチェーンの高さを\(i\)とする

組\((n, i)\)がブロックチェーンに書き込まれる

\(i\)番目のブロックのハッシュ値を\(h\)として、運営は\(\alpha := H(n \mid\mid h)\)を計算し、それに対応する景品をユーザーに与える。ただし、このときの値と景品の対応をユーザーは事前に知っているものとする

ユーザーは\(\alpha := H(n \mid\mid h)\)を検証する

このような現在のブロックのハッシュ値を利用する場合はこの攻撃が可能ですが、一方で現在のブロックよりも将来のブロックのハッシュ値を利用する場合は少なくともこのままでは攻撃にならないのではないかと思われます。

攻撃の対策

この攻撃の対策としてCODEBLUE 2018でJonghyuk Songさんは次の2つの方法を利用するとよいかもしれないと提案していましたが、彼自身もっとよい方法があるのではないかと述べていて、どちらも完全によいと言うわけではないようです。

ブロックチェーン上でコミットメントを利用する
外部の乱数生成サービスを利用する

（2）については僕が具体的にどのようなサービスなのか分からなかったため詳細を述べることができませんが、（1）について詳しく僕の考えを説明します。僕はJonghyuk Songさんと同じく、少なくとも（1）は問題があると考えていますが、CODEBLUE 2018のトークにおいて彼はどうしてこれらに問題があるのかについては述べていませんでした。従ってここからは僕の主張ということでご了承ください。

実は僕自身がもともとブロックチェーンではなくコミットメントで公平な抽選を行う方法を考えていました。ところが次のような微妙に公平ではない部分が残ってしまい、ブロックチェーンの方がよいのではないかと考えるようになりました。

アリス（運営）が乱数を生成した後で、その乱数はボブ（参加者）の捏造だと主張する
ボブ（参加者）が都合のよい値を生成しその後で、それをアリス（運営）が生成した乱数だと主張する

このような攻撃を回避するために、署名を導入するならSSL/TLSのような証明書が必要になります。もちろんSSL/TLSの証明書を流用してもよいと思いますが、証明書発行機関のような信頼できる第三者を仮定するなら、その者が乱数生成を行えばよいという指摘もあります。実は他にもいくつかコミットメントを行う困難さがありますが、詳しくは次のページをご覧ください。

また、インターナルトランザクションとrevertによってこの攻撃は可能になっているため、これらの機能を持たないEthereumとは異なるブロックチェーン実装を利用するという方法もあります。

そして江原さんらが考えていたような「1つ先のブロック」のハッシュ値を利用するというのも良いように思います。Jonghyuk Songさんのブログ記事も見ましたが、彼の発見した脆弱性も現在のブロックの情報を利用していましたので、将来のブロックに依存させることがよいという可能性はあります。

まとめ

ブロックチェーンを利用した抽選は恐らくEthereumではないブロックチェーン実装でも可能であると思います。ところが最も有名なブロックチェーン実装による乱数生成への攻撃が指摘されたことは、公平なガチャを考えている僕としては興味深い出来事でした。これを参考に今後はたとえインターナルトランザクションやrevertが可能であったとしても公平性が崩れない公平な抽選を考えていきたいと思います。また、@closhiroutoさんの指摘で明らかになったように、将来のブロックのハッシュ値を利用することで本当に安全なのかが今後考えるべきところなのではないかと思います。

参考文献

脚注[+]

脚注
↑1	量子コンピュータと対比して、チューリング完全な計算機をこのように呼びます。
↑2	記事は参考文献にあります。

Recruit Tech Blog

タグから見つける