[mempool] allow tx replacement by smaller witness

LarryRuane commented at 7:06 pm on January 7, 2022: contributor

This PR is a reattempt of #19645, which has been abandoned.

Currently, an existing mempool transaction can’t be replaced by a transaction that’s identical except for its witness (same txid, different wtxid); the request is rejected as a duplicate. This PR changes this behavior such that the mempool will replace the existing transaction if the new transaction has a smaller witness by at least 5% (an anti-Dos measure). The replacement transaction can’t increase the fee (since its inputs and outputs cannot change), but it necessarily has a higher fee rate than the existing transaction, since its overall size is lower. Miners should always prefer the replacement transaction.

An important difference between what this PR implements and the existing RBF (replace-by-fee, BIP125) is that the replacement can occur even if the original transaction is not marked as replaceable. This is because the replacement transaction will pay the same outputs as the transaction being replaced (identical txids ensures this), so the recipients of the existing transaction have no reason to fear not being paid by the replacement transaction. Unlike RBF, all of the existing transaction’s descendants, if any, remain in the mempool.

Initially, we’ll limit this to single transactions (not packages); this can be reconsidered later.

DrahtBot added the label Validation on Jan 7, 2022

glozow commented at 1:05 pm on January 9, 2022: member

concept ACK :)

cc @ariard

glozow added the label TX fees and policy on Jan 9, 2022

in src/validation.cpp:1106 in b15079ac7b outdated

1053     // - it's not part of a package. Since package relay is not currently supported, this
1054-    // transaction has not necessarily been accepted to miners' mempools.
1055-    bool validForFeeEstimation = !bypass_limits && !args.m_package_submission && IsCurrentForFeeEstimation(m_active_chainstate) && m_pool.HasNoInputsOf(tx);
1056+    //   transaction has not necessarily been accepted to miners' mempools
1057+    // - this is not a witness replacement. Miners may not have witness replacement implemented
1058+    //   (yet). TODO: re-include witness replacements in v25.0

ariard commented at 0:06 am on January 10, 2022:

While I’ve seen protocol proposals leveraging same-txid-different-witness, I don’t know any of them which is effectively deployed now (?). If they’re and their usages is high enough to lead to a significant rate of witness conflicts, by that time I would expect this new replacement policy to be widely deployed in the miner ecosystem.

Of course, the majority of miners might run a different policy than the default Core’s one. Though, until the contrary is corroborated by periodic probing of miner’s mempools, I think we can reasonably hold the assumption they’re.

So to simplify, I lean to account witness replacement in fee estimation as early as this PR.

What do you think ?

glozow commented at 10:06 am on January 10, 2022:

The reasoning was based on #9519 - adding a witness replacement to the fee estimator isn’t really accurate unless miners are also allowing witness replacements. I think it’s reasonable to wait 1 or 2 releases for miners to update their policies? We just need to not forget to remove this bool. I imagine it’ll take some time for it to be used, anyway.

ariard commented at 0:24 am on January 10, 2022: member

Concept ACK, thanks for putting back on tracks witness replacement!

W.r.t 5%, I think that’s good enough given we should be upper bounded by MAX_STANDARD_TX_WEIGHT, that should give us two-digit number of replacements as a DoS worst-case. What’s your reasoning behind selecting this value ?

Maybe we would like to fine-tune to allow at least a 1-input/1-ouput Taproot spent, with a control block shorter by one node compared to the replaced transaction. I think one of the most probable witness replacement.

luke-jr commented at 7:44 am on January 12, 2022: member

We should probably use the same criteria for the feerate increase. Either this new criteria is safe to apply to other replacements, or it isn’t safe.

glozow commented at 10:28 am on January 14, 2022: member

We should probably use the same criteria for the feerate increase. Either this new criteria is safe to apply to other replacements, or it isn’t safe.

Just to clarify, what do you mean by “the same” criteria? Our current rules require an increase in absolute fees, which is not possible when the txid is the same.

theStack commented at 10:53 pm on January 22, 2022: contributor

Concept ACK

dunxen commented at 7:07 am on January 24, 2022: contributor

Concept ACK

Would it be worth documenting the behaviour in a new section of doc/policy/mempool-replacements.md in this PR, or are we just reserving that for RBF?

I’d need to try and convince myself whether 5% smaller witness is a reasonable anti-DoS or not.

brunoerg commented at 0:12 am on January 25, 2022: contributor

I understood the proposal by reading the functional test, however I couldn’t imagine a real use case that could reduce the witness. Could you please give an example?

LarryRuane commented at 5:08 pm on January 25, 2022: contributor

@brunoerg

I understood the proposal by reading the functional test, however I couldn’t imagine a real use case that could reduce the witness. Could you please give an example?

There’s some discussion of the motivations in #19645 but one simple example I can mention here involves Taproot. You may know that there are two ways to spend a Taproot output, the key path or the script path. The key path requires all participants to be in agreement with the spend and has a smaller witness. But suppose there is an absence of unanimous agreement, requiring broadcasting a transaction with an input using the script path (which has a large witness). While it’s in the mempool, agreement is reached, and the transaction is sent again but this time using the key path. It’s beneficial to the miner (in terms of feerate) and to the transaction participants (in terms of privacy and confirmation speed) if this second version of the transaction can replace the first, as this PR enables.

I believe this can happen when L2s (such as LN) integrate the use of Taproot, but I don’t understand the details.

brunoerg commented at 6:12 pm on January 25, 2022: contributor

@LarryRuane Great, thank you so much!

ziggie1984 commented at 10:59 pm on January 25, 2022: none

Hi @LarryRuane this PR needs a Rebase because of #21464 which intruduced mandatory parameters for UpdateTransactionsFromBlock() which needs now ancestor_size_limitand ancestor_count_limitthanks to lightlike who pointed me into this direction.

LarryRuane force-pushed on Jan 26, 2022

LarryRuane commented at 1:12 am on January 26, 2022: contributor

Force pushed to improve the test comments, no functional change.

DrahtBot commented at 4:11 am on January 26, 2022: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#27509 (Relay own transactions only via short-lived Tor or I2P connections by vasild)
#27353 (refactor (tidy): Fixes after enable-debug configure by TheCharlatan)
#26451 (Enforce incentive compatibility for all RBF replacements by sdaftuar)
#26403 ([POLICY] Ephemeral anchors by instagibbs)
#25038 (policy: nVersion=3 and Package RBF by glozow)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

LarryRuane force-pushed on Jan 26, 2022

LarryRuane commented at 5:21 am on January 26, 2022: contributor

Force pushed to resolve hidden conflict due to #21464.

unknown changes_requested

unknown commented at 7:36 am on January 26, 2022: none

Concept NACK

This change makes no sense and also mentioned by 2 other reviewers

darosior commented at 9:24 am on January 26, 2022: member

Concept ACK

luke-jr commented at 10:04 am on January 26, 2022: member

Just to clarify, what do you mean by “the same” criteria? Our current rules require an increase in absolute fees, which is not possible when the txid is the same.

Right. So for this to be consistent, those “current rules” would have to change. That’s either safe or not. If not, then it isn’t safe to do for this case either.

glozow commented at 10:33 am on January 26, 2022: member

@luke-jr agree, I should have clarified that we are indeed looking to propose a new set of RBF rules in general as well. I’ve been dragging my feet on it (sorry to everyone) but hopefully posting to ML soon.

michaelfolkson commented at 10:56 am on January 26, 2022: contributor

Concept ACK

I believe this can happen when L2s (such as LN) integrate the use of Taproot, but I don’t understand the details.

Maybe other L2s but LN wouldn’t use this (I don’t think). In LN you might broadcast a unilateral close (sending to a timelocked output) because your counterparty is unresponsive. Then your counterparty comes back online and you agree to do a cooperative close to replace the unilateral close with no timelocked output. But the transactions aren’t identical so you wouldn’t be able to make use of this.

I agree in principle that it makes no sense to prevent someone from using a smaller witness if for whatever reason they previously broadcast a larger witness than was necessary. But I also agree with Luke that it will be much easier to review these RBF PRs once we know what the updated RBF rules are. At the moment we are being asked to review PRs without knowing what the updated rules are.

sdaftuar commented at 3:21 pm on January 26, 2022: member

I’d still like to see a concrete use case (even just a proposal) before we consider merging support for this. This all seems very theoretical to me, and there are both code complexity concerns as well as anti-DoS concerns around using the network to relay transactions that never get mined. So if some protocol is relying on coordinating signatures for transactions by relaying messages on the bitcoin network rather than communicating over some other channel, I think we should be skeptical and carefully evaluate whether this makes sense. Does the bitcoin p2p network really need to serve as a communication medium for layer 2 protocols to construct efficient transactions?

Right. So for this to be consistent, those “current rules” would have to change. That’s either safe or not. If not, then it isn’t safe to do for this case either.

I believe this proposal is equivalent to reducing the minrelayfee for witness-replacement transactions by approximately a factor of 20 – you could imagine someone constructs a transaction with bloated witness which just meets the minrelayfee, and then repeatedly replaces it, dropping the size by 5% each time, resulting in using nearly 20x the bandwidth for the same total fee expended.

Presumably the 5% number could be changed to accommodate a more (or less) conservative bandwidth limit, but I don’t know how we should be picking it without knowing what use cases we are trying to support in the first place. So I tend to concept NACK, at least until we understand concretely what those use cases are.

theStack commented at 4:21 pm on January 26, 2022: contributor

Some small refactoring suggestions for the test:

 0--- a/test/functional/mempool_accept_wtxid.py
 1+++ b/test/functional/mempool_accept_wtxid.py
 2@@ -15,12 +15,10 @@ from test_framework.messages import (
 3     CTxIn,
 4     CTxInWitness,
 5     CTxOut,
 6-    sha256,
 7 )
 8 from test_framework.p2p import P2PTxInvStore
 9 from test_framework.script import (
10     CScript,
11-    OP_0,
12     OP_ELSE,
13     OP_ENDIF,
14     OP_EQUAL,
15@@ -29,9 +27,13 @@ from test_framework.script import (
16     OP_TRUE,
17     hash160,
18 )
19+from test_framework.script_util import (
20+    script_to_p2wsh_script,
21+)
22 from test_framework.test_framework import BitcoinTestFramework
23 from test_framework.util import (
24     assert_equal,
25+    assert_greater_than,
26 )
27
28 class MempoolWtxidTest(BitcoinTestFramework):
29@@ -59,9 +61,7 @@ class MempoolWtxidTest(BitcoinTestFramework):
30         parent.vin.append(CTxIn(COutPoint(int(txid, 16), 0), b""))
31
32         # Create a P2WSH output that the child that will be replaced will spend
33-        witness_program = sha256(witness_script)
34-        # This format (OP_0, <32-byte hash>) identifies this output as P2WSH
35-        script_pubkey = CScript([OP_0, witness_program])
36+        script_pubkey = script_to_p2wsh_script(witness_script)
37         parent.vout.append(CTxOut(int(9.99998 * COIN), script_pubkey))
38         parent.rehash()
39
40@@ -77,8 +77,7 @@ class MempoolWtxidTest(BitcoinTestFramework):
41         # This simple P2WSH pubkey is trivial to spend, will conveniently allow
42         # the grandchild to spend the child's output without needing a signature
43         simple_witness_script = CScript([OP_TRUE])
44-        simple_witness_program = sha256(simple_witness_script)
45-        simple_script_pubkey = CScript([OP_0, simple_witness_program])
46+        simple_script_pubkey = script_to_p2wsh_script(simple_witness_script)
47
48         # Create a new transaction with witness solving first (complicated) branch;
49         # in this case the witness contains the large_witness
50@@ -104,7 +103,7 @@ class MempoolWtxidTest(BitcoinTestFramework):
51         child_txid = child_original_txid
52         # Check the test itself; replacement transaction must be at least 5%
53         # smaller than the transaction being replaced.
54-        assert child_original.get_vsize() * 95 > child_replacement.get_vsize() * 100
55+        assert_greater_than(child_original.get_vsize() * 95, child_replacement.get_vsize() * 100)
56
57         self.log.info("Submit child to the mempool")
58         txid_submitted = node.sendrawtransaction(child_original.serialize().hex())

LarryRuane force-pushed on Jan 26, 2022

LarryRuane commented at 7:55 pm on January 26, 2022: contributor

Force-pushed to incorporate #24007#pullrequestreview-863782916, thanks, @theStack!

laanwj added the label Review club on Jan 26, 2022

JeremyRubin commented at 0:48 am on January 27, 2022: contributor

NACK, will follow up with the author privately

michaelfolkson commented at 2:27 pm on January 27, 2022: contributor

NACK, will follow up with the author privately

Not entirely sure why a justification for a NACK can’t be posted on a currently unmerged PR and why justifying it privately is somehow preferable. Regardless if the PR author summarizes whatever that justification is afterwards on the PR that’s fine I guess.

LarryRuane force-pushed on Jan 28, 2022

LarryRuane commented at 3:53 pm on January 28, 2022: contributor

Force-pushed to address review comments, except #24007 (comment) (still working on that).

DrahtBot added the label Needs rebase on Apr 7, 2022

in src/validation.cpp:482 in 61b2d79405 outdated

499@@ -498,6 +500,7 @@ class MemPoolAccept
500                             /* m_test_accept */ test_accept,
501                             /* m_allow_bip125_replacement */ true,
502                             /* m_package_submission */ false,
503+                            /* m_allow_witness_replace */ true,

fanquake commented at 10:39 am on April 7, 2022:

0                            /*m_allow_witness_replace=*/true,

Anywhere you are adding / touching named args, please use the style from the developer docs.

LarryRuane force-pushed on Apr 21, 2022

DrahtBot removed the label Needs rebase on Apr 21, 2022

LarryRuane force-pushed on Apr 21, 2022

LarryRuane commented at 7:22 pm on April 21, 2022: contributor

Force-pushed rebase to 86ead0f Force-pushed for review comment to af4bf1a

LarryRuane force-pushed on Apr 23, 2022

LarryRuane commented at 4:03 am on April 23, 2022: contributor

Force-pushed to d9b5b831fb to fix CI failure

glozow added the label Needs Conceptual Review on Aug 1, 2022

glozow commented at 10:37 am on August 1, 2022: member

Based on #24007 (comment) and discussion in https://bitcoincore.reviews/24007#l-181, marking this with “needs conceptual review” until more concrete use cases are given and the change has been discussed more thoroughly on e.g. the ML.

DrahtBot added the label Needs rebase on Aug 3, 2022

LarryRuane commented at 6:07 am on August 10, 2022: contributor

@sdaftuar re #24007 (comment)

I agree we need a more solid use case or cases, but just a general thought:

Could rate-limiting mitigate the DoS attack surface? If an attacker submitted the same transaction with incrementally smaller witnesses 20 times, could the node not accept (or relay) the new transaction if the one it’s replacing was accepted and relayed less than so many seconds ago? Maybe implement an exponential backoff policy by requiring an ever-greater delay before accepting the next version of the same transaction.

It’s true that the total required bandwidth would be the same, but if it’s spread out over many minutes or hours, it would be less of a practical DoS threat.

[mempool] allow tx replacement by smaller witness

Currently, an existing mempool transaction can't be replaced by a tx
that's identical except for its witness (same txid, different wtxid);
the request is rejected as a duplicate. Change this behavior such that
the mempool will replace the existing tx if the new tx has a smaller
witness by at least 5% (an anti-Dos measure).

Co-authored-by: glozow <gloriajzhao@gmail.com>

04fe371549

LarryRuane force-pushed on Nov 7, 2022

DrahtBot removed the label Needs rebase on Nov 7, 2022

LarryRuane commented at 7:08 am on November 7, 2022: contributor

Force-pushed rebase to fix conflicts. @sdaftuar re #24007 (comment)

I believe this proposal is equivalent to reducing the minrelayfee for witness-replacement transactions by approximately a factor of 20 – you could imagine someone constructs a transaction with bloated witness which just meets the minrelayfee, and then repeatedly replaces it, dropping the size by 5% each time, resulting in using nearly 20x the bandwidth for the same total fee expended.

Good point. Is the following a possible solution?: Have the mempool keep track of the sum of the sizes of all versions of this transaction (same txid, different witnesses) that it has accepted and relayed, and require that this sum satisfy minrelayfee as a condition of accepting a newer version of the tx.

This would incentivize submitters to supply an initial fee large enough to cover the anticipated series of replacements. If it’s not possible to submit another version of the transaction due to this constraint, it’s not the end of the world; the existing (latest accepted and relayed) transaction remains in the mempool (and presumably will eventually get mined) – this is no worse than today.

Another benefit may be that we could eliminate the requirement that the replacement tx be at least 5% smaller than the existing tx. Instead, the only size constraint would be that the replacement is strictly smaller.

A possible objection here is that an attacker could submit a series of transactions that are each one byte smaller than the previous, thus “using up” the entire minrelayfee, so that the honest party is no longer able to replace the transaction. But two points seem relevant: First, this is no worse than today, since witness-replacement is currently impossible. Second, all these transactions have the same effect on the UTXO set, so the inability to submit a replacement transaction could not be preventing (for example) a layer-2 penalty transaction.

JeremyRubin commented at 2:12 am on November 9, 2022: contributor

One idea that comes to mind that would mitigate DoS but still provide utility in the way I think this might be intended to be used:

Only allow going from a Tr script path to a Tr key path.

This ensures that the witness replacement can only happen once, and prioritizes lazy cooperation.

If APO is added later, another allowable replacement can be added for the 0x01 top branch script.

sdaftuar commented at 2:44 pm on November 9, 2022: member

@LarryRuane It’s hard to evaluate what the right strategy is for mitigating potential network DoS in these cases, without first understanding the use cases we’re trying to support.

At the highest level, I’d say that there’s a benefit to never writing the code or figuring out rules to support tx-replacement-via-smaller-witness if that meant that we just deter all possible protocols people might otherwise come up with which would use our public relay network unnecessarily. If people can figure out a way to relay the best version of their transactions the first time, that’s a strict win for the public relay network.

Expanding on that more: I think a really important idea is that we influence behavior on the network via the policy choices we implement and support. Inventing a standard in the absence of a use case is risky, both because we might encourage unintended behaviors which are bad for the network (and would otherwise have been avoided), and because we add more complexity to our code base without a corresponding benefit.

On the other hand, if there is a use case / protocol where relaying alternate versions of the same txid might arise, we should just talk about what those are, because I would agree that we should find a way to support behaviors that users need and have economic value, to discourage the development of private relay to miners (which would be damaging to the ecosystem).

So regarding your specific proposal: I’m really not sure; something like that might work? But I don’t think it’s worth adding that kind of complexity to our code when we don’t know what specific use cases we’re even trying to reason about.

glozow commented at 3:32 pm on April 25, 2023: member

Closing as there doesn’t seem to be much support for this change - it’s still unclear whether any use cases exist. If something changes, please feel free to comment and we can revisit this at a later time.

glozow closed this on Apr 25, 2023

joostjager commented at 6:33 am on June 7, 2023: none

Regarding use cases: perhaps the potential coinjoin problem with annexes mentioned in https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-June/021736.html can be mitigated with this PR.

If large annexes can be replaced by smaller annexes (same txid, different wtxid), it may not be possible anymore for an attacker to inflate the annex and get it pinned.

joostjager commented at 8:43 am on June 15, 2023: none

In the thread above, an idea came up that could be relevant for this PR in a world where the annex is enabled: In addition to the minimum reduction of 5%, a transaction with an empty annex is also always accepted as a replacement. This prevents an attacker from publishing with an annex that inflates the witness by 4.99% and preventing it from being replaced in the context of a protocol that doesn’t use the annex at all.

bitcoin locked this on Jun 14, 2024

[mempool] allow tx replacement by smaller witness #24007

Conflicts