ハッシュ木

ウィキペディアから無料の百科事典

バイナリハッシュ木の例

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

用途[編集]

ハッシュ木は、単独または複数のコンピュータで保存・処理・転送される任意のデータの検証処理に利用できる。現在の主な用途としては、Peer to Peerネットワークにおいて他のピアから受信したデータブロックが破損したり改竄されたりしていないか、あるいは他のピアが偽のデータブロックを送信していないかといった検証処理が挙げられる。また、ハッシュ木をTrusted Computingで使用するという提案もなされている。具体的な利用例としては、サン・マイクロシステムズがZFSにハッシュ木を使用している[1]。他にも、ハッシュ木はApache Waveプロトコル[2]、分散バージョン管理システムGit、バックアップシステムTahoe-LAFS、BitcoinのPeer to Peerネットワーク、Apache CassandraおよびRiakのようなNoSQLシステム[3]で使用されている。

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

動作原理[編集]

ハッシュ木はノードにハッシュ値を持つ二分木であり、葉の部分にはデータブロック（ファイルや、ファイルを分割したものなど）のハッシュ値が入っている。葉より上位のノードにはそれぞれの子ノードのハッシュ値が入っている。例えば、上図において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ハッシュ（Tiger Tree Hash, TTH）は、広く使用されているハッシュ木の形式の一つである。二分木であり、データブロックのサイズは1024バイト、ハッシュ関数には暗号学的に安全なTigerハッシュを使用している。

Tiger TreeハッシュはGnutella, Gnutella2, and Direct ConnectといったP2Pファイル共有プロトコルや、Phex, BearShare, LimeWire, Shareaza, DCPlusPlus DC++[5], Valknut.[要出典]といったファイル共有アプリケーションで使用されている。

参考文献[編集]

  1. ^ Jeff Bonwick's Blog ZFS End-to-End Data Integrity
  2. ^ Google Wave Federation Protocol Wave Protocol Verification Paper
  3. ^ "When a replica is down for an extended period of time, or the machine storing hinted handoffs for an unavailable replica goes down as well, replicas must synchronize from one-another. In this case, Cassandra and Riak implement a Dynamo-inspired process called anti-entropy. In anti-entropy, replicas exchange Merkle Trees to identify parts of their replicated key ranges which are out of sync. A Merkle tree is a hierarchical hash verification: if the hash over the entire keyspace is not the same between two replicas, they will exchange hashes of smaller and smaller portions of the replicated keyspace until the out-of-sync keys are identified. This approach reduces unnecessary data transfer between replicas which contain mostly similar data." http://www.aosabook.org/en/nosql.html
  4. ^ R. C. Merkle, A digital signature based on a conventional encryption function, Crypto '87
  5. ^ "DC++'s feature list"

関連項目[編集]

外部リンク[編集]

「https://ja.wikipedia.org/w/index.php?title=ハッシュ木&oldid=96619553」から取得