Defense against 0/Unconfirmed double-spending

[etotheipi]

I hear a lot about how small point-of-sale (PoS) transactions are not possible, because it's too unsafe to accept them at the "0/Unconfirmed" state.  However, I am not sure why this has to be a problem, and so far, I haven't been able to find any discussion about this.  If my assumptions are correct, anyone can very reliably defend against a 0/Unconfirmed double-spend with nothing more than a simple client modification.  Worst case, a slight protocol modification could make this attack vector nearly impossible.    I will describe the assumptions and attack vector, and then the solution after that.


Assumptions:

• When I broadcast a transaction, it will immediately be checked by the full nodes and propagated if it is valid
• If the transaction is invalid, each full node will see it but silently reject it without forwarding it to its peers.
• If a node receives a second, conflicting transaction, regardless of whether the first one is confirmed yet, the node will consider the first one it sees to be valid and reject the second one
• Nodes will work to include the tx they see first into a block, and strike it from their queue if a new block is solved that conflicts with it.

The Attack:

Attacker puts special software on his phone which is used to pay merchants in PoS situations.  This software is designed such that whenever he initiates a transaction, the phone will broadcast the "correct" tx to half of the nodes it is connected to, and then 0.1 seconds later broadcast a second, conflicting tx to the other half of the nodes.  The second tx would be a transfer to himself using the same outputs as the first tx they saw.

The first transaction will be seen by ~70% of the network first, and the attacker hopes the merchant node will see it first, too.  Miners in this 70% will consider this to be a real tx and start trying to include it in a block.  The other 30% will see the second transaction first, consider it to be "real", start trying to include it in a block.  Both groups of nodes will receive word of the other transaction when it is passed along, but will silently ignore it because it conflicts with the first transaction they received.

For the moment, forget about the 30% chance that the merchant sees the irrelevant transaction first (as the only person inconvenienced by this is the attacker).  Assume the merchant is in the 70% group.  The merchant will see the expected tx as 0/Unconfirmed, and the buyer takes his merchandise and walks out of the store.  However, there's a 30% chance that the tx to himself ends up in the next block and the merchant's 0/Unconfirmed tx will be invalid.  In this case, the customer is already out of the store, and his transaction is anonymous enough that the merchant might just eat the $100 loss instead of trying to get it investigated.

In this sense, there is very low-risk for the buyer to do this, and might as well do it every chance he has.  Although, I don't think it's actually that low-risk, because there's a lot of things that can go wrong for the attacker if the merchant is in the other 30%.  But I don't want to discuss that here.


The Defense:

In this situation, the merchant node has a 20+ peers, and with 30% of the network being convinced the other transaction is valid, at least one of those peers will send him the conflicting transaction.  The way the client is written now, the transaction is simply rejected because it conflicts with the first.  However, I don't see why the client software can't be designed to see that the second transaction is a threat to the first tx and, instead of rejecting it, alert the user that there's a threat to one of his own transactions.   This is very reliable, because in order for the attack to have a chance of success, the attacker must broadcast the second tx immediately after the first, or else 99%+ of the network will see the first tx and the second one will be DOA and not propagate.  So, either the second tx doesn't propagate and the attack fails, or the merchant will immediately see the conflicting transaction and take appropriate action:  deny service, call the cops, keep the money, etc.  I can't think of a justifiable reason why a conflicting tx would be propagated at the same time unless there was malicious intent. 

Regardless of intent/legalities, the merchant has justification to deny service on the goods until the tx is confirmed in a block.  A customer can avoid being forced to wait for 1+ confirmation by just not attempting to double-spend.  If there's no conflicting transaction, then the first/only transaction is nearly guaranteed to be included in a future block at 0/Unconfirmed, and the customer can do nothing to reverse it.

More far-reaching, but even more reliable, the client software could be set up with a new protocol message specifically for this event.  If any node receives a transaction that conflicts with a transaction currently in the block it's trying to solve, it simply broadcasts a new "dsalert" message that contains the two hashes of the conflicting transactions in question.   Then, even if only 1% of nodes think the conflicting tx is valid and the merchant has no peers in this group, they will still become aware within seconds that they should wait for confirmation before allowing the customer to leave with his merchandise.  All that is needed is for an extra loop in the code to check freshly received transactions against all unconfirmed transactions and notify the user/peers if it sees one.

So? 
If my assumptions and assessment is correct, it would seem that a merchant doesn't actually need a third-party to avoid 0/Unconfirmed double-spending.  If the attack has any chance of success, then there would be immediate evidence that the customer is trying to defraud them.   Where am I going wrong in all this?
 

[genjix]

this opens a can of worms. i could find the entire balance of a site if i can deposit/withdraw with 0 confirms by cycling all the keys in there wallet.

also you can replace transactions using the sequence invalidating your old tx.

not a good idea

[Maged]

Assuming that we're disregarding the Finney attack, you also have to keep in mind that this opens up a large DoS hole by allowing an attacker to have the network relay multiple messages per transaction.

[casascius]

My idea of a sustainable transaction guarantee service would go like this:  a "bond" system.  customer deposits some money in a "bank", and merchants can make API calls to the "bank" to guarantee unconfirmed transaction XYZ.  The customer's balance is locked for six blocks.  

If the transaction goes through, all is well.  If not, the merchant collects from the bank, which deducts it from the customer's balance.

[samr7]

also you can replace transactions using the sequence invalidating your old tx.

Are you referering to the nSequence field of transaction inputs?

I thought that was locked out.

[etotheipi]

@genjix:  I don't see how the sequence number can be used here.  First of all, I thought that non-standard sequence numbers were disabled.  Second of all, merchants are perfectly capable of requiring customers to use 0xffffffff sequence numbers, and can see the sequence number in the 0/Unconfirmed transaction.  Any customer that doesn't agree must wait for confirmation.

@Maged:  Finney attacks are completely irrelevant here.  To execute a Finney attack you not only have to have a tremendous amount of computing power and be extremely lucky to succeed, but you risk losing the 50 BTC you could've gotten if you just submitted the block when you found it.  The transaction would probably have to be more than $1000/100BTC for an attacker to statistically break even trying to pull off Finney attack.   This discussion is about PoS transactions, such as buying groceries or getting a new printer at Best Buy.  Any non-idiot merchant would require at least one confirmation for transactions over 50 BTC, which is completely reasonable for large purchases.

Also, I'm not saying that the only way to implement this defense is to implement a new message.  You can still get 95% of the defense by just putting a check in your own client as I described.  But even if we did include an alert, wouldn't it add tremendous amount of security to the network for very little cost (maybe my understanding of what slows down the network is off)?   Each node will only broadcast/forward a 100-byte alert once when it occurs, which would be very infrequent compared to the total number of transactions.  Compare this to the 500+ bytes that had to be processed by the node to receive two conflicting transactions to begin with.  It doesn't happen often, and it's not a ton of extra data.  Plus, any node that attempts to DoS by sending out lots of conflicting tx's will be shut off anyway for spamming.

@casascius Your idea is perfectly valid.  But the goal of Bitcoin is to remove third-parties as much as possible.  Why would we pay extra fees to a third-party to handle these types of "bonds" as you describe, when we are all perfectly capable of dealing with it by ourselves?  If my idea is a fluke, then your idea is probably ideal.  But everyone would prefer to leave third-parties out of our transactions (except for the third-parties).

[jav]

First off: I agree that monitoring the network for conflicting transactions is a good way to make double spend attacks much harder. Whether or not to modify the protocol for that, is up for discussion. The idea to introduce some type of double spend alert message was also recently discussed on the mailing list, but the consensus seems to be for the moment not to introduce any extra communication for this.

I tend to agree with that, until the possible ramifications - especially in regards to possible DoS attacks - are better understood. And would, for the moment, think that an external tool can also fill this role, by being well connected to a lot of nodes and monitoring the network for conflicting transactions.

However:

Finney attacks are completely irrelevant here.  To execute a Finney attack you not only have to have a tremendous amount of computing power and be extremely lucky to succeed, but you risk losing the 50 BTC you could've gotten if you just submitted the block when you found it.  

I wouldn't dismiss the Finney attack so easily. Let's imagine this scenario: A rogue pool operator provides a little side business which accepts transactions that are conflicting with current unconfirmed transactions and will include them into the next block, should the pool be the one which finds the next block. Let's say this pool has 5 % of the hashing power of the network.

Now whenever I pay a merchant, I submit a conflicting transaction to this pool (the pool doesn't broadcast this transaction, so the network won't know about it).  Should the pool not find the next block, nothing happens. But if the pool finds the next block (a chance of 5 %) I get my money back and just have to pay some fee to the rogue pool for performing the attack. The important thing though is, that neither the pool nor I am risking anything in trying this attack.

The attack can further be made more effective, by creating the original transaction to the merchant in such a way, that it will take a long time to confirm: Use young coins, don't include enough fees etc. This will give the rogue pool more time to include the conflicting transaction into a block.

I find this attack scenario pretty realistic and as such, am not sure if I would advice a merchant today to accept zero confirmation transactions even with a double spend detection mechanism as described by you.

[etotheipi]

Ahh.  If the attacker has "friends" with any significant amount of computing power that won't re-broadcast received transactions, then the conflicting transaction will reliably be hidden from all other nodes.  I cannot see a way around this.  I guess, the only remaining thread I have here is that we are still talking about small PoS transactions.  Just as described in other places, it may still be cheaper for 7-11's to accept such transactions for small purchases, and eat the losses when it occurs.   I think if 10% of all users were attempting this attack, that would be extraordinarily high, yet that would mean only 0.5% of transactions would end up being reversed.  This is probably still cheaper than paying VISA $0.50 to process a $6.79 sandwich.  It would be easy to set a reasonable threshold (much lower than the Finney attack threshold I mentioned above) that makes this virtually insignificant for the merchant.

Of course, if it turns out to be a consistent 5% chance of success for the buyer with no risk of being caught or the rogue pool being caught, 10% of users attempting this may not be so ludicrous.   However, I don't feel like this falls into the category of a "Finney attack," since no one is holding onto the block solution at the risk of losing it.  This is just a more-advanced version of the attack I described in my original post.  But, the label is irrelevant, so I digress...

I will keep thinking on this, but it sounds like this concept has already been identified, discussed and "rejected" by people smarter than me.  I still think the DS detection is a great idea and could be included into the default client to pop up an alert when their own client detects a DS attempt, but I see that this doesn't solve the problem.

[jtimon]

Assumptions:

• When I broadcast a transaction, it will immediately be checked by the full nodes and propagated if it is valid
• If the transaction is invalid, each full node will see it but silently reject it without forwarding it to its peers.
• If a node receives a second, conflicting transaction, regardless of whether the first one is confirmed yet, the node will consider the first one it sees to be valid and reject the second one

This is in the client but not in the protocol. Others peers cannot know what tx he received first when they check the validity of his block, so it cannot be enforced by the protocol.

• Nodes will work to include the tx they see first into a block, and strike it from their queue if a new block is solved that conflicts with it.

I think miners will more likely work for the tx with a higher fee even if they've received it later.