<p>If the calculated Merkle root doesn't match any of the block headers then the proof is invalid and the TX may or may not exist.
That's the default verification state, same as if you never got any proofs.
If someone gives you an invalid Merkle proof then you don't learn any new information.</p>
<p>Merkle proof can prove inclusion in some block, but it <strong>can NOT prove non-inclusion</strong>.</p>
<p>You need all block headers in order to verify the Merkle proof.
A valid proof will match exactly one block header in the header chain of the blockchain you're verifying against.
If there are no matches, then the proof is invalid for the blockchain you have headers for.
It could still be a valid proof for some other blockhain (like a fork of Bitcoin, and with exact same header format &amp; Merkle tree computation).</p>

CC BY-SA 4.0
2023-11-22T16:34:37.687Z
Thanks. I don't get the point of SPV then. Doesn't a light client also need a proof of non-inclusion? What would a light client do if the merkle proof fails?
ieggel
CC BY-SA 4.0
2023-11-22T16:45:42.823Z
@ieggel The merkle proof wouldn't fail (if it does, the client could show an error to the user, who could get suspicious). Instead, a server can just claim there is no transaction, so there isn't even a proof to give. And the result would be that the client doesn't know about a transaction. The solution is either trusting the server, querying multiple servers, ignoring this failure mode, or using a different architecture (e.g. not using SPV at all, and e.g. using a full node wallet).
Pieter Wuille
CC BY-SA 4.0
2023-11-22T16:58:48.077Z
Thanks @PieterWuille. I don't get why SPV is 'marketed' the way it is then. In my opinion  a client NEEDS to know if a transaction was not included. Querying multiple full nodes makes sense, but even then I guess it's not fully trustable. Ignoring  the failure just means accepting the transaction was either included or not included, which would be the same as not querying at all. Connecting to a trusted full node seems the only way. But SPV was invented so no trusted full nodes are required, if I got it right. Has Satoshi not taken this into consideration, which seems weird?
ieggel
CC BY-SA 4.0
2023-11-22T17:21:30.880Z
It's hard to speculate about the intentions of someome who disappeared a decade ago, as we have no idea about their reaction to evolved understanding since. The SPV design as presented in the white paper just fundamentally doesn't work (it relies on fraud proofs for security, but misses that attackers can always withold data that would let someone disprove it). The SPV protocol that was actually implemented on the P2P layer (BIP37) came years after Satoshi disappeared, and its independent problems (the one you point out, but even more its privacy) became clear even later than that.
Pieter Wuille
CC BY-SA 4.0
2023-11-22T21:52:54.843Z
Thanks for all the insights @PieterWuille. I've been studying bitcoin for 2 weeks now and started reading about merkle trees and SPV last week. I always had the impression that it does not make a lot of sense the way it was described and I was sure that I must be missing something. It's just incredible that it was not obvious for the developers from the very beginning. Now I am wondering why merkle roots are used in the block header and not just a hash over all transaction hashes, or something alike. Do some full nodes get rid of the transaction data itself and inly keep the headers?
ieggel
CC BY-SA 4.0
2023-11-22T22:21:06.783Z
Yes, it's possible to run a node that doesn't keep the block data (called a pruned node), but that's not incompatible with just hashing the list of transactions either. Truth is, the protocol uses Merkle tree simply because it always has (and likely because the system's creator envisioned SPV to be used differently than it is today). Unless there is an *extremely* good reason to change it, there is no way such an invasive protocol change would happen. At worst, Merkle trees are slightly slower than using a flat list of hashes. At best, the inclusion proofs are useful somehow. No harm done.
Pieter Wuille
CC BY-SA 4.0
2023-11-23T06:18:51.510Z
FWIW Satoshi imagined SPV to be used when someone pays you and wants to directly prove to you that he paid you, and he imagined here something like Electrum protocol: "The simplified payment verification in the paper imagined you would receive transactions directly, as with sending to IP address which nobody uses, or a node would index all transactions by public key and you could download them like downloading mail from a mail server." -- https://www.bitcoin.com/satoshi-archive/emails/mike-hearn/9/#selection-25.149-25.1252
bca-0353f40e
CC BY-SA 4.0
2023-11-23T13:20:11.297Z
Thank you @PieterWuille and bca-0353f40e, very useful information. The thing is that almost everyone providing information about Merkle Trees and SPV in bitcoin found on the www take it for granted that merkle trees are absolutely necessary and do not question their usefulness at all. It's hilarious how they repeat everything they heard like parrots which no questioning at all. Even people that provide courses. Thanks again guys, very appreciated.
ieggel
CC BY-SA 4.0
2023-11-23T13:41:02.097Z
I think there is a possibly important security property you get with inclusion proofs without exclusion proofs, which you wouldn't have without: when querying multiple servers, it now suffices that one honest server gives you all transactions (or, alternatively, all servers together give you all transactions). Without inclusion proofs, if multiple servers gave you distinct things, you'd have no idea which one to believe. It's certainly not a clear-cut "this is sufficient", but it is a substantial improvement still.
Pieter Wuille
CC BY-SA 4.0
2023-11-22T16:15:15.547Z
2023-11-22T16:15:15.547Z
bca-0353f40e
<p>How does a light client via SPV make sure that the requested merkle path is not fake?</p>
<p>I know that the client has its own copy of the block headers, so it can trust the merkle root from there. It then queries a full node for the merkle path, calculates the merkle root from that, and finally compares the reference merkle root with the calculated one. If both are the same, the client can be sure the transaction was included, even if it does not trust the full node, since there is no way for the full node to engineer the same merkle root from different data. So far so good.</p>
<p>However, how can it trust the received path in case both merkle roots do not match? The full node could send a fake path, which then leads to a different merkle root upon verification, which let's the client assume the transaction was not included when in reality it might have been included.</p>
<p>Can someone please clarify?
Thanks :)</p>
<hr />
<p><strong><em>UPDATE</em></strong>: Thanks to the answers and many comments I now understand that SPV via merkle root does not prove <strong>non-inclusion</strong> of a transaction in a specific block. In can only prove <strong>inclusion</strong>. In case the merkle roots match, we can be sure that the transaction is included in the block. If the merkle roots do not match, then the transaction could be included (fake path received) or not (legitimate path received), we don't know for sure.</p>
<p><em>In order to prove <strong>inclusion</strong> <strong><em>AND</em></strong> <strong>non-inclusion</strong>, it is probably easier and more secure to just have the transaction data of the block in question, received from a trusted full node.</em></p>
<p>Other 'workarounds' could be to:</p>
<ul>
<li>trust the server</li>
<li>query multiple servers</li>
<li>ignore the merkle root mismatch (do nothing, notify the user)</li>
</ul>
<p>Finally it turns out that merkle trees are not really that useful since SPV does not really work the way it was supposed to and that's why it is rarely used. A simple hash over all transaction would have worked as well.</p>
<p>Another addition, thanks to  @Pieter Wuille for the hints: A possible advantage of using merkle trees would be that <em>inclusion</em> can be proved by just a single legitimate path when querying multiple servers, because a valid merkle proof cannot be faked. That means all non-matching proofs (when querying multiple servers) can just be ignored in case there is a single one that matches.</p>
<p>Thank you everybody for the help!</p>

CC BY-SA 4.0
2023-11-22T15:28:22.827Z
How could it be faked? The Merkle path *proves* the leaf was committed to by the root in the header. To come up with a fake path that verifies correctly would need breaking the security of the hash function to construct the tree.
Pieter Wuille
CC BY-SA 4.0
2023-11-22T15:37:58.237Z
Or is your question about the Merkle root itself? The SPV client must have its own headers chain already *which it trusts*, and it will only accept Merkle paths that connect to one of these headers. If the Merkle root isn't the root included in one of its trusted block headers, it won't be accepted.
Pieter Wuille
CC BY-SA 4.0
2023-11-22T16:05:28.017Z
@PieterWuille. The fullnode could make the client intentionally assume that the transaction was not included when in reality it was. That means the fullnode wants the client to fail the merkle root comparison. A failed comparison means the transaction was not included, or am I getting something wrong?
ieggel
CC BY-SA 4.0
2023-11-22T16:07:12.750Z
Oh, yes, SPV proofs only prove *inclusion*, they cannot prove *exclusion*. This is one of the limitations of BIP37, and why it's not really used anymore.
Pieter Wuille
CC BY-SA 4.0
2023-11-22T16:36:02.277Z
@PieterWuille. So you say it is not used anymore? Why was it invented in the first place? What is the alternative?
ieggel
CC BY-SA 4.0
2023-11-22T16:43:00.230Z
There isn't a clear cut answer. I think SPV-style wallets in general just get used less these days. Merkle proofs are still used in protocols like Electrum, but that involves clients talking to Electrum-specific servers (which can be self-run, rather than being random untrusted full nodes). For some use cases, client-side filtering (BIP157) is a replacement (better privacy than BIP37, though not a fundamental solution to lack of exclusion proofs, but does allow a client to know when two servers claim distinct things).
Pieter Wuille
CC BY-SA 4.0
2023-11-23T18:24:24.733Z
re. "A simple hash over all transaction would have worked as well.", well, then miners would have to keep re-hashing the whole block whenever they update any 1 TX in the block template. With the Merkle structure, they only need to hash few 100 bytes for any single TX update.

Also note that proof of exclusion would be possible if the structure of the tree would be changed (look up "Merkle prefix trees") - this would require a soft fork. However, servers could still omit transactions, and you'd have to query a big enough set to have high confidence that nothing is missing.
bca-0353f40e
<full-node><merkle-tree><spv><merkleblock>
Legitimate merkle paths for SPV
ieggel
# Legitimate merkle paths for SPV

(Asked by: username_0 on 2023-11-22)

How does a light client via SPV make sure that the requested merkle path is not fake?

I know that the client has its own copy of the block headers, so it can trust the merkle root from there. It then queries a full node for the merkle path, calculates the merkle root from that, and finally compares the reference merkle root with the calculated one. If both are the same, the client can be sure the transaction was included, even if it does not trust the full node, since there is no way for the full node to engineer the same merkle root from different data. So far so good.

However, how can it trust the received path in case both merkle roots do not match? The full node could send a fake path, which then leads to a different merkle root upon verification, which let's the client assume the transaction was not included when in reality it might have been included.

Can someone please clarify?
Thanks :)

---

***UPDATE***: Thanks to the answers and many comments I now understand that SPV via merkle root does not prove **non-inclusion** of a transaction in a specific block. In can only prove **inclusion**. In case the merkle roots match, we can be sure that the transaction is included in the block. If the merkle roots do not match, then the transaction could be included (fake path received) or not (legitimate path received), we don't know for sure.

*In order to prove **inclusion** ***AND*** **non-inclusion**, it is probably easier and more secure to just have the transaction data of the block in question, received from a trusted full node.*

Other 'workarounds' could be to:

* trust the server
* query multiple servers
* ignore the merkle root mismatch (do nothing, notify the user)

Finally it turns out that merkle trees are not really that useful since SPV does not really work the way it was supposed to and that's why it is rarely used. A simple hash over all transaction would have worked as well.

Another addition, thanks to @username_1 for the hints: A possible advantage of using merkle trees would be that *inclusion* can be proved by just a single legitimate path when querying multiple servers, because a valid merkle proof cannot be faked. That means all non-matching proofs (when querying multiple servers) can just be ignored in case there is a single one that matches.

Thank you everybody for the help!

**Tags:** full-node, merkle-tree, spv, merkleblock

> **Comments:**
> **username_1**: How could it be faked? The Merkle path *proves* the leaf was committed to by the root in the header. To come up with a fake path that verifies correctly would need breaking the security of the hash function to construct the tree.  
> **username_1**: Or is your question about the Merkle root itself? The SPV client must have its own headers chain already *which it trusts*, and it will only accept Merkle paths that connect to one of these headers. If the Merkle root isn't the root included in one of its trusted block headers, it won't be accepted.  
> **username_0**: @username_1. The fullnode could make the client intentionally assume that the transaction was not included when in reality it was. That means the fullnode wants the client to fail the merkle root comparison. A failed comparison means the transaction was not included, or am I getting something wrong?  
> **username_1**: Oh, yes, SPV proofs only prove *inclusion*, they cannot prove *exclusion*. This is one of the limitations of BIP37, and why it's not really used anymore.  
> **username_0**: @username_1. So you say it is not used anymore? Why was it invented in the first place? What is the alternative?  
> **username_1**: There isn't a clear cut answer. I think SPV-style wallets in general just get used less these days. Merkle proofs are still used in protocols like Electrum, but that involves clients talking to Electrum-specific servers (which can be self-run, rather than being random untrusted full nodes). For some use cases, client-side filtering (BIP157) is a replacement (better privacy than BIP37, though not a fundamental solution to lack of exclusion proofs, but does allow a client to know when two servers claim distinct things).  
> **username_2**: re. "A simple hash over all transaction would have worked as well.", well, then miners would have to keep re-hashing the whole block whenever they update any 1 TX in the block template. With the Merkle structure, they only need to hash few 100 bytes for any single TX update.  Also note that proof of exclusion would be possible if the structure of the tree would be changed (look up "Merkle prefix trees") - this would require a soft fork. However, servers could still omit transactions, and you'd have to query a big enough set to have high confidence that nothing is missing.  

---

## 1 answers

### Answer by username_2 on 2023-11-22. Score: 3 | Accepted answer

If the calculated Merkle root doesn't match any of the block headers then the proof is invalid and the TX may or may not exist.
That's the default verification state, same as if you never got any proofs.
If someone gives you an invalid Merkle proof then you don't learn any new information.

Merkle proof can prove inclusion in some block, but it **can NOT prove non-inclusion**.

You need all block headers in order to verify the Merkle proof.
A valid proof will match exactly one block header in the header chain of the blockchain you're verifying against.
If there are no matches, then the proof is invalid for the blockchain you have headers for.
It could still be a valid proof for some other blockhain (like a fork of Bitcoin, and with exact same header format & Merkle tree computation).

> **Comments:**
> **username_0**: Thanks. I don't get the point of SPV then. Doesn't a light client also need a proof of non-inclusion? What would a light client do if the merkle proof fails?  
> **username_1**: @username_0 The merkle proof wouldn't fail (if it does, the client could show an error to the user, who could get suspicious). Instead, a server can just claim there is no transaction, so there isn't even a proof to give. And the result would be that the client doesn't know about a transaction. The solution is either trusting the server, querying multiple servers, ignoring this failure mode, or using a different architecture (e.g. not using SPV at all, and e.g. using a full node wallet).  
> **username_0**: Thanks @username_1. I don't get why SPV is 'marketed' the way it is then. In my opinion  a client NEEDS to know if a transaction was not included. Querying multiple full nodes makes sense, but even then I guess it's not fully trustable. Ignoring  the failure just means accepting the transaction was either included or not included, which would be the same as not querying at all. Connecting to a trusted full node seems the only way. But SPV was invented so no trusted full nodes are required, if I got it right. Has Satoshi not taken this into consideration, which seems weird?  
> **username_1**: It's hard to speculate about the intentions of someome who disappeared a decade ago, as we have no idea about their reaction to evolved understanding since. The SPV design as presented in the white paper just fundamentally doesn't work (it relies on fraud proofs for security, but misses that attackers can always withold data that would let someone disprove it). The SPV protocol that was actually implemented on the P2P layer (BIP37) came years after Satoshi disappeared, and its independent problems (the one you point out, but even more its privacy) became clear even later than that.  
> **username_0**: Thanks for all the insights @username_1. I've been studying bitcoin for 2 weeks now and started reading about merkle trees and SPV last week. I always had the impression that it does not make a lot of sense the way it was described and I was sure that I must be missing something. It's just incredible that it was not obvious for the developers from the very beginning. Now I am wondering why merkle roots are used in the block header and not just a hash over all transaction hashes, or something alike. Do some full nodes get rid of the transaction data itself and inly keep the headers?  
> **username_1**: Yes, it's possible to run a node that doesn't keep the block data (called a pruned node), but that's not incompatible with just hashing the list of transactions either. Truth is, the protocol uses Merkle tree simply because it always has (and likely because the system's creator envisioned SPV to be used differently than it is today). Unless there is an *extremely* good reason to change it, there is no way such an invasive protocol change would happen. At worst, Merkle trees are slightly slower than using a flat list of hashes. At best, the inclusion proofs are useful somehow. No harm done.  
> **username_2**: FWIW Satoshi imagined SPV to be used when someone pays you and wants to directly prove to you that he paid you, and he imagined here something like Electrum protocol: "The simplified payment verification in the paper imagined you would receive transactions directly, as with sending to IP address which nobody uses, or a node would index all transactions by public key and you could download them like downloading mail from a mail server." -- https://www.bitcoin.com/satoshi-archive/emails/mike-hearn/9/#selection-25.149-25.1252  
> **username_0**: Thank you @username_1 and username_2, very useful information. The thing is that almost everyone providing information about Merkle Trees and SPV in bitcoin found on the www take it for granted that merkle trees are absolutely necessary and do not question their usefulness at all. It's hilarious how they repeat everything they heard like parrots which no questioning at all. Even people that provide courses. Thanks again guys, very appreciated.  
> **username_1**: I think there is a possibly important security property you get with inclusion proofs without exclusion proofs, which you wouldn't have without: when querying multiple servers, it now suffices that one honest server gives you all transactions (or, alternatively, all servers together give you all transactions). Without inclusion proofs, if multiple servers gave you distinct things, you'd have no idea which one to believe. It's certainly not a clear-cut "this is sufficient", but it is a substantial improvement still.  

---

