Coin selection algorithm not working as expected resulting in more fees

ghost commented at 9:22 am on December 8, 2020: none

One user reported the issue on Bitcoin SE: https://bitcoin.stackexchange.com/questions/100437/bitcoin-cli-0-19-1-wallet-not-sending-from-addresses-with-closest-amount

UTXO A : 0.5 BTC UTXO B-Z : 0.5 BTC

UTXO B-Z are selected instead of UTXO A as the input for the transaction if I try to pay someone 0.5 BTC or more. Size of transaction is increased so user has to pay more fees.

Expected behavior

UTXO A should be selected as input automatically which will decrease the size of transaction and fees.

To reproduce

I tried to reproduce the issue by following below steps:

Create 850 addresses in bitcoin core: for ($i=1; $i -le 850; $i++) {.\bitcoin-cli.exe getnewaddress}
Add random amounts similar to the transaction mentioned by user in the issue: 81e681e4d7ed58a7645b3d8ae38c584e14954c359e3db8788b5ef645d65e9e64

CSV file with address and amounts: https://mega.nz/file/ixsyjDYC#19Ff2qZP7LQjCvhz4ISF84uESPBesWrZmMVngJWGMOk
Create, Sign and Broadcast a transaction to one of the address in my bitcoin core wallet using above CSV file from electrum wallet

Tx: https://blockstream.info/testnet/tx/b5c6c6dd204420020795fbf356d4db85a9398dbd99e575c72b76ec5f8d8d78e2
Send 0.54 BTC in one more transaction to my bitcoin core wallet:

https://blockstream.info/testnet/tx/37675b6d44d1fe1b8095349f5d08d12197cee76504a0da6b0ab99fb29a4fa176
Finally we have a similar setup in bitcoin core to reproduce the issue. Try to send 0.49 BTC to some address and very small amounts to few other addresses by creating a transaction in bitcoin core wallet as the user did in tx mentioned on SE: https://i.imgur.com/utWKiZN.png

https://i.imgur.com/WtduQx8.png
If I do not use “coin control features” and inputs are selected automatically:

If use “coin control features” and select UTXO with 0.54 BTC:

System information

Bitcoin Core v 0.20.0

Additional information

Still trying to understand how Coin Selection Algorithm works, why it didn’t select tb1qztazgd5665j9q0ww7qw24ms42gny6vc2h3z5yg as input automatically and how can we fix this.

The user has mentioned on SE:

I have a feeling that coin control favors more inputs with less combined “change” over less inputs with more combined change. In this case the change address (3BF5VhQgnabWMsB8QhVrBoWD6is2XMKuQs) received 0.00008051 BTC, where the input with the closest full amount amount would have resulted in (0.02544158 - tx fee) in change

unknown added the label Bug on Dec 8, 2020

achow101 commented at 5:45 pm on December 8, 2020: member

In general, our coin selection algorithm does not currently consider the fee that each input will require when it does the selection. The exception is the first Branch and Bound pass that we do. This pass will attempt to find a solution without change at all, and it does consider the fee paid in its selection. This could result in an input set that is very large but produces no change. However that is not the case here. Further selection attempts (when BnB fails) will attempt to create a minimum change amount of 0.01 BTC, although it may fail to do so and make smaller change. There is no preference for smaller change at this stage because smaller change means that UTXOs will tend to be broken down into dust.

The fallback selection method includes randomness and will somewhat randomly choose different UTXOs for inclusion, although it is not a true random selector. I believe that if you run this experiment many times, eventually one of the results will have lower fees and choose the largest input. Due to the large number of UTXOs in this wallet, various iteration limits may be run into here so a less optimal solution may be chosen.

Lastly, always choosing a lowest fee input set always degenerates into the largest first case which is not ideal. Largest first selection is not healthy for the wallet as over time it grinds UTXOs into dust which causes future transactions to pay even higher fees.

ghost commented at 7:59 pm on December 8, 2020: none

In general, our coin selection algorithm does not currently consider the fee that each input will require when it does the selection.

This doesn’t look right approach considering lot of users and projects might be trusting the algorithm to provide the best selection for them while creating a transaction. In this case it is a business that does the transactions for users so I am assuming a lot of transactions are overpaying from years for transactions that could have been done with less fees.

There is no preference for smaller change at this stage because smaller change means that UTXOs will tend to be broken down into dust.

Still trying to read the code, experiment with wallet and understand what role does “change” play in this and how does it affect selecting inputs with more fees involved. Maybe will get some clarity by morning.

I believe that if you run this experiment many times, eventually one of the results will have lower fees and choose the largest input.

This does not help the users and projects who are trusting the algorithm and creating transactions with whatever results they get first time.

Largest first selection is not healthy for the wallet as over time it grinds UTXOs into dust which causes future transactions to pay even higher fees.

Agree but in this case it might have helped especially if we had some warning messages or hints included in the RPC commands createrawtransaction or fundrawtransaction results.

Example:

The user tries to create a transaction with inputs automatically selected. Algorithm added inputs. Size: 54kB Fees: 0.0135 BTC and there is a warning message: “You can save fees by selecting other input(s). Size: 0.48kB Fees: 0.00012 BTC”
If the user doesn’t care about fees he can go ahead and sign this transaction to broadcast it later.
If the user wants to save fees he should be able to create transaction with other input. Algorithm should be smart enough to suggest such things for users who trust bitcoin core.
We can also add additional information in the warning messages: Links to know about UTXO consolidation, Best Practices to save fees, Segwit addresses benefits etc.
This user could have done the transaction with bigger input to save fees and also not wait for days to get the transaction confirmed as its related to business. Time and Money matters a lot for businesses. They are trusting bitcoin core algorithms to help them.
Later the user could have done UTXO consolidation when mempool is clear with 1sat/vByte to get all the small amount UTXOs in to one. This would again require less fees but might have to wait for hours/days which can be considered a planned maintenance with preparation.
If warning messages are not possible or won’t help most of the users, can we have one option in bitcoin.conf to enable priority for coin selection like spendzeroconfchange and txconfirmtarget ? Maybe: coinselection=1 for privacy, coinselection=2 for fees, coinselection=3 for dust and by default it will work as its working right now.

achow101 commented at 8:19 pm on December 8, 2020: member

best selection

And how is “best” defined? There is no clear definition of what is best because there are so many variables involved in coin selection.

Example:

Providing so much additional information to users generally makes a bad user experience, especially for users who don’t know how transactions and transaction fees work. I don’t think it would be good to do be suggesting alternatives and telling users to study all this other stuff. The point of having a software manage UTXOs and make transactions is to abstract all of that away from the user. You end with with decision paralysis or users choosing some “obvious” thing without understanding the nuance. I’m certain that if you presented the option for users to have a “prefer lower fees” coin selection, the vast majority of users would pick that and not realize that doing so will create a degenerate wallet in the long run.

I agree that coin selection should be better. But all of that takes work and requires review. And it most certainly won’t happen quickly. Few people understand coin selection to review changes to it. Few people are willing to review coin selection code. We have to make it understandable first before any material changes to the algorithms can be done. I currently have 3 coin selection PRs open that address some issues: #20040, #17331, #17526. I have additional branches based on those which make it much easier to understand coin selection, so hopefully we can begin working on other material changes to the algorithms.

ghost commented at 4:18 am on December 9, 2020: none

I currently have 3 coin selection PRs open that address some issues: #20040, #17331, #17526. I have additional branches based on those which make it much easier to understand coin selection, so hopefully we can begin working on other material changes to the algorithms.

Sounds good

ahmadaoun commented at 4:49 am on December 9, 2020: none

@prayank23 thank you for submitting this issue and for your input thus far. @achow101 thanks for clarifying a few things as well. I am the user with this issue/concern so I thought I would add my bit as well.

While I agree the “best selection” is relative, there has to be a way to balance using UTXOs with small fees and using UTXOs with closest available amount, as well as change. I’m not entirely sure why change is considered bad, I may be missing something.

I run a business where a lot of our transactions are between $10-$20. We do a fair amount of transactions over $100 and a very few over $1,000. We never send out more than we have received on a single transaction.

In 2017 we decided to use senttomany and consolidate all our sends to every 4 hours instead of sending to a single address every time an escrow is released or refunded so that we can reduce the fees. That did help, but over the past 5 months we have sent out 8 transactions where each cost 0.01 - 0.05 BTC in fees. The total amount for the 8 transactions was 2.1511 BTC and the total fee was 0.18 BTC. This should not happen considering all the sent amount had been received (plus 2.5%-5% explained below) to different addresses.

If coin selection was selecting the inputs with the closes amounts to the amount being sent, then all my addresses would be within 2.5% - 5% from that amount. The 2.5%-5% is the fee being deducted from the amount we send back out. For example, if we receive 0.5 BTC to an address, then we would expect to send out 0.475 - 0.4875 BTC back out within 30 days (in most cases within 10 days).

If the transactions were personal, then this would never be a problem. It would take a lot of effort to build up a 1,000 input wallet for personal use. But businesses can run into this issue a lot more frequently. We have around 2,500 new inputs a month.

If there was a way to set a flag to set a max input per transaction where the desired amount can be reached then it would help businesses put a “stop loss” on fees so that a single transaction fee doesn’t blow up the way some of ours did.

I know this is a far chance, but is there a way to consolidate inputs automatically every x days/weeks? I tried researching and what I found was too fiddly and cannot be automated.

The transactions are below for reference:

fee	txid	time
-0.03600705	81e681e4d7ed58a7645b3d8ae38c584e14954c359e3db8788b5ef645d65e9e64	4/12/2020 15:00
-0.01397923	ad1e27699b5ee4fb71029e4fcff4170919846a324bf5a980085aa00fa9c5b400	5/11/2020 23:00
-0.01690541	0def8fa0066760e5d7bb7a6bc4d1c4e6c0575a817509695862e8d0e1f9aa12a9	27/10/2020 19:00
-0.01078708	d77eeb378fd757437cb717cf9262de0a715a6b494027c1b20a77fb945c2e360f	10/09/2020 18:00
-0.01714392	a5e0ca1763c3d077229d7e71e81f18e234293fb8811f46fe18549d2531b81d9a	7/09/2020 23:10
-0.01011056	b9b981e6f90e9f3fd0f692280a47aa71c23cb1d2387d9610c5bbc39a0c9f0f71	28/07/2020 22:00
-0.02339042	ee86fbe4db58131b3347cda1fc2691ab8a7c31c458a7adb64a82bc5f09c3dac3	22/07/2020 22:00
-0.0517428	01ed3e118c81c3a3b837abfbfa97ae095deecf3105ddd36d4d1cace66d1d1b73	22/07/2020 21:59
-0.18006647

ghost commented at 6:39 am on December 9, 2020: none

If there was a way to set a flag to set a max input per transaction where the desired amount can be reached then it would help businesses put a “stop loss” on fees so that a single transaction fee doesn’t blow up the way some of ours did. @ahmadaoun Maybe you can use maxtxfee in bitcoin.conf to configure maximum fee per transaction and anything above it should be discarded.

Also check other options available that may help you in avoiding such issues: https://github.com/jlopp/bitcoin-core-config-generator/blob/master/src/data.json

MarcoFalke commented at 7:04 am on December 9, 2020: member

maxtxfee doesn’t affect coin selection. It will abort transactions, but this is also mentioned in the docs:

0  -maxtxfee=<amt>
1       Maximum total fees (in BTC) to use in a single wallet transaction;
2       setting this too low may abort large transactions (default: 0.10)

MarcoFalke commented at 7:10 am on December 9, 2020: member

I think in the future it might make sense to offer different coin selection algorithms, because the one-size-fits-all doesn’t really fit everyone. An algorithm that selects the least amount of input coins to reach the target (for a high feerate tx) could make sense in a wallet that regularly consolidates the change-spam with lower feerates.

Obviously, there is always the possibility to implement coin selection externally, but not all users of Bitcoin Core might have the expertise to do so.

ghost commented at 7:01 pm on December 12, 2020: none

maxtxfee doesn’t affect coin selection. It will abort transactions

True. I was just suggesting a workaround for now to avoid paying more fees.

I think in the future it might make sense to offer different coin selection algorithms, because the one-size-fits-all doesn’t really fit everyone.

Agree.

I found something that looks interesting and maybe help in improving ‘coin selection algorithm’ in bitcoin core or creating multiple algorithms to select from:

https://github.com/vladmelnyk/coinselection

Randomly picks unspent outputs from the provided list until the target value is covered. In case the algorithm has picked too many inputs (default 60) - fallback to Largest first algorithm.

Take remaining inputs until reaching 2*target, so that the change output is close to target. This creates useful UTXOs in the long run, especially if we tend to send approximately the same amount.

sipa commented at 7:08 pm on December 12, 2020: member

@prayank23 The problem isn’t a lack of ideas on how to improve coin selection; see #17526 for example which implements an algorithm suggested in @Xekyo’s master thesis on the topic (https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf; a good read if you’re interested in a comparison between various strategies). The issue is finding reviewers and getting assurances about touching this code in the first place.

promag commented at 7:20 pm on December 12, 2020: member

The best selection really depends on the use case. For instance, those that send to multiple destinations too often might want to consolidate on each batch - add extra small inputs and get them in the change output - because at the end this can be cheaper and lead to better unspent set.

achow101 commented at 5:06 pm on October 5, 2021: member

Has 22.0 had any significant effect on this? #17331 was merged for 22.0 and that implements some consideration of input fees when selecting inputs.

How about current master? Both #22009 and #17526 were merged. These are significant changes to coin selection. The first introduces a waste metric which should help avoid such scenarios. The second adds a new coin selection algorithm that could perform better.

ghost commented at 0:39 am on October 6, 2021: none

I will try to reproduce this on master branch today and share the results.

ghost commented at 7:55 pm on October 6, 2021: none

Tx1 (send small amounts to 700 addresses): 21f5c6a9f5681d9a15833875e617a51284da9296ef56c3ada0b93a5263abce66 Tx2 (send 0.4 BTC to one address): 051f0b371800bfbc11a47f5e778e74fc007f41b99ec5a7ec17ef3ec7012a61fb

Using Coin selection and trying to send 0.4 BTC:

641 inputs used for it in Tx3: 98177fd0927f67fc46f38414cdc60ea208a86aad41a7346974489da73fbe1331

So v 22.0 does not fix this and issue remains same. Will try it on master branch in morning.

ghost commented at 1:53 pm on October 7, 2021: none

Awesome! The issue is resolved in master branch.

Tx: 1bc0b7c388f999ec5a484edd39be03046625a06b9317b23428554864aed41eb3

I have one question:

It used few inputs to pay for fees and create a change which is 0.01. Is this 0.01 some minimum change which is required? @achow101

unknown closed this on Oct 7, 2021

achow101 commented at 4:06 pm on October 7, 2021: member

Yes, when making transaction with change, the coin selection algorithms will try to make a minimum change of 0.01 BTC. This could probably be tuned, but the goal is to avoid creating really small change that could end up being dust in the future.

Xekyo commented at 8:01 pm on October 22, 2021: member

@prayank23: Your test transactions do not test the issue described in the SE post. Bitcoin Core’s coin selection will prefer a smaller input set at high feerates to reduce cost and a bigger input set at low feerates to aid in consolidation. At 1 sat/vB Bitcoin Core will prefer a larger input set, so it was probably pure chance that you got a small transaction in the last attempt. If you’d like to test whether it’s now more thrifty in cases as described by the asker on SE, you need to build your transaction at a higher feerate (like the mentioned 46 sat/vB).

ghost commented at 8:13 pm on October 22, 2021: none

Interesting. Will try tomorrow. Travelling right now.

ghost commented at 6:31 pm on November 3, 2021: none

@Xekyo Tried same thing but used 45 sat/vB this time: 1 input 2 output

969bbc7d668bbbe1efde1e599533a806d7128fec17c388c126e9715e4d04fc4a

DrahtBot locked this on Nov 3, 2022

Coin selection algorithm not working as expected resulting in more fees #20598