Merkle Tree
概要
マークルツリー (Merkle tree; ハッシュ木) はあるデータセットのハッシュ値を再帰的にハッシュ化することで得られるツリー構造。このツリーのルートにあたるルートハッシュはすべてのノードのハッシュ特性を含んだ固定サイズの値であるため、あとでデータを検証するために保持するのに都合が良い。
Table of Contents
マークルツリーの最も一般的な利用例は、あるデータセットを信頼できないストレージやノードに分散して保存するケースである。アプリケーションは自分の持つ固定長のルートハッシュとそれらからロードしたデータを比較することで、データが破損や改ざんを受けていないかを効率よく検証することができる。このため P2P ネットワークやファイルシステムでよく利用されている。
データを分散して保存する場合、データセット全体に対して生成した単一のハッシュ値で検証する場合には、データセット全体をロードする必要があり非効率的である。またデータごとにハッシュ値を作成するとデータサイズが大きくなるにつれて保存して置かなければならないハッシュ値も増大する。するのと違い、必要に応じてデータの一部だけを検証したい場合に都合が良い。
構造
マークルツリーの葉はデータセットの各データのハッシュ値である。隣り合う 2 つのハッシュ値を結合して再びハッシュ化し親のハッシュ値を生成する。ルートハッシュはすべてのデータのハッシュ特性を含んでいることになるため、データが少しでも改変されていれば全く異なる値をとる。
データセットからルートハッシュを算出することは難しくない。またツリー全体を持たずにルートハッシュだけを持っていたとしても、そのルートハッシュが (過去に自身で算出したり信頼できる第三者によって算出された) 信頼できるものであれば、あまり信頼できない経路で入手したマークルツリーが正しいかを検証することもたやすいだろう。
ハッシュ関数には改ざんに強く計算の高速な SHA-256 のような暗号論的ハッシュ関数を使用する必要がある。ただし、悪意のある改ざんを心配する必要がなく単にデータ破損の検出のみが目的であれば CRC のようなチェックサムを使用することもできる。
部分データ検証
マークルツリーはデータセットの一部のみを入手し、それが正しいことを検証するケースでしばしば有用である。信頼性の低いストレージや素性の知れないネットワークからロードしたデータおよびマークツリーは破損や改ざんを受けていないことを検証しなければならないが、それらから算出したルートハッシュが手元の \(h\) と一致していれば、そのデータとマークルツリーはルートハッシュを算出したときと同一である確証を得ることができる。したがってアプリケーションはこの検証のために固定長のルートハッシュ \(h\) のみを保存していれば良い。
マークルツリーの特定の葉からルートハッシュを算出する過程では、ほとんどのハッシュ値は上位のハッシュ値に代替されるか、もしくは算出が可能である。したがって検証のためにロードしなければならないハッシュ値は、データ数 \(n\) に対して \(\log_2 n\) と非常に少なくて済む。Fig 2 の例ではロードしたデータ \(010\) を検証するために 3 つのハッシュ値のみを入手すれば十分であることを示している。
- \(h_{010}\) はデータ \(010\) から算出可能である。
- \(h_{01} = {\rm hash}(h_{010} || h_{011})\) を算出する。
- \(h_{0} = {\rm hash}(h_{00} || h_{01})\) を算出する。
- 最後に算出する \({\rm hash}(h_{0} || h_{1})\) が \(h\) と一致していればデータ \(010\) は改変されていない。
この 3 つのハッシュ値のようにデータからマークルルートに到達するまでに必要なノードを認証パス (authentication path) と呼ぶ。暗号論的ハッシュ関数を用いれば、この計算過程の最終的な結果が \(h\) と一致するようなデータ \(010\) および認証パス \(h_{011}\)、\(h_{00}\)、\(h_{1}\) を意図的に偽造することは困難である。つまり悪意を持ったノードであっても検証を成功させるようなデータの改ざんは現実的ではない。
参考
- 説明に使用した機関車のイラスト
は freepik.com に帰属する。