Add first-seen-safe replace-by-fee logic to the mempool

petertodd commented at 2:52 pm on May 22, 2015: contributor

Replaces transactions already in the mempool if a new transaction is seen with a higher fee, provided that the replacement transaction’s outputs pay all previous outputs an equal or greater amount. This preserves the “first seen” behavior of the mempool, in the sense that a transaction will never be replaced in a fashion that prevents an address from receiving funds that it otherwise would have. In short, zero-conf transactions are unaffected. (beyond the usual breakage for any mempool behavior change)

To prevent replacements from being used as a DoS attack mechanism a replacement only happens if the new transaction has a higher fee, pays a higher fee/KB rate, and the fee increase is sufficient to pay for the bandwidth consumed in relaying the replacement.

Includes stand-alone unittests for regtest in qa/replace-by-fee/ (implemented w/ python-bitcoinlib as I’ve been asked for a backport of this to v0.10/v0.9)

You can easily try out the behavior using https://github.com/petertodd/replace-by-fee-tools bump-fee.py with the -s first-seen-safe mode switch.

CC: @aalness @coblee re: https://github.com/petertodd/bitcoin/pull/3

in qa/replace-by-fee/replace-by-fee-tests.py: in a4d1ddae21 outdated

 9+
10+import os
11+import sys
12+
13+# Add python-bitcoinlib to module search path:
14+sys.path.append(os.path.join(os.path.dirname(os.path.abspath(__file__)), "python-bitcoinlib"))

jonasschnelli commented at 2:57 pm on May 22, 2015:

Would it not be possible to rewrite/adapt this test so it would conform to other qa/rpc-tests/* and would therefore use the same framework?

petertodd commented at 3:02 pm on May 22, 2015:

Sure, but that framework kinda sucks due to the lack of a good python Bitcoin library. Also, like I said above, I know I’ll be backporting it so I needed a stand-alone set of tests that I could test the backports against.

in src/main.cpp: in a4d1ddae21 outdated

1151@@ -1051,8 +1152,26 @@ bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransa
1152             return error("AcceptToMemoryPool: BUG! PLEASE REPORT THIS! ConnectInputs failed against MANDATORY but not STANDARD flags %s", hash.ToString());
1153         }
1154 
1155+        // Are we replacing an existing transaction?
1156+        if (pool.exists(hash))
1157+        {
1158+        }

sdaftuar commented at 3:03 pm on May 22, 2015:

Empty code block?

petertodd commented at 3:14 pm on May 22, 2015:

Lol, I must be blind… That’s stub code replaced by the lines just below it; fixed, thanks!

petertodd force-pushed on May 22, 2015

in src/main.cpp: in fb472276b1 outdated

1163+        {
1164+            LogPrint("mempool", "replacing tx %s with %s for %s BTC additional fees, %d delta bytes\n",
1165+                     txConflicted.GetHash().ToString(),
1166+                     hash.ToString(),
1167+                     FormatMoney(nFees - nConflictingFees),
1168+                     (int)nSize - (int)nConflictingSize);

sdaftuar commented at 4:08 pm on May 22, 2015:

I believe it shouldn’t be possible for there to be more than one transaction in ltxConflicted here, is that right? Perhaps clarifying the comment at line 1155 (or adding an assertion about the size of this list) would be helpful.

petertodd commented at 4:52 pm on May 22, 2015:

The mempool isn’t locked the whole time, so I believe there’s a small chance there could be more than one conflicting transaction. (never mind future design changes!)

Updated comment.

sdaftuar commented at 8:13 pm on May 26, 2015:

Mostly an fyi after looking at this more: despite the mempool lock not being held the whole time, cs_main is held, and that seems important for a preventing a race condition (otherwise the result of view.HaveInputs() at line 1029 could have changed by the time you get to pool.addUnchecked() at line 1182)… Anyway, I don’t think there can be more than one conflicting transaction.

jtimon commented at 9:15 am on June 29, 2015:

@sdaftuar other policies can replace more than one conflicting transaction. But, yeah, since this code doesn’t, an assert with a comment along the lines “disable multiple replacement feature for now” wouldn’t hurt.

petertodd force-pushed on May 22, 2015

sdaftuar commented at 10:04 am on May 23, 2015: member

I think we need to add a check that the replacing transaction isn’t spending an output of the to-be-replaced transaction; I just wrote up a quick test and it looks to me like this would cause an orphan transaction to enter the mempool.

petertodd force-pushed on May 23, 2015

petertodd commented at 4:14 pm on May 23, 2015: contributor

@sdaftuar Nice catch! Fixed.

petertodd force-pushed on May 23, 2015

laanwj added the label Mempool on May 26, 2015

dgenr8 commented at 6:40 pm on May 26, 2015: contributor

Should also ensure that no inputs have been removed or changed (other than scriptsigs) – only added.

Otherwise, the semantics change for the original signers. Imagine a tx with two inputs from different parties. Should it be easy for party 1 to be able to eliminate party 2 as a contributor of funds? It’s not difficult to imagine real-world consequences to not having contributed to the transaction. tx-level attributes like nLocktime should not change either.

The result would be something very like CPFP, but with the new inputs and outputs merged into the original tx, saving space and tx count.

sdaftuar commented at 7:30 pm on May 26, 2015: member

I don’t see a problem with removing inputs, but perhaps we should consider an additional requirement that any inputs not in the original transaction must also not be in the mempool (and therefore must already be confirmed).

I think the idea should be that the replacing-transaction is more likely to be confirmed than the previous transaction. If the replacing transaction has slightly higher fees but adds an input that depends on an unlikely-to-be-confirmed transaction, then a miner might prefer to not do the replacement.

petertodd commented at 1:14 am on May 27, 2015: contributor

@sdaftuar That’s an interesting point. You’re right that just forcing the input to be confirmed works; a more sophisticated - but still fairly easy to implement - approach would be to to have the mempool track the sum fee of transactions’ parents and reject the replacement if you’re going from a higher fee/KB parent to a lower one.

Having said that, I’m don’t think you can really create an attack out of this: in either case the attacker is limited by the min-relay-fee, so they could have always done an attack by just broadcasting a long chain of transactions anyway.

Anyway, I can’t think of any applications other than adding inputs to transactions signed with SIGHASH_SINGLE where restricting new inputs to be confirmed would be a major limitation.

petertodd commented at 1:19 am on May 27, 2015: contributor

@dgenr8 re: nLockTime, we only allow transactions into the mempool if they’re final, in which case the exact nLockTime value is irrelevant; I don’t think we should bend over backwards to accommodate weird smart contract protocols, particularly when it’s easy to design them such that eliminating a contributor of funds from the transaction means the “thing” that was meant to happen doesn’t happen. In all the smart contract stuff I’ve worked on the natural outcome of party #1 eliminating party #2 from being an input simply means that they’ve decided to “purchase” the thing/contract/right/whatever in question all by themselves rather than with the assistance of others.

I didn’t write it up in my FSS RBF writeup, but being able to replace transaction inputs rather than simply add to the vin makes fee bumping significantly more efficient in many scenarios; I’ll write that up later on the -dev mailing list.

dgenr8 commented at 4:20 am on May 27, 2015: contributor

@petertodd For a fee increase, there is no need to expose to deletion inputs in a transaction with inputs from multiple parties, which cannot be distinguished from a transaction whose inputs are all owned by a single party. (A tx with exactly one input can’t conflict with a 1-input replacement if it increases the fee, given the restrictions on changes to outputs).

You’re right about nLocktime, but there is simply no need for it to be changed to accomplish a fee bump.

This is a NACK for me unless it sticks to only what is necessary to allow a fee bump without otherwise altering the effects of the transaction replaced. IMO economizing on number of inputs is not a good enough reason.

petertodd commented at 7:32 am on May 27, 2015: contributor

@dgenr8 With CLTV you may need to set nLockTime on a transaction that previous had it unset to accomplish a fee bump; spending an input may require nLockTime to be set. Equally there are 2fa wallet cases where nLockTime must be set. Allowing nLockTime to be increased by the replacement fits well with the fee-sniping protection added by https://github.com/petertodd/bitcoin/commit/ba7fcc8de06602576ab6a5911879d3d8df80d36a

Re: cost savings, I posted them to the mailing list. Cost savings in one common example are %34

In any case, we’ll see if anyone else raises any objections to this aspect of the patch; @gmaxwell has already stated he doesn’t see any issue: http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg07846.html http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg07860.html

sdaftuar commented at 1:43 pm on May 27, 2015: member

@petertodd I agree comparing the total fee/kb with all parent tx’s ought to address the issue, but I wasn’t sure if implementing that would be worth the complexity, mainly because CPFP hasn’t yet been merged. But either approach seems fine to me.

Anyway I also don’t see this as an attack vector, more like a way to prevent a user from accidentally RBF’ing to a higher fee tx that has a lower chance of confirming, then having to RBF to a yet-higher-fee to correct the error (assuming the error is even noticed).

petertodd force-pushed on Jun 6, 2015

petertodd commented at 2:41 am on June 6, 2015: contributor

@sdaftuar Here’s a new version with the additional restriction that additional inputs must be confirmed.

aalness commented at 8:23 pm on June 20, 2015: contributor

@petertodd While I really appreciate you thinking to cc me on this review please do not expect one from me. I’ve decided to no longer work on bitcoin-related projects nor participate further in the community.

Add first-seen-safe replace-by-fee logic to the mempool

Replaces transactions already in the mempool if a new transaction is
seen with a higher fee, provided that the replacement transaction's
outputs pay all previous outputs an equal or greater amount. This
preserves the "first seen" behavior of the mempool, in the sense that a
transaction will never be replaced in a fashion that prevents an address
from receiving funds that it otherwise would have. In short, zero-conf
transactions are unaffected.

To prevent replacements from being used as a DoS attack mechanism a
replacement only happens if the new transaction has a higher fee, pays a
higher fee/KB rate, and the fee increase is sufficient to pay for the
bandwidth consumed in relaying the replacement.

Includes stand-alone unittests for regtest in qa/replace-by-fee/

f3044fd191

in src/main.cpp: in b7ac851a98 outdated

968+                    }
969+                }
970+
971+                // Make sure the outputs of the transaction we're replacing
972+                // have not been spent.
973+                for (unsigned int j = 0; j < ptxConflicting->vout.size(); j++)

ashleyholman commented at 10:30 pm on June 20, 2015:

You could avoid checking each vout sequentially by checking mapNextTx.lower_bound(COutPoint(hashConflicting, 0))

petertodd commented at 10:41 am on June 21, 2015:

As in, check if the mapNextTx.lower_bound() hash == hashConflicting or the lower_bound() returns mapNextTx.end()?

Seems reasonable, though the way that depends on which way COutPoint’s is sorted bothers me slightly.

petertodd commented at 4:58 am on June 22, 2015:

@ashleyholman Switched to lower_bound(), thanks! Mind checking the new code over?

in src/main.cpp: in b7ac851a98 outdated

1013+                    // checked that the conflicts outputs were all unspent above,
1014+                    // we only have to check against the conflict, not any
1015+                    // children. Similarly because we'll only ever replace
1016+                    // transactions on a 1-1 basis, we only have to do this check
1017+                    // once.
1018+                    if (tx.vin[j].prevout.hash == hashConflicting)

ashleyholman commented at 10:31 pm on June 20, 2015:

I may be wrong here, but wouldn’t your previous check (no new inputs are in the mempool) already catch this case?

petertodd commented at 10:35 am on June 21, 2015:

Ah, yeah, that’s true now that it’s been changed to require new inputs to be confirmed. Good catch.

petertodd commented at 4:59 am on June 22, 2015:

Removed this check and replaced it with a comment describing how it’s needed if we ever allow the new inputs to be unconfirmed.

petertodd force-pushed on Jun 22, 2015

sdaftuar commented at 7:09 pm on June 25, 2015: member

ACK

petertodd commented at 5:03 am on June 29, 2015: contributor

Closing in favor of #6352

petertodd closed this on Jun 29, 2015

MarcoFalke locked this on Sep 8, 2021

Add first-seen-safe replace-by-fee logic to the mempool #6176