What is the canonical way of creating Merkle tree branches?

Question

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:

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?

Answer 1

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:

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)
    else:
      currentNode = hash(node, currentNode)
    index = index >> 1 // shift 1 right is essentially like dividing by 2, ignoring the remainder
  return currentNode == root

Answer 2

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.