The Strategy of Selection: Introduction to Coin Selection Algorithms

8. The Strategy of Selection: Introduction to Coin Selection Algorithms

Once the "Inventory Report" is complete, the wallet faces its most difficult challenge: Coin Selection. If you want to send 0.5 BTC, and you have 100 different "Pieces of Gold" (UTXOs) totaling 10 BTC, which specific pieces should you use? This is not just a math problem; it is a "Strategy Puzzle." The coins you pick will determine the "Size" of your transaction (and thus the fee), the amount of "Change" you receive back, and the "Privacy" of your financial trail. In Bitcoin Core, this is handled by several sophisticated algorithms working in concert. It is the "Strategy of the Sovereign."

The goal of coin selection is to find the "Best" combination of inputs to satisfy a payment. But "Best" means different things in different contexts. Sometimes "Best" means "Smallest Fee." Sometimes it means "No Change Output" (to save space). Sometimes it means "Maximum Privacy." Bitcoin Core uses a "Hierarchy of Algorithms" to try and satisfy all these goals. It starts with the most efficient and falls back to more robust methods if necessary.

Analyzing the Hierarchy of Choice: AttemptSelection

In the source code (src/wallet/spend.cpp), we can see how the wallet "Cycles" through different strategies. It doesn't just pick one; it tries them all and picks the "Winner" based on a "Waste Metric."

/**
 * This function "Attempts" different coin selection strategies to find the best result.
 */
util::Result<SelectionResult> ChooseSelectionResult(...)
{
    std::vector<SelectionResult> results;

    // 1. Try "Branch and Bound" (BnB).
    // Goal: Find a "Perfect Match" that results in ZERO change.
    if (auto bnb_result = SelectCoinsBnB(...)) {
        results.push_back(*bnb_result);
    }

    // 2. Try "Knapsack Solver."
    // Goal: Solve the "Subset Sum" problem (Robust but may create change).
    if (auto knapsack_result = KnapsackSolver(...)) {
        results.push_back(*knapsack_result);
    }

    // 3. Try "Single Random Draw" (SRD).
    // Goal: A fast, simple fallback that adds privacy through randomness.
    if (auto srd_result = SelectCoinsSRD(...)) {
        results.push_back(*srd_result);
    }

    // 4. We pick the "Winner" with the lowest "Waste."
    return *std::min_element(results.begin(), results.end(), [](const auto& a, const auto& b) {
        return a.GetWaste() < b.GetWaste();
    });
}

Explaining the Strategy: The Shopping Trip

• "No Change" (BnB): Imagine you are buying a coffee for $4.25. If you have a $5 bill, you will get $0.75 in change. That change is a "New Coin" that you have to track. But if you have exactly four $1 bills and one quarter in your pocket, you can pay "Exactly." This is what BnB tries to do. It looks through your pocket to see if you have the "Exact Change." This is the "Cleanest" way to pay because it doesn't create any messy leftovers.

• "Waste Metric": How do you compare a "Small Transaction with Change" to a "Large Transaction without Change"? Bitcoin Core calculates a "Waste Metric." This metric accounts for the "Fee" you are paying now, the "Future Fee" you will have to pay to spend the change, and the "Privacy Loss" of creating new coins. The algorithm with the "Lowest Waste" wins. It is the "Economic Wisdom" of the computer.

• "Fallback Logic": The BnB algorithm is very "Picky." It will only work if it finds a perfect match. If your pocket is full of random coins, it will likely fail. This is why we have the "Knapsack" and "SRD" fallbacks. They are less efficient, but they are "Guaranteed" to find a solution as long as you have enough money. It is the "Resilience of the Bank."

The Sovereign's Choice: Automated vs. Manual

By default, Bitcoin Core handles all of this automatically. But as a "Sovereign Architect," you can override this logic using "Coin Control." You can manually pick the "Pieces of Gold" you want to spend, and the computer will build the transaction exactly as you commanded. This "Manual Override" is the ultimate power of the wallet. It allows you to ignore the "Waste Metric" in favor of your own personal "Privacy Metric." You are the "General of the Coins," the one who makes the final decision on the field of the ledger.