Merkle Tree

1. 概要

マークルツリー (Merkle Tree) [1, 2] またはハッシュツリー (Hash Tree) は、順序のあるデータセットの各要素をハッシュ化し、それらを二分木構造で組み合わせて構築されるデータ構造である。木の各葉ノードは個々のデータのハッシュ値を格納し、各内部ノードは子ノードのハッシュ値を連結してハッシュ化した値を格納する。最上位のルートハッシュはデータセット全体の暗号論的要約として機能し、データの整合性検証に用いられる。

マークルツリーは、主に大量のデータの効率的な検証を目的として 1979 年に Ralph C. Merkle によって発明された。この構造により、データセット全体を保持することなく、特定のデータが更新、破損、改ざんされていないことを対数時間で検証することが可能になる。

マークルツリーは分散ストレージシステム、P2P ファイル共有ネットワーク、ブロックチェーン、データベースシステムなど、データの整合性保証が重要な多くの分野で利用されている。特に、信頼性の低いネットワークやノードが存在する分散環境において、効率的なデータ検証手段として広く利用されている。

Table of Contents

1. 1. 概要
2. 2. マークルツリーの構築
3. 3. データの検証
   1. 3.1. 異なるデータの特定
   2. 3.2. 部分データの検証
      1. 3.2.1. 例: データ検証
      2. 3.2.2. 例: チケット購入者の確認
4. 4. マークルツリーの変種
   1. 4.1. スパースマークルツリー
   2. 4.2. Merkle Search Tree
   3. 4.3. Prolly Tree
   4. 4.4. History Tree
5. 5. 参考文献

2. マークルツリーの構築

マークルツリーは完全二分木として構成される。葉ノードにはデータのハッシュ値が格納され、各内部ノードには 2 つの子ノードのハッシュ値を連結した値のハッシュが格納される。ツリーの構築は以下の手順で行われる:

1. 各データ \(D_i\) に対してあるハッシュ関数 \(h\) を使ってハッシュ値 \(h_i = h(D_i)\) を算出し、葉ノードを生成する。

2. 隣接する 2 つの葉ノードのハッシュ値を連結してハッシュ値 \(h_{i,i+1}=h(h_i\,||\,h_{i+1})\) を算出し、親ノードを生成する。

3. ルートノードに達するまで同じ操作を上位レベルに向かって再帰的に繰り返す。

Figure 1 は 8 個のデータ ("To", "be", "or", "not", "to", "be", "that", "is") からマークルツリーを構築する例を示している (実際に SHA-256 を使用して算出している)。各データをハッシュ化して 8 個の葉ノードを生成し、隣接するハッシュ値を連結してさらにハッシュ化することで上位ノードを作成する。

この例では 8 個のデータから高さ 4 のマークルツリーが構築され、単一のルートハッシュ値 B76BC6BC によってデータセット全体が表現される。

データ数が 2 のべき乗でない場合、二分木を構築するために追加の処理が必要となる。一般的な実装では以下のいずれかの方法が採用される:

最終ブロックの複製

最も単純な手法として、2 のべき乗個となるまで最後のノードを複製する方法がある。例えば \(D_0\) から \(D_4\) の 5 つのデータブロックの場合、6 から 8 番目の葉ノードは \(h_4=h(D_4)\) を複製してツリーを作成する。この方法は実装が簡単だが、同一データの重複により若干の空間的非効率性が生じる。

単独ノードの上位昇格

より効率的な方法として、同じレベルでペアを持たないノードをそのまま上位レベルに昇格させる方法がある。5 つのデータブロックの例では \(h(D_4)\) を第 1 レベルに直接昇格させ、最終的にルートハッシュは \(h(h(h(h_0 || h_1) || h(h_2 || h_3)) || h_4)\) のような非対称な構造で算出される。この方法はストレージ効率に優れるが、実装がやや複雑になる。

パディングによる補完

データセット末尾に空のブロックやダミーデータを追加し、2 のべき乗個まで補完する方法がある。この場合、パディングされたブロックには既定の値 (通常は 0) を使用し、\(h(0)\) などの固定値で葉ノードを生成する。

空の中間ノードの追加

History Tree [3] では完全二分木をベースの形として、データが存在しない部分木のルートノードを \(h(\emptyset)\) などの空のハッシュ値と置き換えることで部分木全体の保存空間を節約する。

BitTorrent プロトコルでは最終ブロックの複製方式、Bitcoin 等の多くのブロックチェーンシステムでは単独ノードの昇格方式を採用している。どの方式を選択するのが最良かは、実装の複雑さ、ストレージ効率、および既存システムとの互換性要件に依存する。

3. データの検証

ハッシュ関数における雪崩効果 (avalanche effect) は、元データに 1 ビットでも変更があるとハッシュ値が完全に異なる値になることである。この性質により、マークルツリーでは 2 つのデータセットが同一であるかをそれぞれのルートハッシュを比較するだけで判断できる。さらに、ハッシュ値がツリー構造を構成していることにより、差異のあるハッシュ値の枝を葉に向かって下ることで、差異のあるデータを効率的に見つけることができる。

Figure 2 は Figure 1 における "be" を "pee" に変更した例である。変更のあった "pee" の葉ノードからルートノードまでのハッシュ値が全く違う値になることが分かる。

3.1. 異なるデータの特定

データセット A と B のルートハッシュが一致する場合、暗号論的ハッシュ関数の衝突耐性により A と B は同一のデータセットであると見なすことができる。逆に、ルートハッシュが異なる場合、少なくとも 1 つのデータに差異が存在すると判断できる。

マークルツリーはハッシュ値をツリー状に配置した構造を持つため、2 つのマークルツリーから差異のあるデータを効率的に特定できる。ルートノードから開始し、ツリーの各レベルで対応するノードのハッシュ値を比較して異なるハッシュを持つ子ノードを絞り込んでいくことで、変更されたデータまで対数時間で辿り着くことができる。具体的な手順は次の通りである:

1. ルートノードで差異を検出する。

2. 2 つの子ノードのハッシュ値を比較し、ハッシュ値の異なる部分ツリーを選択する (両方の子ノードが異なっている可能性があることに注意)。

3. 葉ノードに到達するまで同様の比較を繰り返す。

4. 最終的に特定された葉ノードが、差異のあるデータである。

この探索過程では各レベルで候補が半分に絞り込まれるため、\(n\) 個のデータを持つツリーにおいて差異のある 1 つのブロックを \(O(\log n)\) 回の比較で特定できる。例えば 1,000,000 個のデータブロックを持つデータセットでも最大 20 回程度の比較で変更箇所を特定可能である。

差異のあるデータ数が \(m \le n\) 個存在する場合、各レベルで差異を持つノードの数が増加するため、探索すべき部分木が増大する。最悪のケースはすべてのデータが異なる \(m = n\) のケースで、これはツリー上のすべてのノードで差異が発生するため、2 つのツリーのすべてのノードを完全に走査する必要がある。したがって、完全二分木のノード数 \(2n-1\) より、最悪計算量は \(O(n)\) となる。

分散システムでは、差分レプリケーション (差分バックアップ) やアンチエントロピー機構において、差異のあるデータを特定する目的でマークルツリーが使用されている。

3.2. 部分データの検証

マークルツリーの主要な利点の一つは、データセット全体を保持することなく特定のデータの整合性を検証できることである。言い換えると、メンバーシップ検証 (membership verification) が可能である。検証者は事前に信頼できるルートハッシュのみを保持し、検証対象のデータと認証パス（authentication path）と呼ばれる最小限のハッシュ値セットを用いて検証を行う。

3.2.1. 例: データ検証

部分データ検証の実用例を Figure 3 に示す。この例では、クライアントが信頼できるルートハッシュを事前に保持しており、計算処理のためにデータセットから \(D_5\) のみをサーバに要求する状況である。

このシナリオでは、クライアントは何かを計算するためにデータ \(D_5\) をサーバに要求する。しかし、何らかの理由でクライアントが取得した \(D_5\) が破損していた。しかし、クライアントはデータと共に取得した認証パスからルートハッシュを計算して、自身の持つ信頼できるルートハッシュと比較することで、このデータ (または認証パス) が破損していることを検出できる。

サーバが悪意をもってデータを改ざんしようとしても、ルートハッシュを一致させるような認証パスを意図的に作成することは困難であることに注意。マークルツリーで使用するハッシュ関数は用途に応じて選択される。悪意のある改ざんからの保護が必要な場合は SHA-256 や SHA-3 などの暗号学的ハッシュ関数が必要である。一方、単純なデータ破損の検出が目的であれば aHash などの高速な非暗号論的ハッシュ関数 (あるいはもっと弱いチェックサム) も考慮することができる。

3.2.2. 例: チケット購入者の確認

あるイベントがあり、チケット発行会社が購入者リストを保持している。ただし、セキュリティの観点から購入者リストをイベント運営会社 (外部の業者) に渡したくない。受付に来た客のチケットが正規のものであることを、イベント運営会社はどう確認すれば良いだろうか?

チケット発行会社は購入者リストを Merkle Tree 化し、チケットには購入者の認証パスを記載して渡す。またイベント会場の受付には購入者リストのマークルルート値をあらかじめ伝えておく。受付は、客の提示したチケットからルートハッシュを算出し、それがチケット発行会社から伝えられたハッシュ値と一致していれば、そのチケットが正規に購入されたものであることを確証できる (本人確認は別途必要)。

この方法には 2 つの利点がある。一つは、チケット発行会社とイベント運営会社の間で購入者リストを受け渡す必要がないこと。もう一つは、イベント運営会社はイベント当日にチケット発行会社のシステム状況に依存せずにチケット購入の確認ができることである。ただし、実際にはツリーが確定する (チケット販売が終了する) までルートハッシュも認証パスも確定できないため、実際のチケット送付がそれ以降になるというような、現実的な問題をクリアする必要がある。

4. マークルツリーの変種

マークルツリーの基本的なアイディアはデータの整合性を検証するために設計されている。しかし、現実適用する上では対象とするアプリケーション要件に合わせてカスタマイズする必要があったり、異なるデータ構造やアルゴリズムと組み合わせて追加の効果を提案するアイディアの余地が多くあるため、様々な変種が提案されている。

4.1. スパースマークルツリー

葉の数 \(n\) が非常に大きいが (例えば \(n=2^{256}\))、そのほとんどが 0 や null といった値を持たない (つまりデフォルト値の) マークルツリーをスパースマークルツリー (sparse merkle tree; 疎マークルツリー) と呼ぶ。\(n\) 個の葉のうち \(k\) 個が有効な値の場合、レベル 0 のノードのうち \(n-k\) 個はデフォルト値 \(h_*=H(0)\) を持つことになる。同様にレベル 1 のほとんどは \(h_*=H(H(0)\,|\,H(0))\) である。このようにスパースマークルツリーのほとんどの中間ノードはデフォルト値のままである。このようなスパースマークルツリーのルートハッシュはデフォルト値のハッシュ計算を省略することで \(O(k \log n)\) の計算コストで算出することができる。

疎となることが前提のマークルツリーはデフォルト値となる葉やノードを省略してパトリシアツリー (Patricia tree) またはマークルパトリシアトライ (Merkle Patricia trie) と呼ばれる構造を適用することができる。例えば Ripple や Ethereum ではスパースマークルツリーとしてパトリシアツリーを使用している。

4.2. Merkle Search Tree

Merkle Search Tree (MST) は Key-Value ペアのデータを格納でき、キーのソート順に基づいてノードを構築する、バランスの取れた二分検索木構造のマークルツリーである。同じデータセットに対して同じ順序でデータを挿入すると常に同じツリー構造が生成される決定論性を持つことから、ブロックチェーンのステート DB など、厳密な順序性と決定論性が必要なシステムに適している。

Merkle Search Tree は BlueSky の AT Protocol で Key-Value ストアのアンチエントロピー機構として使用されている。

4.3. Prolly Tree

Prolly Tree (Probabilistic Merkle Tree) は入力データに対してローリングハッシュで算出したハッシュ値からチャンク境界を決定し、各チャンクがそれぞれツリーの葉に対応する。

与えられたデータ列を特定のアルゴリズムに基づいて小さな塊 (chunk) に分割することを Chunking と呼ぶ。特定のアルゴリズムとは、例えばデータのハッシュ値の末尾がいくつのゼロで終わるといった条件である。

ローリングハッシュは、データ列でウィンドウ (範囲) を移動させ、そのウィンドウに入っているデータからハッシュ値を算出する (ウィンドウ移動時のハッシュ値計算量がウィンドウサイズによらず \(O(1)\) となる特徴を持つ)。データ列にローリングハッシュを使用する場合、ある位置でのデータ挿入、変更、削除はウィンドウ範囲内のハッシュ値にしか影響しない。つまり、ローリングハッシュを使用してチャンク境界を決定するスキームは、変更に対して局所的にハッシュ値や境界に影響が出るものの、他の大多数のチャンクに影響はなく、ツリー全体の構造は大きく変わらないという特性を持つ。この方法により、同じデータセットに対して常に同じ構造のツリーが生成される履歴独立性を持つ。

2 つの Prolly Tree を比較するときは、通常のハッシュツリーのようにルートから順にハッシュ値を比較するだけではなく、大きく共通している部分をスキップする。このような差分探索は \(O(\log n)\) で行うことができる。Prolly Tree は、構造の安定性と差分検出効率が良いため、データが頻繁に更新される環境や、ネットワークを介して効率的に同期を行う場合に有用であり、分散システムでのデータ同期や CRDT 実装に向いている。

Dolt は Prolly Tree 上に構築されたバージョン管理型 SQL データベースである。

4.4. History Tree

Merkle ツリーの亜種である History Tree [3] は追加が可能な改ざん証跡ログシステムを提案している。またこの研究では、中間ノードに属性を持たせることで、データセットの簡易的な検索を行うことができる Merkle 集約 (Merkle aggregation) も提案している。

また、中間ノードに属性や Bloom Filter を設置することによって簡易的な検索を行う提案が成されている。

5. 参考文献

1. Merkle, R.C. (1979). A Certified Digital Signature. In: Brassard, G. (eds) Advances in Cryptology — CRYPTO’ 89 Proceedings. CRYPTO 1989. Lecture Notes in Computer Science, vol 435. Springer, New York, NY. https://doi.org/10.1007/0-387-34805-0_21
2. Merkle, R.C. (1987) A Digital Signature Based on a Conventional Encryption Function. Conference on the Theory and Application of Cryptographic Techniques, Santa Barbara, 16-20 August 1987, 369-378. https://doi.org/10.1007/3-540-48184-2_32
3. Crosby, Scott A., and Dan S. Wallach. Efficient Data Structures for Tamper-Evident Logging. USENIX security symposium. 2009.