The challenge for picking a Coin Selection Algorithm is that there are multiple goals to optimize for:
Privacy
The Coin Selection should reveal as little as possible about the user’s wallet contents.
Transaction Fee
One wants to minimize the current transaction fee, but also the overall long-term 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)
Good
- Will use up dust UTXO as they come up in your transaction history.
Bad
- 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 the amount of bitcoins someone is holding by watching when he spends a known output.
- Will not minimize the transaction fee.
Newest UTXOs first (LIFO)
Good
- Reveals less information about your wallet than FIFO.
- Most of your UTXOs see hardly any action at all (potentially good for privacy).
Bad
- Grinds your latest UTXO to dust, until a newer is received or it is used up. Might generate a wallet full of small UTXOs.
- 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
Good
- Consolidates dust asap.
- Continuously keeps number of UTXO at minimum in wallet.
Bad
- Reveals lower bound of UTXO value in wallet.
- Large input lists (especially as long as dust exists in wallet) cause 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
Good
- Minimal transaction fees.
- Likely to create non-dust changes.
Bad
- Reveals upper bound of UTXO value in wallet.
- Never consolidates dust.
- Usually increases number of UTXO in network.
The Knapsack Selection Algorithm used by Bitcoin Core
Good
- Often small transaction fees
- Random selection of UTXOs seldomly reveals any information about the wallet.
- May consolidate dust UTXOs at random.
Bad
- Always aims for 10 mBTC change outputs.
- With a lot of small UTXOs in your wallet, likely to cause big transaction fees.
(2014:) 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 UTXOs associated with the same address as well: less linking of transactions improves privacy, potentially consolidates UTXOs 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 useful amounts, this would create new UTXOs of useful 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.
- Select UTXO set to minimize transaction fee, instead of minimizing change output.
Update in 2021:
- Removed a few allusions to Coin Age Priority as transaction selection policy in block building which was removed in Bitcoin Core 0.12.0 in 2016.
- Removed erroneous claim that spending multiple inputs from the same address is cheaper
Note that Bitcoin Core used the Knapsack solver as its only algorithm until 2017, but since then has added an improved algorithm proposed by the author of this answer.