Replace coin selection fallback strategy with Single Random Draw #13307

achow101 · 2018-05-23T03:24:07Z

When BnB selection fails to find an exact match, we fall back to the original Bitcoin Core algorithm. This PR replaces that fallback with the Single Random Draw strategy. Additionally, because SRD uses effective values, the previous fee increasing loop thing is now removed and effective value is used everywhere.

Some tests may fail spuriously because they may rely on semi-deterministic behavior from the original coin selection algorithm. I have been able to fix the ones that fail the most, but others may still have issues. Please let me know if you see any tests fail for coin selection reasons (e.g. insufficient funds, missing inputs, etc.) and I will try to fix them.

I will be working on doing simulations this week and will post the data once I finish them.

achow101 · 2018-05-23T03:24:21Z

cc @xekyo @instagibbs

Empact · 2018-05-23T10:30:52Z

src/wallet/coinselection.cpp

+
+        // We have enough coins, stop selecting
+        if (curr_value >= target_value + not_input_fees) {
+            break;


Could return true here, return false if the loop exhausts, to avoid duplicating the condition.

Empact · 2018-05-23T10:36:35Z

src/wallet/wallet.cpp

        return true;
    } else {
-        bnb_used = false;
        return SingleRandomDraw(nTargetValue, utxo_pool, setCoinsRet, nValueRet, not_input_fees);


Could collapse this to boolean fallback at this point.

Empact · 2018-05-23T10:56:19Z

src/wallet/wallet.h

@@ -849,8 +849,8 @@ class CWallet final : public CCryptoKeyStore, public CValidationInterface
     * completion the coin set and corresponding actual target value is
     * assembled
     */
-    bool SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> vCoins,
-        std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params, bool& bnb_used) const;
+    bool SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibilty_filter, std::vector<COutput> vCoins,


eligibilty_filter typo

instagibbs

"Calculate the transaction fees" <--- this commit probably needs more description, not sure what it's doing.

instagibbs · 2018-06-04T22:20:24Z

src/wallet/coinselection.cpp

+/*
+ * Randomly selects coins until the target value is exceeded. Uses effective values
+ */
+bool SingleRandomDraw(const CAmount& target_value, std::vector<CInputCoin>& utxo_pool, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees)


non_input_fees? It's not "not fees", rather "non-input". Easier for me to read.

instagibbs · 2018-06-04T22:29:43Z

src/wallet/wallet.cpp

@@ -2509,9 +2509,10 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil
    // Calculate the fees for things that aren't inputs
    CAmount not_input_fees = coin_selection_params.effective_fee.GetFee(coin_selection_params.tx_noinputs_size);

-    if (coin_selection_params.use_bnb) {
+    // Start with BnB. If that fails, use SRD
+    if (SelectCoinsBnB(utxo_pool, nTargetValue, cost_of_change, setCoinsRet, nValueRet, not_input_fees)) {


I think this new logic means that non-BnB will be tried more often? Instead of trying all variants of BnB(6 confirms, 1 confirm, small chain, etc), we seem to be trying 6 confirms for BnB, then 6 confirms for non-BnB

Hmm, yes, that appears to be what is happening. I guess this depends on whether we want to select an exact match for coins with less confirmatoins, or whether we want confirmations over exact match.

This is a good point. Perhaps a solution is to add a use_bnb argument to SelectCoinsMinConf (but not as part CoinSelectionParams), and then have a sequence of attempts with and without use_bnb in SelectCoins?

I prefer the behavior in master due to privacy reasons of change-less transactions.

I have implemented this change.

instagibbs · 2018-06-04T22:46:05Z

src/wallet/wallet.cpp

@@ -2916,6 +2887,40 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CTransac
            for (const auto& coin : setCoins)
                txNew.vin.push_back(CTxIn(coin.outpoint,CScript(),
                                          nSequence));
+
+            // Fill vout
+            bool fFirst = true;


maybe rename to first_output

instagibbs · 2018-06-04T22:58:58Z

src/wallet/wallet.cpp

@@ -2498,7 +2499,7 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil
            continue;

        CInputCoin coin(output.tx->tx, output.i);
-        coin.effective_value = coin.txout.nValue - (output.nInputBytes < 0 ? 0 : coin_selection_params.effective_fee.GetFee(output.nInputBytes));
+        coin.effective_value = coin.txout.nValue - (output.nInputBytes < 0 || !use_effective ? 0 : coin_selection_params.effective_fee.GetFee(output.nInputBytes));


parenthesis please

instagibbs · 2018-06-04T23:02:29Z

Some thoughts.

achow101 · 2018-06-05T05:33:02Z

"Calculate the transaction fees" <--- this commit probably needs more description, not sure what it's doing.

Reworded, hopefully it's better.

Empact · 2018-06-08T06:19:11Z

nit: Somewhat better to revert the merge commit 9552dfb rather than the 2 pr commits, to be explicit that the whole PR was reverted (and which one).

Empact · 2018-06-08T06:19:39Z

src/wallet/coinselection.cpp

-bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet)
+/*
+ * Randomly selects coins until the target value is exceeded. Uses effective values
+ */


nit: Better to document in the header, and use doxygen comment /**

Empact · 2018-06-08T06:20:52Z

src/wallet/test/coinselector_tests.cpp

-        CoinSelectionParams coin_selection_params_knapsack(false, 34, 148, CFeeRate(0), 0);
-        CoinSelectionParams coin_selection_params_bnb(true, 34, 148, CFeeRate(0), 0);
+
+        CoinSelectionParams coin_selection_params_bnb(34, 148, CFeeRate(0), 0);


_bnb probably no longer relevant

Removed here and elsewhere

Empact · 2018-06-08T06:21:30Z

src/wallet/test/coinselector_tests.cpp

@@ -216,316 +214,13 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
    }

    // Make sure that effective value is working in SelectCoinsMinConf when BnB is used
-    CoinSelectionParams coin_selection_params_bnb(true, 0, 0, CFeeRate(3000), 0);
+    CoinSelectionParams coin_selection_params_bnb(0, 0, CFeeRate(3000), 0);


Empact · 2018-06-08T06:29:59Z

src/wallet/wallet.cpp

@@ -2529,14 +2529,18 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
            if (!out.fSpendable)
                 continue;
            nValueRet += out.tx->tx->vout[out.i].nValue;
-            setCoinsRet.insert(CInputCoin(out.tx->tx, out.i));
+            CInputCoin coin(out.tx->tx, out.i);
+            coin.effective_value = coin.txout.nValue - (out.nInputBytes < 0 || !use_effective ? 0 : coin_selection_params.effective_fee.GetFee(out.nInputBytes));


nit: explicit precedence would be nice here: (out.nInputBytes < 0 || !use_effective)

I thought I did this earlier. Must have gotten lost in a rebase. Fixed.

Doesn't look changed fyi.

How about now?

Empact · 2018-06-08T06:30:20Z

src/wallet/wallet.cpp

            it = vCoins.erase(it);
-        else
+        }
+        else {


nit: whitespace

Empact · 2018-06-08T06:55:08Z

src/wallet/coinselection.h

-    CAmount long_term_fee = 0;
+    mutable CAmount effective_value;
+    mutable CAmount fee = 0;
+    mutable CAmount long_term_fee = 0;


nit: Better to squash this change into the commit that calls for it

achow101 · 2018-06-08T23:18:03Z

nit: Somewhat better to revert the merge commit 9552dfb rather than the 2 pr commits, to be explicit that the whole PR was reverted (and which one).

Done

sipa · 2018-06-09T17:49:44Z

src/wallet/coinselection.cpp

+
+bool SingleRandomDraw(const CAmount& target_value, std::vector<CInputCoin>& utxo_pool, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount non_input_fees)
+{
+    random_shuffle(utxo_pool.begin(), utxo_pool.end(), GetRandInt);


Two comments:

Requesting new entropy for each element being sorted may be slow (each call to GetRandInt invokes OpenSSL for randomness) (this also applies to the code you copied, but you're going to remove that anyway).

It's overkill to permute all elements, as you're likely only going to use a few.

For the first, create a FastRandomContext and use that in std::shuffle (rather than random_shuffle):

std::shuffle(utxo_pool.begin(), utxo_pool.end(), FastRandomContext());`

For the second, you can permute on the fly; for example:

FastRandomContext ctx; for (size_t i = 0; i < utxo_pool.size; ++i) { size_t pos = i + ctx.randrange(utxo_pool.size() - i); // randomly pick one of the remaining elements std::swap(utxo_pool[i], utxo_pool[pos]); const CInputCoin& utxo = utxo_pool[i]; ... }

sipa · 2018-06-09T18:03:18Z

src/wallet/wallet.cpp

@@ -2509,9 +2509,10 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil
    // Calculate the fees for things that aren't inputs
    CAmount not_input_fees = coin_selection_params.effective_fee.GetFee(coin_selection_params.tx_noinputs_size);

-    if (coin_selection_params.use_bnb) {
+    // Start with BnB. If that fails, use SRD
+    if (SelectCoinsBnB(utxo_pool, nTargetValue, cost_of_change, setCoinsRet, nValueRet, not_input_fees)) {


This is a good point. Perhaps a solution is to add a use_bnb argument to SelectCoinsMinConf (but not as part CoinSelectionParams), and then have a sequence of attempts with and without use_bnb in SelectCoins?

sipa · 2018-06-09T18:07:17Z

src/wallet/wallet.cpp

-                                          nSequence));
+                if (nSubtractFeeFromAmount != 0) {
+                    // If we are subtracting the fee from the amount, nChange cannot be less than 0 because nFeeRet is not involved.
+                    // We need to decrase nFeeRet by the change output fee so that we do not overpay.


Typo: decrase

sipa · 2018-06-09T23:57:31Z

src/wallet/coinselection.cpp

-    nValueRet = 0;
+    FastRandomContext random_ctx;
+    CAmount curr_value = 0;
+    for (size_t i = 0; i < utxo_pool.size; ++i) {


Travis fails because of size (instead of size()).

achow101 · 2018-06-10T02:04:41Z

I'm not quite sure what is causing the travis failure.

achow101 · 2018-07-07T00:38:38Z

Fixed the test failure.

…et inputs" This reverts commit 9552dfb, reversing changes made to f686002.

SingleRandomDraw randomly chooses UTXOs until there is sufficient effective value.

Replaces the knapsack solver fallback with the SRD fallback. Also changes SelectCoinsMinConf to use exclusively effective value to work with BnB and SRD

Instead of the caller telling SelectCoinsMinConf when to use BnB or the fallback, have SelectCoinsMinConf do it itself. This removes the use_bnb field of coin_selection_params

We are now using effective value for coin selection, so there is no need for the loop or any of the fee checking things that were done within it. All fees ard handled by the effective value selection Move vout filling to after coins are selected so that the transaction fee is actually known to handle when users want to subtract the fee from the outputs.

…mount

bnb_used is no longer necessary since we account for fees when calculating how much change there is

For preset inputs, use their effective values

Fix tests that relied on non-deterministic coin selection to be able to handle the random coin selection.

achow101 · 2018-08-17T21:15:09Z

Rebased

DrahtBot · 2018-09-07T18:53:31Z

Note to reviewers: This pull request conflicts with the following ones:

refactor: Make explicit CMutableTransaction -> CTransaction conversion. #14156 ([WIP] refactor: Make explicit CMutableTransaction -> CTransaction conversion. by lucash-dev)
Drop unused GetType() from CSizeComputer #13558 (Drop unused GetType() from CSizeComputer by Empact)
wallet: Fix use of uninitialized value bnb_used in CWallet::CreateTransaction(...) #13546 (wallet: Avoid potential use of uninitialized value bnb_used in CWallet::CreateTransaction(...) by practicalswift)
[tests] Speed up knapsack_solver_test by not recreating wallet 100 times. #13419 ([tests] Speed up knapsack_solver_test by not recreating wallet 100 times. by lucash-dev)
refactor pre-selected coin code #13057 (refactor pre-selected coin code by instagibbs)
Add missing locks: validation.cpp + related #11652 (Add missing locks: validation.cpp + related by practicalswift)
wallet: Add missing cs_wallet/cs_KeyStore locks to wallet #11634 (wallet: Add missing cs_wallet/cs_KeyStore locks to wallet by practicalswift)
Refactor: separate wallet from node #10973 (Refactor: separate wallet from node by ryanofsky)
Remove CWalletTx merging logic from AddToWallet #9381 (Remove CWalletTx merging logic from AddToWallet by ryanofsky)

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 · 2018-09-11T08:38:52Z

Needs rebase

DrahtBot · 2018-12-12T19:23:21Z

There hasn't been much activity lately and the patch still needs rebase, so I am closing this for now. Please let me know when you want to continue working on this, so the pull request can be re-opened.

fanquake added the Wallet label May 23, 2018

achow101 force-pushed the srd-fallback branch from c7b64d3 to 3583093 Compare May 23, 2018 05:37

Empact reviewed May 23, 2018

View reviewed changes

achow101 force-pushed the srd-fallback branch 2 times, most recently from 80a9f2c to 9eea461 Compare May 23, 2018 17:40

instagibbs reviewed Jun 4, 2018

View reviewed changes

achow101 force-pushed the srd-fallback branch from 9eea461 to 50000b1 Compare June 5, 2018 05:31

achow101 mentioned this pull request Jun 8, 2018

[tests] Speed up knapsack_solver_test by not recreating wallet 100 times. #13419

Merged

Empact reviewed Jun 8, 2018

View reviewed changes

achow101 force-pushed the srd-fallback branch from 50000b1 to 4a574d7 Compare June 8, 2018 23:17

sipa reviewed Jun 9, 2018

View reviewed changes

achow101 force-pushed the srd-fallback branch 2 times, most recently from efda8e0 to 05dfc65 Compare June 9, 2018 23:27

sipa reviewed Jun 9, 2018

View reviewed changes

achow101 force-pushed the srd-fallback branch from 05dfc65 to abe9c30 Compare June 10, 2018 00:16

DrahtBot added the Needs rebase label Jun 11, 2018

maflcko removed the Needs rebase label Jun 11, 2018

DrahtBot removed the Needs rebase label Jul 7, 2018

DrahtBot added the Needs rebase label Jul 24, 2018

achow101 added 11 commits August 17, 2018 14:14

Revert "Merge bitcoin#12694: Actually disable BnB when there are pres…

2f4ab05

…et inputs" This reverts commit 9552dfb, reversing changes made to f686002.

Implement the SingleRandomDraw coin selection method

65b535b

SingleRandomDraw randomly chooses UTXOs until there is sufficient effective value.

Replace the coin selection fallback with SRD

ffd7156

Replaces the knapsack solver fallback with the SRD fallback. Also changes SelectCoinsMinConf to use exclusively effective value to work with BnB and SRD

Remove KnapsackSolver and related tests

02b288f

Have SelectCoinsMinConf figure out when to use BnB or SRD

33737a5

Instead of the caller telling SelectCoinsMinConf when to use BnB or the fallback, have SelectCoinsMinConf do it itself. This removes the use_bnb field of coin_selection_params

Don't use effective values when we are subtracting the fee from the a…

ae9a8e1

…mount

Remove bnb_used

8ecb634

bnb_used is no longer necessary since we account for fees when calculating how much change there is

handle preset inputs

6989b9d

For preset inputs, use their effective values

Split change output creation from fee calculation for change

e3903f3

Make tests work with non-deterministic coin selection

339d977

Fix tests that relied on non-deterministic coin selection to be able to handle the random coin selection.

achow101 force-pushed the srd-fallback branch from 6014f63 to 339d977 Compare August 17, 2018 21:14

DrahtBot removed the Needs rebase label Aug 17, 2018

This was referenced Aug 29, 2018

Minor style enhancement in documentation #14091

Closed

Refactoring: Clarify code using encrypted_batch in CWallet #14144

Closed

DrahtBot mentioned this pull request Sep 6, 2018

refactor: Make explicit CMutableTransaction -> CTransaction conversion. #14156

Closed

DrahtBot added the Needs rebase label Sep 11, 2018

achow101 mentioned this pull request Sep 14, 2018

Actually disable BnB when there are preset inputs #12694

Merged

DrahtBot added the Up for grabs label Dec 12, 2018

DrahtBot closed this Dec 12, 2018

laanwj removed the Needs rebase label Oct 24, 2019

bitcoin locked as resolved and limited conversation to collaborators Dec 16, 2021

maflcko removed the Up for grabs label Mar 22, 2022

Replace coin selection fallback strategy with Single Random Draw #13307

Replace coin selection fallback strategy with Single Random Draw #13307

Uh oh!

Conversation

achow101 commented May 23, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

achow101 commented May 23, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

instagibbs left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

instagibbs commented Jun 4, 2018

Uh oh!

achow101 commented Jun 5, 2018

Uh oh!

Empact commented Jun 8, 2018

Uh oh!

Empact Jun 8, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

achow101 commented May 23, 2018 •

edited

Loading

Empact Jun 8, 2018 •

edited

Loading

DrahtBot commented Sep 7, 2018 •

edited

Loading