Bitcoinの取引の可撓性（transaction malleability）とMt.Gox

Bitcoinに関する論文「[Bitcoin Transaction Malleability and MtGox](http://arxiv.org/abs/1403.6676)」（Christian Decker, Roger Wattenhofer, 2014）の纏めです。

# 関連記事

[Bitcoinの取引の可撓性（transaction malleability）について](http://qiita.com/pizyumi/items/9d5a553fb95fb69d1769)

# 1

* 可撓性攻撃（malleability attack）
	* 支払い人が、自身がBitcoinネットワークに新たに放流した取引がネットワークによって承認され、執行されたかどうかを、自身がネットワークに放流した取引そのものがブロック鎖に格納されているか（自身がネットワークに放流した取引の要約値（hash value）と同一の要約値を有する取引がブロック鎖に格納されているか）のみにより判断している場合に受け取り人が仕掛けることのできる可能性のある取引の可撓性（transaction malleability）を悪用した攻撃。
	* 手順
		* 受け取り人は支払い人に対してBTCの支払いを要求し、要求に応じて支払い人から受け取り人への新しい取引が発生したことをできる限り早期に検出するためにBitcoinネットワークを監視する。
		* 支払い人は受け取り人の要求が正当である場合、受け取り人が要求する額面のBTCを支払い人から受け取り人に移動する新しい有効な取引を作成し、ネットワークに放流する。
		* 受け取り人は支払い人から受け取り人への新しい取引を検出し、取引の可撓性を利用して元々の取引から署名を有効なままに保ちつつ要約値を変更した撓められた新しい有効な取引（衝突（condlict）と言う）を作成し、ネットワークに放流する。
		* ネットワークは元々の取引か撓められた取引かの何れかの取引を承認する。元々の取引の方が承認された場合には、攻撃は失敗である。撓められた取引の方が承認された場合には、受け取り人は支払い人に対して（実際には支払いは既に執行されているのだが）支払いが未だ実行されていない（か、あるいは、支払いの実行に不備があるのではないか）と主張を申し立て、支払い人を欺罔する。
		* 支払い人はブロック鎖に元々の取引が格納されているか検証するが、思いも寄らず、格納されていないことを確認する。支払い人は支払いの実行に何らかの不備があったと判断し、受け取り人が要求する額面のBTCを支払い人から受け取り人に移動する新しい有効な取引を作成し、ネットワークに放流する。
		* ネットワークは新しい取引を承認する。
	* 結果
		* 受け取り人は支払いを2回受け取った。
	* 対策
		* 支払いの成否を、自身がネットワークに放流した取引そのものがブロック鎖に格納されたかによって判断するのではなく、取引に使用した未使用の取引出力が使用済みになったかどうかによって判断する。
			* 仮に支払い人が懈怠していたとしても、百発百中確実に攻撃が成功する訳ではない。ネットワークの状態や攻撃方法の細部の差異によって成功率は変動する（攻撃の成否はネットワークが元々の取引か撓められた取引かの何れかの取引を承認するかに依存する）。
	* 嘗て存在したBitcoin取引所の1つであり、嘗ては世界最大規模のBitcoin取引所でもあったMt.Goxは可撓性攻撃による被害を受けており、85万BTCを喪失したと発表している。

# 2

* Bitcoinネットワークで衝突が検出された場合、可撓性攻撃が実行された可能性がある。
	* 最終的なブロック鎖には元々の取引か撓められた取引かの何れかが有効なものとして格納されるので、ブロック鎖の内容を検査するだけでは可撓性攻撃が実行されたかどうかを検証することはできない。
	* ネットワークを常に監視していなければならない。
		* なお、衝突を検出する確率は監視対象のノード数の増加に伴い急速に1に近付く（Bamert et al.[^1]）。そのため、十分な割合のノードを監視していれば、遺漏なく衝突を検出できると考えて良い。
	* 衝突を検出する方法
		* 衝突を作成する際には取引の中で署名対象となっている部分は変更することができない。
		* すなわち、取引の中で署名対象となっている部分は元々の取引と衝突とで同一である。
		* すなわち、署名対象となっている部分が同一の取引が複数あれば、それらは元々の取引か衝突かの何れかである。
		* そして、取引の中で署名対象となっている部分とは、署名スクリプト（signature script）以外の部分である。
		* したがって、取引から署名スクリプトを除いたものが同一である複数の取引は元々の取引か衝突かの何れかである。
			* このような複数の取引を衝突組（conflict set）と言う。
* 衝突を検出しても、可撓性攻撃が成功したかどうかまでは分からない。
	* 支払い人が攻撃に対して脆弱であるかどうかに依存する。
	* 同一口座へ同一額面のBTCを移動する新しい取引を検出したとしても、可撓性攻撃とは全く無縁の別の独立した取引であるかもしれない。
* とは言え、撓められた取引と考えられる取引がブロック鎖に格納された場合には、可撓性攻撃が成功した可能性はどの程度かは分からないがある程度はあるはず。
	* そこで、撓められた取引と考えられる取引がブロック鎖に格納された数を可撓性攻撃が成功した数の上界と考えることにしよう。

# 3

* 調査期間中に見付かった衝突組は35202個。
* ただし、取引入力が、存在しないか使用済みの取引出力を参照していたり、署名が無効であったりして、衝突組の取引がそもそも無効である場合もあるので、それらを除外すると29139個。
* 29139個の内、28595個は使用しているデータ積み込み命令が異なっていた。
	* 可撓性攻撃によるものであった蓋然性が高い。
	* 標準データ積み込み（normal data push）の代わりに`OP_PUSHDATA2`を使用していた。署名スクリプトでは標準データ積み込みを使用するのが通例であるため、標準データ積み込みを使用しているものの方が元々の取引で`OP_PUSHDATA2`を使用しているものの方が撓められた取引であると考えられる。
* 残りは署名が完全に異なっていた。
	* 署名の表現方法が異なっていたり、元々の署名から作成することのできる署名であったりしたのではなく、秘密鍵を知っている所有者しか作成することのできないものであった。
	* どのような目的であるか分明でないが、あるいは、ただ単に支払い人が利用しているシステムの不具合によるものであっただけかもしれないが、同一の取引に複数回署名して、署名のみ異なる同一の取引をネットワークに放流した結果であると思われる。秘密鍵を知っている所有者しか完全に異なる署名を作成することはできないので、可撓性攻撃には当て嵌まらない。
* 28595個の内、可撓性攻撃が成功した可能性があるのは5670個。総額は約64564BTC。
	* 可撓性攻撃が成功した数の上界。
	* 個数割合で19.46%。金額割合で21.36%。

# 4

* 可撓性攻撃の数はMt.Goxが可撓性攻撃を受けていた旨の報道発表を公開してから急増している（更に報道発表後暫く経過してから報道発表前と同水準まで急減している）。
* Mt.Goxが報道発表を公開するまで可撓性攻撃は殆ど実行されていなかった。
* 仮にMt.Goxが報道発表を公開し、BTCの引き出しを停止するまでの全ての可撓性攻撃がMt.Goxに対するものであったとしても、それによってMt.Goxが喪失したBTCは極僅かである。
* したがって、**Mt.Goxの報道発表は虚偽である**。

[^1]: Tobias Bamert, Christian Decker, Lennart Elsen, Samuel Welten, and Roger Wattenhofer.  Have a snack, pay with bitcoin.  In *IEEE Internation Conference on Peer-to-Peer Computing (P2P), Trento, Italy*, 2013