<p>Say a block consisting of these 10 transactions, noted by their txids at indexes 0 to 9:</p>

<pre><code>E1AF205960AE338A37174B407EE71067C3CD7F04D48A5CEC7E13F6ECCB61DCBC
A314970CD7C647D1CC0A477E1A2122B98205B6924B73001B8DAB20EE81C2F4F7
B08EB9DCE0452A1B1970C4D29E88BDEE07669A2A5D1B08586D7FFA17B2E3F6B5
958B9E94AEA9A485BA494C50FB3192558057F7CAED9705D4B11369F071F10642
3D278CA01CC527D4C7D577B668E0B976FBBCB94E6A9BA89664C721F36FADA6A1
95AFFA405501498EF6F4E4B6CDDC1F1B24B9D2E534584B31A9142C453920C889
D97A21CF46FD5AFB0BF9EA4237BC4BF5C84E8B47D38D1EEE2BBEB5C0F8A1C625
AE1E670BDBF8AB984F412E6102C369AECA2CED933A1DE74712CCDA5EDAF4EE57
90E03319DDC9D48DA38AB39B2F37C0A5AF5AFC736F6FF2A9D8B8653E0FEB308D
84251842A4C0F0E188E1C2BF643EC37A1402DD86A25A9AB5004633467D16E313
</code></pre>

<p>With a merkle root that we both agree on (it's in the blockchain):</p>

<pre><code>B152ECA4364850F3424C7AC2B337D606C5CA0A3F96F1554F8DB33D2F6F130BBE
</code></pre>

<p>And say you want me to prove to you that the transaction <code>D97A21CF46FD5AFB0BF9EA4237BC4BF5C84E8B47D38D1EEE2BBEB5C0F8A1C625</code> is in this block.</p>

<p>I give you this proof :</p>

<pre><code>AE1E670BDBF8AB984F412E6102C369AECA2CED933A1DE74712CCDA5EDAF4EE57,
EFC2B3DB87FF4F00C79DFA8F732A23C0E18587A73A839B7710234583CDD03DB9,
F1B6FE8FC2AB800E6D76EE975A002D3E67A60B51A62085A07289505B8D03F149,
E827331B1FE7A2689FBC23D14CD21317C699596CBCA222182A489322ECE1FA74
</code></pre>

<p>And tell you that this transaction is at index <code>6</code>, and that this is a tree of depth <code>4</code>.</p>

<p><code>(2^4) + 6 = 22</code>, and that is <code>10110</code> in base 2.
This representation in base 2 is the path we need to take from the first txid for which we want to prove the inclusion to the root.</p>

<p>Now all you're left with is to walk the path from the txid to the root, and if proof is correct, then you should get the block's merkle root.
We start the path from right to left, so with the <code>0</code> bit of of the base 2 number (the left most 1 is not used (it is the root really)).
Since this is a <code>0</code>, we should place "our" hash (the txid) on the left side :</p>

<pre><code>hash256 D97A21CF46FD5AFB0BF9EA4237BC4BF5C84E8B47D38D1EEE2BBEB5C0F8A1C625|AE1E670BDBF8AB984F412E6102C369AECA2CED933A1DE74712CCDA5EDAF4EE57
=
066AD6D9939EC0C90B7F3B775122785BD8ACA2A2C5857205AF7E0615E9AF9796
</code></pre>

<p>The next is a <code>1</code>, "our" hash is on the right :</p>

<pre><code>hash256 EFC2B3DB87FF4F00C79DFA8F732A23C0E18587A73A839B7710234583CDD03DB9|066AD6D9939EC0C90B7F3B775122785BD8ACA2A2C5857205AF7E0615E9AF9796
=
8BE15FC2AB11EF3E079568D43B2B09ED5A5690FB13ECB1032F7AAB99238A1847
</code></pre>

<p>Next is a <code>1</code> again, so again we're on the right :</p>

<pre><code>hash256 F1B6FE8FC2AB800E6D76EE975A002D3E67A60B51A62085A07289505B8D03F149|8BE15FC2AB11EF3E079568D43B2B09ED5A5690FB13ECB1032F7AAB99238A1847
=
8D9D737B484E96EED701C4B3728AEA80AA7F2A7F57125790ED9998F9050A1BEF
</code></pre>

<p>Next is a <code>0</code>, we're on the left :</p>

<pre><code>hash256 8D9D737B484E96EED701C4B3728AEA80AA7F2A7F57125790ED9998F9050A1BEF|E827331B1FE7A2689FBC23D14CD21317C699596CBCA222182A489322ECE1FA74
=
B152ECA4364850F3424C7AC2B337D606C5CA0A3F96F1554F8DB33D2F6F130BBE
</code></pre>

<p>And this is the block's merkle root.  The proof is correct.
The txid exists in a block on chain in this specific index, and the block has the correct depth.</p>

<p>For a very large tree, the effect is even more dramatic.  The quantity of steps it takes to prove an element is in a tree is logarithmic to the size of the tree, so proof stays small.
Hopefully this is what you were asking.</p>

<p>These transactions are from block <code>0000000000000a3290f20e75860d505ce0e948a1d1d846bec7e39015d242884b</code> by the way.</p>

CC BY-SA 3.0
2018-01-22T01:42:30.267Z
I followed the above. But after you offer the proof, it's unclear where you get these values from:
AE1E670BDBF8AB984F412E6102C369AECA2CED933A1DE74712CCDA5EDAF4EE57, EFC2B3DB87FF4F00C79DFA8F732A23C0E18587A73A839B7710234583CDD03DB9,
F1B6FE8FC2AB800E6D76EE975A002D3E67A60B51A62085A07289505B8D03F149,
E827331B1FE7A2689FBC23D14CD21317C699596CBCA222182A489322ECE1FA74. According to what other people have written, the hash values for everything in the Merkle treet (OTHER THAN the Merkle root) is not stored anywhere in the blockchain...
Jazimov
CC BY-SA 3.0
2018-01-22T07:53:52.730Z
These four values correspond to the yellow elements in the tree in your example (you have a tree with depth 3, so only 3 of these yellow elements).
Anyone with the full list of transactions in a block can generate them for someone else asking to see proof that a transaction is included in some block, or when encountering such proof themselves, it is easily verifiable (only about log(n) steps) without going through the whole transaction list.
arubi
CC BY-SA 3.0
2018-01-22T13:31:37.840Z
Wrong, you cannot generate just the yellow element hashes without recomputing the entire tree and that doesn't save any computations.
Jazimov
CC BY-SA 3.0
2018-01-22T17:37:42.827Z
"My question is why Merkle trees are an efficient way for blockchains to determine whether transactions are present in the Merkle tree given the Merkle root hash value and the leaf hash value.

I don't see how it's possible to execute a Merkle proof without recalculating the entire Merkle tree."

It's not an efficient way for "blockchains" to do anything.  Merkle proofs are an efficient way to prove membership of an element in a set.
This is used by lite-wallets and their servers.  Not by the actual bitcoin protocol.
arubi
CC BY-SA 3.0
2018-01-23T12:27:49.817Z
Then what's the point of using a Merkle root? Why not just calculate a single hash from every transaction in transaction sequence? That also would generate a unique hash that detects transaction-sequence changes as well as transaction data changes. Why go with Merkle at all???
Jazimov
CC BY-SA 3.0
2018-01-23T17:44:38.830Z
Because it's very useful to be able to prove membership of a transaction in a block using only log2(tree size) hashes instead of using the entire transaction list (which is the tree size itself).  SPV has been an intended feature since the beginning, and while we're not using the same SPV talked about in the white paper, the merkle tree construction still applies.
Consider that proving a txid exists in a set of 2000~ txids will take 11 hashes using a merkle tree construction, versus the entire 2000~ transactions given in a linear list.
arubi
CC BY-SA 4.0
2019-01-06T13:40:54.503Z
How can I "ask" to full node, please check this `D97A21CF46FD5AFB0BF9EA4237BC4BF5C84E8B47D38D1EEE2BBEB5C0F8A1C625` and return 4 txid to check manually like your example? thanks
monkeyUser
CC BY-SA 4.0
2020-09-29T17:49:35.527Z
+1 for this much better answer than the accepted one...
Marcus
CC BY-SA 3.0
2018-01-21T23:34:16.803Z
2018-01-21T23:46:44.293Z
2018-01-21T23:46:44.293Z
arubi
<p>There are two kinds of efficiencies:</p>

<ol>
<li><p>Computation: Merkle tree is as efficient as any other binary search tree in terms of computation and searching.</p></li>
<li><p>Storage: This is where the magic happens. <a href="https://i.sstatic.net/we8A1.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/we8A1.jpg" alt="enter image description here"></a></p></li>
</ol>

<p>Merkle root: H<sub>ABCDEFGH</sub><br>
Hash to verify: H<sub>D</sub></p>

<p>Process:<br>
1. H<sub>CD</sub>       = Hash( H<sub>C</sub> , H<sub>D</sub>)<br>
2. H<sub>ABCD</sub>     = Hash( H<sub>CD</sub>, H<sub>AB</sub>)<br>
3. H<sub>ABCDEFGH</sub> = Hash( H<sub>ABCD</sub>, H<sub>EFGH</sub>)<br></p>

<p>In the whole process of verification of H<sub>D</sub>(of total 8), we only need to store extra 3 hashes (H<sub>C</sub>, H<sub>AB</sub>, H<sub>EFGH</sub>).</p>

<p>Storage complexity: log<sub>2</sub>n = log<sub>2</sub>8 = 3</p>

<p>When n = 1024: log<sub>2</sub>n = log<sub>2</sub>1024 = 10 <br>
When n = 1048576: log<sub>2</sub>n = log<sub>2</sub>1048576 = 20</p>

<p>In this sense, Merkle trees are efficient compared to other data structures.</p>

CC BY-SA 3.0
2018-01-28T03:49:59.240Z
2018-01-28T03:49:59.240Z
Preet
<p>For a bitcoin block to be valid, the block's header must hash to an output that is within a certain range of values (defined by the current network difficulty). </p>

<p>The merkle root is one component of the block header, so in effect the merkle root is a cryptographic commitment to the transactions included in the block. Changing any single transaction (or the order of transactions) would alter the merkle root, and thus alter the block's hash (which, by overwhelming probabilty, would make the block invalid). </p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>The leaf hashes are not explicitly contained in the block, but it is trivial for any node to verify that a given transaction is properly included in the block (and therefore included in the merkle root). This is done by hashing the transaction [in your example, H(D)], and then combing H(D) with H(C) to get H(CD), and so on, until the merkle root is reached (and found to be correct against the merkle root of the block). </p>

<p>Full node clients download the entire blockchain, and are thus capable of performing this validation on their own. 'Litewallet' clients just download the block headers, and can use simplified payment verification (SPV) to perform a cryptographic check for transaction validity in a less intensive manner. SPV involves requesting just the hashes in the relevant branch of the tree, working from the transaction in question up to the root. Any attempt by the wallet's peers to lie about the transactions/hashes in a block will result in an invalid merkle root, so it is impossible for a peer to lie and say a transaction is included in a block, when it is in fact not. </p>

<blockquote>
  <p>With respct 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?</p>
</blockquote>

<p>It is not a matter of knowing a 'new' or 'old' H(CD), there is simply <strong>the</strong> H(CD) that was an intermediate step in calculating the merkle root of the relevant block. Once the block is accepted as valid by the network, there is no ability to change a transaction in it (and thus change the higher level hashes in the tree). Changing anything would change the merkle root, and thus the block's hash, so the network would no longer accept that block as valid. </p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>Each block contains the merkle root, as well as all of the transactional data. The leaf / intermediate level hashes are not explicitly included, instead they can be calculated by nodes to verify and validate the block's transactional data. (<a href="https://en.bitcoin.it/wiki/Protocol_documentation#block" rel="nofollow noreferrer">There are some other bits of data included in a block</a>, but it is the merkle root and transaction data that is relevant to your question)</p>

<p>You may be interested in reading over <a href="https://bitcoin.stackexchange.com/questions/10479/what-is-the-merkle-root#10487">the top answers to this question</a>, they are great explanations of the function of the merkle root.</p>

CC BY-SA 3.0
2018-01-20T15:20:03.387Z
Answer appreciated but you totally missed the point of my questions. You say that "it is trivial for any node to verify that a given transaction is properly included in the block" and cite calculating H(D) hashes back to the root. But as my question articulated, you cannot calculate the Merkle root from H(D) without reconstructing the ENTIRE Merkle tree hashes. I realize this can be done, but there is no efficiency in doing that because all leaf nodes must be rehashed to calculate the root. Merkle proofs speak of the "efficiency" of the Merkle structure in proving a node exists.
Jazimov
CC BY-SA 3.0
2018-01-20T15:22:17.470Z
My issue is not that I do not understand how to create a Merkle tree and the root hash--which is what you explained--but why this structure is EFFICIENT especially if non-leaf hashes en route to the Merkle root are not retained in a Bitcoin block. Please re-read question B to see my specific example. Thanks!
Jazimov
CC BY-SA 3.0
2018-01-20T23:39:11.933Z
In that case, the ‘efficiency’ comes from being able to cryptographically commit to a huge number of transactions being in a given block. Having to include all of the txs in the header explicitly would be much less efficient. So yes, a node must perform these validating computations, but the ‘efficiency gains’ talked about do not relate to this specifically (at least as far as I’ve ever read/understood).
chytrik
CC BY-SA 3.0
2018-01-20T23:46:48.390Z
Related: Consider also that having a Merkle root in the block header (instead of an explicit list of transactions) means that a miner must perform the same computation for a block with 5 txs as a block with 500 txs. So there is no incentive for a miner to include less txs, in order to perform POW computations more quickly.
chytrik
CC BY-SA 3.0
2018-01-21T04:22:14.913Z
You're still missing my point. Read Alin Tomescu's answer in https://bitcoin.stackexchange.com/questions/48928/why-does-each-block-store-a-merkle-root. He says "Merkle roots are stored in Bitcoin block headers so as to enable efficient membership proofs for transactions in a block, which are necessary for Simple Verified Payment verification (SPV) nodes that only store block headers and not block contents" but doesn't explain. My question is about "efficient membership proofs" and you're not addressing that in any of your responses.
Jazimov
CC BY-SA 3.0
2018-01-21T05:38:39.030Z
I think I understand better now. Rather than download and hash through every transaction in the entire tree, an SPV wallet can just request the sibling hashes. So in your example, after calculating H(AB), a wallet can just request H(CD), rather than requesting T(C) and T(D) to calculate H(CD) locally. An SPV wallet can trust it has been provided with valid info as long as the Merkle root is reached. So a transaction’s membership in a block can be verified more easily than if every transaction in the block had to be hashed. The Q I linked to has a little more info on this.
chytrik
CC BY-SA 3.0
2018-01-22T22:58:53.863Z
comment to B: wouldn't SPV nodes read the six blocks from the first occurance of the tx in a block, and then with the six'th block do the final check? a peer would send the requested block with the block header and the merkle path (for the tx). The SPV node uses this path to calculate up to the block header. That is, what speeds up the verification time....
pebwindkraft
CC BY-SA 3.0
2018-01-20T06:53:04.657Z
2018-01-20T06:53:04.657Z
chytrik
<p>Let's start with understanding the fact that BlockChain(Bitcoin's ledger) is distributed across multiple nodes. So, nodes cannot trust each other as they are not managed by some trusted party. Whenever a thin node(non-miner) P request's a full node(miner) Q to verify the presence of a txn t in a block B the full node Q has to convince the node P that it(Q) is saying the truth. Merkle trees come into play here.</p>
<p>So, the thin node P has the root-hash of block B and the hash of the txn t. The one thing the full node cannot wrongly convince the thin node about the block B is its root-hash. So as proof to &quot;the full node is telling the truth about the presence of txn t in block B&quot; it also sends the hash values of the sibling nodes of the nodes in the path from the root to the txn t in the Merkle tree. The thin node then backtracks the hash values along the path from txn t to the root of the Merkle tree using the sibling's hashes sent by the full node. If the resulting root-hash is equal to the one in block B's header then the full node is telling the truth.</p>
<p>Now assume I'm a full node and I want to falsely convince a thin node that a txn t is in block B. I can simply say that I've checked all the leaf's hashes and found hash of txn t in the list. But who can tell if I'm lying. Now the leaf node might request me to send the list of txns to check the list by itself, but I can always add the txn t to the list and send over the altered list.</p>
<p>Now if the thin node asks me to provide the hash value of the parent node of the txn t so that it can verify itself by hashing txn t's sibling and t together and compare the result with the parent's hash I just sent over. Now I can just send a wrong hash value of the parent to misguide the thin node. So the thin node has to verify that this parent-hash is infact the actual hash in the Merkle tree. This process of verification is recursive until I reach a point where the parent node is the root node. This time the thin node has the hash of the parent node and can verify itself. So whenever the thin node can backtrack the root-hash to the one in the block's header the full node is not lying/misguiding.
Now all of this is possible because of the one-way/non-invertible nature of the hash functions used. As we cannot predict inputs to be given according to the desired hash, I cannot adjust sibling hashes I sent to the thin node to make sure that the backtracking ends up giving the correct hash value of the root node.</p>

CC BY-SA 4.0
2020-08-26T10:16:33.797Z
2020-08-26T10:16:33.797Z
NIKHIL KOMMINENI
<p>One of the previous answers directly answers your question about efficiency. It is certainly not necessary to communicate or store every hash.</p>

<p>One great efficiency of using a Merkle Tree is:</p>

<blockquote>
  <p><a href="https://en.bitcoin.it/wiki/Block_hashing_algorithm" rel="nofollow noreferrer">https://en.bitcoin.it/wiki/Block_hashing_algorithm</a><br>
  The body of the block contains the transactions. These are hashed only indirectly through the Merkle root. Because transactions aren't hashed directly, hashing a block with 1 transaction takes exactly the same amount of effort as hashing a block with 10,000 transactions.</p>
</blockquote>

CC BY-SA 3.0
2018-01-27T01:10:43.750Z
2018-01-27T01:10:43.750Z
Willtech
<p>Reading your question, I suspect the cause for your confusion is around <em>the setting</em> 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.</p>
<p>Here's my two cents. To understand the <em>efficiency</em> aspect of Merkle trees, consider the two parties that are actually involved in the protocol:</p>
<ol>
<li>A Bitcoin <em>full node</em> who has full blocks.</li>
<li>A Bitcoin <em>thin node</em> who has headers but wants to verify that a transaction is in one of the full blocks.</li>
<li>(It might be worth mentioning that the current Bitcoin protocol <strong>does not</strong> allow a thin node to <em>efficiently</em> verify that a transaction is <strong>not</strong> in any of the blocks.)</li>
</ol>
<p><strong>First</strong>, recall that when receiving a new block <code>B</code> with block header <code>H</code> and transactions <code>T</code>, the full node does the following:</p>
<ol>
<li>computes <code>h = SHA256(H)</code>, verifies the proof-of-work in <code>h</code> and checks the timestamp in <code>H</code>, etc.</li>
<li>for each transaction <code>t \in T</code>, verifies <code>t</code>'s signature(s), verifies <code>t</code> does not double spend, and appends <code>t</code> as the rightmost leaf of the current block's <em>Merkle tree</em>. (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 <code>H</code>.)</li>
<li>after all <code>t \in T</code> have been verified and appended, computes <strong>and stores</strong> the Merkle tree, <strong>of course computing all</strong> <em>interior node</em> hashes and the <em>root hash</em> <code>r</code> (as depicted in your Merkle tree figure).</li>
<li><strong>Crucially</strong>, verifies that the computed root hash <code>r</code> equals the root hash in the block header <code>H</code>.</li>
</ol>
<p><em>Moral of the story:</em> Yes, you are right that to prove membership of a leaf with respect to a Merkle root <code>r</code>, 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 <strong>are not</strong> part of the 1MB block <code>B</code>: 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.</p>
<p><strong>Second</strong>, recall that when receiving a new block header <code>H</code>, a thin node just does step (1) from above.</p>
<p>Now, here's <em>the setting</em> in Bitcoin:</p>
<ol>
<li>The full node has all the blocks, including the interior node hashes computed in Step 3 above.</li>
<li>The thin node has all block headers. Recall that each header includes the Merkle root.</li>
<li>The full node wants to convince the thin node that some transaction <code>t</code> is in some block <code>B</code> with block header <code>H</code> (which of course the thin node has)</li>
</ol>
<p><em>Thesis:</em> <strong>Merkle trees allow the full node to convince the thin nodes of this <em>efficiently</em></strong>, preventing the full node from changing <code>t</code> into <code>t'</code> (which would allow a full node to trick a thin node into thinking it got paid).</p>
<p><em>Proof:</em> Let <code>r</code> denote the Merkle root in <code>H</code>. The thin node has that same <code>H</code> and <code>r</code>. The full node has the interior nodes &quot;under&quot; <code>r</code> cached (recall Step 3 from the full node). The full node <strong>fetches</strong> the (already cached) <em>sibling path</em> starting at the leaf containing the transaction <code>t</code> and going all the way up to the root <code>r</code>, sending it to the thin node. The thin node recursively hashes up <code>t</code> with the received siblings, obtaining a root hash <code>r'</code> (hand-waving here, assuming you understand Merkle proofs). The thin node checks that <code>r == r'</code>.</p>
<p><strong>Efficiency:</strong> The full node (i.e., prover) only has to send <code>O(\log{n})</code> siblings in a Merkle tree of <code>n</code> leafs to the thin node (i.e., the verifier), who only has a 256-bit root hash <code>r</code>. (Of course, the prover needs to have all the leafs and all the interior nodes, as discussed before.)</p>
<p>Naturally, this protocol guarantees the full node cannot &quot;lie&quot; about any transaction &quot;under&quot; the root <code>r</code>. 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.</p>
<p>To answer your questions:</p>
<p><strong>Question A</strong> seems to be about how membership of a transaction <code>t</code> works. You say,</p>
<blockquote>
<p>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?</p>
</blockquote>
<p>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 <em>precise</em>.</p>
<p>The thin node cannot &quot;just look at the list of leaf hashes&quot; because it only has the root hash <strong>and no leafs</strong> 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, <strong>that would be inefficient</strong>: <code>O(n)</code> bandwidth for <code>n</code> leafs. In contrast, a Merkle proof for a leaf under a root hash <strong>is much more efficient</strong>: only <code>O(\log{n})</code> hashes + the leaf itself.</p>
<p><strong>Question B</strong> 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.</p>
<p><strong>Question C</strong>:</p>
<blockquote>
<p>Does Bitcoin persist the Merkle tree hashes for not only the leaf nodes but for the entire tree all the way to the root?</p>
</blockquote>
<p>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.</p>
<blockquote>
<p>Where exactly and how exactly does it store this information? All I ever see is the Merkle root in the block...</p>
</blockquote>
<p>Presumably, on disk in the database of the full node. But not in the block: they are redundant info because blocks contains leafs <code>=&gt;</code> can compute hashes of interior nodes and root node.</p>
<blockquote>
<p>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...</p>
</blockquote>
<p>Ugh, I want to say <em>&quot;Yes, because it would be a waste of space to store interior node hashes in the blocks.&quot;</em> 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;</p>
<p>Hope this helps!</p>

CC BY-SA 3.0
2018-01-26T01:03:45.323Z
In regards to 'wouldn't you just look at the list of leaf hashes to determine whether H(D) is there?', in doing so you miss proof that the transaction is in the block and that the block is unaltered. The computation steps are necessary for proof.
Willtech
CC BY-SA 3.0
2018-01-26T16:32:26.070Z
Of course! @Jazimov, if you find your reply to be too long, you might want to simply ask one or more new, concise questions?
Alin Tomescu
CC BY-SA 3.0
2018-01-29T01:10:23.603Z
@Alin: Great answers: Just one comment (please revised/append your answer if you agree that this point was unclear)... With respect to you answer to my Question A: [[The thin node cannot "just look at the list of leaf hashes"]] I understand that. But if thin node wants to verify that transaction 12345 is there, why not just ask the full node to look at its full-node leaf Tx values for transaction 12345 (or a hash of 12345)? That's enough to prove the Tx is in the block, no? Computing the Merkle root, though, guarantees that's it's there AND in the same position. Is that the real point?
Jazimov
CC BY-SA 3.0
2018-01-29T09:38:59.120Z
@Jazimov, I will edit my answer to clarify. The quick answer I can give you now is that _no, it is not enough_. Just ask yourself: What's to prevent a full node from showing one thin node TXN 1235 sending coins from A to B while showing another thin node TXN 12345' (not part of the block) sending coins from A to C and thereby double spending? The answer is the Merkle membership proof + miners preventing double spends. It is important to note Merkle trees are sufficient, but not necessary here, as I discussed in a previous answer you linked to.
Alin Tomescu
CC BY-SA 3.0
2018-01-29T23:42:19.010Z
@Jazimov, I realized I am bit confused by your question. You said _"But if thin node wants to verify that transaction 12345 is there, why not just ask the full node to look at its full-node leaf Tx values for transaction 12345 (or a hash of 12345)?_" What would the **full node** looking at a TXN in some leaf achieve? The thin node needs to be convinced with a cryptographic proof from the full node. The full node can look wherever it wants, but that won't convince the thin node of anything. Position in the tree of a TXN doesn't matter AFAICT. (Why would it?) Am I misunderstanding your question?
Alin Tomescu
CC BY-SA 3.0
2018-01-30T02:18:15.653Z
If a thin node wants to verify that TXN 12345 (say it has hash of "123AABBC") is in full node, I am wondering why the full node can't just inspect its list of TXNs for a hash = "123AABBC"? That could be sped-up using an index of hashes for full-node TXNs. My comment relates to why a Merkle proof would need to be part of that full-node verification that TXN 12345 (via it's hash) is in fact in the full node...
Jazimov
CC BY-SA 3.0
2018-01-30T22:03:42.907Z
First, the thin node wants to verify that TXN 12345 is in a **block.** Not sure what you mean by "in a full node." The full node is merely helping relay data that convinces the thin node, specifically, the Merkle sibling path. This Merkle proof is sufficient to convince the thin node that TXN 12345 is **in the block.** However, other techniques can be used as well: it's just that their proof size will be bigger or they come at a higher computation overhead! If you understood the setting (i.e., full node tries to convince thin node that TXN is in block), you need to understand Merkle security.
Alin Tomescu
CC BY-SA 3.0
2018-01-30T22:05:50.863Z
To understand the security of Merkle proofs, it's probably best to ask a separate question or see what's out there. Keep in mind that the prover **can lie** to a verifier. Commiting to the *data* using a Merkle tree and giving the root hash to the verifier **before the verifier queries**, prevents the prover from lying to the verifier about the *data* if the verifier correctly checks the Merkle membership proof.
Alin Tomescu
CC BY-SA 3.0
2018-01-31T04:26:33.407Z
OK, "in the block" (I said full node because all transaction data rather than header only is in a full node only).Meanwhile, I think you and I agree that a Merkle proof composed of a sibling path is sufficient to prove that a TX is in a block. I still don't understand why the sibling has to be involved. Why not just hash TX 12345 and check if its hash is a leaf node? As I already said, an index containing hashes of leaf nodes will speed that look-up. Why get a sibling involved?
Jazimov
CC BY-SA 3.0
2018-01-31T10:28:42.037Z
Let's take the simplest example and make sure we understand each other. Suppose the prover has `tx_1` and `tx_2` with hashes `h_0` and `h_1` respectively. Suppose the prover computes a Merkle tree over these two leafs so the root hash is `r = H(h_0, h_1)`. (This is a really small tree.) Suppose the verifier has `r` and prover gives it **just** `tx_1` and `h_1` as a (insecure) membership proof? I'm assuming this is what you're proposing. Is this correct so far? If so, you tell me how the verifier should check this (insecure) proof... :)
Alin Tomescu
CC BY-SA 3.0
2018-01-25T22:45:58.327Z
2018-01-26T16:36:48.870Z
2020-06-16T11:10:03.350Z
Alin Tomescu
<p>This is one of those questions that everyone seems to write about but the same bad explanations are just plagiarized from site to site.</p>

<hr>

<p><strong><em>Edit:</em></strong> The heart of my question is why Merkle trees are claimed to be <em>efficient</em> 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 <em>claims</em> 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 <em>all</em> hashes in the entire tree would need to be recalculated, as I explain below...</p>

<hr>

<p>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:</p>

<p><a href="https://i.sstatic.net/qYBPm.jpg" rel="noreferrer"><img src="https://i.sstatic.net/qYBPm.jpg" alt="From Investopedia.com"></a></p>

<p>Merkle Trees in General</p>

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

<p>A. Whether the H(D) leaf is in the Merkle tree. </p>

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

<p>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?</p>

<p>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.</p>

<p>My final question:</p>

<p>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... </p>

<p>Thanks!</p>

<merkle-tree>
Merkle Root and Merkle Proofs
Jazimov
# Merkle Root and Merkle Proofs

(Asked by: username_0 on 2018-01-19)

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:

[![From Investopedia.com](https://i.sstatic.net/qYBPm.jpg)](https://i.sstatic.net/qYBPm.jpg)

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!

**Tags:** merkle-tree


---

## 6 answers

### Answer by username_9 on 2018-01-25. Score: 27 | Accepted answer

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!

> **Comments:**
> **username_8**: In regards to 'wouldn't you just look at the list of leaf hashes to determine whether H(D) is there?', in doing so you miss proof that the transaction is in the block and that the block is unaltered. The computation steps are necessary for proof.  
> **username_9**: Of course! @username_0, if you find your reply to be too long, you might want to simply ask one or more new, concise questions?  
> **username_0**: @username_9: Great answers: Just one comment (please revised/append your answer if you agree that this point was unclear)... With respect to you answer to my Question A: [[The thin node cannot "just look at the list of leaf hashes"]] I understand that. But if thin node wants to verify that transaction 12345 is there, why not just ask the full node to look at its full-node leaf Tx values for transaction 12345 (or a hash of 12345)? That's enough to prove the Tx is in the block, no? Computing the Merkle root, though, guarantees that's it's there AND in the same position. Is that the real point?  
> **username_9**: @username_0, I will edit my answer to clarify. The quick answer I can give you now is that _no, it is not enough_. Just ask yourself: What's to prevent a full node from showing one thin node TXN 1235 sending coins from A to B while showing another thin node TXN 12345' (not part of the block) sending coins from A to C and thereby double spending? The answer is the Merkle membership proof + miners preventing double spends. It is important to note Merkle trees are sufficient, but not necessary here, as I discussed in a previous answer you linked to.  
> **username_9**: @username_0, I realized I am bit confused by your question. You said _"But if thin node wants to verify that transaction 12345 is there, why not just ask the full node to look at its full-node leaf Tx values for transaction 12345 (or a hash of 12345)?_" What would the **full node** looking at a TXN in some leaf achieve? The thin node needs to be convinced with a cryptographic proof from the full node. The full node can look wherever it wants, but that won't convince the thin node of anything. Position in the tree of a TXN doesn't matter AFAICT. (Why would it?) Am I misunderstanding your question?  
> **username_0**: If a thin node wants to verify that TXN 12345 (say it has hash of "123AABBC") is in full node, I am wondering why the full node can't just inspect its list of TXNs for a hash = "123AABBC"? That could be sped-up using an index of hashes for full-node TXNs. My comment relates to why a Merkle proof would need to be part of that full-node verification that TXN 12345 (via it's hash) is in fact in the full node...  
> **username_9**: First, the thin node wants to verify that TXN 12345 is in a **block.** Not sure what you mean by "in a full node." The full node is merely helping relay data that convinces the thin node, specifically, the Merkle sibling path. This Merkle proof is sufficient to convince the thin node that TXN 12345 is **in the block.** However, other techniques can be used as well: it's just that their proof size will be bigger or they come at a higher computation overhead! If you understood the setting (i.e., full node tries to convince thin node that TXN is in block), you need to understand Merkle security.  
> **username_9**: To understand the security of Merkle proofs, it's probably best to ask a separate question or see what's out there. Keep in mind that the prover **can lie** to a verifier. Commiting to the *data* using a Merkle tree and giving the root hash to the verifier **before the verifier queries**, prevents the prover from lying to the verifier about the *data* if the verifier correctly checks the Merkle membership proof.  
> **username_0**: OK, "in the block" (I said full node because all transaction data rather than header only is in a full node only).Meanwhile, I think you and I agree that a Merkle proof composed of a sibling path is sufficient to prove that a TX is in a block. I still don't understand why the sibling has to be involved. Why not just hash TX 12345 and check if its hash is a leaf node? As I already said, an index containing hashes of leaf nodes will speed that look-up. Why get a sibling involved?  
> **username_9**: Let's take the simplest example and make sure we understand each other. Suppose the prover has `tx_1` and `tx_2` with hashes `h_0` and `h_1` respectively. Suppose the prover computes a Merkle tree over these two leafs so the root hash is `r = H(h_0, h_1)`. (This is a really small tree.) Suppose the verifier has `r` and prover gives it **just** `tx_1` and `h_1` as a (insecure) membership proof? I'm assuming this is what you're proposing. Is this correct so far? If so, you tell me how the verifier should check this (insecure) proof... :)  

---

### Answer by username_1 on 2018-01-21. Score: 10

Say a block consisting of these 10 transactions, noted by their txids at indexes 0 to 9:

```
E1AF205960AE338A37174B407EE71067C3CD7F04D48A5CEC7E13F6ECCB61DCBC
A314970CD7C647D1CC0A477E1A2122B98205B6924B73001B8DAB20EE81C2F4F7
B08EB9DCE0452A1B1970C4D29E88BDEE07669A2A5D1B08586D7FFA17B2E3F6B5
958B9E94AEA9A485BA494C50FB3192558057F7CAED9705D4B11369F071F10642
3D278CA01CC527D4C7D577B668E0B976FBBCB94E6A9BA89664C721F36FADA6A1
95AFFA405501498EF6F4E4B6CDDC1F1B24B9D2E534584B31A9142C453920C889
D97A21CF46FD5AFB0BF9EA4237BC4BF5C84E8B47D38D1EEE2BBEB5C0F8A1C625
AE1E670BDBF8AB984F412E6102C369AECA2CED933A1DE74712CCDA5EDAF4EE57
90E03319DDC9D48DA38AB39B2F37C0A5AF5AFC736F6FF2A9D8B8653E0FEB308D
84251842A4C0F0E188E1C2BF643EC37A1402DD86A25A9AB5004633467D16E313

```

With a merkle root that we both agree on (it's in the blockchain):

```
B152ECA4364850F3424C7AC2B337D606C5CA0A3F96F1554F8DB33D2F6F130BBE

```

And say you want me to prove to you that the transaction `D97A21CF46FD5AFB0BF9EA4237BC4BF5C84E8B47D38D1EEE2BBEB5C0F8A1C625` is in this block.

I give you this proof :

```
AE1E670BDBF8AB984F412E6102C369AECA2CED933A1DE74712CCDA5EDAF4EE57,
EFC2B3DB87FF4F00C79DFA8F732A23C0E18587A73A839B7710234583CDD03DB9,
F1B6FE8FC2AB800E6D76EE975A002D3E67A60B51A62085A07289505B8D03F149,
E827331B1FE7A2689FBC23D14CD21317C699596CBCA222182A489322ECE1FA74

```

And tell you that this transaction is at index `6`, and that this is a tree of depth `4`.

`(2^4) + 6 = 22`, and that is `10110` in base 2.
This representation in base 2 is the path we need to take from the first txid for which we want to prove the inclusion to the root.

Now all you're left with is to walk the path from the txid to the root, and if proof is correct, then you should get the block's merkle root.
We start the path from right to left, so with the `0` bit of of the base 2 number (the left most 1 is not used (it is the root really)).
Since this is a `0`, we should place "our" hash (the txid) on the left side :

```
hash256 D97A21CF46FD5AFB0BF9EA4237BC4BF5C84E8B47D38D1EEE2BBEB5C0F8A1C625|AE1E670BDBF8AB984F412E6102C369AECA2CED933A1DE74712CCDA5EDAF4EE57
=
066AD6D9939EC0C90B7F3B775122785BD8ACA2A2C5857205AF7E0615E9AF9796

```

The next is a `1`, "our" hash is on the right :

```
hash256 EFC2B3DB87FF4F00C79DFA8F732A23C0E18587A73A839B7710234583CDD03DB9|066AD6D9939EC0C90B7F3B775122785BD8ACA2A2C5857205AF7E0615E9AF9796
=
8BE15FC2AB11EF3E079568D43B2B09ED5A5690FB13ECB1032F7AAB99238A1847

```

Next is a `1` again, so again we're on the right :

```
hash256 F1B6FE8FC2AB800E6D76EE975A002D3E67A60B51A62085A07289505B8D03F149|8BE15FC2AB11EF3E079568D43B2B09ED5A5690FB13ECB1032F7AAB99238A1847
=
8D9D737B484E96EED701C4B3728AEA80AA7F2A7F57125790ED9998F9050A1BEF

```

Next is a `0`, we're on the left :

```
hash256 8D9D737B484E96EED701C4B3728AEA80AA7F2A7F57125790ED9998F9050A1BEF|E827331B1FE7A2689FBC23D14CD21317C699596CBCA222182A489322ECE1FA74
=
B152ECA4364850F3424C7AC2B337D606C5CA0A3F96F1554F8DB33D2F6F130BBE

```

And this is the block's merkle root. The proof is correct.
The txid exists in a block on chain in this specific index, and the block has the correct depth.

For a very large tree, the effect is even more dramatic. The quantity of steps it takes to prove an element is in a tree is logarithmic to the size of the tree, so proof stays small.
Hopefully this is what you were asking.

These transactions are from block `0000000000000a3290f20e75860d505ce0e948a1d1d846bec7e39015d242884b` by the way.

> **Comments:**
> **username_0**: I followed the above. But after you offer the proof, it's unclear where you get these values from: AE1E670BDBF8AB984F412E6102C369AECA2CED933A1DE74712CCDA5EDAF4EE57, EFC2B3DB87FF4F00C79DFA8F732A23C0E18587A73A839B7710234583CDD03DB9, F1B6FE8FC2AB800E6D76EE975A002D3E67A60B51A62085A07289505B8D03F149, E827331B1FE7A2689FBC23D14CD21317C699596CBCA222182A489322ECE1FA74. According to what other people have written, the hash values for everything in the Merkle treet (OTHER THAN the Merkle root) is not stored anywhere in the blockchain...  
> **username_1**: These four values correspond to the yellow elements in the tree in your example (you have a tree with depth 3, so only 3 of these yellow elements). Anyone with the full list of transactions in a block can generate them for someone else asking to see proof that a transaction is included in some block, or when encountering such proof themselves, it is easily verifiable (only about log(n) steps) without going through the whole transaction list.  
> **username_0**: Wrong, you cannot generate just the yellow element hashes without recomputing the entire tree and that doesn't save any computations.  
> **username_1**: "My question is why Merkle trees are an efficient way for blockchains to determine whether transactions are present in the Merkle tree given the Merkle root hash value and the leaf hash value.  I don't see how it's possible to execute a Merkle proof without recalculating the entire Merkle tree."  It's not an efficient way for "blockchains" to do anything.  Merkle proofs are an efficient way to prove membership of an element in a set. This is used by lite-wallets and their servers.  Not by the actual bitcoin protocol.  
> **username_0**: Then what's the point of using a Merkle root? Why not just calculate a single hash from every transaction in transaction sequence? That also would generate a unique hash that detects transaction-sequence changes as well as transaction data changes. Why go with Merkle at all???  
> **username_1**: Because it's very useful to be able to prove membership of a transaction in a block using only log2(tree size) hashes instead of using the entire transaction list (which is the tree size itself).  SPV has been an intended feature since the beginning, and while we're not using the same SPV talked about in the white paper, the merkle tree construction still applies. Consider that proving a txid exists in a set of 2000~ txids will take 11 hashes using a merkle tree construction, versus the entire 2000~ transactions given in a linear list.  
> **username_2**: How can I "ask" to full node, please check this `D97A21CF46FD5AFB0BF9EA4237BC4BF5C84E8B47D38D1EEE2BBEB5C0F8A1C625` and return 4 txid to check manually like your example? thanks  
> **username_3**: +1 for this much better answer than the accepted one...  

---

### Answer by username_4 on 2018-01-28. Score: 3

There are two kinds of efficiencies:

1. Computation: Merkle tree is as efficient as any other binary search tree in terms of computation and searching.
2. Storage: This is where the magic happens. [![enter image description here](https://i.sstatic.net/we8A1.jpg)](https://i.sstatic.net/we8A1.jpg)

Merkle root: HABCDEFGH  
Hash to verify: HD

Process:  
1. HCD = Hash( HC , HD)  
2. HABCD = Hash( HCD, HAB)  
3. HABCDEFGH = Hash( HABCD, HEFGH)

In the whole process of verification of HD(of total 8), we only need to store extra 3 hashes (HC, HAB, HEFGH).

Storage complexity: log2n = log28 = 3

When n = 1024: log2n = log21024 = 10   
When n = 1048576: log2n = log21048576 = 20

In this sense, Merkle trees are efficient compared to other data structures.


---

### Answer by username_5 on 2018-01-20. Score: 1

For a bitcoin block to be valid, the block's header must hash to an output that is within a certain range of values (defined by the current network difficulty).

The merkle root is one component of the block header, so in effect the merkle root is a cryptographic commitment to the transactions included in the block. Changing any single transaction (or the order of transactions) would alter the merkle root, and thus alter the block's hash (which, by overwhelming probabilty, would make the block invalid).

> 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?

The leaf hashes are not explicitly contained in the block, but it is trivial for any node to verify that a given transaction is properly included in the block (and therefore included in the merkle root). This is done by hashing the transaction [in your example, H(D)], and then combing H(D) with H(C) to get H(CD), and so on, until the merkle root is reached (and found to be correct against the merkle root of the block).

Full node clients download the entire blockchain, and are thus capable of performing this validation on their own. 'Litewallet' clients just download the block headers, and can use simplified payment verification (SPV) to perform a cryptographic check for transaction validity in a less intensive manner. SPV involves requesting just the hashes in the relevant branch of the tree, working from the transaction in question up to the root. Any attempt by the wallet's peers to lie about the transactions/hashes in a block will result in an invalid merkle root, so it is impossible for a peer to lie and say a transaction is included in a block, when it is in fact not.

> With respct 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?

It is not a matter of knowing a 'new' or 'old' H(CD), there is simply **the** H(CD) that was an intermediate step in calculating the merkle root of the relevant block. Once the block is accepted as valid by the network, there is no ability to change a transaction in it (and thus change the higher level hashes in the tree). Changing anything would change the merkle root, and thus the block's hash, so the network would no longer accept that block as valid.

> 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?

Each block contains the merkle root, as well as all of the transactional data. The leaf / intermediate level hashes are not explicitly included, instead they can be calculated by nodes to verify and validate the block's transactional data. ([There are some other bits of data included in a block](https://en.bitcoin.it/wiki/Protocol_documentation#block), but it is the merkle root and transaction data that is relevant to your question)

You may be interested in reading over [the top answers to this question](https://bitcoin.stackexchange.com/questions/10479/what-is-the-merkle-root#10487), they are great explanations of the function of the merkle root.

> **Comments:**
> **username_0**: Answer appreciated but you totally missed the point of my questions. You say that "it is trivial for any node to verify that a given transaction is properly included in the block" and cite calculating H(D) hashes back to the root. But as my question articulated, you cannot calculate the Merkle root from H(D) without reconstructing the ENTIRE Merkle tree hashes. I realize this can be done, but there is no efficiency in doing that because all leaf nodes must be rehashed to calculate the root. Merkle proofs speak of the "efficiency" of the Merkle structure in proving a node exists.  
> **username_0**: My issue is not that I do not understand how to create a Merkle tree and the root hash--which is what you explained--but why this structure is EFFICIENT especially if non-leaf hashes en route to the Merkle root are not retained in a Bitcoin block. Please re-read question B to see my specific example. Thanks!  
> **username_5**: In that case, the ‘efficiency’ comes from being able to cryptographically commit to a huge number of transactions being in a given block. Having to include all of the txs in the header explicitly would be much less efficient. So yes, a node must perform these validating computations, but the ‘efficiency gains’ talked about do not relate to this specifically (at least as far as I’ve ever read/understood).  
> **username_5**: Related: Consider also that having a Merkle root in the block header (instead of an explicit list of transactions) means that a miner must perform the same computation for a block with 5 txs as a block with 500 txs. So there is no incentive for a miner to include less txs, in order to perform POW computations more quickly.  
> **username_0**: You're still missing my point. Read username_9's answer in https://bitcoin.stackexchange.com/questions/48928/why-does-each-block-store-a-merkle-root. He says "Merkle roots are stored in Bitcoin block headers so as to enable efficient membership proofs for transactions in a block, which are necessary for Simple Verified Payment verification (SPV) nodes that only store block headers and not block contents" but doesn't explain. My question is about "efficient membership proofs" and you're not addressing that in any of your responses.  
> **username_5**: I think I understand better now. Rather than download and hash through every transaction in the entire tree, an SPV wallet can just request the sibling hashes. So in your example, after calculating H(AB), a wallet can just request H(CD), rather than requesting T(C) and T(D) to calculate H(CD) locally. An SPV wallet can trust it has been provided with valid info as long as the Merkle root is reached. So a transaction’s membership in a block can be verified more easily than if every transaction in the block had to be hashed. The Q I linked to has a little more info on this.  
> **username_6**: comment to B: wouldn't SPV nodes read the six blocks from the first occurance of the tx in a block, and then with the six'th block do the final check? a peer would send the requested block with the block header and the merkle path (for the tx). The SPV node uses this path to calculate up to the block header. That is, what speeds up the verification time....  

---

### Answer by username_7 on 2020-08-26. Score: 1

Let's start with understanding the fact that BlockChain(Bitcoin's ledger) is distributed across multiple nodes. So, nodes cannot trust each other as they are not managed by some trusted party. Whenever a thin node(non-miner) P request's a full node(miner) Q to verify the presence of a txn t in a block B the full node Q has to convince the node P that it(Q) is saying the truth. Merkle trees come into play here.

So, the thin node P has the root-hash of block B and the hash of the txn t. The one thing the full node cannot wrongly convince the thin node about the block B is its root-hash. So as proof to "the full node is telling the truth about the presence of txn t in block B" it also sends the hash values of the sibling nodes of the nodes in the path from the root to the txn t in the Merkle tree. The thin node then backtracks the hash values along the path from txn t to the root of the Merkle tree using the sibling's hashes sent by the full node. If the resulting root-hash is equal to the one in block B's header then the full node is telling the truth.

Now assume I'm a full node and I want to falsely convince a thin node that a txn t is in block B. I can simply say that I've checked all the leaf's hashes and found hash of txn t in the list. But who can tell if I'm lying. Now the leaf node might request me to send the list of txns to check the list by itself, but I can always add the txn t to the list and send over the altered list.

Now if the thin node asks me to provide the hash value of the parent node of the txn t so that it can verify itself by hashing txn t's sibling and t together and compare the result with the parent's hash I just sent over. Now I can just send a wrong hash value of the parent to misguide the thin node. So the thin node has to verify that this parent-hash is infact the actual hash in the Merkle tree. This process of verification is recursive until I reach a point where the parent node is the root node. This time the thin node has the hash of the parent node and can verify itself. So whenever the thin node can backtrack the root-hash to the one in the block's header the full node is not lying/misguiding.
Now all of this is possible because of the one-way/non-invertible nature of the hash functions used. As we cannot predict inputs to be given according to the desired hash, I cannot adjust sibling hashes I sent to the thin node to make sure that the backtracking ends up giving the correct hash value of the root node.


---

### Answer by username_8 on 2018-01-27. Score: 0

One of the previous answers directly answers your question about efficiency. It is certainly not necessary to communicate or store every hash.

One great efficiency of using a Merkle Tree is:

> <https://en.bitcoin.it/wiki/Block_hashing_algorithm>  
> The body of the block contains the transactions. These are hashed only indirectly through the Merkle root. Because transactions aren't hashed directly, hashing a block with 1 transaction takes exactly the same amount of effort as hashing a block with 10,000 transactions.


---

