The challenge for picking a Coin Selection Algorithm is that there are multiple goals to optimize for:
The Coin Selection should reveal as little as possible about the user's wallet contents.
One wants to minimize the current transaction fee, but also the overall longterm transaction fees.
Non-dust change creation
It would be preferable to create non-dust change.
Reduction of Dust UTXO
Dust UTXO have to be stored on all users' devices and therefore create data volume even on thin clients. It should be a priority to reduce their number.
Unfortunately, these are contradictory to one another, and therefore every solution must find an appropriate balance for itself.
Oldest UTXOs first (FIFO)
- Will use up dust UTXO as they come up in your transaction history.
- Gives a date for the oldest UTXO the sender has in his Wallet. E.g. reveals how long a user at least has been using Bitcoin (with that wallet), might even be used to guess amount of bitcoins someone is holding by watching when he spends a known output.
- Will not minimize the transaction fee.
Newest UTXOs first (LIFO)
- Reveals less information about your wallet than FIFO.
- Most of your UTXO see hardly any action at all (potentially good for privacy).
- Grinds your latest UTXO to dust, until a newer is received or it is used up. Might generate a wallet full of small UTXO.
- Very new UTXO are more expensive to spend.
- At equal or more income than spending, dust will never be consolidated.
- Will not minimize transaction fee.
- Will link your recent activities by always reusing the newest change output.
UTXOs with the smallest amounts first
- Consolidates dust asap.
- Constantly keeps number of UTXO at mininum in wallet.
- Reveals lower bound of UTXO value in wallet.
- Large input lists (especially as long as dust exists in wallet): Huge fees and slow confirmation.
- Links lots of addresses in your wallet together.
- Can be exploited to increase your transaction fee, if people just send you low-value outputs.
UTXOs with the greatest amounts first
- Minimal transaction fees.
- Likely to create non-dust changes.
- Reveals upper bound of UTXO value in wallet.
- Never consolidates dust.
- Except for specific circumstances constantly increases number of UTXO in network.
The Core Client Selection Algorithm
- Often small transaction fees
- Random selection of UTXO seldomly reveals any information about wallet.
- May consolidate dust UTXO at random.
- Minimizes change outputs.
- With a lot of small UTXO in your wallet, likely to cause big transaction fees.
I have been looking into coming up with a better Coin Selection Algorithm, but haven't found one yet that significantly improves on the Core Client Selection Algorithm.
Here are some ideas to improve it:
- When a UTXO is randomly selected, add all other UTXO associated with the same address as well: Takes less space in transaction than adding UTXO from different addresses, no decrease in privacy, potentially consolidates UTXO into fewer.
- Instead of selecting the smallest change, one could aim to create a change of the same size as the spending target. Assuming that people mostly send decent amounts, this would create new UTXO of decent value instead of the smallest possible changes as it currently does. It also makes it harder to guess what was the change and what was the payment.
- After randomly selecting UTXO to spend, "fill up the transaction" with dust UTXO, unless they increase the necessary transaction fee. This would help consolidate the UTXO pool, potentially links more of your addresses together though.
- Select UTXO set to minimize transaction fee, instead of minimizing change output.