3

When someone would like to make a transaction, their software has to choose which of their UTXOs to spend. Here are a few different ways that one might prioritize which UTXOs get spent.

  • Oldest UTXOs first
  • Newest UTXOs first
  • UTXOs with the smallest amounts first
  • UTXOs with the greatest amounts first
  • The Core Client Selection Algorithm: What is the coin selection algorithm?
  • Others?

What the trade-offs are for the different ways of prioritizing spending of UTXOs? Are some faster? Do some make make the block chain less big (grow less quickly)? Do some make the UTXO set smaller? What about making it so that the user has to pay the least fees? Taking all these factors into consideration, is there a method that is generally accepted to be the best way?

On possibility, which I like, is to spend the most UTXOs possible while still staying in the 1kb minimum fee limit. That way if nodes that prune the blockchain of STXOs (spent transaction outputs), they can prune more and it makes the blockchain smaller for them. Although, this might cause a small amount of bloating for nodes who keep the whole block chain, so it's a tradeoff.

  • Ahh, yes, this is essentially the same question. However, I think some more general discussion on the different algorithms to choose which UTXOs to spend could be a good idea. – morsecoder Oct 27 '14 at 16:21
  • You could edit your question to focus on that aspect. It would be best to try to keep to specific, answerable questions as "general discussion" is not the purpose of this site. – Nate Eldredge Oct 27 '14 at 17:43
7

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

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 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 UTXO 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 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

Good

  • Consolidates dust asap.
  • Constantly keeps number of UTXO at mininum in wallet.

Bad

  • 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

Good

  • Minimal transaction fees.
  • Likely to create non-dust changes.

Bad

  • 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

Good

  • Often small transaction fees
  • Random selection of UTXO seldomly reveals any information about wallet.
  • May consolidate dust UTXO at random.

Bad

  • 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.
  • Thank you for this great, and very thorough answer. There were quite a few things in there I hadn't considered. – morsecoder Nov 12 '14 at 2:27
  • Thanks for this detailed answer. Looks like still legit in 2019, but is there any new "Coin Selection Algorithm" to look around ? – onepix Apr 10 at 15:42
  • Yes, Bitcoin Core started using the Branch and Bound algorithm in 0.17.0: bitcoin.stackexchange.com/a/72928/5406. You can also read a bit more about coin selection in general here: murch.one/wp-content/uploads/2016/11/… – Murch Apr 10 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.