Add Single Random Draw as an additional coin selection algorithm

achow101 commented at 10:47 pm on November 19, 2019: member

To ease in the use of SRD as our fallback mechanism, this PR adds it as a secondary fallback algorithm in addition to the knapsack solver. Since #22009, the solution with the least waste will be chosen. This pattern is continued with SRD simply being another solution whose waste is compared.

achow101 commented at 10:49 pm on November 19, 2019: member

Some simulations results: https://gist.github.com/achow101/edf6b5e308035a489fbb1f28d12e2109

I think the important thing to see here is that this is the same or better in every metric except for “mean UTXOs”. But I think the thing to note here is that it’s about the same mean UTXOs as the positive only effective value simulation. So I think the different there is primarily due to dust outputs that aren’t being consumed.

fanquake added the label Wallet on Nov 19, 2019

DrahtBot commented at 2:17 am on November 20, 2019: 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:

#17211 (Allow fundrawtransaction and walletcreatefundedpsbt to take external inputs 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 Needs rebase on Nov 22, 2019

achow101 force-pushed on Nov 22, 2019

DrahtBot removed the label Needs rebase on Nov 22, 2019

achow101 force-pushed on Nov 25, 2019

DrahtBot added the label Needs rebase on Dec 1, 2019

achow101 force-pushed on Dec 2, 2019

DrahtBot removed the label Needs rebase on Dec 2, 2019

laanwj added the label Feature on Mar 27, 2020

DrahtBot added the label Needs rebase on Apr 17, 2020

achow101 force-pushed on Apr 19, 2020

DrahtBot removed the label Needs rebase on Apr 19, 2020

DrahtBot added the label Needs rebase on May 4, 2020

achow101 force-pushed on May 4, 2020

DrahtBot removed the label Needs rebase on May 4, 2020

Xekyo commented at 2:37 am on June 15, 2020: member

Concept ACK. The results look promising!

“Better” is defined as having lower fees. If the fees are the same, then the one that chooses more inputs (so consolidates more). If that is also the same, Knapsack is then used (i.e. Knapsack is preferred).

Since you already have a waste metric in BnB, have you considered using the waste metric to pick between the Knapsack and SRD?

in src/wallet/wallet.cpp:2265 in 885418e3f5 outdated

2270-        CFeeRate long_term_feerate = GetMinimumFeeRate(*this, temp, &feeCalc);
2271-
2272-        // Calculate cost of change
2273-        CAmount cost_of_change = GetDiscardRate(*this).GetFee(coin_selection_params.change_spend_size) + coin_selection_params.effective_fee.GetFee(coin_selection_params.change_output_size);
2274+    // Calculate the fees for things that aren't inputs
2275+    CAmount not_input_fees = coin_selection_params.effective_fee.GetFee(coin_selection_params.tx_noinputs_size);

Xekyo commented at 2:49 am on June 15, 2020:

not_input_fees is a bit hard to grok. How about fixed_fees, payload_fees, or fees_excluding_inputs?

in src/wallet/wallet.cpp:2397 in 885418e3f5 outdated

2288-            if (pos_group.effective_value > 0) utxo_pool.push_back(pos_group);
2289+    // Get long term estimate
2290+    FeeCalculation feeCalc;
2291+    CCoinControl temp;
2292+    temp.m_confirm_target = 1008;
2293+    CFeeRate long_term_feerate = GetMinimumFeeRate(*this, temp, &feeCalc);

Xekyo commented at 3:05 am on June 15, 2020:

Note to self: I assume this gets the minimum of the current fee rate and the 1008 block target.

in src/wallet/wallet.cpp:2408 in 885418e3f5 outdated

2292+    temp.m_confirm_target = 1008;
2293+    CFeeRate long_term_feerate = GetMinimumFeeRate(*this, temp, &feeCalc);
2294+
2295+    // Calculate cost of change
2296+    CAmount change_fee = coin_selection_params.effective_fee.GetFee(coin_selection_params.change_output_size);
2297+    CAmount cost_of_change = GetDiscardRate(*this).GetFee(coin_selection_params.change_spend_size) + change_fee;

Xekyo commented at 3:07 am on June 15, 2020:

Note to self: What was DiscardRate exactly?

Why do you use DiscardRate here and not long_term_feerate?

in src/wallet/wallet.cpp:2319 in 885418e3f5 outdated

2295+    // Calculate cost of change
2296+    CAmount change_fee = coin_selection_params.effective_fee.GetFee(coin_selection_params.change_output_size);
2297+    CAmount cost_of_change = GetDiscardRate(*this).GetFee(coin_selection_params.change_spend_size) + change_fee;
2298+
2299+    // Filter by the min conf specs and add to utxo_pool and calculate effective value
2300+    std::vector<OutputGroup> positive_groups;

Xekyo commented at 4:03 am on June 15, 2020:

I assume positive_groups pertains to the spendable_utxo?

in src/wallet/wallet.cpp:2321 in 885418e3f5 outdated

2297+    CAmount cost_of_change = GetDiscardRate(*this).GetFee(coin_selection_params.change_spend_size) + change_fee;
2298+
2299+    // Filter by the min conf specs and add to utxo_pool and calculate effective value
2300+    std::vector<OutputGroup> positive_groups;
2301+    std::vector<OutputGroup> all_groups;
2302+    for (OutputGroup& group : groups) {

Xekyo commented at 4:05 am on June 15, 2020:

I do not understand why they are called OutputGroup. I figure you are filtering each UTXO for whether it is economically spendable. How are these UTXO a group, and not just single UTXO?

Xekyo commented at 4:14 am on June 15, 2020:

Aaah, are we talking about ancestry sets of outputs?

achow101 commented at 3:29 pm on June 15, 2020:

The have the same scriptPubKey. IIRC it’s for the avoid reuse stuff. Most of the time, they will be single UTXOs.

in src/wallet/wallet.cpp:2298 in 885418e3f5 outdated

2324-            if (!group.EligibleForSpending(eligibility_filter)) continue;
2325-            utxo_pool.push_back(group);
2326-        }
2327         bnb_used = false;
2328-        return KnapsackSolver(nTargetValue, utxo_pool, setCoinsRet, nValueRet);
2329+        return KnapsackSolver(nTargetValue + not_input_fees, all_groups, setCoinsRet, nValueRet);

Xekyo commented at 4:08 am on June 15, 2020:

all_groups here are all UTXO not just the economically spendable?

achow101 commented at 3:29 pm on June 15, 2020:

Yes.

in src/wallet/wallet.cpp:2493 in 885418e3f5 outdated

2346-            if (coin_selection_params.use_bnb) {
2347-                value_to_select -= coin.effective_value;
2348-            } else {
2349-                value_to_select -= coin.txout.nValue;
2350-            }
2351+            coin.effective_value = coin.txout.nValue - (coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.effective_fee.GetFee(coin.m_input_bytes));

Xekyo commented at 4:11 am on June 15, 2020:

Shouldn’t the 0 be the second outcome of the tertiary statement here? If coin_selection_params.m_subtract_fee_outputs is truthy, shouldn’t then the fee be deducted?

in src/wallet/coinselection.cpp:359 in 0bfc40037e outdated

337+{
338+    fee = 0;
339+    long_term_fee = 0;
340+    effective_value = 0;
341+    for (CInputCoin& coin : m_outputs) {
342+        coin.m_fee = coin.m_input_bytes < 0 ? 0 : effective_feerate.GetFee(coin.m_input_bytes);

Xekyo commented at 5:05 am on June 15, 2020:

I’m curious, how come coin.m_input_bytes can be smaller than 0 here?

achow101 commented at 4:19 pm on June 15, 2020:

The default value is -1 to indicate that it isn’t set.

in src/wallet/coinselection.cpp:365 in 0bfc40037e outdated

343+        fee += coin.m_fee;
344+
345+        coin.m_long_term_fee = coin.m_input_bytes < 0 ? 0 : long_term_feerate.GetFee(coin.m_input_bytes);
346+        long_term_fee += coin.m_long_term_fee;
347+
348+        coin.effective_value = coin.txout.nValue - coin.m_fee;

Xekyo commented at 5:08 am on June 15, 2020:

Wouldn’t the above case where coin.m_input_bytes is smaller than 0 overstate the effective_value of the coin here? Would it not be better to set the effective_value of a coin whose size is haywire to 0 or negative here?

in src/wallet/coinselection.cpp:370 in 0bfc40037e outdated

348+        coin.effective_value = coin.txout.nValue - coin.m_fee;
349+        effective_value += coin.effective_value;
350+    }
351+}
352+
353+OutputGroup OutputGroup::GetPositiveOnlyGroup()

Xekyo commented at 5:10 am on June 15, 2020:

“Positive” is rather unspecific. How about calling this GetSpendableGroup()?

achow101 commented at 4:21 pm on June 15, 2020:

How is Positive unspecific? The OutputGroup has only Positive effective values.

in src/wallet/wallet.cpp:2282 in 0bfc40037e outdated

2296-                    it = group.Discard(coin);
2297-                }
2298+            if (coin_selection_params.m_subtract_fee_outputs) {
2299+                group.SetFees(CFeeRate(0), long_term_feerate);
2300+            } else {
2301+                group.SetFees(coin_selection_params.effective_fee, long_term_feerate);

Xekyo commented at 5:14 am on June 15, 2020:

Isn’t coin_selection_params.effective_fee a fee rate?

achow101 commented at 3:33 pm on June 15, 2020:

Yes. It is a CFeeRate

in src/wallet/coinselection.cpp:52 in 9cb997a8a2 outdated

47@@ -48,28 +48,25 @@ struct {
48  * @param const std::vector<CInputCoin>& utxo_pool The set of UTXOs that we are choosing from.
49  *        These UTXOs will be sorted in descending order by effective value and the CInputCoins'
50  *        values are their effective values.
51- * @param const CAmount& target_value This is the value that we want to select. It is the lower
52+ * @param const CAmount& actual_target This is the value that we want to select. It is the lower

Xekyo commented at 5:18 am on June 15, 2020:

Nice clean-up. From what I understand, actual_target is the sum of the recipient outputs plus the precalculable overhead and output costs. If that’s the case, maybe amend the comment to clarify that. What do you think of selection_target instead of actual_target?

in src/wallet/wallet.cpp:2858 in 919abc311d outdated

2698@@ -2701,209 +2699,159 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CTransac
2699             CFeeRate discard_rate = GetDiscardRate(*this);
2700 
2701             // Get the fee rate to use effective values in coin selection
2702-            CFeeRate nFeeRateNeeded = GetMinimumFeeRate(*this, coin_control, &feeCalc);
2703+            coin_selection_params.effective_fee = GetMinimumFeeRate(*this, coin_control, &feeCalc);

Xekyo commented at 5:21 am on June 15, 2020:

I think that’s a fee rate. Would not effective_fee_rate be then a better name?

in src/wallet/wallet.cpp:2949 in 919abc311d outdated

2721+            txNew.vin.clear();
2722+            txNew.vout.clear();
2723 
2724-                // vouts to the payees
2725+            // vouts to the payees
2726+            if (!coin_selection_params.m_subtract_fee_outputs) {

Xekyo commented at 5:25 am on June 15, 2020:

Now that I think about it… assuming this is pertaining to a mode where the fees are deducted from the recipient output, and the output groups are considered with their actual values instead of their fee rates: have you considered the impact on the outcome for BnB selection? Would be kinda harsh if it suddenly considered all dust inputs spendable, burned a bunch of economically unspendable inputs and then deducted it from the recipient.

in src/wallet/wallet.cpp:2950 in 919abc311d outdated

2722+            txNew.vout.clear();
2723 
2724-                // vouts to the payees
2725+            // vouts to the payees
2726+            if (!coin_selection_params.m_subtract_fee_outputs) {
2727+                coin_selection_params.tx_noinputs_size = 11; // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 output count, 1 witness overhead (dummy, flag, stack size)

Xekyo commented at 5:28 am on June 15, 2020:

I’ve seen the witness element count been counted towards the witness block usually before. Are people now counting it to the transaction header? How come we are not counting in WU? :thinking:

achow101 commented at 3:41 pm on June 15, 2020:

This parameter is just generally all of the overhead, regardless of it’s location in a transaction. It’s in vbytes, which is weight / 4

in src/wallet/wallet.cpp:2818 in 919abc311d outdated

2728+            }
2729+            for (const auto& recipient : vecSend)
2730+            {
2731+                CTxOut txout(recipient.nAmount, recipient.scriptPubKey);
2732+
2733+                // Include the fee cost for outputs. Note this is only used for BnB right now

Xekyo commented at 5:32 am on June 15, 2020:

I’m confused. Previously I thought that m_subtract_fee_outputs deducts the cost of the transaction from the recipient outputs. This comment seems to indicate that it’s just the cost of the outputs.

achow101 commented at 3:45 pm on June 15, 2020:

tx_noinputs_size becomes not_input_fees later which ultimately increases the selection target so that the selection target covers the fees for the transaction. When subtracting the fee from the outputs, the selection target should not be increasing to cover the fees.

in src/wallet/wallet.cpp:2844 in 919abc311d outdated

2798+            // Choose coins to use
2799+            CAmount selected_value = 0;
2800+            setCoins.clear();
2801+            int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this);
2802+            // If the wallet doesn't know how to sign change output, assume p2sh-p2wpkh
2803+            // as lower-bound to allow BnB to do it's thing

Xekyo commented at 5:35 am on June 15, 2020:

Given that this would be 32 B, but a non-segwit change output could be 34 B, wouldn’t it be more conservative to use 34 B? Can we rely that it will always use segwit addresses?

achow101 commented at 3:48 pm on June 15, 2020:

This is moved code, so I think it should remain as is.

in src/wallet/wallet.cpp:2996 in 919abc311d outdated

2859+                {
2860+                    if (nChangePosInOut == -1)
2861                     {
2862-                        nChangePosInOut = -1;
2863-                        nFeeRet += nChange;
2864+                        // Insert change txn at random position:

Xekyo commented at 5:37 am on June 15, 2020:

“change output”

in src/wallet/wallet.cpp:2997 in 919abc311d outdated

2860+                    if (nChangePosInOut == -1)
2861                     {
2862-                        nChangePosInOut = -1;
2863-                        nFeeRet += nChange;
2864+                        // Insert change txn at random position:
2865+                        nChangePosInOut = GetRandInt(txNew.vout.size()+1);

Xekyo commented at 5:37 am on June 15, 2020:

Does Bitcoin Core not use BIP-69? Or will the outputs be sorted afterwards when the amounts are all fixed?

achow101 commented at 3:49 pm on June 15, 2020:

No.

in src/wallet/wallet.cpp:3026 in 919abc311d outdated

2965+            if (feeCalc.reason == FeeReason::FALLBACK && !m_allow_fallback_fee) {
2966+                // eventually allow a fallback fee
2967+                error = _("Fee estimation failed. Fallbackfee is disabled. Wait a few blocks or enable -fallbackfee.");
2968+                return false;
2969+            }
2970+            if (nFeeRet < fee_needed) {

Xekyo commented at 5:42 am on June 15, 2020:

It’s surprising to me that the nFeeRet could be lower than a minimum fee here. Wouldn’t the fee rate on the input side of transaction building need to be bigger than GetMinimumFee?

in src/wallet/wallet.cpp:2915 in 919abc311d outdated

2911@@ -2964,7 +2912,7 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CTransac
2912     reservedest.KeepDestination();
2913 
2914     WalletLogPrintf("Fee Calculation: Fee:%d Bytes:%u Needed:%d Tgt:%d (requested %d) Reason:\"%s\" Decay %.5f: Estimation: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
2915-              nFeeRet, nBytes, nFeeNeeded, feeCalc.returnedTarget, feeCalc.desiredTarget, StringForFeeReason(feeCalc.reason), feeCalc.est.decay,
2916+              nFeeRet, nBytes, nFeeRet, feeCalc.returnedTarget, feeCalc.desiredTarget, StringForFeeReason(feeCalc.reason), feeCalc.est.decay,

Xekyo commented at 5:45 am on June 15, 2020:

Why did you overwrite nFeeNeeded with nFeeRet here?

achow101 commented at 3:50 pm on June 15, 2020:

nFeeNeeded no longer exists. This should have been removed already. I probably forgot to rebase this branch.

achow101 commented at 3:52 pm on June 15, 2020: member

@Xekyo This PR is built on top of 2 other PRs. It would be better to review those first as many of your comments are for the changes in those PRs. You should start with #17458, then #17331, then this one.

Xekyo commented at 4:45 pm on June 15, 2020: member

@achow101: Okay, I’ll take a look at them.

DrahtBot added the label Needs rebase on Jun 16, 2020

achow101 force-pushed on Jun 17, 2020

DrahtBot removed the label Needs rebase on Jun 17, 2020

DrahtBot added the label Needs rebase on Jul 30, 2020

achow101 force-pushed on Jul 30, 2020

DrahtBot removed the label Needs rebase on Jul 30, 2020

achow101 force-pushed on Aug 11, 2020

achow101 force-pushed on Aug 17, 2020

achow101 force-pushed on Sep 30, 2020

achow101 force-pushed on Oct 1, 2020

DrahtBot added the label Needs rebase on Oct 21, 2020

achow101 force-pushed on Oct 21, 2020

DrahtBot removed the label Needs rebase on Oct 21, 2020

achow101 force-pushed on Oct 22, 2020

achow101 force-pushed on Nov 10, 2020

DrahtBot added the label Needs rebase on Nov 17, 2020

achow101 force-pushed on Nov 17, 2020

DrahtBot removed the label Needs rebase on Nov 17, 2020

achow101 force-pushed on Nov 17, 2020

in src/wallet/coinselection.cpp:175 in 82525ebeae outdated

166@@ -167,6 +167,24 @@ bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& actual_t
167     return true;
168 }
169 
170+bool SelectCoinsSRD(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, std::set<CInputCoin>& out_set, CAmount& value_ret)
171+{
172+    out_set.clear();
173+    value_ret = 0;
174+
175+    CAmount selected_value = 0;

Xekyo commented at 11:27 pm on December 8, 2020:

Consider naming this selected_eff_value

achow101 commented at 1:36 am on December 9, 2020:

Done

in src/wallet/wallet.cpp:2427 in c1d39948b2 outdated

2394+        knapsack_fees += coin.m_fee;
2395+    }
2396+
2397+    std::set<CInputCoin> srd_coins;
2398+    CAmount srd_value;
2399+    bool srd_ret = SelectCoinsSRD(positive_groups, nTargetValue + change_fee + MIN_FINAL_CHANGE, srd_coins, srd_value);

Xekyo commented at 11:35 pm on December 8, 2020:

Would be nice if the order of the parameters on KnapsackSolver and SelectCoinsSRD matched.

achow101 commented at 1:27 am on December 9, 2020:

It would, but changes to KnapsackSolver are out of scope for this PR. I prefer to use the current order for SelectCoinsSRD.

in src/wallet/wallet.cpp:2453 in c1d39948b2 outdated

2435+    } else {
2436+        // srd_coins.size() <= knapsack_coins.size()
2437+        setCoinsRet = knapsack_coins;
2438+        nValueRet = knapsack_value;
2439+        return true;
2440+    }

Xekyo commented at 11:45 pm on December 8, 2020:

How about:

 0if (knapsack_ret) {
 1        setCoinsRet = knapsack_coins;
 2        nValueRet = knapsack_value;
 3}
 4if (srd_ret) {
 5    // Use SRD if knapsack had no solution, SRD has lower fees, or SRD has more inputs for same fees
 6    if (!knapsack_ret || srd_fees < knapsack_fees || srd_fees == knapsack_fees && srd_coins.size() > knapsack_coins.size()) {
 7        setCoinsRet = srd_coins;
 8        nValueRet = srd_value;
 9    }
10}
11if (knapsack_ret || srd_ret) return true;
12
13// No solution
14setCoinsRet.clear();
15nValueRet = 0;
16return false;

achow101 commented at 1:36 am on December 9, 2020:

Done

Xekyo commented at 11:53 pm on December 8, 2020: member

Concept ACK

achow101 force-pushed on Dec 9, 2020

achow101 force-pushed on Jan 13, 2021

DrahtBot added the label Needs rebase on Feb 1, 2021

achow101 force-pushed on Feb 1, 2021

DrahtBot removed the label Needs rebase on Feb 1, 2021

jonatack commented at 6:20 pm on February 4, 2021: member

Concept ACK, will review if #17331 is merged.

DrahtBot added the label Needs rebase on Mar 8, 2021

achow101 force-pushed on Mar 10, 2021

DrahtBot removed the label Needs rebase on Mar 10, 2021

DrahtBot added the label Needs rebase on Mar 17, 2021

achow101 force-pushed on Mar 17, 2021

DrahtBot removed the label Needs rebase on Mar 17, 2021

DrahtBot added the label Needs rebase on Apr 29, 2021

achow101 force-pushed on Apr 29, 2021

DrahtBot removed the label Needs rebase on Apr 29, 2021

in src/wallet/coinselection.h:186 in fac99dcaf3 outdated

166 };
167 
168-bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees);
169+bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret);
170+
171+bool SelectCoinsSRD(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, std::set<CInputCoin>& out_set, CAmount& value_ret);

glozow commented at 9:43 pm on April 29, 2021:

Need dat doxygen (also to confirm my understanding)

0/** Select coins by Single Random Draw, picking random OutputGroups from utxo_pool until the target
1 * value is satisfied.
2 * [@param](/bitcoin-bitcoin/contributor/param/)[in]   utxo_pool   All eligible OutputGroups no additional filter will be applied.
3 * [@param](/bitcoin-bitcoin/contributor/param/)[out]  out_set     Populated with the coins selected. Any coins in the set will be cleared
4 *                          at the start, so don't put pre-selected coins here.
5 * [@param](/bitcoin-bitcoin/contributor/param/)[out]  value_ret   Total aggregated nValue of all selected coins.
6 * [@returns](/bitcoin-bitcoin/contributor/returns/) true if successful, false otherwise.
7 */
8bool SelectCoinsSRD(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, std::set<CInputCoin>& out_set, CAmount& value_ret);

jnewbery commented at 4:32 pm on May 3, 2021:

Please add doxygen comments for new functions.

achow101 commented at 7:26 pm on September 2, 2021:

Added docs.

achow101 commented at 7:27 pm on September 2, 2021:

Done

in src/wallet/wallet.cpp:2419 in fac99dcaf3 outdated

2425 
2426-        // Calculate cost of change
2427-        CAmount cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);
2428+    std::set<CInputCoin> knapsack_coins;
2429+    CAmount knapsack_value;
2430+    bool knapsack_ret = KnapsackSolver(nTargetValue + change_fee, all_groups, knapsack_coins, knapsack_value);

glozow commented at 10:20 pm on April 29, 2021:

0    const bool knapsack_ret = KnapsackSolver(nTargetValue + change_fee, all_groups, knapsack_coins, knapsack_value);

in src/wallet/wallet.cpp:2427 in fac99dcaf3 outdated

2439-        return SelectCoinsBnB(groups, nTargetValue, cost_of_change, setCoinsRet, nValueRet, not_input_fees);
2440-    } else {
2441-        std::vector<OutputGroup> groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, CFeeRate(0), CFeeRate(0), eligibility_filter, false /* positive_only */);
2442+    std::set<CInputCoin> srd_coins;
2443+    CAmount srd_value;
2444+    bool srd_ret = SelectCoinsSRD(positive_groups, nTargetValue + change_fee + MIN_FINAL_CHANGE, srd_coins, srd_value);

glozow commented at 10:20 pm on April 29, 2021:

0    const bool srd_ret = SelectCoinsSRD(positive_groups, nTargetValue + change_fee + MIN_FINAL_CHANGE, srd_coins, srd_value);

in src/wallet/coinselection.cpp:171 in fac99dcaf3 outdated

167@@ -171,6 +168,24 @@ bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_v
168     return true;
169 }
170 
171+bool SelectCoinsSRD(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, std::set<CInputCoin>& out_set, CAmount& value_ret)

glozow commented at 10:23 pm on April 29, 2021:

Pretty basic conceptual question, but why only SRD once? Why not run it, say, 100 times, and pick the best one before comparing with knapsack?

jnewbery commented at 4:57 pm on May 3, 2021:

Consider returning a std::optional<std::pair<std::set<CInputCoin>, CAmount>> rather than using out references and returning a bool to indicate success.

jnewbery commented at 4:58 pm on May 3, 2021:

Is there a reason this param is named utxo_pool rather than groups?

0bool SelectCoinsSRD(std::vector<OutputGroup>& groups, const CAmount& target_value, std::set<CInputCoin>& out_set, CAmount& value_ret)

jnewbery commented at 4:58 pm on May 3, 2021:

Pass simple types like CAmount by value:

0bool SelectCoinsSRD(std::vector<OutputGroup>& utxo_pool, CAmount target_value, std::set<CInputCoin>& out_set, CAmount& value_ret)

Xekyo commented at 5:42 pm on June 11, 2021:

That would minimize the input set at high fees and maximize the input set at low fees. If you wanted that, you could directly do largest first selection at high fees and smallest first at low fees. My gut feeling would be that it would grind down the larger UTXOs and very aggressively consolidate your smallest UTXOs at low fees, potentially leading to a large count of similarly sized UTXOs in the mid range. Just picking once with SRD would be expected to give a more even selection of the UTXO pool: if you have a lot of small UTXOs, you’ll get more of those, if you only have few and large UTXOs, you’ll get a solution with one or few. I.e. one could do that, but it would make the behavior change more extremely respective to the feerate, and I’m not sure whether more extreme is better.

achow101 commented at 6:40 pm on September 2, 2021:

utxo_pool is a more descriptive name.

achow101 commented at 7:27 pm on September 2, 2021:

Done

achow101 commented at 7:27 pm on September 2, 2021:

Done

in src/wallet/coinselection.cpp:178 in fac99dcaf3 outdated

173+    out_set.clear();
174+    value_ret = 0;
175+
176+    CAmount selected_eff_value = 0;
177+    Shuffle(utxo_pool.begin(), utxo_pool.end(), FastRandomContext());
178+    for (const auto& group : utxo_pool) {

glozow commented at 10:35 pm on April 29, 2021:

I know you only pass in positive groups, but I wonder if it could be a good sanity check to add an Assume(group.effective_value > 0) here?

achow101 commented at 7:27 pm on September 2, 2021:

Done

glozow commented at 10:37 pm on April 29, 2021: member

Concept ACK

In/after the commit Add SelectCoinsSRD function, it would be nice to have some unit tests for correctness in coinselector_tests.cpp - gives you the right amount, doesn’t always spit out the same result, etc.

in src/wallet/coinselection.cpp:177 in fac99dcaf3 outdated

172+{
173+    out_set.clear();
174+    value_ret = 0;
175+
176+    CAmount selected_eff_value = 0;
177+    Shuffle(utxo_pool.begin(), utxo_pool.end(), FastRandomContext());

jnewbery commented at 4:37 pm on May 3, 2021:

This calls std::swap() up to n-1 times on utxo pool, which seems unnecessary. How about creating a vector of ints from 0 to n-1, shuffling those, and then using that to index into utxo_pool. That’d also allow utxo_pool to be passed in as a const reference.

achow101 commented at 7:27 pm on September 2, 2021:

Done

achow101 force-pushed on May 17, 2021

achow101 force-pushed on May 19, 2021

achow101 marked this as a draft on May 20, 2021

achow101 commented at 8:37 pm on May 20, 2021: member

Converting this to a draft as I will be introducing some refactors and other changes that this will be based on.

achow101 force-pushed on May 21, 2021

achow101 commented at 0:31 am on May 21, 2021: member

I’ve rebased this onto #22009 because it uses the waste metric to decide which solution to use which I think is a much better and more consistent way than what was implemented here previously.

achow101 force-pushed on May 25, 2021

achow101 force-pushed on May 30, 2021

achow101 force-pushed on Jun 9, 2021

achow101 force-pushed on Aug 27, 2021

achow101 force-pushed on Sep 1, 2021

achow101 marked this as ready for review on Sep 1, 2021

laanwj added this to the "Blockers" column in a project

achow101 force-pushed on Sep 2, 2021

in src/wallet/coinselection.cpp:187 in f72c5b7ab5 outdated

182+
183+    CAmount selected_eff_value = 0;
184+    for (const size_t i : indexes) {
185+        const OutputGroup& group = utxo_pool.at(i);
186+        Assume(group.GetSelectionAmount() == 0);
187+        selected_eff_value += group.GetSelectionAmount();

naumenkogs commented at 1:09 pm on September 3, 2021:

sorry, I can’t wrap my head around it. If it’s assumed to be 0 (prev line), what’s the point of adding it and checking it below?

achow101 commented at 3:52 pm on September 3, 2021:

Oops, it’s supposed to be >. Fixed.

achow101 force-pushed on Sep 3, 2021

Xekyo commented at 5:10 pm on September 3, 2021: member

I’ve rebased this onto #22009 because it uses the waste metric to decide which solution to use which I think is a much better and more consistent way than what was implemented here previously.

In the opening comment of the PR, you mention that BnB is always preferred and if there is no BnB solution, the better of Knapsack or SRD is picked.

Shouldn’t all three selection results simply be compared on basis of the waste metric rather than always preferring the BnB solution when one is found? If there is a 5-input BnB solution, and a single input SRD solution at 130 sat/vB, I think there would be an argument to be made to prefer the latter. If that’s already the case, please update the OP.

achow101 commented at 5:46 pm on September 3, 2021: member

Updated the OP

in src/wallet/coinselection.h:188 in 1ff54f8634 outdated

184@@ -183,6 +185,15 @@ struct OutputGroup
185 
186 bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret);
187 
188+/** Select coisn by Single Random Draw. OutputGroups are selected randomly from the eligible

Xekyo commented at 6:06 pm on September 3, 2021:

0/** Select coins by Single Random Draw. OutputGroups are selected randomly from the eligible

achow101 commented at 6:37 pm on September 3, 2021:

Done

in src/wallet/coinselection.cpp:181 in 1ff54f8634 outdated

176+    CAmount value_ret = 0;
177+
178+    std::vector<size_t> indexes;
179+    indexes.resize(utxo_pool.size());
180+    std::iota(indexes.begin(), indexes.end(), 0);
181+    Shuffle(indexes.begin(), indexes.end(), FastRandomContext());

Xekyo commented at 6:07 pm on September 3, 2021:

Wouldn’t it be easier to shuffle the utxo_pool directly? Or is this the same object that is used for the other selection algorithms?

achow101 commented at 6:35 pm on September 3, 2021:

This change was suggested in #17526 (review)

in src/wallet/coinselection.cpp:191 in 1ff54f8634 outdated

186+        Assume(group.GetSelectionAmount() > 0);
187+        selected_eff_value += group.GetSelectionAmount();
188+        value_ret += group.m_value;
189+        util::insert(out_set, group.m_outputs);
190+        if (selected_eff_value >= target_value) {
191+            return std::make_pair(out_set, value_ret);

Xekyo commented at 6:14 pm on September 3, 2021:

I saw that a selection result object is being introduced in #22019. Are you planning for 22019 to succeed or precede this PR?

achow101 commented at 6:36 pm on September 3, 2021:

It doesn’t particularly matter. Currently I would like for this PR to precede 22019

Xekyo commented at 4:20 pm on September 6, 2021:

Okay, thanks

in src/wallet/spend.cpp:391 in d13d357214 outdated

381@@ -382,6 +382,15 @@ bool CWallet::AttemptSelection(const CAmount& nTargetValue, const CoinEligibilit
382         results.emplace_back(std::make_tuple(waste, std::move(knapsack_coins), knapsack_value));
383     }
384 
385+    // We include the minimum final change for SRD as we do want to avoid making really small change.
386+    // KnapsackSolver does not need this because it includes MIN_CHANGE internally.

Xekyo commented at 6:17 pm on September 3, 2021:

I would prefer if all three selection methods would receive the actual selection_target and they would internally add MIN_FINAL_CHANGE where applicable. Whether or not an input parameter needs to be amended by a global constant makes more sense as an implementation detail of the called function than each callsite needing to be aware of it, and it would allow the function calls to the selection methods to be more alike.

I.e. I think adding the MIN_FINAL_CHANGE should happen inside of SelectCoinsSRD(...)

achow101 commented at 6:37 pm on September 3, 2021:

Currently that is difficult to do with the way that we do the waste calculation. I think this can be done in the future, especially post #22019

achow101 force-pushed on Sep 3, 2021

instagibbs commented at 10:50 pm on September 3, 2021: member

seems like “fallback” is now a misnomer?

Any simulations/results/intuitions on how often each of the algorithms are likely to be picked?

in src/wallet/spend.cpp:392 in 397eccc530 outdated

381@@ -382,6 +382,15 @@ bool CWallet::AttemptSelection(const CAmount& nTargetValue, const CoinEligibilit
382         results.emplace_back(std::make_tuple(waste, std::move(knapsack_coins), knapsack_value));
383     }
384 
385+    // We include the minimum final change for SRD as we do want to avoid making really small change.
386+    // KnapsackSolver does not need this because it includes MIN_CHANGE internally.
387+    const CAmount srd_target = nTargetValue + coin_selection_params.m_change_fee + MIN_FINAL_CHANGE;

instagibbs commented at 11:09 pm on September 3, 2021:

any simulations/intuitions on what these change outputs look like vs knapsack values, aside from the difference in constant?

Why was this constant MIN_FINAL_CHANGE defined but never used before? How was it picked?

achow101 commented at 0:16 am on September 4, 2021:

It looks like we lost it during the effective value change. MIN_FINAL_CHANGE used to be the minimum allowed change output with the looping behavior. Perhaps this should target MIN_CHANGE and drop MIN_FINAL_CHANGE?

instagibbs commented at 11:52 pm on September 3, 2021: member

concept ACK, I really like the waste heuristic as a picker if nothing else to dislodge bikeshedding about coin selection hierarchies. I’d like to see how much this changes the frequency of change-less solutions in simulations since BnB isn’t preferred anymore, since I believe the argument is change-less solutions are simply only preferred after this in an economic sense, not privacy/ending the chaining of change way.

achow101 renamed this:
~~Use Single Random Draw In addition to knapsack as coin selection fallback~~
Add Single Random Draw as an additional coin selection algorithm
on Sep 4, 2021

achow101 commented at 0:15 am on September 4, 2021: member

seems like “fallback” is now a misnomer?

Updated the title.

Any simulations/results/intuitions on how often each of the algorithms are likely to be picked?

Not currently. Perhaps @Xekyo has something?

Xekyo commented at 4:18 pm on September 6, 2021: member

Any simulations/results/intuitions on how often each of the algorithms are likely to be picked?

Not currently. Perhaps @Xekyo has something?

That depends heavily on the amount and value diversity of the UTXOs that are available. I’ve seen an exchange wallet do 93% BnB transactions across a timeframe of four weeks just after enabling BnB while they were chewing through a large UTXO pool. The same wallet later settled around 55-65%, IIRC. I’d guess most enterprises with a send-and-receive hot wallet would probably fall into the range of 30-60%, send-only enterprise wallets probably more like 5-15%. On the higher end of that range if they’re batching payments since BnB solutions are easier to find for larger amounts.

On an end-user wallet I would expect 0-15% BnB solutions, especially on the lower end if it often sends at extremely low feerates since that shrinks the exact match window (as the cost of change is less) and tends to consolidate the available UTXO pool further.

in src/wallet/coinselection.h:191 in 6206f3c378 outdated

184@@ -183,6 +185,15 @@ struct OutputGroup
185 
186 bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret);
187 
188+/** Select coins by Single Random Draw. OutputGroups are selected randomly from the eligible
189+ * outputs until the target is satisfied
190+ *
191+ * @param[in]  utxo_pool    The OutputGroups eligible for selection

glozow commented at 10:29 am on September 9, 2021:

In 6206f3c378

It might be helpful to document that all groups should have positive effective values here

achow101 commented at 5:33 pm on September 23, 2021:

Done

in test/functional/rpc_fundrawtransaction.py:50 in 397eccc530 outdated

46@@ -47,7 +47,40 @@ def setup_network(self):
47         self.connect_nodes(0, 2)
48         self.connect_nodes(0, 3)
49 
50+    def lock_outputs_type(self, wallet, outputtype):

glozow commented at 10:58 am on September 9, 2021:

in 3c00f2d72d8db7109fa6d2fae10b65c485d6ae2c

Feel free to ignore, but this naming is a bit confusing since it’s locking everything but this type?

0    def lock_outputs_except_type(self, wallet, outputtype):

achow101 commented at 5:25 pm on September 23, 2021:

No, it’s (supposed to be) locking everything of the given type.

glozow commented at 9:20 am on September 24, 2021:

woops :scream:

in test/functional/rpc_fundrawtransaction.py:1009 in 4b0e091ccc outdated

1011 
1012         # But we can opt-in to use them for funding.
1013         fundedtx = wallet.fundrawtransaction(rawtx, {"include_unsafe": True})
1014         tx_dec = wallet.decoderawtransaction(fundedtx['hex'])
1015-        assert any([txin['txid'] == txid1 and txin['vout'] == vout1 for txin in tx_dec['vin']])
1016+        assert all(any(txin["txid"] == inp[0] and txin["vout"] == inp[1] for inp in inputs) for txin in tx_dec["vin"])

glozow commented at 11:12 am on September 9, 2021:

in 4b0e091cccb6844f1fc4ab76c911f5293d842800

Review note, I had a hard time parsing this, but it’s testing “all of the inputs of fundedtx come from inputs” and is the same thing as

0        assert all((txin["txid"], txin["vout"]) in inputs for txin in tx_dec["vin"])

achow101 commented at 5:33 pm on September 23, 2021:

Done

in test/functional/rpc_fundrawtransaction.py:1015 in 397eccc530 outdated

1019+        assert wallet.testmempoolaccept([signedtx['hex']])[0]["allowed"]
1020 
1021         # And we can also use them once they're confirmed.
1022         self.nodes[0].generate(1)
1023-        rawtx = wallet.createrawtransaction([], [{self.nodes[2].getnewaddress(): 3}])
1024         fundedtx = wallet.fundrawtransaction(rawtx, {"include_unsafe": True})

glozow commented at 11:27 am on September 9, 2021:

Not related to this PR, but this call shouldn’t have include_unsafe: True, right? The coins we’re testing are confirmed and no longer unsafe.

achow101 commented at 5:26 pm on September 23, 2021:

Yes.

achow101 commented at 5:33 pm on September 23, 2021:

I’ve fixed this issue while making changes in the vicinity.

DrahtBot added the label Needs rebase on Sep 9, 2021

tests: rpc_fundrawtx lock to UTXO types

For some of the tests within rpc_fundrawtx, there is the expectation
that two independent calls to coin selection RPCs will use the same type
of UTXO. This is not necessarily guaranteed, so to make sure it is, use
lockunspent prior to those tests.

df765a484d

tests: rpc_fundrawtx use specific inputs for unavailable change test

For the test that checks that there is no error when change is
unavailable but change is also not needed, use specific UTXOs so that
SRD does not cause this to fail when it chooses random inputs.

a165bfbe44

achow101 force-pushed on Sep 9, 2021

Xekyo commented at 7:50 pm on September 9, 2021: member

since I believe the argument is change-less solutions are simply only preferred after this in an economic sense, not privacy/ending the chaining of change way.

Given that the change output has a big negative impact on the waste score, the BnB solution should always be preferred, if it has the same count of inputs (given the same type). Due to usually needing to combine multiple inputs in order to arrive at a specific amount and the deterministic search path going from highest effective value to lowest, BnB solutions tend to have a small count of 2 or more inputs.

Especially in a cluttered wallet, SRD or Knapsack often find a larger solution that may be preferred at low feerates even when it produces a change output. At higher feerates, especially SRD can find the occasional lucky single input solutions that would might have a lower waste score. This may result in slightly fewer BnB solutions than before, but only in cases where the BnB solution was less cost effective.

Given the high estimated cost of change outputs, I’d say that we already have a decent handicap on solutions producing change. It would be possible to further dissuade change, but I’d consider it an open question how to pick the “correct” handicap.

DrahtBot removed the label Needs rebase on Sep 9, 2021

achow101 commented at 6:33 pm on September 13, 2021: member

I’ve ran simulations (using the same data) on a recent commit of master as well as on this PR. I’ve uploaded the results to a gist for master and for this PR.

The main result from this particular simulation is that with SRD, less inputs are being consumed overall (mean # of utxos is higher), but fees are slightly lower. SRD ended up being used ~1/3 of the time, BnB ~1/5, and Knapsack the rest.

Xekyo commented at 4:33 pm on September 15, 2021: member

I’ve ran simulations (using the same data) on a recent commit of master as well as on this PR. I’ve uploaded the results to a gist for master and for this PR.

The main result from this particular simulation is that with SRD, less inputs are being consumed overall (mean # of utxos is higher), but fees are slightly lower. SRD ended up being used ~1/3 of the time, BnB ~1/5, and Knapsack the rest.

Let me try to cast the results slightly differently: the variant with SRD reduces fees by 6% and while that variant spends 296 fewer inputs those seem to be largely accounted for by it creating 255 fewer change outputs in the first place. So yes, the mean UTXO pool is a bit larger, but in effect it also creates 4.4% fewer change outputs in the first place. Not creating so many UTXOs in the first place seems great to me!

achow101 commented at 10:20 pm on September 15, 2021: member

I redid the simulations with some fixes to how data is gathered and gathered a lot more data. The original simulation was accidentally incorrectly counting usage due to the double selection that occurs for the optimistic avoidpartialspends. I am now also measuing how many uneconomical UTXOs are being spent, and how many changeless txs of each algorithm produces. The aforementioned gist has been updated with the new measurements.

With the new measuring, we see that SRD produces a lot more BnB solutions and ends up spending almost no uneconomical outputs (which would explain the significant increase in UTXOs in the wallet).

glozow commented at 1:23 pm on September 23, 2021: member

code review ACK 981b9d13bdb1743710ea3d0c67ec13ab40619256

I wanted to see if there were any other tests that could be broken due to relying on deterministic coin selection behavior, so I edited AttemptSelection to always return the SRD solution; all the functional tests passed.

tests: rpc_fundrawtx better test for UTXO inclusion with include_unsafe

Don't assume that specific inputs are going to be used when they aren't
specified explicitly.

Also fixes a bug in the include_unsafe test where after the inputs
confirm, include_unsafe should be set to False rather than True.

59ba7d2861

tests: wallet_txn explicilty specify inputs

Instead of relying on coin selection to deterministically choose
the correct inputs to use, just specify them explicitly and use
the raw transaction RPCs.

b77885f13e

tests: wallet_basic lock needed unspents

To avoid accidentally spending UTXOs that are needed later in the test,
lock those UTXOs after they're creation.

2ad3b5d2ad

Add SelectCoinsSRD function 8bf789b4b4

Use SelectCoinsSRD if it has less waste

Try to find a solution with SelectCoinsSRD. If we do have one, add it to
the list of solutions from which we choose the one with the least waste
as the solution to use.

3633b667ff

achow101 force-pushed on Sep 23, 2021

glozow commented at 9:29 am on September 24, 2021: member

reACK 3633b66 via git range-diff 981b9d1...3633b66, thanks for taking the suggestions

in src/wallet/coinselection.cpp:178 in 8bf789b4b4 outdated

169@@ -168,6 +170,30 @@ bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selectio
170     return true;
171 }
172 
173+std::optional<std::pair<std::set<CInputCoin>, CAmount>> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value)
174+{
175+    std::set<CInputCoin> out_set;
176+    CAmount value_ret = 0;
177+
178+    std::vector<size_t> indexes;

meshcollider commented at 2:50 am on September 26, 2021:

nit: indices > indexes :)

meshcollider commented at 2:54 am on September 26, 2021: contributor

Code review ACK 8bf789b4b4b26082aea1d91c4d7aa8b01aedfdcf

I like that this coin selection algorithm is only 20 lines 😄

fanquake requested review from instagibbs on Sep 27, 2021

laanwj commented at 4:22 pm on September 27, 2021: member

Concept and code review ACK 3633b667ffca5a715d9fb27e977515c1e24f600a

meshcollider merged this on Sep 28, 2021

meshcollider closed this on Sep 28, 2021

fanquake removed this from the "Blockers" column in a project

MarcoFalke commented at 2:15 pm on September 28, 2021: member

Does this cause the intermittent wallet_basic issues?

0 test  2021-09-28T12:06:48.167000Z TestFramework (ERROR): Assertion failed 
1                                   Traceback (most recent call last):
2                                     File "/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/test_framework/test_framework.py", line 131, in main
3                                       self.run_test()
4                                     File "/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/wallet_basic.py", line 500, in run_test
5                                       assert_fee_amount(fee, tx_size, Decimal(fee_rate_btc_kvb))
6                                     File "/tmp/cirrus-ci-build/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/test/functional/test_framework/util.py", line 41, in assert_fee_amount
7                                       raise AssertionError("Fee of %s BTC too low! (Should be %s BTC)" % (str(fee), str(target_fee)))
8                                   AssertionError: Fee of 0.00000255 BTC too low! (Should be 0.00000256 BTC)

https://cirrus-ci.com/task/6110688373374976?logs=ci#L3915

achow101 commented at 4:10 pm on September 28, 2021: member

Does this cause the intermittent wallet_basic issues?

Potentially. The main thing is that this change makes coin selection non-deterministic which means that tests which rely on assuming certain UTXOs are being selected are no longer correct. I thought I got all of the tests that did that, but it is possible that a few were missed.

S3RK commented at 7:43 am on September 30, 2021: member

Post merge ACK 3633b66

Reviewed code and independently reproduced simulation results. Confirmed that adding SRD increases amount of changeless solutions.

MarcoFalke commented at 8:36 am on March 22, 2022: member

I think this picked up #13307#event-6281610244, so I removed the “up for grabs” label there.

DrahtBot locked this on Mar 22, 2023

Add Single Random Draw as an additional coin selection algorithm #17526

Conflicts