The Perfect Fit: The Branch and Bound (BnB) Algorithm Explained

9. The Perfect Fit: The Branch and Bound (BnB) Algorithm Explained

The "Gold Standard" of coin selection is the Branch and Bound (BnB) algorithm. Developed by the legendary Bitcoin researcher Mark Erhardt (Murch), BnB is designed with one primary goal: Avoid Change. In a traditional transaction, you spend some coins and receive "Change" back to a new address. This change output takes up space in the blockchain (costing you fees) and "Links" your addresses together (hurting your privacy). BnB searches your inventory for a combination of UTXOs that exactly matches the amount you want to send plus the fee. If it finds such a combination, you receive NO change. It is the "Perfect Fit" of the forge.

BnB is a "Search Algorithm." It treats your UTXOs like a "Binary Tree." At each step, it asks: "Should I include this coin or not?" It explores these "Branches" until it finds a set that hits the "Target Range." If a branch becomes "Too Heavy," it "Bounds" (stops) that search and tries another path. It is the "Mathematical Precision" of the internal bank.

Analyzing the Search Engine: SelectCoinsBnB

In the source code (src/wallet/coinselection.cpp), we can see the "Inner Workings" of this search. It is a "Depth-First Search" that is limited by a "Try Count" to ensure it doesn't slow down your computer.

/**
 * This is the core logic of the Branch and Bound search.
 */
util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, ...)
{
    // 1. Sort the coins from "Largest" to "Smallest."
    std::sort(utxo_pool.begin(), utxo_pool.end(), descending);

    // 2. Start the search. We allow up to 100,000 "Guesses."
    for (size_t curr_try = 0; curr_try < 100000; ++curr_try) {

        // 3. If the current total is within the "Target Range"... SUCCESS!
        if (curr_value >= selection_target && curr_value <= selection_target + cost_of_change) {
            // We found a perfect match. No change needed.
            return result;
        }

        // 4. "Branching": Should we add the next coin?
        if (curr_value + next_coin <= target_upper_bound) {
            // Add the coin and keep moving "Forward."
            curr_value += next_coin;
        } else {
            // "Bounding": This path is too heavy. Move "Backwards" and try another branch.
            backtrack = true;
        }
    }
}

Explaining the Search: The Suitcase Puzzle

• cost_of_change: Why do we say "Exactly" if we have a "Range"? Because creating a change output is not "Free." You have to pay the miners to include it in the block, and you'll have to pay again to spend it later. cost_of_change is the total price of "Making and Spending" that leftover piece of gold. If the "Overpayment" in your transaction is LESS than the cost of change, it's actually "Cheaper" to just give the extra money to the miners as a tip. BnB tries to find a combination where the overpayment is tiny. It is the "Efficiency of the Forge."

• 100,000 Guesses: If you have 1,000 coins, there are more combinations than there are atoms in the universe. The computer cannot check them all. This limit is the "Patience of the Node." If it can't find a perfect match quickly, it gives up and lets the "Knapsack" algorithm handle it. This ensures your wallet remains "Snappy" even if your inventory is massive. It is the "Practicality of the Core."

• descending (The Sort): By starting with the "Biggest" coins, the algorithm can "Fail Fast." If the three biggest coins are already over the limit, it knows it doesn't need to check any combinations involving those three. This "Pruning" is what makes BnB so incredibly fast. It is the "Strategy of the Search."

The "Changeless" Advantage

A changeless transaction is a "Privacy Masterpiece." To an outside observer looking at the blockchain, a transaction with two outputs (Recipient and Change) clearly shows that money is moving from one person to another. But a transaction with only ONE output is "Ambiguous." Did you send the whole amount to someone else? Or did you move the whole amount to another wallet you own? By avoiding change, you "Muddy the Water" of the ledger. You are the "Master of the Fit," protecting your wealth through the power of "Mathematical Perfection."