2

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 @Pieter Wuille 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!

Improve this question
7
  • 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
    Commented Nov 22, 2023 at 15:28
  • 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
    Commented Nov 22, 2023 at 15:37
  • @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
    Commented Nov 22, 2023 at 16:05
  • 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.
    – Pieter Wuille
    Commented Nov 22, 2023 at 16:07
  • 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).
    – Pieter Wuille
    Commented Nov 22, 2023 at 16:43

1 Answer 1

Reset to default
3

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

Improve this answer
9
  • 1
    @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
    Commented Nov 22, 2023 at 16:45
  • 2
    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
    Commented Nov 22, 2023 at 17:21
  • 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.
    – Pieter Wuille
    Commented Nov 22, 2023 at 22:21
  • 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." -- bitcoin.com/satoshi-archive/emails/mike-hearn/9/…
    – bca-0353f40e
    Commented Nov 23, 2023 at 6:18
  • 2
    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
    Commented Nov 23, 2023 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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