こないだのBitcoin Optechのニュースレターで取り上げられていたトランザクションサイズに関するトピックについて↓、本筋とは直接関係ないけど2017年に発見された脆弱性CVE-2017-12842について触れられていたので、どういった脆弱性だったのか見てみる。
CVE-2017-12842
CVE-2017-12842はBitcoin Core 0.14.0以前のバージョンにおいて、SPVウォレットに対して実際に支払いが行われていないのに、支払いが行われたと認識させることが可能なSPVプルーフを作成できるという脆弱性。
問題となるのはBitcoinで採用されているマークルツリーの仕組み。Bitcoinではブロック内の全トランザクションのハッシュをリーフノードとした2分木を作成し、そのルートノードのハッシュをマークルルートとしてブロックヘッダーにセットしている。つまりブロックヘッダーはブロックの全トランザクションについてコミットしている。
このマークルツリーを構成する際、ツリーのリーフノードと内部ノードの区別はされていない。
どちらも32バイトのハッシュ値で、値を見ただけでは内部ノードの値なのかリーフノードの値なのか判定することはできない。
また、ブロックヘッダーにはブロックに含まれるトランザクション数にコミットしていないので、軽量ノードがブロックヘッダーだけ見ただけでは、トランザクション数が分からず、マークルツリーの高さも分からない。
SPVプルーフの仕組み
軽量クライアントであるSPVウォレットは、ブロックチェーン全体をダウンロードせず1ブロックあたり80バイトのブロックヘッダーのみをダウンロードする。このため、UTXOが使用済みかどうかの判定を自身で行うことができない。そのためSPVウォレットはフルノードに対してフィルタを設定し、自身のscriptPubkeyなどの情報をフィルタにロードすることで、フィルタに合致した場合、その関連するトランザクションがブロックに含まれていることを証明するMerkel Proofとトランザクションを送ってもらうようになっている。
Merkle Proofには、該当トランザクションがブロックに含まれていることを確認するために必要なデータが含まれている。軽量クライアントがマークルツリーを部分的に復元しマークルルートを再計算するために必要な、自身に関連するとされているトランザクションのマークルツリー上での兄弟となるとTXIDと、マークルルートまでの計算に必要な内部ノードのハッシュ値だ。これらを使って軽量クライアントはマークルルートを計算し、それがブロックヘッダーのマークルルートと一致すれば、確かにそのトランザクションは該当ブロックに含まれていることを確信する。
このあたりやフィルタの仕組みが知りたい場合は、共著のブロックチェーン・プログラミングで解説している。
脆弱性の内容と攻撃方法
このBitcoinのマークルツリーの構造と軽量クライアントの仕組みを悪用すると、軽量ノードに対してマークルツリーの内部ノードをリーフノードと認識させることことができる。(この攻撃が可能なのは、実質マイナーのみだが)具体的には以下のようなトランザクションを持つブロックを作成する。
この内、Tx3はサイズが64バイトのトランザクション。そして、Tx3の前半32バイトと後半32バイトとトランザクションIDが一致するフェイクトランザクション1,2を作成する。このうち1つのトランザクション(Fake Tx 2)は、これから騙そうとする軽量ノード宛の送金アウトプットを1つ持つトランザクションになる。
このようなブロックを作るのに成功した場合、軽量ノードに対しては、Fake Tx 2で軽量ノード宛に支払いをした証拠であるMerkel Proofを提供する。この場合Merkle Proofに含まれるのはFake Tx 1、Tx 4、Node Aの値。あとはFake Tx2を送れば、それが自分宛の送金であり、Merkle Proofから部分的にブロックのマークルツリーを再構成し、計算したルートハッシュがブロックヘッダーのマークルルートと一致すると、Fake Tx2が確かにこのブロックに入っているトランザクションだと認識する。
ただ実際にはFake Tx 1, 2はブロックに含まれてはいない。実際にブロックに入っているのはTx 3で、攻撃者はそれをFake Tx 1, 2から計算された内部ノードであると軽量ノードに錯覚させているだけ。
Tx 3のような64バイトのトランザクションを作ろうとすると以下のようなトランザクションができあがる。
データ | バイト数 |
---|---|
nVersion | 4 |
インプットの数 | 1 |
インプットのTXID | 32 |
インプットのアウトプットインデックス | 4 |
scriptSigの長さ | 1 |
scriptSig | 0 |
nSequence | 4 |
アウトプットの数 | 1 |
アウトプットの値 | 8 |
アウトプットのscriptPubkeyの長さ | 1 |
アウトプットのscriptPubkey | 4 |
nLocktime | 4 |
最初のnVersion
、インプットの数
、インプットのTXIDの先頭27バイト
までが前半32バイトになり、それ以降のデータが後半32バイトになる。このような構成のトランザクションを作ったら、その後、前半32バイトとTXIDが一致するFake Tx 1、後半32バイトとTXIDが一致するFake Tx 2を作成する。
nLocktime
やインプット値を僅かに変えながら、期待したTXIDのトランザクションを見つけるため総当りで計算する。
攻撃コスト
↑により軽量クライアントを騙すことが理論上は可能だが、そのようなトランザクションを作るためには仕組み上結構な計算コストがかかる。この攻撃にかかるコストはは130万ドルと推定されており(最適化により半分にまでに抑えられるともされている)、少なくともそれ以上の金額をSPVウォレットに対する支払いとして騙せる可能性がなければ実際の攻撃は成立しないだろう。
攻撃を防ぐための対応
上記の攻撃を完全に不可能にするため、(witnessのデータを除外して)トランザクションサイズが65バイト未満のトランザクションを無効とするコンセンサスルールの適用を求めるソフトフォーク(Consensus Cleanup)の提案もされている。
またコンセンサスルールではないが、Bitcoin Coreのトランザクションの標準ルールとして、現状82バイト未満のトランザクションのリレーやマイニングをサポートしていない。
参考
ちなみに、こういう問題もあってか、Taprootで提案されているスクリプトツリーでは、リーフノードや内部ノードのハッシュ値を計算する際に、それぞれを識別できるようタグ(TapLeaf、TapBranch、TapTweak)が付与される仕様になっている。