暗号理論および計算機科学において、ハッシュ木(Hash tree, ハッシュツリー)またはマークル木(Merkle tree)とは、より大きなデータ（例えばファイル）の要約結果を格納する木構造の一種であり、データの検証を行う際に使用される。このデータ構造はハッシュリストとハッシュチェインの組み合わせでできており、ハッシュ法の延長上にある手法といえる。特に、ハッシュ関数にTigerを使用したものはTiger TreeまたはTiger Treeハッシュとも呼ばれる。ハッシュ木は、単独または複数のコンピュータで保存・処理・転送される任意のデータの検証処理に利用できる。現在の主な用途としては、Peer to Peerネットワークにおいて他のピアから受信したデータブロックが破損したり改竄されたりしていないか、あるいは他のピアが偽のデータブロックを送信していないかといった検証処理が挙げられる。また、ハッシュ木をTrusted Computingで使用するという提案もなされている。具体的な利用例としては、サン・マイクロシステムズがZFSにハッシュ木を使用している。他にも、ハッシュ木はApache Waveプロトコル、分散バージョン管理システムGit、バックアップシステムTahoe-LAFS、BitcoinのPeer to Peerネットワーク、Apache CassandraおよびRiakのようなNoSQLシステムで使用されている。ハッシュ木は1979年にラルフ・マークルによって発明された。元々の目的は大量のランポート署名を効率的に処理することであった。ランポート署名は量子コンピュータが実現してもなお安全性を保つことができると言われているが、ひとつの鍵は一つのメッセージの署名にしか使用できないという制約がある。ここで、ランポート署名をハッシュ木と組み合わせると、ひとつの鍵を複数のメッセージに対して使用できるようになり、効率的なデジタル署名スキームを構築することができる。ハッシュ木はノードにハッシュ値を持つ二分木であり、葉の部分にはデータブロック（ファイルや、ファイルを分割したものなど）のハッシュ値が入っている。葉より上位のノードにはそれぞれの子ノードのハッシュ値が入っている。例えば、上図において"hash 0"には、"hash 0-0"と"hash 0-1"とを結合した結果のハッシュ値が入っている。つまり、"hash 0 = hash(hash 0-0 || hash 0-1)"となっている（ここで||は文字列結合の意味）。多くのハッシュ木の実装は二分木（各ノードが高々2つの子ノードを持つ）であるが、各ノードがそれより多くの子ノードを持つようにもできる。通常、ハッシュ関数にはSHA-1, Whirlpool, Tigerといった暗号学的ハッシュ関数が使用される。なお、意図しないデータ破損に対する保護だけを目的にハッシュ木を使用する場合であれば、CRCなどのよりセキュリティの低いチェックサムを使用してもよい。ハッシュ木のルートには、"トップハッシュ"(top hash)（あるいは"ルートハッシュ"(root hash), "マスターハッシュ"(master hash)）が格納される。P2Pネットワークにおいてファイルのダウンロードを開始する前には、信頼できる情報源（例えば友人や、トップハッシュのダウンロード用に推奨されているウェブサイトなど）からトップハッシュを取得するようになっている場合が多い。トップハッシュさえ利用可能になっていれば、ハッシュ木そのものはどこから取得してもよく、例えばP2Pネットワークのピアなどの信頼できない情報源から取得してもよい。次に、信頼できるトップハッシュを使って、取得したハッシュ木の検査を行い、ハッシュ木が破損していたり偽物だったりした場合は別の情報源からハッシュ木を取得する。プログラムはトップハッシュによる検査が合格するまでこれを繰り返せばよい。ハッシュリストとの主な違いは、ハッシュ木の一部の枝だけをダウンロードでき、またハッシュ木の全体が利用可能でなくても枝の完全性を検査することができるという点にある。例えば、上図の"data block 001"の完全性を検査するには、ハッシュ木に"hash 0-0"と"hash 1"さえ含まれていればよい（"data block 001"のハッシュ値と"hash 0-0"の値を組み合わせ、次に"hash 1"の値と組み合わせればトップハッシュの値と比較が行える）。同様に、"data block 002"の完全性を検査するには"hash 1-1"と"hash 0"の値があればよい。この特徴を利用して、ファイルを非常に小さなブロックに分割しておき、ブロックが破損していたら再ダウンロードするようにすれば効率的に処理が行える。ハッシュ化対象のファイルが非常に大きい場合、ハッシュ木やハッシュリストのサイズはそれに応じて大きくなるが、ハッシュ木なら一部の小さな枝だけをダウンロードでき、枝の完全性チェックが行え、データブロックのダウンロードをすぐに開始することができる。ハッシュ木に関するその他のテクニック、利点、詳細などについては参考文献および外部リンクを参照すること。Tiger Treeハッシュ（Tiger Tree Hash, TTH）は、広く使用されているハッシュ木の形式の一つである。二分木であり、データブロックのサイズは1024バイト、ハッシュ関数には暗号学的に安全なTigerハッシュを使用している。Tiger TreeハッシュはGnutella, Gnutella2, and Direct ConnectといったP2Pファイル共有プロトコルや、Phex, BearShare, LimeWire, Shareaza, DCPlusPlus DC++, Valknut.といったファイル共有アプリケーションで使用されている。

出典:wikipedia