ハッシュ木
ハッシュ木はノードにハッシュ値を持つ二分木であり、葉の部分にはデータブロック(ファイルや、ファイルを分割したものなど)のハッシュ値が入っている。葉より上位のノードにはそれぞれの子ノードのハッシュ値が入っている。例えば、上図において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ネットワークのピアなどの信頼できない情報源から取得してもよい。