You still haven't fixed the DoS attack this enables; there's two ways to fix it FWIW...

Back-of-the-envelope on what it would take to DoS:

Assume wimpy 10mbps (~ 1 megabyte per second) connections that you are trying to DoS.

A double-spend-flood-the-network attack lets you broadcast 100Kilobyte transactions at very low cost (attack is: broadcast a normal-sized transaction, then broadcast a max-transaction-sized (100K) double-spend version of that transaction).

To sustain this attack, you need to be able to produce 10 transactions per second.

Each transaction needs at least one at-least-fee-plus-more-than-dust-sized input, so you consume your unspent transaction outputs quicker than the transactions can be confirmed in blocks: so a DoS is not sustainable.

So if you have 36,000 unspent transaction outputs you can DoS anybody connected to the network with a 1Mbps or slower connection for one hour.

"meh"

You'd need 36 million UTXO's to try to DoS nodes with gigabit ethernet connections for an hour. "good luck with that"

If somebody did manage to successfully mount this attack, worst case they would slow down part of the network for a limited amount of time; I doubt most nodes would even notice something was happening (because the attacker's transactions will get mixed in with normal transaction traffic). The network regularly takes more than an hour to confirm a transaction, just because of block-finding variability.

You know, the phrase "Don't stop your opponent when they're in the middle of digging themselves into a hole." comes to mind. Especially when in this case the hole you're digging happens to be right where I needed a basement for my new house.

ACK

With this change in wide use, the probability of a merchant suffering the mining of an adverse double spend will be inversely related to the amount of time he decides to watch for a relayed double spend before delivering the goods. The rest is just numbers, PROVIDED miners adhere to mining the first spend seen.

Any kind of transaction replacement would create a game for attacker to wait a little while (merchant timeout), but not too long (next block), before broadcasting second spend.

@dgenr8 I don't want to follow that logic too far down the rabbit hole. There are valid use cases for transaction replacement.

Also, now that I've actually looked at the code, I see two implementation-specific DoS attacks above and beyond the problems fundamental to this idea:

1. The double-spent transactions don't end up in the mempool, so they fail AlreadyHave() in the "inv" message processing. Since we don't have them, next stop is pfrom->AskFor(inv), which adds them to the size-limited mapAlreadyAskedFor. Unfortunately that is limited to 50,000 entries, so if it rolls over we'll waste bandwidth re-asking for those double-spending transactions all over again. This shouldn't be too much of an issue, as we wouldn't resend those transactions, but...

2. Because the double-spend detection is based on a bloom filter which is cleared with 1/1000 probability on every hit if I have enough double-spends to exceed that limit, and subsequently the percolation threshold of the network, I can re-double-spend outputs over and over again. Or even worse, nodes in the network might resend those transactions in a big loop if things get bogged down enough and the attack will self-propagate.

@dgenr8 So do us all a favor and add a simple rate-limiter to the RelayDoubleSpend() function. You can copy the design of the free transaction rate limiter. (

@gavinandresen Notice how this is a good example of why actually testing against real attacks is valuable.

With this change in wide use, the probability of a merchant suffering the mining of an adverse double spend will be inversely related to the amount of time he decides to watch for a relayed double spend before delivering the goods. The rest is just numbers, PROVIDED miners adhere to mining the first spend seen.

::sigh:: No opinion currently on the rest of it (I don't have time at the moment to investigate the implementation specifics), but you're arguing for this with an incorrect argument here. E.g. Finney attack, and the fact that miners already do not mine the first spend seen (~all mine the first that they accepted, not seen, and there is already some hashpower that mines highest fees).

This kind of bad argument makes me uncomfortable and it makes it harder for me to objectively evaluate the implementation on its own merits when I know its proponents are exaggerating its benefits.

@petertodd Is this what you had in mind? Have you got any scripts that might help test this?

@petertodd Doesn't rate-limiting respend relay give attacker a way to silence relay before executing his real double-spend? Contrast with free transactions where antagonist wants his transaction relayed. This is the opposite.

@gmaxwell This change is concerned with countering race attacks on merchants accepting unconfirmed transactions. I don't think it helps against Finney or any attack requiring hash power.

It implements one of the three recommendations ("5.3 Communicating Double-Spending Alerts Among Peers") made by the research I am aware of. The other two recommendations are a merchant listening period and merchants being well-connected.

@dgenr8 could you add a note about that with reference to https://github.com/bitcoin/bitcoin/blob/master/doc/release-notes.md

@petertodd To your concern about bloom filter reset: a DoS attack on a single node runs into the problem that its peer nodes have different randomized bloom filters which will not propagate repeat respend transactions at the moment attacked node's filter is reset unless another 1/1000 hurdle is passed, and so on.

Bloom filter states in adjacent peers might be too similar though. State depends on node startup moment and subsequent respend traffic seen. Perhaps the first clear() should be randomized to occur after U(500,1500) insertions or something like that.

Next commit adds support for immediate UI notification when wallet sees a respend that affects it.

@sipa confirmed via IRC that pull tester failed because of broken tests on git head. Hopefully auto-test will be re-run when it is fixed.

ACK from me. better is better, and this is better than the current behavior.

Is this still alerting on malleability mutants (/simple resignatures that sign the same inputs and have the same outputs)?

@gmaxwell Any wallet transaction with conflicting spends is highlighted.

@dgenr8 then it becomes trivial for a network trouble-maker to make every transaction turn up red. I don't think we should do this. Beyond it being a nuisance if it frequently cries wolf users will be told to ignore it.

A "double spend" that continues to pay you as much as the listed payment should probably not trigger the alert. And especially third parties should not be able to trigger the alert.

I would like to see some sort of alert, even if triggerable by 3rd parties, but perhaps something more discrete than the red background. It's still nice to know about, and can be a factor in deciding whether to accept a transaction. The indication could be as discrete as the graphic showing the number of confirmations, perhaps an exclamation mark...?

@gmaxwell @laanwj Ok, we want a new distinction - that of a transaction whose only conflicts, re-signed or not, have identical inputs and outputs. And this condition would suppress red highlight and alert, and we sync metadata to those identical conflicts (a single respent input triggers current SyncMetaData).

Adds respend txids to RPC output and adds -respendnotify hook for immediate user-defined action when a double-spend is observed.

I'm running a mainnet node on 0.9.0 + this branch.

Connect some clients to it and double-spend yourself, if you're in the mood. If it works maybe you can add another respend-relaying node to the list.

In the last 10 days, node has relayed just over 50 respend attempts per day.

As an example, today it tried to warn that SatoshiBONES was being double-spent when it saw 7bd9cab732f33e375f9bf319a9d6c35275d59b941372b365e9ad2a4434533190 at 19:54:34, a standard respend with a .00002 fee bump and missing the .001 payment to merchant. The merchant-paying tx 6609ecd56281b680cd76c69b2d56f034c70eba067cbb00127fa67a42e6678512 was seen at 19:53:56. The double-spend was successful, block time 19:57:32.

I've brought up a node on this branch running on riker.plan99.net but it seems that your node is unreachable, @dgenr8 ?

mike@mikeh:/bitcoin/src$ date
Wed May 7 22:11:49 MSK 2014
mike@mikeh:/bitcoin/src$ telnet 54.186.233.100 8333
Trying 54.186.233.100...
telnet: Unable to connect to remote host: Connection refused

@SergioDemianLerner Note how a scriptSig-based method really needs payment protocol support as even spending a txout with the same scriptPubKey twice can be turned into a false double-spend. With payment protocol support it works fine though and works well with scorched-earth. (though I need to fix a minor DoS attack w/ ANYONECANPAY transactions re: attackers adding useless inputs to them)

@sipa That's only true if you are trying to make zeroconf secure; if you are trying to give everyone consistent information about the double spends that exist it's better if you propagate both. The latter is what scorched-earth needs from the network.

@sipa How does that work? If you see A and then B, and you always relay A and then B, then in the absence of other information your peers will agree with you on the ordering. If they saw B and then A first, it doesn't matter what order you relay in. I don't see how it affects the likelihood of changing the perceived order for any transaction. Could you try explaining that again?

Another way to implement this is to make the double spend relay not a "tx" message but a "dtx" message. Core can treat them identically, other nodes will ignore them, and it's I think easier to see that the behaviour of the network should not change.

@mikehearn Not everyone will accept A to their mempool.

What @petertodd said, plus new nodes starting up may just see the double spend, and not the original.

@mikehearn A "dtx" message sounds like a good idea to me, it removes all risks of accidentally interpreting the transaction that was intended as a double spend as something else.

Of course as the "dtx" channel is trivially swamped we're back to the situation where the feature is useless, even for other uses like increasing fees. If we're going to go to the trouble of a separate message might as well just do scriptSig relaying and do it right.

Remember that anyone can write a "dtx->tx" message converter and deploy a few nodes doing it. I personally would as that's a more useful behaviour for the network to have.

On 2 July 2014 10:45:06 CEST, Pieter Wuille notifications@github.com wrote:

@mikehearn A "dtx" message sounds like a good idea to me, it removes
all risks of accidentally interpreting the transaction that was
intended as a double spend as something else.

---

Reply to this email directly or view it on GitHub:
#3883 (comment)

@petertodd My presumption was that "dtx" must include an automatic dtx->tx converter, in the bitcoind implementation. Otherwise you get the properties you describe. If you have not seen a "dtx", then convert it to a tx and process accordingly.

Thus, no ordering problems, and older nodes magically ignore 2nd's.

No, a "dtx" is never treated as a regular transaction, as outlined above.

If you send a double spend onwards knowing it's a double spend but not marking it as such, and the remote node already saw the first spend, then it will be ignored same as today.

The haven't-seen-first-spend-yet case should be handled. Was not referring to opposite.

You cannot assume anything about a double spend, including intent behind it. It may be a user attempting a valid recovery, or executing a branch of a smart contract.

Ah, well I think not knowing about transactions is supposed to be fixed by syncing the mempool at startup, right? But before that we need a limited/ordered mempool. So fixing this case involves the resource management/anti-DoS work.

With respect to the intent, I think under Bitcoin's current design there are no situations where a double spend of a broadcast transaction is valid. It's always a mistake or fraud. The contracts cases I know of involve double spending transactions that were never broadcast (i.e. because they are not valid).

Again with the over-assuming. You cannot assume intent behind a double spend.

Easy counter examples:

• User's transaction got relayed, but is stuck in limbo (not confirming) due to insufficient fees or some other factor. Fix is usually to double spend with higher fees.
• Payment channel (smart contract). User's refund TX races with payment channel rapidly-revised TX in at least one edge case. Refund transactions intentionally spend the same inputs as the rapidly-revised TX, to guarantee only one is valid.
• https://github.com/jgarzik/auctionpunk/ is another example of the common pattern of relying on X transactions to spend the same input(s), to guarantee that only one-of-N is valid.

There are valid cases for double spending, and you simply do not have information sufficient to judge a "good" versus "evil" double spend.

Let's dispense with the "no situations under Bitcoin's current design" hokem right now. One-of-N determination is a key use of the Bitcoin protocol -- including protocols you've helped design.

@mikehearn There isn't a "design" of Bitcoin - a decentralised network - only what's possible given the implementations on the network. Right now the "design" includes even replace-by-fee by virtue of the fact that some % of hashing power and nodes on the p2p network support it.

In any case people already do double-spends to get stuck transactions unstuck by bumping fees. Note that you'll never get mempool uniformity because nodes have different resources available.

@jgarzik Reasonable. Seems to me that "dtx" can be the same code-path as "tx"

On 2 July 2014 11:11:39 CEST, Mike Hearn notifications@github.com wrote:

Ah, well I think not knowing about transactions is supposed to be fixed
by syncing the mempool at startup, right? But before that we need a
limited/ordered mempool. So fixing this case involves the resource
management/anti-DoS work.

With respect to the intent, I think under Bitcoin's current design
there are no situations where a double spend of a broadcast transaction
is valid. It's always a mistake or fraud. The contracts cases I know of
involve double spending transactions that were never broadcast (i.e.
because they are not valid).

---

Reply to this email directly or view it on GitHub:
#3883 (comment)

@jgarzik Replace by fee isn't supposed to work, the fact that it does is a regrettable bug that we must work on, indeed this patch is part of doing that. And if a merchant sold something and then the tx was replaced-by-fee then that would certainly count as a form of payment fraud, no different to passing a bouncing cheque or forged paper currency. The fact that cheques can bounce and paper currency can be forged doesn't mean it's an intentional part of their design.

In payment channels the refund isn't supposed to be used unless one side has hung up/gone away. If the refund is used simultaneous with the last best signed tx, then one side or the other is attempting an attack or has come back online simultaneous with the channel closing and there's been a byzantine communication failure of some kind (mistake).

I don't know about the auctionpunk case, I haven't seen how that works. I'll take your word for it that this is a case where you want semi-random (?) resolution of which transaction is the winner.

@petertodd What do you think the white paper is if not an explanation of the design? The fact that our implementation doesn't always meet the design goals doesn't mean there's no design.

W.R.T mempool resource uniformity, that's certainly something we'll want to tackle in future, if we end up with mempools routinely overflowing. But if we go overcapacity like that I'd expect the transactions that are constantly losing to eventually go away. There's no point in using Bitcoin in such a way that you know you'll constantly fail to obtain the supply of the service you need. The mismatch should end up being manageable.

@mikehearn I was not referring to replace-by-fee. And in general, you seem to be trying to avoid any case that fails to fit neatly inside a pre-conceived box ascribing maliciousness to all double-spends. The primary mistake is attempting to divine any intent of a double spend, or cast a strict judgement upon the entire class. The world is not that simple.

The standard in-the-field advice for a transaction stuck in limbo, not confirming, is to respend [many of] the same inputs with a higher fee. It is effective field advice because the "stuck" transaction usually hasn't propagated well and made it to miners, and it provides 100% guarantee that the other version of the transaction will never confirm.

This is not some deployed and argued-about "replace by fee" policy but a standard workaround for the "stuck in limbo" problem that is as old as bitcoin itself.

RE mempool uniformity and synchronization, this is a topic of open debate.

RE mempool overflowing, there are already designs (#3723) and PRs (#3753) that address such issues without any need to resort to any sort of explicit mempool uniformity scheme.

@jgarzik Agreed. Anyway I'll see if I can get some time to write up a better patch after I get home if no-one else is going to write one.

@mikehearn Replace-by-fee scorched-earth can be viewed as a proposed way of meeting that white paper's design goals; coinbase reallocation/blacklisting is another way. Greenaddress's double-spend guarantees is yet another way.

Which idea(s) are best remains to be seen, but if I can make replace-by-fee effective with a few reddit/bitcointalk posts and a few hundred dollars budget that suggests that designs that assume it doesn't exist are insecure. Meanwhile the community, research and otherwise, has rejected a whole host of miner level approaches to double-spending quite thoroughly.

On 2 July 2014 11:50:26 CEST, Mike Hearn notifications@github.com wrote:

@jgarzik Replace by fee isn't supposed to work, the fact that it does
is a regrettable bug that we must work on, indeed this patch is part of
doing that. And if a merchant sold something and then the tx was
replaced-by-fee then that would certainly count as a form of payment
fraud, no different to passing a bouncing cheque or forged paper
currency. The fact that cheques can bounce and paper currency can be
forged doesn't mean it's an intentional part of their design.

In payment channels the refund isn't supposed to be used unless one
side has hung up/gone away. If the refund is used simultaneous with the
last best signed tx, then one side or the other is attempting an attack
or has come back online simultaneous with the channel closing and
there's been a byzantine communication failure of some kind (mistake).

I don't know about the auctionpunk case, I haven't seen how that works.
I'll take your word for it that this is a case where you want
semi-random (?) resolution of which transaction is the winner.

@petertodd What do you think the white paper is if not an explanation
of the design? The fact that our implementation doesn't always meet the
design goals doesn't mean there's no design.

W.R.T mempool resource uniformity, that's certainly something we'll
want to tackle in future, if we end up with mempools routinely
overflowing. But if we go overcapacity like that I'd expect the
transactions that are constantly losing to eventually go away. There's
no point in using Bitcoin in such a way that you know you'll constantly
fail to obtain the supply of the service you need. The mismatch should
end up being manageable.

---

Reply to this email directly or view it on GitHub:
#3883 (comment)

Wow, this is veering off-topic quickly...

RE: @mikehearn : suggesting version bump:

All implementations MUST handle double-spends already. If we have two transactions tx1 and tx2 that spend the same outpoints, you must, today, be able to handle receiving 'inv' and 'tx' data for both of them.

The only change this makes is that you might now get the inv/tx messages from the same peer instead of different peers. Are there implementations that care about which peer sends them which transaction data?

RE: 'dtx' message: Same argument as above. The reference implementation doesn't care where transaction data comes from, and it MUST be able to handle double-spends.

RE: writing up a better patch: okey dokey. Better is better.

Agreed. Do we really need to worry about nodes, or cooperating groups of nodes, who have decided to rely totally on the external network never to send them an unconfirmed double-spend? That kind of faulty assumption must have been punished by nature long ago.

"dtx" would be a value judgment by one node intended for others, and it could be faked.

@dgenr8 The concern is custom setups, e.g. exchanges with software that assumes Bitcoin never sends a doublespend tx without a block in between. The situation would not be "punished by nature" as the node in question is internal and trusted.

@petertodd : if such an exchange (using bitcoind as a front-end, relying on it never relaying a double-spend) jumps in here and says "no, we don't want to know about possible double-spends until we see the second spend in a block" and they had some good reason (which I can't imagine right now-- why wouldn't you want to know about the double-spend earlier rather than later?) then maybe I'd change my mind.

@gavinandresen I suspect such an exchange isn't following development as closely as they should... Anyway, good to remember to put in the release notes when this gets settled.

I agree with the "dtx" message rather than "tx" - this allows bitcoin implementations to choose whether they subscribe to double-spend messages.