Bitcoinのブロックヘッダにはブロックに入っているトランザクションのリストにコミットするため、各トランザクションのTXIDをリーフノードにしたマークルツリーを構築し、そのマークルルートの値が入れられるようになっている。ブロックにどれだけたくさんのトランザクションが含まれていても、それらから計算されるマークルルートは32バイトの固定値で、その固定値が全てのデータセットのコミットメントになる、とても空間効率の良いデータ構造で、ブロックヘッダのマークルルート以外にも様々な使い方が提案されている。
このマークルツリーの構造の改良について、Fast Merkle Treeという新しい提案（BIP-98）が公開され↓
https://github.com/bitcoin/bips/blob/master/bip-0098.mediawiki
↓のような特徴がある。
パフォーマンスの向上
リーフノードからマークルツリーを構築する際、親ノードの値は２つの子ノードの値を結合し、それをdouble-SHA256ハッシュした値になる。この提案では必ずしもここでdouble-SHA256である必要はなく、これをfast-SHA256という新しく定義する暗号学的ハッシュ関数に置き換えることでパフォーマンスを向上させる。ただこのハッシュ関数はインプットとして2つの32バイトのハッシュ値を持つデータに対してのみ有効なハッシュ関数となる。
脆弱性への対応
マークルツリーの構築アルゴリズムでは、マークルツリーのリーフ要素が奇数の場合、奇数の最後の要素を複製して偶数個にするが、ここに重複エントリーの問題がある。奇数個のリストのアイテムを持つマークルツリーと、奇数個の最後の要素と全く同じ要素を加えて偶数個にしたリストのマークルツリーは、リーフノードの要素数は異なるが、それら計算したマークルルートは同じ値になる。Fast Merkle Treeの場合、要素数が奇数個の場合にその要素をコピーして偶数個にすることをしないことで、この脆弱性を回避する。
データがマークルツリーに含まれていることを証明するInclusion Proofのエンコード方法
マークルツリーにあるデータが含まれていることを示すプルーフ提供の仕組みは、SPVノードなどが受け取るmerkleblockメッセージなどで利用されている。このメッセージには
が含まれており、これをベースにマークルツリーの部分的な復元や検証をしている。この内、フラグリストには1バイト中に8個のフラグビットがセットされ、そのフラグビットの0 or 1でマークツリー内のノードにハッシュを割り当てるかどうか判断している。
一方このFast Merkle Treeでは、ツリーの内部ノードの数を可変長整数でシリアライズし、その後に内部ノードが持つ２つの子ノードが{SKIP,VERIFY,DESCEND}のどの構成であるか示す3 bitのデータをルートノードから順番にバイト列にパックしシリアライズしたデータでツリー構造を表現するようになっている。
用途
↑のような特徴があるFast Merkle Treeだが、既存のブロックヘッダのマークルルートの計算方法をこれに変えようという提案ではなく（変更するとHFになる）、別で提案されているBIP-116のMERKLEBRANCHVERIFYの実装でこのアルゴリズムを使用するようだ。
詳細についてはBIPの内容を見てみる↓
概要
多くのアプリケーションでは、あるデータがデータセット内のデータであることを証明するのに、データセットの全データを明らかにする必要はない。インナー/内部ノードのラベルがその子ノードのハッシュから生成されるマークルハッシュツリーは、それを実現する暗号化ツールだ。Bitcoinではブロック内のトランザクションをブロックヘッダにコミットするのにマークルハッシュツリーを利用している。Satoshiによって作られたこの設計は、National Vulnerability DatabaseのCVE-2012-2459*1に記載されているように重複したエントリーに関連する深刻な欠陥に悩まされており、また不必要なダブルハッシュにより最適なパフォーマンスとは言えない。
このBIPでは、CVE-2012-2459の脆弱性がなく、最適化したSatoshiのマークルハッシュツリー構造の実装に比べてハッシュツリーの構築および検証時間が55%減少する、より効率的なマークルハッシュツリー構造について説明する。
動機
マークルハッシュツリーは、全ての非末端ノードはそのノードに接続されているノードの値もしくはラベルを結合した値のハッシュ値でラベルされる非循環有向グラフのデータ構造である。BitcoinはSatoshiが考案したユニークなマークルハッシュツリー構造を利用して、ブロック内のトランザクションのリストに対するブロックヘッダのコミットメントを計算している。新しいアプリケーションではこれと同じデータ構造を利用することで、実装の共有やメンテナンスコストの削減が見込まれるが、再利用には３つの欠陥がある。
最初に、Satoshiのマークルハッシュツリー構造は重複したエントリーについて深刻な欠陥があり、そのまま使用するとプロトコルにバグをまねく可能性がある。この欠陥の悪用からプロトコルと実装を保護することは可能だが、この脆弱性を回避する安全なプロトコルを設計するには洞察といくつかの注意が必要だ。新しいプロトコルの設計者はネイティブな実装による下流のバグの可能性を確実に減らすため、可能な限りSatoshiのマークルツリーハッシュ構造の使用を避けなければならない。
第二に、Satoshiのマークルツリーハッシュは不要な数の暗号学的ハッシュ関数の圧縮ラウンドを実行する必要があり、本来の用途として必要な数に比べて、簡単な実装では約3倍の計算時間と検証時間がかかり、目的に特化した実装でも2.32倍以上の計算量が必要になる*2。後方互換性を必要としない新しい実装では、不必要な負荷を実行しないハッシュツリーの実装を検討する必要がある。
第三に、Satoshiのアルゴリズムは順序付きリストからツリーインデックスを構築することを前提としているため、ツリー内の全ての要素についてルートからリーフまで均一のパス長をもつバランスの取れたツリーをサポートするよう設計されている。一方、多くのアプリケーションでは不均衡なパス長を持つツリーを活かしている。特に短いパスが使用される可能性が高い場合により効果的だ。Satoshiのハッシュツリーのいくつかの要素を他の要素より短いパスにすることも可能だが、そのためのトリックはツリーのサイズに依存しあまり柔軟ではない。
これら３つの理由は、これらの問題を解決する新しいプロトコルで使用する標準的なマークルハッシュツリー構造を指定する際の正当性を提供する。このBIPではその構造について記述し、実装例を示す。
仕様
このBIPで定義されているマークルハッシュツリーは任意のバランスのバイナリツリーで、その末端のリーフノードはデータのdouble-SHA256ハッシュでラベル付けされ（そのフォーマットは本BIPの範囲外）、内部ノードはその子ノードのラベルのfast-SHA256 から生成された値でラベル付けされる。以下の図はアンバランスなハッシュツリーの例を示している。
AおよびB、Cはリーフラベルで、リーフに関連付けられたデータの32バイトのdouble-SHA256ハッシュである。NodeとRootは内部ノードで、そのラベルはそれぞれの子ノードのラベルのfast-SHA256ハッシュである。NodeはBとCを連結したfast-SHA256ハッシュでラベル付けされる。RootはAとNodeを連結したfast-SHA256ハッシュでラベル付けされ、このツリーのマークルルートである。子ノードが１つだけのノードは許可されない。
double-SHA256暗号学的ハッシュ関数は、任意の長さのデータをインプットとし、FIPS 180-4*3で指定されたSHA256ハッシュ関数を介してデータを実行し、length-extension attack（伸長攻撃）から保護するため同じハッシュを再度実行して32バイトのハッシュを生成する。
fast-SHA256暗号学的ハッシュ関数は２つのハッシュ値を取り、これらを連結して64バイトのバッファを生成し、 カスタム初期化ベクトル (IV)と、メッセージパディング無しでSHA256ハッシュ関数を1回実行する。結果は結合されたハッシュ値と内部ノードのラベルである32バイトのmidstate*4である。変更されたIVは、パス拡張攻撃に対する保護になる。fast-SHA256は2つの32バイトのハッシュに対してのみ有効な定義である。カスタムIVは、以下の16進エンコードされたバイト列について標準のSHA256を実行したmidstateを展開した後に生成される中間ハッシュ値である。
cbbb9d5dc1059ed8 e7730eaff25e24a3 f367f2fc266a0373 fe7a4d34486d08ae d41670a136851f32 663914b66b4b3c23 1b9e3d7740a60887 63c11d86d446cb1c
このデータは9番目の素数である23の平方根の最初の512小数bitであり、結果得られるmidstateはfast-SHA256暗号学的ハッシュ関数のIVとして使われる。
static unsigned char _MidstateIV[32] =
{ 0x89, 0xcc, 0x59, 0xc6, 0xf7, 0xce, 0x43, 0xfc,
0xf6, 0x12, 0x67, 0x0e, 0x78, 0xe9, 0x36, 0x2e,
0x76, 0x8f, 0xd2, 0xc9, 0x18, 0xbd, 0x42, 0xed,
0x0e, 0x0b, 0x9f, 0x79, 0xee, 0xf6, 0x8a, 0x24 };
fast-SHA256は2つの32バイトハッシュのインプットに対してのみ定義されているので、2つの特殊なケースがある。空のマークルツリーは許可されず、そういったツリーに対してはルートハッシュも定義されない。データが１つだけのマークルツリーの場合、そのルートハッシュはツリーの唯一のリーフノード自身の値と同じになる（パススルー操作でハッシュ計算が行われない）。
論拠
64バイトのデータをFIPS 180-4で指定されているSHA256でハッシュすると（メッセージパディングのため）2回の圧縮が実行され、double-SHA256を計算するのに3回の圧縮が実行される。このためfast-SHA256ハッシュ関数は、用途を特化したdouble-SHA256の実装より2.32倍高速に、通常のSHA256プリミティブを2回適用する実装より3倍高速に計算できる。同様にfast-SHA256のマークルルートの検証は、SatoshiがBitcoinで使用するdouble-SHA256より2倍以上高速に行える。さらにfast-SHA256の実装は一般的なSHA256の実装であり、パフォーマンスコストをかけずに汎用回路やコードへの再利用が可能だ。
fast-SHA256はインプットがハッシュ値で数値と長さが固定されているので、メッセージのパディングやダブルハッシュによる攻撃の影響を受けることはなく、安全に内部ノードのラベル付けを行うことができる。
fast-SHA256の初期化ベクトル（IV）はリーフハッシュや内部ノードのコミットメントが別のリーフハッシュと部分的に衝突するような上位レベルのプロトコルに対する攻撃を防ぐために変更されている。IVはカスタムIVをサポートしていない暗号ライブラリインタフェースとの互換性を保つため、カスタムIVやmidstateからのレジュームをサポートしていない場合、↑の2倍のパフォーマンスを犠牲にして標準のSHA256とmidstateの抽出を行い計算される。ハッシュされたデータは、ハッシュプリイメージが知られていないnothing-up-my-sleeve numberである。2〜19までの最初の8個の素数の先頭bitが既にSHA256自体の設定に使われている定数であるため、その次の9個めの素数23を選択した。次の素数を順番に使うことで一定の因子の再利用による弱点が導入される可能性を減らすことができる。
データ要素が１つしかないツリーのマークルルートハッシュは、何の変更もないリーフハッシュへの単純にパススルーで、スプリットプルーフの連鎖検証を可能にする。これは、Bitcoinスクリプトのプッシュ制限のような検証サイズに制限があるような検証環境において便利だ。連鎖検証により検証者は１つのプルーフを2つ以上に分割することができ、リーフは内部ノードの下に示され、内部ノードがルートの下に示される。データ要素が１つのみツリーにおいてパススルーハッシングでない場合だと、連鎖検証を使うのにチェーンのリンクの数と同じ最小パス数の要件が余計に必要になる。単一要素のパススルーハッシングは１つ以上の連鎖検証の代わりにゼロ長パスからなるNOPプルーフを使うことができ、それにより例えば固定された一連の４つの連鎖検証が長さ３以下のパスを検証できる。
Inclusion Proofs
マークルルートハッシュの使い方で重要なのは、オーダーlog（サイズ）のプルーフで、任意のデータが含まれていることをコンパクトに証明できることだ。このセクションでは、ある複数の要素がツリーに含まれていることを証明するプルーフの標準的なエンコード方法を定義する。
特定のルートを持つマークルツリーにあるハッシュのセットが含まれていることを証明するには次の４つの情報が必要になる。（この要素は既存のマークルツリーの場合と同じ）
- マークルツリーのルートハッシュ
- 検証されるハッシュ値。通常データ要素のdouble-SHA256で構成されるが、それか内部ノードのラベルかその両方。
- ルートから対象のハッシュがあるノードへのパス（シリアライズされたバイナリツリー構造として表現される）。
- それらのパスに含まれないブランチ（ノード）のハッシュ値
通常↑の最後の２つの要素（パスとパスを辿らないブランチのハッシュ）をまとめてプルーフと呼んでいる。
シリアライズする際は、まずプルーフ内の内部ノードの数Nを可変長整数（Varint）としてエンコードする。次にツリーの構造を、深さ優先で左から右、前順・先行順・前置順・行きがけ順で各内部ノードを走査する前提で、各ノードの構成をパックした3bit表現でエンコードする（ノード数Nに応じて(3*N + 7) / 8バイト消費する）。続いてスキップするハッシュの数（プルーフの中に含まれるハッシュ、プルーフで検証しないもの）は、可変長整数（Varint）でシリアライズされ、その後にプルーフで明かされるハッシュ自体が順番に続く。
以下の図のように８個の内部ノードの構成が可能だ。
この図では、DESCENDは"..."とラベル付けされた子グラフ要素で表されている別の内部ノードへの分岐リンクを意味する。SKIPはそのブランチに省略されたサブツリーのハッシュか要素のハッシュが含まれていることを意味し、このブランチのサブツリーのfast-SHA256ルートハッシュかデータ要素のdouble-SHA256ハッシュのどちらかがプルーフデータの中に含まれている。VERIFYはそのブランチにプルーフの検証に必要なwintessとして外部から提供されたハッシュが含まれていることを意味する。表形式にするとこれらのコード値は以下の通り。
| コード | Left | Right |
|---|---|---|
| 000 | VERIFY | SKIP |
| 001 | VERIFY | VERIFY |
| 010 | VERIFY | DESCEND |
| 011 | DESCEND | SKIP |
| 100 | DESCEND | VERIFY |
| 101 | DESCEND | DESCEND |
| 110 | SKIP | VERIFY |
| 111 | SKIP | DESCEND |
この３つのbitコードは3バイト毎に8つのコードが収まるようバイト列にパックされる。バイトを埋めていく順序は最上位bit0x80で始まり、最下位bit0x01で終わる。内部ノードの数が8の倍数でない限り、シリアライズした最終バイトは下位bitが余ることになり、この余りのbitには全てゼロがセットされなければならない。
ツリーのシリアライゼーションは自己分割であることに注意すること。ツリー構造を追跡することで、プルーフの校正者はパーサーがいつ最後の内部ノードに到達したかを知ることができる。プルーフ内にシリアライズされた内部ノードの数は、ツリー構造自体から推論されるノード数と等しくなければならない。同様に、SKIPハッシュの数はシリアライズされたツリー構造から推論することもでき、プルーフ内のハッシュの数と等しくなければならない。
（内部ノードが無い）シングルハッシュプルーフはN=0で、（内部ノードが無いので）ツリー構造もシリアライズされずSKIPハッシュの数は0または1のいずれか。
例
次のマークルツリー構造を考えてみよう。
この構造では6個の内部ノードがある。深さ優先で左から右、前順・先行順・前置順・行きがけ順で探索するとA→B→→D→F→C→Eの順に回る。３つのSKIPハッシュがあり、0x00... → 0x66... → 0x22...の順に回る。残りの４つのハッシュは実行時に提供されプルーフにより検証される。
| Byte 1 | Byte 2 | Byte3 | |
|---|---|---|---|
| Bits | 76543210 | 76543210 | 76543210 |
| Nodes | AAABBBDD | DFFFCCCE | EE------ |
| Code | 10111101 | 10000100 | 01000000 |
シリアライゼーションは内部ノードの数の可変長整数（Varint）で始まるので↑だと0x06、次にツリーのシリアライゼーション自体（↑だと0xbd8440）が続く。次のSKIPハッシュの数も可変長整数としてエンコードされ↑だと0x03、その後に３つのハッシュが順番に続く。結果101バイトのプルーフBase64で以下のようにエンコードされた値となる。
Br2EQAMAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmREREREREREREREREREREREREREREREREREREREREREQ=
論拠
内部ノードの3 bitエンコードは、左右のブランチがそれぞれ｛DESCEND, SKIP, VERIFY｝のいずれかであるかを示す構成をエンコードすることができる。この他、除外された第９のパターンとして、左右のブランチが両方共SKIPであるパターンがある。
このパターンは検証のため許可されていない（そのブランチ自体へのSKIPと同じことであるため）。この２つのSKIPブランチを持つノードを不許可にすることで、プルーフのmalleabitiyの原因を排除している。
プルーフを検証するために必要なハッシュ計算の回数は、ハッシュの数（SKIPとVERIFYを合わせた数）より１つ少なく、内部ノードの数Nと等しい。可変長整数エンコーディングにはシリアライズされた数値も辞書順にソートされたものも数値順にソートされるという性質がある。最初にシリアライズされるのは内部ノードの数であるため、プルーフを辞書順にソートすることはプルーフの検証に必要な作業量でプルーフをソートする効果がある。
プルーフの検証のためのインプットとして必要なハッシュの数は、N+1からSKIPハッシュの数を引いたもので、ツリー構造を解析することなく素早く計算することができる。
シリアライズされたツリー構造のコーディングルールとパッキングルールは辞書比較を有効にするため選択された。もし完全に拡張されたツリー（SKIPが無く全てVERIFYの）を左から右に深さ優先で要素のリストをエンコードするとみなした場合、欠損している値のハッシュをSKIPし、SKIP,SKIPノードを再帰的にプルーニングすることでリストのサブセットのプルーフ抽出することができる。結果得られるシリアライズされたツリー構造を辞書順に比較することは、派生したプルーフによって検証されたオリジナルのリストからインデックスのリストを比較するのと同じことである。
内部ノードの数とSKIPハッシュの数はツリー構造から抽出可能であるため、プルーフ内の可変長整数は両方とも冗長で省略可能だ。しかし、そうするとシリアライゼーションと検証の両方で、デシリアライズの際にメモリ上に明示的にツリーを構築・保持する必要があるか、比較的複雑なツリー解析コードの複製が必要になる。そのため（単一ハッシュのエッジケースの場合も同様）、冗長だが内部ノードの数とSKIPハッシュの数を明示的にシリアライゼーションし、プルーフが有効であるためにはその２つの値がツリー構造から推測される値と一致しなければならない。これによりデシリアライズが簡単になり、検証のタイミングまでツリーの構築を遅らせることができる。これには対数時間の検証アルゴリズムが有効になるという追加のメリットがある。
Fast Merkle Lists
多くのアプリケーションではマークルツリーを使用してリスト内の要素についてのインデックス化やコンパクトなメンバーシップ証明を提供する。この仕組はいろんな長さのリストのための標準的な平衡木構造を構築するアルゴリズムを指定する。このアルゴリズムには、重複エントリーに関連する脆弱性を構造的に防止するため、Satoshiのアルゴリズムとは微細だが重要な点で違いがある。
- まず任意のデータ文字列のリストがある。
- リストの各要素をそれぞれdouble-SHA256ハッシュした値に置き換える前処理を行う。
- リストが空の場合は、ゼロハッシュを返す。
- リストに２つ以上の要素がある場合は
- リストの隣接するエントリーを結合し、fast-SHA256ハッシュに渡す。リストの要素が奇数の場合、最後の要素をそのまま残す（これにより脆弱性を修正する）。このステップでN個のリストの要素をceil(N/2) 個のエントリーに減らす。
- リストに残った最後のアイテムがマークルルートである。
このアルゴリズムはBitcoinで使われているマークルリストと２つの点で異なる。１つめは、内部ノードのラベル付けにdouble-SHA256でなくfast-SHA256が使われる。２つめは、奇数長のリストの最終エントリーは重複してハッシュされない。これはCVE-2012-2459につながった間違いだ。
実装
このBIPのマークルブランチの抽出と高速なマークルブランチの検証は以下のGithubのリポジトリで利用可能だ。
https://github.com/maaku/bitcoin/tree/fast-merkle-tree
このリポジトリにはこのBIPのアルゴリズムを使用してルート値の計算と任意ツリーのinclusion proofsの抽出および値のリストからツリーを構築するmerklebranch RPCと、２つ以上のマークルinclusion proofsを統合する（SKIPハッシュを別のproofから抽出したサブツリーに置き換える）ためのmergemerklebranch RPCが含まれる。
デプロイ
このBIPは、BIP-116（MERKLEBRANCHVERIFY）がソフトフォーク用のNOP拡張opcodeを使用してMerkle inclusion proof の検証をスクリプトに追加するために使用される。MERKLEBRANCHVERIFYのデプロイはこのBIPの内容を決定的にするだろう。BIP-116のデプロイ計画はそのBIPの本文に記載されている。
*1:bitcoind及びBitcoin-QTの0.6.2より前のバージョンにあったDoS攻撃の脆弱性で、マークルツリーのリーフに重複したトランザクションを配置してブロックハッシュを衝突させ、同じハッシュを持つ正当なブロックを受け入れられないようにする。
*2:2017年9月にPieter Wuilleとの個人的なコミュニケーションの結果、ハッシュ関数の各ステージのインプットが固定長であるという知識を利用することで、Satoshiのマークルツリー構造ハッシュ集約関数について、Wuille氏は64バイトデータのdouble-SHA256ハッシュの計算にかかる時間を22.7%短縮することができた
*3:Federal Information Processing Standard（FIPS） PUB 180-4
*4:SHA256はデータを64バイト毎のチャンクに分割し処理を行う。チャンク毎に、データを分割→拡張→圧縮という工程を経るが、この時の圧縮してできたデータがmidstateで、次のチャンクで圧縮処理をする際に使用される。
