<p>Given a merkle tree and a transaction that is in that tree, to find the path from the root to that transaction, first hash the transaction. Then find the leaf node in the merkle tree with that hash. Add that node to a list. Take the parent of that node. Add that node to the list. Take it's parent, add it to the list. So on and so forth until you reach the merkle root (which can be identified as the node with no parent). The list of nodes is the path.</p>

<p>If you also need the other node each node was hashed with so you can construct a merkle proof, for every node, when you go to it's parent node, see which side the node you came from was on and record it. And then record the hash of the node on the other side and the side it was on.</p>

CC BY-SA 4.0
2018-09-27T12:52:32.120Z
How do you find the leaf node with that hash? Depth first search?
Boon
CC BY-SA 4.0
2018-09-27T13:39:41.537Z
If you have the tree, you do a depth first search. That will also give you the path to the merkle root. However, usually you don't have the merkle tree. Rather you construct it from a list of transactions. So you search the list for the transaction you want and remember it when you construct the tree so you know where to start.
Ava Chow
CC BY-SA 4.0
2018-10-04T15:40:38.357Z
I thought SPV node doesn't have the full transactions, only the Merkle root. Or how would it search the list for the transaction?
Boon
CC BY-SA 4.0
2018-10-05T22:37:09.547Z
SPV nodes don't search for transactions in the merkle tree. Rather they receive from a node the path through the merkle tree to their transaction so that there is proof that a transaction exists in a block.
Ava Chow
CC BY-SA 4.0
2018-09-27T03:56:53.193Z
2018-09-27T03:56:53.193Z
Ava Chow
<p>How is Merkle path calculated? I am looking for a detailed algorithm rather than a quick one liner for this so I can implement it.</p>

<p>Note that this is not the same as computing Merkle root or building Merkle tree. Also not asking why Merkle path is needed. I did not find any info on this site going over the algorithm for deriving Merkle path.</p>

CC BY-SA 4.0
2018-09-27T17:17:54.470Z
It's not a duplicate. Merkle path and Merkle tree are not the same thing.
Boon
CC BY-SA 4.0
2018-09-28T04:03:39.340Z
This one answers your question: https://bitcoin.stackexchange.com/questions/50674/why-is-the-full-merkle-path-needed-to-verify-a-transaction
MCCCS
CC BY-SA 4.0
2018-10-04T15:37:40.623Z
I read through the link, it doesn't explain how merkle path is derived.
Boon
<bitcoin-core><merkle-tree>
How is Merkle path derived or calculated?
Boon
# How is Merkle path derived or calculated?

(Asked by: username_0 on 2018-09-26)

How is Merkle path calculated? I am looking for a detailed algorithm rather than a quick one liner for this so I can implement it.

Note that this is not the same as computing Merkle root or building Merkle tree. Also not asking why Merkle path is needed. I did not find any info on this site going over the algorithm for deriving Merkle path.

**Tags:** bitcoin-core, merkle-tree

> **Comments:**
> **username_0**: It's not a duplicate. Merkle path and Merkle tree are not the same thing.  
> **username_1**: This one answers your question: https://bitcoin.stackexchange.com/questions/50674/why-is-the-full-merkle-path-needed-to-verify-a-transaction  
> **username_0**: I read through the link, it doesn't explain how merkle path is derived.  

---

## 1 answers

### Answer by username_2 on 2018-09-27. Score: 0

Given a merkle tree and a transaction that is in that tree, to find the path from the root to that transaction, first hash the transaction. Then find the leaf node in the merkle tree with that hash. Add that node to a list. Take the parent of that node. Add that node to the list. Take it's parent, add it to the list. So on and so forth until you reach the merkle root (which can be identified as the node with no parent). The list of nodes is the path.

If you also need the other node each node was hashed with so you can construct a merkle proof, for every node, when you go to it's parent node, see which side the node you came from was on and record it. And then record the hash of the node on the other side and the side it was on.

> **Comments:**
> **username_0**: How do you find the leaf node with that hash? Depth first search?  
> **username_2**: If you have the tree, you do a depth first search. That will also give you the path to the merkle root. However, usually you don't have the merkle tree. Rather you construct it from a list of transactions. So you search the list for the transaction you want and remember it when you construct the tree so you know where to start.  
> **username_0**: I thought SPV node doesn't have the full transactions, only the Merkle root. Or how would it search the list for the transaction?  
> **username_2**: SPV nodes don't search for transactions in the merkle tree. Rather they receive from a node the path through the merkle tree to their transaction so that there is proof that a transaction exists in a block.  

---

