Merkle Tree

概要

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

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

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

Table of Contents

1. 概要
2. マークルツリーの構築
3. データの検証
   1. 異なるデータの特定
   2. 部分データの検証
4. スパースマークルツリー
5. 参考文献

マークルツリーの構築

マークルツリーは完全二分木として構成される。葉ノードにはデータのハッシュ値が格納され、各内部ノードには 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)\) などの固定値で葉ノードを生成する。

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

データの検証

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

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

異なるデータの特定

データセット 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)\) となる。

部分データの検証

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

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

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

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

スパースマークルツリー

葉の数 \(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 ではスパースマークルツリーとしてパトリシアツリーを使用している。

参考文献

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