# Can we use a Merkle Tree structure to reduce digest size?

A 2nd preimage attack is possible on the standard Merkle tree as pictured below. I'm aware that we can add identifiers (to differentiate nodes) to the input of each hash as discussed in the link. If then using a good hash function, it should be resistant to any kind of attacks.

However it would be preferable to have a tree structure where a change in L1 (even if it hashed to Hash0-0) would affect Hash0.

If such a tree structure is viable, it seems we could use it to reduce the digest size used, without necessarily reducing security to the same degree.

That is, if it is difficult to find a pre-image collision in a secure 256 bit digest with a 256 bit input, is it just as difficult to find a pre-image collision in a 128 bit digest when the 256 bit input is constrained by being used further up the tree?

To use a rubbish hash as an example. For MD5, it may be possible to find a pre-image collision for X. Is it harder if I ask you to find an input that hashes to X, where the input must also be used to create another pre-image collision at the parent/grandparent of X?

To illustrate my idea, see a simple example of what I imagine below. Everything except the red blocks would be 128 bit. 'Split & XOR' is splitting the 256 bit DATA block into two 128bit blocks and XORing them together. The aim being that the attacker (after seeing DATA0 and relevant auth path) cannot simply provide an alternative DATA1, as it will also need to 'Split & XOR' to create the correct parent block. The idea is the attacker is left to find the real 256 bits of DATA1, not just a pre-image for the 128 bits of HASH1.

Questions

1. Is this a viable idea?
2. Is such an idea (obviously not as rudimentary as mines) employed anywhere?

The problem is that your construction (the whole second picture) still constitutes a compressing function with 128bit output. Hence, we can find collisions at complexity about $$t\cdot2^{64}$$, where t is the runtime of your construction.