6
$\begingroup$

Wikipedia says about a Merkle tree:

Nodes further up in the tree are the hashes of their respective children. Usually, a cryptographic hash function such as SHA-2 or SHA-3 is used for the hashing.

A cryptographic hash function can be defined using a 1-way compression function. Can we use a 1-way compression function for hashing children? It seems more efficient. We don't do length padding. For every node there is 1 less computation of a compression function.

In Merkle hash torrent extension of BitTorrent and in TTH (Russian version describing Tiger Tree Hashing) they use hash functions, not compression functions. I did not find data on AICH of eMule. What about other tree hash functions (I don't know such; maybe, you know)?

$\endgroup$
1
  • 2
    $\begingroup$ In principle you can use compression functions if you know what you're doing. But the devil is in the details. Skein and Blake2 only pad to a full block, never adding an additional compression. $\endgroup$ Aug 12, 2014 at 16:07

2 Answers 2

1
$\begingroup$

In a Merkle Tree, data is eventually and inevitably lost, because it is compressed away. If a Merkle Tree used a non-padded compression function, the size of the resulting hashes would go down level by level, resulting in a top hash that is very short. The shorter that top hash is, the less it CAN say about the contents of its tree. The longer the resulting hashes in a Merkle Tree are, the more unique the tree is, and the better it expresses its data. In addition, if the results of the compression functions are not standard (i.e. dependent on tree level), than it is very hard from a developer perspective to create software that can work for any and all sizes of Merkle Tree. In short, a non-padded compression function would destroy the "uniqueness" of a tree, and be harder from a developer perspective (keeping the top hash of a long enough size to preserve data)

$\endgroup$
1
$\begingroup$

It depends on what properties the compression function has, which in turn depends on how the hash function was constructed.

In hash functions based on the Merkle–Damgård construction, the compression function is required to be collision, preimage and second preimage resistant, just like the hash function itself. The only difference is input length: the compression function has a constant input size.

Since Merkle trees require preimage and second preimage resistance, a compression function from a Merkle–Damgård hash (e.g. SHA-2) of the correct size should be secure.

For other kinds of hash functions, you need to look at what preimage resistance is claimed for the compression function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.