Merkle Root and Merkle Proofs

Question

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!

Answer 1

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!

Answer 2

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.

Answer 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.

Merkle root: H_ABCDEFGH
Hash to verify: H_D

Process:
1. H_CD = Hash( H_C , H_D)
2. H_ABCD = Hash( H_CD, H_AB)
3. H_ABCDEFGH = Hash( H_ABCD, H_EFGH)

In the whole process of verification of H_D(of total 8), we only need to store extra 3 hashes (H_C, H_AB, H_EFGH).

Storage complexity: log₂n = log₂8 = 3

When n = 1024: log₂n = log₂1024 = 10
When n = 1048576: log₂n = log₂1048576 = 20

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

Answer 4

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 5

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 6

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.