I was learning about Merkle trees and understood that if A, B, C and D are the leaf nodes, then their parents will be H(H(A)+H(B) and H(H(C)+H(D)) rsp. and the root will be H( H(H(A)+H(B)) + H(H(C)+H(D)) ). What if instead of this, the parents of the leaf node were: H(A+B) and H(C+D) and the root be H(A+B+C+D)?

I intuitively know this may not be a good choice but can someone explain it in a better way?

  • 2
    $\begingroup$ Are you using + to denote addition, or xor, or concatenation? $\endgroup$
    – Mikero
    Feb 18, 2018 at 17:39
  • $\begingroup$ @Mikero You can take + to be anything you want, addition or xor. Concatenation wouldn't make any sense I guess?? $\endgroup$ Feb 18, 2018 at 17:54

1 Answer 1


If + means concatenation, then $H(A+B+C+D)$ doesn't help make verification easier. You still need all leaves in order to verify any leaf, whereas the point of Merkle tree is to be able to verify individual leaves with only logarithmic cost.

If + means XOR or addition, then $H(A+B+C+D)$ is not collision-resistant so the construction fails to authenticate the leaves.

  • $\begingroup$ But in order to calculate H( H(H(A)+H(B)) + H(H(C)+H(D)) ), ie the root hash, don't you need the leaf nodes anyhow? $\endgroup$ Feb 19, 2018 at 5:02
  • 1
    $\begingroup$ @SwapnilPandey say you want me to prove that I included C in the tree. With your approach, I need to give you A, B, and D. With a Merkle tree, only H(H(A)+H(B)), and H(D) are needed. The difference is small in this example, because there is a small number of leaf nodes, but for a tree with $n$ levels (here $n = 3$), you only need to provide $n-1$ pieces of data (all being short hashes), instead of all of the $2^{n-1}-1$ leaves in the tree, all being potentially very long. $\endgroup$
    – Maya
    Feb 19, 2018 at 16:06

Your Answer

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

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