Quote from: Gavin Andresen on September 06, 2012, 04:01:09 PM

Sergio:

Is a new type of message necessary?

How about just making the transaction relay rules:

1) If the transaction has inputs that conflict with one already in the best blockchain, drop it.
2) If the transaction has inputs that conflict with another transaction in the memory pool, and it is the first such conflicting transaction, check the new transaction's signatures and if they're OK mark the memory pool transaction as "saw a double spend". Then relay the conflicting transaction (but don't otherwise remember it).

Rule (1) is to prevent an attacker from taking a bunch of her old, already-in-the-blockchain outputs and trying to generate a "double spend alert storm" by sending bogus double-spend attempts for them.

Rule (2) is to limit the amount of network traffic / signature checks an attacker can create to be twice what they can generate today (attackers can, and do, try to flood the network with transactions, but transaction fees and the free transaction relay policy keeps them in check).

The GUI/RPC should definitely show attempted-double-spend memory pool (0-conf) transactions as "BEWARE".

I think those rules will flood the network with the double-spend attempt, alerting merchants/users that something odd is happening. Without making it possible for an attacker to get the network flooded with gazillions of double-spend alert messages.

+1 !!

For my BiRD client, I've tried analyzing different ways to detect double spending in the following scenario: "bad" customer at brick-and-mortar store uses a POS to pay for goods. POS communicates with BiRD (to get unspent txs, make & sign a tx), BiRD talks to 1 or more normal full bitcoin nodes to relay the new tx. "bad" customer sends at the same time (using his smartphone or whatever, connected to other nodes) the same coins to another address he owns. Store accepts 0 confirmations.

With the current implementation of dropping double-spend txs, and with only 1 connection to the Bitcoin network, the double-spend attempt is NEVER seen by my BiRD client, which is bad. So it would require something along the lines: send tx out on 1 node, listen on other nodes if they all signal this same tx (or instead the conflicting one).

Then I read this paper too on the "timing attack": Double-Spending Attacks on Fast Payments in Bitcoin, which further seems to complicate things (you'll need to connect to many nodes to get some chance of seeing conflicting txs).

BUT if Gavin's rule 2 from above is slightly modified like this:

2a) If the transaction has inputs that conflict with another transaction in the memory pool, and it is the first such conflicting transaction, check the new transaction's signatures and if they're OK mark the memory pool transaction as "saw a double spend". Relay the conflicting transaction as usual and remember it as long as the memory pool transaction.
2b) If the transaction has inputs that conflict with another transaction in the memory pool, and it is NOT the first such conflicting transaction, drop it. (This can be easily checked as the first conflicting tx is remembered)

THEN the "isolation" of a victim node (as shown in the paper) is no longer possible, even when it is listening to only 1 (trusted) node.

So at least the timing attack is no longer useful: a merchant can wait for example 10 seconds before accepting the tx. If in that time no other conflicting tx is seen, most nodes will have merchant's tx.