user114274: 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.

user208: 
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.

114274: <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>
 208: <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>
