The PR branch HEAD was 4ac1add at the time of this review club meeting.
Wallets maintain their balance as a pool of Unspent Transaction Outputs
collects all UTXOs that were sent to the same public key.
Coin selection refers to the process of picking UTXOs from the wallet’s UTXO
pool to fund a transaction.
Beyond the primary goal of funding a transaction, the secondary goals of coin
Minimizing short term and long term fees:
We have to balance two needs: we want to pay the smallest fee now to get a
timely confirmation, but we have to keep in mind that all of the wallet’s
UTXOs will need to be spent at some point. We shouldn’t over-optimize
locally at the detriment of large future costs. E.g. always using
largest-first selection minimizes the current cost, but grinds the
wallet’s UTXO pool to dust.
Maintaining financial privacy:
There are a number of heuristics that tracking companies employ to cluster
payments and addresses. For example, using inputs with the same output
script in two transactions indicates that the two transactions involved
the same party. Similarly, it is usually assumed that all inputs of a
transaction were controlled by the same entity. Sometimes the privacy and
economic considerations are opposed. If you want to understand privacy
considerations better, check out the Privacy
article on the Bitcoin wiki.
Reliably move the payment(s) to finalization:
Using unconfirmed inputs can make transactions unreliable. Unconfirmed
transactions received from another wallet may time out or be replaced,
making those funds disappear. Even using self-sent unconfirmed funds may
delay the new transaction if the parent transaction has an extensive
ancestry, is extraordinarily large, or used a lower feerate than targeted
for the child transaction.
The process of creating a transaction in Bitcoin Core’s wallet roughly
follows these steps:
CreateTransaction() builds the header and recipient outputs, i.e. the
parts of the transaction that will remain fixed throughout the coin
The long_term_feerate, effective_feerate, and discard_feerate are
established using GetMinimumFeeRate(), which falls back either to fee
estimation or user input. The feerates remain constant for the remaining
process. The amount to be raised from the inputs, nTargetValue is
calculated from the sum of recipient amounts, the target feerate, and the
size of the fixed transaction parts.
The wallet’s UTXO pool is retrieved via AvailableCoins().
Using the above fixed values, SelectCoins() is used to pick an input
set to fund the transaction. If the user manually selected some UTXOs by
means of the CoinControl feature, these UTXOs are used first. The
remaining UTXOs are grouped into OutputGroups. The grouped UTXOs are
then used in one or multiple rounds of SelectCoinsMinConf(), using
increasingly permissive CoinEligibilityFilters to preselect
OutputGroups until an input set is found.
Determine whether to create a change output, finish assembling the
transaction, and sign the transaction.
When a UTXO is selected as an input, the size of the transaction is increased,
which in turn increases the necessary fees to maintain the targeted feerate.
We can preempt the cost added by the input by considering each UTXO at its
effective value, its value reduced by the UTXO’s input cost at the given
Bitcoin Core currently uses two different solvers:
The knapsack solver sorts the available UTXOs by effective value, and
then combines candidate input sets by randomly selecting or skipping
inputs until it has sufficient funds for the transaction. When it finds a
viable solution, it keeps the solution if it produces a smaller change
than the prior stored solution. Then, the algorithm deselects the last
input and continues traversing the UTXO list as described, trying to
converge on the smallest change output above MIN_CHANGE. This random
process is repeated up to 1,000 times.
The Branch and Bound solver (BnB) deterministically searches the
complete combination space to find an input set that will avoid the
creation of a change output. It performs a depth-first search on a binary
tree where each branch represents the inclusion or exclusion of a UTXO,
exploring inclusion branches first, and backtracking whenever a subtree
cannot yield a solution. It returns the first discovered input set that
is an exact match for the funding requirement of the transaction. The
qualifier “exact match” here refers here to an input set that overshoots
the nTargetValue by less than the cost of a change output. The BnB
algorithm is not guaranteed to find a solution even when there are
sufficient funds since an exact match may not exist.
Using effective values in coin selection means that we can freely add and
remove inputs until we have have raised enough funds to pay for the
transaction’s fixed costs: the payment amounts, the transaction header and the
output data. Whatever final input set we settle for, the increased transaction
size and input costs have already been accounted for.
PR #17331 implements the use
of effective values across all different coin selection strategies. Prior,
it was only used for the BnB selection where it facilitated the search to be
effectively performed. Introducing effective values into the knapsack solver
means it no longer works on a moving target, and thus only needs to be run
once. It also allows some of the pre-selection steps to be shared between BnB
This PR also changes the behavior of SelectCoinsMinConf() to try BnB first
and then attempt knapsack only in the case that BnB did not find an input set.
Before this PR, the function would only run one or the other strategy
controlled by the boolean flag use_bnb.
How does the effective valuediffer
from the nValue of a UTXO?
<lightlike> but isn't the knapsack algorithm non-deterministic with some randomness involved? In that case, couldn't running it multiple times still get a better solution, regardless of effective values used or not?
<sipa> raj__: at the time coin selection is invoked we already have what you could call an "incomplete" transaction; it can have multiple inputs and outputs already (which must be included); the goal of coin selection is adding (a) additional inputs from the wallet and (b) optionally adding change so that the fee is as intended
<murch> glozow: Great question, I hadn't actually thought about it. But I think that is resolved by the coin control inputs getting used first in either selection procedure and their fees getting accounted for then.
<murch> Even when some wallets e.g. copy the output type of the recipient output(s), when we are starting the coni selection, we know what we are going for as an output type—if we need one in the first place
<murch> an estimate of the maximum feerate that we will need to pay in the long term to use a UTXO. A reasonable upper bound on what we might need to pay for a low time preference transaction in the long term.