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?
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.
H( H(H(A)+H(B)) + H(H(C)+H(D)) ), ie the root hash, don't you need the leaf nodes anyhow?
$\endgroup$
Commented
Feb 19, 2018 at 5:02
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$
+to denote addition, or xor, or concatenation? $\endgroup$