45

When creating a transaction in the standard client, what is the algorithm used to determine which unspent outputs will be used as inputs?

Has this changed since the first version? What different algorithms are used by alternative clients?

Does the client make any attempt to optimize which 'coins' are used based on minimizing the transaction size, the resulting fragmentation, or the 'age' of the coins (value/transactions) used as the source?

Improve this question
1

2 Answers 2

Reset to default
29

I couldn't find the results of the Coin Selection written out anywhere, and just finished piecing it together from the code. It works as David mentioned, but here are more details.

The Coin Selection Algorithm logic to transfer Target amount

  1. If any of your UTXO² matches the Target¹ it will be used.
  2. If the "sum of all your UTXO smaller than the Target" happens to match the Target, they will be used. (This is the case if you sweep a complete wallet.)
  3. If the "sum of all your UTXO smaller than the Target" doesn't surpass the target, the smallest UTXO greater than your Target will be used.

  4. Else Bitcoin Core does 1000 rounds of randomly combining unspent transaction outputs until their sum is greater than or equal to the Target. If it happens to find an exact match, it stops early and uses that.
    Otherwise it finally settles for the minimum of

    • the smallest UTXO greater than the Target
    • the smallest combination of UTXO it discovered in Step 4.

As David mentioned, the subset problem will first restrict to UTXO that have at least one confirmation if sent by yourself, or six confirmations if received from another wallet, then later relaxes these requirements in two further passes if no suitable set of UTXO could be discovered.

Some examples

Alice has four UTXO:
• UTXO_A 0.1BTC
• UTXO_B 0.3BTC
• UTXO_C 0.5BTC
• UTXO_D 1BTC

I will be ignoring transaction fees for simplicity's sake.

Example 1:

Alice wants to send 0.3BTC.
Bitcoin Core discovers that UTXO_B matches the Target, and it only uses UTXO_B as input.

Example 2:

Alice wants to send 0.4BTC.
Bitcoin Core finds that UTXO_C is the smallest UTXO greater than the Target, and that the sum of all UTXO smaller than the target (i.e. UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4) matches the Target here. Both UTXO_A and UTXO_B are used as inputs.

Example 3:

Alice wants to send 0.45BTC.
Bitcoin Core finds that UTXO_C is the smallest UTXO greater than the Target, and that the sum of all UTXO smaller than the target (i.e. UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4) does not surpass the Target. UTXO_C is used as the sole input, being the next smallest input greater than the Target.

Example 4:

Alice wants to send 0.35BTC.
Bitcoin Core finds that UTXO_C is the smallest UTXO greater than the Target, and that the sum of all UTXO smaller than the target (i.e. UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4) does not match the Target. It adds up randomly selected UTXO 1000 times until they surpass the Target, remembering the smallest sufficient combination. The smallest sufficient combination is then compared with the smallest single input greater than the target. Assuming that it does find the best combination here which would be UTXO_A + UTXO_B, it finds that Target < UTXO_A + UTXO_B < UTXO_C and uses UTXO_A and UTXO_B as inputs.

Example 5:

Alice wants to send 0.6BTC.
Bitcoin Core finds that UTXO_D is the smallest UTXO greater than the Target, and that the sum of all UTXO smaller than the target (i.e. UTXO_A + UTXO_B + UTXO_C = 0.1 + 0.3 + 0.5 = 0.9) does not match the Target. It starts trying random combinations as before, and in this situation would probably discover that UTXO_A + UTXO_C = Target. As it finds a combination that matches the Target, it breaks and immediately goes with that combination. UTXO_A and UTXO_C are used as inputs.

¹"Target" is used here for the amount to be spent.
²UTXO = Unspent Transaction Output

Improve this answer
3
  • It seems like the algorithm optimizes for smallest change. Is there any reason why it isn't optimized for lowest transaction fee (fewer inputs resulting in a smaller transaction size)?
    – Michael Enriquez
    Aug 16, 2014 at 23:52
  • 2
    @MichaelEnriquez That's my understanding as well. Apparently, a lot of people aren't happy with this part of Bitcoin Core, but nobody has improved it yet. Most likely, there are also some disagreements what an improvement would constitute.
    – Murch ♦
    Aug 27, 2014 at 16:41
  • As coin selection is an implementation defined behaviour rather than being part of the protocol, few people attempt to improve it.
    – Erkin Alp Güney
    Mar 20, 2021 at 6:28
23

Yes, that is exactly what the client does. It uses heuristics to do this, solving a subset/sum or knapsack problem.

It uses a multi-pass approach, first trying to use only coins with at least six confirmations. In the next two passes it relaxes these requirements. Within each pass, it tries to minimize the number of transaction outputs claimed and then the amount of change returned.

Note that all coins in your wallet are considered. In the accounting model that the Bitcoin client uses, specific coins do not belong to specific accounts.

If you want to check the code yourself, search for SelectCoins in wallet.cpp.

Improve this answer
5
  • 1
    Actually I think it even goes further and tries to use the oldest coins first.
    – David Ammouial
    Sep 15, 2011 at 15:23
  • 6
    no, it does not.
    – Pieter Wuille
    Mar 19, 2012 at 11:56
  • 2
    It also doesn't really try to "minimize the number of transaction outputs claimed". It will use a single output if there's one which is the exact right size, but other than that it doesn't care about the number of outputs and tries to minimize the amount of change.
    – Chris Moore
    Mar 19, 2012 at 16:07
  • David, thanks for the detailed answer. I'm looking through the wallet.cpp now, but was wondering if you could talk a bit about the performance considerations when finding unspent outputs (especially with Berkeley DB). For example I can imagine a naive approach that would essentially be foreach address in account { foreach transaction { foreach output ...if spent?... }}} But some values could be cached/denormalized..are they? Thanks!
    – Brian Armstrong
    Nov 9, 2012 at 5:54
  • why do you need a knapsack algorithm? knapsack is important when you want to not go passed a certain amount, but that's not important here cause you can give change. In particular, the sorting on this line github.com/bitcoin/bitcoin/blame/… seems like a huge over kill
    – relG
    Nov 27, 2017 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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