この記事はCTF Advent Calendar 2018の23日目の記事です！

本稿では、Ethereumスマートコントラクトを用いて、CTF（に限らず、様々なイベント）の賞金支払いをどう行うか？を検討してみます。

はじめに

Capture The Flagにおいては、その上位者に賞金が支払われる大会がしばしば開催されている。

こうしたCTFをはじめとする各種賞金付き大会において、その賞金の支払いをDAppsを用いて行う事を考える。

DAppsを用いる意義

確かに賞金が用意されていることを証明できる
主催者が賞金を支払う意志があることをアピールできる
入賞者自身が引き出しを行うので、支払いの手間がかからない

DAppsを用いた賞金付きCTF

今回は簡単化のため、優勝者のみに賞金が支払われ、問題数は1つ（正解のFLAGが1つ）の単純な大会を想定とする。また、優勝者は「FLAGを入手し、賞金支払い手続きを最も早く行った参加者」と定義する。

DAppsやブロックチェーンなど、分散基盤上で「賞金支払い」を行う場合に、大きく問題となるのが未受理トランザクションの存在である。要は、未受理のままネットワーク（mempool）を漂っているトランザクションをコピーしてより高い手数料を付与すれば、最初にトランザクションを投入した参加者の賞金受け取り権利を横取りできてしまう、という話である。

優勝者が必ず、もしくは極めて高い確率で賞金を手にすることができるDAppsを考えてみよう。

従来手法

[1]: Bitcoinによる新しいCapture The Flag（CTF）

この手法では、FLAG検証に参加者固有の値を用いることで先述の問題を解決している。ブロックチェーン上に各参加者ごとに固有のFLAGハッシュを予め記憶しておくことで、検証を行う。

チーム $T_i$ はFLAG文字列 $F$ を入手すると、 $h_i=H(F||i)$ を含むトランザクションを提出する。 $H$ は適当なハッシュ関数である。このトランザクションに対し、予め記録されている $ans_i=H(h_i)$ と比較することで正しいFLAGを持っているか検証できる。仮にチーム $T_j$ がこのトランザクションをコピーしても、チーム $T_j$ に対する正解 $ans_j$ は $ans_i$ と異なるため、正解とみなされない。また、 $h_i$ を入手してもハッシュの原像計算困難性により、 $F$ は入手できない。

Ethereumを用いて実装した例もある。

しかし、[1]では予めCTFイベントへの参加者が確定している必要があり、開始時刻以降は参加者を追加できない。開催中にイベントの存在を知ったユーザが新たに参加できず、ユーザビリティを欠いている。

[2]: ERC20トークンを用いた宝探しゲーム(真)の提案

この手法では、テーマとして「宝探し」を取り扱っているが、秘密の文字列を何らかの手段によって入手した参加者に報奨を与えるという点で、お宝をFLAGに、ERC20トークンを賞金と読み替えれば、CTFにおける賞金支払いに応用可能である。

基本的なアイデアは[1]とほぼ同等で、各参加者ごとに固有のFLAGハッシュがスマートコントラクト上に記録されている。

[1]と異なるの　は、後から参加者の追加を可能としている点である。 [1]がBitcoinのscriptPubKeyで記述されているのに対して、[2]ではEthereumスマートコントラクト上で実装しているため、より柔軟なDAppsが記述できている。

しかしながら、[2]では参加者の追加をするために主催者が手数料を支払う必要がある。一度デプロイが完了した後にも、コントラクトの面倒を見続ける必要があるのは欠点であると言えよう。

加えて、DoS攻撃の余地がある。 EthereumのEOAアドレスは無コストで生成可能であるので、何度も参加要求を送り続けければ、主催者のEthereumが枯渇してしまう。これを防ぐには、何らかのオフチェーン要素とアドレスを紐付けて個人を特定する、CTFへの参加に手数料を徴収する、などが考えられる。しかし、これらは主催者側の負担が大きい。到底De-centralized Appsとは呼べるものではない！

さらに、[2]では主催者がこっそり賞金を自分の懐に収める可能性を排除できない。 [1]では、予め参加者を確定させておくことでこの問題をうまく回避している。

提案手法

提案手法では、後から参加者が追加可能であり、その際に手数料を必要としないことを目標とする。また、DAppsプラットフォームとしては、Ethereumスマートコントラクトを想定している。

[N案]: コミットメントによる引き出し

本手法では、予めFLAGハッシュをコントラクト上に乗せることなく、検証時には参加者ごとに異なるFLAGハッシュを用いて検証することを目指す。これを可能とするのがコミットメント方式である。コミットメントについては、Wikipediaの解説やブロックチェーンを利用した公平なガチャの提案が詳しい。

コントラクト上には、FLAG文字列 $F$ のハッシュ $F'=H(F)$ を予め記録されている。 $H$ は適当なハッシュ関数である。まず、commitとrevealの2つの操作を定義する。

commitは、言わば賞金を引き出す権利の予約である。参加者 $T_i$ は、FLAG文字列 $F$ を入手すると、自身のアドレス $A_i$ を用いてコミット $C_i=H(F||A_i)$ を送信する。コミット $C_i$ は、コントラクト上に格納される。また、 $C_i$ は従来手法で予めコントラクト上に格納しておくものと等しい。この時点では、トランザクションを観察しても $F$ は復元困難である。これがコミットメント方式の秘匿性である。

revealは、予約した権利が正当であることを証明し、それを行使して賞金を引き出す操作である。参加者 $T_i$ は、FLAG文字列 $F$ を単に公開する。コントラクトは、 $H(F)$ を計算し、予め記録されている $F'$ と比較して、FLAG文字列が正しいかを確認した後、 $H(F||A_i)$ を計算し、commit時に記録された $C_i$ と比較を行うことで、参加者はcommitの時点でこのFLAGを本当に所有していたのかを確認する。以上で、commit時点で正しいことFLAGを所有していたことが確認されれば、直ちに賞金を支払う。 commit時に提出したFLAGは、reveal時に変更できない。これがコミットメント方式の拘束性である。

コミットメント方式による賞金支払いでは、revealした瞬間にFLAG文字列が全員に対して明らかになる点に注意が必要である。そのため、検証を2段階に分けたとしても、誰かがrevealした瞬間に高手数料でcommitし、すぐにrevealすれば逆転可能性がある。

この手法のキモは、commitから一定時間（ブロック高）が経過しないとrevealできないような制約を設けることにある。これによって、revealトランザクションを投入した瞬間から一定時間内は、攻撃者は絶対に引き出しができない。したがって、この一定時間内にrevealトランザクションが承認されれば良いため、極めて高い確率で最も先にcommitした参加者に賞金が支払われる。一定時間の遅延は、言わば攻撃者の賞金引き出し操作を遅延させるために存在するものと言える。

Solidityによる実装例は以下。

pragma solidity ^0.5.0;

contract Prize {
	event Commit(address sender, uint revealable);

	bytes32 private flagHash;

	mapping(address => bytes32) private commits;
	mapping(address => uint) private revealable;

	constructor(bytes32 _flagHash) public payable {
		flagHash = _flagHash;
	}

	function commit(bytes32 commitment) external {
		commits[msg.sender] = commitment;
		emit Commit(msg.sender, revealable[msg.sender] = block.number + 128);
	}
	function reveal(bytes32 flag) external {
		require(calcFlagHash(flag) == flagHash);
		require(calcCommitment(flag, msg.sender) == commits[msg.sender]);
		require(block.number >= revealable[msg.sender]);
		selfdestruct(msg.sender);
	}

	function calcFlagHash(bytes32 flag) public pure returns(bytes32) {
		return keccak256(abi.encodePacked(flag));
	}
	function calcCommitment(bytes32 flag, address sender) public pure returns(bytes32) {
		return keccak256(abi.encodePacked(flag, sender));
	}
}

[A案]: コミットメントによる権利移転

[N案]では、要件を満たす賞金支払いDAppsを定義したが、この方式には1点課題が残る。それは、一定時間が経過しなくてもrevealできてしまう点である。

この場合、正しく実装されたコントラクトでは、支払いは行われず、FLAGが想定より早く公開されてしまう。一定時間が経過する前にrevealした参加者は、我々が苦心して用意した権利保護期間を自ら捨て去ってしまったことになるのだ！

[N案]を拡張し、こうした誤操作が起こりえない、言わばフールプルーフ的な構造を取り入れたのが[A案]である。

commitとrevealの2つに加えて、新たにwithdraw操作を定義する。

commitでは、[N案]の $C_i$ に加えて、commitした時刻（ブロック高）を記録しておく。

revealでは、[N案]と同様の検証を行った後に、権利の移転を行う。 [A案]では、コントラクト上で「現在の引き出し権利者」（優勝者）を記憶している。権利の移転とは、現在の権利者がcommitした時刻よりも、早い時刻にcommitした参加者がrevealした際に、権利を移動する操作である。

そしてwithdrawは、引き出し権利を行使して賞金を引き出すものである。この権利行使を遅延させるのが[A案]である。遅延は、「commit時から一定時間後」でもいいし「権利取得時から一定時間後」でも良い。 commit時から一定時間後としたほうが、参加者の待ち時間は短くなり、ユーザビリティが向上するだろう。

これによって、commit後に即時revealしても損をすることがない。 revealトランザクションを見てすぐさま権利を横取りしたとしても、withdrawの遅延によってすぐに引き出せないし、その間に正当権利者がrevealすれば良い。（commitが最も早いものが最終的な権利を得る。）

Solidityによる実装例は以下。

pragma solidity ^0.5.0;

contract Prize {
	event Commit(address sender, uint withdrawable);
	event Reveal(address sender, uint withdrawable);

	bytes32 private flagHash;
	address payable private winner;

	mapping(address => bytes32) private commits;
	mapping(address => uint) private withdrawable;

	constructor(bytes32 _flagHash) public payable {
		flagHash = _flagHash;
	}

	function commit(bytes32 commitment) external {
		commits[msg.sender] = commitment;
		emit Commit(msg.sender, withdrawable[msg.sender] = block.number + 128);
	}
	function reveal(bytes32 flag) external {
		require(calcFlagHash(flag) == flagHash);
		require(calcCommitment(flag, msg.sender) == commits[msg.sender]);
		require(winner == 0 || withdrawable[msg.sender] < withdrawable[winner]);
		emit Reveal(winner = msg.sender, withdrawable[msg.sender]);
	}
	function withdraw() external {
		require(msg.sender == winner);
		require(block.number >= withdrawable[msg.sender]);
		selfdestruct(msg.sender);
	}

	function calcFlagHash(bytes32 flag) public pure returns(bytes32) {
		return keccak256(abi.encodePacked(flag));
	}
	function calcCommitment(bytes32 flag, address sender) public pure returns(bytes32) {
		return keccak256(abi.encodePacked(flag, sender));
	}
}

提案手法の課題

主催者による賞金回収

[2]の問題として上げた以下の点は、解決できていない。

主催者がこっそり賞金を自分の懐に収める可能性を排除できない。

しかし、後から参加者の追加を許す場合では、この可能性を排除することは極めて難しい。この問題についてはとりあえずは目をつむって、主催者は信頼に足る人間である、ということにしておこう……！

暗号通貨に価値があることを前提としている

まぁいいじゃん。アゼルバイジャン。

おわりに

コミットメントの持つ秘匿性・束縛性を活用し、後から参加者が追加可能であり、その際に手数料を必要としない賞金支払いコントラクトを提案した。

謝辞

本稿は、@42_0N氏との長時間に渡る議論を経て書き上げたものです。ありがとナス！！！！！！！！

ところで、最近公開したミニCTF:NaruseJunCTFはプレイして頂けましたか？なんと、全問正解者には賞金があります！（2018/12/23 現在まだ賞金は残ってます）賞金支払いには[N案]コントラクトを用いていますヨ。DAppsによる賞金受け取りを是非体験してみてくださいネ。

6715.jp

DAppsによる賞金付きCTF