wallet: Check max transaction weight in CoinSelection

aureleoules commented at 12:33 pm on July 28, 2022: member

This PR is an attempt to fix #5782.

I have added 4 test scenarios, 3 of them provided here #5782 (comment) (slightly modified to use a segwit wallet).

Here are my benchmarks :

PR

ns/op	op/s	err%	ins/op	cyc/op	IPC	bra/op	miss%	total	benchmark
1,466,341.00	681.97	0.6%	11,176,762.00	3,358,752.00	3.328	1,897,839.00	0.3%	0.02	`CoinSelection`

Master

ns/op	op/s	err%	ins/op	cyc/op	IPC	bra/op	miss%	total	benchmark
1,526,029.00	655.30	0.5%	11,142,188.00	3,499,200.00	3.184	1,994,156.00	0.2%	0.02	`CoinSelection`

fanquake added the label Wallet on Jul 28, 2022

aureleoules marked this as a draft on Jul 28, 2022

aureleoules force-pushed on Jul 28, 2022

DrahtBot commented at 3:56 pm on July 28, 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, w0xlt, furszy
Stale ACK	Xekyo

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:

#25806 (wallet: group outputs only once, decouple it from Coin Selection by furszy)

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.

aureleoules marked this as ready for review on Jul 28, 2022

achow101 commented at 5:20 pm on July 28, 2022: member

It shouldn’t be necessary to pass an entire CMutableTransaction to SelectCoins. CoinSelectionParams already has the information about the sizes of the rest of the transaction, modulo the change output. So a calculation can be done with that information.

Additionally, depending on the algorithm used, there may or may not be a change output, so it’s size will need to be accounted for in each size calculation.

aureleoules commented at 6:38 pm on July 28, 2022: member

Thank you for the feedback @achow101. Sizes in the CoinSelectionParams appear to be in “bytes” and not in “weight”, so I’m not sure how to use them as the multiplier of each field hasn’t been taken into account, unless I’m mistaken.

Additionally, depending on the algorithm used, there may or may not be a change output, so it’s size will need to be accounted for in each size calculation.

I’ll look into that thanks.

achow101 commented at 6:44 pm on July 28, 2022: member

The size is always vsize, so multiplyging by WITNESS_SCALE_FACTOR is sufficient to convert to weight. There will be some rounding error, but vsize always rounds up, so weight calculated in that way will always be a slight overestimate.

aureleoules force-pushed on Jul 28, 2022

aureleoules commented at 9:40 pm on July 28, 2022: member

I’ve removed the need for a dummy transaction. Though I’m not sure how to include the change output in the size calculation yet.

in src/wallet/spend.cpp:528 in 627b715f9d outdated

524 
525+    std::vector<SelectionResult> eligible_results;
526+    for (const auto& result : results) {
527+        int weight = coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR;
528+        for (const auto& coin : result.GetInputSet()) {
529+            weight += CalculateMaximumSignedInputSize(coin.txout, &wallet, &coin_control) * WITNESS_SCALE_FACTOR;

furszy commented at 9:43 pm on July 28, 2022:

Can directly use coin.input_bytes instead of calculating the size again.

aureleoules commented at 10:11 pm on July 28, 2022:

Thanks, that’s much better.

aureleoules force-pushed on Jul 28, 2022

aureleoules marked this as a draft on Jul 29, 2022

aureleoules marked this as ready for review on Jul 30, 2022

aureleoules commented at 3:15 pm on August 3, 2022: member

Pinging you @Xekyo as you commented on the issue recently.

murchandamus commented at 10:28 pm on August 4, 2022: contributor

Cool, thank you for working on this. This PR as it is would get us almost all the way there as it should ensure that any coin selection results that exceeded the weight limit get filtered out before we do our final pick out of the selection candidates. Now we’ll succeed at building a transaction if there is at least one selection result that doesn’t exceed the weight limit, where we might have failed previously if that solution had the best waste score (and that would be the case at a low feerate, as a higher total input weight would get preferred).

I was pondering whether this would fail to find an existing solution in any scenario. I came up with this:

Send ₿49.5 at a low feerate from a UXTO pool with • 10,000 P2PKH inputs of ₿0.04 • 1,455 P2WPKH inputs of ₿0.034

Explanation: • The UTXO pool has enough funds to pay for the transaction • At a negligible not_input_size, a standard transaction can have about ~675 P2PKH inputs, but 1470 P2WPKH inputs • With the above UTXOs, it would take 1,238 P2PKH inputs to pay for the transaction (which would exceed the limit by far), and it awould take 1,456 P2WPKH inputs to pay for the transaction (but there are too few) ⇒ Only an input set from mixed inputs that is almost exclusively composed from P2WPKH inputs (and a single digit number of P2PKH inputs) would result in a standard transaction

I don’t think that any of our coin selection approaches would find such an input set, even if we added backtracking to BnB when the standard weight limit is exceeded. I figure that to succeed in this edge-case we would need an explicit mechanism to replace the inputs with the lowest value per weight once we exceed the standard weight limit. E.g. adding a heap to SRD that sorts the input set by effectiveValue/weight. I think this is out of scope though.

Approach ACK, will have to get back to review the code more carefully.

aureleoules force-pushed on Aug 8, 2022

aureleoules commented at 9:03 am on August 8, 2022: member

Rebased because of silent merge conflict.

aureleoules commented at 9:08 am on August 8, 2022: member

Send ₿49.5 at a low feerate from a UXTO pool with • 10,000 P2PKH inputs of ₿0.04 • 1,455 P2WPKH inputs of ₿0.034

I tested this case with the following code and the coin selector did not find a result as you said @Xekyo.

 0{
 1    // Send ₿49.5 at a low feerate from a UXTO pool with
 2    // 10,000 P2PKH inputs of ₿0.04
 3    // 1,455 P2WPKH inputs of ₿0.034
 4
 5    std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase());
 6    wallet->LoadWallet();
 7    LOCK(wallet->cs_wallet);
 8    wallet->SetupLegacyScriptPubKeyMan();
 9
10    CoinsResult available_coins;
11    for (int j = 0; j < 10000; ++j) {
12        add_coin(available_coins, *wallet, CAmount(0.04 * COIN), CFeeRate(0), 144, false, 0, true);
13    }
14
15    for (int j = 0; j < 1455; ++j) {
16        add_coin(available_coins, *wallet, CAmount(0.034 * COIN), CFeeRate(0), 144, false, 0, true);
17    }
18
19    const auto result = SelectCoins(*wallet, available_coins, target, cc, cs_params);
20    BOOST_CHECK(result);
21}

in test/functional/rpc_fundrawtransaction.py:990 in c166411dad outdated

979@@ -980,7 +980,7 @@ def test_transaction_too_large(self):
980             outputs[recipient.getnewaddress()] = 0.1
981         wallet.sendmany("", outputs)
982         self.generate(self.nodes[0], 10)
983-        assert_raises_rpc_error(-4, "Transaction too large", recipient.fundrawtransaction, rawtx)
984+        assert_raises_rpc_error(-4, "Insufficient funds", recipient.fundrawtransaction, rawtx)

murchandamus commented at 8:05 pm on August 8, 2022:

Insufficient funds might be a confusing error message since the wallet would also report having sufficient funds at the same time. Perhaps we could return a more specific error, if the last attempt returns from eligible_results being empty e.g. Cannot fund transaction, wallet too fragmented.

in src/wallet/spend.cpp:571 in c166411dad outdated

533+        });
534+
535+        return weight <= static_cast<int>(MAX_STANDARD_TX_WEIGHT);
536+    });
537+
538+    if (eligible_results.empty()) {

murchandamus commented at 8:08 pm on August 8, 2022:

Perhaps we could store some “result hint” when we get into this if-block on a coin selection attempt that we could later use to inform the result message.

aureleoules commented at 9:37 pm on August 9, 2022:

Here’s my attempt a3dece4e41de7bd5e118278abf09abcd2fcb4922.

murchandamus commented at 8:16 pm on August 8, 2022: contributor

utACK c166411dad1f4cdaa61f70b92728ecebfc3fc749

Tests look reasonable, it might be nice if we could provide a more targeted error message when the case is hit for all coin selection attempts.

Yeah, I had an easier scenario at first for which I was going to suggest a fix, but then I realized that it wouldn’t cause a failure because after #24584 we will always try to build input sets from a single type. I think my above scenario is sufficiently constructed that it would be very unlikely to occur in the wild. But, since I had already tinkered it all out, I figured I might as well keep a record of a worst-case scenario.

aureleoules force-pushed on Aug 9, 2022

aureleoules commented at 9:39 pm on August 9, 2022: member

I have rebased this PR on top of #25734 (slightly rebased because of merge conflicts of the original PR). Added a3dece4e41de7bd5e118278abf09abcd2fcb4922 to show a more specific error message when the transaction weight is exceeded during the coin selection.

furszy commented at 10:45 pm on August 9, 2022: member

About the specific error messages topic, I don’t think that passing an enum reference to the function is the best solution. We have the util::Result class to cover this purpose (more info in #25218 and #25721)

Plus, some notes about this in case you haven’t seen them:

I have decoupled the preset inputs fetching block of code from SelectCoins and added util::Result class connection with proper error descriptions in #25685. (the error descriptions there are not due “Insufficient Funds”, that was wrong).
And then have #25806, which has 3b3054f9 which basically adds util::Result error support to the entire SelectCoins function (which is what I would say that you actually need here).

So, would suggest to either cherry-pick 3b3054f9 here, so can return the error string (returning an empty string if the error is “Insufficient Funds” so there aren’t changes out of the scope of the PR and you can still return the specific error) or, if you don’t want it, maybe leave the proper error description point for a follow-up PR and only focus on the functionality here.

aureleoules force-pushed on Aug 10, 2022

aureleoules commented at 4:02 pm on August 10, 2022: member

Thank you @furszy for your comments! I’ll probably wait until #25806 and #25734 are merged before continuing working on this error message commit and will drop a3dece4e41de7bd5e118278abf09abcd2fcb4922 in the meantime. I rebased it again since #25734 just got rebased.

aureleoules force-pushed on Aug 22, 2022

in src/wallet/spend.cpp:543 in c9c55455a9 outdated

539         return std::nullopt;
540     }
541 
542+    std::vector<SelectionResult> eligible_results;
543+    std::copy_if(results.begin(), results.end(), std::back_inserter(eligible_results), [coin_selection_params](const SelectionResult& result) {
544+        const int weight = std::accumulate(result.GetInputSet().begin(), result.GetInputSet().end(), static_cast<int>(coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR), [](int acc, const auto& coin) {

achow101 commented at 9:06 pm on September 19, 2022:

tx_noinputs_size is 0 when we are subtracting the fee from the outputs, so using it here may not always result in the correct calculation.

aureleoules commented at 12:11 pm on September 20, 2022:

Do you know how I can take this into account? I did hear you say “fuck” on your stream VOD while reviewing this so I guess that’s not trivial?

achow101 commented at 3:38 pm on September 20, 2022:

The easiest way to handle this is to change when and how tx_noinputs_size is calculated and used. Essentially you need to find everywhere that tx_noinputs_size is being set/updated and make sure that the places that use tx_noinputs_size for calculations treat it as if it were 0 when SFFO. I don’t think this should be too difficult as it is only used within CreateTransactionInternal and only for calculating not_input_fees.

murchandamus commented at 8:18 pm on September 20, 2022:

I am not surprised that not_input_fees would be zero in case of SFFO, but quite surprised that tx_noinputs_size would be 0, though. Just given the variable name, I would have expected it to simply be the size of the recipient outputs plus header data, regardless of who pays the fees. Would it perhaps be doable to fix the behavior in that direction, to reduce future developer surprise?

aureleoules commented at 9:32 am on September 29, 2022:

I applied your advice @achow101 here: https://github.com/bitcoin/bitcoin/compare/32a233773b4536aadecd00a52c897614dc9981b8..9421f362d5e0c6d4c7fe047a23ef7e0676f380b9. Is this right?

Also, maybe we could make tx_noinputs_size private and have a getter that returns 0 in case of SFFO?

achow101 commented at 1:03 am on October 7, 2022:

No, that’s not what I meant.

What you’ve done is no different from how it was before. My point was that you need to be using the non-inputs size always, not set it to 0 for SFFO. This size is typically tracked by tx_noinputs_size, but it gets set to 0 when SFFO. So you need to find everywhere else (generally in CreateTransactionInternal) that tx_noinputs_size is used, change it so that it is always calculated, and change the places that expected it to be 0 for SFFO to still use 0 (e.g. with a ternary).

aureleoules commented at 8:20 am on October 7, 2022:

Ah okay my bad. I pushed it, should be good?

in src/wallet/test/coinselector_tests.cpp:944 in c9c55455a9 outdated

939+        /*change_spend_size=*/148,
940+        /*min_change_target=*/CENT,
941+        /*effective_feerate=*/CFeeRate(0),
942+        /*long_term_feerate=*/CFeeRate(0),
943+        /*discard_feerate=*/CFeeRate(0),
944+        /*tx_noinputs_size=*/static_cast<size_t>(10) + GetSerializeSize(txout, PROTOCOL_VERSION), // static header size + output size

achow101 commented at 9:15 pm on September 19, 2022:

Since sizes are already being hardcoded above for change_output_size and change_spend_size, I think it’s fine to hard code this as well instead of having to create an entire wallet just to fetch a single destination in order to get this size, where accuracy also doesn’t really matter.

in src/wallet/test/coinselector_tests.cpp:939 in c9c55455a9 outdated

934+
935+    FastRandomContext rand;
936+    CoinSelectionParams cs_params{
937+        rand,
938+        /*change_output_size=*/34,
939+        /*change_spend_size=*/148,

achow101 commented at 9:16 pm on September 19, 2022:

While these values don’t particularly matter, they should probably match the p2wpkh sizes rather than the p2pkh.

0        /*change_output_size=*/31,
1        /*change_spend_size=*/68,

in src/wallet/test/coinselector_tests.cpp:960 in c9c55455a9 outdated

955+        // The 50.0 BTC output should be selected, because the transaction would otherwise be too large
956+
957+        std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase());
958+        wallet->LoadWallet();
959+        LOCK(wallet->cs_wallet);
960+        wallet->SetupLegacyScriptPubKeyMan();

achow101 commented at 9:16 pm on September 19, 2022:

Let’s avoid making LegacySPKMs in tests which are not specifically testing that behavior.

in src/wallet/test/coinselector_tests.cpp:980 in c9c55455a9 outdated

947+
948+    CMutableTransaction txDummy;
949+    txDummy.vout.push_back(txout);
950+
951+    {
952+        // Scenario 1:

achow101 commented at 9:18 pm on September 19, 2022:

ISTM these tests could be deduplicated intoa helper function with each scenario just being a set of parameters as each test case does basically the same thing but with slightly different params.

in src/wallet/test/coinselector_tests.cpp:1048 in c9c55455a9 outdated

1082+            add_coin(available_coins, *wallet, CAmount(0.017 * COIN), CFeeRate(0), 144, false, 0, true);
1083+        }
1084+
1085+        // Perform selection
1086+        const auto result = SelectCoins(*wallet, available_coins, target, cc, cs_params);
1087+        BOOST_CHECK(!result);

achow101 commented at 9:18 pm on September 19, 2022:

A comment for this test case would be nice.

aureleoules force-pushed on Sep 20, 2022

aureleoules commented at 12:12 pm on September 20, 2022: member

I refactored the tests and changed the values a bit because I switched from a legacy wallet to a descriptor wallet. Also documented the last test.

aureleoules force-pushed on Sep 29, 2022

DrahtBot added the label Needs rebase on Oct 4, 2022

aureleoules force-pushed on Oct 4, 2022

DrahtBot removed the label Needs rebase on Oct 4, 2022

aureleoules force-pushed on Oct 7, 2022

in src/wallet/spend.cpp:523 in dbeddc1f7f outdated

519         return std::nullopt;
520     }
521 
522+    std::vector<SelectionResult> eligible_results;
523+    std::copy_if(results.begin(), results.end(), std::back_inserter(eligible_results), [coin_selection_params](const SelectionResult& result) {
524+        const auto initWeight{coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR};

achow101 commented at 7:03 pm on October 31, 2022:

In dbeddc1f7f43c6df293133cd2b12a7187c0e321e “wallet: Check max tx weight in coin selector”

We still need to calculate the weight correctly even when subtracting the fee from outputs, so this should not be checking that.

0        const auto initWeight{coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR};

in src/wallet/test/coinselector_tests.cpp:1058 in fc5219f518 outdated

1053+        const bool has_0_0625_coin = std::any_of(result->GetInputSet().begin(), result->GetInputSet().end(), [](const auto& coin) {
1054+            return coin.GetEffectiveValue() == 0.0625 * COIN;
1055+        });
1056+        const bool has_not_50_coin = std::any_of(result->GetInputSet().begin(), result->GetInputSet().end(), [](const auto& coin) {
1057+            return coin.GetEffectiveValue() != 50 * COIN;
1058+        });

achow101 commented at 7:12 pm on October 31, 2022:

In fc5219f51813b6e9c128d6bc0cc70c63a5edce48 “test: Check max transaction weight in CoinSelection”

It’s not clear to my why we shouldn’t expect the 50 Coin to be picked? ISTM Random selection should eventually find the 50 Coin single input solution and go with that.

aureleoules commented at 12:28 pm on November 1, 2022:

Right, I removed the check. The two other coins should always be present though.

in src/wallet/test/coinselector_tests.cpp:976 in fc5219f518 outdated

971+        // Perform selection
972+
973+        const auto result = select_coins(
974+            target, cs_params, cc, [&](CWallet& wallet) {
975+                CoinsResult available_coins;
976+                for (int j = 0; j < 1500; ++j) {

achow101 commented at 7:20 pm on October 31, 2022:

In fc5219f51813b6e9c128d6bc0cc70c63a5edce48 “test: Check max transaction weight in CoinSelection”

The comment says 1515, but this is only 1500? It seems like 1500 works anyways.

aureleoules force-pushed on Nov 1, 2022

aureleoules commented at 12:30 pm on November 1, 2022: member

Thanks @achow101 I addressed your comments and added you as co-author.

aureleoules force-pushed on Nov 1, 2022

aureleoules commented at 1:36 pm on November 1, 2022: member

Rebased and solved silent merge conflicts.

aureleoules force-pushed on Nov 1, 2022

in src/wallet/test/coinselector_tests.cpp:1026 in 54ecb044c0 outdated

1054+            },
1055+            chain, m_args);
1056+
1057+        BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(0.025 * COIN)));
1058+        BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(0.0625 * COIN)));
1059+    }

achow101 commented at 7:23 pm on November 1, 2022:

In 54ecb044c0ebf40ec06bd192725d6f49dcff90ff “test: Check max transaction weight in CoinSelection”

It’s not clear to me how this scenario is materially different from scenario 2. It just adds the 50 Coin UTXO and I’m not sure what that actually adds to the test?

Additionally, this will fail 1 in 2401 runs as the 50 Coin could be chosen as a single input solution. This would then fail the checks.

aureleoules commented at 10:39 am on November 2, 2022:

Thanks, I removed it.

aureleoules force-pushed on Nov 2, 2022

aureleoules commented at 10:39 am on November 2, 2022: member

Removed scenario 3 and removed unnecessary check in scenario 2 (https://github.com/bitcoin/bitcoin/compare/54ecb044c0ebf40ec06bd192725d6f49dcff90ff..ffd744f9a0391beda6bb98de1d4e851fc6ca7ca4)

aureleoules force-pushed on Nov 3, 2022

aureleoules commented at 8:52 pm on November 3, 2022: member

~~Rebased to fix CI p2p_sendtxrcncl.py failure.~~ didn’t seem to work :neutral_face:

achow101 commented at 7:23 pm on November 9, 2022: member

ACK b763b072cec235d397fae4dafc6a69f5902eb3f6

in src/wallet/spend.cpp:572 in dc9bce1866 outdated

568+    std::vector<SelectionResult> eligible_results;
569+    std::copy_if(results.begin(), results.end(), std::back_inserter(eligible_results), [coin_selection_params](const SelectionResult& result) {
570+        const auto initWeight{coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR};
571+        const int weight = std::accumulate(result.GetInputSet().begin(), result.GetInputSet().end(), static_cast<int>(initWeight), [](int acc, const auto& coin) {
572+            return acc + coin.input_bytes * WITNESS_SCALE_FACTOR;
573+        });

furszy commented at 4:42 pm on November 17, 2022:

Instead of doing this entire for-loop accumulation, what about adding a field m_weight_sum to OutputGroup?

Initializing it to coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR in the constructor and increasing it at every output insertion (inside OutputGroup::Insert).

So, when SelectionResult::AddInput gets called, you already have the total weight for each output group. And can just sum it up inside another cache field there.

aureleoules force-pushed on Nov 17, 2022

aureleoules commented at 7:54 pm on November 17, 2022: member

Thanks @furszy, I’ve implemented your suggestion: https://github.com/bitcoin/bitcoin/compare/b763b072cec235d397fae4dafc6a69f5902eb3f6..119fea975463b05d9a2dddbb36db17b2c91ef880.

It appears to be slightly faster:

Before (dc9bce1866f1cce851a216d2c7bfd7a890c27006)

ns/op	op/s	err%	ins/op	cyc/op	IPC	bra/op	miss%	total	benchmark
1,614,196.00	619.50	0.6%	11,151,218.00	3,710,976.00	3.005	1,995,456.00	0.3%	0.02	`CoinSelection`

Current (98efb22650c803c3bd4c094d58ef7ba16b77fee2)

ns/op	op/s	err%	ins/op	cyc/op	IPC	bra/op	miss%	total	benchmark
1,466,341.00	681.97	0.6%	11,176,762.00	3,358,752.00	3.328	1,897,839.00	0.3%	0.02	`CoinSelection`

I’ve updated the PR description’s benchmarks.

I also realized that in the previous commit the weight could go in the negatives because coin.input_bytes is equal to -1 for external inputs and I simply summed this number, I fixed it.

furszy commented at 12:42 pm on November 18, 2022: member

I also realized that in the previous commit the weight could go in the negatives because coin.input_bytes is equal to -1 for external inputs and I simply summed this number, I fixed it.

Hmm, that shouldn’t be happening. We do have a check inside the preset inputs fetching function that throws an error if input_bytes == -1. Maybe what your wallet is trying to spend is a not solvable coin owned by the wallet.

aureleoules commented at 2:05 pm on November 18, 2022: member

Sorry @furszy I meant that the weight could be negative in other tests, which probably used external coins. My test was not affected.

aureleoules force-pushed on Nov 18, 2022

achow101 commented at 4:27 pm on November 18, 2022: member

ACK 3474b5f7684cacd0c098a11c95079e29f5e905b4

aureleoules commented at 4:33 pm on November 18, 2022: member

Thanks @achow101. @furszy suggested to me in private that the WITNESS_SCALE_FACTOR may not be correctly applied tough. I drafted a quick diff here: https://gist.github.com/aureleoules/8a7cfcd93a66b70eecc74e7a6692d300

Would you agree?

achow101 commented at 5:11 pm on November 18, 2022: member

No, it is correct as it is now. Converting vbytes to weight is always just multiply by WITNESS_SCALE_FACTOR. It doesn’t matter what the script type is.

aureleoules commented at 5:14 pm on November 18, 2022: member

Okay great thank you!

in src/wallet/coinselection.cpp:461 in 070ca66bd5 outdated

456 {
457     util::insert(m_selected_inputs, inputs);
458     m_use_effective = !subtract_fee_outputs;
459+
460+    m_weight += std::accumulate(inputs.cbegin(), inputs.cend(), 0, [](int sum, const auto& coin) {
461+        return sum + std::min(coin.input_bytes, 0) * WITNESS_SCALE_FACTOR;

furszy commented at 10:11 pm on November 19, 2022:

Should be std::max(coin.input_bytes, 0).

Otherwise, this entire sum will be 0 most of the time (it’s taking the smaller value between input_bytes and 0).

aureleoules commented at 11:27 pm on November 19, 2022:

Right thanks, I confused myself. Pushed.

aureleoules force-pushed on Nov 19, 2022

in src/wallet/spend.cpp:563 in 645dd06320 outdated

558@@ -557,14 +559,24 @@ std::optional<SelectionResult> ChooseSelectionResult(const CWallet& wallet, cons
559         results.push_back(*srd_result);
560     }
561 
562-    if (results.size() == 0) {
563+    if (results.empty()) {
564         // No solution found
565         return std::nullopt;
566     }

furszy commented at 6:29 pm on November 21, 2022:

As std::copy_if is a no-op if the vector is empty, could remove these lines.

aureleoules commented at 7:07 pm on November 21, 2022:

Leaving the results.empty()) check would also avoid creating the eligible_results no?

furszy commented at 1:07 pm on November 22, 2022:

yes, would only avoid the empty vector initialization.

in src/wallet/test/coinselector_tests.cpp:1000 in 30b71d1f0e outdated

 995+                return available_coins;
 996+            },
 997+            chain, m_args);
 998+
 999+        BOOST_CHECK(result);
1000+        BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(50 * COIN)));

furszy commented at 6:36 pm on November 21, 2022:

As this is expecting to find one single output, might be better to do:

0const auto& inputs = result->GetInputSet();
1BOOST_CHECK_EQUAL(inputs.size(), 1);
2BOOST_CHECK_EQUAL(inputs.begin()->GetEffectiveValue(), 50 * COIN);

aureleoules commented at 7:06 pm on November 21, 2022:

It appears that there is more than 1 coin selected (hundreds), I’m guessing this is because of UTXO consolidation? The 50 BTC coin will always be in the input set though.

furszy commented at 1:25 pm on November 22, 2022:

hmm, privacy wise, sounds odd to add hundreds of UTXO from different external sources when the target amount is being covered only by one of them.. the rest are not needed, they are just leaking information about the wallet and making the tx bigger.

Will give it a look. It’s not something that should block this PR, just a parallel investigation.

furszy approved

furszy commented at 6:37 pm on November 21, 2022: member

code review ACK 30b71d1f, left few small comments.

achow101 commented at 7:08 pm on November 23, 2022: member

ACK 30b71d1f0ea7e8b69b069713b66e45d472373832

fanquake requested review from murchandamus on Nov 23, 2022

DrahtBot added the label Needs rebase on Dec 5, 2022

wallet: Check max tx weight in coin selector

Co-authored-by: Andrew Chow <github@achow101.com>

6b563cae92

test: Check max transaction weight in CoinSelection

Co-authored-by: Andrew Chow <github@achow101.com>

c7c7ee9d0b

aureleoules force-pushed on Dec 5, 2022

aureleoules commented at 6:34 pm on December 5, 2022: member

Rebased

DrahtBot removed the label Needs rebase on Dec 5, 2022

DrahtBot renamed this:
~~wallet: Check max transaction weight in CoinSelection~~
wallet: Check max transaction weight in CoinSelection
on Dec 5, 2022

achow101 commented at 9:06 pm on December 5, 2022: member

reACK c7c7ee9d0b2d7b303b9300f941e37e09e7d8d8b6

w0xlt approved

w0xlt commented at 3:10 am on December 6, 2022: contributor

ACK https://github.com/bitcoin/bitcoin/pull/25729/commits/c7c7ee9d0b2d7b303b9300f941e37e09e7d8d8b6

in src/wallet/coinselection.cpp:360 in 6b563cae92 outdated

354@@ -354,6 +355,10 @@ void OutputGroup::Insert(const COutput& output, size_t ancestors, size_t descend
355     // descendants is the count as seen from the top ancestor, not the descendants as seen from the
356     // coin itself; thus, this value is counted as the max, not the sum
357     m_descendants = std::max(m_descendants, descendants);
358+
359+    if (output.input_bytes > 0) {
360+        m_weight += output.input_bytes * WITNESS_SCALE_FACTOR;

S3RK commented at 7:45 am on December 6, 2022:

While this is fine for the purposes of this PR, the weight here is not always precise due to rounding error of input_bytes.

Ideally, we would store the actual weight in COutput and just take it from there. I realise, this might be out of scope for this PR. But maybe we can add a warning in code for future devs and create an issue in this repo?

w0xlt commented at 1:52 pm on December 6, 2022:

the weight here is not always precise due to rounding error of input_bytes

Could elaborate, since both COutput::input_bytes and WITNESS_SCALE_FACTOR are integer ?

achow101 commented at 4:56 pm on December 6, 2022:

1 virtual byte = 4 weight units. When computing vbytes from weight, if the weight is not divisible by 4, the vbytes is rounded up. For example, 6 WU is really 1.5 vbytes, but is rounded to 2 vbytes. Since input_bytes stores this rounded number, computing weight from it results in 8 WU rather than the correct value of 6.

in src/wallet/spend.cpp:900 in c7c7ee9d0b

896@@ -888,7 +897,7 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
897     }
898 
899     // Include the fees for things that aren't inputs, excluding the change output
900-    const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);
901+    const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.tx_noinputs_size);

furszy commented at 2:53 pm on December 6, 2022:

could:

0    const CAmount not_input_fees = coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);

achow101 commented at 4:58 pm on December 6, 2022:

I would actually rather that not_input_fees is always calculated, and the SFFO handling is done for just the target. We really need to try to reduce the number of places that we have differences between normal and SFFO coin selection. Since not_input_fees is used elsewhere, having its value be dependent on SFFO results in a cascading effect that I think we should be avoiding.

But that can be done in a followup.

furszy approved

furszy commented at 2:54 pm on December 6, 2022: member

diff ACK c7c7ee9d

achow101 merged this on Dec 6, 2022

achow101 closed this on Dec 6, 2022

sidhujag referenced this in commit 7b7cd87679 on Dec 6, 2022

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

sidhujag referenced this in commit cab438784e on Jan 4, 2023

aureleoules deleted the branch on Jan 12, 2023

achow101 referenced this in commit 395b932807 on Apr 20, 2023

bitcoin locked this on Jan 12, 2024

wallet: Check max transaction weight in CoinSelection #25729

PR

Master

Reviews

Conflicts

Before (dc9bce1866f1cce851a216d2c7bfd7a890c27006)

Current (98efb22650c803c3bd4c094d58ef7ba16b77fee2)