Does any wallet software use the heuristic of adding a dust UTXO in each TX?

[Shymaa-Arafat]

The question of why do we calculate the dust limit as for a complete transaction not just one input, was not originally mine
However, it triggered an idea on my mind of a coin selection strategy following the heuristic of one large & one small ( can't recall the corresponding abstract algorithmic heuristic now)
If u want to spend X, select UTXOS A&a such that:
 a is dust
(A+a - X) is not dust

The point is if we want to mitigate the dust problem while performing coin selection at the same time, then I don't see the problem as a SUBSET SUM anymore; we do not want the almost exact match (it will create dust), we want an over-sized fit so that the change is not dust.

Does any wallet already does that?
Whether there's or there's not, what do u think about such a strategy

[hosseinimr93]

First of all, note that you should consider the transaction fee too.
So, your proposal should be:
Select UTXOs A & a in way so that, A + a - X - f is not a dust, where f is transaction fee.

Secondly note that if A + a - X - f is a dust, the transaction cannot be broadcast at all.

I don't know any wallet do this. Electrum (as the best SPV wallet I know) adds the dust change to the transaction fee.

In electrum and some other wallets, you can use coin control feature and select the UTXOs as you want.

[nc50lc]

-snip-
Does any wallet already does that?
Whether there's or there's not, what do u think about such a strategy

Good as long as the output isn't the one that'll be changed when the change is dust unless the user specified/agreed (eg. via checkbox).
Most users will find sudden change in output amount, however small it is, a bad feature.
It's best to just add the dust to the transaction fee if it reached the "dust threshold", preset or set by the user.
With that, you should have an advanced option to set the maximum amount to be considered as dust based from the users' preference.

As hosseinimir mentioned, Electrum have a similar feature but it's only when the change is lower than the "standard" output amount which is currently 547 satoshi.
My suggestion is to implement a similar feature but the "amount" is dust or the range set be the user.

[Shymaa-Arafat]

First of all, note that you should consider the transaction fee too.
So, your proposal should be:
Select UTXOs A & a in way so that, A + a - X - f is not a dust, where f is transaction fee.

No problem with that, I referred to X as all whatever the user is going to pay

Secondly note that if A + a - X - f is a dust, the transaction cannot be broadcast at all.

What do you mean Sir here?!
-I'm talking about a coin selection algorithm that implicitly mitigates the dust problem, if the difference is dust the algorithm will not choose those A&a in the first place.
-Ofcourse the algorithm naturally chooses from the available UTXOS; for example if a user has only one UTXO then let it be, if the user wants to choose the UTXOS by himself then the algorithm (software) will just notify him/her of an existing better deal of using his dust at a cost of 1 input only or saving his change from being dust.
-If, I mean for example, Bitcoin core ever applied it I really don't know if they let their user choose.

Good as long as the output isn't the one that'll be changed when the change is dust unless the user specified/agreed (eg. via checkbox).
Most users will find sudden change in output amount, however small it is, a bad feature.

Again your words are not clear to me Sir, I'm talking about/suggesting a coin selection method that uses the existing dust with min cost & tries to avoid creating new dust.
What is the bad feature?or the sudden change in the output amount?
I did not suggest anything that leads to sudden change in the value of the output users usually call "change"
.
.
.
I really don't understand from where came the misunderstanding?
 or why?
I'm answering & explaining every detail for the sake of the record ( the group record of the post with its comments)

[o_e_l_e_o]

As I understand, you are proposing a system that whenever you make a bitcoin transaction which will create some amount of non-dust change, the wallet automatically includes any dust inputs you have in your wallet to consolidate them in to your non-dust change and make them useful again.

There are two main issues with this.

1 - Fees. Depending on how full the mempool is and how much you decide to pay in fees, you might end up spending more to include the dust input than the dust input is actually worth. You may end up losing money by consolidating it.
2 - Privacy. I absolutely would not want a wallet which included unnecessary inputs in to my transaction without me telling it to. This would result in change addresses from previous transactions being linked to new transactions you are making, and greatly compromising your privacy.

[hosseinimr93]

As I understand, you are proposing a system that whenever you make a bitcoin transaction which will create some amount of non-dust change, the wallet automatically includes any dust inputs you have in your wallet to consolidate them in to your non-dust change and make them useful again.

My understanding from OP's proposal:

Let's say you have three UTXOs.

UTXO A: 0.0010 BTC
UTXO B: 0.0011 BTC
UTXO C: 0.0012 BTC

If you want to send 0.001196 BTC (the fee is included), your wallet will probably use the UTXO C. This will cause your transaction to have a dust change.
OP is proposing an algorithm in which the wallet uses UTXOs A and B instead of UTXO C.

[Shymaa-Arafat]

2 - Privacy. I absolutely would not want a wallet which included unnecessary inputs in to my transaction without me telling it to. This would result in change addresses from previous transactions being linked to new transactions you are making, and greatly compromising your privacy.

Isn't Bitcoin Core and some wallets already have a coin selection strategy?
The idea of a wallet choosing which UTXOS is there from the beginning, maybe it's optional in some wallets but it exists, or am I missing something here?

As I understand, you are proposing a system that whenever you make a bitcoin transaction which will create some amount of non-dust change, the wallet automatically includes any dust inputs you have in your wallet to consolidate them in to your non-dust change and make them useful again.

It's not whenever u have a "non dust" change, it's the selection method to avoid generating "dust" change and use ur previously generated dust at the same time
Instead of choosing the closest match like Bitcoin Core Branch& Bound selection algorithm does, this algorithm will favor larger UTXOS that do not generate dust change & try to use ur old dust at the same time.

you might end up spending more to include the dust input than the dust input is actually worth. You may end up losing money by consolidating it.

As I said u add the extra fee for only 1 more UTXO input not a complete TX, and the algorithm will not do it if it costs the user
In this case the algorithm will only make sure the new change is not dust by choosing a larger UTXO
The whole idea is to accumulate the old dust to ur new change with minimal cost

[o_e_l_e_o]

Isn't Bitcoin Core and some wallets already have a coin selection strategy?

Yes, plenty of wallets will automatically select inputs, and plenty of wallets do so in a way which compromises the user's privacy. All I'm saying is that I wouldn't want to use such a wallet or feature.

this algorithm will favor larger UTXOS that do not generate dust change & try to use ur old dust at the same time.

Yes, this is exactly what I'm saying. It would automatically include any dust inputs in to a transaction you are making so they are consolidated in to useful change at the same time. This is bad for privacy unless you are very carefully selecting which inputs to use.

As I said u add the extra fee for only 1 more UTXO input not a complete TX, and the algorithm will not do it if it costs the user.

A P2PKH input is still ~148 vbytes. Given that a dust input could be as low as 546 sats, then even a fee as low as 4 sats/vbyte might cost you more than the value of your input.

The whole idea is to accumulate the old dust to ur new change with minimal cost

If you don't care about privacy, then the best solution is simply to consolidate all the dust in your wallet at once whenever you make a 1 sat/vbyte transaction. If you do care about privacy, then you should try to avoid creating dust in the first place, and if you do, then be very selective about which other inputs you consolidate it with.

[Shymaa-Arafat]

Let's say you have three UTXOs.

UTXO A: 0.0010 BTC
UTXO B: 0.0011 BTC
UTXO C: 0.0012 BTC

If you want to send 0.001196 BTC (the fee is included), your wallet will probably use the UTXO C. This will cause your transaction to have a dust change.
OP is proposing an algorithm in which the wallet uses UTXOs A and B instead of UTXO C.

Yes, that's part of the idea; the other part if u have
UTXO A: 0.0010 BTC
UTXO B: 0.0011 BTC
UTXO C: 0.0012 BTC
UTXO D: 0.0013 BTC
My algorithm will choose D as it does not create dust change would be 0.000104)
.
If they're
UTXO A: 0.0010 BTC
UTXO B: 0.0011 BTC
UTXO C: 0.0012 BTC
UTXO D: 0.0013 BTC
UTXO E: 0.000005 BTC
I will choose D&E to accumulate E to the change 0.000109 BTC)
.
However, if user have only one more dust UTXO say D:

UTXO A: 0.0010 BTC
UTXO B: 0.0011 BTC
UTXO C: 0.0012 BTC
UTXO D: 0.000005
I may choose C&D as the change 0.000009 is not dust, but now I think in these tight cases the algorithm must calculate the cost accurately and add the dust only if it's profitable
 ( indeed yes one UTXO  above the dust limit is better than 2 below it, but not at extra cost since 0.000009 could be dust in some higher fee hours)
.
Ps.
Why r u referring to me by "OP"?

[Shymaa-Arafat]

I should add that I'm not just thinking of the user best interest here, I'm also thinking of the burden of dust UTXOS to the whole UTXOS set

[nc50lc]

Good as long as the output isn't the one that'll be changed when the change is dust unless the user specified/agreed (eg. via checkbox).
Most users will find sudden change in output amount, however small it is, a bad feature.

I really don't understand from where came the misunderstanding?

I thought adjusting the output is part of it when you said "over-sized fit" and "(not) almost exact match" in the second paragraph.
Anyhow, the later replies further cleared what you are speaking about.

By the way, do you think my proposal of adding the dust change to the fee has better results in terms of UTXO set clutter, transaction size and possibly for privacy?
In respective order:

• if fewer txns produce change, there'll be less UTXO to save in the blockchain;
• less inputs will make smaller txns thus smaller fee;
• having one output might mislead blockchain analytics that it's "self-transfer" and having less change outputs in the wallet means less UTXO that may lead to privacy issue when used together.

I'm not going to discuss this heavily since it's not the topic here, just a suggestion for an alternative.

[Shymaa-Arafat]

By the way, do you think my proposal of adding the dust change to the fee has better results in terms of UTXO set clutter, transaction size and possibly for privacy?

I think from previous replies that what u r suggesting (of adding the change to the fee if it's dust) is already an implemented option in the Electrum wallet, and it goes along with the Bitcoin Core selection strategy of using the closest match ( no problem if the remainder is dust). This is like when u leave a small remaining change as a tip in fiat currency real life transactions.

However, I think this doesn't deal with existing dust or solve the problem completely. Although I don't know the exact current dust UTXOS ratio, I know it has been significantly reduced since 2019/2020 days; but I also kind of know it still exists because of all the dust sweeping/donation projects in the GitHub

[Pmalek]

UTXO A: 0.0010 BTC
UTXO B: 0.0011 BTC
UTXO C: 0.0012 BTC

If you want to send 0.001196 BTC (the fee is included), your wallet will probably use the UTXO C. This will cause your transaction to have a dust change.
OP is proposing an algorithm in which the wallet uses UTXOs A and B instead of UTXO C.

That's where coin control features come in. If you don't want the change to be below the dust limit, use other inputs manually and learn how to do it. I wouldn't want to use a wallet that selects two or more inputs in order to avoid dust change, creating a bigger transaction with more fees, instead of just one input. But I do want to have the option to do that if that pleases me and coin control allows exactly that. 

[o_e_l_e_o]

By the way, do you think my proposal of adding the dust change to the fee has better results in terms of UTXO set clutter, transaction size and possibly for privacy?

This is what I do. If I cannot create a reasonable amount of change by selecting appropriate inputs, then I don't want to create a dust output. I'm going to lose a significant amount of the value of it anyway when I try to spend or consolidate it, and it will almost certainly compromise my privacy in the process. In the past I've either bought an extra item from the merchant or added something else to my basket to spend the dust, added it on to the payment as a tip or donation, added it to the fee, or redirected it to a donation address of a charity or organization I support.

I wouldn't want to use a wallet that selects two or more inputs in order to avoid dust change, creating a bigger transaction with more fees, instead of just one input.

Particularly since the wallet does not know what fee you will end up selecting for such a transaction, or even if you might bump the transaction fee in the future. I might end up wanting to send a transaction with very high priority for whatever reason, selecting a high fee, and then my wallet starts throwing in unnecessary inputs and costing me a lot of money.

[Shymaa-Arafat]

I guess the case everyone agrees on is

UTXO A: 0.0010 BTC
UTXO B: 0.0011 BTC
UTXO C: 0.0012 BTC
UTXO D: 0.0013 BTC
My algorithm will choose D as it does not create dust change would be 0.000104)

.
If u plan to add ur dust change to the fee fine no problem with that, but when u still have dust UTXOS they constitute an overhead to the UTXO set
I don't know their exact ratio now, but previous studies in  2018-2020 estimated them to be 10-15% of UTXOS (at that time the UTXO set was 60 m, ie 6-9m)

Do u imagine every full node is storing & book-keeping unnecessary 6-9m UTXOs along with their hashes?
A Stateless node using proofs/ witnesses is on average getting an extra hash in every proof for that.
I think this may have an effect on every regular user, even if implicit.

[goatpig]

Not sure this fits the discussion. If change for a tx would come out as dust, Armory will burn that amount as fee instead.

[Shymaa-Arafat]

Not sure this fits the discussion. If change for a tx would come out as dust, Armory will burn that amount as fee instead.

Others say this happens in Electrum wallet too, but if this is already happening & dust ~0.16$, and was even less when Bitcoin was less than 30,000$, where did the dust problem came from?
why there's ever dust ?

[o_e_l_e_o]

why there's ever dust ?

Even if using one of the wallets discussed here, a user can choose not to burn their dust and receive it as change. There are also plenty of wallets which don't do this, and return the dust as change normally. There are also spammers which perform "dust attacks", sending out hundreds of thousands of dust outputs to try to deanonymize addresses when they are later consolidated.

One of my favorite ideas regarding dust, which unfortunately is not active, was Peter Todd's Dust-B-Gone. Everyone would sign a transaction spending all their dust, using SIGHASH_NONE and SIGHASH_ANYONECANPAY, and then send that transaction to Todd's server. Once he had a lot of transactions from a lot of different users, he would combine them all in to a single transaction which spent all the dust as fee and broadcast it. This effectively turned everyone's dust in to extra miner reward, while maintaining privacy and not linking two or more dust outputs together.

[goatpig]

Others say this happens in Electrum wallet too, but if this is already happening & dust ~0.16$, and was even less when Bitcoin was less than 30,000$, where did the dust problem came from?
why there's ever dust ?

Dust in Armory is defined as a change amount that is less than the transaction's fee. At the time of signing this tx, it is unlikely the change can be spent on its own. The privacy implication and why it is preferable to burn the dust rather than to keep it is that it will most likely lead to damaged privacy in a later transaction, that will combine the dust output with another UTXO. Note that in this assessment, only the fee amount in satoshi is relevant, not the fiat value.

The economics of fees in satoshi vs fiat is hard to predict. In the long term, fees in $$$ tend to stabilize around certain price points (instead of growing unbounded). Fees in satoshi are affected by network load rather than price (the two do tend to come together however), regardless of price point, and will cycle up and down. There is therefor a buffer of UTXOs that is within the reach of the dust threshold, in perpetuity.

To predict what will be in and out of that buffer in the future is about as hard as predicting the market. Armory errs on the side of caution and burns dust by default (you can disable this), while it tries to avoid UTXO consolidation. This is because I expect a user's privacy is worth more to him than a few cents/dollars, even if he might not think so at the moment.

For what it's worth, there is a dust "propagation rule" in Core. There is a minimum amount of satoshis per output Core will tolerate (something like 350, don't quote me on this). A transaction with outputs that have less than this limit will be valid but won't be propagated by default Core nodes (i.e. it is likely you'd have to mine it yourself).

[ranochigo]

As hosseinimir mentioned, Electrum have a similar feature but it's only when the change is lower than the "standard" output amount which is currently 547 satoshi.
My suggestion is to implement a similar feature but the "amount" is dust or the range set be the user.

The actual standardness limits actually puts the threshold native segwit transaction at 294 satoshis, not 546 satoshis. Electrum includes <546sat output as fees because they didn't want to change the threshold, which is understandable because more often than not, it costs more to spend it. However, it is still important to note that just because Electrum always doesn't include change <546 satoshis, it doesn't mean that it is done because it violates the standardness rules.

I don't know their exact ratio now, but previous studies in  2018-2020 estimated them to be 10-15% of UTXOS (at that time the UTXO set was 60 m, ie 6-9m)

Do u imagine every full node is storing & book-keeping unnecessary 6-9m UTXOs along with their hashes?
A Stateless node using proofs/ witnesses is on average getting an extra hash in every proof for that.
I think this may have an effect on every regular user, even if implicit.

You can never eliminate dust, that is a fact. You cannot prune them because it makes no sense. Including better coin control will help but it would be marginally more useful at the expense of more privacy leakage from the user. Whether this is an area for improvement is a whole other issue.

Others say this happens in Electrum wallet too, but if this is already happening & dust ~0.16$, and was even less when Bitcoin was less than 30,000$, where did the dust problem came from?
why there's ever dust ?

Dust isn't that common actually. If you have a dust output, then more often than not, the transaction was once non-standard and miners had to manually include it. You're probably defining it in terms of either costing more to spend it than the actual value or just low value inputs. More often than not, wallets will eventually spend them but it is not always the case. Dust will always exist, while there are proposals for Electrum to start including those smaller and insignificant inputs, I highly doubt it would be widely implemented because the dusting attack will often link many addresses together.