wallet: bugfix, invalid CoinsResult cached total amount

furszy commented at 3:13 pm on November 23, 2022: member

This comes with #26559.

Solving few bugs inside the wallet’s transaction creation process and adding test coverage for them. Plus, making use of the CoinsResult::total_amount cached value inside the Coin Selection process to return early if we don’t have enough funds to cover the target amount.

Bugs

The CoinsResult::Erase method removes only one output from the available coins vector (there is a loop break that should have never been there) and not all the preset inputs.

Which on master is not a problem, because since #25685 we are no longer using the method. But, it’s a bug on v24 (check #26559).

This method it’s being fixed and not removed because I’m later using it to solve another bug inside this PR.
As we update the total cached amount of the CoinsResult object inside AvailableCoins and we don’t use such function inside the coin selection tests (we manually load up the CoinsResult object), there is a discrepancy between the outputs that we add/erase and the total amount cached value.

Improvements

This makes use of the CoinsResult total amount field to early return with an “Insufficient funds” error inside Coin Selection if the tx target amount is greater than the sum of all the wallet available coins plus the preset inputs amounts (we don’t need to perform the entire coin selection process if we already know that there aren’t enough funds inside our wallet).

Test Coverage

Adds test coverage for the duplicated preset input selection bug that we have in v24. Where the wallet invalidly selects the preset inputs twice during the Coin Selection process. Which ends up with a “good” Coin Selection result that does not cover the total tx target amount. Which, alone, crashes the wallet due an insane fee. But.. to make it worst, adding the subtract fee from output functionality to this mix ends up with the wallet by-passing the “insane” fee assertion, decreasing the output amount to fulfill the insane fee, and.. sadly, broadcasting the tx to the network.
Adds test coverage for the CoinsResult::Erase method.

DrahtBot commented at 3:13 pm on November 23, 2022: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	achow101, josibake
Stale ACK	Xekyo, S3RK, glozow

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#26573 (Wallet: don’t underestimate the fees when spending a Taproot output by darosior)
#26567 (Wallet: estimate the size of signed inputs using descriptors by darosior)
#25729 (wallet: Check max transaction weight in CoinSelection by aureleoules)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label Wallet on Nov 23, 2022

in src/wallet/spend.cpp:114 in 7f6abb3915 outdated

117+        auto remove_it = std::remove_if(vec.begin(), vec.end(), [&](const COutput& coin) {
118+            auto it = coins_to_remove.find(coin.outpoint);
119+            if (it == coins_to_remove.end()) return false;
120+
121+            // remove coin
122+            coins_to_remove.erase(it);

achow101 commented at 4:39 pm on November 23, 2022:

In 7f6abb39159cd55b6c9193630ca4c3d9ae551be6 “wallet: bugfix, ‘CoinsResult::Erase’ is erasing only one output of the set”

How come we need to have coins_to_remove and erase the removed coins from it? coins_to_remove isn’t being used anywhere else so this doesn’t seem to be doing anything?

furszy commented at 9:30 pm on November 23, 2022:

It’s to decrease the search time while moving across the CoinsResult vectors.

Erase receives a const set with all the coins that needs to be removed from the CoinsResult internal vectors. So, what we do is loop across each coins vector and, for each coin inside them, we test whether the coin is inside the set of coins provided by the caller, if it’s there, then we update the internal state and return true so std:.remove_if does its magic. (bolded the important part)

So, if we remove coins as we find them on the CoinsResult vectors from the to_remove set, we will continually search inside a container with less elements up until there is none and we can stop the search earlier.

achow101 commented at 9:50 pm on November 23, 2022:

I don’t think that’s really a useful optimization since outs is likely to be very small. If we are concerned about the complexity of find, then I think it would be better to use an unordered_set rather than erasing after each removal.

This isn’t really a blocking comment, I just found it a bit confusing.

furszy commented at 0:27 am on November 24, 2022:

yeah, an unordered_set sounds good too.

still, what I wanted to add (and I actually didn’t add it for some reason..) is the capability to stop early if the set has no elements. E.g. if the wallet has 100k UTXO inside, the preset inputs set is small, and the coins appear early in the loop: the process could stop right away (no need to keep traversing the entire available coins vector if we already found them).

but.. as this is primarily to solve the dangerous bug in v24. Could go ahead with the unordered_set, make the code simpler, and leave any optimization for later.

achow101 commented at 4:39 pm on November 23, 2022: member

Good catch! Unfortunate that this was found right as we’re doing the 24.0 release.

furszy force-pushed on Nov 24, 2022

fanquake requested review from murchandamus on Nov 24, 2022

fanquake requested review from S3RK on Nov 24, 2022

in test/functional/rpc_fundrawtransaction.py:1227 in f20f88f60e outdated

1222+        for _ in range(10):
1223+            outputs[wallet.getnewaddress(address_type="bech32")] = 5
1224+        self.nodes[0].sendmany("", outputs)
1225+        self.generate(self.nodes[0], 1)
1226+
1227+        # Select the preset inputs and lock the rest of the coins

S3RK commented at 3:45 pm on November 26, 2022:

Is locking here necessary? Can we just fund the wallets with 2 coins instead of 10?

furszy commented at 2:46 pm on November 28, 2022:

let me double check it, IIRC I added it to make the wallet have enough funds in case we have an early balance check in the flow.

furszy commented at 7:32 pm on November 28, 2022:

All good, just removed it. Seems that I was just over-thinking it.

in src/wallet/test/spend_tests.cpp:125 in d8e195bc3d outdated

120+
121+    LOCK(wallet->cs_wallet);
122+    auto available_coins = AvailableCoins(*wallet);
123+    std::vector<COutput> coins = available_coins.All();
124+    std::set<COutPoint> preset_inputs = {coins[0].outpoint, coins[1].outpoint};
125+    // Lock the rest of the coins

S3RK commented at 4:33 pm on November 26, 2022:

Same question here. Do we really need to lock the coins?

furszy commented at 7:33 pm on November 28, 2022:

not really, removed it. Thanks

in src/wallet/test/spend_tests.cpp:115 in d8e195bc3d outdated

111@@ -112,5 +112,38 @@ BOOST_FIXTURE_TEST_CASE(FillInputToWeightTest, BasicTestingSetup)
112     // Note: We don't test the next boundary because of memory allocation constraints.
113 }
114 
115+BOOST_FIXTURE_TEST_CASE(wallet_duplicated_preset_inputs_test, TestChain100Setup)

S3RK commented at 4:36 pm on November 26, 2022:

nit: I’m not sure having second test provides enough extra value. I’d rather keep one, but ultimately up to you.

furszy commented at 2:53 pm on November 28, 2022:

yeah. I almost remove it but.. ended up leaving because (1) the severity of the bug and (2) because it’s easier to debug and assert that the code is failing where is supposed to be failing (in the functional test case, as we use the send RPC command, we do have other stuff involved).

I’m fine either way, if this still doesn’t convince you and more people don’t see it useful, can remove it for sure.

josibake commented at 2:05 pm on November 29, 2022:

I also agree that the second unit test (which isn’t really a unit test) seems redundant and also a little confusing to me. I think the unit test for CoinsResult::Erase in an earlier commit is correct for a unit test and the functional test is better suited for testing the wallet behavior

in src/wallet/spend.cpp:590 in f20f88f60e outdated

583@@ -575,6 +584,14 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
584         return result;
585     }
586 
587+    // Return early if we cannot cover the target with the wallet's UTXO.
588+    // We use the total effective value if we are not subtracting fee from outputs and 'available_coins' contains the data.
589+    CAmount available_coins_total_amount = coin_selection_params.m_subtract_fee_outputs ? available_coins.total_amount :
590+            (available_coins.total_effective_amount.has_value() ? *available_coins.total_effective_amount : available_coins.total_amount);

S3RK commented at 5:09 pm on November 26, 2022:

I don’t think it’s correct to fallback on available_coins.total_amount when we don’t do SFFO.

with SFFO we must have effective amount, if we don’t - something went wrong.

furszy commented at 4:18 pm on November 28, 2022:

Hmm, need a bit of context here. Guess that you are saying that because, with SFFO, the wallet needs to select a group of UTXOs that will be able to pay for themselves? So, the entire coin selection relies on the effective value existence so.. if it’s not there there is a bug?

achow101 commented at 5:08 pm on November 28, 2022:

By the time we get here, if total_effective_amount doesn’t have a value, that means that none of the UTXOs in this wallet were solvable, so we can’t do any coin selection here in that case. So I think it would be better to always return early in that case.

furszy commented at 6:43 pm on November 28, 2022:

By the time we get here, if total_effective_amount doesn’t have a value, that means that none of the UTXOs in this wallet were solvable, so we can’t do any coin selection here in that case

Hmm, code wise, that doesn’t seems to be what is happening.

At the COutput constructor, if the coin isn’t solvable then effective_value will be equal to the nominal output value. So it will always have an effective value during the tx creation process.

The only way that a COutput has no effective_value is when we don’t provide the feerate param to AvailableCoins (which happens on all the flows that uses AvailableCoins that are not part of the tx creation process).

achow101 commented at 6:54 pm on November 28, 2022:

Oh, hmm, I thought it checked input_bytes as well.

In that case, total_effective_amount should always have a value if we have any coins. If it isn’t set, then we don’t have any coins and we can still return early.

in src/wallet/spend.h:61 in f20f88f60e outdated

50@@ -51,8 +51,10 @@ struct CoinsResult {
51     void Shuffle(FastRandomContext& rng_fast);
52     void Add(OutputType type, const COutput& out);
53 
54-    /** Sum of all available coins */
55+    /** Sum of all available coins raw value */
56     CAmount total_amount{0};
57+    /** Sum of all available coins effective value (each output value minus fees required to spend it) */
58+    std::optional<CAmount> total_effective_amount{0};

S3RK commented at 5:24 pm on November 26, 2022:

note to self: not a huge fan of how this looks like with optional. The code would look much simpler if we can just always pass a fee rate to AvailableCoins (we can set it 0 by default). Can’t make my mind which way is better…

furszy commented at 6:56 pm on November 28, 2022:

I would agree on always passing the fee rate to AvailableCoins if we were using the function only for the tx creation process, but we are using it for other processes that don’t require to calculate the effective value nor the output spending fee.

We definitely can improve it but I don’t think that this PR is the best place to do it.

Side from that, from my side, have some plans to re-write the AvailableCoins functionality differently post #25806 (because, after it, will be able to continually connect outputs to existent output groups, outside of the coin selection process which is currently forcing us to do the whole calculation on-demand).

S3RK commented at 5:33 pm on November 26, 2022: contributor

oh wow, that’s a nasty bug.

Almost Code Review ACK modulo use of available_coins.total_amount with SFFO in the last commit.

I was quite surprised something like this wasn’t caught by some assert. So I dig up and maybe we can add something like e783af37a77bbe91cd6ec8802292838377d9a0aa while you’re at it

Sjors commented at 1:54 pm on November 28, 2022: member

Asking here instead of in the backport: is this only in v24 or also earlier versions?

fanquake commented at 2:03 pm on November 28, 2022: member

Asking here instead of in the backport: is this only in v24 or also earlier versions?

My understanding is only v24.x. Seems like the buggy behaviour was introduced in #24584 + #25734?

fanquake requested review from josibake on Nov 28, 2022

furszy commented at 2:04 pm on November 28, 2022: member

Asking here instead of in the backport: is this only in v24 or also earlier versions?

Yeah. @Sjors only for v24. The dangerous bug was introduced in #25734 which is only on v24, and after branching off, we merged #25685 which fixed it without noticing it.

furszy force-pushed on Nov 28, 2022

furszy commented at 7:48 pm on November 28, 2022: member

Feedback tackled, thanks @S3RK and @achow101.

Changes:

In the tests, removed the unneeded coins lock.
Now SelectCoins returns early if the wallet’s available coins total_effective_amount is not available (it does not fallback to use the raw total amount anymore).

luke-jr commented at 4:10 am on November 29, 2022: member

I think probably CoinsResult::coins should be a std::map<OutputType, std::unordered_set<COutput>> instead of [map of] vectors. It’s too strange that we could end up with the same output in there twice. Maybe even an assert failure if we try to add the same ones twice?

luke-jr changes_requested

luke-jr commented at 4:12 am on November 29, 2022: member

The bugfix should also be done in its own commit, absent any refactoring.

I think this means just dropping the break and replacing the find_if with remove_if?

in src/wallet/spend.cpp:109 in 65126cb522 outdated

112-            vec.erase(i);
113-            break;
114-        }
115+    for (auto& [type, vec] : coins) {
116+        auto remove_it = std::remove_if(vec.begin(), vec.end(), [&](const COutput& coin) {
117+            return coins_to_remove.count(coin.outpoint) == 1;

josibake commented at 1:50 pm on November 29, 2022:

in https://github.com/bitcoin/bitcoin/pull/26560/commits/65126cb522b28f53a020ce56826f7d15560241c9:

Shouldn’t this be a std::find? count will traverse the entire coins_to_remove vector whereas std::find will stop as soon as it finds the outpoint.

furszy commented at 3:22 pm on November 29, 2022:

coins_to_remove is an unordered set, not a vector. Internally, uses a hash table where keys are hashed into indices. So, time complexity wise, count and find should take the same constant time.

josibake commented at 4:49 pm on November 29, 2022:

ah, good point! i forgot how find \ count work is dependent on the underlying container

in src/wallet/spend.h:50 in 65126cb522 outdated

46@@ -47,7 +47,7 @@ struct CoinsResult {
47      * i.e., methods can work with individual OutputType vectors or on the entire object */
48     size_t Size() const;
49     void Clear();
50-    void Erase(std::set<COutPoint>& preset_coins);
51+    void Erase(const std::unordered_set<COutPoint, SaltedOutpointHasher>& outs);

josibake commented at 1:52 pm on November 29, 2022:

in https://github.com/bitcoin/bitcoin/pull/26560/commits/65126cb522b28f53a020ce56826f7d15560241c9:

nit, but can we keep the parameter names consistent? either use outs in both places or coins_to_remove in both places?

furszy commented at 3:22 pm on November 29, 2022:

yeah, thanks

in test/functional/rpc_fundrawtransaction.py:1261 in a07c3b4cfd outdated

1248+        # First case, use 'subtract_fee_from_outputs' to make the wallet create a tx that pays an insane fee on v24.0.
1249+        assert_raises_rpc_error(-4, "Insufficient funds", wallet.send, outputs=[{wallet.getnewaddress(address_type="bech32"): 14}], options=options)
1250+
1251+        # Second case, don't use 'subtract_fee_from_outputs' to make the wallet crash due the insane fee on v24.0
1252+        del options["subtract_fee_from_outputs"]
1253+        assert_raises_rpc_error(-4, "Insufficient funds", wallet.send, outputs=[{wallet.getnewaddress(address_type="bech32"): 14}], options=options)

josibake commented at 2:08 pm on November 29, 2022:

As it’s written, the test comment doesn’t make sense unless you have the background context. The comment describes a certain type of failure (insane fee, or wallet crash), but the assertion seems to check something entirely different. Perhaps it’s worth writing a long comment which explains why you are checking for insufficient funds and what you would expect if the insufficient funds assert fails.

furszy commented at 3:39 pm on November 29, 2022:

yeah ok. I added the topic background inside the commit description that introduces the tests. But.. agree that, at least in this post-mortem bug case, the link to the PR that fixes it and further comments inside the test code would make it more digestible. Thanks.

in src/wallet/spend.cpp:110 in 1b14bd7ac7 outdated

105@@ -106,7 +106,13 @@ void CoinsResult::Erase(const std::unordered_set<COutPoint, SaltedOutpointHasher
106 {
107     for (auto& [type, vec] : coins) {
108         auto remove_it = std::remove_if(vec.begin(), vec.end(), [&](const COutput& coin) {
109-            return coins_to_remove.count(coin.outpoint) == 1;
110+            // remove it if it's on the set
111+            if (coins_to_remove.count(coin.outpoint) == 0) return false;

josibake commented at 2:10 pm on November 29, 2022:

in https://github.com/bitcoin/bitcoin/pull/26560/commits/1b14bd7ac77027351a1e5b3ef21fb2d1de659efd:

same comment from before, I’d suggest using find here.

josibake commented at 2:16 pm on November 29, 2022:

also, might be worth adding the if () return false; in the earlier commit so you don’t end up touching this line twice?

furszy commented at 3:26 pm on November 29, 2022:

in 1b14bd7:

same comment from before, I’d suggest using find here.

answered in the first commit comment #26560 (review)

also, might be worth adding the if () return false; in the earlier commit so you don’t end up touching this line twice?

not sure what you meant, the first commit has a single line (the count function will either return 1 if the element is in the set or 0 if not).

0return coins_to_remove.count(coin.outpoint) == 1;

josibake commented at 4:55 pm on November 29, 2022:

yeah, more just saying you could write the first commit like:

0if (coins_to_remove.count(coin.outpoint) == 0) return false;
1return true;

because you know that in a later commit you will add the total_amount and total_effective code, and this way you avoid re-writing the same line twice. it doesn’t really matter in this case, just a suggestion. in general, it can be confusing as a reviewer when the same line of code is edited multiple times in different commits

furszy commented at 5:32 pm on November 29, 2022:

Ideally, commits should introduce atomic changes. Did the first one in this way so it can be backported without any dependency into a different branch (due the lack of #25685, v24 branch cannot cherry-pick https://github.com/bitcoin/bitcoin/commit/1b14bd7ac77027351a1e5b3ef21fb2d1de659efd).

So, we would only have those lines inside v24, which I think that is ugly. The current one looks better.

josibake approved

josibake commented at 2:23 pm on November 29, 2022: member

ACK https://github.com/bitcoin/bitcoin/pull/26560/commits/1b14bd7ac77027351a1e5b3ef21fb2d1de659efd

Glad you caught this! Surprised and pretty bummed this slipped through in #25734 :disappointed:

Left a few suggestions, but non-blocking.

furszy commented at 3:10 pm on November 29, 2022: member

I think probably CoinsResult::coins should be a std::map<OutputType, std::unordered_set<COutput>> instead of [map of] vectors. It’s too strange that we could end up with the same output in there twice. Maybe even an assert failure if we try to add the same ones twice? @luke-jr: we can’t end up with the same output twice there. That struct is loaded inside AvailableCoins which traverses the wallet’s txes map once. In v24, where we don’t have #25685 merge, the preset inputs were fetched twice: first inside AvailableCoins which was appending them to the CoinsResult vectors and secondly inside SelectCoins where we were manually fetching them from the wallet txes map here (by calling GetWalletTx(outpoint)). Then, SelectCoins was removing the preset inputs from the CoinsResult vectors before start the automatic coin selection process so the process does not select them (bug was here, the Erase function was not removing them). Then, at the end of the selection process, we merge both results (the preset inputs selection result and the automatic coin selection result).

wallet: bugfix, 'CoinsResult::Erase' is erasing only one output of the set

The loop break shouldn't have being there.

f930aefff9

josibake commented at 5:03 pm on November 29, 2022: member

fwiw, I ran the failing CI test locally and it passed, so I think all you need to do is restart the test

furszy force-pushed on Nov 29, 2022

furszy commented at 10:57 pm on November 29, 2022: member

Updated per feedback, thanks everyone. Small diff.

Changes:

Per @S3RK feedback, cherry-picked the simple fallback assertion (eb76557). I still think that we might want to merge different SelectionResult objects that share some outputs in the future but.. now it’s definitely not the right time to do it.
Per @josibake feedback, added #26559 mention in the functional test cases and few more details in the comments.

furszy force-pushed on Nov 29, 2022

achow101 commented at 11:06 pm on November 29, 2022: member

ACK eb76557331b4f34b568da1d9c589c7005d7ab46d

josibake commented at 9:56 am on November 30, 2022: member

ACK https://github.com/bitcoin/bitcoin/commit/eb76557331b4f34b568da1d9c589c7005d7ab46d

reviewed the diff, looks good

in src/wallet/test/coinselector_tests.cpp:1008 in 4ba9351276 outdated

1003+        std::unordered_set<COutPoint, SaltedOutpointHasher> outs_to_remove;
1004+        const auto& coins = available_coins.All();
1005+        for (int i = 0; i < 2; i++) {
1006+            outs_to_remove.emplace(coins[i].outpoint);
1007+        }
1008+        available_coins.Erase(outs_to_remove);

glozow commented at 2:51 pm on November 30, 2022:

nit: Could add a check that you also haven’t removed things that weren’t supposed to be removed. For example, a BOOST_CHECK_EQUAL(available_coins.Size(), 8); would catch a case of, for example, accidentally removing the entire map entry for that output type instead of an element in the vector of the entry.

furszy commented at 3:35 pm on December 2, 2022:

sounds good

in test/functional/rpc_fundrawtransaction.py:1248 in 01d5cf9d1d outdated

1243+                },
1244+                {
1245+                    "txid": preset_inputs[1]["txid"],
1246+                    "vout": preset_inputs[1]["vout"]
1247+                },
1248+            ],

glozow commented at 2:55 pm on November 30, 2022:

nit: why can’t you just make this equal to preset_inputs - maybe I’m missing something?

0           "inputs": preset_inputs,

furszy commented at 3:36 pm on December 2, 2022:

nop, you are right. I was doing this stuff manually at the beginning, can simplify it now. Thanks

in src/wallet/test/spend_tests.cpp:134 in 01d5cf9d1d outdated

129+    coin_control.m_allow_other_inputs = true;
130+    for (const auto& outpoint : preset_inputs) {
131+        coin_control.Select(outpoint);
132+    }
133+
134+    // First case, use 'subtract_fee_from_outputs' to make the wallet create a tx that pays an insane fee on v24.0.

murchandamus commented at 7:54 pm on November 30, 2022:

Just a nit, but the term “insane fee” had me thinking that this test has us paying a huge amount of fees, something that would be conflicting with our sanity checks.

fanquake commented at 4:18 pm on December 1, 2022:

I don’t think we should be adding specific version numbers to comments, because this just becomes (mostly) incorrect, once we’ve merged a backport, and doesn’t really provide any value otherwise.

0    // First case, use 'subtract_fee_from_outputs' to make the wallet create a tx that pays an insane fee.

furszy commented at 4:35 pm on December 2, 2022:

yeah ok, I used that term because the nFeeRet calculation prior to the SFFO process, can go insanely high based on the duplicated preset inputs, then we deduct it from the recipient’s target. will improve the documentation.

furszy commented at 5:37 pm on December 2, 2022:

done

in src/wallet/test/spend_tests.cpp:152 in 01d5cf9d1d outdated

131+        coin_control.Select(outpoint);
132+    }
133+
134+    // First case, use 'subtract_fee_from_outputs' to make the wallet create a tx that pays an insane fee on v24.0.
135+    util::Result<CreatedTransactionResult> res_tx = CreateTransaction(*wallet, recipients, /*change_pos*/-1, coin_control);
136+    BOOST_CHECK(!res_tx.has_value());

murchandamus commented at 7:55 pm on November 30, 2022:

It was not clear to me at first why the expected outcome is that we don’t create a transaction. That could have perhaps been captured in the comment instead: the wallet shouldn’t have sufficient funds to create the tx, but the bug caused us previously to assume that preset UTXOs were available twice and thus overestimate our funding.

glozow commented at 9:59 am on December 5, 2022:

Marking this as resolved - it now explains there are insufficient funds.

in test/functional/rpc_fundrawtransaction.py:1222 in 01d5cf9d1d outdated

1217+        # a tx that sends more coins than what inputs are covering for.
1218+        #
1219+        # Which, combined with the subtract fee from outputs option,
1220+        # makes the wallet generate and broadcast a tx that pays
1221+        # up to the sum of all the preset inputs, minus one, amounts in
1222+        # fee :(.

murchandamus commented at 7:56 pm on November 30, 2022:

I see, that is the context that I was missing above! :)

in src/wallet/spend.cpp:114 in a45ecd64ba outdated

110+            // remove it if it's on the set
111+            if (coins_to_remove.count(coin.outpoint) == 0) return false;
112+
113+            // update cached amounts
114+            total_amount -= coin.txout.nValue;
115+            if (coin.HasEffectiveValue()) total_effective_amount = *total_effective_amount - coin.GetEffectiveValue();

murchandamus commented at 8:24 pm on November 30, 2022:

Are we sure that total_effective_value is always set here?

Maybe assume(total_effective_amount.has_value() here?

S3RK commented at 8:49 pm on November 30, 2022:

I had this question myself. I figured if we remove the coin with effective value, then the coin was added before, hence we have total_effective_value defined. Please correct me if my reasoning is flawed.

furszy commented at 4:32 pm on December 2, 2022:

yeah. As we only use CoinsResult::Add to append new coins: if we have the coin inside CoinsResult, and the coin has an effective value, then we must have total_effective_amount.

in src/wallet/spend.cpp:590 in a45ecd64ba outdated

583@@ -575,6 +584,14 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
584         return result;
585     }
586 
587+    // Return early if we cannot cover the target with the wallet's UTXO.
588+    // We use the total effective value if we are not subtracting fee from outputs and 'available_coins' contains the data.
589+    CAmount available_coins_total_amount = coin_selection_params.m_subtract_fee_outputs ? available_coins.total_amount :
590+            (available_coins.total_effective_amount.has_value() ? *available_coins.total_effective_amount : 0);

murchandamus commented at 8:35 pm on November 30, 2022:

We will never use SelectCoins() without a feerate. If you end up not having total_effective_amount here, something went terribly wrong. Perhaps just:

0    assume(available_coins.total_effective_amount.has_value());
1    CAmount available_coins_total_amount = coin_selection_params.m_subtract_fee_outputs ? available_coins.total_amount : *available_coins.total_effective_amount);

in src/wallet/coinselection.cpp:455 in eb76557331 outdated

451@@ -452,12 +452,16 @@ void SelectionResult::AddInputs(const std::set<COutput>& inputs, bool subtract_f
452 
453 void SelectionResult::Merge(const SelectionResult& other)
454 {
455+    // Obtain the expected selected inputs count after the merge (for now, duplicates are not allowed)

murchandamus commented at 8:38 pm on November 30, 2022:

0    // Store sum of combined input sets to check that no UTXO was used twice

furszy commented at 7:20 pm on December 2, 2022:

this relies on #26560 (review) (where we are talking about whether should include the assertion commit here or in a follow-up PR). Please, feel free to comment there.

murchandamus commented at 8:43 pm on November 30, 2022: contributor

ACK eb76557331b4f34b568da1d9c589c7005d7ab46d

in src/wallet/spend.h:61 in eb76557331 outdated

54 
55-    /** Sum of all available coins */
56+    /** Sum of all available coins raw value */
57     CAmount total_amount{0};
58+    /** Sum of all available coins effective value (each output value minus fees required to spend it) */
59+    std::optional<CAmount> total_effective_amount{0};

achow101 commented at 8:49 pm on November 30, 2022:

I think it would be useful to make total_amount, total_effective_amount, and coins private members to ensure that we are only adding/removing things with Add and Erase.

furszy commented at 5:36 pm on December 2, 2022:

done

S3RK commented at 8:55 pm on November 30, 2022: contributor

ACK eb76557331b4f34b568da1d9c589c7005d7ab46d

Will reack if you address nits

in src/wallet/coinselection.cpp:464 in eb76557331 outdated

459     m_use_effective |= other.m_use_effective;
460     if (m_algo == SelectionAlgorithm::MANUAL) {
461         m_algo = other.m_algo;
462     }
463     util::insert(m_selected_inputs, other.m_selected_inputs);
464+    assert(m_selected_inputs.size() == expected_count);

glozow commented at 10:23 am on December 1, 2022:

It’s a bit unclear to me how the assert added in eb76557331b4f34b568da1d9c589c7005d7ab46d is more safe? Wouldn’t this mean we still crash if we haven’t caught a similar bug before shipping?

glozow commented at 5:36 pm on December 1, 2022:

I suggest removing this last commit for this PR, and following up with an “add sanity checks to coin selection code” PR.

Of course we don’t want to create a bad transaction, but an assert would cause the user’s node to crash in case we have implemented it wrong. I think something better could be to add if(!Assume(...)) {return "sorry, something went wrong and transaction creation failed. please report this bug...";} which should stop the wallet from doing something horrible but also not crash. Apologies if this is bikesheddy - my concrete suggestion is to remove this for now, and do a followup PR for these types of changes. Other appropriate sanity checks could include AddInput() never adds an input that’s already there, SelectCoins result should cover selection_target, etc.

furszy commented at 4:19 pm on December 2, 2022:

Of course we don’t want to create a bad transaction, but an assert would cause the user’s node to crash in case we have implemented it wrong. I think something better could be to add if(!Assume(…)) {return “sorry, something went wrong and transaction creation failed. please report this bug…”;} which should stop the wallet from doing something horrible but also not crash.

Sure. I totally agree on using more Assume + user friendly error return messages than crashing the node with bare assertions.

I do actually implemented the capability to return error messages from the Coin Selection process inside #25806 -> 45bc10687f7b0131fd1c4575406b62f0608e2c01 few months ago (which is later used to return specific error messages instead of the current general “Insufficient Funds”. Which is required to implement your suggestions as we currently don’t have a way to return specific errors to the upper layers).

So, in short, could drop the last commit and open a follow-up PR moving forward with it, and more, for sure. But.. as I added the last commit by reviewers request, would be good to see if @S3RK is sync with this reasoning too (otherwise we would be going in circles). Note: Since, after the fix, this problem cannot realistically happen anymore, I’m fine to move either way.

achow101 commented at 9:01 pm on December 2, 2022:

I think it’s find to change this to Assume for this PR. We should probably try to avoid asserts in general.

S3RK commented at 7:53 am on December 5, 2022:

I’ll be fine with any of the following: keep asserts as I proposed, replaced them with Assume for this PR, remove the commit and address this in a follow up. With that said, here’s my strong opinion held lightly.

In the absence of ability of returning error messages from coin selection we have only two options. So the question is what is better within the scope of this PR: a) crash the node if assert is hit b) keep executing and potentially creating bad transactions.

Both are bad, but a) is strictly better, because recovering from a crash is much easier than from a bad tx. Replacing asserts and returning error messages could/should done in a follow up.

Now I agree that in general the wallet should not ever crash the node, but for this we need a general mechanism, something like multiprocess.

Also, my original suggestion included check within AddInput() and AddInputs(), as SelectionResult is not designed to work with duplicated inputs. This would make the class safe and its interface consistent.

maflcko commented at 9:33 am on December 5, 2022:

Another alternative (not sure if applicable here) would be to throw an exception. This should only crash when running in the gui, but not when called from the RPC server.

glozow commented at 10:46 am on December 5, 2022:

Right, so the question of how to implement sanity checks warrants additional discussion and/or refactoring but that discussion shouldn’t hold up this PR. Hence the recommendation to remove it.

I disagree that it’s harmless to have this assert after the fix; the bug can still exist or be reintroduced. But assuming these last few commits won’t be backported and we’ll have a followup PR to add/change sanity checks, fine with leaving it in this PR.

josibake commented at 4:45 pm on December 5, 2022:

It seems we all (mostly) agree that the assert is not ideal and how to deal with this should be addressed in a follow-up with more discussion, so I’d recommend dropping the commit so we don’t merge code that we know will be removed/refactored shortly after and to avoid any confusion when backporting commits from this PR for v24

furszy commented at 7:40 pm on December 5, 2022:

working on it 🚜 .

in test/functional/rpc_fundrawtransaction.py:1255 in eb76557331 outdated

1250+            "subtract_fee_from_outputs": [0],
1251+            "add_to_wallet": False
1252+        }
1253+
1254+        # First case, use 'subtract_fee_from_outputs' to make the wallet create a tx that pays an insane fee on v24.0.
1255+        # (further details in #26559).

fanquake commented at 4:22 pm on December 1, 2022:

There is no need to continually write v24.0 and (further details in [#26559](/bitcoin-bitcoin/26559/)) (here and below and further above). If you need to provide further context or details, please put them in the commit (or PR) descriptions, so they are available with the code change.

furszy commented at 4:38 pm on December 1, 2022:

those were my initial thoughts actually, added this on the last push per request #26560 (review).

seems that not everyone read the PR/commit description. But well, will just revert it.

josibake commented at 4:52 pm on December 1, 2022:

Sorry if this wasn’t clear in my comment, but I wasn’t suggesting adding v24 and links to the PR. My comment was to point out that the comments in the test didn’t match what was being checked in the assertion, which would be confusing to someone who didn’t have the background context. I understand this is a bit tricky because the test is for a bug that is no longer there, but ideally, the comment should explain why you are asserting “Insufficient Funds” in the happy case, and why, if the bug were present, that you would expect the “Insufficient Funds” assertion to fail. If you do want to link to the PR for more context, perhaps a top-level comment would be the best place?

furszy commented at 7:08 pm on December 2, 2022:

Ok, done thanks. Ready for another review round.

achow101 commented at 5:11 pm on December 1, 2022: member

Retracting my ACK for now. It seems that the comment wordings is confusing several people, so it would be good to have those be clear as to what the bugs are to avoid confusion in the future.

in test/functional/rpc_fundrawtransaction.py:1224 in eb76557331 outdated

1219+        # Which, combined with the subtract fee from outputs option,
1220+        # makes the wallet generate and broadcast a tx that pays
1221+        # up to the sum of all the preset inputs, minus one, amounts in
1222+        # fee :(.
1223+
1224+        # Create and fund the wallet with 2 UTXO of 5 BTC each

glozow commented at 5:52 pm on December 1, 2022:

0        self.log.info('Test wallet preset inputs are not double-counted or reused in coin selection')
1
2        # Create and fund the wallet with 2 UTXO of 5 BTC each, total balance 10 BTC.

furszy commented at 5:37 pm on December 2, 2022:

done

in test/functional/rpc_fundrawtransaction.py:1259 in eb76557331 outdated

1254+        # First case, use 'subtract_fee_from_outputs' to make the wallet create a tx that pays an insane fee on v24.0.
1255+        # (further details in #26559).
1256+        assert_raises_rpc_error(-4, "Insufficient funds", wallet.send, outputs=[{wallet.getnewaddress(address_type="bech32"): 14}], options=options)
1257+
1258+        # Second case, don't use 'subtract_fee_from_outputs' to make the wallet crash due the insane fee on v24.0.
1259+        # (further details in #26559).

glozow commented at 5:53 pm on December 1, 2022:

0        # Attempt to send 14 BTC. The wallet should exclude the preset inputs from the pool of
1        # available coins, realize that there is not enough money to fund the 14 BTC payment,
2        # and fail with "insufficient funds."
3        # Even with SFFO, the wallet can only afford to send 10 BTC.
4
5        # If the wallet does not properly exclude preset inputs from the pool of available coins
6        # prior to coin selection, it may create a transaction that does not fund the full payment
7        # amount or, through SFFO, incorrectly reduce the payment amount so that payment+fee is not
8        # equal to 14 BTC.
9        assert_raises_rpc_error(-4, "Insufficient funds", wallet.send, outputs=[{wallet.getnewaddress(address_type="bech32"): 14}], options=options)

furszy commented at 5:37 pm on December 2, 2022:

Updated, thanks

in test/functional/rpc_fundrawtransaction.py:1256 in eb76557331 outdated

1251+            "add_to_wallet": False
1252+        }
1253+
1254+        # First case, use 'subtract_fee_from_outputs' to make the wallet create a tx that pays an insane fee on v24.0.
1255+        # (further details in #26559).
1256+        assert_raises_rpc_error(-4, "Insufficient funds", wallet.send, outputs=[{wallet.getnewaddress(address_type="bech32"): 14}], options=options)

glozow commented at 5:56 pm on December 1, 2022:

Cherry-picking this test on top of 24.x, I can see that the wallet mistakenly uses a preset input twice and deducts the fee+5BTC from the payment, but the fee is actually exactly what is expected (since at the end the transaction only has 10BTC inputs and not 15): https://github.com/glozow/bitcoin/blob/test-n26560/test/functional/rpc_fundrawtransaction.py#L1250-L1266 @achow101 suggested that maybe nFeeRet from FundTransaction() or CreatedTransactionResult::fee could be incorrect but I wasn’t able to get a test to show that. @achow101 then pointed me to this code showing the sffo fee should be correctly set before CreateTransaction returns: https://github.com/bitcoin/bitcoin/blob/f668a3a85933512e7efc369b5b2922d44b4bad82/src/wallet/spend.cpp#L971-L1004

I could be mistaken, but in that case could you maybe write a test for v24.0 that shows what the expected vs actual fee are? Otherwise I’d suggest removing this from the comments/commit message/PR descriptions.

Having 2 test cases for sffo and non-sffo codepaths is still meaningful, but I think the current comment is misleading and can cause us to have trouble understanding this test in the future.

furszy commented at 7:17 pm on December 2, 2022:

Done, updated per feedback. Thanks.

Some context: The “insane fee” label came from the nFeeRet calculation. Which, in case of this bug, sets a high value then is later deducted from the recipient’s amount. Which.. as we spoke via dm, it’s true that this is internal to the wallet only.. so the description should be something like “double-counted preset inputs during Coin Selection incorrectly deduces the user’s selected recipient’s amount” (or something similar)

glozow commented at 5:58 pm on December 1, 2022: member

strong Concept ACK, I understand the bug has a significant impact and agree with the fix, but the documentation should be changed as I think it is currently incorrect and could be misleading to someone in the future trying to debug / reproduce what was wrong with v24.0.

TLDR I don’t think the “insane fee” bug is actually possible? I’ve made some suggestions for what I think the documentation should be inline (same suggestion wrt the commit messages).

furszy commented at 6:51 pm on December 1, 2022: member

Ok great, thanks everyone. Now I see where the confusion arises. Will be tackling all the feedback and updating the PR soon.

test: wallet, coverage for CoinsResult::Erase function 341ba7ffd8

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.

cf79384697

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.

cac2725fd0

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).

c4e3b7d6a1

wallet: add assert to SelectionResult::Merge for safety 3282fad599

refactor: make CoinsResult total amounts members private 7362f8e5e2

furszy force-pushed on Dec 2, 2022

glozow commented at 11:10 am on December 5, 2022: member

ACK cf793846978a8783c23b66ba6b4f3f30e83ff3eb (I assume these 3 are the backport commits) Verified that the tests in cf793846978a8783c23b66ba6b4f3f30e83ff3eb pass with the fix, fail on 24.x without the fix. I now think the documentation is accurate and would be helpful in a situation in which the test has broken again - thanks for taking the feedback!

ACK 7362f8e5e2497bc1ef27bfa871fc6dd306dd33c3, I assume there will be a followup PR to add coin selection sanity checks and we can discuss the best way to do that there.

glozow requested review from josibake on Dec 5, 2022

glozow requested review from achow101 on Dec 5, 2022

achow101 commented at 4:50 pm on December 5, 2022: member

ACK 7362f8e5e2497bc1ef27bfa871fc6dd306dd33c3

josibake commented at 4:53 pm on December 5, 2022: member

ACK 7362f8e

Give the discussion, I think it’s best if we drop https://github.com/bitcoin/bitcoin/pull/26560/commits/3282fad59908da328f8323e1213344fe58ccf69e and address it in a follow-up, but not worth holding the PR up if the author feels differently.

A big thanks to furszy for incorporating all of the feedback regarding the tests and documentation: everything is very clear now as to what’s being tested and why

achow101 merged this on Dec 5, 2022

achow101 closed this on Dec 5, 2022

sidhujag referenced this in commit 8dde7021c5 on Dec 5, 2022

fanquake referenced this in commit 195f0dfd0e on Dec 5, 2022

fanquake referenced this in commit 9d73176d00 on Dec 5, 2022

fanquake referenced this in commit 8b726bf556 on Dec 5, 2022

fanquake commented at 6:17 pm on December 5, 2022: member

Backported the 3 commits in #26616.

maflcko referenced this in commit 3afbc7d67d on Dec 6, 2022

achow101 referenced this in commit 3f8591d46b on Jan 3, 2023

sidhujag referenced this in commit cab438784e on Jan 4, 2023

484812 commented at 8:37 pm on March 27, 2023: none

Gj

furszy deleted the branch on May 27, 2023

bitcoin locked this on Aug 31, 2024

wallet: bugfix, invalid CoinsResult cached total amount #26560

Bugs

Improvements

Test Coverage

Reviews

Conflicts