<p>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 <a href="https://bitcoin.stackexchange.com/a/1078/5406">David mentioned</a>, but here are more details.</p>

<h2>The <a href="https://github.com/bitcoin/bitcoin/blob/3015e0bca6bc2cb8beb747873fdf7b80e74d679f/src/wallet.cpp#L1276" rel="noreferrer">Coin Selection Algorithm</a> logic to transfer <em>Target</em> amount</h2>

<ol>
<li>If any of your <a href="https://bitcoin.stackexchange.com/tags/utxo/info">UTXO</a>² matches the Target¹ it will be used.</li>
<li>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.)</li>
<li>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.</li>
<li><p>Else Bitcoin Core <a href="https://github.com/bitcoin/bitcoin/blob/3015e0bca6bc2cb8beb747873fdf7b80e74d679f/src/wallet.cpp#L1129" rel="noreferrer">does 1000 rounds of randomly combining unspent transaction outputs</a> 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.<br>
Otherwise it finally settles for the minimum of </p>

<ul>
<li>the smallest UTXO greater than the Target</li>
<li>the smallest combination of UTXO it discovered in Step 4.</li>
</ul></li>
</ol>

<p>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.</p>

<hr>

<h2>Some examples</h2>

<p>Alice has four UTXO:<br>
• UTXO_A 0.1BTC<br>
• UTXO_B 0.3BTC<br>
• UTXO_C 0.5BTC<br>
• UTXO_D 1BTC</p>

<p><em>I will be ignoring transaction fees for simplicity's sake.</em></p>

<h2>Example 1:</h2>

<p>Alice wants to send <strong>0.3BTC</strong>.<br>
<em>Bitcoin Core discovers that UTXO_B matches the Target, and it only uses UTXO_B as input.</em></p>

<h2>Example 2:</h2>

<p>Alice wants to send <strong>0.4BTC</strong>.<br>
<em>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. <code>UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4</code>) matches the Target here. Both UTXO_A and UTXO_B are used as inputs.</em></p>

<h2>Example 3:</h2>

<p>Alice wants to send <strong>0.45BTC</strong>.<br>
<em>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. <code>UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4</code>) does not surpass the Target. UTXO_C is used as the sole input, being the next smallest input greater than the Target.</em></p>

<h2>Example 4:</h2>

<p>Alice wants to send <strong>0.35BTC</strong>.<br>
<em>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. <code>UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4</code>) 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 <code>UTXO_A + UTXO_B</code>, it finds that <code>Target &lt; UTXO_A + UTXO_B &lt; UTXO_C</code> and uses UTXO_A and UTXO_B as inputs.</em></p>

<h2>Example 5:</h2>

<p>Alice wants to send <strong>0.6BTC</strong>.<br>
<em>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. <code>UTXO_A + UTXO_B + UTXO_C = 0.1 + 0.3 + 0.5 = 0.9</code>) does not match the Target. It starts trying random combinations as before, and in this situation would probably discover that <code>UTXO_A + UTXO_C = Target</code>. 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.</em></p>

<hr>

<p>¹<sub>"Target" is used here for the amount to be spent.</sub><br>
²<sub>UTXO = Unspent Transaction Output</sub></p>

CC BY-SA 3.0
2014-08-16T23:52:28.373Z
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
CC BY-SA 3.0
2014-08-27T16:41:03.157Z
@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
CC BY-SA 4.0
2021-03-20T06:28:31.040Z
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
CC BY-SA 4.0
2014-08-10T01:23:55.543Z
2019-09-09T03:11:41.433Z
2019-09-09T03:11:41.433Z
Murch
<p>Yes, that is exactly what the client does. It uses heuristics to do this, solving a subset/sum or knapsack problem.</p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-11-09T05:54:45.423Z
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
CC BY-SA 3.0
2017-11-27T20:42:42.717Z
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  https://github.com/bitcoin/bitcoin/blame/3c098a8aa0780009c11b66b1a5d488a928629ebf/src/wallet/wallet.cpp#L2459 seems  like a huge over kill
relG
CC BY-SA 3.0
2011-09-15T15:23:53.597Z
Actually I think it even goes further and tries to use the oldest coins first.
David Ammouial
CC BY-SA 3.0
2012-03-19T11:56:19.167Z
no, it does not.
Pieter Wuille
CC BY-SA 3.0
2012-03-19T16:07:26.437Z
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
CC BY-SA 3.0
2011-09-15T08:06:14.010Z
2011-09-15T08:06:14.010Z
David Schwartz
<p>When creating a transaction in the standard client, what is the algorithm used to determine which unspent outputs will be used as inputs?</p>

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

<p>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?</p>

CC BY-SA 3.0
2012-09-30T19:58:47.203Z
Here's more info: http://en.bitcoin.it/wiki/User:Gmaxwell/coin_selection
Stephen Gornick
<transactions><wallet><client><fragmentation><coin-selection>
What is the coin selection algorithm?
Andrew Jones
# What is the coin selection algorithm?

(Asked by: username_0 on 2011-09-15)

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?

**Tags:** transactions, wallet, client, fragmentation, coin-selection

> **Comments:**
> **username_1**: Here's more info: http://en.bitcoin.it/wiki/User:Gmaxwell/coin_selection  

---

## 2 answers

### Answer by username_2 on 2014-08-10. Score: 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 [username_5 mentioned](https://bitcoin.stackexchange.com/a/1078/5406), but here are more details.

## The [Coin Selection Algorithm](https://github.com/bitcoin/bitcoin/blob/3015e0bca6bc2cb8beb747873fdf7b80e74d679f/src/wallet.cpp#L1276) logic to transfer *Target* amount

1. If any of your [UTXO](https://bitcoin.stackexchange.com/tags/utxo/info)² 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](https://github.com/bitcoin/bitcoin/blob/3015e0bca6bc2cb8beb747873fdf7b80e74d679f/src/wallet.cpp#L1129) 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 username_5 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

> **Comments:**
> **username_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)?  
> **username_2**: @username_3 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.  
> **username_4**: As coin selection is an implementation defined behaviour rather than being part of the protocol, few people attempt to improve it.  

---

### Answer by username_5 on 2011-09-15. Score: 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`.

> **Comments:**
> **username_8**: Actually I think it even goes further and tries to use the oldest coins first.  
> **username_9**: no, it does not.  
> **username_10**: 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.  
> **username_6**: username_5, 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!  
> **username_7**: 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  https://github.com/bitcoin/bitcoin/blame/3c098a8aa0780009c11b66b1a5d488a928629ebf/src/wallet/wallet.cpp#L2459 seems  like a huge over kill  

---

