How do you get Sibling Hashed Values in a Merkle Proof?

Question

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?

Answer 1

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.