Disposing of "dust attack" UTXOs

Implementation
21

Link to latest revision of draft BIP is: https://github.com/bubb1es71/ddust/blob/main/docs/bip-dust-disposal.md

1 Like
22

The details seem a bit tailored to Bitcoin Core’s current policy.

SIGHASH_NONE|SIGHASH_ANYONECANPAY would allow 1 input, ash OP_RETURN output transactions to be constructed and then aggregated by a third party into a transaction with an empty OP_RETURN output. However, this also allows miners or third party aggregators to add txouts. As far as I can tell that makes no difference, i.e. does not increase DoS concern.

Alternatively, if OP_RETURN ash was always required (i.e. not allowing empty OP_RETURN), then there would be just one class of such transactions that can always be aggregated into a valid transaction, with 3 virtual bytes of shared overhead even when that is unnecessary. The rationale section for SIGHASH_ALL|SIGHASH_ANYONECANPAY only discusses the ANYONECANPAY part and not ALL vs NONE.

However, it seems to me like a policy carveout for single input, empty OP_RETURN output transactions would be even better? This allows the smallest single output txs, and does not present any more of DoS concern than what is already allowed.

Furthermore, if every dust input was relayed separately in a standalone minimal transaction, and always aggregated in the mempool using deterministic sorting rules, this would effectively be a carveout for the entire space of aggregate transactions, removing the need for any replacement logic for such transactions, which is asymptotically optimal bandwidth per output destroyed and maximizes revenues. This is backwards compatible in that peers that do not understand aggregation at all could simply enforce current standardness rules and replacement rules while still relaying 1 input 1 output transactions that could be aggregated by miners etc, but that requires either the 3 vbyte overhead of ash or SIGHASH_NONE to be blockspace optimal.

23

Thanks for these helpful insights. I will address them in order.

Yes, part of the motivation for this proposal was the ability of Bitcoin Core 30.0+ to relay sub 1 sat/vb fee-rate txs. But I see your point that we don’t need to specify a specific fee rates in the proposal since the standard min fee rate could change over time (up or down). I’ll see if I can remove unnecessary restrictions that tailor it for Bitcoin Core’s current policy.

My original concern with SIGHASH_NONE|SIGHASH_ANYONECANPAY was that dust disposal tx with high enough amounts would get poached into transactions with a regular output and take up more space on-chain. But I think you’re correct, allowing batching to remove the “ash” marker is more important. If someone is able to poach these dust inputs into a tx with other types of outputs they still need to follow the RBF rules so this isn’t a spam vector. If @harris and other’s agree I’m good with this change, and will add these thoughts to the rationale section of the draft BIP.

I’m now leaning towards your SIGHASH_NONE|SIGHASH_ANYONECANPAY approach.

I agree that even with SIGHASH_NONE|SIGHASH_ANYONECANPAY original disposal tx should never have the OP_RETURN “ash” if not needed. I expect many/most disposal tx won’t get batched or poached so need to make them as efficient as possible.

Are you talking about mempool signature aggregation here?

Anyway I don’t want to rely on any mempool or dedicated third-parties batching/aggregating disposal tx inputs in a certain way. I think it will be more reliable (even if less efficient) to let any wallets do it opportunistically when they find other dust disposal txs in the mempool at the same time they are creating their dust disposal tx. This is how @harris implemented it in the ddust reference client. But still even with opportunistic client batching I favor using SIGHASH_NONE over always padding with ash.

24

it seems to me like miners can do this at their discretion, i.e. they equally “unpoach” any such inputs that have been poached, or choose to include such inputs with 0 overhead into other transactions that already have ANYONECANPAY effectively removing the full overhead (i.e. locktime version etc, as well as the cost of an empty OP_RETURN), so it seems like this is a potential net increase in efficiency, and i couldn’t think of anything that is made concretely worse by removing this additional restriction

fwiw this isn’t my approach, IIRC it’s how dustbgone was implemented

i don’t think there’s a conflict between your approach and pursuing a policy carveout, the former can have a positive impact right now whereas the latter will take at least a release cycle and can impact the former positively on that longer time frame

not signature aggregation, but yes mempool, specifically my point is about the DoS surface and sub-optimality of relying on transaction replacement policy.

given n dust outputs for which an ANYONECANPAY signature is known, anyone can produce a total of 2^n -1= \sum_{k=1}^n {n \choose k} and for each size k and for each subset of size k there are k! possible orderings, so \sum_{k=1}^n k! {n \choose k} possible transactions with SIGHASH_ALL. with SIGHASH_NONE, the outputs of the transaction is completely unrestricted. let’s ignore ordering ([edit: because it has no effect on payoffs] suppose inputs are always ordered by effective value descending, with lexicographical ordering of outpoint for tie breaking), and the output side (since that isn’t costless, for a given set of dust inputs the feerate of a poaching transaction will always be strictly lower, and miners can always omit or substitute such outputs), this still leaves just 2^k-1 choices.

the problem i see with this is that there is path dependence in this exponential sized space. suppose there are dust outputs a, b, c and one user broadcast \{a, b\} and another attempts to broadcast \{b, c\} or \{a, b, c\}. this may not be possible if output c ’s effective value insufficient for these transactions to be considered valid replacements for the one spending \{a, b\}. an attacker may strategically choose to construct such transactions, and even for small n be able to produce O(2^n) conflicting transactions that it can then broadcast to different mempools, each of which is a local maxima, in order to attempt to impede not just the broadcast of other such transactions, but to cause block propagation delays as well.

while i haven’t worked out the details of how bad this could get, my point is just that if you assume miners will always combine dust input spends into a single bulk dust removal transaction with just one OP_RETURN (or arbitrary outputs of their choice, which if it’s a miner doesn’t matter), then a policy carveout for 1 input transaction and policy restriction on multi input transactions will enforce that only n distinct transactions are ever actually broadcast instead of O(2^n) potential ones. RBF is no longer an issue, as the batch transactions are replaced implicitly. modulu eviction, every peer will spend at most a fixed amount of bandwidth per dust input, as opposed to per potential combination of dust inputs, but the theoretical minimum blockspace required to spend these outputs is still accessible to miners without needing to relax relay policy. if replacement rules were just relaxed and larger and larger combinations of transactions were repeatedly broadcast as new dust outputs are spent, the minimum blockspace transactions be available, but the bandwidth cost would scale exponentially in the worst case.

or put more simply, the DoS surface is substantially reduced if the rule is that dust spends are only relayed as 1 input transactions, even though these can be freely aggregated by anyone. compact block relay could also be extended to take this special case into account.

again i don’t think there is a conflict between client side aggregation in the near term and designing for something like this in the long term, it just seemed notable that a policy carveout could simultaneously reduce DoS risks and remove restrictions on how efficient such batching could get.

25

I double checked and yes you are correct, in dustbgone Peter constructs a tx with NONE|ANYONECANPAY inputs and a single empty OP_RETURN output. So very much like this BIP proposal in those regards.

Thanks for the details, I understand the DoS issue better now and why the policy carveout would help. I certainly hope we eventually see enough dust UTXOs being disposed this way that a policy carveout is needed. My more immediate concern is having a spec wallets can implement that is safe and effective before the problem gets any worse.

1 Like
26

Makes sense! For what it’s worth if this was my project the way i would probably go about this is:

  1. demonstrate interest in fixing this, as you are already doing
  2. if SIGHASH_NONE proves problematic with increased adoption, advocate for very narrow policy careveout just to eliminate the empty vs. 3 vbyte OP_RETURN consideration
  3. very long term, try to integrate my implicit aggregation suggestion into mempool code, since this makes the wallet implementation trivial (always just broadcast 1 input txs), makes it easier for optimal blockspace cost to be achieved and removes the DoS concern of replacement logic. this is very long term because, assuming there’s even any buy in or sufficient demand, it would be a pretty involved change likely to take years to actually land

BTW one last nitpick (and this really is a nitpick) about the proposed BIP text itself, the requirement to not aggregate coins originating from a single wallet seems a bit too strong, since by relying on PR #29415 (-privatebroadcast=1, already mentioned in this thread) a node could arguably reliably simulate aggregation by multiple independent parties (broadcast a tx spending the first input, then reuse the exact same signature in a tx spending another), but in the absence of -privatebroadcast=1 or when Tor daemon is unavailable, an adversary model for dust attacks (which used to be a much bigger problem with the old rebroadcast behavior) where the adversary is monitoring for (re)broadcast of received dust transactions is arguably still a concern for these spending transactions, and disallowing direct submission to 3rd party aggregators seems to be motivated by such leaks.

i think the rationale there could be improved to discuss how privatebroadcast changes the threat model, as well as the issue with spending dust coins with more than one distinct address being contingent on the adversary being able to observe the absence of a prior transaction that only spends from one distinct address. in fact, if a third party aggregator buffers such spends before broadcasting a batch spend, and the adversary then concludes that this suggests that those coins are related similarly to the common input ownership heuristic, this can poison clustering data with counterfactual information, (“cluster collapse”, c.f. MtGoxAndOthers supercluster on wallet explorer for example), which is arguably beneficial for privacy and fungibility.

1 Like
27

Thanks nothingmuch and bubb1es. Lots of interesting details over here. After reading through this new discussion, i agree to SIGHASH_NONE|SIGHASH_ANYONECANPAY suggestion and relaying of every dust input separately in a standalone transaction, and finally the miner performing the aggregation locally.

I think the “single input, single output“ pattern tx is important to prevent introducing another DoS surface of batching at relay level(the current approach) as already described by nothingmuch. This way, relying on standard min fee rate is also not needed. We could preserve relay-level batching while avoiding the 2^n explosion by enforcing an append-only rule - i.e. a batched dust transaction can only be replaced by one that contains all the same inputs plus additional ones, with inputs always in a deterministic order(No removing inputs, no alternative subsets). This would make the replacement space linear i.e. at most n replacements to go from 1 input to n inputs.

But even with this constraint, it still doesn’t beat the cleaner approach of single-input relay + miner aggregation

28

I see how technically with -privatebroadcast=1 a client wallet could simulate a third-party batching their dust while doing it all themselves. And doing this could be a bit more block space efficient and relay efficient. But I’m more concerned that in an environment where dust disposal tx are few and far between an attacker could easily correlate dust UTXOs confirmed and/or broadcast around the same time. For convenience I’d rather see wallets pre-sign dust disposal txs and then broadcast them at random times, and/or when they see some others in the mempool they can batch with.

I’ll try to improve the rationale section of the proposal around this point.

1 Like
29

Note that a miner aggregating this way can always choose to omit inputs that are less lucrative, so the replacement space can’t be enforced linear without some form of consistent broadcast. That said the fact that it’s still O(2^n) is no more of a problem than block contents being an arbitrary choice of the mempool, especially since totally ordering the 1-in-1-out txs is trivial.

From this point of view ANYONECANPAY aggregation can just be modeled as a weight discount on the 1-in-1-out txs. If at least one such transaction is included then it would not be discounted, but penalized with an additional virtual byte for worst case nIns compact size increase (i believe this is the only non-linearity), and then every additional one could be counted as if its weight is just that of its TxIn.

Miners can already do this, so I think the right question to ask is why haven’t they? If i understood the charts @bubb1es shared above suggests in an upper bound of about 4 btc of revenue in the best case. ddust seems like a good way of strengthening this incentive.

You’re right I think that’s the bigger concern

1 Like
30

Since it has not been mentioned, I feel it should be brought up in the “Security Considerations” section that wallets SHOULD NOT enable such a dust disposal function for UTXOs if there are “real” unspent funds on the same address, especially if a) no funds have previously been spent from the address and b) it is an address type with a hashed public key.

Rationale being that even if you don’t want to consolidate your real funds with the dust, disposing of said dust without moving the real funds first would reveal the public key for the address, which would make the real funds vulnerable in a hypothetical future where CRQCs capable of long-exposure attacks against 256-bit ECDLP public keys exist. In such a future, I could see attackers sending dust to wallets specifically to attempt tricking people into disposing of dust in order to reveal their public key, thus enabling such an attack.

3 Likes
31

Good suggestion, I’ll update the proposed draft BIP “Security Considerations”. I’ll also add an issue to update the ddust reference implementation to make this an optional (but default) feature when selecting dust UTXOs to dispose of.

Beyond the quantum concern, spending non-dust UTXOs before the dust is also a good way to make sure large, non-dust UTXOs can never be accidentally signed as NONE|ANYONECANPAY inputs.

2 Likes
32

For those of you following along at home, some big new developments on this project.

  • The bitcoin/bips editors have assigned BIP 451 to our proposed “Dust UTXO Disposal Protocol”
  • @harris and I have updated the reference ddust tool to implement the revised BIP 451 spec. Notable changes include:
    • All disposal transactions now use the same OP_RETURN “ash”output; transactions are slightly larger but have more opportunities to be batched
    • Batching logic accurately follows RBF calculations for bitcoin core 31.0 cluster mempool
    • By default (but optional) dust UTXOs will only be dispose of if there are no non-dust UTXOs using the same address; prevents prematurely revealing the address public key
    • Tested with bitcoin core 31.0 and -privatebroadcast; improves privacy

See all the PRs details.

We’re still looking for feedback on the draft BIP if anyone has any new suggestions.

A big thanks to everyone in this thread, the current spec is vastly better because of your constructive input.

2 Likes
33

Another update, we’ve created a new bip451 GitHub org for the ddust, dusts and any future related repos. Please see or open issues and PRs at these new locations.

We are also making a small adjustment to the license on these repos to be MIT or Apache 2.0, at the users discretion, to ensure easier adoption for anyone who needs an explicit patent grant.

A few next steps on the road to moving BIP-451 from “draft” to “complete” and ultimately “deployed”:

  1. improve test coverage and fix any bugs in the reference ddust client and/or spec
  2. gather more on-chain data about dust attacks to better understand the scope of the issue
  3. work with wallet and wallet lib projects to add BIP-451 support
  4. create a website to educate bitcoin users about BIP-451 and disposing of dust UTXOs
  5. track and report progress on disposing of main chain dust

If you’re a wallet developer please reach out if you’d be interested in adding BIP-451 support to your project. :folded_hands:

2 Likes
34

I’m curious about the section: bips/bip-0451.md at 686c1b0ed7fc550ab567b2ec94f7e3f58b319e58 · bubb1es71/bips · GitHub

From your previous post, you seem to be saying this is principally just about not revealing public keys (i.e. the second reason in the BIP draft):

By default (but optional) dust UTXOs will only be dispose of if there are no non-dust UTXOs using the same address; prevents prematurely revealing the address public key

I don’t quite understand the logic: surely, in practice, it will be extremely common that there remain non-dust utxos at the address being dusted. Thus you’d be recommending people not to move a lot of the dust (even worse (imo) they might interpret it as “hurry up and spend your coins at dusted addresses!” which could be bad for various reasons, not least, creating another heuristic for onchain/metadata observers, possibly).

The “problem” of exposed pubkeys already exists in every single wallet/address/bitcoin usage, you cannot redesign protocols for public key cryptography to avoid revealing public keys. Solving the theoretical quantum threat is orthogonal imo. I personally would remove any reference to that.

(Edit: OK, fair enough, this is a special case of reuse which wouldn’t exist without dusting. I still don’t buy it as a good reason not to de-dust, except perhaps in case of exotic scripts existing “under” a taproot or script-hash address; that seems like a reasonable reason, that you don’t want to expose it if there is no taproot override (external key signing) that could hide the business logic).

But you wrote two cases, and the first of the two didn’t mention hashed pubkeys (I presume you’re referring to taproot, then?); is there another reason I’m not noticing?

35

Perhaps we’re being overly cautious here by trying to avoid revealing the public key of an address that contains non-dust UTXOs. But one of the goals with disposing of dust is to avoid any potential reduction in wallet privacy or security just by disposing of the dust.

We did use the SHOULD language in dust selection part of the spec. since in our reference implementation gives users the option to spend dust that has unspent non-dust UTXOs. But does this cause a user fingerprinting issue? I have to think about that since unlike the quantum stuff it’s a real, non-hypothetical concern.

On the other hand you bring up another real issue that we don’t want to expose unique hidden tap script paths just to dispose of dust.

Overall I agree that we want to make disposing of dust as convenient as possible so it actually gets done. But we need to do our Hippocratic duty of first do no harm. I’d like to hear what you and others think about the relative importance of these potential risks:

  1. revealing public keys when spending dust
  2. fingerprinting the user/wallet by giving them dust selection options
  3. revealing tap script tree scripts when disposing of TR dust
  4. requiring non-dust UTXOs MUST be spent before disposing of dust for the same address

The happy path dust disposal scenario I have in mind is:

  1. dust UTXOs are automatically locked when received (can’t be spent in normal coin selection)
  2. non-dust UTXOs are spent in the normal course of coin selection
  3. dust UTXOs becomes eligible for disposal
  4. wallet creates & signs dust disposal txs when keys are available
  5. at random times the wallet broadcasts (and tries to batch) signed disposal txs

This procedure applies as well to when someone migrates all their non-dust UTXOs to a new wallet keys/descriptor leaving behind the dust UTXOs.