wallet: Refactor OutputGroups to handle fees and spending eligibility on grouping #20040

pull achow101 wants to merge 7 commits into bitcoin:master from achow101:inner-groupoutputs changing 6 files +199 −192
  1. achow101 commented at 6:46 PM on September 29, 2020: member

    Even after #17458, we still deal with setting fees of an OutputGroup and filtering the OutputGroup outside of the struct. We currently make all of the OutputGroups in SelectCoins and then copy and modify them within each SelectCoinsMinConf scenario. This PR changes this to constructing the OutputGroups within the SelectCoinsMinConf so that the scenario can be taken into account during the group construction. Furthermore, setting of fees and filtering for effective value is moved into OutputGroup::Insert itself so that we don't add undesirable outputs to an OutputGroup rather than deleting them afterwards.

    To facilitate fee calculation and effective value filtering during OutputGroup::Insert, OutputGroup now takes the feerates in its constructor and computes the fees and effective value for each output during Insert.

    While removing OutputGroups in accordance with the CoinEligibilityFilter still requires creating the OutputGroups first, we can do that within the function that makes them - GroupOutputs.

  2. Remove OutputGroup non-default constructors 2acad03657
  3. Move GroupOutputs into SelectCoinsMinConf 6148a8acda
  4. Move fee setting of OutputGroup to Insert
    OutputGroup will handle the fee and effective value computations
inside of Insert. It now needs to take the effective feerate and long
term feerates as arguments to its constructor.
    99b399aba5
  5. Move EligibleForSpending into GroupOutputs
    Instead of filtering after the OutputGroups have been made, do it as
they are being made.
    d895e98b59
  6. achow101 renamed this:
    wallet: Refactor OutputGroups to handle fees and spending eligibility on insert
    wallet: Refactor OutputGroups to handle fees and spending eligibility on grouping
    on Sep 29, 2020
  7. achow101 force-pushed on Sep 29, 2020
  8. achow101 force-pushed on Sep 29, 2020
  9. meshcollider added the label Wallet on Sep 29, 2020
  10. achow101 cross-referenced this on Sep 29, 2020 from issue Use effective values throughout coin selection by achow101
  11. DrahtBot commented at 12:18 AM on September 30, 2020: contributor

    <!--e57a25ab6845829454e8d69fc972939a-->

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

    <!--174a7506f384e20aa4161008e828411d-->

    Conflicts

    Reviewers, this pull request conflicts with the following ones:

    • #18418 (wallet: Increase OUTPUT_GROUP_MAX_ENTRIES to 100 by fjahr)
    • #17526 (Use Single Random Draw In addition to knapsack as coin selection fallback by achow101)
    • #17355 (gui: grey out used address in address book by za-kk)
    • #17331 (Use effective values throughout coin selection by achow101)

    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.

  12. DrahtBot cross-referenced this on Sep 30, 2020 from issue wallet: Increase OUTPUT_GROUP_MAX_ENTRIES to 100 by fjahr
  13. DrahtBot cross-referenced this on Sep 30, 2020 from issue Add Single Random Draw as an additional coin selection algorithm by achow101
  14. DrahtBot cross-referenced this on Sep 30, 2020 from issue gui: grey out used address in address book by za-kk
  15. achow101 force-pushed on Oct 1, 2020
  16. achow101 force-pushed on Oct 2, 2020
  17. in src/wallet/wallet.h:615 in 6148a8acda outdated 
     609 | @@ -610,8 +610,16 @@ struct CoinSelectionParams
 610 |      size_t tx_noinputs_size = 0;
 611 |      //! Indicate that we are subtracting the fee from outputs
 612 |      bool m_subtract_fee_outputs = false;
 613 | -
 614 | -    CoinSelectionParams(bool use_bnb, size_t change_output_size, size_t change_spend_size, CFeeRate effective_fee, size_t tx_noinputs_size) : use_bnb(use_bnb), change_output_size(change_output_size), change_spend_size(change_spend_size), effective_fee(effective_fee), tx_noinputs_size(tx_noinputs_size) {}
 615 | +    bool m_avoid_partial_spends = false;
 616 | +
 617 | +    CoinSelectionParams(bool use_bnb, size_t change_output_size, size_t change_spend_size, CFeeRate effective_fee, size_t tx_noinputs_size, bool avoid_partial) :
    instagibbs commented at 1:43 PM on October 2, 2020:

    musing: this constructor only seems useful for tests

  18. in src/wallet/coinselection.cpp:306 in 4b15eae4fc outdated 
     299 | @@ -300,16 +300,24 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
 300 |  
 301 |   ******************************************************************************/
 302 |  
 303 | -void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
 304 | +void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only) {
 305 | +    // Compute the effective value first
 306 | +    CAmount coin_fee = output.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.m_input_bytes);
 307 | +    CAmount ev = output.txout.nValue - coin_fee;
    instagibbs commented at 1:59 PM on October 2, 2020:

    const

    achow101 commented at 5:45 PM on October 2, 2020:

    Done

  19. in src/wallet/coinselection.cpp:305 in 4b15eae4fc outdated 
     299 | @@ -300,16 +300,24 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
 300 |  
 301 |   ******************************************************************************/
 302 |  
 303 | -void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
 304 | +void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only) {
 305 | +    // Compute the effective value first
 306 | +    CAmount coin_fee = output.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.m_input_bytes);
    instagibbs commented at 1:59 PM on October 2, 2020:

    const

    achow101 commented at 5:45 PM on October 2, 2020:

    Done

  20. in src/wallet/wallet.cpp:2492 in d4b8b8d25a outdated 
    2488 | @@ -2489,8 +2489,8 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
2489 |          (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2490 |          (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2491 |          (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2492 | -        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2493 | -        (m_spend_zero_conf_change && !fRejectLongChains && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max()), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
2494 | +        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
    instagibbs commented at 2:08 PM on October 2, 2020:

    nit: annotate the new bool

    Also why is this being set to true? I thought that we get more relaxed as we fail to select with "nicer" coin sets? This seems to make it a tighter criteria?

    achow101 commented at 4:32 PM on October 2, 2020:

    No, it's less restrictive. When it is false, we won't include partial groups. When is true, we do. At least that is the intended behavior.

    instagibbs commented at 4:34 PM on October 2, 2020:

    ahhhh, I had "avoid partial" in my head for this.

    instagibbs commented at 4:34 PM on October 2, 2020:

    so yes, annotation is :ok_hand: because it would have fixed my thought here

    achow101 commented at 5:45 PM on October 2, 2020:

    Annotated

  21. in src/wallet/wallet.cpp:2493 in d4b8b8d25a outdated 
    2488 | @@ -2489,8 +2489,8 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
2489 |          (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2490 |          (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2491 |          (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2492 | -        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2493 | -        (m_spend_zero_conf_change && !fRejectLongChains && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max()), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
2494 | +        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2495 | +        (m_spend_zero_conf_change && !fRejectLongChains && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::max(), true), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
    instagibbs commented at 2:08 PM on October 2, 2020:

    nit: annotate the new bool

    achow101 commented at 5:45 PM on October 2, 2020:

    Done

  22. in src/wallet/wallet.cpp:4239 in d4b8b8d25a outdated 
    4234 | @@ -4235,9 +4235,9 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
4235 |      if (!single_coin) {
4236 |          for (auto& it : gmap) {
4237 |              auto& group = it.second;
4238 | -            if (full_groups.count(it.first) > 0) {
4239 | -                // Make this unattractive as we want coin selection to avoid it if possible
4240 | -                group.m_ancestors = max_ancestors - 1;
4241 | +            if (full_groups.count(it.first) > 0 && !filter.m_include_partial_groups) {
4242 | +                // Don't include partial groups if we don't want them yet
    instagibbs commented at 2:08 PM on October 2, 2020:

    yet?

    achow101 commented at 5:45 PM on October 2, 2020:

    removed

  23. instagibbs commented at 2:12 PM on October 2, 2020: member
  24. Move OutputGroup positive only filtering into Insert 416d74fb16
  25. Explicitly filter out partial groups when we don't want them
    Instead of hacking OutputGroup::m_ancestors to discourage the inclusion
of partial groups via the eligibility filter, add a parameter to the
eligibility filter that indicates whether we want to include the group.
Then for those partial groups, don't return them in GroupOutputs if we
indicate they aren't desired.
    f6b3052739
  26. achow101 force-pushed on Oct 2, 2020
  28. fanquake commented at 2:22 AM on October 10, 2020: member

    cc @Xekyo

  29. apoelstra cross-referenced this on Nov 14, 2020 from issue Allow fundrawtransaction and walletcreatefundedpsbt to take external inputs by achow101
  30. laanwj added this to the "Blockers" column in a project
  31. in src/wallet/coinselection.cpp:306 in 99b399aba5 outdated 
     301 | @@ -302,6 +302,16 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
 302 |  
 303 |  void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
 304 |      m_outputs.push_back(output);
 305 | +    CInputCoin& coin = m_outputs.back();
 306 | +    coin.m_fee = coin.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(coin.m_input_bytes);
    murchandamus commented at 10:14 PM on November 24, 2020:

    I think I have asked this before, but why can m_input_bytes ever be below zero here? Perhaps it would be good to have a comment to explain that.

    achow101 commented at 10:38 PM on November 24, 2020:

    m_input_bytes is initialized to -1 to indicate that it hasn't been calculated yet.

    murchandamus commented at 10:42 PM on November 24, 2020:

    But this is at the point where we calculate the effective value of UTXOs, so we need to know the size. Why would we want to mitigate a missing size here rather than throwing?

    achow101 commented at 6:32 PM on November 30, 2020:

    Since the intention is to not change behavior in this PR, I think I will leave this as is for now.

    Additionally I don't think it is guaranteed that when we add a CInputCoin to an OutputGroup that we do know the size. It could be for a preset input or an input not in the wallet (there is a PR for that) where we add those coins to an OutputGroup and just don't use the effective value calculation. In those instances, the m_input_bytes may not be set.

    fjahr commented at 9:38 PM on January 1, 2021:

    A comment would still be a good idea :)

  32. in src/wallet/wallet.cpp:4236 in d895e98b59 outdated 
    4229 | @@ -4237,8 +4230,10 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
4230 |                      ins.first->second.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);
4231 |                  }
4232 |              } else {
4233 | -                groups.emplace_back(effective_feerate, long_term_feerate);
4234 | -                groups.back().Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);
4235 | +                // This is for if each output gets it's own OutputGroup
4236 | +                OutputGroup coin(effective_feerate, long_term_feerate);
4237 | +                coin.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants);
4238 | +                if (coin.EligibleForSpending(filter)) groups.push_back(coin);
    murchandamus commented at 10:21 PM on November 24, 2020:

    Wouldn't this mean that if you got a tiny and a large UTXO associated with the same address that you would potentially form a OutputGroup with just the large coin? Shouldn't the group rather be ineligible as a whole to avoid the partial spend?

    achow101 commented at 10:40 PM on November 24, 2020:

    This would make the wallet more vulnerable to dust attacks. An attacker could them lock out a user from their funds by sending dust to an already used address.

    murchandamus commented at 10:49 PM on November 24, 2020:

    Yeah, I guess dust should get ignored altogether, but at higher fee rates this could in the worst-case even affect a small amount and a slightly larger amount, which should be prohibited by the partial spending restriction.

  33. in src/wallet/coinselection.cpp:306 in 416d74fb16 outdated 
     299 | @@ -300,16 +300,24 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
 300 |  
 301 |   ******************************************************************************/
 302 |  
 303 | -void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
 304 | +void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only) {
 305 | +    // Compute the effective value first
 306 | +    const CAmount coin_fee = output.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.m_input_bytes);
 307 | +    const CAmount ev = output.txout.nValue - coin_fee;
    murchandamus commented at 10:23 PM on November 24, 2020:

    I think that this will result in the OutputGroup accepting uneconomic inputs in the case that the recipient is paying the fees. Should we perhaps rather filter by whether the UTXO are uneconomic, but just calculate with the value instead of the effective value for the case of the recipient paying the fees?

    achow101 commented at 10:49 PM on November 24, 2020:

    Given that the recipient paying the fees is typically used when sweeping the wallet, I don't think it really matters.

    murchandamus commented at 7:38 PM on November 25, 2020:

    Oh, I didn't realize that it was just used for that. Wouldn't it be much easier to implement that as a "send everything": no coin selection, just sum up everything, deduct fees and pay the recipient address that?

    achow101 commented at 7:41 PM on November 25, 2020:

    That's the most common use case I think, but not the only one.

    murchandamus commented at 3:27 AM on December 10, 2020:

    It may be worth considering an explicit sweepwallet rpc since I don't think the expectations for "recipient pays fees" and "empty my wallets and send as much as you can" necessarily match. Although, maybe in both cases it would be appropriate not to use uneconomic UTXOs. ;)

  34. murchandamus commented at 9:31 PM on November 30, 2020: contributor

    Code Review ACK https://github.com/bitcoin/bitcoin/pull/20040/commits/f6b305273910db0e46798d361413a7e878cb45f7

  35. murchandamus commented at 9:34 PM on November 30, 2020: contributor

    Disclaimer: @achow101 has walked me throw the PR, I have reviewed it at least twice. I think that the concept makes sense, but I'm not familiar with the wallet code globally and my C++ is somewhat rusty.

  36. achow101 cross-referenced this on Dec 8, 2020 from issue Coin selection algorithm not working as expected resulting in more fees by ghost
  37. achow101 commented at 12:23 AM on December 9, 2020: member

    I've added a commit to rewrite GroupOutputs based on the comments left in downstream PR review (https://github.com/bitcoin/bitcoin/pull/17331#discussion_r536209337)

  38. in src/wallet/wallet.cpp:4200 in 97256cabb3 outdated 
    4203 |  
4204 | -    for (const auto& output : outputs) {
4205 | -        if (output.fSpendable) {
4206 | -            CTxDestination dst;
4207 | -            CInputCoin input_coin = output.GetInputCoin();
4208 | +    if (single_coin) {
    murchandamus commented at 11:59 PM on December 9, 2020:

    Is this an optimization from the outside transferring the knowledge that all coins were received to separate destinations, or is this an instruction not to group coins? Assuming it's the latter, I would suggest separate_coins: true or group_coins: false.

    achow101 commented at 1:21 AM on December 10, 2020:

    Changed to separate_coins

  39. in src/wallet/wallet.cpp:4262 in 97256cabb3 outdated 
    4295 | +        group->Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants, positive_only);
4296 | +    }
4297 | +
4298 | +    // Now we go through the entire map and pull out the OutputGroups
4299 | +    for (const auto& groups_pair : groups_map) {
4300 | +        const std::vector<OutputGroup>& groups = groups_pair.second;
    murchandamus commented at 12:28 AM on December 10, 2020:

    groups ⇒ output_groups_per_spk

    achow101 commented at 1:21 AM on December 10, 2020:

    Changed to groups_per_spk

  40. in src/wallet/wallet.cpp:4227 in 97256cabb3 outdated 
    4260 | +    // except when there are more than OUTPUT_GROUP_MAX_ENTRIES COutputs grouped in an OutputGroup.
4261 | +    // To do this, we maintain a map where the key is the scriptPubKey and the value is a vector of OutputGroups.
4262 | +    // For each COutput, we check if the scriptPubKey is in the map, and if it is, the COutput's CInputCoin is added
4263 | +    // to the last OutputGroup in the vector for the scriptPubKey. When the last OutputGroup has
4264 | +    // OUTPUT_GROUP_MAX_ENTRIES CInputCoins, a new OutputGroup is added to the end of the vector.
4265 | +    std::map<CScript, std::vector<OutputGroup>> groups_map;
    murchandamus commented at 12:33 AM on December 10, 2020:

    groups_map ⇒ spk_to_output_groups_map

    achow101 commented at 1:21 AM on December 10, 2020:

    Changed to spk_to_groups_map

  41. in src/wallet/wallet.cpp:4261 in 97256cabb3 outdated 
    4294 | +        // Add the input_coin to group
4295 | +        group->Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants, positive_only);
4296 | +    }
4297 | +
4298 | +    // Now we go through the entire map and pull out the OutputGroups
4299 | +    for (const auto& groups_pair : groups_map) {
    murchandamus commented at 12:34 AM on December 10, 2020:

    groups_pair ⇒ spk_and_output_groups

    achow101 commented at 1:21 AM on December 10, 2020:

    Changed to spk_and_groups_pair

  42. murchandamus commented at 12:43 AM on December 10, 2020: contributor

    Just reviewed 97256cabb3723dee32dc20aade7d3ae618cff59c

    It's much clearer, thank you also for the illustrative comments. Have a few naming suggestions.

  43. Rewrite OutputGroups to be clearer and to use scriptPubKeys
    Rewrite OutputGroups so that the logic is easier to follow and
understand.

There is a slight behavior change as OutputGroups will be grouped by
scriptPubKey rather than CTxDestination as before. This should have no
effect on users as all addresses are a CTxDestination. However by using
scriptPubKeys, we can correctly group outputs which fall into the
NoDestination case. But we also shouldn't have any NoDestination
outputs.
    5d4597666d
  44. achow101 force-pushed on Dec 10, 2020
  45. murchandamus commented at 3:31 AM on December 10, 2020: contributor

    Code review ACK: https://github.com/bitcoin/bitcoin/pull/20040/commits/5d4597666d589e39354e0d8dd5b2afbe1a5d7d8e

  46. in src/wallet/coinselection.h:88 in 99b399aba5 outdated 
      89 | +
  90 |      void Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants);
  91 |      std::vector<CInputCoin>::iterator Discard(const CInputCoin& output);
  92 |      bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
  93 |  
  94 | -    //! Update the OutputGroup's fee, long_term_fee, and effective_value based on the given feerates
    fjahr commented at 5:27 PM on January 1, 2021:

    in 99b399aba5d27476b61b4865cc39553d03965d57

    nit: Maybe add a similar comment to Insert that this updates the fees now if you retouch.

  47. in src/wallet/coinselection.cpp:305 in 416d74fb16 outdated 
     299 | @@ -300,16 +300,24 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
 300 |  
 301 |   ******************************************************************************/
 302 |  
 303 | -void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
 304 | +void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only) {
 305 | +    // Compute the effective value first
 306 | +    const CAmount coin_fee = output.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.m_input_bytes);
    fjahr commented at 5:36 PM on January 1, 2021:

    in 416d74fb1687ae1d47a58c153d09d9afe0b6dc60

    nit: I think you could skip both intermediary vars (coin_fee, ev) here and instead set the coin members here and use them in the following lines without hurting readability.

  48. in src/wallet/wallet.h:844 in 416d74fb16 outdated 
     840 | @@ -841,7 +841,7 @@ class CWallet final : public WalletStorage, public interfaces::Chain::Notificati
 841 |      bool IsSpentKey(const uint256& hash, unsigned int n) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
 842 |      void SetSpentKeyState(WalletBatch& batch, const uint256& hash, unsigned int n, bool used, std::set<CTxDestination>& tx_destinations) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
 843 |  
 844 | -    std::vector<OutputGroup> GroupOutputs(const std::vector<COutput>& outputs, bool single_coin, const size_t max_ancestors, const CFeeRate& effective_feerate, const CFeeRate& long_term_feerate, const CoinEligibilityFilter& filter) const;
 845 | +    std::vector<OutputGroup> GroupOutputs(const std::vector<COutput>& outputs, bool single_coin, const size_t max_ancestors, const CFeeRate& effective_feerate, const CFeeRate& long_term_feerate, const CoinEligibilityFilter& filter, bool positive_only) const;
    fjahr commented at 5:44 PM on January 1, 2021:

    in 416d74fb1687ae1d47a58c153d09d9afe0b6dc60

    nit: maybe make positive_only const as well?

  49. in src/wallet/wallet.cpp:2492 in f6b3052739 outdated 
    2488 | @@ -2489,8 +2489,8 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
2489 |          (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2490 |          (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2491 |          (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2492 | -        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
2493 | -        (m_spend_zero_conf_change && !fRejectLongChains && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max()), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
2494 | +        (m_spend_zero_conf_change && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) ||
    fjahr commented at 5:57 PM on January 1, 2021:

    in f6b305273910db0e46798d361413a7e878cb45f7

    Now since max_descendants and partial_groups are decoupled it could be discussed if it stays like this or if this coin selection step is split up into one which only tries with the old config (leaving out partial groups) and then one after that adds partial groups. But it can be left for a follow-up if that change is desired.

  50. in src/wallet/wallet.cpp:4201 in 5d4597666d 
    4204 | -    for (const auto& output : outputs) {
4205 | -        if (output.fSpendable) {
4206 | -            CTxDestination dst;
4207 | -            CInputCoin input_coin = output.GetInputCoin();
4208 | +    if (separate_coins) {
4209 | +        // Single coin means no grouping. Each COutput gets its own OutputGroup.
    fjahr commented at 6:10 PM on January 1, 2021:

    in 5d4597666d589e39354e0d8dd5b2afbe1a5d7d8e

    nit: update comment "Single coin" => "Separate coin"

  51. in src/wallet/wallet.cpp:4215 in 5d4597666d 
    4243 | +            // Make an OutputGroup containing just this output
4244 | +            OutputGroup group{effective_feerate, long_term_feerate};
4245 | +            group.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants, positive_only);
4246 | +
4247 | +            // Check the OutputGroup's eligibility. Only add the eligible ones.
4248 | +            if (positive_only && group.effective_value <= 0) continue;
    fjahr commented at 6:33 PM on January 1, 2021:

    in 5d4597666d589e39354e0d8dd5b2afbe1a5d7d8e

    There is already the effectively same check in Insert so I think the following line is enough (group.m_outputs.size() > 0) and this one can safely be removed.

  52. in src/wallet/wallet.cpp:4262 in 5d4597666d 
    4295 | +        group->Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants, positive_only);
4296 | +    }
4297 | +
4298 | +    // Now we go through the entire map and pull out the OutputGroups
4299 | +    for (const auto& spk_and_groups_pair: spk_to_groups_map) {
4300 | +        const std::vector<OutputGroup>& groups_per_spk= spk_and_groups_pair.second;
    fjahr commented at 9:16 PM on January 1, 2021:

    in 5d4597666d589e39354e0d8dd5b2afbe1a5d7d8e

    whitespace missing before =

  53. in src/wallet/wallet.cpp:4265 in 5d4597666d 
    4298 | +    // Now we go through the entire map and pull out the OutputGroups
4299 | +    for (const auto& spk_and_groups_pair: spk_to_groups_map) {
4300 | +        const std::vector<OutputGroup>& groups_per_spk= spk_and_groups_pair.second;
4301 | +
4302 | +        // Go through the vector backwards. This allows for the first item we deal with being the partial group.
4303 | +        for (auto group_it = groups_per_spk.rbegin(); group_it != groups_per_spk.rend(); group_it++) {
    fjahr commented at 9:18 PM on January 1, 2021:

    in 5d4597666d589e39354e0d8dd5b2afbe1a5d7d8e

    nit: ++group_it

  54. in src/wallet/wallet.cpp:4274 in 5d4597666d 
    4308 |                  continue;
4309 |              }
4310 | -            // If the OutputGroup is not eligible, don't add it
4311 | +
4312 | +            // Check the OutputGroup's eligibility. Only add the eligible ones.
4313 |              if (positive_only && group.effective_value <= 0) continue;
    fjahr commented at 9:20 PM on January 1, 2021:

    in 5d4597666d589e39354e0d8dd5b2afbe1a5d7d8e

    same as above, I think this is not necessary since Insert takes care of this now.

  55. in src/wallet/wallet.cpp:4235 in 5d4597666d 
    4268 | +        if (!output.fSpendable) continue;
4269 | +
4270 | +        size_t ancestors, descendants;
4271 | +        chain().getTransactionAncestry(output.tx->GetHash(), ancestors, descendants);
4272 | +        CInputCoin input_coin = output.GetInputCoin();
4273 | +        CScript spk = input_coin.txout.scriptPubKey;
    fjahr commented at 9:23 PM on January 1, 2021:

    in 5d4597666d589e39354e0d8dd5b2afbe1a5d7d8e

    nit: spk seems to be only used in the line below so I would drop it.

  56. in src/bench/coin_selection.cpp:45 in 6148a8acda outdated 
      41 | @@ -42,21 +42,19 @@ static void CoinSelection(benchmark::Bench& bench)
  42 |      }
  43 |      addCoin(3 * COIN, wallet, wtxs);
  44 |  
  45 | -    // Create groups
  46 | -    std::vector<OutputGroup> groups;
  47 | +    // Create coins
    fjahr commented at 9:30 PM on January 1, 2021:

    in 6148a8acda5e594bb9b3b2d989056f9e03ddbdbd

    nit: This comment isn't that helpful, I would suggest something like "Prepare coins in a format that can be passed to SelectCoinsMinConf()"

  57. in src/wallet/wallet.cpp:2384 in 6148a8acda outdated 
    2380 | @@ -2381,6 +2381,8 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil
2381 |          temp.m_confirm_target = 1008;
2382 |          CFeeRate long_term_feerate = GetMinimumFeeRate(*this, temp, &feeCalc);
2383 |  
2384 | +        std::vector<OutputGroup> groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, eligibility_filter.max_ancestors);
    fjahr commented at 9:33 PM on January 1, 2021:

    in 6148a8acda5e594bb9b3b2d989056f9e03ddbdbd

    This line seems to be the same in both if-else blocks so it could be moved to the beginning of the function before the if

    fjahr commented at 10:02 PM on January 1, 2021:

    Ah, never mind, it becomes necessary later when the positive_only param is added

  58. fjahr commented at 9:58 PM on January 1, 2021: contributor

    Code review ACK 5d4597666d589e39354e0d8dd5b2afbe1a5d7d8e

    Nice refactoring! I had a bunch of suggestions for small improvements but I don't consider them blocking for a merge.

    One more comment: The behavior change in 416d74fb1687ae1d47a58c153d09d9afe0b6dc60 could be noted a little more explicitly I think. Before this change, the OutputGroups are filled up and then filtered for positive-only later, sometimes then using groups that are not filled completely in coin selection. Now, since the non-positive coins are never inserted we will have full groups with only positive values. This will lead to different results in certain cases. I think this is an improvement and I don't see any issues arise from it but it wouldn't hurt to mention it in the commit message as it is in 5d4597666d589e39354e0d8dd5b2afbe1a5d7d8e.

  59. achow101 commented at 7:14 PM on January 28, 2021: member

    @fjahr Since this now has two ACKs, I'm going to leave this as-is for now.

  60. fanquake requested review from meshcollider on Jan 29, 2021
  61. fanquake requested review from instagibbs on Jan 29, 2021
  62. meshcollider commented at 9:02 AM on February 1, 2021: contributor

    Light utACK 5d4597666d589e39354e0d8dd5b2afbe1a5d7d8e

    Nice cleanup thanks Andrew!

  63. meshcollider merged this on Feb 1, 2021
  64. meshcollider closed this on Feb 1, 2021
  65. meshcollider removed this from the "Blockers" column in a project
  66. sidhujag referenced this in commit d9c59c9bce on Feb 2, 2021
  67. bitcoin locked this on Aug 16, 2022
Contributors
achow101DrahtBotinstagibbsfanquakemurchandamusfjahrmeshcollider


instagibbs

Labels
Wallet
Linked (view graph)
#17211 Allow fundrawtransaction and walletcreatefundedpsbt to take external inputs#17331 Use effective values throughout coin selection#17458 Refactor OutputGroup effective value calculations and filtering to occur within the struct#20598 Coin selection algorithm not working as expected resulting in more fees
github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-05-20 06:54 UTC