Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Mempool DoS risk in segwit due to malleated transactions #8279

Closed
petertodd opened this issue Jun 28, 2016 · 11 comments
Closed

Mempool DoS risk in segwit due to malleated transactions #8279

petertodd opened this issue Jun 28, 2016 · 11 comments
Labels

Comments

@petertodd
Copy link
Contributor

@petertodd petertodd commented Jun 28, 2016

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

@sdaftuar

This comment has been minimized.

Copy link
Member

@sdaftuar sdaftuar commented Jul 7, 2016

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

This comment has been minimized.

Copy link
Contributor Author

@petertodd petertodd commented Jul 9, 2016

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

This comment has been minimized.

Copy link

@chjj chjj commented Jul 10, 2016

@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

This comment has been minimized.

Copy link
Member

@sdaftuar sdaftuar commented Jul 10, 2016

@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

This comment has been minimized.

Copy link
Member

@sipa sipa commented Jul 10, 2016

Some ideas (based on an IRC discussion yesterday):

  1. Switch to a wtxids based invs/getdatas, as well as wtxid-indexed mempool, relay pool, and p2p logic.
  2. 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).
  3. 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.
  4. 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.
  5. 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 laanwj closed this in #8312 Jul 14, 2016
@sdaftuar

This comment has been minimized.

Copy link
Member

@sdaftuar sdaftuar commented Jul 14, 2016

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

@sipa sipa reopened this Jul 14, 2016
@sdaftuar

This comment has been minimized.

Copy link
Member

@sdaftuar sdaftuar commented Aug 4, 2016

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

This comment has been minimized.

Copy link
Member

@sipa sipa commented Aug 16, 2016

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):

19: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
...
19:47:34 <sipa> morcos: i like that... but i think it's a big change for 0.13.1
...
19: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
19:48:27 <sipa> morcos: ack
19:48:32 <morcos> we can see how easy and short he other 2 are
@sdaftuar

This comment has been minimized.

Copy link
Member

@sdaftuar sdaftuar commented Sep 13, 2016

@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

This comment has been minimized.

Copy link
Contributor

@jl2012 jl2012 commented Sep 16, 2016

@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 laanwj removed this from the 0.13.1 milestone Sep 22, 2016
@petertodd petertodd closed this Feb 11, 2017
@danra

This comment has been minimized.

Copy link
Contributor

@danra danra commented Sep 29, 2017

@laanwj Is this intentionally still under "Current issues"?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
8 participants
You can’t perform that action at this time.