3

I understand what the merkle root is for. And I understand that blocks don't store the merkle tree.

Question 1) Is there any place that the complete merkle trees get stored? I don't mean the merkle root hashes since I know they are in the block headers.

Question 2) Let's say a full node starts proving to a light node that a specific transaction is in Block J. How does the full node send the merkle branch to the light node? Does it loop through the transactions again to get the hashes and then sends the interior node hashes of transactions, or do full nodes already have the complete merkle tree (whole tree and each internal hash) stored somewhere?

Improve this question

1 Answer 1

Reset to default
3

Bitcoin Core, in its BIP37 implementation, will compute the Merkle proofs on the fly. It does not store the blocks' Merkle trees anywhere (only its root is stored).

Improve this answer
3
  • 1
    Thank you Pieter. I wanna add someting. merkle roots are used to reduce operations from n to logn . Looks like for full node, operation count is still n. it gets reduced to logn for light nodes since full node only sends a path of merkle tree instead of the whole merkle tree. do you agree to all i've just said ?
    – Nika Kurashvili
    Oct 9, 2020 at 5:10
  • any comments about my last reply ? Thanks in advance.
    – Nika Kurashvili
    Oct 9, 2020 at 17:01
  • @Nika That's correct, though it's really the only option. BIP37 uses Bloom filters to select which transactions are interesting, which isn't something we can build an index for fast lookup for. As a result, the node answering must go through the entire block anyway to determine even which transactions are interesting to the client. Building the Merkle tree and responding with the paths of matching transaction is a minor cost compared to that.
    – Pieter Wuille
    Oct 9, 2020 at 17:08

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.