12

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

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!

13
+25

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!

  • 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 Jan 26 '18 at 1:03
  • 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 Jan 26 '18 at 16:32
  • @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 Jan 29 '18 at 1:10
  • @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 Jan 29 '18 at 9:38
  • @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 Jan 29 '18 at 23:42
6

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.

  • 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 Jan 22 '18 at 1:42
  • 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 Jan 22 '18 at 7:53
  • Wrong, you cannot generate just the yellow element hashes without recomputing the entire tree and that doesn't save any computations. – Jazimov Jan 22 '18 at 13:31
  • "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 Jan 22 '18 at 17:37
  • 2
    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 Jan 23 '18 at 17:44
2

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

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.

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, 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, they are great explanations of the function of the merkle root.

  • 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 Jan 20 '18 at 15:20
  • 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 Jan 20 '18 at 15:22
  • 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 Jan 20 '18 at 23:39
  • 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 Jan 20 '18 at 23:46
  • You're still missing my point. Read Alin Tomescu's answer in bitcoin.stackexchange.com/questions/48928/…. 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 Jan 21 '18 at 4:22
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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