Constructing transactions

In order to construct a transaction the wallet will validate the outputs, before selecting some coins to use in the transaction. This involves multiple steps and we can follow an outline of the process by walking through the sendtoaddress RPC command, which returns by calling SendMoney().

After initialisation SendMoney() will call wallet.CreateTransaction() (CWallet::CreateTransaction()) followed by wallet.CommitTransaction() if successful. If we follow wallet.CreateTransaction() we see that it is a wrapper function which calls private member function CWallet::CreateTransactionInternal().

CreateTransactionInternal

We fetch change addresses of an "appropriate type" here, where "appropriate" means that it should try to minimise revealing that it is a change address, for example by being a different OUTPUT_TYPE to the other outputs. Once a suitable change address is selected A new ReserveDestination object is created which keeps track of reserved addresses to prevent address re-use.

The address is not "fully" reserved until GetReservedDestination() is called later.

Next some basic checks on the requested transaction parameters are carried out (e.g. sanity checking of amounts and recipients) by looping through each pair of (recipient, amount). After initializing a new transaction (txNew), a fee calculation (feeCalc) and variables for the transaction size, we enter into a new code block where the cs_wallet lock is acquired and the nLockTime for the transaction is set:

src/wallet/wallet.cpp#CWallet::CreateTransactionInternal()
// ...

CMutableTransaction txNew;
FeeCalculation feeCalc;
CAmount nFeeNeeded;
std::pair<int64_t, int64_t> tx_sizes;
int nBytes;
{
    std::set<CInputCoin> setCoins;
    LOCK(cs_wallet);
    txNew.nLockTime = GetLocktimeForNewTransaction(chain(), GetLastBlockHash(), GetLastBlockHeight());
        {
            std::vector<COutput> vAvailableCoins;
            AvailableCoins(vAvailableCoins, true, &coin_control, 1, MAX_MONEY, MAX_MONEY, 0);

    // ...

Bitcoin Core chooses to set nLockTime to the current block to discourage fee sniping.

We must acquire the lock here because we are about to attempt to select coins for spending, and optionally reserve change addresses.

If we did not have the lock it might be possible for the wallet to construct two transactions which attempted to spend the same coins, or which used the same change address.

AvailableCoins

After this, a second new code block is entered where "available coins" are inserted into a vector of COutputs named vAvailableCoins. The concept of an "available coin" is somewhat complex, but roughly it excludes:

  1. "used" coins

  2. coins which do not have enough confirmations (N.B. confirmations required differs for own change)

  3. coins which are part of an immature coinbase (< 100 confirmations)

  4. coins which have not entered into our mempool

  5. coins which are already being used to (attempt) replacement of other coins

This call to AvailableCoins() is our first reference back to the underlying ScriptPubKeyMans controlled by the wallet. The function iterates over all coins belonging to us — found in the CWallet.mapWallet mapping — checking coin availability before querying for a SolvingProvider (ultimately calling GetSigningProvider()): essentially querying whether the active CWallet has a ScriptPubKeyMan which can sign for the given output.

src/wallet/wallet.cpp#CWallet::GetSolvingProvider()
std::unique_ptr<SigningProvider> CWallet::GetSolvingProvider(const CScript& script, SignatureData& sigdata) const
{
    for (const auto& spk_man_pair : m_spk_managers) {
        if (spk_man_pair.second->CanProvide(script, sigdata)) {
            return spk_man_pair.second->GetSolvingProvider(script);
        }
    }
    return nullptr;
}

Below is a section of the AvailableCoins() function which illustrates available coins being added to the vAvailableCoins vector, with the call to GetSolvingProvider() visible.

If a SigningProvider is found a second check is performed: to see if the coin is "solvable" by calling IsSolvable().

Whilst getSolvingProvider() might return a SigningProvider (read: SPKM), not all SPKMs will be able to provide private key data needed for signing transactions, e.g. in the case of a watch-only wallet.

After we have determined solvablility, "spendability" is calculated for each potential output along with any coin control limitations:

src/wallet/wallet.cpp#AvailableCoins()
    // ...

    for (unsigned int i = 0; i < wtx.tx->vout.size(); i++) {

        // ...

        std::unique_ptr<SigningProvider> provider = GetSolvingProvider(wtx.tx->vout[i].scriptPubKey);

        bool solvable = provider ? IsSolvable(*provider, wtx.tx->vout[i].scriptPubKey) : false;
        bool spendable = ((mine & ISMINE_SPENDABLE) != ISMINE_NO) || (((mine & ISMINE_WATCH_ONLY) != ISMINE_NO) && (coinControl && coinControl->fAllowWatchOnly && solvable));

        vCoins.push_back(COutput(&wtx, i, nDepth, spendable, solvable, safeTx, (coinControl && coinControl->fAllowWatchOnly)));

        // Checks the sum amount of all UTXO's.
        if (nMinimumSumAmount != MAX_MONEY) {
            nTotal += wtx.tx->vout[i].nValue;

            if (nTotal >= nMinimumSumAmount) {
                return;
            }
        }

        // Checks the maximum number of UTXO's.
        if (nMaximumCount > 0 && vCoins.size() >= nMaximumCount) {
            return;
        }

        // ...

See the full CWallet::AvailableCoins() implementation for additional details and caveats.

CreateTransactionInternal continued

After available coins have been determined, we check to see if the user has provided a custom change address (used coin control), or whether the earlier not-fully-reserved change address should finally be reserved and selected by calling GetReservedDestination(). The change outputs' size, discard_free_rate and effective_fee_rate are then calculated. The discard_fee_rate refers to any change output which would be dust at the discard_rate, and that you would be willing to discard completely and add to fee (as well as continuing to pay the fee that would have been needed for creating the change).

Coin selection

Now that we have a vector of available coins and our fee rate settings estimated, we are ready to start coin selection itself. This is still an active area of research, with two possible coin selection solving algorithms currently implemented:

  1. Branch and bound ("bnb")

  2. Knapsack

The branch and bound algorithm is well-documented in the codebase itself:

src/wallet/coinselection.cpp
/*
This is the Branch and Bound Coin Selection algorithm designed by Murch. It searches for an input
set that can pay for the spending target and does not exceed the spending target by more than the
cost of creating and spending a change output. The algorithm uses a depth-first search on a binary
tree. In the binary tree, each node corresponds to the inclusion or the omission of a UTXO. UTXOs
are sorted by their effective values and the trees is explored deterministically per the inclusion
branch first. At each node, the algorithm checks whether the selection is within the target range.
While the selection has not reached the target range, more UTXOs are included. When a selection's
value exceeds the target range, the complete subtree deriving from this selection can be omitted.
At that point, the last included UTXO is deselected and the corresponding omission branch explored
instead. The search ends after the complete tree has been searched or after a limited number of tries.

The search continues to search for better solutions after one solution has been found. The best
solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
spend the current inputs at the given fee rate minus the long term expected cost to spend the
inputs, plus the amount the selection exceeds the spending target:

waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)

The algorithm uses two additional optimizations. A lookahead keeps track of the total value of
the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range
cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us
to skip testing the inclusion of UTXOs that match the effective value and waste of an omitted
predecessor.

The Branch and Bound algorithm is described in detail in Murch's Master Thesis: https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf

@param const std::vector<CInputCoin>& utxo_pool The set of UTXOs that we are choosing from.
       These UTXOs will be sorted in descending order by effective value and the CInputCoins'
       values are their effective values.
@param const CAmount& target_value This is the value that we want to select. It is the lower
       bound of the range.
@param const CAmount& cost_of_change This is the cost of creating and spending a change output.
       This plus target_value is the upper bound of the range.
@param std::set<CInputCoin>& out_set -> This is an output parameter for the set of CInputCoins
       that have been selected.
@param CAmount& value_ret -> This is an output parameter for the total value of the CInputCoins
       that were selected.
@param CAmount not_input_fees -> The fees that need to be paid for the outputs and fixed size
       overhead (version, locktime, marker and flag)
*/

You can read a little more about the differences between these two coin selection algorithms in this StackExchange answer.

You can read more about waste and the waste metric in this StackExchange answer.

Coin selection is performed as a loop, as it may take multiple iterations to select the optimal coins for a given transaction.