4
$\begingroup$

I was reading the following on Wikipedia, it appears that the leaf nodes are hashed. What are the benefits of this? Why is it done?. I fell like they are done so that they can be transferred securely. However, I am not sure about this, would like some points to resources

$\endgroup$
1
  • 1
    $\begingroup$ Why the downvote? Any explanation? A downvote must indicate the reason so that we can see our mistakes and correct it or even delete the answer! $\endgroup$
    – kelalaka
    Mar 1 at 20:37
2
$\begingroup$

If you only send the root and the Merkle tree is just used for parallel hashing then it doesn't matter how the tree is written down. The algorithm works even if you have the intermediate nodes describe $\operatorname{hash}(L1) | \operatorname{hash}(L2)$ instead of $\operatorname{hash}_1 | \operatorname{hash}_2$ as they are fully equivalent. In the end only the root (and possibly the tree configuration) need to be known by the verifying party.

You can also use the Merkle tree to quickly change the root hash if one of the elements changes, without having to re-hash the entire message. In that case you need to have the hash of the element present in the tree. So in that case at least the leaf hashes need to be communicated (although communicating the entire tree avoids recalculation). If you'd combine hashes then you'd have to hash two elements - basically removing a level.

$\endgroup$
4
  • $\begingroup$ This is how I always understood it, so I decided to write it down; please shoot it out of existence if my understanding is flawed (comments appreciated if you do so). $\endgroup$
    – Maarten Bodewes
    Feb 27 at 11:40
  • $\begingroup$ Are you saying you committed to the root of the argument, and then revealed the leaves as you typed it? =) $\endgroup$
    – Cort Ammon
    Feb 27 at 16:40
  • 2
    $\begingroup$ This seems mostly correct, but note that one must be careful with the handling of leaf nodes in a Merkle tree to avoid introducing trivial second preimage attacks. Such attacks can happen e.g. if an attacker can construct a tree with leaf node that is identical to a non-leaf node in a larger tree; see e.g. my answer to a related question for more details (and also another similar question). Your notation above looks vague enough to me that it neither implies nor excludes the possibility of such attacks. $\endgroup$ Feb 28 at 2:02
  • $\begingroup$ My brain is hurting to figure out all the possible attack scenarios that would lead to the attack that Ilmari has described, most specifically for the second part. I don't think it changes my answer though, but an additional warning might be in order. $\endgroup$
    – Maarten Bodewes
    Feb 28 at 11:30
4
$\begingroup$

Merkle Tree is based on hashing to the root to provide an efficient digital signature. If the leaves just contain a single data then the parents cannot contain the hash of both children and the combined hash in a simple node design. This can complicate the structure and programming so that the last parents must contain the hash of their children and their combined hashes, too.

You can design like that, however, it will not simple as the Merkle tree. For example, as pointed on the patent, you can design a Merkle tree trinary tree too.

This is rather an efficiency issue, not a security issue if the hash chain still has the countermeasure to prevent the second pre-image attack with the prefixes.

$\endgroup$
1
  • $\begingroup$ Why the downvote? $\endgroup$
    – kelalaka
    Mar 1 at 20:30

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.