Add replace-by-fee logic to the mempool

petertodd commented at 10:13 am on June 6, 2014: contributor

Replaces transactions if a new transaction is seen with a higher fee, specifically both a higher fee per KB and a higher absolute fee. Children are evaluated for replacement as well, using a fixed depth/breadth limit to prevent DoS attacks. Child-pays-for-parent is however not yet supported.

This patch doesn’t include any wallet changes to actually take advantage of replace-by-fee, e.g. fee bumping functionality. I have however written some Python utilities for experimentation: https://github.com/petertodd/replace-by-fee-tools Now that the wallet code handles double-spends correctly fee bumping and other replace-by-fee applications won’t mess up your wallet with never-confirming transactions. That said Bitcoin-QT does need some UI improvements re: conflicts.

Note that this is the version suitable for a pull-req; if you want to actually try out replace-by-fee functionality use https://github.com/petertodd/bitcoin/tree/replace-by-fee-v0.9.1 instead. It has preferential peering code that seeks out other replace-by-fee supporting peers and connects to them, ensuring your replacements get propagated and you see others’ replacements.

As discussed elsewhere ad nauseam, unconfirmed transactions are easily double-spent via a variety of methods with high success rates, even without miners implementing replace-by-fee. For instance the above replace-by-fee-tools has about a 95% success rate against most wallet software by taking advantage of the minimum v0.9 fee drop. Better to be honest to users about what security guarantees Bitcoin actually provides, and replace-by-fee functionality is highly useful otherwise to lower fees through more aggressive fee estimation, fix stuck transactions, lower fees by combining successive transactions, etc.

Add simple replace-by-fee logic to mempool.

Replaces transactions if a new transaction is seen with a higher fee,
specifically both a higher fee per KB and a higher absolute fee.
Children are evaluated for replacement as well, using a fixed
depth/breadth limit to prevent DoS attacks.

Thanks-to Zeilap for code review and suggestions.

32ca5de2af

ghost commented at 12:29 pm on June 7, 2014: none

I’m going to copy my comments from Reddit in response to petertodd:

I think you’re doing great work and this patch is undoubtedly necessary and will improve the ecosystem as a whole. But you or your colleagues working on the core need to harden the payment protocol before you ACK this. Making it 95% likely that anybody can double spend a zero conf transaction breaks real world usage of bitcoin.

With a 10-minute block time, zero conf transactions NEED to happen in order to allow real world purchases at everyday retailers. Either that or we start having centralised services where you pre-load an account before you can order a happy meal at McDonalds, have people implement credit-card-level fees to compensate for the few who will abuse the system, or make people wait 10 minutes to buy their morning coffee before walking off. None of these alternatives are desirable.

Your work is appreciated, but the inclusion of this patch before implementing further appropriate safety features is unfortunately wrong.

ghost commented at 12:53 pm on June 7, 2014: none

Maybe OT, but actually there is a place for offchain transactions. Loading a debit card with bitcoin very well be a way forward for small and micro-transactions. It’s certainly not a terrible thing and fits right into the paradigm of debit cards and more inclusive than requiring everyone carry a smartphone. You can still maintain control over most of your funds, just loading the card as you need with smaller amounts.

ghost commented at 0:59 am on June 8, 2014: none

So who issues the debit card? What if they choose to withdraw that service? How about people who DO have mobile wallets - will they no longer be able to use them? And there are a lot more people out there with wallet-capable smartphones than you seems to give credit for.

The fundamental issue here is that in the real world you walk into a shop, slap your money on the counter, and walk out with a Coke 10 seconds later.

Complaining about the insecurities of zero conf transactions makes for good philosophical fodder, but ignores the needs of everyday merchants and buyers alike. Until you make off-chain transactions a possibility, or harden the payment protocol further against double spends and other simple defrauding, pulls like this will only do more harm than good.

luke-jr commented at 1:25 am on June 8, 2014: member

How do you think they currently deal with credit card fraud? Losing an occasional Coke is built into the costs of business. If you’re doing a high-value transaction, just ask to see a photo id and copy down the name/number so you can sue later if they double-spent you.

Pretending zero-confirmation on-chain can be secure is just a false sense of security in the best of circumstances.

petertodd commented at 2:55 am on June 8, 2014: contributor

It’s notable that without many (any?) miners supporting replace-by-fee right now my double-spend script(1) has about a 95% success rate. Even if you try to take fees into account, try to measure propagation, detect double-spends, etc. you still end up with a 5% to 10% success rate.

You can says things need to be “hardened” first, before we “break” zeroconf security, but it’s already broken, as evidenced by the vendors I’m talking to right now who are getting ripped off by double-spends. Might as well accept this and move forward.

https://github.com/petertodd/replace-by-fee-tools/blob/master/doublespend.py

jgarzik commented at 3:04 am on June 8, 2014: contributor

“We are seeing bad behavior, might as well release a feature making bad behavior easier” is illogical.

ghost commented at 10:09 am on June 8, 2014: none

jgarzik - You’ve summarised it much better than I could have :)

petertodd - If you’re speaking to vendors right now, what mitigating strategies/software changes are they putting into place to counteract fraud on zero conf transactions? Why not include some of those strategies in the core before this pull goes live?

sipa commented at 10:47 am on June 8, 2014: member

There are two opinions about what the responsibility of the network should be, here: zero-confirmation double-spending prevention or not.

In my opinion, zero-confirmation security is a useful feature, and one that a significant portion of the network came to rely on. Most of those are aware that it’s only a best-effort mechanism, and that with cooperation from miners, it is easily bypassed. But people do rely on the fact that it at least isn’t trivial to pull off, and that it will happen only in a small percentage of cases. This property is still valuable; something similar happens for credit-card fraud (where it’s sometimes the merchant taking the risk, sometimes the bank, but they still feel that even if risky, the payment system provided is valuable).

Mechanisms exist to improve detection of potential double-spends, but due to technical reasons, I believe it is not possible to reliably build this into the core network responsabilities either (at least not without making it either a huge DoS attack vector, or making it trivially bypassable for someone who is already intentionally attacking).

Anyhow, I don’t see how this property of preventing 0-conf double spends can be maintained in the long term. It only requires a few miners to choose for the (short-term) rational behavior (choosing the most per-byte-valuable transactions, regardless of which was first) to to remove that protection entirely. In addition, every change in standardness, consensus rule upgrades, conditional or rate-limiting of relays, … add additional and hard-to-predict risks.

When that happens, I think it’s much healthier for the ecosystem to acknowledge that double spending can and will happen. I don’t think that means accepting a broken system. It just has different properties than what many expect today; for example, there is much less need for overshooting fees to be sure a transaction gets accepted.

I don’t think that means we must force the whole ecosystem to switch to that model immediately. Changing such assumptions is hard, and the disruption can hurt. I’m not sure today is the right time either, but eventually I think we better prepare for that.

ghost commented at 12:10 pm on June 8, 2014: none

Sipa - your point is very valid. This is an evolving process and petertodd’s changes are certainly where the network should be moving. But surely, there can be some form of mitigation/risk management built in?

Maybe an option for vendors to enforce scorched-earth payments through some simple hard-coded mechanism to begin with - all a merchant wants to do is display a single QR code and get a ‘beep - accepted’ response. Anything else breaks the simplicity a customer expects when buying a sandwich, such as ‘First set up a protective payment for me with this QR code’. Wait. ‘No, you can trust I (the merchant) am not going to defraud you’. Wait. ‘Now, pay me through this QR code’. Wait.
‘Dust sweeping transactions’ whereby a single user can sign a large collection of dust-ONLY transactions all at once in order to sweep them into a single usable stack of coins. This would give no reason for dust to be included in retail transactions and therefore transactions containing dust inputs could be blocked entirely.

I’m trying to think of others, which is why I’d also like to know the outcome of the conversations petertodd says he has been having with vendors - what has he recommended they do in order to reduce fraud?

If we just have to ‘accept’ a certain percentage of fraud, we will end up EXACTLY where the credit card companies are with their 3.5% fees to retailers.

robbak commented at 12:33 pm on June 8, 2014: contributor

If you want trustworthy 0-conf transactions, you’ll have to invent a new coin that makes it happen. The decisions made with Bitcoin don’t make it possible. Sorry.

The only way I can see of making a quick-confirmation system work is to come to an agreement with more than 50% of the mining power that once they see one of your transactions, they will never accept a conflicting transaction, or mine on a block that includes such a transaction. Then you let the goods go once those miners confirm that they have received it.

petertodd commented at 8:54 pm on June 8, 2014: contributor

The reason why you switch to replace-by-fee is because the only way to make the current way of making zeroconf transactions secure is to do things that greatly harm Bitcoin’s decentralization. For instance Mike Hearn’s coinbase reallocation/block blacklisting proposal can make zeroconf secure, but at the cost of adding real-world politics and regulation to whether or not a block is accepted by the network. Equally if defacto behavior is what’s required prevent double-spending, then courts will very likely find failure to follow that behavior grounds for civil liability:

21:22 < gmaxwell> In a civil claim, its almost sufficient to just show someone was harmed and that you were on the critical path.

(the full IRC discussion where the above came from is worth reading: http://download.wpsoftware.net/bitcoin/wizards/2013/11/13-11-20.log)

By using replace-by-fee policy you set an early precedent that the Bitcoin network and Bitcoin mining does not provide guarantees it can’t provide in a decentralized environment. This is why I argued previously that if you care about decentralization, you should be mining with replace-by-fee: https://pay.reddit.com/r/Bitcoin/comments/235zv5/why_you_should_mine_with_replacebyfee_a/

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

@NanoAkron This whole “scorched earth” thing is completely compatible with any standard Bitcoin transaction; you don’t need to do anything special to use it. That said because current Bitcoin wallets don’t appear to be very good at not double-spending by accident you will want some explicit support in the payment protocol for it to let wallet software know that they must be sure a double-spend isn’t going to accidentally happen. (also needed by coinjoin - you’d give the merchant a version of the transaction w/o coinjoin in case one of the coinjoin participants double-spends you)

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

@robbak Yup, and such >50% agreements sound suspiciously like a group controlling >50% of the hashing power don’t they… Also if those agreements are for a fee, they also mean that controlling a large amount of hashing power is more profitable than controlling a small amount, which encourages centralization of mining power. Just another reason why not adopting replace-by-fee now is very unwise. Fortunately only a small minority needs to do it to start us down the right path.

ghost commented at 11:04 pm on June 8, 2014: none

Thanks for your replies @petertodd.

Could you perhaps clarify this double (triple?) negative for me: “current Bitcoin wallets don’t appear to be very good at not double-spending by accident”. If they are not good at not double spending by accident, they must be good at double spending on purpose?

And perhaps if you solved this issue first (in your own words) “explicit support in the payment protocol for it to let wallet software know that they must be sure a double-spend isn’t going to accidentally happen”, then introducing replace-by-fee right now wouldn’t leave zero conf transactions quite so open to potential abuse.

Furthermore, what mitigation methods have you discussed with vendors?

Cheers!

jgarzik commented at 11:16 pm on June 8, 2014: contributor

@petertodd “the only way to make the current way of making zeroconf transactions secure is to do things that greatly harm Bitcoin’s decentralization” This is sufficiently subjective to the point of being simply wrong. There are many business cases involving 0conf which map easily onto bitcoin, as I’ve pointed out on IRC, that are accomplished today without “greatly harm[ing] Bitcoin’s decentralization.”

0conf transactions imply you must take additional steps to fully secure the transaction. They have an existing set of security properties, but they are unstable, as they are not yet locked into the timeline. That does not therefore imply that it is wise to make attacks even easier by relaxing the existing security properties further.

Replace-by-fee was widely considered anti-social on various forums. I don’t see how that has changed at all.

petertodd commented at 11:38 pm on June 8, 2014: contributor

@NanoAkron That’s just an observation from my double-spending logs. Basically it appears that at least some clients are double-spending inputs on occasion, probably because the wallet software doesn’t reliably record the fact that it’s created a transaction spending the input. If you’re to use replace-by-fee scorched-earth then your going to want wallet software that takes additional steps to be absolutely sure it won’t double-spend accidentally.

As for solving the issue first, everything I’m seeing indicates that it’s a minority of services that are actually depending on the existing and very weak zeroconf security, and that minority keeps getting smaller. e.g. at the Bitcoin conference I talked to two-way ATM vendors, and most had already implemented a receipt scheme so customers could go to the ATM, send their funds, get a receipt for it, and then upon confirmation, come back and get their money. Meanwhile Mycelium’s local trader feature is showing that in the absence of clarity people are implementing stuff that is a lot more vulnerable then they realize; with replace-by-fee implemented I’m sure Mycelium would have done things right the first time and implemented secure multisig escrow and/or micropayment channels. @jgarzik There’s nothing anti-social about wanting to see strongly secure solutions be implemented, and mining stay unregulated. As I’ve argued quite clearly, the more people expect zeroconf to work as-is, the greater the temptation is to use legal tools against miners who mine double-spends, either intentionally or by accident. Secondly it creates a market for guaranteeing confirmation, which is something only large miners can offer, not small ones, again creating an incentive to centralize mining.

ghost commented at 11:12 am on June 9, 2014: none

@petertodd How do you suggest someone buys a pint in a pub with bitcoin? Pay first, get a receipt, walk back to their table, wait 10 or maybe 20 minutes, walk back to the bar and collect their drink? Have you thought about how people transact in the real world or is the philosophical/intellectual perfection of the software more important to you than real world use?

And if micropayment channels are one of the solutions you’re proposing, why not implement them in the core before devastating what little security there is in 0conf?

As @jgarzik said before: “We are seeing bad behavior, might as well release a feature making bad behavior easier” is illogical.

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

@NanoAkron You’re example of a bar is a perfect example where existing practices find that security isn’t needed - the bar in the real world will happily give you a drink prior to paying.

re: micropayment channels, etc. I can’t and am not going to fix everything. We’ve also found out over and over again that people write remarkably broken and insecure code when they can’t see why it’s insecure - e.g. the services talking to me right now about how they’re getting defrauded via doubles-spends.

Equally, if you stick with the broken zeroconf security we have now, every time we (or anyone else) changes anything in Bitcoin Core we’re allowing for doublespends - I’ve already seen Mike Hearn argue against making changes on that basis rather than sound technical reasons: #3715 (comment)

If you insist on a patch like this (which just puts off the inevitable for a few minutes - hardly useful), please at least just make it block inclusion rather than relay policy. Otherwise it turns miners that use it into double spending tools for no benefit or reason, forcing everyone else to use an ever more convoluted risk analysis to decide whether an unconfirmed transaction might get double spent by a -datacarrier=0 user. This doesn’t help anyone, not even the node running the flag, who must process and store the transaction when another miner confirms it anyway.

Equally look at Luke-Jr’s pool Eligius, which happily mines non-standard transactions no-one else does; I can always double-spend with %8 probability by simply submitting a conflicting tx to Eligius first. Or I could just double-spend you with some other high probability by submitting a tx with a dust output, which many miners still mine. (BTC Guild IIRC) This is only going to get worse too with fee estimation, as I can always just fine a pool with a lower minfee estimate than most of the network, relay to them first, and then relay the more reasonable fee tx to everyone else. Again, do we just not deploy fee estimation because it’ll harm zeroconf security? Remember that relaying double-spends around the network is a DoS attack.

Also, here’s an interesting experiment: Earn 1% more by mining with replace-by-fee - https://bitcointalk.org/index.php?topic=645120.0 At some price miners will upgrade.

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

“Replace by fee” is not an accurate name for this change.

The policy implied by the fee checks is murky. No attempt is made to ensure that any of the original outputs are still paid, and all the original inputs are dropped, regardless of who signed them.

mikehearn commented at 10:19 am on June 11, 2014: contributor

The places being double spent need a better risk analysis that takes into account the fact that our network kind of sucks; not people simply giving up on the idea of a useful Bitcoin full stop.

For instance, places that are being double spent can simply reject payments that pay lower than the old min fee, or force them to wait for a confirmation. That’s a much simpler change than this one, although the lack of information provided by the P2P network unfortunately makes calculating the fee for a tx harder than it should be. Eventually miners will either upgrade past the fee drop, or will move to floating fees, and so on, so predicting miner behaviour should get easier.

fraggle222 commented at 12:15 pm on June 18, 2014: none

So, summarizing from what I’ve read on this issue:

Arguments for replace-by-fee patch:

zero conf transactions are not safe but people are using them anyway
so we need to make them really unsafe
then people will then stop using zero conf transactions
bitcoin will be better off because no one will accept zero conf transactions (but see next)**
this patch also opens the door for the ‘scorched earth’ approach to safer zero-conf transactions**

Some arguments against this patch are:

we need a way for merchants (mostly brick & mortar) to accept payments in 1 second not 10-60 minutes.
so we need to figure out a way to make zero-conf ‘somewhat safe’ (at least for smaller transactions)
solutions that require 3rd parties (greenaddress.it) work, but sort of suck because of the 3rd party party requirement (less decentralized, higher costs for merchants)
we have not fully explored ways to make zero-conf safer (node detection, block rejection, etc), and some proposed solutions to it might work.
the ‘scorched earth’ approach to zero-conf transactions seems promising but we are not convinced it is the way to go yet.**

Would love to know if that is roughly correct.

I am against this patch (for now). The arguments for it are indeed “neater”, but I’d like to be convinced that there aren’t some solutions that will allow bitcoin to work ‘faster’, but with some small risk, associated with zero confirmation transactions. Ultimately I feel strongly that we should’t have to rely on 3rd parties to make bitcoin fast. EDITS => After reading more about the ‘scorched earth’ approach to zero conf, this patch makes a bit more sense but I’m not yet convinced of the ‘scorched’ approach. Seems like it hasn’t been fully vetted and opens the door to other ways to convince miners to do non-standard things through fees.

**Edited after reading more on the ‘scorched earth’ approach.

jtimon commented at 2:02 pm on June 18, 2014: contributor

@petertodd I think mining policies should be abstracted away. So instead of replacing “first-seen + starndard” policy with a new “replace-by-fee + standard” policy, this patch could implement an abstract class Policy, extended by StandardPolicy (which reproduces the current behavior) which in turn is extended by ReplaceByFeePolicy modifying its behavior. a –policy parameter can select one of them. That way the PR would be much less polemic and would also make it simpler for miners to implement their own policies. Although I’m in favor of replace-by-fee, I think a maintainable way to support several different policies may be a reasonable prerequisite for accepting a controversial policy like this one. That would also open the door, for example, for a miner to implement a “0.01 usd min fee” policy looking at the indexes he trusts or something. Well, just an example, it would make policy innovation simpler in general. @fraggle222 You can have secure 0 confirmation protocols with replace-by-fee, in fact, the majority of miners using a replace-by-fee policy makes some of those protocols more reliable or even possible. They’re usually referred to as “scorched earth” payment protocols. Here’s one example: http://ehc.ac/p/bitcoin/mailman/message/32263765/ In fact, the payment protocol could be extended to support them.

fraggle222 commented at 4:27 pm on June 18, 2014: none

@jtimon thanks for that, I will review and edit my response if necessary. Although I don’t really see a comprehensive discussion on scorched earth in that thread.

jtimon commented at 4:44 pm on June 18, 2014: contributor

@fraggle222 I did my best with that example of scorched earth protocol, I’m sorry it’s not clear enough. Feel free to ask from clarifications in the mailing list. What about the thread linked to from that thread? I know there’s an earlier explanation somewhere.

petertodd commented at 5:17 am on June 19, 2014: contributor

@jtimon That’s not a bad idea, although keep in mind that part of the controversy here is some thing having even a different policy than the “standard” is in itself a bad thing.

BitcoinPullTester commented at 1:25 am on June 23, 2014: none

Automatic sanity-testing: FAILED MERGE, see http://jenkins.bluematt.me/pull-tester/p4298_32ca5de2af36e71aa720c2400836be7b0313b2a4/ for test log.

This pull does not merge cleanly onto current master 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.

jgarzik commented at 4:55 pm on July 29, 2014: contributor

Closing, as there is clearly no consensus that we should move forward on this in the near future.

Should consensus emerge, we can reopen this PR.

jgarzik closed this on Jul 29, 2014

luke-jr commented at 5:14 pm on July 29, 2014: member

This is relay/miner policy, so developers should not be making any decision on the direction here. @petertodd Can you make this a runtime option(s)?

Side note: For relay-only nodes, I think they should require the replacing transaction to have PLUS ; relay nodes don’t get any direct benefit from the transaction fees, so they should insist on payment for bandwidth, not just the data. Otherwise, a spammer could continually replace with 1 satoshi more fee each time…

jgarzik commented at 5:19 pm on July 29, 2014: contributor

@luke-jr hmmm, that is a fair point about miner policy.

petertodd commented at 5:46 pm on July 29, 2014: contributor

—–BEGIN PGP SIGNED MESSAGE—– Hash: SHA256

Sure, runtime option is fine.

The patch requires that transactions pay for the bandwidth consumed by the rebroadcast by requiring that fees be increased by at least MIN_RELAY_FEE * size; a single satoshi replacement won’t be relayed.

On 29 July 2014 13:14:42 GMT-04:00, Luke-Jr notifications@github.com wrote:

This is relay/miner policy, so developers should not be making any decision on the direction here.

@petertodd Can you make this a runtime option(s)?

Side note: For relay-only nodes, I think they should require the replacing transaction to have PLUS ; relay nodes don’t get any direct benefit from the transaction fees, so they should insist on payment for bandwidth, not just the data. Otherwise, a spammer could continually replace with 1 satoshi more fee each time…

Reply to this email directly or view it on GitHub: #4298 (comment) —–BEGIN PGP SIGNATURE—– Version: APG v1.1.1

iQFQBAEBCAA6BQJT190MMxxQZXRlciBUb2RkIChsb3cgc2VjdXJpdHkga2V5KSA8 cGV0ZUBwZXRlcnRvZGQub3JnPgAKCRAZnIM7qOfwhY1vCAClq5Eyg7XxC260wFwD DXesq/SEcBgFoAP1fxkp29UPD9jKugiDr8hKx1NXSnimrMiXazWS1YIAZ1PsznM6 PlIC+iMYWgc7/M/e9ueaa8F8QxP3oGGu5oC8hrX73kxHr0or2EFyW5/H8M/BGxCR kzGPVOE3pwEZx70aAWH7D6WWAh4mujlscC6jh4khg8F17zb0RbK6OEUTA5qoDzQ8 ntqCUNULyUNWwcOcmOiIP/dtbja+qLCobdENIttgfDl+2nJfqu6JYGTRnuDYdqqS VziOLDra70squX/JYZE/lvEt2rNILgNX2RS2hLWiiVBgoxK5QyXB1yLDBpbu0rcJ ndj5 =4J2W —–END PGP SIGNATURE—–

laanwj commented at 8:25 am on July 30, 2014: member

@luke-jr I agree. However the other side of the coin is that we don’t have to merge everything that involves changing miner policy because someone may want to use it. Ideally some more modular system would be implemented here (that can outsource the decisions to an external process, for example) so that we don’t end up merging a grab-bag of rarely used, never tested options.

petertodd commented at 10:15 am on July 30, 2014: contributor

@laanwj I think in this case if people don’t use it you’d remove the code at a later date; a runtime option allows us to test the waters temporarily.

jtimon commented at 10:01 am on August 5, 2014: contributor

As said, I think it would be cleaner to encapsulate the policy under a class and then you can have several of them using a factory to allow the runtime option and either polymorphism or templates. Probably a couple of policies (standard and replace-by-fee?) will be enough for people understand the class and cleanly implement their own. Personally I’m in favor of replace-by-fee, but I would prefer if the policy code becomes cleaner (and gets out of main.cpp!!) after adding this change (or before).

sidhujag referenced this in commit ff28136028 on Aug 4, 2021

MarcoFalke locked this on Sep 8, 2021

Add replace-by-fee logic to the mempool #4298