Relay and alert user to double spends

dgenr8 commented at 7:51 pm on March 16, 2014: contributor

Rebased version of #3354.

Instead of dropping double-spend transactions, relay them to peers. This is crucial to allowing all parts of the network to detect double-spend attempts as quickly as possible, i.e. reducing the “confirmation” time for buying coffee to a time on par with credit card transactions. Only the first respend seen is relayed.

I successfully completed a primary test running 3 copies of bitcoin-qt in regtest mode with this patch applied, connected in a node1-newtorknode-node2 configuration.

I used the rawtransaction API for steps 2 and 3, but with -salvagewallet and a single funding transaction, tests would be possible that did not require rawtransactions.

Still TODO: Regression test plan

Primary Test Details Step 1

Send transaction from node1 to a node2 address
* Transaction is relayed through networknode, to node2
* Transaction appears in node2 wallet

Step 2

Restart node1 with -salvagewallet (so it forgets about 1st spend)
Send new transaction using same input (first double-spend), using rawtransaction API
* Transaction is relayed through networknode, to node2
* node2 does not accept the double-spend into its mempool and it does not appear in node2 wallet

Step 3

Restart node1 with -salvagewallet again
Send transaction using same input (second double spend), using rawtransaction API
* Transaction is not relayed through networknode

Step 4 One more test for good measure

Restart node1 with -salvagewallet again
Using regular UI (not rawtransaction API), send entire wallet balance to node2 (third double spend). This included additional inputs besides the spent one.
* Transaction is not relayed through networknode

petertodd commented at 2:00 am on March 17, 2014: contributor

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

gavinandresen commented at 12:15 pm on March 17, 2014: contributor

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.

petertodd commented at 2:45 pm on March 17, 2014: contributor

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

dgenr8 commented at 1:24 am on March 18, 2014: contributor

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.

jgarzik commented at 1:51 am on March 18, 2014: contributor

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

petertodd commented at 4:09 am on March 18, 2014: contributor

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:

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…
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. (https://github.com/bitcoin/bitcoin/blob/5b6e9811fa64540c8feecc24f11fa867392f262f/src/main.cpp#L912) Make sure you make that rate limiter adjustable by a command-line option. @gavinandresen Notice how this is a good example of why actually testing against real attacks is valuable.

gmaxwell commented at 8:59 pm on March 18, 2014: contributor

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.

dgenr8 commented at 2:36 am on March 20, 2014: contributor

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

dgenr8 commented at 3:41 am on March 20, 2014: contributor

@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.

dgenr8 commented at 9:12 pm on March 20, 2014: contributor

@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.

ghost commented at 9:27 pm on March 20, 2014: none

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

dgenr8 commented at 4:14 pm on March 22, 2014: contributor

@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.

dgenr8 commented at 10:32 pm on March 24, 2014: contributor

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

capture

dgenr8 commented at 2:41 pm on March 25, 2014: contributor

@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.

dgenr8 renamed this:
~~Relay first double spend transactions (rebase)~~
Relay and alerts for double spends (rebase)
on Mar 25, 2014

dgenr8 renamed this:
~~Relay and alerts for double spends (rebase)~~
Broad relay and user alerts for double spends
on Mar 25, 2014

dgenr8 renamed this:
~~Broad relay and user alerts for double spends~~
Relay and alert user to double spends
on Mar 26, 2014

gavinandresen commented at 12:56 pm on April 3, 2014: contributor

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

gmaxwell commented at 2:59 pm on April 3, 2014: contributor

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

in src/wallet.cpp: in 43d6ff23a2 outdated

261@@ -262,42 +262,6 @@ bool CWallet::SetMaxVersion(int nVersion)
262     return result;
263 }
264 
265-void CWallet::SyncMetaData(pair<TxSpends::iterator, TxSpends::iterator> range)

laanwj commented at 3:53 pm on April 3, 2014:

I don’t entirely understand why there is no more use for this function. The reason it was added was to make sure that the ‘malleated’ versions of transactions take over the metadata (such as the payment request data) of the original transaction. Is this now handled in another way?

dgenr8 commented at 5:50 pm on April 3, 2014:

@laanwj Malicious respends affecting the wallet will be tracked by the wallet db, and we don’t want to give them that treatment.

laanwj commented at 6:44 am on April 4, 2014:

But what about genuine mallleated clones (same transaction but different txid)? They should still have that treatment. I don’t think it is valid to remove this for every case.

dgenr8 commented at 5:49 pm on April 3, 2014: contributor

@gmaxwell Any wallet transaction with conflicting spends is highlighted.

gmaxwell commented at 5:56 pm on April 3, 2014: contributor

@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.

rebroad commented at 3:47 am on April 4, 2014: contributor

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…?

dgenr8 commented at 12:55 pm on April 4, 2014: contributor

@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).

dgenr8 commented at 11:18 pm on April 9, 2014: contributor

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

dgenr8 commented at 5:07 pm on April 11, 2014: contributor

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.

dgenr8 commented at 4:44 am on May 1, 2014: contributor

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.

mikehearn commented at 6:12 pm on May 7, 2014: contributor

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

dgenr8 commented at 9:02 pm on May 7, 2014: contributor

@mikehearn hmm, bitcoind had died on trap divide. Try again, thank you!

mikehearn commented at 9:05 pm on May 7, 2014: contributor

You got a divide by zero? That’s …. not good! Any idea how that happened?

mikehearn commented at 10:30 pm on May 7, 2014: contributor

Last time we had a divide by zero it was in the Bloom c’tor where the division happens. I can’t see anywhere you initialise a filter with zero elements - it’s always set to the constant. I think Gregory said he saw where the bug was.

BitcoinPullTester commented at 1:39 pm on May 8, 2014: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/56473b676b8400df3d52d13f232414a6222d5a95 for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

mikehearn commented at 1:53 pm on May 19, 2014: contributor

Hey dgenr8, could you tell me what to look for in the logs? I am not seeing anything unusual printed to them by default, perhaps I have my node set up wrong.

dgenr8 commented at 5:26 pm on May 19, 2014: contributor

@mikehearn The extra logging I added is an invasive hack, so it’s not part of the branch. I’ll send to you privately for now.

mikehearn commented at 5:35 pm on May 19, 2014: contributor

Hmm. Seems like some logging at least would be useful/needed for node operators and developers.

mikehearn commented at 11:24 am on May 22, 2014: contributor

Thanks. Node is up and running and indeed logging double spends that appear related to SatoshiBones. I guess they’re getting attacked quite heavily using what we might call classical double spending - and maybe exploiting some miners that applied the stupid “pick the highest fee” patch.

petertodd commented at 10:23 am on May 24, 2014: contributor

Note that SatoshiBones isn’t replying to those double-spent transactions and thus isn’t vulnerable to them and isn’t losing money.

dgenr8 commented at 6:17 am on May 28, 2014: contributor

@petertodd These respends are being transmitted only when the original bet placed was a loser, so the house is quite steadily losing money to the perpetrator.

It’s happening to SatoshiDICE also. Example: 9642d56ac0e4de9a65dfa4579b5eac2ec79cc2bde1578f4f6037d73ad02572a2. This respend trailed the paying tx by 18 seconds, as observed by our tiny respend-relaying network. That is time enough for the bettor to have learned he lost, and transmitted the “undo” respend with higher fee.

While a regular merchant doesn’t have to worry about paying out winnings, he also doesn’t have the luxury of his product being a bitcoin payout that can be made a child of the original bet, as these gambling services do.

petertodd commented at 6:50 am on May 28, 2014: contributor

@dgenr8 When I looked into this I didn’t observe SatoshiBones or SatoshiDice paying out to unconfirmed bets, whether or not double-spent. Looking at blockchain.info, it appears that SatoshiDice has started responding to unconfirmed bets again, which will predictably cause them to lose money to simple attacks. Why they have decided to make their service less secure is unknown to me and I won’t be surprised if they go back to the more secure behavior.

Do note BTW that since Eligius does not accept satoshidice bets into their mempool you can always double-spend them with ~10% probability, something this relay and alert patch is inherently unable to prevent.

mikehearn commented at 9:23 am on May 28, 2014: contributor

I’m curious if the issue these dice sites have is the Eligius “spam filter” that’s allowing the double spends, or if it’s actually that some big miner is running with the highest-fee-in-mempool patch. It’d be good to correlate the blocks that contain the double spends with blockchain.info’s list of pools to learn more.

dgenr8 commented at 1:10 pm on May 28, 2014: contributor

Per b.i, the two examples listed here were mined by Eligius. The fact that the respends have higher fees suggests that as the reason (otherwise, why offer the higher fee?)

We’re noticing this because of the green vanity addresses being used. Digging for likely successful respends against regular merchants will take a little more effort. @petertodd There are a great many problems that this patch doesn’t prevent. But it would have notified merchant over 20 minutes earlier in this case. Of course, if they haven’t noticed this happening already, I guess we shouldn’t expect them to do much with the alert.

mikehearn commented at 1:14 pm on May 28, 2014: contributor

For double spends mined by Eligius that come from dice sites it’s hard to tell because they deliberately don’t allow transactions mentioning dice addresses into their mempool - and attackers know this. It would be better to find blocks not mined by Eligius and see if those miners are using the patch (and ask them to stop, if so).

luke-jr commented at 1:18 pm on May 28, 2014: member

@mikehearn Uh, miners should NOT stop filtering spam. If anything, more need to adopt it.

mikehearn commented at 1:19 pm on May 28, 2014: contributor

Perhaps that discussion should be had over on #3715 instead.

luke-jr commented at 1:21 pm on May 28, 2014: member

Not really, it’d be off-topic on #3715.

petertodd commented at 1:24 pm on May 28, 2014: contributor

@luke-jr Good point.

Why would a miner want to keep the transaction in their mempool? They’ll use the bandwidth again when the block is broadcast anyway - might as well keep their mempools free of what they consider junk, particularly since not doing so can enable DoS attacks. (e.g. with the sigops issue, or indeed, any case where tx’s are being mined by only a minority)

dgenr8 commented at 1:25 pm on June 9, 2014: contributor

For research, deployed mainnet node now publishes the double-spends it is relaying here.

petertodd commented at 1:27 pm on June 9, 2014: contributor

@dgenr8 Your site isn’t accessible from my machine; firewall?

dgenr8 commented at 1:46 pm on June 9, 2014: contributor

You’re blocked. Kidding. Fixed ;)

petertodd commented at 1:54 pm on June 9, 2014: contributor

Your node is seeing way less doublespends than mine; try running a replace-by-fee node and connecting to it explicitly.

petertodd commented at 1:54 pm on June 9, 2014: contributor

(specifically my v0.9.1 branch that does preferential peering)

dgenr8 commented at 5:39 pm on June 9, 2014: contributor

@petertodd if you pull the changes from this branch, and connect to one of these nodes, all the double-spends your node sees will be on the list. That’s the idea of this PR after all.

I’m happy to connect to you, where?

petertodd commented at 7:28 pm on June 9, 2014: contributor

Like I said, if you run a replace-by-fee node and connect to it with your doublespend node you’ll get more reliable results. Getting point-to-point connections to stay up in the long run is surprisingly difficult due to how the DoS rules/connection limits of Bitcoin work. Much easier if you either just run two nodes yourself and explicitly connect to either. You’ll know it’s working if getpeerinfo shows peers with services “04000001”

Besides, I did say above that I think this patch opens up DoS attack vulnerabilities - I have no desire to be running insecure software. :)

dgenr8 commented at 8:33 pm on June 9, 2014: contributor

@petertodd You never addressed my question of Mar 22 regarding your DOS objection, and in fact @gavinandresen had already anticipated that attack by randomizing the clear moment. Also, 5e3ee30 was committed at your explicit request due to general DOS concern. You could demonstrate an attack at this point. If txes show up on the list, they would have been relayed.

petertodd commented at 8:46 pm on June 9, 2014: contributor

@dgenr8 The doublespend proof “blow-up” issue is pretty fundamental - I can double spend with a 100K (or heck, ~1MB) transaction and now the network has to propagate a bunch of useless data. My other concerns were just implementation specific mistakes that made that fundamental issue even worse.

Better to stick with proving double-spends by showing specific inputs were double-spent, and then on top of that using a custom payment protocol that guarantees things like never reusing addresses. (not unlike how I suspect any scorched earth implementation really needs to be its own payment protocol separate from normal transactions)

Anyway, I’ve got no desire to waste a bunch of bandwidth DoS attacking the network on someone else’s behalf. Seems you’ve got a connection to a replace-by-fee node through somewhere anyway - my double-spends I’m creating as part of my 1% reward for implementing replace-by-fee experiment(1) are showing up now. (I count 9 running on the network right now; I’m running 3 of those)

https://bitcointalk.org/index.php?topic=645120.0

petertodd commented at 8:59 pm on June 9, 2014: contributor

BTW, as for specifics, there’s a few parts:

Payment protocol where Alice’s wallet makes the promise to never double-spend some set of inputs, or even spend the same scriptPubKey twice. (at least until the payment goes through) To be able to add fees, sign with SIGHASH_ANYONECANPAY.
Make double-spend relaying only relay a single double-spending scriptSig + list of SignatureHash() outputs. (to show signatures are valid) This is max 10KB of data, even for a non-standard tx double-spend proof.
…notice that you’ve implemented the double-spend notification I need for scorched earth to work. :) Also having a payment protocol for it makes it easy to do things like have the user put up more than the actual payment as a risk deposit. (1)
http://www.mail-archive.com/bitcoin-development%40lists.sourceforge.net/msg05211.html - “[Bitcoin-development] Replace-by-fee scorched-earth without child-pays-for-parent”

dgenr8 commented at 11:15 pm on June 9, 2014: contributor

@petertodd Many interesting ideas, I look forward to the PR’s/projects. Remember, 5e3ee30 limits bandwidth usage to 50K/10 minutes.

If relaying respends increased their success rate, nobody is happy about that, even if it makes a cool project like scorched-earth-child-pays-for-parent-double-spend-retaliation more necessary. But looking at the data, I don’t see much evidence that relaying respends will increase the success rate of malicious ones, because so many are successful already.

gavinandresen commented at 3:51 pm on June 11, 2014: contributor

DoS and transaction malleability issues have been addressed. Any issues remaining with this? I still think ‘better is better….’

sipa commented at 4:58 pm on June 11, 2014: member

I still think ‘an easy to avoid defense is a false sense of security’. It may seem to work now because people aren’t trying to avoid the protection that is proposed, but when it becomes succesful, I’m sure that those already intentionally double-spending will adapt their behaviour.

SIGHASH_ANYONECANPAY + just relaying proof of double spending rather than relaying full transactions seems much more scalable and harder to block (it doesn’t have transaction size limitations on relay, for example).

dgenr8 commented at 6:21 pm on June 11, 2014: contributor

@sipa Consider this: even if receiver only learns of being double-spent AFTER the double-spend is confirmed, it still may not be too late to stop real-world losses. He may still have time to withhold the unpaid-for goods or service, especially if block was mined quickly. This can work for any double-spend, even a non-standard one.

This seems only logical and I am planning to add wallet notification of respends discovered via block in a follow-up PR.

Viewed in this context, the 0-conf notification is just part of a continuum of actions trying to protect the receiver.

petertodd commented at 7:34 pm on June 11, 2014: contributor

@dgenr8 Yes, but if it doesn’t work because of false alarms, DoS attacks, etc. we’ve made things worse, not better. We can’t just consider features in isolation, we need to consider how they’ll impact the whole ecosystem. For that matter, this really needs a BIP and public discussion on the mailing list - do you realize how your double-spend relaying mechanism would make for great BitMessage functionality? I mean, heck, my ideas for how to implement decentralized CoinJoin are suspiciously similar come to think of it… :/

dgenr8 commented at 8:13 pm on June 11, 2014: contributor

@petertodd Sorry if it sounded like I was proposing some new network alert. I should have explained better. I only meant that local wallet alert of a double-spend suddenly appearing in a block seems like a no-brainer, and a good example for other wallets.

tuttleorbuttle commented at 5:38 pm on June 22, 2014: none

sounds like a pretty good idea imho. aren’t the false alarm and DoS issues already solved?

about eligius… can’t luke-jr just add a simple fix to also refuse to mine double spends related to casino sites?

sipa commented at 5:46 pm on June 22, 2014: member

IMHO, the DoS protection and no-false-sense-of-security are mutually exclusive: if the mechanism provided by these notifications are useful in preventing monetary loss, an attacker will just flood the network with other double spend alerts, hoping his real attack will not get through.

mikehearn commented at 8:09 am on June 23, 2014: contributor

…. until he runs out of coins to double spend, unless the network is fast enough that it doesn’t matter or unless businesses react to a flood of double spend alerts by temporarily pausing their operations, etc.

I’m very wary of adversarial scenarios where people try to anticipate all the way to the end game. I’ve seen this sort of discussion before, back when my old team first proposed the Google anti-hijacking system. Indulge me in a quick story. Spammers had found ways to obtain millions of correct passwords and were logging in to people’s email accounts, to send spam to their friends. So that was the problem. We proposed to try and solve it using risk analysis and asking additional questions at login time when possible.

Needless to say we got lots and lots of negative feedback about this idea. It’ll never work. You’ll break the login system. Users won’t accept it. Hackers will just log in from the same country as the users do and then you won’t be able to spot them. Even if you do, they’ll just switch to using old protocols like SMTP and IMAP where you can’t ask for more than the password, and then it’ll be game over. Users should just all use two-factor logins, anything else is a waste of time. Everyone being hacked is the future, it’s inevitable, don’t fight it. Etc.

All of these were great points made by smart people. Some of them we didn’t have good answers for. We proceeded anyway, partly because we got paid to fight spam and just resigning from our jobs didn’t seem like an option :)

Anyway, end of the story: we did beat them. It turned out that even though there were a lot of different groups doing this kind of hacking they were not infinite and they were not invincible. A lot of the original justifications for why we would fail were based on faulty assumptions that weren’t obvious at the time. For example, that attackers were infinitely smart, capable, didn’t make mistakes, had unlimited time and endless motivation. Another more subtle assumption was that our current set of tactics was the entire possible set; that we wouldn’t invent or discover anything new, even though we did.

If we’d listened to those smart people back then, we’d have never started and thus never have succeeded.

I don’t know if this situation is analogous, I just know that it’s very easy to think you can anticipate everything, that there’s no point in playing defence because, “I’m sure I could beat myself so why bother”. We shouldn’t fall into that trap. In this case, I think the DoS issues are resolved as best we can with our current framework (i.e. not that great but it can improve in future), so the most harm that can occur here is that we do lose this first round, people ignore the alerts and the community ends up back in the same situation it’s currently in. Not so terrible, really.

petertodd commented at 12:03 pm on June 23, 2014: contributor

@sipa Agreed. And you know, basically you can say the difference between my “relay the scriptSig” proposal - which you also deserve credit for IIRC - and the “relay the whole tx” proposal is that the whole tx version requires about 100x more bandwidth to defend against an attacker.

We could do even better than that though and implement a “relay the scriptSig” double-spend alert scheme where the size of the scriptSig we’ll relay was limited. Basically we’d only be making useful promises about scriptPubKey’s that can only be redeemed with small scriptSigs - ~500 bytes should be fine for 99.9% of transactions. In that case per txout you can only get the network to relay another 500 bytes of data max, which is only about 5-10x the bandwidth creating the txout caused in the first place. Perfectly acceptable and keeps this feature from getting abused as a replacement for BitMessage.

gavinandresen commented at 7:33 pm on June 23, 2014: contributor

@dgenr8 : commit history is messy; can you rebase -i to squash bugfix commits?

Everybody else: see any bugs (as opposed to philosophical “I can think of a better way”) that should prevent me from poking the “merge pull request” button?

in src/main.cpp: in 43688adc16 outdated

829@@ -810,6 +830,21 @@ int64_t GetMinFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree,
830     return nMinFee;
831 }
832 
833+bool RateLimitExceeded(double& dCount, int64_t& nLastTime, int64_t nLimit, unsigned int nSize)

sipa commented at 8:17 pm on June 23, 2014:

Can the meaning of this nLimit value be documented somewhere? It looks like it means “nLimit=X means up to X*1000 per minute”.

sipa commented at 8:19 pm on June 23, 2014: member

It seems the current default double spending relay limit is 5000 bytes per minute? Is it intentionally so low?

sipa commented at 8:46 pm on June 23, 2014: member

Has anyone tested how this behaves in case a mutated version of an existing transaction is received? Does it broadcast the “double spend” and/or warn the user?

EDIT: nevermind, it seems the double-spend logic won’t trigger, as the transaction is seen as equivalent.

dgenr8 commented at 9:07 pm on June 23, 2014: contributor

@sipa Correct regarding relaying only isStandard, but an additional check could be added to relay only when !(tx1.isEquivalentTo(tx2)). In this example, tx1 was admitted to mempool, and only scriptSig differs in tx2. Wallet alert is already prevented.

dgenr8 commented at 9:14 pm on June 23, 2014: contributor

@sipa I chose 5000 bytes/min to be .33 of the free relay limit. Currently, count of respend relays is less than .1 count of free transactions. I haven’t looked at size stats. EDIT: the limit was triggered during an attack on my test node on June 10/11, 2014.

sipa commented at 9:16 pm on June 23, 2014: member

So broadcasting 50 kB in a short time - by all attackers combined - worth of double spends is enough to flood the double-spend relay channel, globally?

petertodd commented at 9:16 pm on June 23, 2014: contributor

@dgenr8 You realize how incredibly cheap it’ll be to saturate that limit constantly? We’re literally talking pennies a day.

Heck, it may very well get saturated by just people bumping tx fees, which would be the more useful use of this patch.

sipa commented at 9:18 pm on June 23, 2014: member

Oh, and if you relay simple mutations, it’s even cheaper, as you can use any transaction in the network, not just those you own the coins for. So yes, make sure you don’t trigger double-spend relays for those.

dgenr8 commented at 9:25 pm on June 23, 2014: contributor

@petertodd Is your preferred value for this limit no longer zero? That is progress.

dgenr8 commented at 9:31 pm on June 23, 2014: contributor

@sipa Ok, but if I’m not mistaken, third parties cannot create mutants that pass isStandard. I think that can only be done by altering the signature characteristics, but I’m out of my area there. It would be great if someone could look at the example to see what is actually different about scriptSig.

sipa commented at 9:33 pm on June 23, 2014: member

@dgenr8 They can, it’s trivial. In BIP62 a new transaction type is introduced that can optionally be made non-malleable, but we are months away from availability for starters, and even then it can only work for wallets that choose to adopt that new type.

petertodd commented at 9:39 pm on June 23, 2014: contributor

@dgenr8 Yes, this is great for replace-by-fee, and fee bumping in general, so please set the limit high enough to be useful and low enough that you don’t take the network down. Something more like 50-150KB/minute should be fine. @sipa Additionally remember Gavin’s relax IsStandard() patch(1) that opens up a whole new classes of malleability. Or for that matter SIGHASH_ANYONECANPAY transactions.

#4365

gavinandresen commented at 1:35 am on June 24, 2014: contributor

@petertodd : what “new classes of malleability” are you thinking of? The only one I can see is “Superfluous scriptSig operations” (BIP 62 category 3), but since the reference implementation wallet will never produce any such weird transactions where that malleability is an issue that is not relevant to this pull request.

Other wallet implementations that might produce wacky P2SH transactions might have to deal with malleability, but the right solution for that is to implement the BIP62 malleability fixes.

petertodd commented at 3:04 am on June 24, 2014: contributor

@gavinandresen @sipa and I are talking about DoS attacks enabled by unrelated third parties’ malleable transactions and the attacker creating fake double-spends through malleability; the sender doesn’t necessarily care that their tx’s are malleable.

dgenr8 commented at 5:52 am on June 24, 2014: contributor

@sipa @petertodd Your requested changes have been committed, please review. @gavinandresen I tried, but having brought merges in previously, rather than rebasing, means a lot of edits would be required. Sorry for the rookie mistake.

dgenr8 commented at 6:29 am on June 24, 2014: contributor

Mainnet node’s observed double-spend tracking page includes, since 2014-06-22, double-spends that were first seen in a block. Unless tx1->tx2 elapsed time is very short, these were likely introduced by the miner. Background shaded red.

tuttleorbuttle commented at 5:16 pm on June 24, 2014: none

@dgener8 those red shaded transactions are interesting. the three top ones are all using outputs from tx 8e71c09772e9c456a1ca19c9b1d7fe68e4ac62e10ab88b755781a2421afedf69. seems like someone did this repeatedly throughout the day :D the 4th one is pretty cool. seems like someone sent a tx with and without fee and was lucky enough to get the feeless transaction into a block first. sorry for the off-topic rambling.

petertodd commented at 11:46 pm on June 24, 2014: contributor

@dgenr8 re: rebase, use git add -p to recreate a sensible set of commits for review. Remember that git isn’t a tool to record what you did, it’s a tool to communicate to others what you want to do.

dgenr8 commented at 7:35 am on June 26, 2014: contributor

@gavinandresen @petertodd All cleaned up, thanks for the guidance.

dgenr8 commented at 1:53 am on June 27, 2014: contributor

@gavinandresen This time I compiled the intermediates :$

CBloomFilter::clear() method 8fbf03995d

Relay double-spends, subject to anti-DOS

Allows network wallets and other clients to see transactions that respend
a prevout already spent in an unconfirmed transaction in this node's mempool.

Knowledge of an attempted double-spend is of interest to recipients of the
first spend.  In some cases, it will allow these recipients to withhold
goods or services upon being alerted of a double-spend that deprives them
of payment.

As before, respends are not added to the mempool.

Anti-Denial-of-Service-Attack provisions:
 - Use a bloom filter to relay only one respend per mempool prevout
 - Rate-limit respend relays to a default of 100 thousand bytes/minute
 - Define tx2.IsEquivalentTo(tx1): equality when scriptSigs are not considered
 - Do not relay these equivalent transactions

Remove an unused variable declaration in txmempool.cpp.

d640a3ceab

UI to alert of respend attempt affecting wallet.

Respend transactions that conflict with transactions already in the
wallet are added to it.  They are not displayed unless they also involve
the wallet, or get into a block.  If they do not involve the wallet,
they continue not to affect balance.

Transactions that involve the wallet, and have conflicting non-equivalent
transactions, are highlighted in red.  When the conflict first occurs, a
modal dialog is thrown.

CWallet::SyncMetaData is changed to sync only to equivalent transactions.

When a conflict is added to the wallet, counter nConflictsReceived is
incremented.  This acts like a change in active block height for the
purpose of triggering UI updates.

ada5a067c7

Add -respendnotify option and new RPC data

-respendnotify=<cmd> Execute command when a network tx respends wallet
tx input (%s=respend TxID, %t=wallet TxID)

Add respendsobserved array to gettransaction, listtransactions, and
listsinceblock RPCs.  This omits the malleated clones that are included
in the walletconflicts array.

Add RPC help for respendsobserved and walletconflicts (help was missing
for the latter).

9004798e62

Add release notes entry 9fa53dd3bd

gavinandresen commented at 4:52 pm on June 27, 2014: contributor

ACK.

ghost commented at 5:46 pm on June 27, 2014: none

ACK

petertodd commented at 8:25 pm on June 27, 2014: contributor

Code quality ACK.

Yeah, that’s how you want to split up changes into individual commits, good job.

Formatting, spelling, comment fixes. 7a19efe040

in src/main.cpp: in 9fa53dd3bd outdated

982-            dFreeCount *= pow(1.0 - 1.0/600.0, (double)(nNow - nLastTime));
983-            nLastTime = nNow;
984-            // -limitfreerelay unit is thousand-bytes-per-minute
985-            // At default rate it would take over a month to fill 1GB
986-            if (dFreeCount >= GetArg("-limitfreerelay", 15)*10*1000)
987+        	if (RateLimitExceeded(dFreeCount, nLastFreeTime, nFreeLimit, nSize))

Diapolo commented at 9:18 pm on June 27, 2014:

Nit: Indentation

in src/main.cpp: in 9fa53dd3bd outdated

 999@@ -971,6 +1000,49 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
1000     return true;
1001 }
1002 
1003+static void

Diapolo commented at 9:19 pm on June 27, 2014:

Nit: Could this not be 2 lines?

in src/qt/transactionrecord.h: in 9fa53dd3bd outdated

19@@ -20,7 +20,8 @@ class TransactionStatus
20 public:
21     TransactionStatus():
22         countsForBalance(false), sortKey(""),

Diapolo commented at 9:21 pm on June 27, 2014:

Nit: Would be more readable, if every variable had a single line.

in src/qt/walletmodel.cpp: in 9fa53dd3bd outdated

137@@ -138,6 +138,14 @@ void WalletModel::checkBalanceChanged()
138 
139 void WalletModel::updateTransaction(const QString &hash, int status)
140 {
141+	if (status == CT_GOT_CONFLICT)

Diapolo commented at 9:22 pm on June 27, 2014:

Nit: Indentation

in src/qt/transactiontablemodel.cpp: in 9fa53dd3bd outdated

536@@ -535,7 +537,13 @@ QVariant TransactionTableModel::data(const QModelIndex &index, int role) const
537         return formatTooltip(rec);
538     case Qt::TextAlignmentRole:
539         return column_alignments[index.column()];
540+    case Qt::BackgroundColorRole:
541+    	if (rec->status.hasConflicting)

Diapolo commented at 9:22 pm on June 27, 2014:

Nit: Indentation

in src/wallet.cpp: in 9fa53dd3bd outdated

633@@ -610,7 +634,12 @@ bool CWallet::AddToWalletIfInvolvingMe(const CTransaction& tx, const CBlock* pbl
634         AssertLockHeld(cs_wallet);
635         bool fExisted = mapWallet.count(tx.GetHash());
636         if (fExisted && !fUpdate) return false;
637-        if (fExisted || IsMine(tx) || IsFromMe(tx))
638+
639+        bool fIsConflicting = IsConflicting(tx);
640+        if (fIsConflicting)
641+        	nConflictsReceived++;

Diapolo commented at 9:23 pm on June 27, 2014:

Nit: Indentation

in src/ui_interface.h: in 9fa53dd3bd outdated

20@@ -21,7 +21,8 @@ enum ChangeType
21 {
22     CT_NEW,
23     CT_UPDATED,
24-    CT_DELETED
25+    CT_DELETED,
26+    CT_GOT_CONFLICT

Diapolo commented at 9:25 pm on June 27, 2014:

CT_CONFLICTED? We use that term for this already anyway.

sipa commented at 11:15 pm on June 27, 2014:

NAK as long as it relays trivial mutations of transactions. That makes it trivial to flood the bandwidth of the double-spend relay traffic.

If that has been fixed by now (I can’t check), my NAK is gone, but I still think it is a bad idea. Let consensus decide, however.

dgenr8 commented at 0:08 am on June 28, 2014:

@Diapolo Formatting changes applied, thank you. Despite the name of the updateTransaction “status” parameter containing it, CT_GOT_CONFLICT is an event type and not a status. The transaction being updated is the original spend that just got a conflict. @sipa It has been fixed.

BitcoinPullTester commented at 0:08 am on June 28, 2014: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/p3883_7a19efe04069d9a1e251cdc94b25184f76d9d901/ for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

dgenr8 commented at 7:12 pm on June 29, 2014: contributor

It turns out no changes are needed to alert when a double-spend affecting the local wallet is first seen in a block. It already works, because the wallet looks at every tx in a newly connected block.

gavinandresen referenced this in commit 8ceb28afc3 on Jun 30, 2014

gavinandresen merged this on Jun 30, 2014

gavinandresen closed this on Jun 30, 2014

laanwj referenced this in commit 77888d68d5 on Jun 30, 2014

dgenr8 commented at 8:29 pm on June 30, 2014: contributor

@jgarzik No, for the general anti-DoS machinery, respends are treated like duplicates. In recent versions, AcceptToMemoryPool returns false after detecting a respend, and does not flag an error in the validation state.

One effect is that it won’t contribute to a peer ban. Another is that the peer does not get feedback about the rejection. I suggested adding a rejection code in response to #4057. But, to your point, the simple version of that change would have the effect of increasing traffic via the rejection network message. Whether it contributed to peer banning would depend on the nDoS value chosen.

gavinandresen commented at 3:12 pm on July 1, 2014: contributor

I think there is a potential attack here (as noted by Sergio in another github thread):

Attacker send you a valid transaction. Then attacker sends you a double-spend with an invalid signature.

You will relay that invalid signature transaction to your peers, and if any didn’t happen to see the first transaction (maybe because they just connected to you) they will DoS-ban you.

There should be a regression test for this scenario (using the raw transactions API– munging a signature to make it invalid should be pretty easy).

petertodd commented at 6:22 pm on July 1, 2014: contributor

Not to mention the second transaction with invalid sigs can be made by anyone.

SergioDemianLerner commented at 10:02 pm on July 1, 2014: contributor

It took me long to read all the comments, but I found no clear requirement that the double-spend relay system requires a bloom filter nor a rate-limit. If each double-spend is relayed only once, we have only doubled the attackers DoS capabilities, which imho is completely tolerable.

Regarding allowing transaction replacements: a tx should be allowed to be replaced as long as it has one more input than the replaced (all the rest match), and the new input amount is higher than the required fees. Simple and effective. Allows to overwrite txs hanging forever. No child-pay-parent mess.

Implementing both of them require 5 lines of code, at most.

petertodd commented at 11:53 pm on July 1, 2014: contributor

The double spend can be hundreds of times larger than the original tx, e.g. a 160 byte minimal tx double spent by a 100k or even 1000k tx. Hence the rate limiter, or my suggestion of relaying just scriptSig’s.

Agreed on the relay with higher fee - I proposed that ages ago. Also no reason not to allow additional outputs to be added, or existing output amounts increased. (note how this is very useful for micropayment channels) I’m pretty sure I remember writing that code too, though like you say, its five lines.

SergioDemianLerner commented at 1:38 am on July 2, 2014: contributor

Ok. So the idea was to give double-spend alerts other relay algorithm because the second double-spend may be larger than the first. That’s a pretty good reason because nodes do not know if miners will include the large or the small one. There is no easy way out this problem.

As Peter proposed, a minimal double-spend alert could be achieved using scriptsigs. I did the same proposal long ago here https://bitcointalk.org/index.php?topic=106026.msg1162636#msg1162636

So I vote to give Peter’s proposal a second thought, I don’t like the complexity of the bloom/rate-filter.

dgenr8 commented at 5:27 am on July 2, 2014: contributor

One reason to relay the tx itself is that it may actually be the first spend. No node is omniscient, but this change gives the network collectively more information to work with.

sipa commented at 6:21 am on July 2, 2014: member

I disagree.

The reason to relay the full transaction is because it is the only way to prove that there was an actual double spend. We wouldn’t want people to be able to make the network incorrectly think a double spend occurred.

Propagating double-spending transactions largely removes the distinction between first and second. As a node on the network you have an incentive to get the globally consistent state as close as possible to your own view of it. That means relaying what you expect or want to be valid, and nothing else.

You are right that what you consider second, may have been the first. But what you saw first does have a higher chance of being actually first, and by propagating both, you’re only decreasing the chance that the actual first one wins.

dgenr8 commented at 7:29 am on July 2, 2014: contributor

@sipa I suspect you are right regarding proof, but I havent really studied the scriptsig idea.

It should not be possible to isolate a node from tx1, simply by sending it tx2 directly. When tx1 reaches the “light cone” of tx2, it should penetrate it and cause local alerts inside, although in that realm it is the “double spend”.

mikehearn commented at 8:04 am on July 2, 2014: contributor

Could we gate this behind a version bump? It seems likely that some clients will not expect this behaviour change and will want to opt into it when they’re ready. Consider an app connected to a local “trusted node” which knows what to do when a block containing a double spend appears, but isn’t programmed to handle mempool double spends.

Additionally, other wallets will have to make the same changes as the Core wallet with respect to showing double spends in the UI and so on.

sipa commented at 8:09 am on July 2, 2014: member

Or an explicit negotiation “I want to receive double spend notifications”?

petertodd commented at 8:22 am on July 2, 2014: contributor

@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.

mikehearn commented at 8:37 am on July 2, 2014: contributor

@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.

petertodd commented at 8:41 am on July 2, 2014: contributor

@mikehearn Not everyone will accept A to their mempool.

sipa commented at 8:43 am on July 2, 2014: member

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

sipa commented at 8:44 am on July 2, 2014: member

@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.

petertodd commented at 8:54 am on July 2, 2014: contributor

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)

jgarzik commented at 8:57 am on July 2, 2014: contributor

@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.

mikehearn commented at 9:03 am on July 2, 2014: contributor

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.

jgarzik commented at 9:08 am on July 2, 2014: contributor

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.

mikehearn commented at 9:11 am on July 2, 2014: contributor

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).

jgarzik commented at 9:27 am on July 2, 2014: contributor

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.

petertodd commented at 9:28 am on July 2, 2014: contributor

@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)

mikehearn commented at 9:49 am on July 2, 2014: contributor

@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.

jgarzik commented at 10:26 am on July 2, 2014: contributor

@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.

jgarzik commented at 10:42 am on July 2, 2014: contributor

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.

petertodd commented at 11:26 am on July 2, 2014: contributor

@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)

gavinandresen commented at 1:45 pm on July 2, 2014: contributor

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.

dgenr8 commented at 1:49 pm on July 2, 2014: contributor

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.

petertodd commented at 2:05 pm on July 2, 2014: contributor

@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.

gavinandresen commented at 3:20 pm on July 2, 2014: contributor

@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.

petertodd commented at 5:28 pm on July 2, 2014: contributor

@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.

rebroad commented at 0:37 am on July 21, 2014: contributor

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

MathyV referenced this in commit c2c2c68763 on Nov 24, 2014

dgenr8 deleted the branch on Sep 19, 2018

reddink referenced this in commit 0f962428fb on May 27, 2020

DrahtBot locked this on Sep 5, 2022

Relay and alert user to double spends #3883