6

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
15

Goals of Coin Selection

The challenge for picking a Coin Selection algorithm is that there are multiple goals to optimize for:

Privacy

A wallet's default behavior should be reasonable conducive to the users' financial privacy. The Coin Selection should reveal as little as possible about the wallet contents. Wallets should avoid linking too many addresses, not reveal excessive funds when unnecessary, minimize discernible patterns and fingerprints, but also maintain sufficient UTXOs to spread the balance out. Wallets should never reuse addresses.

Transaction Fee

The Coin Selection must aim to curtail the transaction fee for current transactions, but also minimize the total transaction fees in the long term. Since every UTXO must be spent eventually, it may be sometimes opportune to spend more UTXOs at a low feerate now, than at a high feerate later.

UTXO pool shaping

Dust should always be avoided, but generally small UTXOs will have a large relative cost at elevated feerates, so we should aim to avoid creating tiny change outputs. As a rule of thumb, wallets should not create UTXOs that cost a significant chunk of their value at moderate feerates. Aim for change to be at least 20–50k sats (less for smaller, more for larger input scripts).

Curtail UTXO set size

All UTXOs have to be stored on every full node, and all UTXOs have to be spent eventually. A wallet should keep sufficient UTXOs to maintain financial privacy, but as few as possible to minimize future blockchain data, fees, and the on-going storage cost on every full node.

Unfortunately, some of these goals are antagonal, and therefore every solution must find an appropriate balance for its priorities.

Common algorithms

Let's go over some of the most common algorithms for coin selection, as well as their advantages and disadvantages. We'll look at:

  • Oldest first (FIFO)
  • Newest first (LIFO)
  • Smallest first
  • Largest first
  • Random
  • Knapsack (used by Bitcoin Core)
  • Branch and Bound (used by Bitcoin Core)
  • Multi-algorithm (used by Bitcoin Core)

Oldest first (FIFO)

Pick UTXOs in order of descending confirmation count.

Good

  • Will consolidate small UTXOs eventually as they come up
  • Input sets are representative of your UTXO pool's composition, neither particularly small or large
  • Will transition wallet's UTXO pool to the new output format when a new output type is adopted for receiving

Bad

  • Gives a date for the oldest UTXO in the wallet, which e.g. reveals how long a user at least has been using this wallet
  • The values and confirmation count spacing of UTXOs may be used to estimate total wallet balance
  • The timestamp ranges on different transactions may form a serial pattern allowing to associate different transactions of the same wallet and to disambiguate it from other wallets using the same software (since time stamp ranges should never overlap except in last or first confirmation height)
  • Might be used to infer information about a wallet by watching when a known output is spent
  • Will not minimize the transaction fee

Newest first (LIFO)

Pick UTXOs with lowest confirmation count first.

Good

  • Most UTXOs have a small transaction graph, which may be beneficial for privacy
  • Spent UTXOs are closest in acquisition value to value at spending time resulting in smallest effective gain/loss

Bad

  • Hardly any consolidation at all if wallet's funds are increasing over time
  • Grinds latest UTXO down, until a newer is received or it is used up. May result in the wallet's UTXO pool having lots of small UTXOs.
  • Will combine the extensive transaction graphs of multiple youngest UTXOs when a larger amount is sent
  • Will link up all your recent activity by always reusing the newest change output
  • Will not minimize transaction fee

Smallest first

Pick UTXOs in order of ascending value.

Good

  • Consolidates small UTXOs ASAP, curbing the wallet's UTXO pool and minimizing future spending cost

Bad

  • Reveals lower bound for current UTXO values in wallet
  • Maximizes input sets which increases transaction fees for current transaction
  • Tends to overconsolidate the UXTO pool, reducing financial privacy
  • Links lots of addresses
  • Decreases value range of wallet's UTXO pool

Largest first

Pick UTXOs in order of descending value.

Good

  • Minimal transaction fees for current transaction
  • Links few addresses
  • Likely to create sizeable change outputs

Bad

  • Reveals upper bound for UTXO value in wallet
  • May reveal that wallet holds vastly more funds than necessary to make the current payment
  • Links consecutive transactions while change output is still the largest UTXO
  • Defers consolidation of small UTXOs, maximizing future cost
  • Bloats wallet's UTXO pool (and the global UTXO set) as single recipient spends are usually ±0 on UTXO pool count (minus one input, plus one change output), but incoming transactions increase the UTXO pool

Random

Draft UTXOs with equal chance randomly from all available.

Good

  • Selected UTXOs have no consistent fingerprints like age or value
  • Input sets are probabilistically representative of wallet's UTXO pool composition, becoming more consolidatory when more small UTXOs are present
  • Easy to implement
  • Random change output amounts increase value diversity

Bad

  • Does not minimize fees
  • May exhibit some fingerprints randomly such as revealing much greater funds in the wallet than necessary for payment

Knapsack (used by Bitcoin Core)

This algorithm (which incidentally does not solve a Knapsack problem) approaches Coin Selection by sorting all UTXOs by value and running 1000 iterations of selections randomly picking UTXOs with a 50% chance from largest to smallest. Whenever it overshoots the target, it deselects the last included UTXO and continues with smaller UTXOs. The algorithm is described exhaustively in in What is the coin selection algorithm?.

Good

  • Produces small UTXO pool
  • Pseudorandom selection of UTXOs reveals little information about the wallet

Bad

  • Aggressively consolidates tiny UTXOs including uneconomical outputs
  • Always aims for 10 mBTC change outputs (fingerprint and unnecessarily large)
  • With a lot of small UTXOs in your wallet, likely to cause big transaction fees
  • Unnecessarily expensive computation

Branch and Bound (used by Bitcoin Core since v0.17)

Deterministically search the UTXO pool's combination space for the least wasteful change-avoidant input set. Since there not always is a changeless input set, Bitcoin Core falls back to using the above described "Knapsack" approach in that case.

Good

  • Creates no change output which reduces current fees, future fees, cuts transaction graph for wallet, and has consolidatory effect on wallet's UTXO pool
  • Uses minimal input set among viable candidates reducing address linkage and fees
  • Selected UTXOs have no consistent fingerprints like age or value
  • Uses more inputs at lower feerates and fewer inputs at higher feerates due to waste metric
  • Prefers spending less blockspace efficient output types at lower feerates and more efficient output types at higher feerates due to waste metric

Bad

  • Does not always produce a solution
  • Sender cannot CPFP since there is no change output
  • More complicated to implement and expensive to compute

Multi-algorithm (to be used by Bitcoin Core v23+)

The next release after Bitcoin Core 22.0 will run Knapsack, Single Random Draw, and Branch and Bound coin selection in parallel and then choose among the three resulting input set candidates the one that scores best according to the waste heuristic, which was previously already used to pick the best Branch and Bound solution.

Good

  • Spends more inputs at low feerates, fewer at high feerates reducing total fees
  • Consolidates small inputs when economically sensible
  • Since input sets are sourced from multiple approaches, patterns are more difficult to identify
  • Often avoids change, improving privacy, fees and reducing linkage

Bad

  • Complicated to implement and test
  • Computationally intensive to compute
  • Still uses a fairly high minimum change of 10 mBTC (when change is produced)

Update in Nov 2021:

  • Remove ambiguous use of term "dust"
  • Complete rewrite to update to my current understanding
  • Add Random Selection, Branch and Bound, and Bitcoin Core's multi-algorithm approach

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.

Update in 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.
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.