<p>Still roughly answering &amp; hoping I can clarify the vague area:</p>
<p>1-Witnesses or proofs r used by stateless nodes not full nodes ( their use in full nodes is a future work of the Utreexo project). Stateless nodes r something bet full &amp; lite nodes which doesn't store the whole Merkle Tree just the proofs it needs</p>
<p>2-I think the checking-verifying doesn't work as u wrote...</p>
<ul>
<li>if u noticed in block explorer, u press the numeric value of the UTXO to know where it came from
-So the transaction contains the position of the UTXO in the database, I think, which is linked to the position of it's hash as a leaf node in the Merkle Tree.
.
3-Now u reached the UTXO hash, and u do have the accumulated hash of all existing UTXOs( the root value), u go upward (not downward) from the leaf to the root to know if this leaf hash is correct. This is done by getting all the sibling hashes along the way to extract the leaf from the root and compare both values.
-Those is why it's better to have a tree structure, to get only O(log n) sibling values if the tree is balanced.</li>
</ul>
<p>I think these images may help explain it more
<img src="https://i.sstatic.net/2Ebq0.jpg" alt="To verify the green value HL given the root value, u need to get all the blue values. They're called siblings as they're in the same level of the tree as the UTXO u r verifying, or the upward Internal node in its path" />
(To verify the green value HL given the root value, u need to get all the blue values. They're called siblings as they're in the same level of the tree as the UTXO u r verifying, or the upward Internal node in its path)</p>
<p>Original text from the paper <a href="https://youtu.be/HEKtDILPeaI" rel="nofollow noreferrer">https://youtu.be/HEKtDILPeaI</a>
<img src="https://i.sstatic.net/s1y3W.jpg" alt="text from the paper https://youtu.be/HEKtDILPeaI" />
<img src="https://i.sstatic.net/yaGGy.jpg" alt="Full nodes from the same paper presentation" />
<img src="https://i.sstatic.net/abGQA.jpg" alt="Stateless nodes" /></p>

CC BY-SA 4.0
2021-06-15T18:11:58.683Z
Sorry, I downvoted. I find this incomprehensible.
Pieter Wuille
CC BY-SA 4.0
2021-06-15T18:35:57.327Z
I said it's a rough quick answer
ShAr
CC BY-SA 4.0
2021-06-15T18:46:46.973Z
I mean it doesn't annoy me if someone had a better answer to help the person who asked, but it does annoy me when someone downgrade a Q without answering it ... u do not promote the transfer of knowledge & science this way
ShAr
CC BY-SA 4.0
2021-06-15T18:58:11.720Z
Putting dots on the empty lines breaks your formatting and makes your posts difficult to read. Please use proper words instead of chat lingo like "u" and "r" and make sure that your sentences are grammatically sound.
Murch
CC BY-SA 4.0
2021-06-15T23:39:19.117Z
That's a "meta-group" topic, but I don't think an answerer should have the right to downvote a competing answer, or a Q without answering, answers should be arranged/voted according to correctness for the "came to know & understand" asker. I don't think the "style of writing" is more important than what is written. I came here to find answers which I didn't; when tried to volunteer to help others in same situation by answering what I can, got a "repelling attitude"
ShAr
CC BY-SA 4.0
2021-06-15T23:41:24.273Z
Ok, I've withdrawn my downvote to avoid the impression of a conflict of interest. My intention isn't to criticize; I feel this answer is too hard to read to understand and that makes it a bad answer, and I feel like I owe an explanation when I downvote someone, so the answer can be improved. Style is only one aspect of this.
Pieter Wuille
CC BY-SA 4.0
2021-06-16T15:05:52.937Z
For what it is worth, I also couldn't understand the answer and downvoted. From what I did understand I thought it was answering a question not posed by the asker. The downvote is there for this purpose. However, I am also happy to withdraw my downvote if you feel it is discouraging.
Michael Folkson
CC BY-SA 4.0
2021-06-16T21:30:43.463Z
@ShAr: I'm sorry that you felt that you got a hostile reception. Our community's goal is to build an archive of useful content. Posts that are clear and comprehensive are more expedient to that end than posts that are hard to read or miss the topic. We use upvotes and downvotes to direct our users' and our readers' attention at the content we consider the most useful. Downvotes can generally be avoided by investing a reasonable amount of attentiveness to the form of posts.
Murch
CC BY-SA 4.0
2021-06-15T17:20:53.420Z
2021-06-15T23:29:38.290Z
2021-06-15T23:29:38.290Z
ShAr
<blockquote>
<p>My assumption is that when transaction proof of inclusion occurs</p>
</blockquote>
<p>Which proofs of inclusions are you talking about? The only ones I'm aware of in the Bitcoin P2P protocol are those in BIP37 (server side Bloom filtering of transactions). There are other uses though (e.g. utreexo), but you'll need to be specific.</p>
<blockquote>
<p>it takes place only at full nodes, since this may happen when a block is mined (as a node has to evict transactions from its mempool to make sure the same txns aren't added in their candidate block) and when someone queries a block explorer and the full nodes hold all the transactions (needed for merkle proofs). Is this true?</p>
</blockquote>
<p>Block explorers have nothing to do with inclusion proofs. They just search their database for the transaction. They don't need any proof, because they run their own node, so they know the transactions they have were included - if they weren't, they wouldn't have been entered into their database.</p>
<blockquote>
<p>In these cases then, wouldn't it be quicker to just search through the transactions for a match instead of doing merkle proofs?</p>
</blockquote>
<p>Merkle proofs are only used when one party needs to prove to another that a transaction was included in a block. They are not involved in block explorers at all, as they're just showing users data - nothing is being proven.</p>
<blockquote>
<p>How does a node know which block a TX is in?</p>
</blockquote>
<p>Normal Bitcoin P2P nodes don't, and have no need for this. The protocol supports querying for unconfirmed transactions that were recently relayed (so they're not in a block yet), and supports querying by block. With BIP37 (which is increasingly being abandoned due to bad privacy and DoS risks) it is/was possible to first tell a node which addresses/scripts/transactions you were interested in by sending a Bloom filter, and then ask for &quot;filtered&quot; blocks - blocks with irrelevant transactions removed, and replaced with inclusion proofs for the remaining ones.</p>
<blockquote>
<p>The transaction data doesn't contain what block it is in, so does a node start scanning the chain downwards?</p>
</blockquote>
<p>At least in the Bitcoin P2P protocol, this simply does not happen as it is unnecessary.</p>
<p>Outside of that, indexes are used. For local usage, Bitcoin Core can build an index that remembers which transaction was found in which block, so it can be looked up by txid. The Electrum protocol (which uses separate Electrum servers) may support querying by txid as well, and its servers need an index for that too. I believe they do also construct inclusion proofs (which are built on the fly when requested).</p>
<blockquote>
<p>When someone queries a proof-of-inclusion, a bitfield is constructed as a derivation path down to the leaf in question. For this to work, I assume that for each merkle root, is a mapping, and the associates nodes and all transactions. Doesn't this defeat the purpose of a merkle tree then, still needing to hold all information + more? So is it just to summarise the transaction data in a block header to add some more entropy to a block hash?</p>
</blockquote>
<p>It's very hard to answer this without knowing the concrete application you're talking about. In general, inclusion proofs are unrelated to the problem of finding the data - someone needs to have it, and they can use it to prove it to others.</p>
<blockquote>
<p>If only the root and leaf are known, how is a derivation path found?</p>
</blockquote>
<p>You can't. Proofs are used to prove to someone who has the root already (and trust it) that a particular leaf is in fact part of the tree that that root commits to. Obviously the party constructing the proof needs to know which leaf somehow, and the rest of the block.</p>
<blockquote>
<p>Is it so that that a light clients queries full nodes on who construct the merkle tree on the fly, providing a tree which the light client can then perform proof of inclusion?</p>
</blockquote>
<p>Yes, that's what happens in BIP37 filtered block querying, and presumably also in other protocols.</p>

CC BY-SA 4.0
2021-06-16T02:18:47.313Z
Thanks again Pieter! Understood. Should have realised that merkle-proofs is self-explanatory, for providing 'Proof' that a txn exists in a merkle tree.
Matt Tainsh
CC BY-SA 4.0
2021-06-15T18:08:27.480Z
2021-06-15T18:08:27.480Z
Pieter Wuille
<p>My assumption is that when transaction proof of inclusion occurs, it takes place only at full nodes, since this may happen when a block is mined (as a node has to evict transactions from its mempool to make sure the same txns aren't added in their candidate block) and when someone queries a block explorer and the full nodes hold all the transactions (needed for merkle proofs). Is this true?</p>
<p>In these cases then, wouldn't it be quicker to just search through the transactions for a match instead of doing merkle proofs? How does a node know which block a TX is in? The transaction data doesn't contain what block it is in, so does a node start scanning the chain downwards?</p>
<p>When someone queries a proof-of-inclusion, a bitfield is constructed as a derivation path down to the leaf in question. For this to work, I assume that for each merkle root, is a mapping, and the associates nodes and all transactions. Doesn't this defeat the purpose of a merkle tree then, still needing to hold all information + more? So is it just to summarise the transaction data in a block header to add some more entropy to a block hash?</p>
<p>If only the root and leaf are known, how is a derivation path found?</p>
<p>Is it so that that a light clients queries full nodes on who construct the merkle tree on the fly, providing a tree which the light client can then perform proof of inclusion?</p>
<p>I know I am missing something. Could someone please fill me in here? Thank you.</p>
<p>PS: Apologies for the long drawn out question.</p>

<merkle-tree>
Proof-of-inclusion: Merkle Tress, derivation paths
Matt Tainsh
# Proof-of-inclusion: Merkle Tress, derivation paths

(Asked by: username_0 on 2021-06-15)

My assumption is that when transaction proof of inclusion occurs, it takes place only at full nodes, since this may happen when a block is mined (as a node has to evict transactions from its mempool to make sure the same txns aren't added in their candidate block) and when someone queries a block explorer and the full nodes hold all the transactions (needed for merkle proofs). Is this true?

In these cases then, wouldn't it be quicker to just search through the transactions for a match instead of doing merkle proofs? How does a node know which block a TX is in? The transaction data doesn't contain what block it is in, so does a node start scanning the chain downwards?

When someone queries a proof-of-inclusion, a bitfield is constructed as a derivation path down to the leaf in question. For this to work, I assume that for each merkle root, is a mapping, and the associates nodes and all transactions. Doesn't this defeat the purpose of a merkle tree then, still needing to hold all information + more? So is it just to summarise the transaction data in a block header to add some more entropy to a block hash?

If only the root and leaf are known, how is a derivation path found?

Is it so that that a light clients queries full nodes on who construct the merkle tree on the fly, providing a tree which the light client can then perform proof of inclusion?

I know I am missing something. Could someone please fill me in here? Thank you.

PS: Apologies for the long drawn out question.

**Tags:** merkle-tree


---

## 2 answers

### Answer by username_2 on 2021-06-15. Score: 4 | Accepted answer

> My assumption is that when transaction proof of inclusion occurs

Which proofs of inclusions are you talking about? The only ones I'm aware of in the Bitcoin P2P protocol are those in BIP37 (server side Bloom filtering of transactions). There are other uses though (e.g. utreexo), but you'll need to be specific.

> it takes place only at full nodes, since this may happen when a block is mined (as a node has to evict transactions from its mempool to make sure the same txns aren't added in their candidate block) and when someone queries a block explorer and the full nodes hold all the transactions (needed for merkle proofs). Is this true?

Block explorers have nothing to do with inclusion proofs. They just search their database for the transaction. They don't need any proof, because they run their own node, so they know the transactions they have were included - if they weren't, they wouldn't have been entered into their database.

> In these cases then, wouldn't it be quicker to just search through the transactions for a match instead of doing merkle proofs?

Merkle proofs are only used when one party needs to prove to another that a transaction was included in a block. They are not involved in block explorers at all, as they're just showing users data - nothing is being proven.

> How does a node know which block a TX is in?

Normal Bitcoin P2P nodes don't, and have no need for this. The protocol supports querying for unconfirmed transactions that were recently relayed (so they're not in a block yet), and supports querying by block. With BIP37 (which is increasingly being abandoned due to bad privacy and DoS risks) it is/was possible to first tell a node which addresses/scripts/transactions you were interested in by sending a Bloom filter, and then ask for "filtered" blocks - blocks with irrelevant transactions removed, and replaced with inclusion proofs for the remaining ones.

> The transaction data doesn't contain what block it is in, so does a node start scanning the chain downwards?

At least in the Bitcoin P2P protocol, this simply does not happen as it is unnecessary.

Outside of that, indexes are used. For local usage, Bitcoin Core can build an index that remembers which transaction was found in which block, so it can be looked up by txid. The Electrum protocol (which uses separate Electrum servers) may support querying by txid as well, and its servers need an index for that too. I believe they do also construct inclusion proofs (which are built on the fly when requested).

> When someone queries a proof-of-inclusion, a bitfield is constructed as a derivation path down to the leaf in question. For this to work, I assume that for each merkle root, is a mapping, and the associates nodes and all transactions. Doesn't this defeat the purpose of a merkle tree then, still needing to hold all information + more? So is it just to summarise the transaction data in a block header to add some more entropy to a block hash?

It's very hard to answer this without knowing the concrete application you're talking about. In general, inclusion proofs are unrelated to the problem of finding the data - someone needs to have it, and they can use it to prove it to others.

> If only the root and leaf are known, how is a derivation path found?

You can't. Proofs are used to prove to someone who has the root already (and trust it) that a particular leaf is in fact part of the tree that that root commits to. Obviously the party constructing the proof needs to know which leaf somehow, and the rest of the block.

> Is it so that that a light clients queries full nodes on who construct the merkle tree on the fly, providing a tree which the light client can then perform proof of inclusion?

Yes, that's what happens in BIP37 filtered block querying, and presumably also in other protocols.

> **Comments:**
> **username_0**: Thanks again username_2! Understood. Should have realised that merkle-proofs is self-explanatory, for providing 'Proof' that a txn exists in a merkle tree.  

---

### Answer by username_1 on 2021-06-15. Score: -1

Still roughly answering & hoping I can clarify the vague area:

1-Witnesses or proofs r used by stateless nodes not full nodes ( their use in full nodes is a future work of the Utreexo project). Stateless nodes r something bet full & lite nodes which doesn't store the whole Merkle Tree just the proofs it needs

2-I think the checking-verifying doesn't work as u wrote...

* if u noticed in block explorer, u press the numeric value of the UTXO to know where it came from
  -So the transaction contains the position of the UTXO in the database, I think, which is linked to the position of it's hash as a leaf node in the Merkle Tree.
  .
  3-Now u reached the UTXO hash, and u do have the accumulated hash of all existing UTXOs( the root value), u go upward (not downward) from the leaf to the root to know if this leaf hash is correct. This is done by getting all the sibling hashes along the way to extract the leaf from the root and compare both values.
  -Those is why it's better to have a tree structure, to get only O(log n) sibling values if the tree is balanced.

I think these images may help explain it more
![To verify the green value HL given the root value, u need to get all the blue values. They're called siblings as they're in the same level of the tree as the UTXO u r verifying, or the upward Internal node in its path](https://i.sstatic.net/2Ebq0.jpg)
(To verify the green value HL given the root value, u need to get all the blue values. They're called siblings as they're in the same level of the tree as the UTXO u r verifying, or the upward Internal node in its path)

Original text from the paper <https://youtu.be/HEKtDILPeaI>
![text from the paper https://youtu.be/HEKtDILPeaI](https://i.sstatic.net/s1y3W.jpg)
![Full nodes from the same paper presentation](https://i.sstatic.net/yaGGy.jpg)
![Stateless nodes](https://i.sstatic.net/abGQA.jpg)

> **Comments:**
> **username_2**: Sorry, I downvoted. I find this incomprehensible.  
> **username_1**: I said it's a rough quick answer  
> **username_1**: I mean it doesn't annoy me if someone had a better answer to help the person who asked, but it does annoy me when someone downgrade a Q without answering it ... u do not promote the transfer of knowledge & science this way  
> **username_3**: Putting dots on the empty lines breaks your formatting and makes your posts difficult to read. Please use proper words instead of chat lingo like "u" and "r" and make sure that your sentences are grammatically sound.  
> **username_1**: That's a "meta-group" topic, but I don't think an answerer should have the right to downvote a competing answer, or a Q without answering, answers should be arranged/voted according to correctness for the "came to know & understand" asker. I don't think the "style of writing" is more important than what is written. I came here to find answers which I didn't; when tried to volunteer to help others in same situation by answering what I can, got a "repelling attitude"  
> **username_2**: Ok, I've withdrawn my downvote to avoid the impression of a conflict of interest. My intention isn't to criticize; I feel this answer is too hard to read to understand and that makes it a bad answer, and I feel like I owe an explanation when I downvote someone, so the answer can be improved. Style is only one aspect of this.  
> **username_4**: For what it is worth, I also couldn't understand the answer and downvoted. From what I did understand I thought it was answering a question not posed by the asker. The downvote is there for this purpose. However, I am also happy to withdraw my downvote if you feel it is discouraging.  
> **username_3**: @username_1: I'm sorry that you felt that you got a hostile reception. Our community's goal is to build an archive of useful content. Posts that are clear and comprehensive are more expedient to that end than posts that are hard to read or miss the topic. We use upvotes and downvotes to direct our users' and our readers' attention at the content we consider the most useful. Downvotes can generally be avoided by investing a reasonable amount of attentiveness to the form of posts.  

---

