Loading article…
暗号学およびコンピュータ科学において、ハッシュツリーまたはマークルツリーとは、すべての「葉」ノードにデータブロックの暗号学的ハッシュがラベル付けされ、葉ではないすべてのノード（ブランチ、インナーノード、またはinodeと呼ばれる）にはその子ノードのラベルの暗号学的ハッシュがラベル付けされたツリーのことです。ハッシュツリーを使用すると、大規模なデータ構造の内容を効率的かつ安全に検証できます。ハッシュツリーは、ハッシュリストとハッシュチェーンの一般化です。
葉ノードが特定のバイナリハッシュツリーの一部であることを証明するには、ツリー内の葉ノードの数の対数に比例する数のハッシュを計算する必要があります。 [ 1 ]逆に、ハッシュリストでは、その数は葉ノードの数自体に比例します。したがって、マークルツリーは、ツリーのルートがコミットメントと見なされ、葉ノードが元のコミットメントの一部であることが明らかになり証明される暗号コミットメントスキームの効率的な例です。[ 2 ]
ハッシュツリーの概念は、1979年に特許を取得したラルフ・マークルにちなんで名付けられました。 [ 3 ] [ 4 ]
ハッシュツリーは、コンピュータ内およびコンピュータ間で保存、処理、転送されるあらゆる種類のデータの検証に使用できます。ピアツーピアネットワークにおいて、他のピアから受信したデータブロックが破損や改ざんされていないことを保証し、さらには他のピアが嘘をついて偽のブロックを送信していないことを確認するのに役立ちます。
ハッシュツリーは以下のような用途で使用されます。
信頼できるコンピューティングシステムではハッシュツリーを使用するという提案がなされている。[ 14 ]
ハッシュツリーとは、ハッシュのツリーであり、その葉（つまり、葉ノード、または「葉」とも呼ばれる）は、例えばファイルやファイルセット内のデータブロックのハッシュです。ツリーの上位にあるノードは、それぞれの子ノードのハッシュです。例えば、上の図では、ハッシュ 0は、ハッシュ 0-0とハッシュ 0-1を連結したものをハッシュした結果です。つまり、ハッシュ 0 =ハッシュ(ハッシュ 0-0 +ハッシュ 0-1 ) であり、「+」は連結を表します。
ほとんどのハッシュツリーの実装はバイナリ（各ノードの下に2つの子ノードを持つ）ですが、各ノードの下にさらに多くの子ノードを使用することも可能です。
通常、ハッシュ化にはSHA-2などの暗号学的ハッシュ関数が使用されます。ハッシュツリーが意図しない損傷を防ぐだけであれば、CRCなどの非暗号学的チェックサムを使用できます。
ハッシュツリーの最上位には、トップハッシュ（またはルートハッシュ、マスターハッシュ）があります。P2Pネットワークでファイルをダウンロードする前に、ほとんどの場合、トップハッシュは信頼できるソース（たとえば、友人やダウンロードするファイルの推奨が優れていることで知られるWebサイト）から取得されます。トップハッシュが利用可能になると、ハッシュツリーはP2Pネットワーク内の任意のピアなど、信頼できないソースから受信できます。次に、受信したハッシュツリーは信頼できるトップハッシュと照合され、ハッシュツリーが破損しているか偽物である場合は、プログラムがトップハッシュに一致するハッシュツリーを見つけるまで、別のソースからの別のハッシュツリーが試されます。[ 15 ]
ハッシュリストとの主な違いは、ハッシュツリーでは一度に1つのブランチをダウンロードでき、ツリー全体がまだ利用できない場合でも、各ブランチの整合性を即座にチェックできる点です。たとえば、図では、データブロックL2をハッシュ化し、その結果をハッシュ0-0とハッシュ1に繰り返し結合し、最後にその結果をトップハッシュと比較することで、ツリーにハッシュ0-0とハッシュ1が既に含まれていれば、データブロックL2の整合性を即座に検証できます。同様に、ツリーにハッシュ1-1とハッシュ0が既に含まれていれば、データブロックL3の整合性を検証できます。これは、ファイルを非常に小さなデータブロックに分割することで、破損した場合に再ダウンロードする必要があるブロックが小さくなるため、効率的です。ハッシュ化されたファイルが大きい場合、このようなハッシュリストやハッシュチェーンはかなり大きくなります。しかし、ツリーであれば、小さなブランチを1つずつ素早くダウンロードし、ブランチの整合性をチェックしてから、データブロックのダウンロードを開始できます。
Merkleハッシュルートはツリーの深さを示さないため、攻撃者が元のドキュメントとは異なる、同じMerkleハッシュルートを持つドキュメントを作成する第2原像攻撃が可能になります。上記の例では、攻撃者は2つのデータブロックを含む新しいドキュメントを作成できます。最初のデータはハッシュ0-0 +ハッシュ0-1、2番目のデータはハッシュ1-0 +ハッシュ1-1です。[ 16 ] [ 17 ]
証明書の透明性では、簡単な解決策が定義されています。リーフノードのハッシュを計算する際には、ハッシュデータに0x00バイトが追加され、内部ノードのハッシュを計算する際には0x01バイトが追加されます。[ 15 ]ハッシュツリーのサイズを制限することは、いくつかの正式なセキュリティ証明 の前提条件であり、いくつかの証明をより厳密にするのに役立ちます。一部の実装では、ハッシュの前にハッシュツリーの深さプレフィックスを使用してツリーの深さを制限するため、抽出されたハッシュチェーンは、プレフィックスが各ステップで減少し、リーフに到達したときにまだ正である場合にのみ有効であると定義されます。
タイガーツリーハッシュは、広く使われているハッシュツリーの一種です。バイナリハッシュツリー（各ノードの下に2つの子ノード）を使用し、通常は1024バイトのデータブロックサイズを持ち、タイガーハッシュを使用します。[ 18 ]
Tiger Tree ハッシュは、Gnutella [ 19 ] 、Gnutella2、 Direct Connect P2Pファイル共有プロトコル[ 20 ]、およびPhex [ 21 ]、BearShare、LimeWire、Shareaza、DC++ [ 22 ]、gtk-gnutella [ 23 ]などのファイル共有アプリケーションで使用されています。
レプリカが長期間ダウンした場合、または利用できないレプリカのヒントハンドオフを保存しているマシンもダウンした場合、レプリカは互いに同期する必要があります。この場合、Cassandra と Riak は Dynamo にヒントを得たアンチエントロピーと呼ばれるプロセスを実装します。アンチエントロピーでは、レプリカはマークルツリーを交換して、同期していない複製キー範囲の部分を特定します。マークルツリーは階層的なハッシュ検証です。キースペース全体のハッシュが 2 つのレプリカ間で同じでない場合、同期していないキーが特定されるまで、複製キースペースのより小さな部分のハッシュを交換します。このアプローチにより、ほとんど同じデータを含むレプリカ間の不要なデータ転送が削減されます。
{{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)