From f930aefff9690a1e830d897d0a8c53f4219ae4a8 Mon Sep 17 00:00:00 2001 From: furszy Date: Tue, 22 Nov 2022 11:39:35 -0300 Subject: wallet: bugfix, 'CoinsResult::Erase' is erasing only one output of the set The loop break shouldn't have being there. --- src/wallet/spend.cpp | 14 ++++++-------- src/wallet/spend.h | 2 +- 2 files changed, 7 insertions(+), 9 deletions(-) (limited to 'src/wallet') diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index 8c0d56a1cb..5f4e3e79c7 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -102,15 +102,13 @@ void CoinsResult::Clear() { coins.clear(); } -void CoinsResult::Erase(std::set& preset_coins) +void CoinsResult::Erase(const std::unordered_set& coins_to_remove) { - for (auto& it : coins) { - auto& vec = it.second; - auto i = std::find_if(vec.begin(), vec.end(), [&](const COutput &c) { return preset_coins.count(c.outpoint);}); - if (i != vec.end()) { - vec.erase(i); - break; - } + for (auto& [type, vec] : coins) { + auto remove_it = std::remove_if(vec.begin(), vec.end(), [&](const COutput& coin) { + return coins_to_remove.count(coin.outpoint) == 1; + }); + vec.erase(remove_it, vec.end()); } } diff --git a/src/wallet/spend.h b/src/wallet/spend.h index ba2c6638c8..df57fc1362 100644 --- a/src/wallet/spend.h +++ b/src/wallet/spend.h @@ -47,7 +47,7 @@ struct CoinsResult { * i.e., methods can work with individual OutputType vectors or on the entire object */ size_t Size() const; void Clear(); - void Erase(std::set& preset_coins); + void Erase(const std::unordered_set& coins_to_remove); void Shuffle(FastRandomContext& rng_fast); void Add(OutputType type, const COutput& out); -- cgit v1.2.3 From 341ba7ffd8cdb56b4cde1f251768c3d2c2a9b4e9 Mon Sep 17 00:00:00 2001 From: furszy Date: Tue, 22 Nov 2022 12:58:19 -0300 Subject: test: wallet, coverage for CoinsResult::Erase function --- src/wallet/test/coinselector_tests.cpp | 40 ++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) (limited to 'src/wallet') diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index f9c8c8ee9d..c76538ad48 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -980,5 +980,45 @@ BOOST_AUTO_TEST_CASE(SelectCoins_effective_value_test) BOOST_CHECK(!result); } +BOOST_FIXTURE_TEST_CASE(wallet_coinsresult_test, BasicTestingSetup) +{ + // Test case to verify CoinsResult object sanity. + CoinsResult available_coins; + { + std::unique_ptr dummyWallet = std::make_unique(m_node.chain.get(), "dummy", m_args, CreateMockWalletDatabase()); + BOOST_CHECK_EQUAL(dummyWallet->LoadWallet(), DBErrors::LOAD_OK); + LOCK(dummyWallet->cs_wallet); + dummyWallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS); + dummyWallet->SetupDescriptorScriptPubKeyMans(); + + // Add some coins to 'available_coins' + for (int i=0; i<10; i++) { + add_coin(available_coins, *dummyWallet, 1 * COIN); + } + } + + { + // First test case, check that 'CoinsResult::Erase' function works as expected. + // By trying to erase two elements from the 'available_coins' object. + std::unordered_set outs_to_remove; + const auto& coins = available_coins.All(); + for (int i = 0; i < 2; i++) { + outs_to_remove.emplace(coins[i].outpoint); + } + available_coins.Erase(outs_to_remove); + + // Check that the elements were actually removed. + const auto& updated_coins = available_coins.All(); + for (const auto& out: outs_to_remove) { + auto it = std::find_if(updated_coins.begin(), updated_coins.end(), [&out](const COutput &coin) { + return coin.outpoint == out; + }); + BOOST_CHECK(it == updated_coins.end()); + } + // And verify that no extra element were removed + BOOST_CHECK_EQUAL(available_coins.Size(), 8); + } +} + BOOST_AUTO_TEST_SUITE_END() } // namespace wallet -- cgit v1.2.3 From cf793846978a8783c23b66ba6b4f3f30e83ff3eb Mon Sep 17 00:00:00 2001 From: furszy Date: Wed, 23 Nov 2022 10:22:50 -0300 Subject: test: Coin Selection, duplicated preset inputs selection This exercises the bug inside CoinsResult::Erase that ends up on (1) a wallet crash or (2) a created and broadcasted tx that contains a reduced recipient's amount. This is covered by making the wallet selects the preset inputs twice during the coin selection process. Making the wallet think that the selection process result covers the entire tx target when it does not. It's actually creating a tx that sends more coins than what inputs are covering for. Which, combined with the SFFO option, makes the wallet incorrectly reduce the recipient's amount by the difference between the original target and the wrongly counted inputs. Which means, a created and relayed tx sending less coins to the destination than what the user inputted. --- src/wallet/test/spend_tests.cpp | 45 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) (limited to 'src/wallet') diff --git a/src/wallet/test/spend_tests.cpp b/src/wallet/test/spend_tests.cpp index a75b014870..81a8883f85 100644 --- a/src/wallet/test/spend_tests.cpp +++ b/src/wallet/test/spend_tests.cpp @@ -112,5 +112,50 @@ BOOST_FIXTURE_TEST_CASE(FillInputToWeightTest, BasicTestingSetup) // Note: We don't test the next boundary because of memory allocation constraints. } +BOOST_FIXTURE_TEST_CASE(wallet_duplicated_preset_inputs_test, TestChain100Setup) +{ + // Verify that the wallet's Coin Selection process does not include pre-selected inputs twice in a transaction. + + // Add 4 spendable UTXO, 50 BTC each, to the wallet (total balance 200 BTC) + for (int i = 0; i < 4; i++) CreateAndProcessBlock({}, GetScriptForRawPubKey(coinbaseKey.GetPubKey())); + auto wallet = CreateSyncedWallet(*m_node.chain, WITH_LOCK(Assert(m_node.chainman)->GetMutex(), return m_node.chainman->ActiveChain()), m_args, coinbaseKey); + + LOCK(wallet->cs_wallet); + auto available_coins = AvailableCoins(*wallet); + std::vector coins = available_coins.All(); + // Preselect the first 3 UTXO (150 BTC total) + std::set preset_inputs = {coins[0].outpoint, coins[1].outpoint, coins[2].outpoint}; + + // Try to create a tx that spends more than what preset inputs + wallet selected inputs are covering for. + // The wallet can cover up to 200 BTC, and the tx target is 299 BTC. + std::vector recipients = {{GetScriptForDestination(*Assert(wallet->GetNewDestination(OutputType::BECH32, "dummy"))), + /*nAmount=*/299 * COIN, /*fSubtractFeeFromAmount=*/true}}; + CCoinControl coin_control; + coin_control.m_allow_other_inputs = true; + for (const auto& outpoint : preset_inputs) { + coin_control.Select(outpoint); + } + + // Attempt to send 299 BTC from a wallet that only has 200 BTC. The wallet should exclude + // the preset inputs from the pool of available coins, realize that there is not enough + // money to fund the 299 BTC payment, and fail with "Insufficient funds". + // + // Even with SFFO, the wallet can only afford to send 200 BTC. + // If the wallet does not properly exclude preset inputs from the pool of available coins + // prior to coin selection, it may create a transaction that does not fund the full payment + // amount or, through SFFO, incorrectly reduce the recipient's amount by the difference + // between the original target and the wrongly counted inputs (in this case 99 BTC) + // so that the recipient's amount is no longer equal to the user's selected target of 299 BTC. + + // First case, use 'subtract_fee_from_outputs=true' + util::Result res_tx = CreateTransaction(*wallet, recipients, /*change_pos*/-1, coin_control); + BOOST_CHECK(!res_tx.has_value()); + + // Second case, don't use 'subtract_fee_from_outputs'. + recipients[0].fSubtractFeeFromAmount = false; + res_tx = CreateTransaction(*wallet, recipients, /*change_pos*/-1, coin_control); + BOOST_CHECK(!res_tx.has_value()); +} + BOOST_AUTO_TEST_SUITE_END() } // namespace wallet -- cgit v1.2.3 From cac2725fd0f5baeb741dfe079a87332784c2adc7 Mon Sep 17 00:00:00 2001 From: furszy Date: Tue, 22 Nov 2022 11:43:44 -0300 Subject: test: bugfix, coinselector_test, use 'CoinsResult::Erase/Add' instead of direct member access Aside from the cleanup, this solves a bug in the following-up commit. Because, in these tests, we are manually adding/erasing outputs from the CoinsResult object but never updating the internal total amount field. --- src/wallet/test/coinselector_tests.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/wallet') diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index c76538ad48..c764264cd7 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -83,7 +83,7 @@ static void add_coin(CoinsResult& available_coins, CWallet& wallet, const CAmoun assert(ret.second); CWalletTx& wtx = (*ret.first).second; const auto& txout = wtx.tx->vout.at(nInput); - available_coins.coins[OutputType::BECH32].emplace_back(COutPoint(wtx.GetHash(), nInput), txout, nAge, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, wtx.GetTxTime(), fIsFromMe, feerate); + available_coins.Add(OutputType::BECH32, {COutPoint(wtx.GetHash(), nInput), txout, nAge, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, wtx.GetTxTime(), fIsFromMe, feerate}); } /** Check if SelectionResult a is equivalent to SelectionResult b. @@ -342,7 +342,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) coin_control.Select(select_coin.outpoint); PreSelectedInputs selected_input; selected_input.Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs); - available_coins.coins[OutputType::BECH32].erase(available_coins.coins[OutputType::BECH32].begin()); + available_coins.Erase({available_coins.coins[OutputType::BECH32].begin()->outpoint}); coin_selection_params_bnb.m_effective_feerate = CFeeRate(0); const auto result10 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb); BOOST_CHECK(result10); @@ -402,7 +402,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) coin_control.Select(select_coin.outpoint); PreSelectedInputs selected_input; selected_input.Insert(select_coin, coin_selection_params_bnb.m_subtract_fee_outputs); - available_coins.coins[OutputType::BECH32].erase(++available_coins.coins[OutputType::BECH32].begin()); + available_coins.Erase({(++available_coins.coins[OutputType::BECH32].begin())->outpoint}); const auto result13 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb); BOOST_CHECK(EquivalentResult(expected_result, *result13)); } @@ -974,7 +974,7 @@ BOOST_AUTO_TEST_CASE(SelectCoins_effective_value_test) cc.SelectExternal(output.outpoint, output.txout); const auto preset_inputs = *Assert(FetchSelectedInputs(*wallet, cc, cs_params)); - available_coins.coins[OutputType::BECH32].erase(available_coins.coins[OutputType::BECH32].begin()); + available_coins.Erase({available_coins.coins[OutputType::BECH32].begin()->outpoint}); const auto result = SelectCoins(*wallet, available_coins, preset_inputs, target, cc, cs_params); BOOST_CHECK(!result); -- cgit v1.2.3 From c4e3b7d6a154e82cdb902fd7bcb7b725aebde5ea Mon Sep 17 00:00:00 2001 From: furszy Date: Tue, 22 Nov 2022 11:51:33 -0300 Subject: wallet: SelectCoins, return early if wallet's UTXOs cannot cover the target The CoinsResult class will now count the raw total amount and the effective total amount internally (inside the 'CoinsResult::Add' and 'CoinsResult::Erase' methods). So there is no discrepancy between what we add/erase and the total values. (which is what was happening on the coinselector_test because the 'CoinsResult' object is manually created there, and we were not keeping the total amount in sync with the outputs being added/removed). --- src/wallet/coinselection.h | 2 ++ src/wallet/spend.cpp | 23 ++++++++++++++++++++--- src/wallet/spend.h | 4 +++- 3 files changed, 25 insertions(+), 4 deletions(-) (limited to 'src/wallet') diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index b23dd10867..b02e006435 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -110,6 +110,8 @@ public: assert(effective_value.has_value()); return effective_value.value(); } + + bool HasEffectiveValue() const { return effective_value.has_value(); } }; /** Parameters for one iteration of Coin Selection. */ diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index 5f4e3e79c7..19f9048dbf 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -106,7 +106,13 @@ void CoinsResult::Erase(const std::unordered_set= params.min_sum_amount) { @@ -575,6 +584,14 @@ std::optional SelectCoins(const CWallet& wallet, CoinsResult& a return result; } + // Return early if we cannot cover the target with the wallet's UTXO. + // We use the total effective value if we are not subtracting fee from outputs and 'available_coins' contains the data. + CAmount available_coins_total_amount = coin_selection_params.m_subtract_fee_outputs ? available_coins.total_amount : + (available_coins.total_effective_amount.has_value() ? *available_coins.total_effective_amount : 0); + if (selection_target > available_coins_total_amount) { + return std::nullopt; // Insufficient funds + } + // Start wallet Coin Selection procedure auto op_selection_result = AutomaticCoinSelection(wallet, available_coins, selection_target, coin_control, coin_selection_params); if (!op_selection_result) return op_selection_result; diff --git a/src/wallet/spend.h b/src/wallet/spend.h index df57fc1362..8612ce49ad 100644 --- a/src/wallet/spend.h +++ b/src/wallet/spend.h @@ -51,8 +51,10 @@ struct CoinsResult { void Shuffle(FastRandomContext& rng_fast); void Add(OutputType type, const COutput& out); - /** Sum of all available coins */ + /** Sum of all available coins raw value */ CAmount total_amount{0}; + /** Sum of all available coins effective value (each output value minus fees required to spend it) */ + std::optional total_effective_amount{0}; }; struct CoinFilterParams { -- cgit v1.2.3 From 3282fad59908da328f8323e1213344fe58ccf69e Mon Sep 17 00:00:00 2001 From: S3RK <1466284+s3rk@users.noreply.github.com> Date: Tue, 29 Nov 2022 19:40:40 -0300 Subject: wallet: add assert to SelectionResult::Merge for safety --- src/wallet/coinselection.cpp | 4 ++++ src/wallet/coinselection.h | 6 ++++++ 2 files changed, 10 insertions(+) (limited to 'src/wallet') diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index a8be6cd83a..b889d31928 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -452,12 +452,16 @@ void SelectionResult::AddInputs(const std::set& inputs, bool subtract_f void SelectionResult::Merge(const SelectionResult& other) { + // Obtain the expected selected inputs count after the merge (for now, duplicates are not allowed) + const size_t expected_count = m_selected_inputs.size() + other.m_selected_inputs.size(); + m_target += other.m_target; m_use_effective |= other.m_use_effective; if (m_algo == SelectionAlgorithm::MANUAL) { m_algo = other.m_algo; } util::insert(m_selected_inputs, other.m_selected_inputs); + assert(m_selected_inputs.size() == expected_count); } const std::set& SelectionResult::GetInputSet() const diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index b02e006435..2ab4061a9b 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -316,6 +316,12 @@ public: void ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee); [[nodiscard]] CAmount GetWaste() const; + /** + * Combines the @param[in] other selection result into 'this' selection result. + * + * Important note: + * There must be no shared 'COutput' among the two selection results being combined. + */ void Merge(const SelectionResult& other); /** Get m_selected_inputs */ -- cgit v1.2.3 From 7362f8e5e2497bc1ef27bfa871fc6dd306dd33c3 Mon Sep 17 00:00:00 2001 From: furszy Date: Fri, 2 Dec 2022 12:33:22 -0300 Subject: refactor: make CoinsResult total amounts members private --- src/wallet/spend.cpp | 8 ++++---- src/wallet/spend.h | 4 ++++ 2 files changed, 8 insertions(+), 4 deletions(-) (limited to 'src/wallet') diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index 19f9048dbf..52d10b74b5 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -332,7 +332,7 @@ CoinsResult AvailableCoins(const CWallet& wallet, // Checks the sum amount of all UTXO's. if (params.min_sum_amount != MAX_MONEY) { - if (result.total_amount >= params.min_sum_amount) { + if (result.GetTotalAmount() >= params.min_sum_amount) { return result; } } @@ -356,7 +356,7 @@ CoinsResult AvailableCoinsListUnspent(const CWallet& wallet, const CCoinControl* CAmount GetAvailableBalance(const CWallet& wallet, const CCoinControl* coinControl) { LOCK(wallet.cs_wallet); - return AvailableCoins(wallet, coinControl).total_amount; + return AvailableCoins(wallet, coinControl).GetTotalAmount(); } const CTxOut& FindNonChangeParentOutput(const CWallet& wallet, const CTransaction& tx, int output) @@ -586,8 +586,8 @@ std::optional SelectCoins(const CWallet& wallet, CoinsResult& a // Return early if we cannot cover the target with the wallet's UTXO. // We use the total effective value if we are not subtracting fee from outputs and 'available_coins' contains the data. - CAmount available_coins_total_amount = coin_selection_params.m_subtract_fee_outputs ? available_coins.total_amount : - (available_coins.total_effective_amount.has_value() ? *available_coins.total_effective_amount : 0); + CAmount available_coins_total_amount = coin_selection_params.m_subtract_fee_outputs ? available_coins.GetTotalAmount() : + (available_coins.GetEffectiveTotalAmount().has_value() ? *available_coins.GetEffectiveTotalAmount() : 0); if (selection_target > available_coins_total_amount) { return std::nullopt; // Insufficient funds } diff --git a/src/wallet/spend.h b/src/wallet/spend.h index 8612ce49ad..2b861c2361 100644 --- a/src/wallet/spend.h +++ b/src/wallet/spend.h @@ -51,6 +51,10 @@ struct CoinsResult { void Shuffle(FastRandomContext& rng_fast); void Add(OutputType type, const COutput& out); + CAmount GetTotalAmount() { return total_amount; } + std::optional GetEffectiveTotalAmount() {return total_effective_amount; } + +private: /** Sum of all available coins raw value */ CAmount total_amount{0}; /** Sum of all available coins effective value (each output value minus fees required to spend it) */ -- cgit v1.2.3