ハッシュ木

ハッシュ木（マークル木）とは

ハッシュ木（Hash tree）またはマークル木（Merkle tree）とは、暗号理論と計算機科学で用いられる木構造の一種です。この木構造では、全ての葉ノードにデータブロックのハッシュ値がラベル付けされ、内部ノードには、その子ノードのラベルのハッシュ値がラベル付けされています。ハッシュ木を用いることで、大規模なデータ構造の内容を効率的かつ安全に検証できます。ハッシュリストとハッシュチェインを組み合わせた構造を持ち、特にハッシュ関数にTigerを使用するものはTiger TreeまたはTiger Treeハッシュとも呼ばれます。

ハッシュ木の用途

ハッシュ木は、単独または複数のコンピュータで保存、処理、転送されるデータの検証に利用されます。主な用途としては、P2Pネットワークにおいて、他のピアから受信したデータブロックが破損や改竄されていないか、または偽のデータブロックが送信されていないかを確認する処理が挙げられます。また、Trusted Computingでの利用も提案されています。具体的な例として、サン・マイクロシステムズのZFSファイルシステムや、Apache Waveプロトコル、分散バージョン管理システムGit、バックアップシステムTahoe-LAFS、BitcoinのP2Pネットワーク、NoSQLシステム（Apache Cassandra、Riakなど）で利用されています。

ハッシュ木の歴史

ハッシュ木は、1979年にラルフ・マークルによって発明されました。当初の目的は、大量のランポート署名を効率的に処理することでした。ランポート署名は量子コンピュータが実現しても安全とされていますが、1つの鍵で1つのメッセージしか署名できないという制約があります。ハッシュ木と組み合わせることで、1つの鍵を複数のメッセージに使用できるようになり、効率的なデジタル署名スキームを構築できます。

ハッシュ木の動作原理

ハッシュ木は、ハッシュ値を持つノードから構成される二分木です。葉ノードには、データブロック（ファイルや分割されたファイルなど）のハッシュ値が格納されます。上位ノードには、それぞれの子ノードのハッシュ値が格納されます。例えば、あるノードのハッシュ値は、その子ノードのハッシュ値を結合したものをハッシュ化したものです。

多くの実装では二分木（各ノードが最大2つの子ノードを持つ）が用いられますが、各ノードがより多くの子ノードを持つようにすることも可能です。ハッシュ関数としては、SHA-1、Whirlpool、Tigerなどの暗号学的ハッシュ関数がよく使われます。ただし、意図しないデータ破損を防ぐだけなら、CRCなどのよりセキュリティの低いチェックサムを使用することも可能です。

ハッシュ木のルートには、トップハッシュ（またはルートハッシュ、マスターハッシュ）が格納されます。P2Pネットワークでファイルをダウンロードする前に、信頼できる情報源からトップハッシュを取得することが一般的です。トップハッシュがあれば、ハッシュ木自体は信頼できない情報源（P2Pネットワークのピアなど）から取得しても構いません。取得したハッシュ木は、トップハッシュを使って検査され、破損や偽物であれば別の情報源から取得し直します。このプロセスを繰り返すことで、信頼性の高いデータ検証が可能になります。

ハッシュリストとの違い

ハッシュリストとの主な違いは、ハッシュ木の一部だけをダウンロードして検証できる点です。ハッシュ木全体が利用可能でなくても、一部の枝の完全性を検証できます。例えば、あるデータブロックの完全性を検証するには、ハッシュ木の一部のハッシュ値だけで十分です。この特性を利用して、ファイルを小さなブロックに分割し、破損したブロックだけを再ダウンロードすることで、効率的な処理が可能になります。

ハッシュ化対象のファイルが大きい場合、ハッシュ木やハッシュリストのサイズも大きくなりますが、ハッシュ木なら一部の小さな枝だけをダウンロードし、検証することで、データブロックのダウンロードをすぐに開始できます。

Tiger Treeハッシュ

Tiger Treeハッシュ（TTH）は、広く利用されているハッシュ木の形式の一つです。二分木であり、データブロックのサイズは1024バイト、ハッシュ関数には暗号学的に安全なTigerハッシュを使用します。Tiger Treeハッシュは、Gnutella、Gnutella2、Direct ConnectなどのP2Pファイル共有プロトコルや、Phex、BearShare、LimeWire、Shareaza、DCPlusPlus、Valknutなどのファイル共有アプリケーションで使われています。

まとめ

ハッシュ木は、データの完全性と信頼性を保証するための重要な技術です。P2Pネットワークや分散システムなど、さまざまな分野で利用されており、その応用範囲は広がり続けています。

参考文献

Merkle tree patent 4,309,569 – ハッシュ木の構造と、複数のワンタイム署名の処理に対する使用法に関する説明。
Tree Hash EXchange format (THEX) – Tigerツリーに関する詳細な説明。
Efficient Use of Merkle Trees – RSA labs マークル木の元々の目的に関する説明（複数のランポート署名を処理する）

関連項目

ハッシュテーブル
ハッシュトライ
Linked Timestamping

外部リンク

ThexCS - TTH (tiger tree hash) maker in C# - C#によるTiger Treeハッシュのソースコード（by Gil Schmidt）
tigertree - CおよびJavaによるTiger Treeハッシュの実装
* RHash - Tiger Treeハッシュおよびマグネットリンクを計算するオープンソースのコマンドラインツール

もう一度検索