Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)?

share|improve this question
2  
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. –  CodesInChaos Aug 12 at 16:07

2 Answers 2

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.

share|improve this answer

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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