Allow updating mempool-txn with cheaper witnesses

ariard commented at 6:18 pm on August 2, 2020: member

Accepting a transaction to the mempool only succeeds if this transaction isn’t already present. This check operating on txid, it prevents new submissions of the transaction with identical non-witness data but smaller valid witnesses. Therefore, overall mempool feerate won’t improve even if such higher-feerate mempool candidate is learnt through wtxid-relay.

This commit changes mempool and transaction broadcast already-present checks from transaction’s txid to its wtxid.

A new-wtxid submission may still fail due to replacement rules in function of local policy settings. @jnewbery RE: #18044 (review) I think we agree on the “same txid, different txids” nonsense, I didn’t mean to track multiple witnesses for one txid rather to accept and rebroadcast “the best mempool candidate known for a given txid”. A script may have alternatives solvable branches and witnesses to spend them might be different in weight thus creating wtxid with divergent feerates. A best known candidate with regards to a txid is defined as a higher-feerate witness (a smaller one) transaction than our current in mempool one, with identical non-witness data.

You might submit a txidA:wtxid1 to your local node, and schedule it for initial-broadcast reattempt. Few minutes, latter you announce to your node a higher-feerate txidA:wtxid2, which effectively replace wtxid1. At ReattemptInitialBroadcast, only wtxid2 will be rebroadcast if needed, as best known candidate for txidA. According to me, that’s where unbroadcast semantic is unclear, to which wtxid the user should expect seeing “broadcast-reattempt” property guarantee ?

Given our current relay policy default, I concede this is rather a marginal case, beyond illustrating another limit of our mempool replacement rules. In the future, it’s likely to worsen as taproot make it far easier to create witnesses with divergent feerates (e.g a 1-of-1 tapscript compared to a 15-of-15 one). In case of concurrent broadcast, the mempool won’t necessary learn the best-feerate candidate. That said, IMO, it’s worthy to fix because “txn-already-in-mempool” isn’t accurate anymore in a wtxid-relay context.

DrahtBot added the label Tests on Aug 2, 2020

DrahtBot added the label Validation on Aug 2, 2020

DrahtBot commented at 8:11 pm on August 2, 2020: member

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#19339 (validation: re-delegate absurd fee checking from mempool to clients 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.

JeremyRubin commented at 8:35 pm on August 2, 2020: contributor

i’m leaning toward a concept nack.

I don’t think this is urgent to fix and incentivizes using the mempool as working space for negotiating smaller witnesses, rather than attempting to produce a smaller signature on first broadcast. Further, this opens up potential attacks where you can make malleable smaller and smaller witnesses and keep resubmitting to boost feerate or something. I also think it’s sufficiently rare that we’d even have smaller valid witnesses to submit, but then if someone starts relying on this behavior we’re stuck supporting it forever.

where you might convince me that it’s a problem is if Alice and Bob are doing a payjoin or something, and then Bob changes his witness to be an even bigger one and then broadcasts, locking Alice onto a lower fee rate for the transaction.

But again, on urgency, these replacement policies are really only relevant once more complex taproot scripts are widely deployed and a change like this can be added to a future release policy easily.

ariard commented at 9:37 pm on August 2, 2020: member

I don’t think this is urgent to fix and incentivizes using the mempool as working space for negotiating smaller witnesses, rather than attempting to produce a smaller signature on first broadcast.

I think the notion of first broadcast doesn’t hold when you have multiple-party involved with alternatives spending paths and so potential concurrent broadcasts. Parties can’t produce smaller signatures because key distribution across script branches encodes a policy, it can be either Alice or Bob+Caroll+Dave, where Alice has a higher level of privileges. As a practical example you might have pre-signed vault transactions, like https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-April/017793.html

Further, this opens up potential attacks where you can make malleable smaller and smaller witnesses and keep resubmitting to boost feerate or something.

You’re still liable to RBF rules compliance, especially rule 4 on incremental relay fee ?

where you might convince me that it’s a problem is if Alice and Bob are doing a payjoin or something, and then Bob changes his witness to be an even bigger one and then broadcasts, locking Alice onto a lower fee rate for the transaction.

As a first step you should avoid to introduce witness malleability if parties are distrusted, and currently as I mentioned it won’t likely propagate due to default mempool settings. But yes if we change it in the future, it would be a limited guardrail for this kind of scenario.

There is no urgency to fix, it’s more making consistent our relay wtxid-policy with our mempool one.

ariard force-pushed on Aug 2, 2020

jnewbery commented at 12:21 pm on August 3, 2020: member

Concept ACK. As long as this is re-using the BIP125 RBF logic, then I can’t see how it can be any more of an attack vector than any other kind of RBF.

these replacement policies are really only relevant once more complex taproot scripts are widely deployed and a change like this can be added to a future release policy easily.

I think we’d want this widely deployed before such scripts were possible.

ShawkiS approved

sdaftuar commented at 1:12 pm on August 5, 2020: member

Conceptually I agree this would be a reasonable (incentive-compatible) behavior, but I’m not sure this is worth the complexity/effort to implement this change. To do this correctly, you’d also want to not evict all the descendants of the replaced transaction in situations like this, which I think means more special cased mempool acceptance logic.

Is there any application out there that would expect to use this behavior? I know this is fun to theorize about but it’s hard for me to imagine there will be anyone using this – so I am skeptical this is worth the effort and added code complexity.

JeremyRubin commented at 4:53 pm on August 5, 2020: contributor

@sdaftuar I think the issue is more that an adversary can use it.

E.g., say I do a coinjoin with you, and we create a txn with a feerate A and a witness weight of X. Then, as one of the parties to the txn, I create a much heavier witness weight 2X, and decrease the feerate to like 0.7A. Now it takes forever to confirm.

So it’s less so someone using it, than abusing it.

sdaftuar commented at 5:03 pm on August 5, 2020: member

E.g., say I do a coinjoin with you, and we create a txn with a feerate A and a witness weight of X. Then, as one of the parties to the txn, I create a much heavier witness weight 2X, and decrease the feerate to like 0.7A. Now it takes forever to confirm.

I get that this is a theoretical concern, but has this ever actually happened to anyone? I can imagine there could be lots of reasons why behavior like this would not actually take place in practice.

If stuff like this has happened, then I can get on board with wanting to deal with it in the right way.

[validation] Allow wtxid-acceptance to mempool

Accepting a transaction to the mempool only succeeds if this transaction
isn't already present. This check operating on txid, it prevents new
submissions of the transaction with identical non-witness data but
smaller valid witnesses. Therefore, overall mempool feerate won't improve
even if such higher-feerate mempool candidate is learnt through wtxid-relay.

This commit changes mempool and transaction broadcast already-present checks
from transaction's txid to its wtxid.

A new-wtxid submission may still fail due to replacement rules in
function of local policy settings.

d02c78ac01

[functional] Add mempool_wtxid.py

Broadcast consequently two identical child transactions with size-divergent
witnesses and thus different feerate. The second broadcast should successfully
replace the first one.

Add assert_not_equal helper in test_framework/util.py

d86e7a1708

ariard force-pushed on Aug 6, 2020

ariard commented at 9:42 am on August 6, 2020: member

To do this correctly, you’d also want to not evict all the descendants of the replaced transaction in situations like this, which I think means more special cased mempool acceptance logic.

I agree in-place substitution while conserving chain of transactions would be better bandwidth-wise. But that would require special RBF rules to handle it and I think it’s better to strictly bound to our current RBF rules to make it easier to reason on. We already have the same issue with someone replacing a parent tx with a new txid and advertising again a chain of transaction paying the same outputs. Cheap RBF replacement should be addressed on its own, this PR doesn’t pretend to make it better or worse ?

Is there any application out there that would expect to use this behavior?

Beyond preventing abuse for potential coinjoin/payjoin/vaults and easing future usage for taproot branches, as of today there is the practical usage of selecting your best-feerate witness among a set of valid ones. I don’t think a lot of users have yet this mental model but I expect this to change with wider adoption of Miniscript.

Updated with better comment/logs. Let me know if you think it’s worthy further review time otherwise I would close it.

naumenkogs commented at 10:12 am on August 6, 2020: member

E.g., say I do a coinjoin with you, and we create a txn with a feerate A and a witness weight of X. Then, as one of the parties to the txn, I create a much heavier witness weight 2X, and decrease the feerate to like 0.7A. Now it takes forever to confirm.

I think this concern is indeed valid and the problem should be addressed. However, it’s hard for me to justify at which cost (code complexity) we want to address it.

We also want to make sure that this solution is indeed sufficient and the best alternative among others.

ariard commented at 12:34 pm on August 6, 2020: member

We also want to make sure that this solution is indeed sufficient and the best alternative among others.

Just to clarify, this current proposal doesn’t effectively mitigate this without further change to our RBF handling due to the default incrementalrelayfee value. However, as my previous comment aims to underscore, it does provide value today for users with alternative script branches, as a tool to select the best-feerate witness, assuming a local policy of incrementalrelayfee=0.

I think mitigating low-feerate pinning is an orthogonal discussion, see #14895 (comment)

IMO, the code complexity of the current proposed PR is straightforward as it doesn’t interfere with RBF.

ajtowns commented at 4:21 pm on August 11, 2020: member

Suggest calling this “updating tx with cheaper witness” or similar – “wtxid-acceptance” is pretty generic, it’s more analogous to “replace by fee”, except that you’re not even replacing anything as far as the txid goes, which is 99% of what matters? I believe the rule is “txid remains the same but overall weight decreases; so only witness data can change, tx fee rate increases, and no descendants are evicted from the mempool”. (Note the taproot bip raises the possibility of weight being artificially increased in some cases, so the witness data might strictly be larger despite the tx weight decreasing)

luke-jr commented at 8:13 pm on August 11, 2020: member

Concept ACK

ariard renamed this:
~~Allow wtxid-acceptance to the mempool~~
Allow updating mempool-txn with cheaper witnesses
on Aug 13, 2020

ariard commented at 2:24 pm on August 13, 2020: member

@ajtowns Good call, took your suggestion. Initially called it “wtxid-acceptance” as this is literally what this PR does, evaluating an already-present utxo-spend candidate on wtxid rather than txid. In practice, I agree that txid is what matters, like evaluating descendants limits. Note, for implementation simplicity, it does evict descendants from mempool, we can implement in-place substitution as a follow-up if it feels needed.

For the taproot hint, I think that rational holds, as from the miner viewpoint you want to increase feerate per weight unit. I don’t think that effective memory-space of these weight units is a burden for miner mempools.

JeremyRubin commented at 3:27 pm on August 13, 2020: contributor

@ariard does it make sense to attempt to merge the witnesses into a lowest fee form? E.g. if witA[0] > witB[0], but witA[1] + withA[0] < witB[0] + withB[1] it may make sense to make a new witC comprised of the best of both.

ariard commented at 9:06 pm on August 20, 2020: member

@JeremyRubin Do you mean cross-inputs, i.e if we learn wtxid_1:(witA, witB) and wtxid_2:(witA’, witB’) and witA > witA’ and witB < witB’ we select witA and witB’ to compose new wtxid_3 ? Or single-input, if by decomposing multiple known witnesses and analyzing witnessScript we’re able to compress to a better feerate witness ?

Either way, I think what your question is raising is a separation of concerns across the bitcoin stack. I don’t think that’s the job of network mempools to optimize your spends based on a set of witness element you may have broadcasted. This sounds like a new DoS vector and you would need to pay for the CPU time, thus reducing worthiness of operation.

I think that composing best-feerate witness in function of your solvable scripts paths is better done by a higher tool. Of course, this software may not implement correctly all weight accounting rules, especially post-Taproot, so this PR allows you to verify composed witnesses against your local mempool, assuming you set incrementalrelayfee=0.

ariard commented at 9:39 pm on August 20, 2020: member

@sdaftuar

I get that this is a theoretical concern, but has this ever actually happened to anyone? I can imagine there could be lots of reasons why behavior like this would not actually take place in practice.

While opening this PR, I thought too it was a theoretical concern, but reviewing the DLC specs last week, such protocol would be vulnerable to witness weight inflation discussed here. And a honest participant can’t rely on RBF as it’s easy for a malicious party to attach a high-absolute-fee, low-feerate chain of transactions to its change output

Of course you can adopt carve-out mechanism and ensure you don’t have more than one immediately spendable output by party but this come with far less protocol flexibility and you might loss few blocks between initial broadcast and trigger of your fee-bump.

I agree that change advocated in this PR won’t fix it without further modifications to our RBF policy but it’s at least a minimal prerequisite.

Or do you think we should first have a broader discussion on the mental model that higher protocol designers should adopt with regards to our mempool/relay policy ?

JeremyRubin commented at 11:27 pm on August 20, 2020: contributor

@JeremyRubin Do you mean cross-inputs, i.e if we learn wtxid_1:(witA, witB) and wtxid_2:(witA’, witB’) and witA > witA’ and witB < witB’ we select witA and witB’ to compose new wtxid_3 ? Or single-input, if by decomposing multiple known witnesses and analyzing witnessScript we’re able to compress to a better feerate witness ?

Either way, I think what your question is raising is a separation of concerns across the bitcoin stack. I don’t think that’s the job of network mempools to optimize your spends based on a set of witness element you may have broadcasted. This sounds like a new DoS vector and you would need to pay for the CPU time, thus reducing worthiness of operation.

It’s not optimizing your spends, it’s optimizing miner revenue, which is ~the whole point.

In terms of DoS the issue that also occurs is that someone can malicious anti-merge your better witness, e.g.,

I see B which is better for every input then A, and then I cut B’s witness with half A’s witnesses, then broadcast. Now B is not minrelay increment better than half B half A, so i get pinned.

MarcoFalke removed the label Tests on Aug 23, 2020

MarcoFalke removed the label Validation on Aug 23, 2020

MarcoFalke added the label TX fees and policy on Aug 23, 2020

glozow commented at 11:41 pm on October 5, 2020: member

“txn-already-in-mempool” isn’t accurate anymore in a wtxid-relay context.

I think at the very least there should be a clearer error for this. AFAIK right now a user would have to guess that the one in mempool has a different witness and then use getrawmempool or getrawtransaction to confirm?

In terms of DoSing, it seems to me that this is essentially “RBF taking into account witness data” (is that incorrect?) and can thus be evaluated in a similar manner.

DrahtBot commented at 4:25 am on October 7, 2020: member

🐙 This pull request conflicts with the target branch and needs rebase.

Want to unsubscribe from rebase notifications on this pull request? Just convert this pull request to a “draft”.

DrahtBot added the label Needs rebase on Oct 7, 2020

ariard commented at 6:15 pm on October 7, 2020: member

@glozow

I think at the very least there should be a clearer error for this. AFAIK right now a user would have to guess that the one in mempool has a different witness and then use getrawmempool or getrawtransaction to confirm?

Good idea, that’s maybe better for now to return a new error for an unsuccessful sendrawtransaction due to an already-present txid-with-different-wtixd. I’ll open separately with the test.

In terms of DoSing, it seems to me that this is essentially “RBF taking into account witness data” (is that incorrect?) and can thus be evaluated in a similar manner.

In the context of multi-party protocol (e.g a CoinSwap, LN), what is concerning is a pinning (https://bitcoinops.org/en/topics/transaction-pinning/) where a malicious participant inflate a provided witness to delay a time-locked transaction either for timevalue-DoS or plainly stealing funds due to concurrent claiming.

Because for the fix to be effective you need to change the RBF logic from requiring an absolute fee increase between 2 transactions from a feerate relative increase (see https://github.com/bitcoin/bitcoin/blob/283a73d7eaea2907a6f7f800f529a0d6db53d7a6/src/validation.cpp#L910) . Currently, with a default incrementalrelayfee > 0, this PR isn’t not going to mitigate the pinning issue network-wise as the absolute fee is committed as part of the txid and thus is strictly the same between a divergent-wtxids/equivalent-txid transaction pair.

It needs more thoughts that the current PR which is more providing locally fee estimation between different witnesses to a user.

laanwj referenced this in commit 8ab0c77299 on Jul 9, 2021

DrahtBot commented at 11:21 am on December 15, 2021: member

Is it still relevant? ➡️ Please solve the conflicts to make it ready for review and to ensure the CI passes.
Is it no longer relevant? ➡️ Please close.
Did the author lose interest or time to work on this? ➡️ Please close it and mark it ‘Up for grabs’ with the label, so that it can be picked up in the future.

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

Closing, superseded by #24007

ariard closed this on Jan 10, 2022

DrahtBot locked this on Jan 10, 2023

Allow updating mempool-txn with cheaper witnesses #19645

Conflicts