Inside Bitcoin

1001        CAmount target = 29.5L * COIN;
1002        int max_selection_weight = 3000;
1003        const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
1004            CoinsResult available_coins;
1005            for (int j = 0; j < 10; ++j) {
1006                add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true);
1007                add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true);
1008            }
1009            return available_coins;
1010        });
1011        BOOST_CHECK(!res);
1012        BOOST_CHECK(util::ErrorString(res).original.find("The inputs size exceeds the maximum weight") != std::string::npos);
1013    }
1014
1015    {
1016        // ###############################################################################################################
1017        // 3) Test that the lowest-weight solution is found when some combinations would exceed the allowed weight
1018        // ################################################################################################################
1019        CAmount target = 25.33L * COIN;
1020        int max_selection_weight = 10'000; // WU
1021        const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
1022            CoinsResult available_coins;
1023            for (int j = 0; j < 60; ++j) { // 60 UTXO --> 19,8 BTC total --> 60 × 272 WU = 16320 WU
1024                add_coin(available_coins, wallet, CAmount(0.33 * COIN), CFeeRate(5000), 144, false, 0, true);
1025            }
1026            for (int i = 0; i < 10; i++) { // 10 UTXO --> 20 BTC total --> 10 × 272 WU = 2720 WU
1027                add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true);
1028            }
1029            return available_coins;
1030        });
1031        SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
1032        for (int i = 0; i < 10; ++i) {
1033            add_coin(2 * COIN, i, expected_result);
1034        }
1035        for (int j = 0; j < 17; ++j) {
1036            add_coin(0.33 * COIN, j + 10, expected_result);
1037        }
1038        BOOST_CHECK(EquivalentResult(expected_result, *res));
1039        // Demonstrate how following improvements reduce iteration count and catch any regressions in the future.
1040        size_t expected_attempts = 37;
1041        BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1042    }
1043
1044    {
1045        // #################################################################################################################
1046        // 4) Test that two less valuable UTXOs with a combined lower weight are preferred over a more valuable heavier UTXO
1047        // #################################################################################################################
1048        CAmount target =  1.9L * COIN;
1049        int max_selection_weight = 400'000; // WU
1050        const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
1051            CoinsResult available_coins;
1052            add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true, 148);
1053            add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 68);
1054            add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 68);
1055            return available_coins;
1056        });
1057        SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
1058        add_coin(1 * COIN, 1, expected_result);
1059        add_coin(1 * COIN, 2, expected_result);
1060        BOOST_CHECK(EquivalentResult(expected_result, *res));
1061        // Demonstrate how following improvements reduce iteration count and catch any regressions in the future.
1062        size_t expected_attempts = 3;
1063        BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1064    }
1065
1066    {
1067        // ###############################################################################################################
1068        // 5) Test finding a solution in a UTXO pool with mixed weights
1069        // ################################################################################################################
1070        CAmount target = 30L * COIN;
1071        int max_selection_weight = 400'000; // WU
1072        const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
1073            CoinsResult available_coins;
1074            for (int j = 0; j < 5; ++j) {
1075                // Add heavy coins {3, 6, 9, 12, 15}
1076                add_coin(available_coins, wallet, CAmount((3 + 3 * j) * COIN), CFeeRate(5000), 144, false, 0, true, 350);
1077                // Add medium coins {2, 5, 8, 11, 14}
1078                add_coin(available_coins, wallet, CAmount((2 + 3 * j) * COIN), CFeeRate(5000), 144, false, 0, true, 250);
1079                // Add light coins {1, 4, 7, 10, 13}
1080                add_coin(available_coins, wallet, CAmount((1 + 3 * j) * COIN), CFeeRate(5000), 144, false, 0, true, 150);
1081            }
1082            return available_coins;
1083        });
1084        BOOST_CHECK(res);
1085        SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
1086        add_coin(14 * COIN, 1, expected_result);
1087        add_coin(13 * COIN, 2, expected_result);
1088        add_coin(4 * COIN, 3, expected_result);
1089        BOOST_CHECK(EquivalentResult(expected_result, *res));
1090        // Demonstrate how following improvements reduce iteration count and catch any regressions in the future.
1091        size_t expected_attempts = 92;
1092        BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1093    }
1094
1095    {
1096        // #################################################################################################################
1097        // 6) Test that the lightest solution among many clones is found
1098        // #################################################################################################################
1099        CAmount target =  9.9L * COIN;
1100        int max_selection_weight = 400'000; // WU
1101        const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
1102            CoinsResult available_coins;
1103            // Expected Result: 4 + 3 + 2 + 1 = 10 BTC at 400 vB
1104            add_coin(available_coins, wallet, CAmount(4 * COIN), CFeeRate(5000), 144, false, 0, true, 100);
1105            add_coin(available_coins, wallet, CAmount(3 * COIN), CFeeRate(5000), 144, false, 0, true, 100);
1106            add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(5000), 144, false, 0, true, 100);
1107            add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 100);
1108            // Distracting clones:
1109            for (int j = 0; j < 100; ++j) {
1110                add_coin(available_coins, wallet, CAmount(8 * COIN), CFeeRate(5000), 144, false, 0, true, 1000);
1111            }
1112            for (int j = 0; j < 100; ++j) {
1113                add_coin(available_coins, wallet, CAmount(7 * COIN), CFeeRate(5000), 144, false, 0, true, 800);
1114            }
1115            for (int j = 0; j < 100; ++j) {
1116                add_coin(available_coins, wallet, CAmount(6 * COIN), CFeeRate(5000), 144, false, 0, true, 600);
1117            }
1118            for (int j = 0; j < 100; ++j) {
1119                add_coin(available_coins, wallet, CAmount(5 * COIN), CFeeRate(5000), 144, false, 0, true, 400);
1120            }
1121            return available_coins;
1122        });
1123        SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
1124        add_coin(4 * COIN, 0, expected_result);
1125        add_coin(3 * COIN, 0, expected_result);
1126        add_coin(2 * COIN, 0, expected_result);
1127        add_coin(1 * COIN, 0, expected_result);
1128        BOOST_CHECK(EquivalentResult(expected_result, *res));
1129        // Demonstrate how following improvements reduce iteration count and catch any regressions in the future.
1130        size_t expected_attempts = 38;
1131        BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1132    }
1133
1134    {
1135        // #################################################################################################################
1136        // 7) Test that lots of tiny UTXOs can be skipped if they are too heavy while there are enough funds in lookahead
1137        // #################################################################################################################
1138        CAmount target =  1.9L * COIN;
1139        int max_selection_weight = 40000; // WU
1140        const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
1141            CoinsResult available_coins;
1142            add_coin(available_coins, wallet, CAmount(1.8 * COIN), CFeeRate(5000), 144, false, 0, true, 2500);
1143            add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 1000);
1144            add_coin(available_coins, wallet, CAmount(1 * COIN), CFeeRate(5000), 144, false, 0, true, 1000);
1145            for (int j = 0; j < 100; ++j) {
1146                // make a 100 unique coins only differing by one sat
1147                add_coin(available_coins, wallet, CAmount(0.01 * COIN + j), CFeeRate(5000), 144, false, 0, true, 110);
1148            }
1149            return available_coins;
1150        });
1151        SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
1152        add_coin(1 * COIN, 1, expected_result);
1153        add_coin(1 * COIN, 2, expected_result);
1154        BOOST_CHECK(EquivalentResult(expected_result, *res));
1155        // Demonstrate how following improvements reduce iteration count and catch any regressions in the future.
1156        size_t expected_attempts = 7;
1157        BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1158    }
1159
1160    {
1161        // #################################################################################################################
1162        // 8) Test input set that has a solution will not find a solution before reaching the attempt limit
1163        // #################################################################################################################
1164        CAmount target = 8 * COIN;
1165        int max_selection_weight = 3200; // WU
1166        dummy_params.m_min_change_target = 0;
1167        const auto& result_a = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
1168            CoinsResult doppelgangers;
1169            for (int i = 0; i < 18; ++i) {
1170                add_coin(doppelgangers, wallet, CAmount(1 * COIN + i), CFeeRate(0), 144, false, 0, true, 96 + i);
1171            }
1172            return doppelgangers;
1173        });
1174        BOOST_CHECK(result_a);
1175        SelectionResult expected_result(CAmount(0), SelectionAlgorithm::CG);
1176        for (int i = 0; i < 8; ++i) {
1177          add_coin(1 * COIN + i, 0, expected_result);
1178        }
1179        BOOST_CHECK(EquivalentResult(expected_result, *result_a));
1180        // Demonstrate a solution is found before the attempts limit is reached.
1181        size_t expected_attempts = 87'525;
1182        BOOST_CHECK_MESSAGE(result_a->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, result_a->GetSelectionsEvaluated()));
1183
1184        // Adding one more doppelganger causes the attempt limit to be reached before finding a solution.
1185        const auto& result_b = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
1186            CoinsResult doppelgangers;
1187            for (int i = 0; i < 19; ++i) {
1188                add_coin(doppelgangers, wallet, CAmount(1 * COIN + i), CFeeRate(0), 144, false, 0, true, 96 + i);
1189            }
1190            return doppelgangers;
1191        });
1192        BOOST_CHECK(!result_b);
1193    }
1194}
1195
1196static util::Result<SelectionResult> select_coins(const CAmount& target, const CoinSelectionParams& cs_params, const CCoinControl& cc, std::function<CoinsResult(CWallet&)> coin_setup, const node::NodeContext& m_node)
1197{
1198    std::unique_ptr<CWallet> wallet = NewWallet(m_node);
1199    auto available_coins = coin_setup(*wallet);
1200
1201    LOCK(wallet->cs_wallet);
1202    auto result = SelectCoins(*wallet, available_coins, /*pre_set_inputs=*/ {}, target, cc, cs_params);
1203    if (result) {
1204        const auto signedTxSize = 10 + 34 + 68 * result->GetInputSet().size(); // static header size + output size + inputs size (P2WPKH)
1205        BOOST_CHECK_LE(signedTxSize * WITNESS_SCALE_FACTOR, MAX_STANDARD_TX_WEIGHT);
1206
1207        BOOST_CHECK_GE(result->GetSelectedValue(), target);
1208    }
1209    return result;
1210}
1211
1212static bool has_coin(const OutputSet& set, CAmount amount)
1213{
1214    return std::any_of(set.begin(), set.end(), [&](const auto& coin) { return coin->GetEffectiveValue() == amount; });
1215}
1216
1217BOOST_AUTO_TEST_CASE(check_max_selection_weight)
1218{
1219    const CAmount target = 49.5L * COIN;
1220    CCoinControl cc;
1221
1222    FastRandomContext rand;
1223    CoinSelectionParams cs_params{
1224        rand,
1225        /*change_output_size=*/34,
1226        /*change_spend_size=*/68,
1227        /*min_change_target=*/CENT,
1228        /*effective_feerate=*/CFeeRate(0),
1229        /*long_term_feerate=*/CFeeRate(0),
1230        /*discard_feerate=*/CFeeRate(0),
1231        /*tx_noinputs_size=*/10 + 34, // static header size + output size
1232        /*avoid_partial=*/false,
1233    };
1234
1235    int max_weight = MAX_STANDARD_TX_WEIGHT - WITNESS_SCALE_FACTOR * (cs_params.tx_noinputs_size + cs_params.change_output_size);
1236    {
1237        // Scenario 1:
1238        // The actor starts with 1x 50.0 BTC and 1515x 0.033 BTC (~100.0 BTC total) unspent outputs
1239        // Then tries to spend 49.5 BTC
1240        // The 50.0 BTC output should be selected, because the transaction would otherwise be too large
1241
1242        // Perform selection
1243
1244        const auto result = select_coins(
1245            target, cs_params, cc, [&](CWallet& wallet) {
1246                CoinsResult available_coins;
1247                for (int j = 0; j < 1515; ++j) {
1248                    add_coin(available_coins, wallet, CAmount(0.033 * COIN), CFeeRate(0), 144, false, 0, true);
1249                }
1250