Add Single Random Draw as an additional coin selection algorithm #17526

[rajarshimaitra]

Session Details

• Date: 06-04-2023
• Time: IST 20:00 (UTC 14:30)
• PR: Add Single Random Draw as an additional coin selection algorithm bitcoin/bitcoin#17526
• Context: [Wallet]
• Difficulty: Moderate
• Language: [python][c++]
• Notes and Questions: https://bitcoincore.reviews/17526

Summary

This PR adds a new coinselection algorithm, SingleRandomDraw as a fallback to existing algorithms if they don't find any solutions.

Learning

• Wallet UTXO management.
• CoinSelection Alogythms
• Core's Coin Selection framework.
• Functional testing with coinselection.

Note: Drop your PR and review related questions below

[rajarshimaitra]

Summary

Before this PR, Bitcoin Core's wallet used to perform two different coinselection algorithms while selecting coins. Namely BranchAndBound and KanpsackSolver. The results of these two algorithms were compared in terms of waste metric to choose the best outcome.

This PR adds another simple algorithm SingleRandomDraw as a fallback of the previous two. The results of all three are compared according to
the least waste, and the best one is selected.

Can you give a high-level description of the coin selection strategy including the changes proposed in this PR?

Core's Coinselection strategy is following

• Get coins selected by the user via CCoinControl.
• Select a list of OutputGroup from the rest of the UTXOs as per different CoinEligibilityFilter.
• Perform coinselection round on the list of selected groups, until a solution is found.

Each selection round consists of the following

• Perform selection via all the algorithms, BNB, Knapsack and SRD.
• Choose the result with the least waste.

This PR adds SRD algorithm to the selection round.

This steps are defined by the
src/wallet/spend.cpp: ChooseSelectionResult()

util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue, Groups& groups, const CoinSelectionParams& coin_selection_params)
{
    // Vector of results. We will choose the best one based on waste.
    std::vector<SelectionResult> results;

    if (auto bnb_result{SelectCoinsBnB(groups.positive_group, nTargetValue, coin_selection_params.m_cost_of_change)}) {
        results.push_back(*bnb_result);
    }

    // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here.
    if (auto knapsack_result{KnapsackSolver(groups.mixed_group, nTargetValue, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast)}) {
        knapsack_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
        results.push_back(*knapsack_result);
    }

    if (auto srd_result{SelectCoinsSRD(groups.positive_group, nTargetValue, coin_selection_params.rng_fast)}) {
        srd_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
        results.push_back(*srd_result);
    }

    if (results.empty()) {
        // No solution found
        return util::Error();
    }

    std::vector<SelectionResult> eligible_results;
    std::copy_if(results.begin(), results.end(), std::back_inserter(eligible_results), [coin_selection_params](const SelectionResult& result) {
        const auto initWeight{coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR};
        return initWeight + result.GetWeight() <= static_cast<int>(MAX_STANDARD_TX_WEIGHT);
    });

    if (eligible_results.empty()) {
        return util::Error{_("The inputs size exceeds the maximum weight. "
                             "Please try sending a smaller amount or manually consolidating your wallet's UTXOs")};
    }

    // Choose the result with the least waste
    // If the waste is the same, choose the one which spends more inputs.
    auto& best_result = *std::min_element(eligible_results.begin(), eligible_results.end());
    return best_result;
}

The above function is conceptually simple and performs the following operations:

Given a set of groups, the target amount, and coin selection parameters, it performs the following

• Calculate selection results for all three algorithms, and store them in the results vector.
• Filter the result for which the weight > MAX_STANDARD_TX_WEIGHT.
• Find the best result (least waste) from the list.

Within ChooseSelectionResult(), if we have both a Knapsack and an SRD solution, how do we decide which one to use?

For all three coinselection algorithms, results are calculated, and the minimum of them is selected. The minimum for SelectionResult
is defined as below
src/wallet/coinselection.cpp

bool SelectionResult::operator<(SelectionResult other) const
{
    Assert(m_waste.has_value());
    Assert(other.m_waste.has_value());
    // As this operator is only used in std::min_element, we want the result that has more inputs when waste are equal.
    return *m_waste < *other.m_waste || (*m_waste == *other.m_waste && m_selected_inputs.size() > other.m_selected_inputs.size());
}

Which first chooses the result with lower waste. If waste is the same, then it selects the result with the lower number of inputs.

Why might we prefer to spend more inputs in the same transaction?

In low-fee periods, it's economical to consolidate many small inputs in a single transaction, and in high-fee periods, the reverse is true.
So the coinselection algorithm should be clever enough to dynamically adjust this behavior given the current fee environment.

Quiz: Based on the coin selection scheme proposed here, let’s say that Solutions A, B, and C exist (ignore the fact that we would exit early after finding a solution we’re satisfied with). Which would we pick? (Hint: which invocation of AutomaticCoinSelection() would each of these come from?)

• Solution A: picked using Knapsack. Produces a change output, pays 100 satoshis in fees, and only uses confirmed UTXOs, each with 4 confirmations
• Solution B: picked using BnB. No change output, pays 95 satoshis in fees, and uses one unconfirmed change output.
• Solution C: picked using SRD. Produces a change output, pays 99 satoshis in fees, and only uses confirmed UTXOs, each with 1 confirmation.

The AutomaticCoinSelection() includes an orderd_filters, which is a list of CoinEligibilityFilter that selects the output groups under various
scenarios before starting the selection algorithm.

src/wallet/spend.cpp: AutomaticCoinSelection()

        std::vector<SelectionFilter> ordered_filters{
                // If possible, fund the transaction with confirmed UTXOs only. Prefer at least six
                // confirmations on outputs received from other wallets and only spend confirmed change.
                {CoinEligibilityFilter(1, 6, 0), /*allow_mixed_output_types=*/false},
                {CoinEligibilityFilter(1, 1, 0)},
        };
        // Fall back to using zero confirmation change (but with as few ancestors in the mempool as
        // possible) if we cannot fund the transaction otherwise.
        if (wallet.m_spend_zero_conf_change) {
            ordered_filters.push_back({CoinEligibilityFilter(0, 1, 2)});
            ordered_filters.push_back({CoinEligibilityFilter(0, 1, std::min(size_t{4}, max_ancestors/3), std::min(size_t{4}, max_descendants/3))});
            ordered_filters.push_back({CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2)});
            // If partial groups are allowed, relax the requirement of spending OutputGroups (groups
            // of UTXOs sent to the same address, which are obviously controlled by a single wallet)
            // in their entirety.
            ordered_filters.push_back({CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, /*include_partial=*/true)});
            // Try with unsafe inputs if they are allowed. This may spend unconfirmed outputs
            // received from other wallets.
            if (coin_selection_params.m_include_unsafe_inputs) {
                ordered_filters.push_back({CoinEligibilityFilter(/*conf_mine=*/0, /*conf_theirs*/0, max_ancestors-1, max_descendants-1, /*include_partial=*/true)});
            }
            // Try with unlimited ancestors/descendants. The transaction will still need to meet
            // mempool ancestor/descendant policy to be accepted to mempool and broadcasted, but
            // OutputGroups use heuristics that may overestimate ancestor/descendant counts.
            if (!fRejectLongChains) {
                ordered_filters.push_back({CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(),
                                                                   std::numeric_limits<uint64_t>::max(),
                                                                   /*include_partial=*/true)});
            }

The parameters in the coin eligibility filters mean the following

    CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants, bool include_partial)

So let's run through the list of filters one by one and see which of the above three solutions fits them.

• (1 /*our conf*/, 6 /*their conf*/, 0 /*ancestor count*/) : None of the solutions fit this filter as the max confirmation we have is for solution A, which is 4.
• (1 /*our conf*/, 1 /*their conf*/, 0 /*ancestor count*/) : Both A and C fit this filter, but B doesn't. So B is out of the game.

Among A and C, they both have 1 change, and 2 inputs. The fee for C is 99 and, A is 100. So on the ground of waste metric, solution C
will be chosen as the final solution.

What are OutputGroups? Why does SRD pick from output groups rather than from UTXOs?

OuputGroups are groups of UTXOs which has the same script pubkeys. I.e., it represents all the UTXOs that have the same addresses. This only happens
in case of address reuse, which is against privacy best practice for Bitcoin.

To defend against accidental address reuse, the wallet prefers to spend all the address-reused UTXOs together, if there are any.

The SRD algorithm randomly chooses from a candidate list. By making it to select from groups, we can ensure all address reused UTXOs are
spent together. If it chose from individual UTXOs, this can't be ensured.

What does calling GroupOutputs() with positive_only=true do (Hint: you may want to review what effective values are)? What could happen if SelectCoinsSRD() was called with all_groups instead of positive_groups?

positive_only = true ensures all the output groups in the candidate list have positive effective value.

effective value = UTXO value in sats - fees required to spend that UTXO.

Thus negative effective value indicates uneconomical UTXOs. Which costs more to spend, than their worth.

If SRD had negative effective values included in the candidate list then it can add more UTXOs than needed to fund the transactions.