Given the standard Merkle Tree as shown Wikipedia. I am having a hard time understanding why Hash(Hash(Leaf A)|| Hash(Leaf B)) at the parent of A and B is advantageous over just Hash(Leaf A) || Hash(Leaf B). I understand that a hash can't be any more collision resistant than it's input, so why can't we just return the concatenation as opposed to double hashing again? Is it just to make the result a fixed size again?


The benefit of the Merkle Tree is that you store only one element, the top hash. You don't need to store any other elements to verify the data. The hash of each element is in the chain to the top hash.

In your proposal, if one needs to get A, then you return Hash(Leaf A) || Hash(Leaf B). But, wait; how one can verify it by the top hash. To verify we need to store Hash(Leaf A) || Hash(Leaf B). So there will be many elements to store. Thus, if you stick the Merkles' idea you will have the benefit.

For the comments;

  • The layer of hashing is necessary since we can store only one element the top hash and we can return only the intended element since the elements are on the leaf level we only need to transfer the requested leaf and path the root hash.

  • Some purposes: Memory verifications against fault attacks. Also, storing files on the cloud. This will prevent the rollback attack, i.e. an attacker replaces the old version of a file. The Merkle Tree enables detection with negligible false acceptance.

  • $\begingroup$ Ok I see that the concatenation requires more storage but why could you just use the XOR of Hash(Leaf A) and Hash(Leaf B)? A 256 bit value XOR a 256 bit value is still 256 bits. How is this worse than Hashing them again? $\endgroup$
    – knowads
    May 9 '19 at 20:38
  • 1
    $\begingroup$ What if the elements are the same? then we will see the hash of 0. Also, with $\oplus$ one can play the order of elements. $\endgroup$
    – kelalaka
    May 9 '19 at 20:47
  • $\begingroup$ @knowads: XOR would be insecure, as anyone could generate an authentication path 'proving' anything they want (by selecting the appropriate value in the authentication path they provide) $\endgroup$
    – poncho
    May 9 '19 at 20:58

In the Merkle tree idea, the internal node combination function is more like Hash( X || Y ), where X and Y are the values of the child nodes.

The idea is that you can prove that X is the value you originally committed to by displaying only Y (and in an $n$ level tree, only $n$ values).

The complication that comes in is where we might not want to reveal leaf nodes other than the one we're showing; the straight-forward implementation of the above idea would require us to reveal the value of the leaf adjacent to the one we're proving.

To get around this, we hash each leaf node first, and then supply those hashes to the Merkle tree. So, one way to express this is that the bottom level is Hash( Hash(X) || Hash(Y) ); that way, to give the authentication path, we show Hash(Y) and not the actual Y value.

This initial hash only applies to the bottom (leaf) nodes; everything else can be done simpler (because we don't care if someone learns the value of intermediate Merkle nodes)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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