3

Playing around with Bitcoin Core Client v0.18.0, I used this command:

$ bitcoin-cli sendtoaddress "mozazucvLK179u41bF5Vd2Agp4wsm7HsPo" 0.1

which created this transaction.

I noticed that the transaction created consumed three inputs, even though there were UTXOs of the exact amount available.

Looking for the UTXO selection algorithm, I came across the Bound Coin Selection Algorithm, but I'm not really familiar with the codebase.

Is this the only coin selection algorithm used by the client? Can someone explain how does it work?

2

1 Answer 1

5

There are a lot of things that need to be considered when selecting coins. Just covering the amount that you want to send is not enough, you have not considered the transaction fees that you will be paying for your transaction. So even though you have UTXOs of 0.1 BTC in value, using just one of those means that you will not have enough value in the transaction to cover the transaction fee so your transaction won't be relayed or confirmed.

So if you have to go over the target value, now you need to have change outputs. But even here you have to be careful. If you choose just enough Bitcoin to cover the outgoing amount and the transaction fee, you may end up producing a very small change output that would be considered dust. Dust outputs are not good as they are uneconomical to spend, i.e. they cost more in transaction fees than they are worth.


Bitcoin Core uses two different coin selection algorithms for different cases, and they have different target values.

The first one (the one that you found), is known as Branch and Bound. It tries to exactly match the amount needed for the transaction (outgoing amount + transaction fees) and not produce change. There is a small buffer allowing the algorithm to select slightly more coins than necessary in order to have a better match and avoid producing change outputs.

The general idea for this buffer is that if you are willing to create a change output and have to consume the cost of spending that output in the future, then you are willing to take that cost now and simply not produce a change output. So long as the extra amount that was selected is less than the predicted cost of spending a change output in the future, it is worth it to burn that amount now as extra transaction fee rather than producing a change output. The cost to the user is at most the same, and more likely to be less.

In general, this will produce smaller transactions and thus pay less in fees due to avoiding change outputs. It also helps with privacy because there is no change to link back to your wallet.

If the Branch and Bound exact matcher fails and it must produce a change output, then Bitcoin Core falls back to its original algorithm. This original algorithm is largely also an exact matcher, it just has a bunch of random fixes and hacks that were put into it to fix various issues. At a high level, it randomly selects coins.

An important part of this fallback algorithm is that, because it must create a change output, it chooses to target a minimum change amount to avoid the dust issue I mentioned earlier. Bitcoin Core defaults a minimum change amount of 0.01 Bitcoin. Of course there are exceptions to this when there are not enough coins in the wallet.


So what happened here is that you did not have coins of the correct values to exactly match 0.01 BTC + transaction fees, so the Branch and Bound algorithm fails. It falls back to the fallback algorithm and now targets 0.01 BTC (outgoing) + 0.01 (minimum change) + transaction fees. The fallback algorithm is able to select coins for this target value and thus you get the transaction that you have.

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.