Merkle Root and Merkle Proofs

Reading your question, I suspect the cause for your confusion is around the setting in which Merkle trees are used. I think you are right that in the Bitcoin world, the setting is taken for granted and is not usually explained clearly.

Here's my two cents. To understand the efficiency aspect of Merkle trees, consider the two parties that are actually involved in the protocol:

1. A Bitcoin full node who has full blocks.
2. A Bitcoin thin node who has headers but wants to verify that a transaction is in one of the full blocks.
3. (It might be worth mentioning that the current Bitcoin protocol does not allow a thin node to efficiently verify that a transaction is not in any of the blocks.)

First, recall that when receiving a new block B with block header H and transactions T, the full node does the following:

1. computes h = SHA256(H), verifies the proof-of-work in h and checks the timestamp in H, etc.
2. for each transaction t \in T, verifies t's signature(s), verifies t does not double spend, and appends t as the rightmost leaf of the current block's Merkle tree. (Recall that a different Merkle tree is computed for each block. Of course, appending the transaction has to be done in a canonical order, so as to obtain the same root hash as in the block header H.)
3. after all t \in T have been verified and appended, computes and stores the Merkle tree, of course computing all interior node hashes and the root hash r (as depicted in your Merkle tree figure).
4. Crucially, verifies that the computed root hash r equals the root hash in the block header H.

Moral of the story: Yes, you are right that to prove membership of a leaf with respect to a Merkle root r, the prover (in this case, the full node) needs the interior node hashes: he can cache them or recompute them (there's some literature on trade-offs here). (I think) Bitcoin full nodes simply cache all hashes, as detailed in Step 3. Importantly, the interior hashes are not part of the 1MB block B: it would be a waste of space, since full nodes can simply recompute them from the leafs (i.e., the TXNs) and match the recomputed root hash with the one in the block header. Note that this prevents network adversaries from tampering with the transactions.

Second, recall that when receiving a new block header H, a thin node just does step (1) from above.

Now, here's the setting in Bitcoin:

1. The full node has all the blocks, including the interior node hashes computed in Step 3 above.
2. The thin node has all block headers. Recall that each header includes the Merkle root.
3. The full node wants to convince the thin node that some transaction t is in some block B with block header H (which of course the thin node has)

Thesis: Merkle trees allow the full node to convince the thin nodes of this efficiently, preventing the full node from changing t into t' (which would allow a full node to trick a thin node into thinking it got paid).

Proof: Let r denote the Merkle root in H. The thin node has that same H and r. The full node has the interior nodes "under" r cached (recall Step 3 from the full node). The full node fetches the (already cached) sibling path starting at the leaf containing the transaction t and going all the way up to the root r, sending it to the thin node. The thin node recursively hashes up t with the received siblings, obtaining a root hash r' (hand-waving here, assuming you understand Merkle proofs). The thin node checks that r == r'.

Efficiency: The full node (i.e., prover) only has to send O(\log{n}) siblings in a Merkle tree of n leafs to the thin node (i.e., the verifier), who only has a 256-bit root hash r. (Of course, the prover needs to have all the leafs and all the interior nodes, as discussed before.)

Naturally, this protocol guarantees the full node cannot "lie" about any transaction "under" the root r. Informally, if a transaction is there, the full node cannot change it to a different transaction and forge a proof for it (i.e., a sibling path). Also informally, if a transaction is not there at all, the full node cannot forge a proof for it being there.

To answer your questions:

Question A seems to be about how membership of a transaction t works. You say,

To do this, wouldn't you just look at the list of leaf hashes to determine whether H(D) is there? Why do anything with the Merkle root?

I think you're misunderstanding the setting. Keep in mind, that when discussing cryptographic protocols, it's quite necessary to refer to the parties by name, rather than using ambiguous pronouns like "you" and "I." "Prover" and "verifier" can be terse and boring, but is precise.

The thin node cannot "just look at the list of leaf hashes" because it only has the root hash and no leafs but wants to be sure that a leaf is there. The full node could send the thin node all the leafs and have the thin node hash them, obtaining the same root hash. However, that would be inefficient: O(n) bandwidth for n leafs. In contrast, a Merkle proof for a leaf under a root hash is much more efficient: only O(\log{n}) hashes + the leaf itself.

Question B should be answered by now: the full node has all interior node hashes. It sends the sibling path to the thin node, who simply recursively hashes up from the leaf being checked. The thin node verifies the root it obtained matches the root in the block header.

Question C:

Does Bitcoin persist the Merkle tree hashes for not only the leaf nodes but for the entire tree all the way to the root?

Not in the blocks themselves: it would be a waste of space as mentioned before. Full nodes compute the interior hashes and the root hash and cache everything locally on disk (presumably, I haven't actually looked at the source code). Then, they are ready to serve proofs for any transaction in any block to any thin node.

Where exactly and how exactly does it store this information? All I ever see is the Merkle root in the block...

Presumably, on disk in the database of the full node. But not in the block: they are redundant info because blocks contains leafs => can compute hashes of interior nodes and root node.

I think I once saw a Merkle value for a transaction node but I never saw any meta data related to non-tree Merkle nodes in the Bitcoin blockchain...

Ugh, I want to say "Yes, because it would be a waste of space to store interior node hashes in the blocks." but reading closer I don't actually know what you mean by "Merkle value for a transaction node" and "metadata related to non-tree Merkle nodes."

Hope this helps!

You can get bonuses upto $100 FREE BONUS when you:
💰 Install these recommended apps:
💲 SocialGood - 100% Crypto Back on Everyday Shopping
💲 xPortal - The DeFi For The Next Billion
💲 CryptoTab Browser - Lightweight, fast, and ready to mine!
💰 Register on these recommended exchanges:
🟡 Binance🟡 Bitfinex🟡 Bitmart🟡 Bittrex🟡 Bitget
🟡 CoinEx🟡 Crypto.com🟡 Gate.io🟡 Huobi🟡 Kucoin.