Merkle Tree

概要

マークルツリー (Merkle tree; ハッシュ木) はあるデータセットのハッシュ値を再帰的にハッシュ化することで得られるツリー構造。このツリーのルートにあたるルートハッシュはすべてのデータのハッシュ特性を含んだ固定サイズの値であるため、後で一部のデータを検証するのに都合が良い。

Table of Contents

1. 概要
2. 構造
3. 部分データ検証
4. Sparse マークルツリー
5. 参考

マークルツリーの最も一般的な適用例は、あるデータセットを分割して信頼性の低いストレージやネットワークに分散して保存するケースである。アプリケーションは自分の持つ固定長のルートハッシュと、それらのストレージからロードしたデータを比較することで、データの破損や改ざんが起きていないことを効率よく検証することができる。このためマークルツリーはファイルシステムや P2P ネットワークでよく利用されている。

構造

マークルツリーの葉はデータセットの各データのハッシュ値である。隣り合う 2 つのハッシュ値を結合して再びハッシュ化し親のハッシュ値を生成する。ルートハッシュはすべてのデータのハッシュ特性を含んでいることになるため、データが少しでも改変されていれば全く異なる値をとる。

データセットからルートハッシュを算出することは難しくない。またツリー全体を持たずにルートハッシュだけを持っていたとしても、そのルートハッシュが (過去に自身で算出したり信頼できる第三者によって算出された) 信頼できるものであれば、あまり信頼できない経路で入手したマークルツリーが正しいかを検証することもたやすいだろう。

ハッシュ関数には改ざんに強く計算の高速な SHA-256 のような暗号論的ハッシュ関数を使用する必要がある。ただし、悪意のある改ざんを心配する必要がなく単にデータ破損の検出のみが目的であれば CRC のようなチェックサムを使用することもできる。

部分データ検証

ルートハッシュ \(h\) を保持しているアプリケーションが一部のデータと検証に必要なマークルツリー上の値のみをロードし、それが正しいことを検証する方法について考える。信頼性の低いストレージや素性の知れないネットワークからロードしたデータであっても、それらから算出したルートハッシュが手元の \(h\) と一致していれば、そのデータとマークルツリーはルートハッシュを算出したときと同一である確証を得ることができる。したがってアプリケーションはこの検証のために固定長のルートハッシュ \(h\) のみを保存していれば良い。

マークルツリーの特定の葉からルートハッシュを算出する過程では、ほとんどのハッシュ値は上位のハッシュ値に代替されるか、もしくは算出が可能である。したがって検証のためにロードしなければならないハッシュ値は、データ数 \(n\) に対して \(\log_2 n\) と非常に少なくて済む。Fig 2 の例ではロードしたデータ \(010\) を検証するために 3 つのハッシュ値のみを入手すれば十分であることを示している。

1. \(h_{010}\) はデータ \(010\) から算出可能である。
2. \(h_{01} = {\rm hash}(h_{010} || h_{011})\) を算出する。
3. \(h_{0} = {\rm hash}(h_{00} || h_{01})\) を算出する。
4. 最後に算出する \({\rm hash}(h_{0} || h_{1})\) が \(h\) と一致していればデータ \(010\) は改変されていない。

この 3 つのハッシュ値のようにデータからマークルルートに到達するまでに必要なノードを認証パス (authentication path) と呼ぶ。暗号論的ハッシュ関数を用いれば、この計算過程の最終的な結果が \(h\) と一致するようなデータ \(010\) および認証パス \(h_{011}\)、\(h_{00}\)、\(h_{1}\) を意図的に偽造することは困難である。つまり悪意を持ったノードであっても検証を成功させるようなデータの改ざんは現実的ではない。

Sparse マークルツリー

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

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

参考

1. 説明に使用した機関車のイラストは freepik.com に帰属する。