<p>The coin selection algorithm present in Bitcoin Core 0.19 tries to either find a solution where there is no change output, or a solution where the change is as close to 0.01 BTC as possible without going under that amount, ignoring fees.</p>
<p>There are two major components in 0.19's coin selection that we need to consider when analyzing this issue. The first is how it determined fees, and the second how it actually chooses the inputs. (There is a third part with finding a changeless solution, but because your transaction has change, this does not matter).</p>
<p>The fees were determined iteratively. It would choose inputs, calculate the fees for a transaction with those inputs, and if it did not happen to have enough value, it would increase the amount to select by that fee value and try selecting again.</p>
<p>For the actual selection part it would first pick out all of the inputs whose value is less than the target, and find the lowest larger input - the lowest valued input whose value is larger than the target. If the lowest larger input does not exactly match the target, it will then do a stochastic approximation.</p>
<p>This approximation will iterate all of the inputs whose value is less than the target and randomly decide whether to include or exclude the input. It will do this loop 1000 times. Of the input sets that this finds, it will choose the one whose total value is the minimum that is still greater than the target (similar to the lowest larger input).</p>
<p>If this approximation does not result in an exact match, and the sum of the inputs whose value is less than the target is greater than the target plus a minimum change of 0.01 BTC, then the approximation will be run again with the target increased by that 0.01 minimum change value.</p>
<p>With this approximation algorithm, an important effect is that if you have a lot of small inputs and just a few outliers that are much higher valued, it is very likely that the approximation will choose a lot of the small inputs to meet a higher value rather than the large inputs with a few small ones. This is due to the randomness used when deciding whether to include or exclude an output.</p>
<p>With that in mind, what happened with this transaction? While I can't say for sure without knowing the values of all of the inputs in the wallet at the time, I can make an educated guess. However we do know that the target value is 0.51977991.</p>
<p>The first thing to notice is that the large input is ~0.025 greater than the target, and with a wallet with lots of small inputs, it's likely that a set of smaller inputs can be chosen that is between the target and that single large input. So in the first iteration, what happened is that the approximation found a set of inputs where the value is between the target and the large input. This would be a large input set and thus require a high fee.</p>
<p>In the next iteration the target would be increased by that fee, and because the approximation is limited to the inputs smaller than the new target, it would still be picking small inputs. So it would end up choosing even more smaller inputs to make up for the fee that is needed.</p>
<p>With a few hundred more inputs of similar size to the ones that ended up being picked, it could be that the first iteration chose ~800 inputs. This would have pushed the target to be larger than your large single input, but your large single input would have just ended up not being picked amongst the multitude of smaller inputs.</p>

CC BY-SA 4.0
2022-06-03T13:32:05.320Z
Note that this iterative behavior of choosing the fee has since been replaced by using the effective value of inputs which directly accounts for the cost of each input when it is picked.
Murch
CC BY-SA 4.0
2022-06-02T23:13:20.833Z
2022-06-02T23:20:38.817Z
2022-06-02T23:20:38.817Z
Ava Chow
<p>I have a weird issue that I thought was fixed a few years back with Bitcoin wallet to reduce fees. I guess not, or I am missing something...</p>
<p>My wallet received a transaction for the amount of <strong><a href="https://www.blockchain.com/btc/address/3JbNMb2Vpn5k6eCmDUDdRqnm5ke1otL9E1" rel="nofollow noreferrer">0.54530200 BTC</a></strong>, yet when I went and sent <strong><a href="https://www.blockchain.com/btc/tx/81e681e4d7ed58a7645b3d8ae38c584e14954c359e3db8788b5ef645d65e9e64" rel="nofollow noreferrer">0.51986042 BTC</a></strong> out using bitcoin-cli sendtomany to 16 outputs, the wallet used <strong>856 inputs</strong> to send the amount that was available and cleared with at least 400+ confirmations in the first address.</p>
<p>The above TX cost me 0.03600705 BTC to send when it should have cost me a fraction of the amount had it used the address that contained the closest amount to the amount it's sending out...</p>
<p><strong>Bitcoint-cli version 0.19.1</strong></p>
<p>Any ideas what I could be doing wrong or what I could be missing?</p>

CC BY-SA 4.0
2020-12-08T00:37:29.730Z
Does the resulting transaction only have recipient outputs and no change outputs?
Ava Chow
CC BY-SA 4.0
2020-12-08T00:58:20.603Z
It has 1 change output and 15 recipient outputs.
Duetschpire
CC BY-SA 4.0
2020-12-09T19:47:24.643Z
Hi Duetschpire, I am wondering how many unspents this wallet roughly had when you were building the transaction.
Murch
CC BY-SA 4.0
2020-12-09T19:54:33.047Z
Nevermind, I'm looking at the issue on Github now.
Murch
CC BY-SA 4.0
2020-12-09T23:33:54.387Z
I can't tell you exactly, this is automated. But I am guessing close to 1,000, which is not unusual as we have over 800 unspent inputs right now in the wallet.
Duetschpire
<bitcoin-cli><coin-selection><input>
Bitcoin-cli 0.19.1 Wallet not Sending from Addresses with Closest Amount?
Duetschpire
# Bitcoin-cli 0.19.1 Wallet not Sending from Addresses with Closest Amount?

(Asked by: username_0 on 2020-12-08)

I have a weird issue that I thought was fixed a few years back with Bitcoin wallet to reduce fees. I guess not, or I am missing something...

My wallet received a transaction for the amount of **[0.54530200 BTC](https://www.blockchain.com/btc/address/3JbNMb2Vpn5k6eCmDUDdRqnm5ke1otL9E1)**, yet when I went and sent **[0.51986042 BTC](https://www.blockchain.com/btc/tx/81e681e4d7ed58a7645b3d8ae38c584e14954c359e3db8788b5ef645d65e9e64)** out using bitcoin-cli sendtomany to 16 outputs, the wallet used **856 inputs** to send the amount that was available and cleared with at least 400+ confirmations in the first address.

The above TX cost me 0.03600705 BTC to send when it should have cost me a fraction of the amount had it used the address that contained the closest amount to the amount it's sending out...

**Bitcoint-cli version 0.19.1**

Any ideas what I could be doing wrong or what I could be missing?

**Tags:** bitcoin-cli, coin-selection, input

> **Comments:**
> **username_1**: Does the resulting transaction only have recipient outputs and no change outputs?  
> **username_0**: It has 1 change output and 15 recipient outputs.  
> **username_2**: Hi username_0, I am wondering how many unspents this wallet roughly had when you were building the transaction.  
> **username_2**: Nevermind, I'm looking at the issue on Github now.  
> **username_0**: I can't tell you exactly, this is automated. But I am guessing close to 1,000, which is not unusual as we have over 800 unspent inputs right now in the wallet.  

---

## 1 answers

### Answer by username_1 on 2022-06-02. Score: 1

The coin selection algorithm present in Bitcoin Core 0.19 tries to either find a solution where there is no change output, or a solution where the change is as close to 0.01 BTC as possible without going under that amount, ignoring fees.

There are two major components in 0.19's coin selection that we need to consider when analyzing this issue. The first is how it determined fees, and the second how it actually chooses the inputs. (There is a third part with finding a changeless solution, but because your transaction has change, this does not matter).

The fees were determined iteratively. It would choose inputs, calculate the fees for a transaction with those inputs, and if it did not happen to have enough value, it would increase the amount to select by that fee value and try selecting again.

For the actual selection part it would first pick out all of the inputs whose value is less than the target, and find the lowest larger input - the lowest valued input whose value is larger than the target. If the lowest larger input does not exactly match the target, it will then do a stochastic approximation.

This approximation will iterate all of the inputs whose value is less than the target and randomly decide whether to include or exclude the input. It will do this loop 1000 times. Of the input sets that this finds, it will choose the one whose total value is the minimum that is still greater than the target (similar to the lowest larger input).

If this approximation does not result in an exact match, and the sum of the inputs whose value is less than the target is greater than the target plus a minimum change of 0.01 BTC, then the approximation will be run again with the target increased by that 0.01 minimum change value.

With this approximation algorithm, an important effect is that if you have a lot of small inputs and just a few outliers that are much higher valued, it is very likely that the approximation will choose a lot of the small inputs to meet a higher value rather than the large inputs with a few small ones. This is due to the randomness used when deciding whether to include or exclude an output.

With that in mind, what happened with this transaction? While I can't say for sure without knowing the values of all of the inputs in the wallet at the time, I can make an educated guess. However we do know that the target value is 0.51977991.

The first thing to notice is that the large input is ~0.025 greater than the target, and with a wallet with lots of small inputs, it's likely that a set of smaller inputs can be chosen that is between the target and that single large input. So in the first iteration, what happened is that the approximation found a set of inputs where the value is between the target and the large input. This would be a large input set and thus require a high fee.

In the next iteration the target would be increased by that fee, and because the approximation is limited to the inputs smaller than the new target, it would still be picking small inputs. So it would end up choosing even more smaller inputs to make up for the fee that is needed.

With a few hundred more inputs of similar size to the ones that ended up being picked, it could be that the first iteration chose ~800 inputs. This would have pushed the target to be larger than your large single input, but your large single input would have just ended up not being picked amongst the multitude of smaller inputs.

> **Comments:**
> **username_2**: Note that this iterative behavior of choosing the fee has since been replaced by using the effective value of inputs which directly accounts for the cost of each input when it is picked.  

---

