This question already has an answer here:

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.

marked as duplicate by MCCCS, Raghav Sood, Anonymous, chytrik, Andrew Chow Oct 3 at 17:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • It's not a duplicate. Merkle path and Merkle tree are not the same thing. – Boon Sep 27 at 17:17
  • This one answers your question: bitcoin.stackexchange.com/questions/50674/… – MCCCS Sep 28 at 4:03
  • I read through the link, it doesn't explain how merkle path is derived. – Boon Oct 4 at 15:37

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.

  • How do you find the leaf node with that hash? Depth first search? – Boon Sep 27 at 12:52
  • 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. – Andrew Chow Sep 27 at 13:39
  • 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 Oct 4 at 15:40
  • 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. – Andrew Chow Oct 5 at 22:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.