0

Merkle Proofs are one of the main reasons that people attribute Bitcoin's use of Merkle Trees. But I'm struggling to understand how these work in practice. Please explain theoretically as well as practically.

Given that Lightweight Nodes only store Block Headers to limit the storage needed for their copies of the BlockChain, Nodes don't have access to the transactions in a Block; by definition of a Block Header, the only info they have about transactions is the Merkle Root.

But the Merkle Root is not enough to prove a transaction is in a block. All the sibling-values up the Merkle Tree are needed. Where do these values come from if they aren't already stored?

Example. Node 1 has a Block on its Blockchain with Merkle Root = H_ABC...P. It wishes to see if H_K is in the block. To do so, it needs the values H_L; H_IJK; H_MNOP; H_ABC..H. Where and how does it get these?

enter image description here

3
  • Given that Nodes only store Block Headers to limit the storage needed for their copies of the BlockChain This is incorrect. Nodes store the entire block. Aug 16, 2018 at 19:34
  • Corrected the question to specify Lightweight Nodes
    – 3mrsh
    Aug 16, 2018 at 20:04
  • They will ask a full node Aug 16, 2018 at 20:12

1 Answer 1

2

But the Merkle Root is not enough to prove a transaction is in a block. All the sibling-values up the Merkle Tree are needed. Where do these values come from if they aren't already stored?

Any full node that has a complete copy of the block can construct a merkle proof that proves a requested transaction identifier (txid) connects to the merkle root in a block header. Here's an animated graphic showing how Bitcoin Core constructs a merkle proof:

For the txid (H5) for transaction 5, a list of hashes necessary to make the proof plus is created along with a list of flags telling the software evaluating the proof which side of each branch the would find the hash.

The lightweight client evaluating the proof uses those flags and hashes to prove the txid connects to the merkle root like this:

For more information, you may wish to read about the peer-to-peer network protocol message merkleblock in the BtcInformation.org Developer Reference, which includes these illustrations.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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