19 #include <boost/test/unit_test.hpp>
23 BOOST_FIXTURE_TEST_SUITE(coinselector_tests, WalletTestingSetup)
30 #define RANDOM_REPEATS 5
39 static void add_coin(
const CAmount& nValue,
int nInput, std::vector<COutput>& set)
42 tx.
vout.resize(nInput + 1);
43 tx.
vout[nInput].nValue = nValue;
45 set.emplace_back(
COutPoint(tx.
GetHash(), nInput), tx.
vout.at(nInput), 1, -1,
true,
true,
true, 0,
false, 0);
51 tx.
vout.resize(nInput + 1);
52 tx.
vout[nInput].nValue = nValue;
54 COutput output(
COutPoint(tx.
GetHash(), nInput), tx.
vout.at(nInput), 1, -1,
true,
true,
true, 0,
false, 0);
56 group.
Insert(output, 0, 0,
true);
63 tx.
vout.resize(nInput + 1);
64 tx.
vout[nInput].nValue = nValue;
66 COutput coin(
COutPoint(tx.
GetHash(), nInput), tx.
vout.at(nInput), 1, 148,
true,
true,
true, 0,
false, fee);
75 tx.
vout.resize(nInput + 1);
76 tx.
vout[nInput].nValue = nValue;
86 const auto& txout = wtx.
tx->vout.at(nInput);
87 available_coins.
Add(
OutputType::BECH32, {
COutPoint(wtx.
GetHash(), nInput), txout, nAge,
CalculateMaximumSignedInputSize(txout, &
wallet,
nullptr),
true,
true,
true, wtx.
GetTxTime(), fIsFromMe, feerate});
94 std::vector<CAmount> a_amts;
95 std::vector<CAmount> b_amts;
97 a_amts.push_back(coin.txout.nValue);
100 b_amts.push_back(coin.txout.nValue);
102 std::sort(a_amts.begin(), a_amts.end());
103 std::sort(b_amts.begin(), b_amts.end());
105 std::pair<std::vector<CAmount>::iterator, std::vector<CAmount>::iterator>
ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
106 return ret.first == a_amts.end() &&
ret.second == b_amts.end();
114 return a.outpoint == b.outpoint;
123 for (
int i = 0; i < utxos; ++i) {
124 target +=
CAmount{1} << (utxos+i);
131 inline std::vector<OutputGroup>&
GroupCoins(
const std::vector<COutput>& available_coins)
133 static std::vector<OutputGroup> static_groups;
134 static_groups.clear();
135 for (
auto& coin : available_coins) {
136 static_groups.emplace_back();
137 static_groups.back().Insert(coin, 0, 0,
false);
139 return static_groups;
156 static std::vector<OutputGroup> static_groups;
157 static_groups =
GroupOutputs(
wallet, available_coins, coin_selection_params, filter,
false);
158 return static_groups;
166 std::vector<COutput> utxo_pool;
188 expected_result.
Clear();
196 expected_result.
Clear();
205 expected_result.
Clear();
209 expected_result.
Clear();
217 expected_result.
Clear();
221 expected_result.
Clear();
233 expected_result.
Clear();
237 expected_result.
Clear();
258 for (
int i = 0; i < 50000; ++i) {
271 for (
int i = 5; i <= 20; ++i) {
275 for (
int i = 0; i < 100; ++i) {
291 coin_selection_params_bnb.m_change_fee = coin_selection_params_bnb.m_effective_feerate.
GetFee(coin_selection_params_bnb.change_output_size);
292 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;
293 coin_selection_params_bnb.min_viable_change = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_spend_size);
294 coin_selection_params_bnb.m_subtract_fee_outputs =
true;
301 wallet->SetupDescriptorScriptPubKeyMans();
305 add_coin(available_coins, *
wallet, 1, coin_selection_params_bnb.m_effective_feerate);
306 available_coins.
All().at(0).input_bytes = 40;
310 available_coins.
Clear();
311 add_coin(available_coins, *
wallet, 1 *
CENT, coin_selection_params_bnb.m_effective_feerate);
312 available_coins.
All().at(0).input_bytes = 40;
323 wallet->SetupDescriptorScriptPubKeyMans();
327 add_coin(available_coins, *
wallet, 5 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
328 add_coin(available_coins, *
wallet, 3 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
329 add_coin(available_coins, *
wallet, 2 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
332 COutput select_coin = available_coins.
All().at(0);
335 selected_input.
Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs);
337 coin_selection_params_bnb.m_effective_feerate =
CFeeRate(0);
338 const auto result10 =
SelectCoins(*
wallet, available_coins, selected_input, 10 *
CENT, coin_control, coin_selection_params_bnb);
346 wallet->SetupDescriptorScriptPubKeyMans();
351 coin_selection_params_bnb.m_effective_feerate =
CFeeRate(5000);
352 coin_selection_params_bnb.m_long_term_feerate =
CFeeRate(3000);
354 add_coin(available_coins, *
wallet, 10 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
355 add_coin(available_coins, *
wallet, 9 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
356 add_coin(available_coins, *
wallet, 1 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
358 expected_result.
Clear();
361 const auto result11 =
SelectCoins(*
wallet, available_coins, {}, 10 *
CENT, coin_control, coin_selection_params_bnb);
363 available_coins.
Clear();
366 coin_selection_params_bnb.m_effective_feerate =
CFeeRate(3000);
367 coin_selection_params_bnb.m_long_term_feerate =
CFeeRate(5000);
369 add_coin(available_coins, *
wallet, 10 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
370 add_coin(available_coins, *
wallet, 9 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
371 add_coin(available_coins, *
wallet, 1 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
373 expected_result.
Clear();
376 const auto result12 =
SelectCoins(*
wallet, available_coins, {}, 10 *
CENT, coin_control, coin_selection_params_bnb);
378 available_coins.
Clear();
381 coin_selection_params_bnb.m_effective_feerate =
CFeeRate(5000);
382 coin_selection_params_bnb.m_long_term_feerate =
CFeeRate(3000);
384 add_coin(available_coins, *
wallet, 10 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
385 add_coin(available_coins, *
wallet, 9 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
386 add_coin(available_coins, *
wallet, 1 *
CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24,
false, 0,
true);
388 expected_result.
Clear();
392 COutput select_coin = available_coins.
All().at(1);
395 selected_input.
Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs);
397 const auto result13 =
SelectCoins(*
wallet, available_coins, selected_input, 10 *
CENT, coin_control, coin_selection_params_bnb);
411 wallet->SetupDescriptorScriptPubKeyMans();
418 available_coins.
Clear();
487 available_coins.
Clear();
545 available_coins.
Clear();
577 available_coins.
Clear();
578 for (
int j = 0; j < 20; j++)
590 available_coins.
Clear();
601 available_coins.
Clear();
612 available_coins.
Clear();
632 available_coins.
Clear();
634 for (uint16_t j = 0; j < 676; j++)
642 if (amt - 2000 <
CENT) {
644 uint16_t returnSize = std::ceil((2000.0 +
CENT)/amt);
645 CAmount returnValue = amt * returnSize;
658 available_coins.
Clear();
659 for (
int i2 = 0; i2 < 100; i2++)
721 wallet->SetupDescriptorScriptPubKeyMans();
726 for (
int i = 0; i < 1000; i++)
743 wallet->SetupDescriptorScriptPubKeyMans();
746 std::default_random_engine generator;
747 std::exponential_distribution<double> distribution (100);
751 for (
int i = 0; i < 100; ++i)
757 for (
int j = 0; j < 1000; ++j)
759 CAmount val = distribution(generator)*10000000;
782 cs_params.m_cost_of_change = 1;
783 cs_params.min_viable_change = 1;
785 const auto result =
SelectCoins(*
wallet, available_coins, {}, target, cc, cs_params);
787 BOOST_CHECK_GE(result->GetSelectedValue(), target);
795 const CAmount change_cost{125};
799 const CAmount excess{in_amt - fee * 2 - target};
828 add_coin(1 *
COIN, 1, selection, fee * 2, fee - fee_diff);
829 add_coin(2 *
COIN, 2, selection, fee * 2, fee - fee_diff);
831 BOOST_CHECK_GT(waste2, waste1);
840 BOOST_CHECK_LT(waste3, waste1);
849 BOOST_CHECK_LT(waste_nochange2, waste_nochange1);
855 const CAmount exact_target{in_amt - fee * 2};
860 const CAmount new_change_cost{fee_diff * 2};
867 const CAmount new_target{in_amt - fee * 2 - fee_diff * 2};
875 const CAmount target_waste1{-2 * fee_diff};
882 const CAmount large_fee_diff{90};
883 const CAmount target_waste2{-2 * large_fee_diff + change_cost};
884 add_coin(1 *
COIN, 1, selection, fee, fee + large_fee_diff);
885 add_coin(2 *
COIN, 2, selection, fee, fee + large_fee_diff);
891 const int input_bytes = 148;
894 const int nInput = 0;
898 tx.
vout[nInput].nValue = nValue;
901 COutput output1(
COutPoint(tx.
GetHash(), nInput), tx.
vout.at(nInput), 1, input_bytes,
true,
true,
true, 0,
false, feerate);
902 const CAmount expected_ev1 = 9852;
906 COutput output2(
COutPoint(tx.
GetHash(), nInput), tx.
vout.at(nInput), 1, -1,
true,
true,
true, 0,
false, feerate);
910 COutput output3(
COutPoint(tx.
GetHash(), nInput), tx.
vout.at(nInput), 1, input_bytes,
true,
true,
true, 0,
false,
CFeeRate(100000));
911 const CAmount expected_ev3 = -4800;
916 COutput output4(
COutPoint(tx.
GetHash(), nInput), tx.
vout.at(nInput), 1, input_bytes,
true,
true,
true, 0,
false, fees);
920 COutput output5(
COutPoint(tx.
GetHash(), nInput), tx.
vout.at(nInput), 1, -1,
true,
true,
true, 0,
false, 0);
930 wallet->SetupDescriptorScriptPubKeyMans();
932 auto available_coins = coin_setup(*
wallet);
936 const auto signedTxSize = 10 + 34 + 68 * result->GetInputSet().size();
939 BOOST_CHECK_GE(result->GetSelectedValue(), target);
946 return std::any_of(set.begin(), set.end(), [&](
const auto& coin) { return coin.GetEffectiveValue() == amount; });
980 for (
int j = 0; j < 1515; ++j) {
985 return available_coins;
1004 for (
int j = 0; j < 400; ++j) {
1007 for (
int j = 0; j < 2000; ++j) {
1010 return available_coins;
1028 for (
int j = 0; j < 1515; ++j) {
1031 return available_coins;
1052 wallet->SetupDescriptorScriptPubKeyMans();
1057 dummyWallet->LoadWallet();
1058 LOCK(dummyWallet->cs_wallet);
1060 dummyWallet->SetupDescriptorScriptPubKeyMans();
1062 add_coin(available_coins, *dummyWallet, 100000);
1081 COutput output = available_coins.
All().at(0);
1088 const auto result =
SelectCoins(*
wallet, available_coins, preset_inputs, target, cc, cs_params);
1099 LOCK(dummyWallet->cs_wallet);
1101 dummyWallet->SetupDescriptorScriptPubKeyMans();
1104 for (
int i=0; i<10; i++) {
1112 std::unordered_set<COutPoint, SaltedOutpointHasher> outs_to_remove;
1113 const auto& coins = available_coins.
All();
1114 for (
int i = 0; i < 2; i++) {
1115 outs_to_remove.emplace(coins[i].outpoint);
1117 available_coins.
Erase(outs_to_remove);
1120 const auto& updated_coins = available_coins.
All();
1121 for (
const auto& out: outs_to_remove) {
1122 auto it = std::find_if(updated_coins.begin(), updated_coins.end(), [&out](
const COutput &coin) {
1123 return coin.outpoint == out;
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 kilovirtualbyte: CAmount / kvB.
CAmount GetFee(uint32_t num_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.
uint64_t randrange(uint64_t range) noexcept
Generate a random integer in the range [0..range).
Interface giving clients (wallet processes, maybe other analysis tools in the future) ability to acce...
void Select(const COutPoint &output)
void SelectExternal(const COutPoint &outpoint, const CTxOut &txout)
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)
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 uint256 & GetHash() const
int64_t GetTxTime() const
static const int WITNESS_SCALE_FACTOR
BOOST_AUTO_TEST_SUITE_END()
static CAmount make_hard_case(int utxos, std::vector< COutput > &utxo_pool)
static const CoinEligibilityFilter filter_standard(1, 6, 0)
std::unique_ptr< WalletDatabase > CreateMockWalletDatabase(DatabaseOptions &options)
Return object for accessing temporary in-memory database.
CAmount GetSelectionWaste(const std::set< COutput > &inputs, CAmount change_cost, CAmount target, bool use_effective_value)
Compute the waste for this result given the cost of change and the opportunity cost of spending these...
BOOST_FIXTURE_TEST_CASE(wallet_coinsresult_test, BasicTestingSetup)
static void add_coin(const CAmount &nValue, int nInput, std::vector< COutput > &set)
util::Result< PreSelectedInputs > FetchSelectedInputs(const CWallet &wallet, const CCoinControl &coin_control, const CoinSelectionParams &coin_selection_params) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet)
Fetch and validate coin control selected inputs.
std::vector< OutputGroup > & KnapsackGroupOutputs(const std::vector< COutput > &available_coins, CWallet &wallet, const CoinEligibilityFilter &filter)
std::vector< OutputGroup > & GroupCoins(const std::vector< COutput > &available_coins)
static void ApproximateBestSubset(FastRandomContext &insecure_rand, const std::vector< OutputGroup > &groups, const CAmount &nTotalLower, const CAmount &nTargetValue, std::vector< char > &vfBest, CAmount &nBest, 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 > 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)
std::optional< SelectionResult > KnapsackSolver(std::vector< OutputGroup > &groups, const CAmount &nTargetValue, CAmount change_target, FastRandomContext &rng)
static bool has_coin(const CoinSet &set, CAmount amount)
static bool EqualResult(const SelectionResult &a, const SelectionResult &b)
Check if this selection is equal to another one.
static util::Result< SelectionResult > select_coins(const CAmount &target, const CoinSelectionParams &cs_params, const CCoinControl &cc, std::function< CoinsResult(CWallet &)> coin_setup, interfaces::Chain *chain, const ArgsManager &args)
int CalculateMaximumSignedInputSize(const CTxOut &txout, const COutPoint outpoint, const SigningProvider *provider, const CCoinControl *coin_control)
std::vector< OutputGroup > GroupOutputs(const CWallet &wallet, const std::vector< COutput > &outputs, const CoinSelectionParams &coin_sel_params, const CoinEligibilityFilter &filter, bool positive_only)
std::optional< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change)
std::set< COutput > CoinSet
BOOST_AUTO_TEST_CASE(bnb_search_test)
@ WALLET_FLAG_DESCRIPTORS
Indicate that this wallet supports DescriptorScriptPubKeyMan.
static const CoinEligibilityFilter filter_confirmed(1, 1, 0)
static bool EquivalentResult(const SelectionResult &a, const SelectionResult &b)
Check if SelectionResult a is equivalent to SelectionResult b.
#define BOOST_CHECK_EQUAL(v1, v2)
#define BOOST_CHECK(expr)
static constexpr unsigned int MAX_STANDARD_TX_WEIGHT
The maximum weight for transactions we're willing to relay/mine.
static CTransactionRef MakeTransactionRef(Tx &&txIn)
static constexpr CAmount CENT
CScript GetScriptForDestination(const CTxDestination &dest)
Generate a Bitcoin scriptPubKey for the given CTxDestination.
A mutable version of CTransaction.
uint256 GetHash() const
Compute the hash of this CMutableTransaction.
std::vector< CTxOut > vout
std::unique_ptr< interfaces::Chain > chain
A UTXO under consideration for use in funding a new transaction.
CAmount long_term_fee
The fee required to spend this output at the consolidation feerate.
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.
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)
A group of UTXOs paid to the same output script.
void Insert(const COutput &output, size_t ancestors, size_t descendants, bool positive_only)
const std::set< 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.