Merkle Root and Merkle Proofs This is one of those questions that everyone seems to write about but the same bad explanations are just plagiarized from site to site.



Edit: The heart of my question is why Merkle trees are claimed to be efficient when determining if a leaf node is present or tampered with when only the root node hash and a leaf node hash value is known and when the Merkle hashes are not cached somewhere (which they appear not to be in the case of Bitcoin's transactions stored in a block)... I so far see only claims of efficiency not any credible demonstrations or explanations of same. The whole point, I understand, of the Merkle "proof" is that the hashes are stored and then the binary feature of the Merkle tree can be leveraged to "walk the tree" from leaf to root with only a fraction of hash calculations required; without the cached hashes, I submit that all hashes in the entire tree would need to be recalculated, as I explain below...



I understand how to build Merkle trees. What I don't understand are two key points about Merkle trees and one key point about Bitcoin's Merkle trees for transactions. For the sake of my questions below, consider this cited Merkle tree from investopedia.com:



Merkle Trees in General

People say that given the Merkle root hash and the hash to H(D), you can quickly determine: 

A. Whether the H(D) leaf is in the Merkle tree. 

B. Whether the H(D) leaf has been tampered with or whether it changed positions. 

With respect to A: 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?

With respect to B: If you have the H(D) hash value and you know that its leaf pair is H(C), you can calculate H(CD). But at that point, if H(D) has changed and you know the old value for H(CD), wouldn't you immediately be able to short-circuit your investigation because the new H(CD) value would not equal the old H(CD) value? If you say to me that you don't have the old H(CD) value then I would ask you: How do I get the value to H(AB) then? It would seem that I need to recalculate the hash for H(AB). And if that's true, I also would need to recalculate the hash to H(EFGH), which means recalculating the entire right half of the Merkle tree starting at the leaf nodes. There isn't much efficiency in that.

My final 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? Where exactly and how exactly does it store this information? All I ever see is the Merkle root in the block... 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... 

Thanks!
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:

A Bitcoin full node who has full blocks.
A Bitcoin thin node who has headers but wants to verify that a transaction is in one of the full blocks.
(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:

computes h = SHA256(H), verifies the proof-of-work in h and checks the timestamp in H, etc.
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.)
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).
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:

The full node has all the blocks, including the interior node hashes computed in Step 3 above.
The thin node has all block headers. Recall that each header includes the Merkle root.
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 &quot;under&quot; 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 &quot;lie&quot; about any transaction &quot;under&quot; 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 &quot;you&quot; and &quot;I.&quot; &quot;Prover&quot; and &quot;verifier&quot; can be terse and boring, but is precise.
The thin node cannot &quot;just look at the list of leaf hashes&quot; 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 =&gt; 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 &quot;Yes, because it would be a waste of space to store interior node hashes in the blocks.&quot; but reading closer I don't actually know what you mean by &quot;Merkle value for a transaction node&quot; and &quot;metadata related to non-tree Merkle nodes.&quot;
Hope this helps!