<p>Edit: Have a look at <a href="https://developer.bitcoin.org/reference/p2p_networking.html#merkleblock" rel="nofollow noreferrer">MSG_MERKLEBLOCK</a>. Included information is: <code>Block Header</code>, <code>Transaction Count</code>, <code>Hash Count</code>, <code>hashes</code>, <code>flag byte count</code>, and <code>flags</code>.</p>
<p><code>hashes</code> include everything from the leaf to root, and <code>flags</code>
gives the positions of the leaf in the Merkle tree.</p>
<p>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.</p>
<p>(Old answer below.)</p>
<hr />
<p>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.</p>
<p>If a transaction does not have a partner, it is paired with itself instead.</p>
<pre><code>    HASH(Hash(AB)Hash(CC))
       /              \
Hash(AB)              HASH(CC)
 /    \                /    \
A      B              C      -

Legend: A,B,C are txid; Hash is short for SHA-256d.
</code></pre>
<p>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:</p>
<pre><code>A: 00
B: 01
C: 10
</code></pre>
<p>Reading from back to front, each <code>1</code> stands for &quot;right position&quot; and each <code>0</code> stands for &quot;left position&quot;.</p>
<p>Example: <code>B(01)</code>, <code>B</code>’s last position is <code>1</code> and B is the right partner to <code>A</code>. <code>B</code>’s second to last position is <code>0</code> and HASH(AB) is the left partner to HASH(CC).</p>
<p>Therefore it is sufficient to add the index in the transaction list and the number of transactions in the block to your proposed &quot;Leaf, Root, Nodes&quot;.</p>
<p>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.</p>

CC BY-SA 4.0
2016-01-15T11:59:33.803Z
2024-03-04T10:15:42.747Z
2024-03-04T10:15:42.747Z
Murch
<p>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.</p>

<p>So in this example:</p>

<p><a href="https://i.sstatic.net/BkXEl.png" rel="noreferrer"><img src="https://i.sstatic.net/BkXEl.png" alt="enter image description here"></a></p>

<p>I would state</p>

<pre><code>Leaf: 12c5
Root: 2f9c
Nodes: [d187, a8b5, 1328, d063]
</code></pre>

<p>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.</p>

<p>I'm wondering - is there a canonical way of listing this information to create the merkle branches?</p>

CC BY-SA 3.0
2016-01-12T01:11:41.913Z
Yes - the index of the transaction, when converted to binary, implies the sequence of left/right children in the path from the root.
Nayuki
CC BY-SA 3.0
2017-08-30T16:22:52.327Z
Your question was featured in [a talk by Sean Seefried](https://www.youtube.com/watch?t=22m42s&v=6VyQMsYUrz8)
Janus Troelsen
<merkle-tree><standard>
What is the canonical way of creating merkle tree branches?
ThePiachu
# What is the canonical way of creating merkle tree branches?

(Asked by: username_0 on 2016-01-11)

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](https://i.sstatic.net/BkXEl.png)](https://i.sstatic.net/BkXEl.png)

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?

**Tags:** merkle-tree, standard

> **Comments:**
> **username_1**: Yes - the index of the transaction, when converted to binary, implies the sequence of left/right children in the path from the root.  
> **username_2**: Your question was featured in [a talk by Sean Seefried](https://www.youtube.com/watch?t=22m42s&v=6VyQMsYUrz8)  

---

## 1 answers

### Answer by username_3 on 2016-01-15. Score: 2

Edit: Have a look at [MSG\_MERKLEBLOCK](https://developer.bitcoin.org/reference/p2p_networking.html#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.


---

