What is the purpose of using different hash functions for the leaves and internals of a hash tree? I just learned that the THEX hash tree specification which is widely used in P2P requires that two different hash functions be used: one for the leaf nodes (hashes of input data) and one for the internal hashes (hashes of hashes).


  In order to protect against collisions between leaf hashes and
  internal hashes, different hash constructs are used to hash the leaf
  nodes and the internal nodes. The same hash algorithm is used as the
  basis of each construct, but a single '1' byte in network byte order,
  or 0x01 is prepended to the input of the internal node hashes, and a
  single '0' byte, or 0x00 is prepended to the input of the leaf node
  hashes.


By contrast, the proposed (though not yet widely adopted) Simple Merkle Hashes extension for BitTorrent just uses unmodified SHA-1 for all hashes. It's conceivable that this was a trade-off of security for simplicity, but that wasn't mentioned in the proposal.

What is the benefit of using two different hashes in this scheme?
If the same standard hash function was used for both leaves and branch nodes, it would be easy to generate collisions and even second preimages.

For example, let $M$ be a message which is longer than the segment size of the hash tree, but (for simplicity) no more than two segments long. Then the hash value of $M$ is calculated as $$H(M) = H_I(H_L(M_0) \,\|\, H_L(M_1)),$$ where $H_I$ is the internal hash function, $H_L$ is the leaf hash function, and $M_0$ and $M_1$ are the first and second segments of $M$.  We'll also assume that the segment size of the hash tree is at least twice as long as the length of the output of $H_L$.

Now let $M&#39; = H_L(M_0) \,\|\, H_L(M_1)$.  Since $M&#39;$ is, by assumption, at most one segment long, its hash will be calculated as $$H(M&#39;) = H_L(M&#39;) = H_L(H_L(M_0) \,\|\, H_L(M_1)).$$  If $H_L = H_I$, then $H(M&#39;) = H(M)$, and we've just found a second preimage for $H(M)$.