Mempool DoS risk in segwit due to malleated transactions

petertodd commented at 2:06 pm on June 28, 2016: contributor

Noticed this in my code review: https://petertodd.org/2016/segwit-consensus-critical-code-review#peer-to-peer-networking

Basically it looks like an attacker may be able to send nodes transactions with malleated witness data, which we don’t consistently mark as possibly corrupted in AcceptToMemoryPool(). Result would be those txids being added to recentRejects, messing up propagation.

That said, I haven’t actually tested this yet; about to go off to a conference, so if someone else wants to confirm for me that’d be much appreciated! Or if I’m wrong you’re welcome to all laugh at my expense. :)

CC: @sdaftuar @sipa

laanwj added the label P2P on Jun 28, 2016

laanwj added the label Mempool on Jun 28, 2016

laanwj added the label Priority High on Jun 28, 2016

sdaftuar commented at 3:07 pm on July 7, 2016: member

Looks like in addition to this problem, there are several other similar issues where being given the wrong witness could blind a node to a transaction:

sigops checks (both the overall sigops check as well as the bytes-per-sigop check)
ancestor/descendant size
replace-by-fee logic

petertodd commented at 11:04 pm on July 9, 2016: contributor

Hmm, that’s a reasonably long list.

I know we spoke a bit about how a wtxid-based mempool could work; might be worthwhile writing some of that down for sake of reference, and figuring out what it’d look like if we released segwit as-is and then added that on later.

chjj commented at 4:45 am on July 10, 2016: none

@petertodd, if the mempool and rejects filter worked based on wtxid, would INV packets also be updated to work based on wtxid? If not, the rejects filter would be useless since the node needs to know to not re-request rejected txs that are listed in INVs (which only use txid).

There might still be a solution here to avoid changing the p2p protocol and mempool. The one I’m thinking of: if the GetTransactionCost() check fails, do a contextual check on the on the tx to verify that the witnesses are actually redeeming witness program coins. If they’re not, ban the peer but do not add the txid to the rejects filter.

Maybe do this for every failure before it gets to the contextual checks. Once it hits the contextual checks in the mempool, AreInputsStandard could check to make sure witnesses are redeeming witness program coins before continuing.

Not ideal, but maybe good enough in practice.

edit: Hmm, nevermind my idea. I guess an attacker could still mutate real witness transactions without changing the txid. A wtxid mempool+inv-packets might be the only solution. This is rough.

sdaftuar commented at 11:30 am on July 10, 2016: member

@chjj I hadn’t written it up yet, but this is what I concluded as well. Post-segwit, the fee rate check that we perform to determine whether a transaction might be able to enter the mempool can fail, without us being able to tell whether the txid is permanently bad – eg for all you know there exists some slightly smaller witness which causes the feerate to be just high enough to make it in to the mempool.

As I think the fee rate check is far and away the most valuable thing to be caching success/failure in recentRejects, either we have to scrap that performance improvement, or maybe rework mempool acceptance to not perform these checks until after scripts have been validated (not sure how feasible this would be), or somehow remember and request transactions based on what we remember about the particular witness we previously evaluated. This last approach – reworking the p2p-layer to be based on wtxid’s when upgraded peers communicate – seems the most logical to me, but others may have a different view?

sipa commented at 12:14 pm on July 10, 2016: member

Some ideas (based on an IRC discussion yesterday):

Switch to a wtxids based invs/getdatas, as well as wtxid-indexed mempool, relay pool, and p2p logic.
Relay resource cost information along with invs (fees, size, sigops). This would allow the receiver to decide ahead of time whether to accept a transaction, removing this as reason for entering the rejection cache (making it much less needed).
Alternatively, extend BIP133 (feefilter) to have mandatory behaviour. This effectively does the same as (2), except the sender is responsible for filtering ahead of time.
Remove the “invalid witness does not cause insertion in rejectioncache” rule entirely. This would simplify the code a lot, and (with the current protocol) does not allow an attacker to do anything they can’t do already (independent from segwit), namely preventing a single peer from hearing about a transaction before it confirms. The rule does not work when transactions have intentionally malleable witnesses anyway.
Verify all received transactions fully (assuming we requested them), even if we know we won’t accept them due to feerate limits. This would allow us to determine conclusively whether the transaction was invalid (in which case we should never ask for it again) or malleated (in which case we should ban the node that sent it, but ask for it again from other peers). This has been suggested long before segwit as a means to detect other DoS attacks. Since by the time we get this option we’ve done most of the work already anyway (bandwidth was wasted, and UTXO entries were retrieved from the database), doing the actual script validation is not a huge amount of work anymore.

My preference is initially just (4), and perhaps (3) and (5) at some point as orthogonal optimizations. Things like (1) and (2) can be incorportated in a future reworked relay mechanism, perhaps one that works based on mempool synchronization rather than individual transaction relay.

I expect (4) to be the most controversial option, but it is also the only one that actually simplifies implementation.

laanwj closed this on Jul 14, 2016

sdaftuar commented at 12:36 pm on July 14, 2016: member

Oops, this should be reopened, as #8312 ended up just being a workaround for 0.13.0 and not a fix for segwit.

sipa reopened this on Jul 14, 2016

sdaftuar commented at 6:57 pm on August 4, 2016: member

Remove the “invalid witness does not cause insertion in rejectioncache” rule entirely. This would simplify the code a lot, and (with the current protocol) does not allow an attacker to do anything they can’t do already (independent from segwit), namely preventing a single peer from hearing about a transaction before it confirms. The rule does not work when transactions have intentionally malleable witnesses anyway.

This strikes me as problematic, as it seems like it’d be very straightforward for an attacker to harm transaction relay across the network by appending junk witness data, causing a transaction to fail to propagate. It only requires one connection slot to many peers to cause this kind of failure (as opposed to announcing but not delivering a tx, which requires at least taking up numerous connection slots of a peer to be effective, since we try to request a given transaction several times before giving up – also this p2p logic could be improved, say by preferring tx downloads from outbound peers, or disconnecting nodes that have high tx-withholding rates, etc).

(3) seems fine in concept, but insufficient to address this issue by itself.

(2) might be sufficient now, and may be a reasonable change in our current environment, but it seems to me like there might at some point be a gap between what we announce with the inv and what we use for policy limits, and having to adapt the p2p layer to adjust for policy changes seems like a bad road to go down. (For instance, if we were to impose a policy rule on the size of the witness stack, then this would be insufficient.)

(1) seems like the most obviously correct solution to me, as it directly addresses the issue (namely, whether we have processed the same data before), and is analogous to what we do pre-segwit (use a tx identifier that commits to all the tx data). (5) seems like it might also be a reasonably robust solution, but with the wide range of scripts now permitted I don’t have an intuition for whether this could be problematic as a potential CPU-DoS issue, and there’s an extra mental leap regarding transactions with intentional malleability (no idea if such things exist on the network today though), that makes it slightly harder to reason about.

So I’d propose we do (1), even though it’s a bit of a bigger change at the p2p level.

sipa commented at 1:47 pm on August 16, 2016: member

From the august 4 2016 IRC meeting logs (http://www.erisian.com.au/meetbot/bitcoin-core-dev/2016/bitcoin-core-dev.2016-08-04-19.00.log.html):

019:46:20 <morcos> proposal: make feefilter mandatory. fully validate txs so we can punish peers who send us invalid stuff. don't put any witness tx in the rejection cache.  then evaluate how useful rejection cache continues to be or whether we have policy violating segwit txs bouncing around
1...
219:47:34 <sipa> morcos: i like that... but i think it's a big change for 0.13.1
3...
419:48:10 <morcos> sipa: i think if we start with " don't put any witness tx in the rejection cache" then we'll be ok
519:48:27 <sipa> morcos: ack
619:48:32 <morcos> we can see how easy and short he other 2 are

jonasschnelli added this to the milestone 0.13.1 on Sep 1, 2016

sdaftuar commented at 6:42 pm on September 13, 2016: member

@sipa So I believe that after #8525, this particular issue has now been addressed, agreed?

The remaining items suggested would be optional improvements:

Make feefilter mandatory
Fully validate txs so we can punish peers who send us invalid stuff.

If we want to do the first thing, I think it’d make sense to draft a BIP update to feefilter that details how this would work, and announce it on the mailing list to get feedback in advance of deployment.

I think the second thing (fully validating transactions in general and disconnecting bad peers) is something being considered for a future release. See #8593.

jl2012 commented at 6:11 pm on September 16, 2016: contributor

@sdaftuar I think 1c0df59 and 9199ff2 in #8499 will also help. They will protect any P2WPKH and canonical multisig P2WSH from malleation attack.

#8593 is a long term goal when we have better sighashing protection

laanwj removed this from the milestone 0.13.1 on Sep 22, 2016

petertodd closed this on Feb 11, 2017

danra commented at 9:11 pm on September 29, 2017: contributor

@laanwj Is this intentionally still under “Current issues”?

laanwj removed this from the "Current issues" column in a project

laanwj referenced this in commit ccef10261e on Jul 22, 2020

sidhujag referenced this in commit bdb259705d on Jul 24, 2020

DrahtBot locked this on Feb 15, 2022

Mempool DoS risk in segwit due to malleated transactions #8279