4
$\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$
2
  • $\begingroup$ Are your sure this is the Merkle-Tree also known as the Hash tree. $\endgroup$
    – kelalaka
    Jul 31, 2020 at 18:50
  • $\begingroup$ @kelalaka yes, both are variants of Merkle-Trees $\endgroup$
    – Alko
    Aug 3, 2020 at 8:25

3 Answers 3

3
$\begingroup$

Further expanding on @Paul Etscheit, sorting the hash pairs simplifies the verification of merkle proofs.

Example: The open zeppelin merkle proof verification smart contract, requires the hash pairs to be sorted. This is made even clearer when you look at their tests.

Merkle inclusion proofs can be verified through a function function verify(bytes[] proof, bytes root, bytes leaf). The function will return true if root is equal to the root computed from the leaf and proof nodes.

Using sorted hash pairs means your merkle proof does not needs to contain information about the order in which the child hashes should be combined in. i.e. Your proof can simply be an array of hashes.

For example:

Using merkletreejs and the following merkle tree:

└─ 7075152d03a5cd92104887b476862778ec0c87be5c2fa1c0a90f87c49fad6eff
   ├─ e5a01fee14e0ed5c48714f22180f25ad8365b53f9779f79dc4a3d7e93963f94a
   │  ├─ ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb
   │  └─ 3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d
   └─ 2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6
      └─ 2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6

Without sorting the hashpairs you need to use .getProof(<node>), which returns a proof of the form:

[
  {
    position: 'right',
    data: <Buffer 3e 23 e8 16 00 39 59 4a 33 89 4f 65 64 e1 b1 34 8b bd 7a 00 88 d4 2c 4a cb 73 ee ae d5 9c 00 9d>
  },
  {
    position: 'right',
    data: <Buffer 2e 7d 2c 03 a9 50 7a e2 65 ec f5 b5 35 68 85 a5 33 93 a2 02 9d 24 13 94 99 72 65 a1 a2 5a ef c6>
  }
]

When you sort the hashpairs, you can use .getHexProof(<node>), which returns a proof of the form:

[
  '0x3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d',
  '0x2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6'
]
$\endgroup$
2
$\begingroup$

A bit late to the party, but the second approach can be useful to simplify the merkle-path. When hashing a pair, it's required to know if the leaf is on the left or right side of the pair. This can become quite complex, for example, when implementing multi-leaf inclusion proofs. By sorting the pairs before hashing, it doesn't matter which side the leaf actually has in the pair, as you're applying the same rule every time. Pretty neat solution in my opinion.

$\endgroup$
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$
2
  • $\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, 2020 at 9:35
  • $\begingroup$ I think Amazon QLDB uses this approach. $\endgroup$
    – Alko
    Jul 29, 2020 at 9:42

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.