20#include <boost/test/unit_test.hpp>
31#define RANDOM_REPEATS 5
33typedef std::set<std::shared_ptr<COutput>>
CoinSet;
43 tx.
vout.resize(nInput + 1);
44 tx.
vout[nInput].nValue = nValue;
48 group.Insert(std::make_shared<COutput>(output), 0, 0);
55 tx.
vout.resize(nInput + 1);
56 tx.
vout[nInput].nValue = nValue;
58 std::shared_ptr<COutput> coin = std::make_shared<COutput>(
COutPoint(tx.
GetHash(), nInput), tx.
vout.at(nInput), 1, 148,
true,
true, 0,
false,
fee);
60 group.Insert(coin, 0, 0);
61 coin->long_term_fee = long_term_fee;
69 tx.
vout.resize(nInput + 1);
70 tx.
vout[nInput].nValue = nValue;
80 const auto& txout = wtx.
tx->vout.at(nInput);
81 available_coins.
Add(
OutputType::BECH32, {
COutPoint(wtx.
GetHash(), nInput), txout, nAge, custom_size == 0 ?
CalculateMaximumSignedInputSize(txout, &
wallet,
nullptr) : custom_size,
true,
true, wtx.
GetTxTime(), fIsFromMe, feerate});
89 return res ? std::optional<SelectionResult>(*res) : std::nullopt;
95 return res ? std::optional<SelectionResult>(*res) : std::nullopt;
102 std::vector<CAmount> a_amts;
103 std::vector<CAmount> b_amts;
105 a_amts.push_back(coin->txout.nValue);
108 b_amts.push_back(coin->txout.nValue);
110 std::sort(a_amts.begin(), a_amts.end());
111 std::sort(b_amts.begin(), b_amts.end());
113 std::pair<std::vector<CAmount>::iterator, std::vector<CAmount>::iterator>
ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
114 return ret.first == a_amts.end() &&
ret.second == b_amts.end();
121 [](
const std::shared_ptr<COutput>& a,
const std::shared_ptr<COutput>& b) {
122 return a->outpoint == b->outpoint;
127inline std::vector<OutputGroup>&
GroupCoins(
const std::vector<COutput>& available_coins,
bool subtract_fee_outputs =
false)
129 static std::vector<OutputGroup> static_groups;
130 static_groups.clear();
131 for (
auto& coin : available_coins) {
132 static_groups.emplace_back();
134 group.Insert(std::make_shared<COutput>(coin), 0, 0);
135 group.m_subtract_fee_outputs = subtract_fee_outputs;
137 return static_groups;
155 static_groups =
GroupOutputs(
wallet, available_coins, coin_selection_params, {{filter}})[filter];
164 wallet->SetupDescriptorScriptPubKeyMans();
173 std::vector<COutput> utxo_pool;
192 coin_selection_params_bnb.m_change_fee = coin_selection_params_bnb.m_effective_feerate.
GetFee(coin_selection_params_bnb.change_output_size);
193 coin_selection_params_bnb.m_cost_of_change = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_spend_size) + coin_selection_params_bnb.m_change_fee;
194 coin_selection_params_bnb.min_viable_change = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_spend_size);
201 add_coin(available_coins, *
wallet, 1, coin_selection_params_bnb.m_effective_feerate);
202 available_coins.
All().at(0).input_bytes = 40;
206 available_coins.
Clear();
207 add_coin(available_coins, *
wallet, 1 *
CENT, coin_selection_params_bnb.m_effective_feerate);
208 available_coins.
All().at(0).input_bytes = 40;
219 coin_selection_params_bnb.m_effective_feerate =
CFeeRate(0);
220 add_coin(available_coins, *
wallet, 5 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
221 add_coin(available_coins, *
wallet, 3 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
222 add_coin(available_coins, *
wallet, 2 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
225 COutput select_coin = available_coins.
All().at(0);
228 selected_input.
Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs);
232 const auto result10 =
SelectCoins(*
wallet, available_coins, selected_input, 10 *
CENT, coin_control, coin_selection_params_bnb);
242 coin_selection_params_bnb.m_effective_feerate =
CFeeRate(5000);
243 coin_selection_params_bnb.m_long_term_feerate =
CFeeRate(3000);
246 CAmount input_fee = coin_selection_params_bnb.m_effective_feerate.GetFee(68);
247 add_coin(available_coins, *
wallet, 10 *
CENT + input_fee, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
248 add_coin(available_coins, *
wallet, 9 *
CENT + input_fee, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
249 add_coin(available_coins, *
wallet, 1 *
CENT + input_fee, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
256 COutput select_coin = available_coins.
All().at(1);
259 selected_input.
Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs);
261 const auto result13 =
SelectCoins(*
wallet, available_coins, selected_input, 10 *
CENT, coin_control, coin_selection_params_bnb);
272 add_coin(available_coins, *
wallet, 10 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
273 add_coin(available_coins, *
wallet, 9 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
274 add_coin(available_coins, *
wallet, 8 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
276 add_coin(available_coins, *
wallet, 3 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
277 add_coin(available_coins, *
wallet, 1 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
282 BOOST_REQUIRE(!no_res);
286 add_coin(available_coins, *
wallet, 5 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
316 params.m_subtract_fee_outputs =
true;
317 params.m_change_fee = params.m_effective_feerate.
GetFee(params.change_output_size);
318 params.m_cost_of_change = params.m_discard_feerate.GetFee(params.change_spend_size) + params.m_change_fee;
319 params.m_min_change_target = params.m_cost_of_change + 1;
322 add_coin(available_coins, *
wallet,
COIN + params.m_cost_of_change, params.m_effective_feerate, 6,
true, 0,
true);
323 add_coin(available_coins, *
wallet, 0.5 *
COIN + params.m_cost_of_change, params.m_effective_feerate, 6,
true, 0,
true);
324 add_coin(available_coins, *
wallet, 0.5 *
COIN, params.m_effective_feerate, 6,
true, 0,
true);
347 available_coins.
Clear();
416 available_coins.
Clear();
474 available_coins.
Clear();
506 available_coins.
Clear();
507 for (
int j = 0; j < 20; j++)
519 available_coins.
Clear();
530 available_coins.
Clear();
541 available_coins.
Clear();
561 available_coins.
Clear();
563 for (uint16_t j = 0; j < 676; j++)
571 if (amt - 2000 <
CENT) {
573 uint16_t returnSize = std::ceil((2000.0 +
CENT)/amt);
574 CAmount returnValue = amt * returnSize;
587 available_coins.
Clear();
588 for (
int i2 = 0; i2 < 100; i2++)
651 for (
int i = 0; i < 1000; i++)
668 std::default_random_engine generator;
669 std::exponential_distribution<double> distribution (100);
673 for (
int i = 0; i < 100; ++i)
679 for (
int j = 0; j < 1000; ++j)
681 CAmount val = distribution(generator)*10000000;
704 cs_params.m_cost_of_change = 1;
705 cs_params.min_viable_change = 1;
707 const auto result =
SelectCoins(*
wallet, available_coins, {}, target, cc, cs_params);
709 BOOST_CHECK_GE(result->GetSelectedValue(), target);
716 const CAmount min_viable_change{300};
717 const CAmount change_cost{125};
734 selection1.RecalculateWaste(min_viable_change, change_cost, change_fee);
741 selection2.RecalculateWaste(min_viable_change, change_cost, change_fee);
742 BOOST_CHECK_GT(selection2.GetWaste(), selection1.GetWaste());
749 selection3.RecalculateWaste(min_viable_change, change_cost, change_fee);
751 BOOST_CHECK_LT(selection3.GetWaste(), selection1.GetWaste());
759 selection_nochange1.RecalculateWaste(min_viable_change, change_cost, change_fee);
767 selection_nochange2.RecalculateWaste(min_viable_change, change_cost, change_fee);
769 BOOST_CHECK_LT(selection_nochange2.GetWaste(), selection_nochange1.GetWaste());
777 selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
786 selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
795 selection.RecalculateWaste(min_viable_change, change_cost , change_fee);
804 selection.RecalculateWaste(min_viable_change, fee_diff * 2, change_fee);
810 const CAmount new_target{exact_target - fee_diff * 2};
814 selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
821 const CAmount target_waste1{-2 * fee_diff};
824 selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
831 const CAmount large_fee_diff{90};
832 const CAmount target_waste2{-2 * large_fee_diff + change_cost};
836 assert(target_waste2 == -55);
839 selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
848 const CAmount min_viable_change{200};
849 const CAmount change_cost{125};
858 const std::vector<std::shared_ptr<COutput>> inputs = selection.GetShuffledInputVector();
860 for (
size_t i = 0; i < inputs.size(); ++i) {
861 inputs[i]->ApplyBumpFee(20*(i+1));
864 selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
865 CAmount expected_waste = fee_diff * -2 + change_cost + 60;
868 selection.SetBumpFeeDiscount(30);
869 selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
870 expected_waste = fee_diff * -2 + change_cost + 60 - 30;
884 const std::vector<std::shared_ptr<COutput>> inputs = selection.GetShuffledInputVector();
886 for (
size_t i = 0; i < inputs.size(); ++i) {
887 inputs[i]->ApplyBumpFee(20*(i+1));
890 selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
891 CAmount expected_waste = fee_diff * -2 + 60 + 40;
894 selection.SetBumpFeeDiscount(30);
895 selection.RecalculateWaste(min_viable_change, change_cost, change_fee);
896 expected_waste = fee_diff * -2 + 60 - 30 + 70;
903 const int input_bytes = 148;
906 const int nInput = 0;
910 tx.
vout[nInput].nValue = nValue;
914 const CAmount expected_ev1 = 9852;
923 const CAmount expected_ev3 = -4800;
939 int max_selection_weight,
977 int max_selection_weight = 10'000;
980 for (
int j = 0; j < 10; ++j) {
984 return available_coins;
995 int max_selection_weight = 3000;
998 for (
int j = 0; j < 10; ++j) {
1002 return available_coins;
1013 int max_selection_weight = 10'000;
1016 for (
int j = 0; j < 60; ++j) {
1019 for (
int i = 0; i < 10; i++) {
1022 return available_coins;
1025 for (
int i = 0; i < 10; ++i) {
1028 for (
int j = 0; j < 17; ++j) {
1033 size_t expected_attempts = 37;
1034 BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts,
strprintf(
"Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1042 int max_selection_weight = 400'000;
1048 return available_coins;
1055 size_t expected_attempts = 3;
1056 BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts,
strprintf(
"Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1064 int max_selection_weight = 400'000;
1067 for (
int j = 0; j < 5; ++j) {
1075 return available_coins;
1084 size_t expected_attempts = 92;
1085 BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts,
strprintf(
"Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1093 int max_selection_weight = 400'000;
1102 for (
int j = 0; j < 100; ++j) {
1105 for (
int j = 0; j < 100; ++j) {
1108 for (
int j = 0; j < 100; ++j) {
1111 for (
int j = 0; j < 100; ++j) {
1114 return available_coins;
1123 size_t expected_attempts = 38;
1124 BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts,
strprintf(
"Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1132 int max_selection_weight = 40000;
1138 for (
int j = 0; j < 100; ++j) {
1142 return available_coins;
1149 size_t expected_attempts = 7;
1150 BOOST_CHECK_MESSAGE(res->GetSelectionsEvaluated() == expected_attempts,
strprintf(
"Expected %i attempts, but got %i", expected_attempts, res->GetSelectionsEvaluated()));
1157 int max_selection_weight,
1191 int max_selection_weight = 10000;
1194 for (
int j = 0; j < 10; ++j) {
1198 return available_coins;
1209 int max_selection_weight = 3000;
1212 for (
int j = 0; j < 10; ++j) {
1217 return available_coins;
1228 int max_selection_weight = 10000;
1231 for (
int j = 0; j < 60; ++j) {
1234 for (
int i = 0; i < 10; i++) {
1237 return available_coins;
1240 BOOST_CHECK(res->GetWeight() <= max_selection_weight);
1247 auto available_coins = coin_setup(*
wallet);
1252 const auto signedTxSize = 10 + 34 + 68 * result->GetInputSet().size();
1255 BOOST_CHECK_GE(result->GetSelectedValue(), target);
1262 return std::any_of(set.begin(), set.end(), [&](
const auto& coin) { return coin->GetEffectiveValue() == amount; });
1295 for (
int j = 0; j < 1515; ++j) {
1300 return available_coins;
1307 BOOST_CHECK_LE(result->GetWeight(), max_weight);
1321 for (
int j = 0; j < 400; ++j) {
1324 for (
int j = 0; j < 2000; ++j) {
1327 return available_coins;
1333 BOOST_CHECK_LE(result->GetWeight(), max_weight);
1346 for (
int j = 0; j < 1515; ++j) {
1349 return available_coins;
1371 add_coin(available_coins, *dummyWallet, 100000);
1390 COutput output = available_coins.
All().at(0);
1398 const auto result =
SelectCoins(*
wallet, available_coins, preset_inputs, target, cc, cs_params);
1410 for (
int i=0; i<10; i++) {
1418 std::unordered_set<COutPoint, SaltedOutpointHasher> outs_to_remove;
1419 const auto& coins = available_coins.
All();
1420 for (
int i = 0; i < 2; i++) {
1421 outs_to_remove.emplace(coins[i].outpoint);
1423 available_coins.
Erase(outs_to_remove);
1426 const auto& updated_coins = available_coins.
All();
1427 for (
const auto&
out: outs_to_remove) {
1428 auto it = std::find_if(updated_coins.begin(), updated_coins.end(), [&
out](
const COutput &coin) {
1429 return coin.outpoint == out;
CScript GetScriptForDestination(const CTxDestination &dest)
Generate a Bitcoin scriptPubKey for the given CTxDestination.
int64_t CAmount
Amount in satoshis (Can be negative)
static constexpr CAmount COIN
The amount of satoshis in one BTC.
#define Assert(val)
Identity function.
Fee rate in satoshis per virtualbyte: CAmount / vB the feerate is represented internally as FeeFrac.
CAmount GetFee(int32_t virtual_bytes) const
Return the fee in satoshis for the given vsize in vbytes.
An outpoint - a combination of a transaction hash and an index n into its vout.
I randrange(I range) noexcept
Generate a random integer in the range [0..range), with range > 0.
PreselectedInput & Select(const COutPoint &outpoint)
Lock-in the given output for spending.
bool m_allow_other_inputs
If true, the selection process can add extra unselected inputs from the wallet while requires all sel...
void SetInputWeight(const COutPoint &outpoint, int64_t weight)
Set an input's weight.
A CWallet maintains a set of transactions and balances, and provides the ability to create new transa...
A transaction with a bunch of additional info that only the owner cares about.
const Txid & GetHash() const LIFETIMEBOUND
int64_t GetTxTime() const
static const int WITNESS_SCALE_FACTOR
BOOST_FIXTURE_TEST_SUITE(cuckoocache_tests, BasicTestingSetup)
Test Suite for CuckooCache.
BOOST_AUTO_TEST_SUITE_END()
bilingual_str ErrorString(const Result< T > &result)
static const CoinEligibilityFilter filter_standard(1, 6, 0)
FilteredOutputGroups GroupOutputs(const CWallet &wallet, const CoinsResult &coins, const CoinSelectionParams &coin_sel_params, const std::vector< SelectionFilter > &filters, std::vector< OutputGroup > &ret_discarded_groups)
BOOST_FIXTURE_TEST_CASE(wallet_coinsresult_test, BasicTestingSetup)
util::Result< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change, int max_selection_weight)
static std::unique_ptr< CWallet > NewWallet(const node::NodeContext &m_node, const std::string &wallet_name="")
util::Result< SelectionResult > CoinGrinder(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, CAmount change_target, int max_selection_weight)
util::Result< PreSelectedInputs > FetchSelectedInputs(const CWallet &wallet, const CCoinControl &coin_control, const CoinSelectionParams &coin_selection_params)
Fetch and validate coin control selected inputs.
std::vector< OutputGroup > & GroupCoins(const std::vector< COutput > &available_coins, bool subtract_fee_outputs=false)
std::vector< OutputGroup > & KnapsackGroupOutputs(const CoinsResult &available_coins, CWallet &wallet, const CoinEligibilityFilter &filter)
util::Result< SelectionResult > KnapsackSolver(std::vector< OutputGroup > &groups, const CAmount &nTargetValue, CAmount change_target, FastRandomContext &rng, int max_selection_weight)
util::Result< SelectionResult > SelectCoins(const CWallet &wallet, CoinsResult &available_coins, const PreSelectedInputs &pre_set_inputs, const CAmount &nTargetValue, const CCoinControl &coin_control, const CoinSelectionParams &coin_selection_params)
Select all coins from coin_control, and if coin_control 'm_allow_other_inputs=true',...
static const CoinEligibilityFilter filter_standard_extra(6, 6, 0)
static bool has_coin(const CoinSet &set, CAmount amount)
std::set< std::shared_ptr< COutput > > CoinSet
static bool EqualResult(const SelectionResult &a, const SelectionResult &b)
Check if this selection is equal to another one.
std::unique_ptr< WalletDatabase > CreateMockableWalletDatabase(MockableData records)
BOOST_AUTO_TEST_CASE(bnb_test)
@ WALLET_FLAG_DESCRIPTORS
Indicate that this wallet supports DescriptorScriptPubKeyMan.
static const CoinEligibilityFilter filter_confirmed(1, 1, 0)
int CalculateMaximumSignedInputSize(const CTxOut &txout, const COutPoint outpoint, const SigningProvider *provider, bool can_grind_r, const CCoinControl *coin_control)
static void add_coin(const CAmount &nValue, int nInput, SelectionResult &result)
static bool EquivalentResult(const SelectionResult &a, const SelectionResult &b)
Check if SelectionResult a is equivalent to SelectionResult b.
static void ApproximateBestSubset(FastRandomContext &insecure_rand, const std::vector< OutputGroup > &groups, const CAmount &nTotalLower, const CAmount &nTargetValue, std::vector< char > &vfBest, CAmount &nBest, int max_selection_weight, int iterations=1000)
Find a subset of the OutputGroups that is at least as large as, but as close as possible to,...
util::Result< SelectionResult > SelectCoinsSRD(const std::vector< OutputGroup > &utxo_pool, CAmount target_value, CAmount change_fee, FastRandomContext &rng, int max_selection_weight)
Select coins by Single Random Draw.
static 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)
#define BOOST_CHECK_EQUAL(v1, v2)
#define BOOST_CHECK(expr)
static constexpr int32_t MAX_STANDARD_TX_WEIGHT
The maximum weight for transactions we're willing to relay/mine.
static CTransactionRef MakeTransactionRef(Tx &&txIn)
static constexpr CAmount CENT
A mutable version of CTransaction.
std::vector< CTxOut > vout
Txid GetHash() const
Compute the hash of this CMutableTransaction.
NodeContext struct containing references to chain state and connection state.
std::unique_ptr< interfaces::Chain > chain
A UTXO under consideration for use in funding a new transaction.
COutPoint outpoint
The outpoint identifying this UTXO.
CTxOut txout
The output itself.
CAmount GetEffectiveValue() const
Parameters for filtering which OutputGroups we may use in coin selection.
Parameters for one iteration of Coin Selection.
FastRandomContext & rng_fast
Randomness to use in the context of coin selection.
CAmount m_min_change_target
Mininmum change to target in Knapsack solver and CoinGrinder: select coins to cover the payment and a...
CAmount m_change_fee
Cost of creating the change output.
int change_output_size
Size of a change output in bytes, determined by the output type.
int tx_noinputs_size
Size of the transaction before coin selection, consisting of the header and recipient output(s),...
COutputs available for spending, stored by OutputType.
void Add(OutputType type, const COutput &out)
std::vector< COutput > All() const
Concatenate and return all COutputs as one vector.
size_t Size() const
The following methods are provided so that CoinsResult can mimic a vector, i.e., methods can work wit...
std::map< OutputType, std::vector< COutput > > coins
void Erase(const std::unordered_set< COutPoint, SaltedOutpointHasher > &coins_to_remove)
std::vector< OutputGroup > mixed_group
A group of UTXOs paid to the same output script.
Stores several 'Groups' whose were mapped by output type.
const std::set< std::shared_ptr< COutput > > & GetInputSet() const
Get m_selected_inputs.
void AddInput(const OutputGroup &group)
State of transaction not confirmed or conflicting with a known block and not in the mempool.
#define WITH_LOCK(cs, code)
Run code while locking a mutex.