5

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.

0
11

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.

3
  • 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 '19 at 15:42
  • 1
    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 '19 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.