About proposed double-spend alerts in "Two Bitcoins at the Price of One"

[Sergio_Demian_Lerner]

Some months ago there was a enlightening debate about the paper "Two Bitcoins at (sic) the Price of One? Double Spending attacks on Fast Payments in Bitcoin." (http://eprint.iacr.org/2012/248.pdf) in the thread https://bitcointalk.org/index.php?topic=79090.0;all.

I recommend anyone who is dealing with 0/unconfirmed payments to read this thread.

The authors of the paper suggest using an alert system to tell nodes if a double-spend has occur. Some have critic the double-spend alert system of being another vector of DoS attacks. First I will describe a modified double-spend alert system does do not suffer from abuse by spamming alerts.

The paper proposes sending (Tx1,Tx2) whenever Tx1 and Tx2 are valid and they share a prevout.
(Tx1,Tx2) may be very large and and it's easy to generate a high number of alerts by combinations of prevouts.

I think the concept of double-spend alert system is not flawed and may add a new layer of certainty for merchants using 0/unconfirmed.
Here is my proposal.

Proposal 1)

Suppose Tx1 refers to the provout p in its input k, with signature script Sign1_p,k, that signs the hash of Tx1 for k, hash1_k
Suppose Tx2 refers to the provout p in its input j, with signature script Sign2_p,j, that signs the hash of Tx2 for j, hash2_j

EDITED: If Tx1 and Tx2 have the same outpoints (addresses and amounts) then no alarm is sent since only fees or previns may have changed. (thanks Etlase2 for pointing out this problem)

Obviously Sign1_p,k != Sign2_p,j and hash1_k !=hash2_j

A node that receives Tx1 and Tx2 builds the alert A=(p,Sign1_p,k,hash1_k, Sign2_p,hash2_j) and sends it to its peers.

This message is, on average, 36+139+32+139+32= 378 bytes
Alerts with length over 512 bytes should be ignored. Merchants can simply accept only standard transactions for 0/unconfirmed.

When a node receives a well-formed alert message A=(p,s1,k,h1, s2,h2)

1) If p is already maked as "double-spended", the client ignores the alert.
2) If p does not yet exists in a block, the client ignores the alert.
3) Alert signatures are checked. If invalid, the client ignores the alert.
4) Mark the outpoint p as "double-spended".
5) Send the alert to the remaining peers.

When a new block arrives, all double-spend marks are removed from previous outpoints.

Also, when a transaction Tx3 is received and refers to a previously marked outpoint, the transaction is ignored and not relayed, no new alert is sent.
(note: The LockTime field was not taken into account in this description)

The crypto part of system works because signatures are non-malleable, so the sole existence of a signature of something, even if the content is unknown, is enough proof.

Proposal 2) Also I'll propose still another layer of security, but this requires a hardfork: If a miner finds two transactions that spend the same prevouts (edit: but have different outputs), both of them can be included in a block (always one after the other), and all the money from prevouts in conflict is given to the miner, the remaining prevouts are untouched. Who will dare to try a double-spend?

Obviously all this measures do not apply to a Finney attack, which is still possible.


Best regards,
 Sergio.

[Etlase2]

Proposal 2) Also I'll propose still another layer of security, but this requires a hardfork: If a miner finds two transactions that spends the same prevouts, both of them can be included in a block (always one after the other), and all the money from prevouts in conflict is given to the miner, the remaining prevouts are untouched. Who will dare to try a double-spend?

People who accidentally double spend which would be fairly easy when multiple devices using the same wallets are common, as well as unconfirmed transactions that never get approved because they have no tx fee and the user eventually creates a new spend (oh I'll include it now that I get the money!).

But I agree that some kind of alert system should be in place especially for in-person transactions.

[Sergio_Demian_Lerner]

People who accidentally double spend which would be fairly easy when multiple devices using the same wallets are common...

One possibility is to "flag" transactions for 0/unconfirmed. Suppose each transaction has a "FAST" bit stored somewhere.  If two transactions are received referring to the same prevout and at least one has the FAST=TRUE, then the alert is sent. If both have FLAG=false, then no alert is sent. Merchants must accept only transactions with FAST=TRUE, for 0/unconfirmed.

For the proposal 2, people using multiple devices for the same wallet should avoid using FAST=TRUE and 0/unconfirmed altogether.

.. as well as unconfirmed transactions that never get approved because they have no tx fee and the user eventually creates a new spend

Originally Bitcoin had the field nSequence in previns for this purpose, but now is not checked.

Nevertheless, with the proposal 1, if you just wait 2 blocks to be broadcast, you're sure that the marks in prevout have been erased, so you should be able to send a new tx without problem.

But anyway there is a simple modification to prevent this problem:

The code that checks if Tx1 and Tx2 are trying a double-spend is skipped if both of them have the same outpoints with the same amounts. (I will edit the main post to reflect this new check)

Best regards

[makomk]

People who accidentally double spend which would be fairly easy when multiple devices using the same wallets are common, as well as unconfirmed transactions that never get approved because they have no tx fee and the user eventually creates a new spend (oh I'll include it now that I get the money!).

What's more, this gives miners an incentive to collude in delaying large transactions with no fee or a small fee in the hope that the sender will try resending it with a fee, allowing them to confiscate all the money. That's probably not a good thing.

[Sergio_Demian_Lerner]

People who accidentally double spend which would be fairly easy when multiple devices using the same wallets are common, as well as unconfirmed transactions that never get approved because they have no tx fee and the user eventually creates a new spend (oh I'll include it now that I get the money!).

What's more, this gives miners an incentive to collude in delaying large transactions with no fee or a small fee in the hope that the sender will try resending it with a fee, allowing them to confiscate all the money. That's probably not a good thing.

Yes, that's why I added to the algorithm that if Tx1 and Tx2 have the same outputs with the same amounts, then the miner cannot claim any prize, and the block is invalid.

[etotheipi]

People who accidentally double spend which would be fairly easy when multiple devices using the same wallets are common, as well as unconfirmed transactions that never get approved because they have no tx fee and the user eventually creates a new spend (oh I'll include it now that I get the money!).

What's more, this gives miners an incentive to collude in delaying large transactions with no fee or a small fee in the hope that the sender will try resending it with a fee, allowing them to confiscate all the money. That's probably not a good thing.

Yes, that's why I added to the algorithm that if Tx1 and Tx2 have the same outputs with the same amounts, then the miner cannot claim any prize, and the block is invalid.

The client won't always construct a "repeat" transaction the same way.  If it's multiple devices, they will probably use different change addresses.  Sometimes it's just the user re-creating a tx that didn't go through and the client will reconstruct using different inputs and a different change address.  If you assume that the one output that changed is the change address, well that could just be someone keeping their change address the same but swapping the intended recipient.  In other words, there's no way to distinguish legit double-spends from accidental.

Btw, I actually implemented a double-spend detector in Armory.  Basically to provide a warning that conflicting transactions were received and it's especially important for the user to wait for 6 confirmations.  Besides the fact that it doesn't in Armory (because it goes through the Satoshi client which drops any conflicting transactions so Armory never sees them), gmaxwell pointed out a very potent argument about how "bad people" will get around this.

(1) Someone sets up a special (dark) mining pool which controls some proportion of the global hash rate (say 5%). 
(2) This pool does not forward any transactions.
(3) Users who pay to be part of this pool get an app that, for every tx they send, it also sends the pool a replacement transaction to start mining
(4) The recipient will never see the double-spend because it doesn't get forwarded
(5) 5% of the time they succeed
(6) Because there is no extra effort to do this for one transaction vs thousands, there will necessarily be services that pop up and can offer people this service for dirt cheap.  Not to mention they get money for mining. 

In other words, it's not unreasonable to believe, that large swaths of users would contribute to such a pool because they get 5% off everything and it hardly costs the pool anything once it's setup.

It's not the same effectiveness as double-broadcasting regularly, but it is a credible equilibrium point of the system/economy.

[Mike Hearn]

Yes, industrialized Finney attacks are an issue but I don't think that means there's no point in doing the double spend broadcasts.

For one the effectiveness of that model rather depends on how much it costs you to take part in the pool vs how often you "win" at unidentified zero-confirm transactions (which are unlikely to be for large sums of money at any rate).

When I think about my own Bitcoin usage, temporarily setting all morality aside it still wouldn't be worth taking part because I just don't make enough transactions that auto-Finney-attacks would be useful.

[kjj]

Also, the existence of such a thing will finally force people to stop accepting 0-confirm transactions, hopefully.  Honestly, just the threat of it should be enough, but apparently it is not.

Over time, as bitcoin matures, services will spring up to handle the transaction risk.

[Mike Hearn]

There's nothing wrong with accepting zero confirm transactions as long as you have a solid understanding of the risks.

[Sergio_Demian_Lerner]

So I see that proposal 2 is not a good solution, because of multiple devices.

Still proposal 1 is an effective layer of protection.

Did anyone found any problem in it? If not, then I may write a BIP.
Note that marks on prevouts are cleared every 10 minutes, so any problem regarding sending double-spends by mistake just fades away quickly.

Regarding transactions with 0 confirmations, is a matter of risk management, as Mike says.

[Gavin Andresen]

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.

[Mike Hearn]

How does "relay but don't remember" work? Just blast it out without an inv? If you want to use the inv protocol to reduce bandwidth usage you have to keep it around, at least for a while, so you can serve it when requested with getdata.

[Gavin Andresen]

Right, you do have to remember them for at least a little while...  Replace "relay but don't remember" with "relay and forget as soon as possible."

[Sergio_Demian_Lerner]

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.

Two problems I see:

(A) I don't like the idea of giving the attacker more power.

For example, suppose the attacker has a connections to the main miners.
First he sends a small transaction to the network (or directly to a miner). This one travels fast.
Then he sends a double spend transaction of 100 Kbytes long to the network, with a high fee. Every node start relaying this double spend. As this transaction is huge, is travels very slow trough the network, consuming a lot of bandwidth.

The attacker is sure that the second one won't be included in a block because miners will reject it.

So miners should change the algorithm to choose the right transaction when a double-spend is detected: choose the one that pays more fees.

(B) How to allow a honest user to replace a transaction because of, for example, low fees specified in the first one?

You have to mark transaction in the pool to be automatically removed after some time, with some type of priority queue structure to allow fast search and removal of old transactions.

Marks in prevouts are lightweight, and easy to wipe out. Just erase them all every 10 minutes.


Best regards,
 Sergio.

[Gavin Andresen]

So miners should change the algorithm to choose the right transaction when a double-spend is detected: choose the one that pays more fees.

Good point. I assume that miners will choose to mine the version of a transaction with the highest fee-per-kilobyte, since that will give them the best profit, but actually changing the code to implement that policy has been controversial when I've brought it up before.

To fight transaction spam, I think the relaying logic will need to get smarter, too.  A large, expensive-to-verify double-spend should be way down on the "stuff that should be relayed when there is enough bandwidth" list.

(B) How to allow a honest user to replace a transaction because of, for example, low fees specified in the first one?

You have to mark transaction in the pool to be automatically removed after some time, with some type of priority queue structure to allow fast search and removal of old transactions.

Marks in prevouts are lightweight, and easy to wipe out. Just erase them all every 10 minutes.

That's a different issue, and a new feature. I think the best way to implement that feature is "child pays for parent" (see https://github.com/bitcoin/bitcoin/pull/1647 for a proposed implementation), and then the user can broadcast a high-fee pay-to-self child transaction to get the parent accepted into a block.

[Mike Hearn]

Right. Allowing people to raise fees by calculating them recursively was brought up a long time ago, but it only recently floated near the top of the todo list.

[Sergio_Demian_Lerner]

I still haven't heard any big problem with proposal 1, a new alert message in the form (p,Sign1_p,k,hash1_k, Sign2_p,hash2_j)

Pros:

- Doesn't give the attacker more power (more bandwidth)
- No modification to the proven protocol of rejection of double-spends
- Minimal interaction with the rest of the protocol
- Does not make worse the problem of "double-spend by mistake".
- Very low bandwidth usage, just 512-byte alerts
- Cannot be source of DoS: a maximum of one alert can be generated for any existing outpoint every 10 minutes.
- Backward compatible: Old clients simply discard the new message type
- Very clean implementation can be coded...

Con:
- It requires more coding than Gavin solution (but Gavin solution is, I think, very error-prone to code well)

[Gavin Andresen]

What stops an attacker from pre-generating tens or hundreds of thousands of alert messages (for tens or hundreds of thousands of their own transactions that the previously put into the chain) and then sending them to the network all at once?

Goal would be to keep the network busy checking the alert signatures.

[Sergio_Demian_Lerner]

What stops an attacker from pre-generating tens or hundreds of thousands of alert messages (for tens or hundreds of thousands of their own transactions that the previously put into the chain) and then sending them to the network all at once?

Goal would be to keep the network busy checking the alert signatures.

Interesting. For each new double-spend the attacker needs a previously unspent outpoint (field p).
So the attacker would need first to own 100K outpoints (impossible without paying a huge amount in fees).
Also each message takes 8 ms to be sent though a 64 Kbytes/s connection, so CPUs won't be blocked in signature checks.
Alerts with invalid signatures are not relayed, so signatures must be valid.

Anyway I do think this may be a problem.

Two possible solutions:

1. The easy. Only check and relay an alert message for p if we already have a transaction that uses p in the memory pool
(the attacker would need to pay fees for each alert message in order to make the attack possible)

2. After n double-spends have been detected for outpoint p, disable the use of p in transactions for 2^n blocks (don't relay a transaction that uses p)
This reduces exponentially the benefit of such attack to the attacker.

[bfever]

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.