7

私はウィキペディアでハッシュツリーについて読んでいましたが、この構造の利点や目的がわかりません。余分なハッシュをあまり使用せずに、葉ごとに1つだけよりも多くのハッシュが必要なようです。

たとえば、ウィキペディアのユースケースは、P2Pシステムで受信したデータを検証するために使用されることです。しかし、ツリー構造を持たずに、ブロック番号とそのハッシュを1対1でマッピングするよりも、なぜこれが優れているのでしょうか。

誰かがハッシュツリーがどのようにそしてなぜ有用であるかを説明してもらえますか?

前もって感謝します、

モシェ

4

1 に答える 1

11
  1. ハッシュツリーは並行して計算できます。ハッシュするデータのブロックが2つある場合は、2つのプロセッサを使用して2倍の速度でハッシュを計算できます。これは、ハッシュ速度がIO速度よりも遅い場合にのみ機能しますが、これはほとんどありません。

  2. ハッシュツリーは、個々のブロックのハッシュから、または正しく配置されたより大きなセクションのハッシュから計算できます。これは重要。

たとえば、ファイルを送信したい場合は、ファイルを1 MiBのチャンクに分割し、各チャンクをそのSHA-256ハッシュとともに送信できます。個々のチャンクのいずれかのハッシュが正しくない場合は、そのチャンクを再度要求できます。最後に、ファイルのツリーハッシュに署名して、署名されたハッシュを送信します。各ブロックハッシュ(すでに検証済み)をハッシュするだけでハッシュを検証できます。これは、ファイル全体を再ハッシュするよりもはるかに高速です。

なぜツリーハッシュを使用するのですか?

ツリーハッシュは、ファイルの一部とファイル全体の両方のハッシュを計算する場合に有利です。SHA-256のような通常のハッシュを使用すると、ファイルチャンクとファイル全体を別々にハッシュする必要があります。ファイルが8GiBの場合、これにはかなりの時間がかかる場合があります。ツリーハッシュでは、チャンクのハッシュがファイルのハッシュの計算に使用されるため、両方のハッシュを計算するために余分な作業は必要ありません。

ツリーハッシュはどのくらい余分な作業ですか?

ツリーハッシュを計算するための「余分な作業」は実際には最小限です。はい、追加のハッシュを計算する必要がありますが、O(1)の追加作業のみが必要です。ブロックサイズが1MiBの場合、ファイルが1 MiB以下であれば、余分な作業はほぼゼロです。データサイズが大きくなると、追加の作業量は、データのブロックごとに2つのハッシュの1つの追加ハッシュに近づきます。SHA-256の場合、コアは最大で1 MiBのデータごとに2回だけ追加で評価されます(1回入力ハッシュ、1回はパディング用)。それほど大したことではない。

于 2012-11-12T01:53:09.027 に答える