I'm currently looking into creating some compact Merkle tree branches to prove that a given hash was included in a given Merkle root. My initial thought was to list the leaf, the Merkle root and all of the hashes that the given leaf was combined with to make the Merkle root.

So in this example:

enter image description here

I would state

Leaf:  12c5
Root:  2f9c
Nodes: [d187, a8b5, 1328, d063]

However, since the order of nodes matter for creating the Merkle root, I would also need to list whether the node was on the left or right side.

I'm wondering if is there a canonical way of listing this information to create the Merkle branches?

  • $\begingroup$ Do you mean specifically in Bitcoin or in general? $\endgroup$
    – mikeazo
    Jan 11 '16 at 20:23
  • $\begingroup$ @mikeazo In general - I'm not sure how often merkle branches are used outside of Bitcoin, but if there is some canonical way of handling them in cryptography, it could be applied to Bitcoin as well. $\endgroup$
    – ThePiachu
    Jan 11 '16 at 22:51
  • $\begingroup$ Given the rest of that information, the verifier can compute the alleged Merkle root on its own. ​ ​ $\endgroup$
    – user991
    Jan 12 '16 at 9:04
  • $\begingroup$ That depends on how you construct and balance the tree. For simple trees the size determines the structure and you'd only need to give the index of the leaf node to know which path leads to the root. $\endgroup$ Jan 12 '16 at 13:26

If you have the index of the leaf, it describes the path from it to the root.

Specifically, the binary representation is a series of left (0) and right (1) turns from the root. If you're working your way up, the least significant bit says if the leaf is a left (0) or right (1) child, the next bit refers to the leaf's parent, etc.

This illustration makes it obvious:

Merkle tree example

The numbers on each node are the binary representation of that node's index in its layer.

So just listing the index of the leaf whose membership is being proven provides enough information to validate the proof.

Here's some simple pseudocode for validating a proof:

func isValidProof(leaf, index, nodes, root):
  currentNode = leaf
  for node in nodes:
    if index mod 2 == 0:
      currentNode = hash(currentNode, node)
      currentNode = hash(node, currentNode)
    index = index >> 1 // shift 1 right is essentially like dividing by 2, ignoring the remainder
  return currentNode == root

Not sure about a canonical way, but a simple way of doing this is to use an extra byte to encode a "left" or a "right" next to the each node's hash in the proof.

So rather than:

Leaf:  12c5
Nodes: [d187, a8b5, 1328, d063]

Instead do:

Leaf:  12c5
Nodes: [left|d187, right|a8b5, left|1328, right|d063]

To save some space, you might want to use a single bit and send the "directions" separately:

Leaf:  12c5
Nodes: [d187, a8b5, 1328, d063]
Dirs:  [0,    1,    0,    1]

This works great if the depth of the tree is a multiple of 8. Otherwise, you'd need some padding.


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.