0

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.

4

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.

1
  • Thanks again Pieter! Understood. Should have realised that merkle-proofs is self-explanatory, for providing 'Proof' that a txn exists in a merkle tree. Jun 16 at 2:18
-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 (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 Full nodes from the same paper presentation Stateless nodes

8
  • 1
    Sorry, I downvoted. I find this incomprehensible. Jun 15 at 18:11
  • 2
    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
    Jun 15 at 18:58
  • 1
    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. Jun 15 at 23:41
  • 2
    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. Jun 16 at 15:05
  • 1
    @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
    Jun 16 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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