How does an SPV node verify an unconfirmed transaction?

Question

Alice pays Bob 1 BTC with a simple pay-to-address type transaction. Three seconds after Alice broadcasts her transaction, Bob's Simplified Payment Verification (SPV) wallet displays a message saying the transaction was received.

How exactly does this work? What checks, if any, does Bob's wallet do before showing the message?

A lot of the SPV documentation I've seen makes vague statements about "height" vs. "depth" verification. These discussions aren't helpful because they don't describe the actual process.

The clearest statement I've found appears on the BitcoinJ documentation (under "Pending transactions"):

... However, in SPV mode the only reason you have to believe the transaction is valid is the fact that the nodes you connected to relayed the transaction. If an attacker could ensure you were connected to his nodes, this would mean they could feed you a transaction that was completely invalid (spent non-existing money), and it would still be accepted as if it was valid.

https://bitcoinj.github.io/security-model

In other words, complete trust is placed in the network to only relay valid transactions. The network isn't supposed to relay double spends or transactions spending bogus coins. Therefore, the relay, and only the relay, vouches for the validity of the unconfirmed transaction. If an attacker can control your internet connection (through a WiFi hotspot, or VPN, for example), then he can send you fake unconfirmed transactions and rip you off.

Is this how SPV nodes handle unconfirmed transactions?

It seems like an SPV node could do better. For example, couldn't Bob's wallet verify that the coins being spent existed at one time? Request the Merkle path and transaction for all outpoints referenced in the unconfirmed transaction's input list. If the parent transactions can't be found, Alice's transaction is trying to spend bogus coins.

Could a similar mechanism be used to further verify that Alice's unconfirmed transaction doesn't double spend coins?

If neither of these checks are possible today, what would need to happen for them to become possible?

Answer 1

First, nobody should rely solely on unconfirmed transactions. This applies equally to full node operators and SPV wallet users.

Bob's wallet verify that the coins being spent existed at one time? Request the Merkle path and transaction for all outpoints referenced in the unconfirmed transaction's input list.

Yes, that can be done now. I doubt any wallets do that now, as with the current P2P network design it would be slow and not definitive.

It would be slow because the network protocol does not allow requesting arbitrary transactions. In order to get a particular transaction, you have to set a bloom filter and then keep requesting merkle blocks until you find the block that contains the transaction. In the case of a negative search, this would require requesting a merkle block for every block on the block chain, or downloading about 32 MB of data and forcing your full node peer to scan its entire about 30 GB block chain.

It would not be definitive because anyone can withhold data from an SPV node. For example, the full node that notifies the SPV node about an unconfirmed transaction can include merkle blocks to each of the inputs, proving that they exist on the block chain. But the full node can't include any proof that those inputs haven't been previously spent on the block chain.

When some form of UTXO commitments gets implemented, it will become possible for full nodes to prove to SPV nodes that an input was unspent up to the tip of the SPV node's header chain. However, it that still doesn't offer any guarantee that the transaction won't be double spent anyway. (In short, it decreases the full node's ability to lie without making unconfirmed transactions any more secure.)

Could a similar mechanism be used to further verify that Alice's unconfirmed transaction doesn't double spend coins?

No, this is fundamentally impossible because an unconfirmed transaction is just data. Alice could create and broadcast transaction T paying Bob and then create transaction T' (a double spend) that she keeps secret on her hard drive. Because it's a secret, you don't know about T', but it's still a valid double spend.

There are various proposals to allow full nodes to relay information about broadcast double spends, such as Gavin Andresen's relay first double spend or Peter Todd's replace by fee, but none of these can provide a method to verify there are no double spends in existence for a particular input.

It's also possible to change how Bitcoin verifies signatures to require either mathematical ECDSA one-show signatures or consensus one-show signatures. This wouldn't stop double spends, but it would mean that anyone who had two signatures for the same input could create a third spend taking all the money for themselves. (E.g. if a miner running a full node received T and T', it could create and mine T3 paying the full input value to itself.)

This would obviously disincentivize creating public double spends, but it wouldn't stop them. Worse, there are some easy ways around the disincentives for systematic fraudsters, but everyday users like you and me who occasionally need to make double spends for legitimate reasons (e.g. because a transaction isn't confirming) couldn't safely make them any more.

Answer 2

This is a known problem and a lot of it has been outlined in this bitcoin.it article. Essentially, what you're relying on when you use an SPV wallet like Electrum is that by using many random servers and certificates, you minimize the risk of being fooled on an unconfirmed transaction.

There's an interesting proposal called "Unused Output Tree" which would make scenarios like yours require less trust.