最近Bitcoin Coreにマージされた変異ブロックに対する早期検証ロジック↓
変異ブロックとは？
変異ブロック（Muted Block）とは、新しく生成された有効なブロックの一部を変更した無効なブロックではあるけど、ハッシュ値が元のブロックと同じブロック。こういった変異ブロックを作成する方法は、いくつかある。
１．マークルツリーの曖昧さを利用する
Bitcoinでブロックを作成する際、ブロック内の全トランザクションのハッシュをリーフノードとしたマークルツリーを構成し、そのルートハッシュをブロックヘッダーにセットするようになっている。
ただ、このトランザクションのコミット方法とルートハッシュの計算方法には、同じマークルルートを導出可能なハッシュのリストを簡単に構築できるという欠陥がある。トランザクションの数が奇数個の場合、不足する最後の要素はその前の要素のハッシュをコピーして偶数にしてツリーの親ノードを計算するようになっている。
例えば、リーフノードの値がa, b, cの3つのリストにコミットするマークルツリーのルートハッシュと、リーフノードがa, b, c, cの4つのリストにコミットするマークルツリーのルートハッシュは同じ値になる。
つまり、トランザクションが奇数個のブロックについて、最後のトランザクションをコピーしてそれを追加したブロックを作れば無効な変異ブロックを作成することができる。最後に追加したトランザクションは１つ前のトランザクションと同じであるため（同じUTXOを二重使用しようとするトランザクションなので）コンセンサスルール上無効なトランザクションになる。
ちなみに、こうった曖昧さの問題もあり、Taprootのスクリプトツリーを構成する際は、タグ付きのハッシュを利用するようになっている。
２．トランザクションのwitnessデータを変更する
Bitcoinのブロックヘッダーは上記のようにトランザクションのデータから作成される値にコミットするようになっているけど、この時segwit系のトランザクションのwitnessデータは、このハッシュには含まれていない。ただ、ブロックヘッダーにはコミットされないけど、代わりにブロック内のコインベーストランザクション内にコミットされる。witnessを含むトランザクションのハッシュについて、上記と同様にマークルツリーを構成し、そのルートハッシュをコインベーストランザクションのアウトプットにセットする必要がある。
ただ、ブロックヘッダーにはコミットされないので、ブロック内のsegwitトランザクションのwitnessデータを変更し（無効なものにし）ても、ブロックヘッダーのハッシュ値は変わらないため、これを利用して無効な変異ブロックを作成することができる。
３．2つのトランザクションのハッシュ値と合致する無効なトランザクションを作成する
方法は1と似ているけど少しだけ複雑。２つの有効なトランザクションのハッシュ（それぞれ32バイト）を連結した値が（無効だけど）トランザクションとしてパースできるような値になるような、２つのトランザクションを生成する。
たとえば、２つのトランザクションTx1とTx2を持つブロックを考える。この場合のマークルルートは、以下のようになる。
graph BT;
A[Tx1] --DSHA256--> B["H(Tx1)"]
C[Tx2] --DSHA256--> D["H(Tx2)"]
B --> E["Root Hash<br>DSHA256(H(Tx1) || H(Tx2))"]
D --> E
ここで、H(Tx1) || H(Tx2))の値がトランザクションとしてパース可能なデータである場合（Tx3 = H(Tx1) || H(Tx2))）、Tx3のみを含むブロックのマークルルートは、
graph BT;
A[Tx3] --DSHA256--> B["Root Hash"]
となり、この2つのマークルルートの値は一致し、無効な変異ブロックを作成することができる。
Tx3はTx1とTx2のハッシュの連結値で構成されるため、64バイトのトランザクション。このようなトランザクションを作成する方法については、以下のペーパーで解説されてる↓
| フィールド | サイズ |
|---|---|
| version | 4 byte |
| インプットのリスト | 可変長 |
| アウトプットのリスト | 可変長 |
| locktime | 4 byte |
で構成されている。インプットとアウトプットのリストの先頭には、その個数がCompactSizeエンコードされている。各インプットは、
| フィールド | サイズ |
|---|---|
| OutPoint | 36 byte |
| scriptSig | 可変長 |
| sequence | 4 byte |
各アウトプットは、
| フィールド | サイズ |
|---|---|
| value | 8 byte |
| scriptPubkey | 可変長 |
という構成になる。scriptSigとscriptPubkeyは、その先頭にCompactSizeエンコードされたそれぞれのサイズが付与される。
64バイトのパース可能なトランザクションになるためには、
- インプットとアウトプットの数は1つだけ。つまり、それぞれのリストのサイズは1 byteの0x01でエンコードされなければならない。
- scriptSigとscriptPubkeyの合計サイズが4 byteでなければならない。
という制約がある。scirptSigが空でscriptPubkeyを4 byteとした場合、トランザクションのデータは以下のように制約される（xは任意の値でOK）↓
xxxxxxxx01xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx00xxxxxxxx01xxxxxxxxxxxxxxxx04xxxxxxxxxxxxxxxx
Tx1のハッシュが上記の前半32 byte中1 byte衝突し、Tx2のハッシュが後半32 byte中3 byteと衝突するような2つのトランザクションを用意できればいい。このような衝突は、少ない計算量の総当りで見つけることができる。
一方、無効ではない有効なトランザクションを見つけるのは、制約されるデータ長が増加するため計算上実行不可能な作業になる。
CVE-2012-2459
上記のような無効な変異ブロックは当然ながらコンセンサスルールに合致しないのでリジェクトされる。ただ、昔のBitcoin Coreの実装では、このリジェクトしたブロックのハンドリング方法に問題があった（2012年に開示されたCVE-2012-2459）。
新しく生成されたブロックについて、攻撃者が上記のような変異ブロックを生成し、変異ブロックの方を先に受信したノードは、そのブロックを無効なブロックとしてマーキングする。そのノードはそのブロックハッシュを無効なものとしてマーキングしているため、その後再起動するまで、同じブロックハッシュを持つ有効なブロックを再度受け入れなくなり、最長チェーンから分離されてしまう。つまり、エクリプス攻撃の一種が実行されてしまう。
この脆弱性は、変異ブロックについてはそれを拒否しても無効なブロックハッシュとしてキャッシュしないようにすることで修正された。
ただその後、2017年にBitcoin Core v0.13.0に加えられた最適化により、このキャッシュの問題が再度発生し、v0.14.0で修正されるということもあった。
検証ロジック
今回のPR#29412では、BLOCKメッセージでブロックを受信した際、そのブロックを処理する前に、それが変異ブロックかどうかを先に検証するロジックを追加している。
具体的には、validatoin.cppにブロックが変異ブロックかどうかを検証するIsBlockMutated関数が追加され、新しく受信したブロックを処理する前に変異ブロックかどうかチェックし、変異ブロックだった場合はそれを送信したピアのスコアを下げ、その後の処理を行わない。
IsBlockMutated関数は、ブロックに対して以下の検証が行う。
- ブロック内のトランザクションリストからマークルルートを計算し、ブロックヘッダーのマークルルートと一致するか検証
- 上記マークルルートの計算中に、ツリー内の兄弟ノードのハッシュ値が同じ値のものがないかチェック（作成方法1のチェック）
- ブロック内の先頭のトランザクション（コインベーストランザクション）のprevoutが空かチェックする。
- 空でない場合、ブロック内のトランザクションでサイズが64バイトのものがないかチェックする（作成方法3のチェック）
- コインベーストランザクションのインプットのwitnessを検証。要素数は1つのみで、そのサイズは32バイトでなければならない。
- ブロック内のトランザクションのリストからwitnessマークルルートを計算し、コインベーストランザクションのアウトプット内にあるwitness commitmentと一致するか検証（作成方法2のチェック）
- Segwitアクティベート前のブロックのトランザクションについて、witnessデータが含まれていないこと。
