Inside Bitcoin

751        // Waste with change is the change cost and difference between fee and long term fee
752        // With long term fee greater than fee, waste should be less than when long term fee is less than fee
753        SelectionResult selection3{target, SelectionAlgorithm::MANUAL};
754        add_coin(1 * COIN, 1, selection3, fee, fee + fee_diff);
755        add_coin(2 * COIN, 2, selection3, fee, fee + fee_diff);
756        selection3.RecalculateWaste(min_viable_change, change_cost, change_fee);
757        BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, selection3.GetWaste());
758        BOOST_CHECK_LT(selection3.GetWaste(), selection1.GetWaste());
759    }
760
761    {
762        // Waste without change is the excess and difference between fee and long term fee
763        SelectionResult selection_nochange1{exact_target - excess, SelectionAlgorithm::MANUAL};
764        add_coin(1 * COIN, 1, selection_nochange1, fee, fee - fee_diff);
765        add_coin(2 * COIN, 2, selection_nochange1, fee, fee - fee_diff);
766        selection_nochange1.RecalculateWaste(min_viable_change, change_cost, change_fee);
767        BOOST_CHECK_EQUAL(fee_diff * 2 + excess, selection_nochange1.GetWaste());
768
769        // Waste without change is the excess and difference between fee and long term fee
770        // With long term fee greater than fee, waste should be less than when long term fee is less than fee
771        SelectionResult selection_nochange2{exact_target - excess, SelectionAlgorithm::MANUAL};
772        add_coin(1 * COIN, 1, selection_nochange2, fee, fee + fee_diff);
773        add_coin(2 * COIN, 2, selection_nochange2, fee, fee + fee_diff);
774        selection_nochange2.RecalculateWaste(min_viable_change, change_cost, change_fee);
775        BOOST_CHECK_EQUAL(fee_diff * -2 + excess, selection_nochange2.GetWaste());
776        BOOST_CHECK_LT(selection_nochange2.GetWaste(), selection_nochange1.GetWaste());
777    }
778
779    {
780        // Waste with change and fee == long term fee is just cost of change
781        SelectionResult selection{target, SelectionAlgorithm::MANUAL};
782        add_coin(1 * COIN, 1, selection, fee, fee);
783        add_coin(2 * COIN, 2, selection, fee, fee);
784        selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
785        BOOST_CHECK_EQUAL(change_cost, selection.GetWaste());
786    }
787
788    {
789        // Waste without change and fee == long term fee is just the excess
790        SelectionResult selection{exact_target - excess, SelectionAlgorithm::MANUAL};
791        add_coin(1 * COIN, 1, selection, fee, fee);
792        add_coin(2 * COIN, 2, selection, fee, fee);
793        selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
794        BOOST_CHECK_EQUAL(excess, selection.GetWaste());
795    }
796
797    {
798        // Waste is 0 when fee == long_term_fee, no change, and no excess
799        SelectionResult selection{exact_target, SelectionAlgorithm::MANUAL};
800        add_coin(1 * COIN, 1, selection, fee, fee);
801        add_coin(2 * COIN, 2, selection, fee, fee);
802        selection.RecalculateWaste(min_viable_change, change_cost , change_fee);
803        BOOST_CHECK_EQUAL(0, selection.GetWaste());
804    }
805
806    {
807        // Waste is 0 when (fee - long_term_fee) == (-cost_of_change), and no excess
808        SelectionResult selection{target, SelectionAlgorithm::MANUAL};
809        add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
810        add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
811        selection.RecalculateWaste(min_viable_change, /*change_cost=*/fee_diff * 2, change_fee);
812        BOOST_CHECK_EQUAL(0, selection.GetWaste());
813    }
814
815    {
816        // Waste is 0 when (fee - long_term_fee) == (-excess), no change cost
817        const CAmount new_target{exact_target - /*excess=*/fee_diff * 2};
818        SelectionResult selection{new_target, SelectionAlgorithm::MANUAL};
819        add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
820        add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
821        selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
822        BOOST_CHECK_EQUAL(0, selection.GetWaste());
823    }
824
825    {
826        // Negative waste when the long term fee is greater than the current fee and the selected value == target
827        SelectionResult selection{exact_target, SelectionAlgorithm::MANUAL};
828        const CAmount target_waste1{-2 * fee_diff}; // = (2 * fee) - (2 * (fee + fee_diff))
829        add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
830        add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
831        selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
832        BOOST_CHECK_EQUAL(target_waste1, selection.GetWaste());
833    }
834
835    {
836        // Negative waste when the long term fee is greater than the current fee and change_cost < - (inputs * (fee - long_term_fee))
837        SelectionResult selection{target, SelectionAlgorithm::MANUAL};
838        const CAmount large_fee_diff{90};
839        const CAmount target_waste2{-2 * large_fee_diff + change_cost};
840        // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost
841        // = (2 * 100) - (2 * (100 + 90)) + 125
842        // = 200 - 380 + 125 = -55
843        assert(target_waste2 == -55);
844        add_coin(1 * COIN, 1, selection, fee, fee + large_fee_diff);
845        add_coin(2 * COIN, 2, selection, fee, fee + large_fee_diff);
846        selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
847        BOOST_CHECK_EQUAL(target_waste2, selection.GetWaste());
848    }
849}
850
851
852BOOST_AUTO_TEST_CASE(bump_fee_test)
853{
854    const CAmount fee{100};
855    const CAmount min_viable_change{200};
856    const CAmount change_cost{125};
857    const CAmount change_fee{35};
858    const CAmount fee_diff{40};
859    const CAmount target{2 * COIN};
860
861    {
862        SelectionResult selection{target, SelectionAlgorithm::MANUAL};
863        add_coin(1 * COIN, 1, selection, /*fee=*/fee, /*long_term_fee=*/fee + fee_diff);
864        add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
865        const std::vector<std::shared_ptr<COutput>> inputs = selection.GetShuffledInputVector();
866
867        for (size_t i = 0; i < inputs.size(); ++i) {
868            inputs[i]->ApplyBumpFee(20*(i+1));
869        }
870
871        selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
872        CAmount expected_waste = fee_diff * -2 + change_cost + /*bump_fees=*/60;
873        BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste());
874
875        selection.SetBumpFeeDiscount(30);
876        selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
877        expected_waste = fee_diff * -2 + change_cost + /*bump_fees=*/60 - /*group_discount=*/30;
878        BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste());
879    }
880
881    {
882        // Test with changeless transaction
883        //
884        // Bump fees and excess both contribute fully to the waste score,
885        // therefore, a bump fee group discount will not change the waste
886        // score as long as we do not create change in both instances.
887        CAmount changeless_target = 3 * COIN - 2 * fee - 100;
888        SelectionResult selection{changeless_target, SelectionAlgorithm::MANUAL};
889        add_coin(1 * COIN, 1, selection, /*fee=*/fee, /*long_term_fee=*/fee + fee_diff);
890        add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
891        const std::vector<std::shared_ptr<COutput>> inputs = selection.GetShuffledInputVector();
892
893        for (size_t i = 0; i < inputs.size(); ++i) {
894            inputs[i]->ApplyBumpFee(20*(i+1));
895        }
896
897        selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
898        CAmount expected_waste = fee_diff * -2 + /*bump_fees=*/60 + /*excess = 100 - bump_fees*/40;
899        BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste());
900
901        selection.SetBumpFeeDiscount(30);
902        selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
903        expected_waste = fee_diff * -2 + /*bump_fees=*/60 - /*group_discount=*/30 + /*excess = 100 - bump_fees + group_discount*/70;
904        BOOST_CHECK_EQUAL(expected_waste, selection.GetWaste());
905    }
906}
907
908BOOST_AUTO_TEST_CASE(effective_value_test)
909{
910    const int input_bytes = 148;
911    const CFeeRate feerate(1000);
912    const CAmount nValue = 10000;
913    const int nInput = 0;
914
915    CMutableTransaction tx;
916    tx.vout.resize(1);
917    tx.vout[nInput].nValue = nValue;
918
919    // standard case, pass feerate in constructor
920    COutput output1(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, input_bytes, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, feerate);
921    const CAmount expected_ev1 = 9852; // 10000 - 148
922    BOOST_CHECK_EQUAL(output1.GetEffectiveValue(), expected_ev1);
923
924    // input bytes unknown (input_bytes = -1), pass feerate in constructor
925    COutput output2(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/ false, feerate);
926    BOOST_CHECK_EQUAL(output2.GetEffectiveValue(), nValue); // The effective value should be equal to the absolute value if input_bytes is -1
927
928    // negative effective value, pass feerate in constructor
929    COutput output3(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, input_bytes, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, CFeeRate(100000));
930    const CAmount expected_ev3 = -4800; // 10000 - 14800
931    BOOST_CHECK_EQUAL(output3.GetEffectiveValue(), expected_ev3);
932
933    // standard case, pass fees in constructor
934    const CAmount fees = 148;
935    COutput output4(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, input_bytes, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, fees);
936    BOOST_CHECK_EQUAL(output4.GetEffectiveValue(), expected_ev1);
937
938    // input bytes unknown (input_bytes = -1), pass fees in constructor
939    COutput output5(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, /*fees=*/0);
940    BOOST_CHECK_EQUAL(output5.GetEffectiveValue(), nValue); // The effective value should be equal to the absolute value if input_bytes is -1
941}
942
943static util::Result<SelectionResult> CoinGrinder(const CAmount& target,
944                                                    const CoinSelectionParams& cs_params,
945                                                    const node::NodeContext& m_node,
946                                                    int max_selection_weight,
947                                                    std::function<CoinsResult(CWallet&)> coin_setup)
948{
949    std::unique_ptr<CWallet> wallet = NewWallet(m_node);
950    CoinEligibilityFilter filter(0, 0, 0); // accept all coins without ancestors
951    Groups group = GroupOutputs(*wallet, coin_setup(*wallet), cs_params, {{filter}})[filter].all_groups;
952    return CoinGrinder(group.positive_group, target, cs_params.m_min_change_target, max_selection_weight);
953}
954
955BOOST_AUTO_TEST_CASE(coin_grinder_tests)
956{
957    // Test Coin Grinder:
958    // 1) Insufficient funds, select all provided coins and fail.
959    // 2) Exceeded max weight, coin selection always surpasses the max allowed weight.
960    // 3) Select coins without surpassing the max weight (some coins surpasses the max allowed weight, some others not)
961    // 4) Test that two less valuable UTXOs with a combined lower weight are preferred over a more valuable heavier UTXO
962    // 5) Test finding a solution in a UTXO pool with mixed weights
963    // 6) Test that the lightest solution among many clones is found
964    // 7) Test that lots of tiny UTXOs can be skipped if they are too heavy while there are enough funds in lookahead
965
966    FastRandomContext rand;
967    CoinSelectionParams dummy_params{ // Only used to provide the 'avoid_partial' flag.
968            rand,
969            /*change_output_size=*/34,
970            /*change_spend_size=*/68,
971            /*min_change_target=*/CENT,
972            /*effective_feerate=*/CFeeRate(5000),
973            /*long_term_feerate=*/CFeeRate(2000),
974            /*discard_feerate=*/CFeeRate(1000),
975            /*tx_noinputs_size=*/10 + 34, // static header size + output size
976            /*avoid_partial=*/false,
977    };
978
979    {
980        // #########################################################
981        // 1) Insufficient funds, select all provided coins and fail
982        // #########################################################
983        CAmount target = 49.5L * COIN;
984        int max_selection_weight = 10'000; // high enough to not fail for this reason.
985        const auto& res = CoinGrinder(target, dummy_params, m_node, max_selection_weight, [&](CWallet& wallet) {
986            CoinsResult available_coins;
987            for (int j = 0; j < 10; ++j) {
988                add_coin(available_coins, wallet, CAmount(1 * COIN));
989                add_coin(available_coins, wallet, CAmount(2 * COIN));
990            }
991            return available_coins;
992        });
993        BOOST_CHECK(!res);
994        BOOST_CHECK(util::ErrorString(res).empty()); // empty means "insufficient funds"
995    }
996
997    {
998        // ###########################
999        // 2) Test max weight exceeded
1000        // ###########################