wallet: document coin selection code

glozow commented at 8:43 pm on April 22, 2021: member

I think it would help code review to have more documentation + doxygen comments

[docs] format existing comments as doxygen

Co-authored-by: Xekyo <murch@murch.one>

0c74716c50

glozow commented at 8:52 pm on April 22, 2021: member

Thanks @Xekyo for explaining all the stuffs to me

DrahtBot commented at 9:06 pm on April 22, 2021: member

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#21359 (rpc: include_unsafe option for fundrawtransaction by t-bast)
#21207 (MOVEONLY: CWallet transaction code out of wallet.cpp/.h by ryanofsky)
#21206 (refactor: Make CWalletTx sync state type-safe by ryanofsky)
#17526 (Use Single Random Draw In addition to knapsack as coin selection fallback by achow101)
#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.

DrahtBot added the label Wallet on Apr 22, 2021

kiminuo commented at 11:22 am on April 23, 2021: contributor

Concept ACK, great job.

darosior commented at 9:54 pm on April 23, 2021: member

Concept ACK

Just need to re-read the (awesome) refactoring in the last commit when it’s earlier in the day :)

in src/wallet/coinselection.h:71 in b74797a5e3 outdated

66+     * We may use unconfirmed UTXOs sent from ourselves, e.g. change outputs. */
67     const int conf_mine;
68+    /** Minimum number of confirmations for outputs received from a different
69+     * wallet. We never spend unconfirmed foreign outputs as we cannot rely on these funds yet. */
70     const int conf_theirs;
71+    /** Maximum number of total unconfirmed ancestors for all UTXOs in the OutputGroup. */

Xekyo commented at 11:54 am on April 26, 2021:

I think this may be slightly more clear:

0    /** Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup. */

in src/wallet/coinselection.h:89 in b74797a5e3 outdated

85 struct OutputGroup
86 {
87+    /** The list of UTXOs contained in this output group. */
88     std::vector<CInputCoin> m_outputs;
89+    /** Whether the UTXOs were sent by the wallet to itself. This is relevant because we may want at
90+     * least certain number of confirmations on UTXOs received from outside wallets while trusting

Xekyo commented at 11:56 am on April 26, 2021:

0     * least a certain number of confirmations on UTXOs received from outside wallets while trusting

in src/wallet/wallet.h:618 in b74797a5e3 outdated

611@@ -604,17 +612,28 @@ class COutput
612     }
613 };
614 
615+/** Parameters for one iteration of Coin Selection. */
616 struct CoinSelectionParams
617 {
618+    /** When true, try to use the Branch and Bound algorithm before falling back to knapsack. */

Xekyo commented at 12:06 pm on April 26, 2021:

Since this is a patch to master, I think use_bnb still means “only use BnB”. The try BnB first and then fall back to knapsack behavior gets introduced by #17331.

0    /** Toggles use of the Branch and Bound coin selection algorithm instead of the knapsack solver. */

in src/wallet/wallet.h:626 in b74797a5e3 outdated

621     size_t change_output_size = 0;
622+    /** Size of the input to spend a change output in virtual bytes. */
623     size_t change_spend_size = 0;
624+    /** The targeted feerate of the transaction being built. */
625     CFeeRate m_effective_feerate;
626+    /** The feerate estimate used to calculate the upper bound of the cost to spend a change output. */

Xekyo commented at 12:17 pm on April 26, 2021:

Mh, this one is a bit more subtle. How about:

0    /** The feerate used to estimate an upper bound on what should be sufficient to spend the change output some time in the future. */

in src/wallet/wallet.h:630 in b74797a5e3 outdated

625     CFeeRate m_effective_feerate;
626+    /** The feerate estimate used to calculate the upper bound of the cost to spend a change output. */
627     CFeeRate m_long_term_feerate;
628+    /** If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees. */
629     CFeeRate m_discard_feerate;
630+    /** Size of the transaction before inputs are selected, the header and recipient output(s). */

Xekyo commented at 12:24 pm on April 26, 2021:

How about

0    /** Size of the transaction before coin selection, consisting of the header and recipient outputs and excluding inputs and change output(s). */

in src/wallet/wallet.h:779 in b74797a5e3 outdated

775@@ -753,8 +776,11 @@ class CWallet final : public WalletStorage, public interfaces::Chain::Notificati
776 
777     /**
778      * Select a set of coins such that nValueRet >= nTargetValue and at least
779-     * all coins from coinControl are selected; Never select unconfirmed coins
780-     * if they are not ours
781+     * all coins from coin_ontrol are selected; Never select unconfirmed coins if they are not ours

Xekyo commented at 12:27 pm on April 26, 2021:

0     * all coins from coin_control are selected; never select unconfirmed coins if they are not ours.

in src/wallet/wallet.h:1068 in b74797a5e3 outdated

1063@@ -1025,7 +1064,12 @@ class CWallet final : public WalletStorage, public interfaces::Chain::Notificati
1064      * Override with -fallbackfee
1065      */
1066     CFeeRate m_fallback_fee{DEFAULT_FALLBACK_FEE};
1067+
1068+    /** If the cost to spend a change output at this rate is greater than the value of the output

Xekyo commented at 12:29 pm on April 26, 2021:

0   /** If the cost to spend a change output at this feerate is greater than the value of the output

in src/wallet/wallet.cpp:2508 in 25d8a0be62 outdated

2512-        (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 /* include_partial_groups */), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
2513 
2514-    // because SelectCoinsMinConf clears the setCoinsRet, we now add the possible inputs to the coinset
2515+    // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the
2516+    // transaction at a target value and feerate. If an attempt fails, more attempts may be made
2517+    // using a more permissive CoinEligibilityFilter.

Xekyo commented at 12:34 pm on April 26, 2021:

“at a target value and feerate” sounds a bit odd to me. Maybe:

0    // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the
1    // transaction at a target feerate. If an attempt fails, more attempts may be made
2    // using a more permissive CoinEligibilityFilter.

in src/wallet/wallet.cpp:2515 in 25d8a0be62 outdated

2519+        // Pre-selected inputs already cover the target amount.
2520+        if (value_to_select <= 0) return true;
2521+
2522+        // If possible, fund the transaction with confirmed UTXOs only. Prefer at least six
2523+        // confirmations on outputs received from other wallets and only spend confirmed change.
2524+        if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) return true;

Xekyo commented at 12:46 pm on April 26, 2021:

Reviewers note that each SelectCoinsMinConf call here shares the same parameters except for differing CoinEligibilityFilters.

Xekyo commented at 12:46 pm on April 26, 2021: member

Code review ACK 25d8a0be62f3ee821178da51633bc38b97ce84b4 Got a few optional suggestions, and a couple places that should perhaps be slightly amended.

[docs] add doxygen comments to wallet code

Co-authored-by: Xekyo <murch@murch.one>

58ea324fdd

refactor + document coin selection strategy

Co-authored-by: Xekyo <murch@murch.one>

6ba892126d

glozow force-pushed on Apr 26, 2021

glozow commented at 6:03 pm on April 26, 2021: member

Thanks @Xekyo, took all suggestions

Xekyo commented at 6:28 pm on April 26, 2021: member

ReACK https://github.com/bitcoin/bitcoin/commit/6ba892126d354219b146f0c7f35d472f9c14bdac

LGTM, @achow101, did we get this right?

achow101 commented at 6:35 pm on April 26, 2021: member

ACK 6ba892126d354219b146f0c7f35d472f9c14bdac

MarcoFalke added the label Docs on Apr 27, 2021

RiccardoMasutti approved

RiccardoMasutti commented at 11:46 am on April 27, 2021: contributor

ACK

fanquake merged this on Apr 29, 2021

fanquake closed this on Apr 29, 2021

glozow deleted the branch on Apr 29, 2021

sidhujag referenced this in commit f10ede6efd on Apr 29, 2021

gwillen referenced this in commit a8362769f4 on Jun 1, 2022

DrahtBot locked this on Aug 16, 2022

wallet: document coin selection code #21759

Conflicts