<p>In order to verify if a transaction is part of a merkle tree, you have to calculate the hash of the transaction id and it's sibling, and verify that the value is correct. For example,</p>

<h2>Merkle Verification</h2>

<p>We’ll start with a simple 2 leaf example (see the <a href="https://www.blockchain.com/en/btc/block/00000000d1145790a8694403d4063f323d499e655c83426834d4ce2f8dd4a2ee" rel="nofollow noreferrer">First Bitcoin Transaction</a>):</p>

<p><a href="https://i.sstatic.net/U5vD7.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/U5vD7.png" alt="2 leaf merkle tree"></a></p>

<p>Lets assume that hashes <code>Ha</code> and <code>Hb</code> have already been calculated from the data <code>Ta</code> and <code>Tb</code> and that:</p>

<pre><code>Ha = b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082
Hb = f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16
</code></pre>

<p>First, we must reverse the bytes (they need to be little endian) because that is how Bitcoin calculates the hashes. You can use this python script, if you like:</p>

<pre><code>#!/usr/bin/env python
line = raw_input("Input original hex string\n")
n = 2
orig_list = [line[i:i+n] for i in range(0, len(line), n)]
reversed_list = orig_list[::-1]
reversed = ''.join(reversed_list)
print reversed
</code></pre>

<p>We get:</p>

<pre><code>Ha = 82501c1178fa0b222c1f3d474ec726b832013f0a532b44bb620cce8624a5feb1
Hb = 169e1e83e930853391bc6f35f605c6754cfead57cf8387639d3b4096c54f18f4
</code></pre>

<p>Then, the node (and root in this case) <code>Hab</code> is calculated by concatenating the two and hashing with sha256 twice (i.e. hash256):</p>

<pre><code>$ printf "82501c1178fa0b222c1f3d474ec726b832013f0a532b44bb620cce8624a5feb1169e1e83e930853391bc6f35f605c6754cfead57cf8387639d3b4096c54f18f4" | xxd -r -p | openssl sha256
(stdin)= a24ee7fb7333f85c16560ed8850a1773d6977ce7a4936367eaf72f8fff33797e
$ printf "a24ee7fb7333f85c16560ed8850a1773d6977ce7a4936367eaf72f8fff33797e" | xxd -r -p | openssl sha256
(stdin)= ff104ccb05421ab93e63f8c3ce5c2c2e9dbb37de2764b3a3175c8166562cac7d
</code></pre>

<p>Now, reverse the bytes! (back to big endian):</p>

<pre><code>7dac2c5666815c17a3b36427de37bb9d2e2c5ccec3f8633eb91a4205cb4c10ff
</code></pre>

<p><a href="https://medium.com/coinmonks/how-to-manually-verify-the-merkle-root-of-a-bitcoin-block-command-line-7881397d4db1" rel="nofollow noreferrer">https://medium.com/coinmonks/how-to-manually-verify-the-merkle-root-of-a-bitcoin-block-command-line-7881397d4db1</a></p>

CC BY-SA 4.0
2019-11-18T17:39:43.813Z
I think he asked about how to find transaction knowing root hash not how to create the merkle tree.
K.Sopheak
CC BY-SA 4.0
2018-11-20T16:12:58.913Z
2018-11-20T16:12:58.913Z
JBaczuk
<p>To search for a transaction in a merkle root, one must know the TXID of the transaction being looked for. It's not possible to search for leaves (transaction IDs) that satisfy a complex pattern [without scanning each of the transactions]. After the TXID and the TXIDs of other transactions in that block are acquired, the tree is traversed by hashing (For details, please see <a href="https://bitcoin.stackexchange.com/questions/50674/why-is-the-full-merkle-path-needed-to-verify-a-transaction">Why is the full Merkle path needed to verify a transaction?</a>) The transaction is proved to be a part of the block if the final hash is equal to the merkle root.</p>

CC BY-SA 4.0
2018-11-20T16:13:20.227Z
2018-11-20T16:13:20.227Z
MCCCS
<p>A common misconception is that a Merkle tree is a data structure which makes finding elements in it easier. It does not. While it does have a tree structure, it is not a search tree like a B-tree or Red-Black or Patricia tree.</p>

<p>As far as searching for data goes, it is conceptually just a list (the leaves of the tree) with a number of associated hash values. Searching in it is exactly as hard as searching in a list is. If the list is sorted, that can be done in O(log n) time, but if the list is not sorted, you need to do an O(n) exhaustive search.</p>

<p>So what is a Merkle tree then useful for?</p>

<p>Proofs. A Merkle tree lets one party <em>prove</em> that a particular element is in it, to anyone who knows the tree's root hash.</p>

<p>So in practice the answer to "How do I find something in a Merkle tree?" is "You don't. You let someone else search for you, and have them show you a proof of what they found.".</p>

CC BY-SA 4.0
2018-11-20T16:24:45.883Z
2018-11-20T16:24:45.883Z
Pieter Wuille
<p>If you want to keep a proof that your transaction was included in a particular block, you need to create and save the proof yourself. To create the proof you need to get a copy of the block and using the transaction ids in the block you compute the path from your transaction to the merkel root. The path would be an array of hash outputs along with the side one which to hash it. If a block had 1000 transaction the path to the merkel root would only have about 10 hash outputs.</p>

<p>The user needs to save their own proof that the transaction was included in a block. You cannot query the network for that. You can query to see if the merkel root is correct.</p>

CC BY-SA 4.0
2020-03-22T18:26:41.280Z
2020-03-22T18:26:41.280Z
Omar
<p>We know the merkel tree is branchs of transaction hash so that root of tree is hash that show in block header. If i want to find a specific transaction, how i can?</p>

CC BY-SA 4.0
2018-11-20T15:04:44.607Z
What do you mean by "special transaction"? Can you be more specific?
Ava Chow
CC BY-SA 4.0
2018-11-20T15:07:46.297Z
Transactions that for example send to Alice address .
R_Jalaei
CC BY-SA 4.0
2018-11-20T15:11:54.403Z
Are you asking how to find a specific transaction?
JBaczuk
CC BY-SA 4.0
2018-11-20T15:17:37.780Z
Yes. How To check if a transaction is included in the Merkle tree ?
R_Jalaei
<transactions>
Find specific transaction in merkel's tree
R_Jalaei
# Find specific transaction in merkel's tree

(Asked by: username_0 on 2018-11-20)

We know the merkel tree is branchs of transaction hash so that root of tree is hash that show in block header. If i want to find a specific transaction, how i can?

**Tags:** transactions

> **Comments:**
> **username_1**: What do you mean by "special transaction"? Can you be more specific?  
> **username_0**: Transactions that for example send to Alice address .  
> **username_2**: Are you asking how to find a specific transaction?  
> **username_0**: Yes. How To check if a transaction is included in the Merkle tree ?  

---

## 4 answers

### Answer by username_2 on 2018-11-20. Score: 1

In order to verify if a transaction is part of a merkle tree, you have to calculate the hash of the transaction id and it's sibling, and verify that the value is correct. For example,
Merkle Verification
We’ll start with a simple 2 leaf example (see the First Bitcoin Transaction):

Lets assume that hashes Ha and Hb have already been calculated from the data Ta and Tb and that:
Ha = b1fea52486ce0c62bb442b530a3f0132b826c74e473d1f2c220bfa78111c5082
Hb = f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16

First, we must reverse the bytes (they need to be little endian) because that is how Bitcoin calculates the hashes. You can use this python script, if you like:
#!/usr/bin/env python
line = raw_input("Input original hex string\n")
n = 2
orig_list = [line[i:i+n] for i in range(0, len(line), n)]
reversed_list = orig_list[::-1]
reversed = ''.join(reversed_list)
print reversed

We get:
Ha = 82501c1178fa0b222c1f3d474ec726b832013f0a532b44bb620cce8624a5feb1
Hb = 169e1e83e930853391bc6f35f605c6754cfead57cf8387639d3b4096c54f18f4

Then, the node (and root in this case) Hab is calculated by concatenating the two and hashing with sha256 twice (i.e. hash256):
$ printf "82501c1178fa0b222c1f3d474ec726b832013f0a532b44bb620cce8624a5feb1169e1e83e930853391bc6f35f605c6754cfead57cf8387639d3b4096c54f18f4" | xxd -r -p | openssl sha256
(stdin)= a24ee7fb7333f85c16560ed8850a1773d6977ce7a4936367eaf72f8fff33797e
$ printf "a24ee7fb7333f85c16560ed8850a1773d6977ce7a4936367eaf72f8fff33797e" | xxd -r -p | openssl sha256
(stdin)= ff104ccb05421ab93e63f8c3ce5c2c2e9dbb37de2764b3a3175c8166562cac7d

Now, reverse the bytes! (back to big endian):
7dac2c5666815c17a3b36427de37bb9d2e2c5ccec3f8633eb91a4205cb4c10ff

https://medium.com/coinmonks/how-to-manually-verify-the-merkle-root-of-a-bitcoin-block-command-line-7881397d4db1

> **Comments:**
> **username_3**: I think he asked about how to find transaction knowing root hash not how to create the merkle tree.  

---

### Answer by username_4 on 2018-11-20. Score: 1

To search for a transaction in a merkle root, one must know the TXID of the transaction being looked for. It's not possible to search for leaves (transaction IDs) that satisfy a complex pattern [without scanning each of the transactions]. After the TXID and the TXIDs of other transactions in that block are acquired, the tree is traversed by hashing (For details, please see [Why is the full Merkle path needed to verify a transaction?](https://bitcoin.stackexchange.com/questions/50674/why-is-the-full-merkle-path-needed-to-verify-a-transaction)) The transaction is proved to be a part of the block if the final hash is equal to the merkle root.


---

### Answer by username_5 on 2018-11-20. Score: 1

A common misconception is that a Merkle tree is a data structure which makes finding elements in it easier. It does not. While it does have a tree structure, it is not a search tree like a B-tree or Red-Black or Patricia tree.

As far as searching for data goes, it is conceptually just a list (the leaves of the tree) with a number of associated hash values. Searching in it is exactly as hard as searching in a list is. If the list is sorted, that can be done in O(log n) time, but if the list is not sorted, you need to do an O(n) exhaustive search.

So what is a Merkle tree then useful for?

Proofs. A Merkle tree lets one party *prove* that a particular element is in it, to anyone who knows the tree's root hash.

So in practice the answer to "How do I find something in a Merkle tree?" is "You don't. You let someone else search for you, and have them show you a proof of what they found.".


---

### Answer by username_6 on 2020-03-22. Score: 0

If you want to keep a proof that your transaction was included in a particular block, you need to create and save the proof yourself. To create the proof you need to get a copy of the block and using the transaction ids in the block you compute the path from your transaction to the merkel root. The path would be an array of hash outputs along with the side one which to hash it. If a block had 1000 transaction the path to the merkel root would only have about 10 hash outputs.

The user needs to save their own proof that the transaction was included in a block. You cannot query the network for that. You can query to see if the merkel root is correct.


---

