[wallet] Use destination groups instead of coins in coin select

kallewoof commented at 7:16 am on January 24, 2018: member

This PR adds an optional (off by default) -avoidpartialspends flag, which changes coin select to use output groups rather than outputs, where each output group corresponds to all outputs with the same destination.

It is a privacy improvement, as each time you spend some output, any other output that is publicly associated with the destination (address) will also be spent at the same time, at the cost of fee increase for cases where coin select without group restriction would find a more optimal set of coins (see example below).

For regular use without address reuse, this PR should have no effect on the user experience whatsoever; it only affects users who, for some reason, have multiple outputs with the same destination (i.e. address reuse).

Nodes with this turned off will still try to avoid partial spending, if the fee of the resulting transaction is not greater than the fee of the original transaction.

Example: a node has four outputs linked to two addresses A and B:

1.0 btc to A
0.5 btc to A
1.0 btc to B
0.5 btc to B

The node sends 0.2 btc to C. Without -avoidpartialspends, the following coin selection will occur:

0.5 btc to A or B is picked
0.2 btc is output to C
0.3 - fee is output to (unique change address)

With -avoidpartialspends, the following will instead happen:

Both of (0.5, 1.0) btc to A or B is picked (one or the other pair)
0.2 btc is output to C
1.3 - fee is output to (unique change address)

As noted, the pro here is that, assuming nobody sends to the address after you spend from it, you will only ever use one address once. The con is that the transaction becomes slightly larger in this case, because it is overpicking outputs to adhere to the no partial spending rule.

This complements #10386, in particular it addresses @luke-jr and @gmaxwell’s concerns in #10386 (comment) and #10386 (comment).

Together with -avoidreuse, this fully addresses the concerns in #10065 I believe.

fanquake added the label Wallet on Jan 24, 2018

luke-jr commented at 7:52 am on January 24, 2018: member

It doesn’t avoid reuse (you still need to sign for each input), and has security issues in the event of QC (but that’s already a hypothetical big issue for us anyway), but seems useful anyway.

Is this affected by the current coin control grouping defect, where it includes change in the same group as unrelated outputs? That would be a serious privacy risk, I think, since it would basically tell the world which output was change.

kallewoof commented at 8:07 am on January 24, 2018: member

@luke-jr:

It doesn’t avoid reuse (you still need to sign for each input), and has security issues in the event of QC (but that’s already a hypothetical big issue for us anyway), but seems useful anyway.

Together with -avoidreuse in #10386 it avoids reuse, I think. Are there any cases I’m missing?

Is this affected by the current coin control grouping defect, where it includes change in the same group as unrelated outputs? That would be a serious privacy risk, I think, since it would basically tell the world which output was change.

I’m not sure what this defect is. Is it described somewhere?

kallewoof force-pushed on Jan 24, 2018

ziggamon commented at 10:49 am on January 24, 2018: none

Does this also keep track of the change outputs in case more coins arrive later to A?

Imagine your example, where the coins from A go to C, with a change output to what we now call D.

If more coins arrive at A later, will they be spent together with D?

kallewoof commented at 12:18 pm on January 24, 2018: member

@ziggamon Change outputs will go to a different destination so they will be considered separate from their inputs. In other words, D in your case will not be considered related to A in this case, and will not be associated with any coins arriving at A afterwards.

kallewoof force-pushed on Jan 24, 2018

kallewoof force-pushed on Jan 25, 2018

in src/wallet/wallet.cpp:3045 in 58e4bb1d39 outdated

3047@@ -3063,6 +3048,30 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
3048     return true;
3049 }
3050 
3051+bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletTx& wtxNew, CReserveKey& reservekey, CAmount& nFeeRet,

NicolasDorier commented at 1:42 pm on January 30, 2018:

I think this is avoidable complexity, because avoidpartial will be always higher fees. I think it is OK, you pay fee for privacy, while giving incentive to privacy over fee by default.

kallewoof commented at 1:47 am on January 31, 2018:

Actually avoidpartial gives the same fee a lot of the times, from what I’ve seen so far. It depends on your utxo set, of course.

NicolasDorier commented at 1:47 pm on January 30, 2018: contributor

Some notes I am leaving here but to think about:

Making it default is the right way, but we should keep in mind that people relying on address reuse will pay way higher fee, so they need to be notified appropriately. Virtually all japanese exchanges are using address reuse (1 address per customer), this change would impact them a lot. I am unsure if they depend on Bitcoin Core Wallet though.
I am unsure if Bitcoin Core filter uneconomical outputs (filtering outputs which are more costly than their value to spend), but if bitcoin core implements this, we need to make sure this rule is always enforced at the Output level and not at the OutputGroup level. (Need to be enforced before you create the group)

in src/wallet/wallet.cpp:2561 in 58e4bb1d39 outdated

2555@@ -2575,17 +2556,21 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
2556             ++it;
2557     }
2558 
2559+    // form groups from remaining coins; note that preset coins will not
2560+    // automatically have their associated (same address) coins included
2561+    std::vector<OutputGroup> groups = group_outputs(vCoins, !(coinControl && coinControl->m_avoid_partial_spends > -1 ? coinControl->m_avoid_partial_spends : gArgs.GetBoolArg("-avoidpartialspends", DEFAULT_AVOIDPARTIALSPENDS)));

NicolasDorier commented at 1:53 pm on January 30, 2018:

I think coinControl->m_avoid_partial_spends should be a boolean, and coinControl should set its value based on the arg avoidpartialspends just after being created. (At worse, just before this call for now)

This will make the code easier to reason about.

kallewoof commented at 1:49 am on January 31, 2018:

Unfortunately that means either adding a coincontrol.cpp file and moving the constructor there, or adding a dependency on the gArg thing in coincontrol.h, which seems a bit overkill just for this. I’m very open to suggestions though; the short thing is an undesired hack.

in src/wallet/coincontrol.h:34 in 58e4bb1d39 outdated

29@@ -30,6 +30,8 @@ class CCoinControl
30     boost::optional<CFeeRate> m_feerate;
31     //! Override the default confirmation target if set
32     boost::optional<unsigned int> m_confirm_target;
33+    //! Avoid partial use of funds sent to a given address: -1 means default
34+    short m_avoid_partial_spends;

NicolasDorier commented at 1:56 pm on January 30, 2018:

what about std::optional<bool> ?

MarcoFalke commented at 2:19 pm on January 30, 2018:

(since C++17) 😛

NicolasDorier commented at 2:31 pm on January 30, 2018:

Ah I forgot we were using boost for that… I would still prefer boost than a short though.

kallewoof commented at 7:34 am on February 23, 2018:

Changed to using a boost::optional.

kallewoof commented at 1:52 am on January 31, 2018: member

@NicolasDorier

Making it default is the right way, but we should keep in mind that people relying on address reuse will pay way higher fee, so they need to be notified appropriately.

I think keeping it off by default for now is reasonable, until we get enough of an idea of the general consensus among people. I suspect, though, that most people won’t care, as long as it doesn’t give overly huge fee increases.

Virtually all japanese exchanges are using address reuse (1 address per customer), this change would impact them a lot. I am unsure if they depend on Bitcoin Core Wallet though.

Also some people have a “permanent” address that they receive payments to over a long period of time (e.g. charities). They also care little about privacy, usually, as their address is publicly tied to them anyway.

I am unsure if Bitcoin Core filter uneconomical outputs (filtering outputs which are more costly than their value to spend), but if bitcoin core implements this, we need to make sure this rule is always enforced at the Output level and not at the OutputGroup level. (Need to be enforced before you create the group)

Good point. I think the dust limit check can be added to the grouping method fairly easily.

in src/wallet/wallet.cpp:2413 in 58e4bb1d39 outdated

2420@@ -2421,103 +2421,84 @@ static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const C
2421     }
2422 }
2423 
2424-bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const int nConfMine, const int nConfTheirs, const uint64_t nMaxAncestors, std::vector<COutput> vCoins,

NicolasDorier commented at 3:26 pm on January 31, 2018:

I am unsure yet, but I think you can make the diff way smaller by keeping the old signature of this method and building the OutputGroup at the scope (local variable) of this function only.

kallewoof commented at 4:42 am on February 1, 2018:

This method doesn’t know whether you want single or grouped as it doesn’t have coincontrol. Would have to add a bool for that at least. Not sure it’ll become smaller though. It’ll just move code around.

NicolasDorier commented at 8:24 am on February 1, 2018:

So the way I did it with NBitcoin is to keep the concept of group internal to only the method which does coin packing.

If grouping is deactivated, I group by random, that way there is a single code path for everything.

I think it is a way smaller code change because all consumer of SelectCoinsMinConf do not have to change (you can make the bool default to false to keep original behavior) The concept of group does not make lot’s of sense anywhere outside of this method.

kallewoof commented at 3:35 am on February 13, 2018:

I discussed with @NicolasDorier and we concluded that the current way this is done is okay (NBitcoin does it differently so it made sense there).

kallewoof force-pushed on Feb 5, 2018

in doc/man/bitcoind.1:395 in 740daf7b2c outdated

388@@ -389,6 +389,14 @@ Include IP addresses in debug output (default: 0)
389 .IP
390 Prepend debug output with timestamp (default: 1)
391 .HP
392+\fB\-avoidpartialspends\fR
393+.IP
394+Group outputs by address, selecting all or none, instead of selecting on
395+a per\-output basis. Improved privacy as an address is only used

NicolasDorier commented at 8:05 am on February 5, 2018:

would say Privacy is improved as an address...

kallewoof commented at 8:09 am on February 5, 2018:

Changed

kallewoof force-pushed on Feb 5, 2018

kallewoof force-pushed on Feb 23, 2018

kallewoof force-pushed on Feb 26, 2018

in src/init.cpp:465 in 2f4376122e outdated

461@@ -462,6 +462,8 @@ std::string HelpMessage(HelpMessageMode mode)
462         strUsage += HelpMessageOpt("-maxsigcachesize=<n>", strprintf("Limit sum of signature cache and script execution cache sizes to <n> MiB (default: %u)", DEFAULT_MAX_SIG_CACHE_SIZE));
463         strUsage += HelpMessageOpt("-maxtipage=<n>", strprintf("Maximum tip age in seconds to consider node in initial block download (default: %u)", DEFAULT_MAX_TIP_AGE));
464     }
465+    strUsage += HelpMessageOpt("-avoidpartialspends", strprintf(_("Group outputs by address, selecting all or none, instead of selecting on a per-output basis. Privacy is improved as an address is only used once (unless someone sends to it "

luke-jr commented at 2:38 am on February 27, 2018:

“by key”. Outputs don’t have addresses.

kallewoof commented at 4:54 am on February 27, 2018:

I see what you’re saying, but in this case I think ‘address’ is fine; we speak of address reuse, after all. While outputs themselves don’t have addresses, the funding to each output was done to a specific address; if that address was the same, then this PR will group them together.

Maybe Group outputs by key (address), selecting all or... would be fine, though?

luke-jr commented at 2:22 am on February 28, 2018:

Also, this should be in wallet/init

kallewoof commented at 5:52 am on February 28, 2018:

Moved

in src/wallet/wallet.cpp:50 in 2f4376122e outdated

46@@ -47,6 +47,8 @@ OutputType g_change_type = OUTPUT_TYPE_NONE;
47 const char * DEFAULT_WALLET_DAT = "wallet.dat";
48 const uint32_t BIP32_HARDENED_KEY_LIMIT = 0x80000000;
49 
50+#define COINCONTROL_AVOID_PARTIAL_SPENDS(cc) ((cc) && (cc)->m_avoid_partial_spends ? (cc)->m_avoid_partial_spends.get() : gArgs.GetBoolArg("-avoidpartialspends", DEFAULT_AVOIDPARTIALSPENDS))

luke-jr commented at 2:45 am on February 27, 2018:

Seems this would be better as a method on CCoinControl…

kallewoof commented at 4:50 am on February 27, 2018:

Coin control needs gArgs in that case, and currently there is no .cpp file so it’d have to be included in the header.

I’m actually starting to think maybe coin control could use a .cpp file…

kallewoof force-pushed on Feb 27, 2018

kallewoof commented at 6:16 am on February 27, 2018: member

I added coincontrol.cpp and moved SetNull into it, setting it to the default given in DEFAULT_AVOIDPARTIALSPENDS. This cleans up use as it is always a bool with an up-to-date value even when default is used.

in src/validation.h:57 in cf9df64071 outdated

52@@ -53,6 +53,8 @@ static const bool DEFAULT_WHITELISTFORCERELAY = true;
53 static const unsigned int DEFAULT_MIN_RELAY_TX_FEE = 1000;
54 //! -maxtxfee default
55 static const CAmount DEFAULT_TRANSACTION_MAXFEE = 0.1 * COIN;
56+//! -avoidpartialspends default
57+static const bool DEFAULT_AVOIDPARTIALSPENDS = false;

luke-jr commented at 2:24 am on February 28, 2018:

Similarly, in wallet/wallet.h

in src/wallet/wallet.cpp:2562 in cf9df64071 outdated

2564+        SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 1, 1, 0, groups, setCoinsRet, nValueRet) ||
2565+        (bSpendZeroConfChange && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 0, 1, 2, groups, setCoinsRet, nValueRet)) ||
2566+        (bSpendZeroConfChange && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 0, 1, std::min((size_t)4, nMaxChainLength/3), groups, setCoinsRet, nValueRet)) ||
2567+        (bSpendZeroConfChange && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 0, 1, nMaxChainLength/2, groups, setCoinsRet, nValueRet)) ||
2568+        (bSpendZeroConfChange && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 0, 1, nMaxChainLength, groups, setCoinsRet, nValueRet)) ||
2569+        (bSpendZeroConfChange && !fRejectLongChains && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 0, 1, std::numeric_limits<int64_t>::max(), groups, setCoinsRet, nValueRet));

luke-jr commented at 4:33 am on February 28, 2018:

Change from uint64_t max to int64_t max should be documented somewhere, probably done alone in a separate bugfix commit.

kallewoof commented at 5:52 am on February 28, 2018:

Split into its own commit, and documented change in commit message.

in src/wallet/wallet.cpp:2454 in cf9df64071 outdated

2494-        setCoinsRet.insert(coinLowestLarger.get());
2495-        nValueRet += coinLowestLarger->txout.nValue;
2496+    // we prioritize the lowest larger if
2497+    // 1. it has multiple outputs (i.e. it is the result of address reuse)
2498+    // 2. it is not substantially (>2x) larger than the target value
2499+    if (nTotalLower < nTargetValue || (lowest_larger && lowest_larger->m_outputs.size() > 1 && lowest_larger->m_value < 2 * nTargetValue)) {

luke-jr commented at 4:39 am on February 28, 2018:

This policy change should be documented in the commit message.

kallewoof commented at 5:52 am on February 28, 2018:

Split into its own commit, and documented policy change.

kallewoof force-pushed on Feb 28, 2018

laanwj commented at 8:08 pm on March 5, 2018: member

Concept ACK

in src/util.h:363 in 44dfa2f86e outdated

357@@ -357,4 +358,14 @@ std::unique_ptr<T> MakeUnique(Args&&... args)
358     return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
359 }
360 
361+//! Simplification of std insertion
362+template <typename Tdst, typename Tsrc>
363+void insert(Tdst& dst, const Tsrc&& src) {

NicolasDorier commented at 2:06 pm on March 7, 2018:

As we discussed you might not need && because you can pass temporary object to the function with const Tsrc&

in src/txmempool.cpp:1057 in be37c0c21d outdated

1054@@ -1055,11 +1055,10 @@ void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpends
1055     }
1056 }
1057

NicolasDorier commented at 2:11 pm on March 7, 2018:

nit: You don’t have to do this, but I think it would be better if this commit was self contained, as now the clients of TransactionWithinChainLimit are not compiling anymore. To verify your change is valid we need to check other commits later. This make it harder to review.

NicolasDorier commented at 2:40 pm on March 7, 2018: contributor

Code Review ACK, though it would be nice to have the remaining TODO in the test done.

I am also wondering potential performance problem for wallet with lots of UTXOs. I already heard complaints that core was getting quite slow at doing transactions when for big wallets. (though this could be worked around by asking people to turn on avoidpartialspends)

kallewoof force-pushed on Mar 7, 2018

kallewoof commented at 3:39 pm on March 7, 2018: member

I am also wondering potential performance problem for wallet with lots of UTXOs. I already heard complaints that core was getting quite slow at doing transactions when for big wallets. (though this could be worked around by asking people to turn on avoidpartialspends)

I think wallets with a ton of outputs would want to use avoidpartialspends as it would affect them minimally fee-wise, and it would improve privacy for odd-ball reuse.

kallewoof force-pushed on Mar 7, 2018

kallewoof force-pushed on Mar 15, 2018

kallewoof commented at 10:17 am on March 15, 2018: member

I rebased this on top of the new coin selection algorithm.

kallewoof force-pushed on Apr 2, 2018

kallewoof force-pushed on Apr 3, 2018

kallewoof force-pushed on Apr 4, 2018

kallewoof force-pushed on Apr 11, 2018

in src/wallet/wallet.cpp:4439 in f9d1a771b1 outdated

4386@@ -4387,7 +4387,7 @@ std::vector<COutput>::iterator OutputGroup::discard(const COutput& output) {
4387 std::vector<CInputCoin> OutputGroup::input_coins() const {
4388     std::vector<CInputCoin> coins;
4389     for (const auto& output : m_outputs) {
4390-        coins.emplace_back(output.tx, output.i);
4391+        coins.emplace_back(output.tx->tx, output.i);

achow101 commented at 4:53 pm on April 11, 2018:

Shouldn’t this change be part of 27872fa1cf4f7ca5e0c136554078448dc7f92d1d?

kallewoof commented at 0:53 am on April 12, 2018:

Yes! Thanks for noticing.

achow101 commented at 4:55 pm on April 11, 2018: member

Light utACK. I kind of scanned over the functional tests.

kallewoof force-pushed on Apr 12, 2018

kallewoof force-pushed on May 9, 2018

laanwj referenced this in commit 1834d4d9f0 on May 9, 2018

kallewoof force-pushed on May 9, 2018

kallewoof force-pushed on May 10, 2018

kallewoof commented at 2:01 am on May 10, 2018: member

Rebased.

kallewoof force-pushed on May 17, 2018

laanwj referenced this in commit 43ae5ee9e4 on Jun 11, 2018

DrahtBot added the label Needs rebase on Jun 11, 2018

kallewoof force-pushed on Jun 12, 2018

kallewoof commented at 6:27 am on June 12, 2018: member

Rebased.

DrahtBot removed the label Needs rebase on Jun 12, 2018

DrahtBot added the label Needs rebase on Jun 30, 2018

kallewoof force-pushed on Jul 2, 2018

kallewoof commented at 5:38 am on July 2, 2018: member

Rebased

kallewoof force-pushed on Jul 6, 2018

DrahtBot removed the label Needs rebase on Jul 7, 2018

in src/wallet/wallet.h:668 in af586af9f0 outdated

679+    CAmount effective_value;
680+    CAmount fee;
681+    CAmount long_term_fee;
682+
683+    OutputGroup() : OutputGroup(std::vector<COutput>(), true, 0, 999, 0, 0) {}
684+    OutputGroup(const std::vector<COutput>&& outputs, bool from_me, CAmount value, int depth, size_t ancestors, size_t descendants)

sipa commented at 11:06 pm on July 13, 2018:

Const rvalue references aren’t very useful.

in src/wallet/coinselection.cpp:6 in 0e7efafa54 outdated

2@@ -3,12 +3,13 @@
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #include <wallet/coinselection.h>
6+#include <wallet/wallet.h>

sipa commented at 11:08 pm on July 13, 2018:

Can you avoid this cyclic module dependency (between coinselection and wallet) by moving OutputGroup to coinselection.h?

kallewoof commented at 5:02 am on July 17, 2018:

OutputGroup depends heavily on COutput, which is integral to the wallet. I could move it, but it feels like COutput doesn’t really belong in coin selection.

sipa commented at 5:04 am on July 17, 2018:

Why not? See the wallet as a user of the coin selection algorithm, filling in the relevant data in its native data type.

sipa commented at 5:08 am on July 17, 2018:

Oh, I see. COutput contains a CWalletTx. Yeah, no, that doesn’t belong in coinselection.

But why does the coin selection code need access to CWalletTx’s?

kallewoof commented at 6:18 am on July 17, 2018:

It needs the tx->tx->vout[output.i].nValue and tx->IsEquivalentTo() (but can probably work around the latter).

I could replace this with a new struct without the CWalletTx reference, if I provided the values, txid, and index, I think.

kallewoof commented at 6:20 am on July 17, 2018:

Actually, I can probably use CInputCoin if I keep the value ivar. Will try that.

kallewoof commented at 10:24 am on July 17, 2018:

CInputCoin worked great after some tweakery.

in src/wallet/wallet.cpp:3026 in 0e7efafa54 outdated

3129+    if (res && !coin_control.m_avoid_partial_spends) {
3130+        CCoinControl tmp_cc = coin_control;
3131+        tmp_cc.m_avoid_partial_spends = true;
3132+        CAmount nFeeRet2;
3133+        int nChangePosInOut2 = nChangePosIn;
3134+        if (_create_tx(vecSend, tx2, reservekey, nFeeRet2, nChangePosInOut2, strFailReason, tmp_cc, sign)) {

sipa commented at 11:14 pm on July 13, 2018:

Can this branching for avoid_partial_spends on/off be done in CWallet::SelectCoins (where all different combinations of confirmation levels and depth limits are tried), instead of creating a second place of iterating through things?

kallewoof commented at 10:15 am on July 17, 2018:

I would love to, but it relies on absolute fee to determine whether to force-use the avoid partial variant, which is not available in SelectCoins.

in src/wallet/coinselection.cpp:246 in 543bc10b3e outdated

243@@ -244,7 +244,10 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
244         return true;
245     }
246 
247-    if (nTotalLower < nTargetValue) {
248+    // we prioritize the lowest larger if

sipa commented at 11:14 pm on July 13, 2018:

This feels like a completely unrelated change to the coin selection algorithm. If it’s useful, I’d like to see simulation results first, and even then it’s probably better in a separate PR.

kallewoof commented at 5:04 am on July 17, 2018:

Dropped the relevant commit. I will make a PR once I have simulation results to back the change after merge.

kallewoof commented at 10:26 am on July 17, 2018:

FWIW, because the system tries to avoid spending larger than target if it can, this actually turns out to be a significant part of the algorithm. I’ve kept it out for now, but I feel that it needs to be in there, or the code will intentionally avoid spending reuse-groups.

sipa commented at 11:16 pm on July 13, 2018: member

Overall: can you follow code style conventions for method names (CamelCase). In addition and relatedly, having methods named push_back on application-level classes is very confusing as it makes it look like they’re STL containers when they’re not even behaving like the equivalently named STL method.

DrahtBot added the label Needs rebase on Jul 14, 2018

in src/wallet/coincontrol.cpp:21 in af586af9f0 outdated

16+    setSelected.clear();
17+    m_feerate.reset();
18+    fOverrideFeeRate = false;
19+    m_confirm_target.reset();
20+    m_signal_bip125_rbf.reset();
21+    m_fee_mode = FeeEstimateMode::UNSET;

MarcoFalke commented at 11:42 am on July 14, 2018:

Generally, we initialize all non-static class members where they are declared. Ensure determinism by avoiding accidental use of uninitialized values. Also, static analyzers balk about this. Initializing the members in the declaration makes it easy to spot uninitialized ones.

https://github.com/bitcoin/bitcoin/blob/master/doc/developer-notes.md#c-data-structures

kallewoof commented at 5:20 am on July 17, 2018:

It would duplicate the initialization in the SetNull() method as well as in the variable declarations. I assume that’s okay, then?

MarcoFalke commented at 12:40 pm on July 17, 2018:

Ah, sorry. I had missed that SetNull() is used in the gui code once.

kallewoof commented at 3:42 am on July 18, 2018:

NP! I am unsure if c942091 should be dropped or if it’s a-good to have. Keeping it unless/until someone complains.

in src/wallet/wallet.h:693 in af586af9f0 outdated

688+    , m_depth(depth)
689+    , m_ancestors(ancestors)
690+    , m_descendants(descendants)
691+    , effective_value(0)
692+    , fee(0)
693+    , long_term_fee(0)

MarcoFalke commented at 11:45 am on July 14, 2018:

nit: same for all members here. Can just inline into CAmount long_term_fee{0}; above to avoid duplication.

kallewoof commented at 5:28 am on July 17, 2018:

Done

kallewoof force-pushed on Jul 17, 2018

kallewoof commented at 10:18 am on July 17, 2018: member

Rebased and addressed all nits except @sipa’s request to move the ’try avoiding’ part into SelectCoins: I cannot access fees easily, since select coins handles sets of coins, rather than transactions. It may be reasonable to switch to simply using ’number of inputs’ rather than ‘absolute fee’, in which case this can be moved to SelectCoins, but I already did the opposite change as input count was deemed to be a bit too crude.

Edit: I should note that I ended up moving CoinEligibilityFilter to coinselection.h, which I think makes perfect sense.

DrahtBot removed the label Needs rebase on Jul 17, 2018

kallewoof force-pushed on Jul 18, 2018

kallewoof commented at 2:31 am on July 18, 2018: member

(mostly @sipa) The policy change in 750db05 is actually a necessary part of the algorithm, so it was re-added. Consider sending 1.1 btc from this utxo set:

1.0 btc to A
0.3 btc to A
0.2 btc to B
1.0 btc to C

The implementation change will see three “coins”: A (1.3 btc), B (0.2), and C (1.0). It will see A as ’lowest larger’, and not use it, because sum(B:C) can cover the payment.

Ideally, we want it to pick A, unless A is really big and/or our payment is really small (I arbitrarily set this limit to 2*target).

kallewoof force-pushed on Jul 18, 2018

sipa commented at 2:47 am on July 18, 2018: member

@kallewoof I understand your argument that it may be desirable, but I don’t understand why it is necessary.

How is it different from a scenario in the existing code where there are only 3 UTXOs (with sizes 1.3 BTC, 0.2 BTC, and 1 BTC)?

kallewoof force-pushed on Jul 18, 2018

kallewoof commented at 3:40 am on July 18, 2018: member

After discussing with @sipa (and after realizing this only applies to the knapsack solver which is intended to be removed in the near future) I removed the policy change again.

kallewoof force-pushed on Jul 18, 2018

gmaxwell commented at 5:32 pm on July 18, 2018: contributor

ACK

in src/wallet/coinselection.cpp:308 in ccb73ae127 outdated

309+    m_outputs.push_back(output);
310+    m_from_me &= from_me;
311+    m_value += output.effective_value;
312+    m_depth = std::min(m_depth, depth);
313+    m_ancestors = std::max(m_ancestors, ancestors);
314+    m_descendants = std::max(m_descendants, descendants);

sdaftuar commented at 6:54 pm on July 18, 2018:

Can you explain why this is taking std::max? I think the correct calculation would involve taking the set of ancestors or descendants of the group and counting the unique entries.

kallewoof commented at 2:37 am on July 19, 2018:

The descendants value is already a complete count of all descendants starting from the top ancestor of the transaction in question. Here we only really care about who has the most.

Edit: to explain this further, the behavior should be the same as if the utxo’s were selected one at a time; in this case, their individual descendants count would determine their applicability for the current select-coins round, not their collective descendants count. Furthermore, if two coins were related, their descendants count would already include both of them, because it works from the top ancestor (name is slightly misleading IMO).

sdaftuar commented at 2:12 pm on July 19, 2018:

I believe this calculation may be fine for descendants (if I’m correctly understanding what the descendants variable represents – it could use a code comment explaining exactly what it is, I think the descendants variable is the max number of descendants of any ancestor of a given coin?), however I think it is incorrect for ancestors.

I believe the ancestor count is the actual number of ancestors a given coin has. If you just take the max across all coins in an output group, then if you have e.g. 30 2-ancestor coins in an output group, you may treat them as a 2-ancestor output group, when in fact you have 60 ancestors in any transaction that includes the group.

(For descendants, I think this works out fine, because all we’re doing by creating a new transaction is adding one more descendant to every ancestor, so considering the max value is sufficient to try to avoid hitting mempool chain limits.)

I understand that the existing logic may be imprecise and hacky around this, but I believe that combining all the coins into an output group exacerbates this issue.

Regardless of what we end up doing here though I think the code could use a comment explaining the logic, as this is non-obvious.

kallewoof commented at 2:40 pm on July 19, 2018:

I believe the ancestor count is the actual number of ancestors a given coin has. If you just take the max across all coins in an output group, then if you have e.g. 30 2-ancestor coins in an output group, you may treat them as a 2-ancestor output group, when in fact you have 60 ancestors in any transaction that includes the group.

Aha! This is a very good point. I will think about a remedy for this post-merge. For now, I added a comment explaining how it works and how it can be improved.

in src/wallet/wallet.h:645 in 8197c13132 outdated

650-    const uint64_t max_descendants;
651-
652-    CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_ancestors) {}
653-    CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_descendants) {}
654-};
655+struct CoinEligibilityFilter;

sipa commented at 7:45 pm on July 18, 2018:

No need for a forward declaration here. wallet/wallet.h already includes wallet/coinselection.h where it is defined.

in src/wallet/coincontrol.h:20 in c94209199f outdated

16@@ -17,23 +17,23 @@ class CCoinControl
17 {
18 public:
19     //! Custom change destination, if not set an address is generated
20-    CTxDestination destChange;
21+    CTxDestination destChange{CNoDestination()};

sipa commented at 7:47 pm on July 18, 2018:

If all local variables have a default initialized, you don’t need the SetNull call in the constructor anymore.

kallewoof commented at 2:41 am on July 19, 2018:

They don’t – specifically the new argument requires gArgs which are not available here.

I should probably drop “Declare-&-initialize…” commit.

kallewoof commented at 2:51 am on July 19, 2018:

Dropped that commit.

in src/wallet/coinselection.h:83 in ccb73ae127 outdated

78+    CAmount fee{0};
79+    CAmount long_term_fee{0};
80+
81+    OutputGroup() {}
82+    OutputGroup(std::vector<CInputCoin>&& outputs, bool from_me, CAmount value, int depth, size_t ancestors, size_t descendants)
83+    : m_outputs(outputs)

sipa commented at 7:50 pm on July 18, 2018:

More efficient: m_outputs(std::move(outputs)). The expression ‘outputs’ here is not an rvalue reference, so this is not automatic.

kallewoof commented at 2:46 am on July 19, 2018:

Huh.. I thought && made it an rvalue. Guess I need to re-read that explanation. Done.

in src/wallet/coinselection.h:12 in e405c94e80 outdated

 8@@ -9,6 +9,8 @@
 9 #include <primitives/transaction.h>
10 #include <random.h>
11 
12+struct OutputGroup;

sipa commented at 7:54 pm on July 18, 2018:

What is the forward declare for?

kallewoof commented at 2:46 am on July 19, 2018:

Leftover. Removed.

in src/wallet/wallet.cpp:2644 in e405c94e80 outdated

2640@@ -2635,8 +2641,8 @@ OutputType CWallet::TransactionChangeType(OutputType change_type, const std::vec
2641     return m_default_address_type;
2642 }
2643 
2644-bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CTransactionRef& tx, CReserveKey& reservekey, CAmount& nFeeRet,
2645-                                int& nChangePosInOut, std::string& strFailReason, const CCoinControl& coin_control, bool sign)
2646+bool CWallet::_create_tx(const std::vector<CRecipient>& vecSend, CTransactionRef& tx, CReserveKey& reservekey, CAmount& nFeeRet,

sipa commented at 7:58 pm on July 18, 2018:

That’s a really crazy function name. What about CreateTransactionInternal or so?

kallewoof commented at 2:46 am on July 19, 2018:

Renamed.

kallewoof force-pushed on Jul 19, 2018

kallewoof force-pushed on Jul 20, 2018

in src/wallet/wallet.cpp:3054 in 19bbab0138 outdated

3015+                                int& nChangePosInOut, std::string& strFailReason, const CCoinControl& coin_control, bool sign)
3016+{
3017+    int nChangePosIn = nChangePosInOut;
3018+    CTransactionRef tx2 = tx;
3019+    bool res = CreateTransactionInternal(vecSend, tx, reservekey, nFeeRet, nChangePosInOut, strFailReason, coin_control, sign);
3020+    // try with avoidpartialspends unless it's enabled already

sdaftuar commented at 9:00 pm on July 20, 2018:

I think I would prefer that we not do this – I’m not sure that -avoidpartialspends works very well on wallets that have substantial address reuse, in particular I think you can devolve into cases where you’d produce giant transactions that take forever to sign and would never pass policy (or consensus) limits, in extreme cases.

I’m going to comment elsewhere about places I think we can mitigate this sort of pathological behavior, but as belt and suspenders I think if the user is not using this new feature, we should not fall back to trying it anyway.

kallewoof commented at 9:40 pm on July 20, 2018:

The code only selects the avoiding tx if its fee is lower than the original. I don’t think you’d ever run into that case for someone with substantial address reuse.

sdaftuar commented at 9:45 pm on July 20, 2018:

But even running the code on a wallet with a large number of outputs with the same scriptPubKey can be very slow. Nothing stops the code from eg trying to generate a multi-megabyte transaction and then hit a huge slow down while trying to sign such a transaction, before the transaction gets rejected. (I have an RPC test that demonstrates this possibility.)

kallewoof commented at 9:55 pm on July 20, 2018:

Now that there is a cap on the utxo count per output group, I think parts of this is mitigated, but I’m not sure I’ve convinced myself this is necessary. Perhaps a 3-state flag (try, on, off) with default=try, so people can disable it…

kallewoof commented at 11:55 am on July 21, 2018:

Removing this. No harm in doing the try style later.

in src/wallet/wallet.cpp:4430 in 19bbab0138 outdated

4391@@ -4379,3 +4392,25 @@ void CWallet::LearnAllRelatedScripts(const CPubKey& key)
4392     LearnRelatedScripts(key, OutputType::P2SH_SEGWIT);
4393 }
4394 
4395+std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outputs, bool single_coin) const {

sdaftuar commented at 9:20 pm on July 20, 2018:

Perhaps we should not create groups that would be excessively large to send together? For instance if someone has a couple thousand outputs to the same address, then as a group they would become unspendable (because the resulting transaction would be too big).

It might be pretty annoying for our users if they became vulnerable to weird DoS attacks where people create lots of dust to prevent them from spending their coins…

kallewoof commented at 9:49 pm on July 20, 2018:

Good point. I’ve set a cap at 10 outputs per group. Perhaps this should be a -option…

That being said, the code (at least BnB algo; knapsack is being deprecated) already removes dust from the group before running coin select. https://github.com/kallewoof/bitcoin/blob/19bbab013860c84475cce98a55179a1167348269/src/wallet/wallet.cpp#L2415-L2422

kallewoof force-pushed on Jul 20, 2018

kallewoof force-pushed on Jul 21, 2018

kallewoof force-pushed on Jul 22, 2018

in src/util.h:360 in 84cf3f14b7 outdated

354@@ -355,4 +355,14 @@ std::string CopyrightHolders(const std::string& strPrefix);
355  */
356 int ScheduleBatchPriority(void);
357 
358+//! Simplification of std insertion
359+template <typename Tdst, typename Tsrc>
360+void insert(Tdst& dst, const Tsrc& src) {

laanwj commented at 3:59 pm on July 23, 2018:

should we call these insert? I think it’s a bit confusing for readability, as it implies the built-in std function is used in ways that the original one cannot be.

kallewoof commented at 4:32 pm on July 23, 2018:

I was considering putting them under a util:: namespace or somehing to emphasize they’re actually not std but since we are no longer using namespace std it felt unnecessary. I’m up for renaming if it still feels confusing though.

kallewoof commented at 6:07 am on July 24, 2018:

I ended up moving into util:: after all.

utils: Add insert() convenience templates 173e18a289

moveonly: CoinElegibilityFilter into coinselection.h a443d7a0ca

wallet: Add input bytes to CInputCoin

With nInputBytes, coin selection can execute without a reference to the COutput

65b3eda458

Add -avoidpartialspends and m_avoid_partial_spends bb629cb9dc

wallet: Add output grouping 87ebce25d6

wallet: Switch to using output groups instead of coins in coin selection 59d6f7b4e2

test: Add basic testing for wallet groups 0128121101

wallet: Remove deprecated OutputEligibleForSpending 43e04d13b1

clean-up: Remove no longer used ivars from CInputCoin e00b4699cc

doc: Add release notes for -avoidpartialspends 232f96f5c8

in src/wallet/coinselection.h:41 in 7927a5d38e outdated

38     CAmount effective_value;
39     CAmount fee = 0;
40     CAmount long_term_fee = 0;
41 
42+    /** Pre-computed estimated size of this output as a fully-signed input in a transaction. Can be -1 if it could not be calculated */
43+    int m_input_bytes{-1};

laanwj commented at 4:12 pm on July 23, 2018:

what makes this different from

0int m_input_bytes = -1;

(my guess is that it is the same, in which case I think that syntax is preferable because it is already used in so many places)

kallewoof commented at 4:44 pm on July 23, 2018:

It is the same. We already use this syntax in a variety of places. See e.g.

https://github.com/bitcoin/bitcoin/blob/7ebd8c6385253bfa30175169a22f93474d8ddfaf/src/wallet/wallet.h#L97-L101

https://github.com/bitcoin/bitcoin/blob/7ebd8c6385253bfa30175169a22f93474d8ddfaf/src/wallet/wallet.h#L674-L675

laanwj commented at 5:54 pm on July 23, 2018:

okay! well then my only comment is that mixing the syntaxes in the same class looks inconsistent, but I don’t care strongly

kallewoof commented at 2:32 am on July 24, 2018:

Oh, hum. I actually thought the {} syntax was preferred and didn’t fix the other stuff to avoid diff bloat.

kallewoof commented at 6:08 am on July 24, 2018:

Oh, actually, the other two lines are removed at the end as they are no longer needed.

in src/wallet/coinselection.cpp:305 in 43dcf1a71f outdated

300+    m_value += output.effective_value;
301+    m_depth = std::min(m_depth, depth);
302+    // m_ancestors is currently the max ancestor count for all coins in the group; however, this is
303+    // not ideal, as a wallet will consider e.g. thirty 2-ancestor coins as having two ancestors,
304+    // when in reality it has 60 ancestors.
305+    m_ancestors = std::max(m_ancestors, ancestors);

sdaftuar commented at 8:51 pm on July 23, 2018:

Rather than use std::max, it seems like we could just sum the ancestor values – that risks overcounting, but what’s the downside? I believe the goal of tracking this stuff is so that calls to SelectCoinsMinConf has a better chance of producing a transaction that passes the mempool chain limits, so if we err on the side of caution here I think that’s just strictly better.

kallewoof commented at 4:33 pm on July 30, 2018:

Yeah, worst case the user has to wait for the inputs to confirm before they can spend them. (Is there a case where that could be a pontential problem? Can’t think of one.)

kallewoof commented at 7:51 pm on July 30, 2018:

See #13812

in src/wallet/wallet.cpp:4441 in 43dcf1a71f outdated

4436+            CInputCoin input_coin = output.GetInputCoin();
4437+
4438+            size_t ancestors, descendants;
4439+            mempool.GetTransactionAncestry(output.tx->GetHash(), ancestors, descendants);
4440+            if (!single_coin && ExtractDestination(output.tx->tx->vout[output.i].scriptPubKey, dst)) {
4441+                if (gmap.count(dst) == 10) {

sdaftuar commented at 9:08 pm on July 23, 2018:

I think you meant if (gmap[dst].m_outputs.size() == 10)? gmap.count(dst) should always be 0 or 1.

Also – I’m not sure if there’s some negative side effect from deterministically creating these subgroups of outputs. Intuitively it seems safer to me if we randomly constructed these groups somehow to prevent someone from triggering some kind of coinselection issue by giving us coins that sort in a particular way. But maybe this concern is overblown.

kallewoof commented at 4:31 pm on July 30, 2018:

I’m not sure it’s a big risk, but I also think it’s better to be safe than sorry. I envision a replacement of push_back with insert(begin() + random(size()) (forgive pseudo-code-abbrev) in

https://github.com/bitcoin/bitcoin/blob/4d550ffab64d79a44fcaa76f6e30c28f01614d3f/src/wallet/coinselection.cpp#L298

Will make a PR unless someone beats me to it.

kallewoof commented at 4:40 pm on July 30, 2018:

Hm.. actually, that’s not sufficient due to the capping at 10. I guess shuffling the entire vector at the top in CWallet::GroupOutputs is the way to go.

kallewoof commented at 5:00 pm on July 30, 2018:

Adding shuffling in #13808. ~~I chose to put it in the GroupOutputs method since it can skip the shuffle for is_single and size() <= 10 cases.~~ Moved outside, due to constness.

promag commented at 9:00 pm on July 30, 2018:

gmap.count(dst) == 10 is always false and is not fixed in #13808.

kallewoof commented at 9:07 pm on July 30, 2018:

It’s fixed in #13805

kallewoof force-pushed on Jul 24, 2018

laanwj commented at 1:33 pm on July 24, 2018: member

utACK 232f96f5c8a3920c09db92f4dbac2ad7d10ce8cf

laanwj merged this on Jul 24, 2018

laanwj closed this on Jul 24, 2018

laanwj referenced this in commit 5f7575e263 on Jul 24, 2018

kallewoof deleted the branch on Jul 24, 2018

sdaftuar commented at 3:39 pm on July 30, 2018: member

Oops, I was mid-review and never posted these comments before merge. I address one of these in #13805.

kallewoof referenced this in commit f7ac7fb753 on Jul 30, 2018

kallewoof referenced this in commit 60df230c42 on Jul 30, 2018

kallewoof referenced this in commit bea78f2405 on Jul 30, 2018

laanwj referenced this in commit 9d86aad287 on Aug 7, 2018

kallewoof referenced this in commit c3b47e306e on Aug 9, 2018

kallewoof referenced this in commit bc9ef8720f on Aug 10, 2018

kallewoof referenced this in commit 18f690ec2f on Aug 10, 2018

ken2812221 referenced this in commit 13d51a2b61 on Aug 13, 2018

Bushstar referenced this in commit b5935289d0 on Aug 13, 2018

uhliksk referenced this in commit 8a92c8a902 on Aug 29, 2018

HashUnlimited referenced this in commit 57895e8a7f on Sep 14, 2018

joemphilips referenced this in commit b2610765ae on Nov 9, 2018

jfhk referenced this in commit 5742e50974 on Nov 14, 2018

meshcollider referenced this in commit 44d8172323 on Jun 18, 2019

sidhujag referenced this in commit 6bcaa95d9d on Jun 19, 2019

jasonbcox referenced this in commit 27b6f17553 on Jun 28, 2019

jtoomim referenced this in commit cabe89c55b on Jun 29, 2019

PastaPastaPasta referenced this in commit beb7b975d6 on Jun 17, 2020

PastaPastaPasta referenced this in commit 0425b71610 on Jun 27, 2020

PastaPastaPasta referenced this in commit a5275cb868 on Jun 28, 2020

PastaPastaPasta referenced this in commit ffb4158774 on Jun 29, 2020

PastaPastaPasta referenced this in commit 688b0736b5 on Feb 2, 2021

PastaPastaPasta referenced this in commit a8863dc3b5 on Feb 4, 2021

Munkybooty referenced this in commit 3a9c562e6e on Jun 15, 2021

Munkybooty referenced this in commit c40f154def on Jun 15, 2021

Munkybooty referenced this in commit 0f644d5f5f on Jun 16, 2021

Munkybooty referenced this in commit e2bf529053 on Jun 22, 2021

Munkybooty referenced this in commit 82659a4eb8 on Jun 24, 2021

Munkybooty referenced this in commit 640b1ceea2 on Jun 24, 2021

UdjinM6 referenced this in commit e1f4da907e on Jul 4, 2021

UdjinM6 referenced this in commit e076832ddb on Jul 4, 2021

UdjinM6 referenced this in commit 5e51a7299a on Jul 6, 2021

UdjinM6 referenced this in commit 000f129f75 on Jul 6, 2021

UdjinM6 referenced this in commit 389aaa07d1 on Jul 6, 2021

UdjinM6 referenced this in commit c76470c98e on Jul 6, 2021

DrahtBot locked this on Dec 16, 2021

[wallet] Use destination groups instead of coins in coin select #12257