# What is the canonical way of creating Merkle tree branches?

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?

• Do you mean specifically in Bitcoin or in general? – mikeazo Jan 11 '16 at 20:23
• @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. – ThePiachu Jan 11 '16 at 22:51
• Given the rest of that information, the verifier can compute the alleged Merkle root on its own. ​ ​ – user991 Jan 12 '16 at 9:04
• 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. – CodesInChaos Jan 12 '16 at 13:26

## 2 Answers

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.

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