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 - is there a canonical way of listing this information to create the merkle branches?

Answer 1

Edit: Have a look at MSG_MERKLEBLOCK. Included information is: Block Header, Transaction Count, Hash Count, hashes, flag byte count, and flags.

hashes include everything from the leaf to root, and flags gives the positions of the leaf in the Merkle tree.

Since the index of the transaction gives it’s position from the left among the leaves in the Merkle Tree, in addition to the transaction count it is sufficient to deduce whether it is the left or right partner in each concatenation.

(Old answer below.)

---

The leaves of the Merkle tree are left to right in the same order as the transaction list of the block. Each layer above is formed by concatenating the children and then performing ad double SHA-256. When only a single entry is left in a layer, we call that the Merkle root.

If a transaction does not have a partner, it is paired with itself instead.

    HASH(Hash(AB)Hash(CC))
       /              \
Hash(AB)              HASH(CC)
 /    \                /    \
A      B              C      -

Legend: A,B,C are txid; Hash is short for SHA-256d.

This means that each transaction’s position in the tree is completely defined just by it’s index in the transaction list. Therefore, the position of its partners on each layer is deductible from that alone: If you write the transaction indices (starting to count with 0) out in Binary, you get the following:

A: 00
B: 01
C: 10

Reading from back to front, each 1 stands for "right position" and each 0 stands for "left position".

Example: B(01), B’s last position is 1 and B is the right partner to A. B’s second to last position is 0 and HASH(AB) is the left partner to HASH(CC).

Therefore it is sufficient to add the index in the transaction list and the number of transactions in the block to your proposed "Leaf, Root, Nodes".

Unfortunately, I don’t know what standard is being used to transfer this information. Maybe you can find it in the Bitcoin Core code catering to the requests of the SPV clients polling nodes for information.