3
$\begingroup$

I am implementing a Merkle tree and am considering using either of the two options.

The first one is sorting only by leaves. This one makes sense to me since you would like to have the same input every time you are constructing a tree from the data, that might not arrive sorted by default.

       CAB
      /    \
     CA     \
   /    \    \
  C     A     B
/  \  /  \  /  \
1  2  3  4  5  6

The second one is sorting by leaves and pairs, which means that after sorting the leaves, you also sort all the pairs after hashing them, however I'm not entirely sure about the benefits of this implementation (if any).

       ACB
      /    \
     AC     \
   /    \    \
  C     A     B
/  \  /  \  /  \
1  2  3  4  5  6

I have seen these implementations of Merkle trees in the past but am not sure about their benefits. So why choose one over the other?

$\endgroup$
  • $\begingroup$ Are your sure this is the Merkle-Tree also known as the Hash tree. $\endgroup$ – kelalaka Jul 31 '20 at 18:50
  • $\begingroup$ @kelalaka yes, both are variants of Merkle-Trees $\endgroup$ – Alko Aug 3 '20 at 8:25
1
$\begingroup$

The first method is the standard one that I've seen.

I'm not clear on what the purpose of the second method would be, or even exactly how it works. It's not something I've seen before.

I'd suggest you use the first method by default, and if you encounter a situation where it is insufficient or has some problems, post a question asking about the specific requirements you have in that situation.

$\endgroup$
  • $\begingroup$ Hey, thanks. The difference is that instead of just the leaves it also sorts the node hash pairs, before hashing them. The purpouse of using this method is also unclear to me. $\endgroup$ – Alko Jul 29 '20 at 9:35
  • $\begingroup$ I think Amazon QLDB uses this approach. $\endgroup$ – Alko Jul 29 '20 at 9:42

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.