Inside Bitcoin
Opening the selected file…
Inside Bitcoin
Opening the selected file…
The code behind the network, with room to understand it.
Release published 2026-10-28 · Snapshot fetched 2026-11-01. Latest stable release at fetch time; development branches and Git history are excluded. Only the selected code window and visible folders load here.
251add_coin(available_coins, *wallet, 9 * CENT + input_fee, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);252add_coin(available_coins, *wallet, 1 * CENT + input_fee, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);254expected_result.Clear();255add_coin(9 * CENT + input_fee, 2, expected_result);256add_coin(1 * CENT + input_fee, 2, expected_result);257CCoinControl coin_control;258coin_control.m_allow_other_inputs = true;259COutput select_coin = available_coins.All().at(1); // pre select 9 coin260coin_control.Select(select_coin.outpoint);261CoinsResult selected_input;262selected_input.Add(OutputType::BECH32, select_coin);263available_coins.Erase({(++available_coins.coins[OutputType::BECH32].begin())->outpoint});264const auto result13 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb);265BOOST_CHECK(EquivalentResult(expected_result, *result13));266expected_attempts = 2;267BOOST_CHECK_MESSAGE(result13->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, result13->GetSelectionsEvaluated()));268}270{271// Test bnb max weight exceeded272// Inputs set [10, 9, 8, 5, 3, 1], Selection Target = 16 and coin 5 exceeding the max weight.274std::unique_ptr<CWallet> wallet = NewWallet(m_node);276CoinsResult available_coins;277add_coin(available_coins, *wallet, 10 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);278add_coin(available_coins, *wallet, 9 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);279add_coin(available_coins, *wallet, 8 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);280add_coin(available_coins, *wallet, 5 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true, /*custom_size=*/MAX_STANDARD_TX_WEIGHT);281add_coin(available_coins, *wallet, 3 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);282add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);284CAmount selection_target = 16 * CENT;285const auto& no_res = SelectCoinsBnB(GroupCoins(available_coins.All(), /*subtract_fee_outputs=*/true),286selection_target, /*cost_of_change=*/0, MAX_STANDARD_TX_WEIGHT);287BOOST_REQUIRE(!no_res);288BOOST_CHECK(util::ErrorString(no_res).original.find("The inputs size exceeds the maximum weight") != std::string::npos);290// Now add same coin value with a good size and check that it gets selected291add_coin(available_coins, *wallet, 5 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);292const auto& res = SelectCoinsBnB(GroupCoins(available_coins.All(), /*subtract_fee_outputs=*/true), selection_target, /*cost_of_change=*/0);294expected_result.Clear();295add_coin(8 * CENT, 2, expected_result);296add_coin(5 * CENT, 2, expected_result);297add_coin(3 * CENT, 2, expected_result);298BOOST_CHECK(EquivalentResult(expected_result, *res));299expected_attempts = 22;300BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));301}302}304BOOST_AUTO_TEST_CASE(bnb_sffo_restriction)305{306// Verify the coin selection process does not produce a BnB solution when SFFO is enabled.307// This is currently problematic because it could require a change output. And BnB is specialized on changeless solutions.308std::unique_ptr<CWallet> wallet = NewWallet(m_node);309WITH_LOCK(wallet->cs_wallet, wallet->SetLastBlockProcessed(300, uint256{})); // set a high block so internal UTXOs are selectable311FastRandomContext rand{};312CoinSelectionParams params{313rand,314/*change_output_size=*/ 31, // unused value, p2wpkh output size (wallet default change type)315/*change_spend_size=*/ 68, // unused value, p2wpkh input size (high-r signature)316/*min_change_target=*/ 0, // dummy, set later317/*effective_feerate=*/ CFeeRate(3000),318/*long_term_feerate=*/ CFeeRate(1000),319/*discard_feerate=*/ CFeeRate(1000),320/*tx_noinputs_size=*/ 0,321/*avoid_partial=*/ false,322};323params.m_subtract_fee_outputs = true;324params.m_change_fee = params.m_effective_feerate.GetFee(params.change_output_size);325params.m_cost_of_change = params.m_discard_feerate.GetFee(params.change_spend_size) + params.m_change_fee;326params.m_min_change_target = params.m_cost_of_change + 1;327// Add spendable coin at the BnB selection upper bound328CoinsResult available_coins;329add_coin(available_coins, *wallet, COIN + params.m_cost_of_change, /*feerate=*/params.m_effective_feerate, /*nAge=*/6, /*fIsFromMe=*/true, /*nInput=*/0, /*spendable=*/true);330add_coin(available_coins, *wallet, 0.5 * COIN + params.m_cost_of_change, /*feerate=*/params.m_effective_feerate, /*nAge=*/6, /*fIsFromMe=*/true, /*nInput=*/0, /*spendable=*/true);331add_coin(available_coins, *wallet, 0.5 * COIN, /*feerate=*/params.m_effective_feerate, /*nAge=*/6, /*fIsFromMe=*/true, /*nInput=*/0, /*spendable=*/true);332// Knapsack will only find a changeless solution on an exact match to the satoshi, SRD doesn’t look for changeless333// If BnB were run, it would produce a single input solution with the best waste score334auto result = WITH_LOCK(wallet->cs_wallet, return SelectCoins(*wallet, available_coins, /*pre_set_inputs=*/{}, COIN, /*coin_control=*/{}, params));335BOOST_CHECK(result.has_value());336BOOST_CHECK_NE(result->GetAlgo(), SelectionAlgorithm::BNB);337BOOST_CHECK(result->GetInputSet().size() == 2);338// We have only considered BnB, SRD, and Knapsack. Test needs to be reevaluated if new algo is added339BOOST_CHECK(result->GetAlgo() == SelectionAlgorithm::SRD || result->GetAlgo() == SelectionAlgorithm::KNAPSACK);340}342BOOST_AUTO_TEST_CASE(knapsack_solver_test)343{344FastRandomContext rand{};345const auto temp1{[&rand](std::vector<OutputGroup>& g, const CAmount& v, CAmount c) { return KnapsackSolver(g, v, c, rand); }};346const auto KnapsackSolver{temp1};347std::unique_ptr<CWallet> wallet = NewWallet(m_node);349CoinsResult available_coins;351// test multiple times to allow for differences in the shuffle order352for (int i = 0; i < RUN_TESTS; i++)353{354available_coins = {};356// with an empty wallet we can't even pay one cent357BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 1 * CENT, CENT));359add_coin(available_coins, *wallet, 1*CENT, CFeeRate(0), 4); // add a new 1 cent coin361// with a new 1 cent coin, we still can't find a mature 1 cent362BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 1 * CENT, CENT));364// but we can find a new 1 cent365const auto result1 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 1 * CENT, CENT);366BOOST_CHECK(result1);367BOOST_CHECK_EQUAL(result1->GetSelectedValue(), 1 * CENT);369add_coin(available_coins, *wallet, 2*CENT); // add a mature 2 cent coin371// we can't make 3 cents of mature coins372BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 3 * CENT, CENT));374// we can make 3 cents of new coins375const auto result2 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 3 * CENT, CENT);376BOOST_CHECK(result2);377BOOST_CHECK_EQUAL(result2->GetSelectedValue(), 3 * CENT);379add_coin(available_coins, *wallet, 5*CENT); // add a mature 5 cent coin,380add_coin(available_coins, *wallet, 10*CENT, CFeeRate(0), 3, true); // a new 10 cent coin sent from one of our own addresses381add_coin(available_coins, *wallet, 20*CENT); // and a mature 20 cent coin383// now we have new: 1+10=11 (of which 10 was self-sent), and mature: 2+5+20=27. total = 38385// we can't make 38 cents only if we disallow new coins:386BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 38 * CENT, CENT));387// we can't even make 37 cents if we don't allow new coins even if they're from us388BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard_extra), 38 * CENT, CENT));389// but we can make 37 cents if we accept new coins from ourself390const auto result3 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_standard), 37 * CENT, CENT);391BOOST_CHECK(result3);392BOOST_CHECK_EQUAL(result3->GetSelectedValue(), 37 * CENT);393// and we can make 38 cents if we accept all new coins394const auto result4 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 38 * CENT, CENT);395BOOST_CHECK(result4);396BOOST_CHECK_EQUAL(result4->GetSelectedValue(), 38 * CENT);398// try making 34 cents from 1,2,5,10,20 - we can't do it exactly399const auto result5 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 34 * CENT, CENT);400BOOST_CHECK(result5);401BOOST_CHECK_EQUAL(result5->GetSelectedValue(), 35 * CENT); // but 35 cents is closest402BOOST_CHECK_EQUAL(result5->GetInputSet().size(), 3U); // the best should be 20+10+5. it's incredibly unlikely the 1 or 2 got included (but possible)404// when we try making 7 cents, the smaller coins (1,2,5) are enough. We should see just 2+5405const auto result6 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 7 * CENT, CENT);406BOOST_CHECK(result6);407BOOST_CHECK_EQUAL(result6->GetSelectedValue(), 7 * CENT);408BOOST_CHECK_EQUAL(result6->GetInputSet().size(), 2U);410// when we try making 8 cents, the smaller coins (1,2,5) are exactly enough.411const auto result7 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 8 * CENT, CENT);412BOOST_CHECK(result7);413BOOST_CHECK(result7->GetSelectedValue() == 8 * CENT);414BOOST_CHECK_EQUAL(result7->GetInputSet().size(), 3U);416// when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10)417const auto result8 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 9 * CENT, CENT);418BOOST_CHECK(result8);419BOOST_CHECK_EQUAL(result8->GetSelectedValue(), 10 * CENT);420BOOST_CHECK_EQUAL(result8->GetInputSet().size(), 1U);422// now clear out the wallet and start again to test choosing between subsets of smaller coins and the next biggest coin423available_coins = {};425add_coin(available_coins, *wallet, 6*CENT);426add_coin(available_coins, *wallet, 7*CENT);427add_coin(available_coins, *wallet, 8*CENT);428add_coin(available_coins, *wallet, 20*CENT);429add_coin(available_coins, *wallet, 30*CENT); // now we have 6+7+8+20+30 = 71 cents total431// check that we have 71 and not 72432const auto result9 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 71 * CENT, CENT);433BOOST_CHECK(result9);434BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 72 * CENT, CENT));436// now try making 16 cents. the best smaller coins can do is 6+7+8 = 21; not as good at the next biggest coin, 20437const auto result10 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 16 * CENT, CENT);438BOOST_CHECK(result10);439BOOST_CHECK_EQUAL(result10->GetSelectedValue(), 20 * CENT); // we should get 20 in one coin440BOOST_CHECK_EQUAL(result10->GetInputSet().size(), 1U);442add_coin(available_coins, *wallet, 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total444// now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, better than the next biggest coin, 20445const auto result11 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 16 * CENT, CENT);446BOOST_CHECK(result11);447BOOST_CHECK_EQUAL(result11->GetSelectedValue(), 18 * CENT); // we should get 18 in 3 coins448BOOST_CHECK_EQUAL(result11->GetInputSet().size(), 3U);450add_coin(available_coins, *wallet, 18*CENT); // now we have 5+6+7+8+18+20+30452// and now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, the same as the next biggest coin, 18453const auto result12 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 16 * CENT, CENT);454BOOST_CHECK(result12);455BOOST_CHECK_EQUAL(result12->GetSelectedValue(), 18 * CENT); // we should get 18 in 1 coin456BOOST_CHECK_EQUAL(result12->GetInputSet().size(), 1U); // because in the event of a tie, the biggest coin wins458// now try making 11 cents. we should get 5+6459const auto result13 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 11 * CENT, CENT);460BOOST_CHECK(result13);461BOOST_CHECK_EQUAL(result13->GetSelectedValue(), 11 * CENT);462BOOST_CHECK_EQUAL(result13->GetInputSet().size(), 2U);464// check that the smallest bigger coin is used465add_coin(available_coins, *wallet, 1*COIN);466add_coin(available_coins, *wallet, 2*COIN);467add_coin(available_coins, *wallet, 3*COIN);468add_coin(available_coins, *wallet, 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents469const auto result14 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 95 * CENT, CENT);470BOOST_CHECK(result14);471BOOST_CHECK_EQUAL(result14->GetSelectedValue(), 1 * COIN); // we should get 1 BTC in 1 coin472BOOST_CHECK_EQUAL(result14->GetInputSet().size(), 1U);474const auto result15 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 195 * CENT, CENT);475BOOST_CHECK(result15);476BOOST_CHECK_EQUAL(result15->GetSelectedValue(), 2 * COIN); // we should get 2 BTC in 1 coin477BOOST_CHECK_EQUAL(result15->GetInputSet().size(), 1U);479// empty the wallet and start again, now with fractions of a cent, to test small change avoidance481available_coins = {};482add_coin(available_coins, *wallet, CENT * 1 / 10);483add_coin(available_coins, *wallet, CENT * 2 / 10);484add_coin(available_coins, *wallet, CENT * 3 / 10);485add_coin(available_coins, *wallet, CENT * 4 / 10);486add_coin(available_coins, *wallet, CENT * 5 / 10);488// try making 1 * CENT from the 1.5 * CENT489// we'll get change smaller than CENT whatever happens, so can expect CENT exactly490const auto result16 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), CENT, CENT);491BOOST_CHECK(result16);492BOOST_CHECK_EQUAL(result16->GetSelectedValue(), CENT);494// but if we add a bigger coin, small change is avoided495add_coin(available_coins, *wallet, 1111*CENT);497// try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5498const auto result17 = KnapsackSolver(KnapsackGroupOutputs(available_coins, *wallet, filter_confirmed), 1 * CENT, CENT);499BOOST_CHECK(result17);500BOOST_CHECK_EQUAL(result17->GetSelectedValue(), 1 * CENT); // we should get the exact amount
Independent explanations by MyBitcoinExplorer. Not affiliated with or endorsed by Bitcoin Core. Guides are educational and do not replace the source or its tests.
Bitcoin Core source © its contributors, distributed under the MIT license. Original notices and bundled third-party licenses are retained in the source tree.