Coin Selection with Murch's algorithm

achow101 commented at 6:09 pm on June 20, 2017: member

This is an implementation of the Branch and Bound coin selection algorithm written by Murch (@xekyo). I have it set so this algorithm will run first and if it fails, it will fall back to the current coin selection algorithm. The coin selection algorithms and tests have been refactored to separate files instead of having them all in wallet.cpp.

I have added some tests for the new algorithm and a test for all of coin selection in general. However, more tests may be needed, but I will need help with coming up with more test cases.

This PR uses some code borrowed from #10360 to use effective values when selecting coins.

achow101 force-pushed on Jun 20, 2017

in src/wallet/coinselection.cpp:48 in 0246f1f79f outdated

43+    std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
44+    
45+    // Calculate remaining
46+    CAmount remaining = 0;
47+    for (CInputCoin utxo : utxo_pool) {
48+        remaining += utxo.txout.nValue;

Xekyo commented at 6:46 pm on June 20, 2017:

Have you filtered utxo_pool to exclude utxo’s that have a net-neg value? Otherwise you’re underestimating the lookahead here. To get an accurate figure for what you may still collect downtree, you should only add utxo.txout.nValue >=0

instagibbs commented at 7:25 pm on June 20, 2017:

@gmaxwell has concerns that Core wallet is only doing semi-sane utxo handling by spending these. With exact match + sane backoff algorithm this concern may be alleviated?

achow101 commented at 7:31 pm on June 20, 2017:

Indeed, that may be a problem. I will add that in as it is still good to have additional checks here even if done elsewhere.

gmaxwell commented at 7:49 pm on June 20, 2017:

I don’t have much of a concern here about the 0/negative effective value inputs: Failing to select negative effective value inputs for an exact match won’t lead to a UTXO count inflation, because changeless transactions are by definition strictly UTXO reducing.

Xekyo commented at 7:51 pm on June 20, 2017:

@instagibbs: I’m not completely opposed to spending net-negative UTXO, my concern here is primarily that it actually may cause the lookahead to be underestimated causing valid solutions not to be found.

I realize now that the knapsack algorithm would also not select uneconomic UTXO anymore, as if it had selected enough value before it reached them it would have already returned the set, and if it actually starts exploring them, cannot add more value in the first place.

Advocatus Diaboli: Would it be that terrible though, if UTXO were only considered when they actually have a net positive value? During times of low fees, they’d be used both during BnB and knapsack, during times of high fees, they wouldn’t bloat the blocks and lose their owner money.

instagibbs commented at 7:58 pm on June 20, 2017:

I am not so concerned, was making sure concerns are brought up.

gmaxwell commented at 6:45 pm on June 22, 2017:

@xekyo we should assume that it would be terrible unless someone can show that it will not cause another massive UTXO bloat event… but thats offtopic here, as I don’t think anyone has this concern with exact matches.

karelbilek commented at 11:50 am on July 1, 2017:

The utxos with negative effective values are filtered anyway in wallet/wallet.cpp, which is the only place (except for tests) from where SelectCoinsBnB is called.

in src/wallet/test/coinselector_tests.cpp:150 in 0246f1f79f outdated

139+    actual_selection.clear();
140+    selection.clear();
141+    
142+    // Select 5 Cent
143+    add_coin(4 * CENT, 4, actual_selection);
144+    add_coin(1 * CENT, 1, actual_selection);

Xekyo commented at 7:05 pm on June 20, 2017:

AFAICT utxo_pool has : 4, 3, 2, & 1. Since you’re exploring randomly selecting 5 then has two possible solutions: 4+1, 3+2.

achow101 commented at 7:28 pm on June 20, 2017:

It is forced to be include first in these tests so the solution is deterministic.

in src/wallet/test/coinselector_tests.cpp:163 in 0246f1f79f outdated

154+    
155+    // Select 10 Cent
156+    add_coin(5 * CENT, 5, utxo_pool);
157+    add_coin(5 * CENT, 5, actual_selection);
158+    add_coin(4 * CENT, 4, actual_selection);
159+    add_coin(1 * CENT, 1, actual_selection);

Xekyo commented at 7:08 pm on June 20, 2017:

Under above assumptions, there is two solutions here as well: 5+4+1, or 5+3+2.

achow101 commented at 7:28 pm on June 20, 2017:

It is forced to be include first in these tests so the solution is deterministic.

in src/wallet/wallet.cpp:2237 in 0246f1f79f outdated

2306-                }
2307-            }
2308-            LogPrint(BCLog::SELECTCOINS, "total %s\n", FormatMoney(nBest));
2309-        }
2310+        CInputCoin coin(pcoin, i);
2311+        coin.txout.nValue -= (output.nInputBytes < 0 ? 0 : effective_fee.GetFee(output.nInputBytes));

Xekyo commented at 7:16 pm on June 20, 2017:

It seems to me that you’re also collecting coins that have a net-negative here. This will cause your lookahead to be underestimated, unless you cater to that case when calculating the remainder.

in src/wallet/test/coinselector_tests.cpp:116 in 0246f1f79f outdated

108+    std::vector<CInputCoin> utxo_pool;
109+    CoinSet selection;
110+    CoinSet actual_selection;
111+    CAmount value_ret = 0;
112+    
113+    /////////////////////////

Xekyo commented at 7:22 pm on June 20, 2017:

I would perhaps add a test that checks what happens if the utxo_pool includes a UTXO that is more costly to spend than its own value. As far as I can tell, this would currently reduce your lookahead and may cause a premature search failure.

Xekyo changes_requested

Xekyo commented at 7:23 pm on June 20, 2017: member

Concept ACK, looks good to me. AFAICT, there’s an issue with the lookahead that should be addressed still.

Xekyo commented at 7:46 pm on June 20, 2017: member

Have you tested the effect of random exploration vs largest first exploration?

Either way, BranchAndBound already guarantees that the global utxo set doesn’t grow (for one output transactions) due to saving the change output.
LFE guarantees the creation of a minimal input set, and purposefully finds a possible solution. This should minimize the input set size variance. In my simulations BranchAndBound with LFE already caused a smaller average UTXO footprint than legacy Core selection.
Random Exploration could find a larger input set by skipping a key UTXO higher up in the tree. This could lead to the selection of a larger number of inputs, or in an edge case could even cause tries to be exhausted before a solution is found. This may increase input set variance, or could perhaps even exhaust small UTXOs too quickly for BnB to often find a viable solution.

I am not sure there is a significant privacy benefit for Random Exploration as for either selection method an attacker would already need to know about another eligible input that would achieve an exact match when switched out for one of the input set.

What benefit do you expect from using Random Exploration?

achow101 commented at 8:25 pm on June 20, 2017: member

@Xekyo I was thinking that Random Exploration would be better for privacy but I see that it probably wouldn’t help. If you think it would be better to change to LFE, I can certainly do that.

Xekyo commented at 8:33 pm on June 20, 2017: member

@achow101: I don’t know how strong the effect is, but I’d expect Random Exploration to increase the required computational effort.

instagibbs commented at 8:52 pm on June 20, 2017: member

Noting that this PR has fairly heavy overlap with #10360 .

From chatting with @achow101 the intention of this PR is to touch as little as possible while still getting BranchNBound coin selection.

To make this successful it should really only be run on first iteration of the loop in CreateTransaction, when nFeeRet == 0 and only use effective value for the BnB coin selection step, rather than the knapsack as well. Once nFeeRet becomes more than zero, interactions start to get strange without a more complete overhaul like #10360.

instagibbs commented at 8:59 pm on June 20, 2017: member

This PR I believe will still create just-over-dust change outputs when BnB finds an exact match. Whenever we are allowing BnB matches(first iteration) we should not make change outputs less than the exact match slack value.

in src/wallet/wallet.cpp:2244 in 0246f1f79f outdated

2313+    }
2314+    if (!use_only_knapsack) {
2315+        // Calculate cost of change
2316+        // TODO: In the future, we should use the change output actually made for the transaction and calculate the cost
2317+        // requred to spend it.
2318+        CAmount cost_of_change = effective_fee.GetFee(148+34); // 148 bytes for the input, 34 bytes for making the output

Xekyo commented at 9:01 pm on June 20, 2017:

This assumes that the input will be spent at a feerate at least as high as the current. This was a valid assumption in my thesis, as I was using a fixed fee rate. I’m not sure whether this a valid assumption for realnet transaction selection, as we’ve literally seen fees between 8-540 sat/byte in the past two weeks. We might want to consider discounting the cost of the input slightly.

instagibbs commented at 9:01 pm on June 20, 2017:

Depends on user time preferences. Could be an option that is set for those who regularly consolidate.

achow101 commented at 11:33 pm on June 20, 2017:

For now I think it is fine to use the current feerate.

Xekyo commented at 9:04 pm on June 20, 2017: member

@instagibbs: In fact, BnB is designed to only work when creating a transaction without a change output. If we were creating a change in the first place, the extensive search pattern would be unnecessarily wasteful.

instagibbs commented at 9:15 pm on June 20, 2017: member

To append onto my previous comments, any effective value match attempt should account for the fees just obtained by SelectCoins. Currently it completely ignores the newly-obtained fees, keeping the previous loop’s value, and then asks if nFeeRet >= nFeeRequired to break from the loop(which currently is 0 on the first go-around).

fanquake added the label Wallet on Jun 20, 2017

achow101 commented at 0:32 am on June 21, 2017: member

I have made the BnB selector to be only run on the first pass of the coin selection loop. It is now set so that effective value is only used for the BnB selector and not the knapsack one. I have also added the negative effective value check and test just as a belt-and-suspenders thing. I also made BnB use Largest First Exploration instead of Random Exploration.

in src/wallet/coinselection.cpp:58 in 1f4b03a33f outdated

53+    {
54+        if (value_ret > target_value + cost_of_change) { // Selected value is out of range, go back and try other branch
55+            backtrack = true;
56+        } else if (value_ret >= target_value) { // Selected value is within range
57+            done = true;
58+        } else if (tries <= 0) { // Too many tries, exit

Xekyo commented at 9:38 pm on June 21, 2017:

Here’s a unexpected behavior in my algorithm: if there is a number of input combinations whose value_ret all exceed the target_value when tries == 0 is passed, tries can go into the negative.

The tries check should be moved to the top of the checks.

achow101 commented at 10:49 pm on June 21, 2017:

Done

sipa commented at 11:26 pm on June 21, 2017: member

Perhaps generically, we should never create change if the amount is less than the cost of creating + spending it (regardless of whether BnB was used to find the inputs or not)?

instagibbs commented at 2:05 pm on June 22, 2017: member

@sipa one question is if we should allow the wallet to consider consolidation-level prices for that change. Perhaps the user is in a hurry now, but would consider spending that change at a much slower pace.

Maybe for a first pass only consider the selected feerate, then Future Work allow a parameter which has more aggressive change protection given longer timescales.

sipa commented at 4:26 pm on June 22, 2017: member

@instagibbs Yes, I agree; we should use long-eatimates for the spend part of change rather than the actual feerate the user is willing to pay now. Perhaps we can make it more conservative without doing that by using a factor 2 or 3 reduction?

in src/wallet/wallet.cpp:2224 in 12aa63abf1 outdated

2281-            continue;
2282+    if (!only_knapsack) {
2283+        // Calculate cost of change
2284+        // TODO: In the future, we should use the change output actually made for the transaction and calculate the cost
2285+        // requred to spend it.
2286+        CAmount cost_of_change = effective_fee.GetFee(148+34); // 148 bytes for the input, 34 bytes for making the output

gmaxwell commented at 6:53 pm on June 22, 2017:

not correct for segwit. If this code ends up being changed to follow pieter’s suggestion of dividing the rate by two or three it should be bounded by the min relay fee. (I’m not super fond of that suggestion).

gmaxwell commented at 6:57 pm on June 22, 2017: contributor

@sipa @achow101 it would be very very easy in the current PR to ask for another estimate for the change, I think ~two loc addition, and minor addition to the selectcoins arguments to pass down a second fee. I think this would be much more desirable than a fixed division. Future work could do things like make that second confirmation target configurable.

in src/wallet/wallet.cpp:2565 in 12aa63abf1 outdated

2561@@ -2562,7 +2562,7 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2562                 }
2563 
2564                 const CAmount nChange = nValueIn - nValueToSelect;
2565-                if (nChange > 0)
2566+                if (nChange > 0 && (!first_pass || nFeeRet == 0)) // nFeeRet is only 0 on the first pass if BnB was not used.

gmaxwell commented at 7:11 pm on June 22, 2017:

Using nFeeRet to signal BNB usage is ugly. I think you shouldn’t pass in nFeeRet at all, but have some explicit signal (e.g. boolean return) for BNB usage and if its set; after select coins set nFeeRet to nChange and use the same signal to bypass this branch.

I also think this condition is slightly incorrect but benign in the current code, lets say our configured feerate were zero: now BNB could find a solution and leave nFeeRet==0. (though nChange would currently be zero too, so it would be harmless but seems to me like the kind of thing to be brittle in future changes)

achow101 commented at 5:32 pm on June 23, 2017: member

Travis failure seems to be unrelated

karelbilek commented at 2:46 am on July 2, 2017: contributor

just fyi, I have used your code as a reference for this code

https://github.com/bitcoinjs/coinselect/pull/13

karelbilek commented at 8:14 pm on July 2, 2017: contributor

I have to say, I don’t understand the target size; maybe there is a bug there.

In wallet.cpp, in CWallet::CreateTransaction, you create nValue, which seems to be the sum of all the outputs. Because the BnB is used only at the first pass, nFeeRet is 0 and nValueToSelect is just the sum of all the outputs.

This is then used as the exact target in the BnB algorithm.

However, you should add the cost of the outputs + the small cost of the tx overhead into the target (done here for the simple case on 1 output - https://github.com/Xekyo/CoinSelectionSimulator/blob/master/src/main/scala/one/murch/bitcoin/coinselection/StackEfficientTailRecursiveBnB.scala#L28 )

Maybe it’s done somewhere, but I don’t see it.

achow101 commented at 8:22 pm on July 2, 2017: member

@runn1ng BnB uses effective values for the inputs so the fee is accounted for when coins are selected. The effective values are calculated in SelectCoinsMinConf

karelbilek commented at 8:27 pm on July 2, 2017: contributor

That eff. value accounts for the inputs of the new transaction, but not for the outputs (plus the overhead of the tx itself, but that is only about 10 bytes).

In SelectCoinsMinConf, you already have the target, which does not account for that.

achow101 commented at 9:26 pm on July 2, 2017: member

Ah, yes. That is a bug. Thanks for finding that!

achow101 force-pushed on Jul 2, 2017

in src/wallet/wallet.cpp:2537 in 407133d206 outdated

2531@@ -2517,6 +2532,9 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2532                             fFirst = false;
2533                             txout.nValue -= nFeeRet % nSubtractFeeFromAmount;
2534                         }
2535+                    } else if (first_pass){
2536+                        // On the first pass BnB selector, include the fee cost for outputs
2537+                        output_fees +=  nFeeRateNeeded.GetFee(recipient.scriptPubKey.size());

instagibbs commented at 3:00 pm on July 3, 2017:

I think it may be better to directly check on serialized size of an output based on that pubkey

in src/wallet/wallet.cpp:2224 in 407133d206 outdated

2281-            continue;
2282+    if (!only_knapsack) {
2283+        // Get the fee rate to use for the change fee rate
2284+        CFeeRate change_feerate;
2285+        FeeCalculation feeCalc;
2286+        change_feerate = GetMinimumFeeRate(1008, ::mempool, ::feeEstimator, &feeCalc);

instagibbs commented at 3:09 pm on July 3, 2017:

just set it when declaring the variable two lines above and make it const

in src/wallet/wallet.cpp:2214 in 407133d206 outdated

2256-    }
2257-}
2258-
2259 bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const int nConfMine, const int nConfTheirs, const uint64_t nMaxAncestors, std::vector<COutput> vCoins,
2260-                                 std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet) const
2261+                                 std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, CAmount& fee_ret, const CFeeRate effective_fee, bool& used_bnb, bool only_knapsack, int change_size) const

instagibbs commented at 3:16 pm on July 3, 2017:

right now it only uses one or the other, so !only_knapsack means used_bnb. I assume this interface is future-looking to where we may try multiple strategies?

achow101 commented at 5:58 pm on July 3, 2017:

The idea behind this was to have BnB be just strictly on top of the current behavior, and separating it like this makes that possible. The first time through the loop uses BnB, but then every time after that uses only the current selector. The loop behavior also stays the same since nFeeRet will remain 0 if the BnB fails.

in src/wallet/wallet.cpp:2507 in 407133d206 outdated

2502@@ -2556,7 +2503,22 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2503                 CAmount nValueToSelect = nValue;
2504                 if (nSubtractFeeFromAmount == 0)
2505                     nValueToSelect += nFeeRet;
2506+
2507+                // Get the fee rate to use effective values in coin selection

instagibbs commented at 3:22 pm on July 3, 2017:

Since we’re moving it already, there’s no reason to not just move this block outside the loop, right? See: https://github.com/bitcoin/bitcoin/pull/10360/files#diff-b2bb174788c7409b671c46ccc86034bdR2476

in src/wallet/wallet.cpp:2576 in 407133d206 outdated

2574+                    else {
2575+                        strFailReason = _("Insufficient funds");
2576+                        return false;
2577+                    }
2578+                }
2579+                if (first_pass) {

instagibbs commented at 3:33 pm on July 3, 2017:

this should be used_bnb? Kind of unclear what the difference is currently.

in src/wallet/wallet.cpp:2493 in 407133d206 outdated

2489@@ -2544,6 +2490,7 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2490             AvailableCoins(vAvailableCoins, true, coinControl);
2491 
2492             nFeeRet = 0;
2493+            bool first_pass = true;

instagibbs commented at 4:20 pm on July 3, 2017:

Add a comment saying this triggers BnB to be the only type tried when true

in src/wallet/wallet.h:863 in 407133d206 outdated

849@@ -837,7 +850,8 @@ class CWallet : public CCryptoKeyStore, public CValidationInterface
850      * completion the coin set and corresponding actual target value is
851      * assembled
852      */
853-    bool SelectCoinsMinConf(const CAmount& nTargetValue, int nConfMine, int nConfTheirs, uint64_t nMaxAncestors, std::vector<COutput> vCoins, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet) const;
854+     // TODO: Change the hard coded change_size when we aren't only using P2PKH change outputs

instagibbs commented at 5:24 pm on July 3, 2017:

if we’re going to change it later to something without a default/dynamic value, maybe just get rid of the default arg and pass it each time.

instagibbs commented at 8:34 pm on September 18, 2017:

this is getting more important now with segwit, and the fact that we have two related optional arguments

in src/wallet/wallet.h:984 in 407133d206 outdated

975@@ -962,11 +976,23 @@ class CWallet : public CCryptoKeyStore, public CValidationInterface
976      */
977     static CAmount GetMinimumFee(unsigned int nTxBytes, unsigned int nConfirmTarget, const CTxMemPool& pool, const CBlockPolicyEstimator& estimator, FeeCalculation *feeCalc = nullptr, bool ignoreGlobalPayTxFee = false);
978     /**
979+     * Estimate the minimum fee rate considering user set parameters
980+     * and the required fee

instagibbs commented at 5:25 pm on July 3, 2017:

perhaps note it doesn’t have the maxtxfee check inside it, making it slightly asymmetrical to the total fee one.

instagibbs commented at 5:28 pm on July 3, 2017: member

In general the semantics of first_run and used_bnb seem tightly linked, and are seemingly used interchangeably. Perhaps something to revisit.

achow101 force-pushed on Jul 3, 2017

karelbilek commented at 10:22 pm on July 3, 2017: contributor

@achow101 for some reason, when I do simulations either on @Xekyo set (in scala) or on bitcoinjs randomly generated data (with the algo rewritten into javascript), the total fees are actually lower when I make the target lower (that is, when I do not include the output cost in the target). So maybe tightening the target rejects more transactions and then the fallbacks somehow make better results.

I will investigate more when I have the time and write results here https://github.com/Xekyo/CoinSelectionSimulator/issues/5

achow101 force-pushed on Jul 5, 2017

instagibbs commented at 5:40 pm on July 6, 2017: member

@runn1ng if you wouldn’t mind, I’d like to know what the difference in rate of change creation for each of those experiments as well.

Xekyo commented at 8:21 pm on July 6, 2017: member

[…]the total fees are actually lower when I make the target lower (that is, when I do not include the output cost in the target). @runn1ng: Um wait. “Target” is the amount to be selected. We are talking about the “cost of change” parameter that gives the leniency window for the exact match, right? Also, do you mean “input cost” instead of “output cost”?

It would be lovely if you could post your experiment’s results somewhere, so we all have the same dataset to discuss.

karelbilek commented at 4:18 pm on July 11, 2017: contributor

@Xekyo The problem with your experiment is that it’s non-deterministic… but maybe I could put there some pre-set random seed

karelbilek commented at 8:13 am on July 13, 2017: contributor

edit: ignore the graphs, see comment below

 0
 1~~~Anyway. I tried changing the cost of change on your scala code, as I wrote here - https://github.com/Xekyo/CoinSelectionSimulator/pull/8 . Now I tried values from 0 to 100 as percent, and this is the result (note that left axis doesn't start at 0)~~~
 2
 3![chart](https://user-images.githubusercontent.com/104945/28156350-aae80dca-67b2-11e7-810e-61eb70867996.png)
 4
 5[google spreadsheet link](https://docs.google.com/spreadsheets/d/1ePfoi08uV_QU48Q68aAu6apB-BG9DwM52JRgxNgSWPk/edit?usp=sharing)
 6
 7~~~x axis is how much percent of the current cost of change is used; y axis is total cost on the big honeypot data set.~~~
 8
 9~~~On the small random test cases there is no difference (what matters more there is the fallback, but that's for another experiment).~~~
10
11~~~Note that there was a [typo](https://github.com/Xekyo/CoinSelectionSimulator/pull/4/files) in the original experiments for the paper, which makes the cost of change "factor" 83%~~~

karelbilek commented at 10:18 am on July 13, 2017: contributor

edit: ignore the graphs, see comment below

0
1~~~If you I try the same at the bitcoinjs example - [defined here](https://github.com/bitcoinjs/coinselect/blob/master/stats/index.js#L9) - small random examples with relatively few utxos - the graph looks completely different, and very dependent on what is a "backup plan" in the case of not found match~~~
2
3![chart 1](https://user-images.githubusercontent.com/104945/28161722-d7710484-67c4-11e7-84cd-09f86393622c.png)
4
5[google sheet](https://docs.google.com/spreadsheets/d/1zUen5aiKfDwRIRkOg-QJgAE0uEn-_OsrSUQwJm2xWDs/edit?usp=sharing)
6
7~~~"rand" is random, "min" is sorting the utxos from the biggest to the lowest and starting from the biggest. (Both are total cost.) I am not sure what "min" strategy does on the big data.~~~
8
9~~~(Just for interest, when I tried 100-200%, the graph goes up again, but not that quickly)~~~

karelbilek commented at 9:44 am on July 14, 2017: contributor

edit: ignore the graphs, see comment below

0
1![chart 2](https://user-images.githubusercontent.com/104945/28207255-47c33440-6889-11e7-9e50-dcfcc444c81e.png)
2
3~~~Again, it's always better to take the "minimal" strategy (that is, to sort utxos by value size descending, and then take from the start until it's enough).~~~
4
5~~~If you want to replicate this experiment - note that it takes, for reasons I don't understand, terribly long time, and you will have to parallelize the simulation - luckily, that's trivial with scala paralel collections - see the commits at https://github.com/runn1ng/CoinSelectionSimulator/tree/exp_multi~~~
6
7~~~I would like to hear [@Xekyo](/bitcoin-bitcoin/contributor/xekyo/) opinions :)~~~
8
9~~~Also I would like to try this PR strategy, that is, to take the current core strategy as a backup.... but that is too complicated (especially in the javascript code), so I won't do it.~~~

achow101 commented at 7:53 pm on July 14, 2017: member

@runn1ng would you be able to try the strategy with Core’s current selector as fallback? The easiest way to do that would be to add/modify the test cases for coin selection.

Xekyo commented at 9:52 pm on July 14, 2017: member

@runn1ng: re random data: I’d surmise that BnB doesn’t perform well on small datasets as there are too few possible combinations. That could easily cause the fallback algorithm to dominate.

re moneypot: What I do find confusing is that your total cost is so much higher than my result with Branch and Bound + Single Random Draw of 58,940,772.30. Were you still running with fixed fees of 10000 satoshi/kB?

I haven’t comprehensively tested all possible fallback algorithms, it is possible that Largest First selection as a fallback to BnB is more efficient as it doesn’t take away as many small utxo that can be used to create combinations.

Do I understand correctly that you calculated “cost of change” and then took a percentage of that, or is this percentage only on the cost of the input? If you did the former, it appears that using just the cost of an additional output as “cost of change” leads to a minimum, considering that 34 bytes is 18.7% of what I proposed as “cost of change” with output+input.

karelbilek commented at 3:29 am on July 15, 2017: contributor

What I do find confusing is that your total cost is so much higher than my result with Branch and Bound + Single Random Draw of 58,940,772.30. Were you still running with fixed fees of 10000 satoshi/kB?

That is weird indeed.

I am running code from your repo. To be sure I reverted all my local changes and I still get 72506973.

When I made the correction here https://github.com/Xekyo/CoinSelectionSimulator/pull/9 , I get total cost 70858076

I use only StackEfficientTailRecursiveBnB, should I try the other BnBs? edit: well, they get stack overflow, so I won’t. :D

karelbilek commented at 3:31 am on July 15, 2017: contributor

I am running the code through sbt run in the main directory. I look just at the total cost in the resulting csv.

karelbilek commented at 3:45 am on July 15, 2017: contributor

I get totally different numbers than in your paper with the other scenarios too. The numbers don’t correspond to neither of the three tables, unfortunately.

edit: oooh, that’s because I am running “MoneyPot After LF”, which was the default scenario, but it’s actually with additional UTXOs from a previous run. The actual scenario from the paper (the first one) is TestCaseMoneyPotEmpty, right.

Xekyo commented at 4:34 am on July 15, 2017: member

Yes correct. The Moneypot after LF, is running the MoneyPot scenario starting with the resulting UTXO pool of running it with Largest First selection before.

karelbilek commented at 11:27 pm on July 17, 2017: contributor

I found out that the two repos for coinselect simulation returned different results for the same strategy, so I painstakingly went through both of them and found where they differ… and put tons of of PRs to both, so they now both return the same results with the same fees + setup

The differences in simulations were:

how they deal with insufficient funds (and how they detect it)
what is minimum change
what are the sizes of “defaut” input/output
some small bugs

…and those added to significant differences. Anyway, when I fixed all the issues, those are the results/graphs I get:

this is for the moneypot scenario, with the fees 10 sat/bitcoin

chart 3 google sheet

this is for the moneypot scenario, when I increase the fee to 200 sat/bitcoin (but I left the values, so more utxos become unspendable)

chart 6 google sheet

In both, rand is slightly better. I am not sure what happened, if it’s because the scenario is different (without the large UTXO set) or because of the subtle differences in benchmarking. The shape is similar though.

This is the scenario of small randomly generated wallets

chart 5 google sheet

BnB+LF performs better, optimum about 50% cost of change.

So, different strategies/parameters are better at different scenarios. Again, there is danger of overfitting on one scenario - plus there might be some more subtle bugs in the benchmark code… in my wallet code, I will probably just use BnB+LF with 50% of cost and call it a day :)

I haven’t shown this in graphs, but having BnB is always better than not having it. :)

If you want to repeat the tests, my forks of the repos are here 1 2

karelbilek commented at 11:29 pm on July 17, 2017: contributor

@Xekyo

Do I understand correctly that you calculated “cost of change” and then took a percentage of that, or is this percentage only on the cost of the input? If you did the former, it appears that using just the cost of an additional output as “cost of change” leads to a minimum, considering that 34 bytes is 18.7% of what I proposed as “cost of change” with output+input.

Hm, that doesn’t seem to be the case, the minimum is not 18%, but 30% to 50% on these two scenarios.

instagibbs commented at 11:50 pm on July 17, 2017: member

@runn1ng is there a plausible explanation why not accounting for the full cost of the change is cheaper overall?

karelbilek commented at 0:00 am on July 18, 2017: contributor

@achow101

@runn1ng would you be able to try the strategy with Core’s current selector as fallback? The easiest way to do that would be to add/modify the test cases for coin selection.

Hm, I already spent too much time on this… :/ I will see if I have time to look into the bitcoin coin selection tests and how to add benchmarks there, but not promising anything.

karelbilek commented at 0:14 am on July 18, 2017: contributor

@instagibbs

I think - and that’s a speculation - that it’s because the target is “tighter”, so the BnB will reject more “lose” matches and will continue searching until it finds better match. So less fee is spent then, even when some matches are rejected that didn’t have to be (and those spend more on fees).

Btw. An interesting thing I just noticed - in the “small random” example, there is not that many BnB matches in the first place! Around 30 (out of 10.000 transactions). It still has an effect on the result…

in src/wallet/coinselection.cpp:105 in 71e9d683be outdated

84+
85+            // Walk backwards to find the first utxo which has not has its second branch traversed
86+            while (selection.at(depth).second) {
87+                // Reset this utxo's selection
88+                if (selection.at(depth).first) {
89+                    value_ret -= utxo_pool.at(depth).txout.nValue;

karelbilek commented at 6:25 pm on July 18, 2017:

This line never fires.

It never happens, that an utxo is at the same time in an exclusion branch (which is what .second does) and is also selected (what .first does). Which makes sense; you never at the same time select and not select an utxo :)

With all my simulations, this line never seems to fire (when I rewrote this to JS).

So the other line after if can also be deleted.

karelbilek commented at 6:31 pm on July 18, 2017:

I also think that .second is not needed at all; all the information necessary is in the first and depth; the only situation where .first != !(.second) is after we backtrack here, but the information in .second is useless anyway (since we will change it anyway before we backtrack to it again).

achow101 commented at 6:36 pm on July 18, 2017:

Right. That appears to be a relic of when this randomly selected which branch to try first before I changed it to always try including first.

in src/wallet/coinselection.cpp:123 in 71e9d683be outdated

 98+                if (depth < 0) { // We have walked back to the first utxo and no branch is untraversed. No solution, exit.
 99+                    return false;
100+                }
101+            }
102+            
103+            if (!done) {

karelbilek commented at 7:53 pm on July 18, 2017:

This is never true here. done is never true when backtrack is true. (Istanbul caught that :))

karelbilek commented at 7:55 pm on July 18, 2017:

I mean done is never true and this block always happens

Xekyo commented at 8:34 pm on July 18, 2017:

This block doesn’t happen when backtrack is false and done is true which happens when a solution is found.

karelbilek commented at 8:36 pm on July 18, 2017:

in that case, the while cycle terminates before that

karelbilek commented at 8:38 pm on July 18, 2017:

In the if at the start of the while cycle, either backtrack or done is set, never both. We got here only when backtrack == true, so done cannot be true.

instagibbs commented at 8:23 pm on September 18, 2017:

ACK on @runn1ng ’s comment. Impossible to be “done” and require backtracking.

morcos commented at 8:30 pm on March 6, 2018:

Agree on removing this unnecessary check

karelbilek commented at 12:11 pm on August 10, 2017: contributor

@achow101 frankly, the “old” (current) core code seems to complex to me, because it introduces state, I don’t understand it enough to make the simulation with the current core code as a backup

achow101 force-pushed on Aug 11, 2017

achow101 force-pushed on Aug 15, 2017

achow101 force-pushed on Aug 17, 2017

achow101 commented at 11:00 pm on August 17, 2017: member

I have squashed a few commits and rebased this. I’ll work on this some more after the 0.15.0 release.

achow101 force-pushed on Sep 6, 2017

achow101 commented at 9:28 pm on September 6, 2017: member

I have squashed this even more (by getting a diff and re-committing) and hopefully made each commit a more logical chunk of code.

I have also changed this to use the discard fee rate for the change fee rate. The cost of change is also now calculated with the fee rate for making an output being the effective fee rate (fee rate being used) and the fee rate for spending the change being the discard fee rate.

The original commits are available in a separate branch here: https://github.com/achow101/bitcoin/tree/bnb-coin-select-orig (just in case I screwed something up).

achow101 force-pushed on Sep 6, 2017

achow101 commented at 3:45 pm on September 18, 2017: member

I’m not sure what the travis failure here was so I restarted that build.

MarcoFalke commented at 7:22 pm on September 18, 2017: member

@achow101 Travis failure is due to some weird behavior of travis to merge in latest master, but keep the yaml or config from the past (maybe when the pull was created).

You might be able to fix it by force pushing the last commit (EDITOR=true git commit --amend && git push origin bnb-coin -f) or just rebase on master.

in src/wallet/coinselection.cpp:31 in 88ca715178 outdated

26+bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, std::vector<CAmount>& fee_vec, CAmount& fee_ret)
27+{
28+    out_set.clear();
29+    value_ret = 0;
30+
31+    if (utxo_pool.size() <=0) {

instagibbs commented at 7:51 pm on September 18, 2017:

just empty() seems more straight forward

achow101 commented at 1:47 am on September 19, 2017:

Done

in src/wallet/coinselection.cpp:45 in 88ca715178 outdated

40+    bool backtrack = false;
41+
42+    // Sort the utxo_pool
43+    std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
44+
45+    // Calculate remaining

instagibbs commented at 7:53 pm on September 18, 2017:

define “remaining”, or drop the comment

achow101 commented at 1:47 am on September 19, 2017:

Done; renamed to lookahead

in src/wallet/coinselection.cpp:51 in 88ca715178 outdated

46+    CAmount remaining = 0;
47+    for (CInputCoin utxo : utxo_pool) {
48+        remaining += utxo.txout.nValue;
49+    }
50+
51+    // Depth first search to find

instagibbs commented at 7:54 pm on September 18, 2017:

to find what?

achow101 commented at 1:47 am on September 19, 2017:

Done

in src/wallet/coinselection.cpp:36 in 88ca715178 outdated

31+    if (utxo_pool.size() <=0) {
32+        return false;
33+    }
34+
35+    int depth = 0;
36+    int tries = 100000;

instagibbs commented at 7:54 pm on September 18, 2017:

remaining_tries?

achow101 commented at 1:47 am on September 19, 2017:

done

in src/wallet/coinselection.cpp:37 in 88ca715178 outdated

32+        return false;
33+    }
34+
35+    int depth = 0;
36+    int tries = 100000;
37+    std::vector<std::pair<bool, bool>> selection; // First bool: select the utxo at this index; Second bool: traversing second branch of this utxo

instagibbs commented at 7:56 pm on September 18, 2017:

define what second branch means?

achow101 commented at 1:47 am on September 19, 2017:

Done

in src/wallet/wallet.h:457 in feeb3cab3e outdated

452@@ -453,6 +453,9 @@ class CWalletTx : public CMerkleTx
453     CAmount GetAvailableWatchOnlyCredit(const bool& fUseCache=true) const;
454     CAmount GetChange() const;
455 
456+    // Get the marginal bytes if spending the specified output from this transaction
457+    int GetSpendSize(unsigned int i) const;

instagibbs commented at 8:32 pm on September 18, 2017:

nOut or something better please

achow101 commented at 1:47 am on September 19, 2017:

done

in src/wallet/wallet.cpp:2357 in feeb3cab3e outdated

2484-
2485-    return true;
2486 }
2487 
2488-bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CCoinControl* coinControl) const
2489+bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, CAmount& fee_ret, const CFeeRate effective_fee, const CCoinControl& coin_control, bool use_bnb, int change_size) const

instagibbs commented at 8:33 pm on September 18, 2017:

Some asymmetry now with SC and SCMC, the former having one “change size” parameter, the other two. change_output_size to match.

achow101 commented at 1:47 am on September 19, 2017:

done

in src/wallet/wallet.h:1239 in feeb3cab3e outdated

1209@@ -1195,4 +1210,12 @@ bool CWallet::DummySignTx(CMutableTransaction &txNew, const ContainerType &coins
1210     return true;
1211 }
1212 
1213+// Calculate the size of the transaction assuming all signatures are max size
1214+// Use DummySignatureCreator, which inserts 72 byte signatures everywhere.
1215+// TODO: re-use this in CWallet::CreateTransaction (right now
1216+// CreateTransaction uses the constructed dummy-signed tx to do a priority
1217+// calculation, but we should be able to refactor after priority is removed).

instagibbs commented at 8:34 pm on September 18, 2017:

priority is removed; revisit?

achow101 commented at 1:43 am on September 19, 2017:

You wrote it (I took it from one of your commits); revisit it for me :D

in src/wallet/coinselection.cpp:72 in 31914f0697 outdated

69+            curr_waste += value_ret - target_value;
70+            if (curr_waste <= best_waste) {
71+                best_selection.assign(selection.begin(), selection.end());
72+                best_waste = curr_waste;
73+            }
74+            curr_waste -= value_ret - target_value;

instagibbs commented at 8:46 pm on September 18, 2017:

parens around the value being subtracted would be nice

in src/wallet/coinselection.cpp:67 in 31914f0697 outdated

64             backtrack = true;
65+        } else if (curr_waste > best_waste) { // Don't select things which we know will be more wasteful
66+            backtrack = true;
67         } else if (value_ret >= target_value) { // Selected value is within range
68-            done = true;
69+            curr_waste += value_ret - target_value;

instagibbs commented at 8:47 pm on September 18, 2017:

parens around the value being subtracted would be nice

instagibbs commented at 9:00 pm on September 18, 2017:

Also, note that this value is the “excess” being added and removed later, in contrast to the input-selection waste (wonder if we can find a good name for this cost)

achow101 commented at 1:47 am on September 19, 2017:

Done here and elsewhere

achow101 commented at 1:48 am on September 19, 2017:

Done

instagibbs commented at 8:53 pm on September 18, 2017: member

Added some comments. Still working through the latest commit.

in src/wallet/coinselection.cpp:26 in 88ca715178 outdated

21+    {
22+        return t1.txout.nValue < t2.txout.nValue;
23+    }
24+};
25+
26+bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, std::vector<CAmount>& fee_vec, CAmount& fee_ret)

instagibbs commented at 9:09 pm on September 18, 2017:

nit, can you rename it input_fee_vec

achow101 commented at 1:48 am on September 19, 2017:

Done

achow101 force-pushed on Sep 19, 2017

achow101 commented at 1:49 am on September 19, 2017: member

Rebased and addressed @instagibbs’s comments

achow101 force-pushed on Sep 19, 2017

karelbilek commented at 12:57 pm on September 27, 2017: contributor

@achow101 I cannot find it in the comments anymore, but you asked me for the simulation data some time ago

I tried the simulation on two targets.

First scenario (moneypot scenario) is I think from here (note - large file; one line is one income/expense) https://github.com/Xekyo/CoinSelectionSimulator/tree/master/src/main/resources/scenarios

Second is randomly generated from here https://github.com/bitcoinjs/coinselect/blob/master/stats/index.js

It would probably be better if you run the c++ core code directly though; my simulations were on the javascript + scala code

MarcoFalke deleted a comment on Sep 30, 2017

karelbilek commented at 10:15 pm on September 30, 2017: contributor

I am looking at this commit

https://github.com/achow101/bitcoin/commit/0fb73ae532aab061d3df0be54579b6d40c1e93ff

I have to say, I don’t understand, why are long term fees used in the waste calculation and what exactly does this mean

0CCoinControl temp;
1temp.m_confirm_target = 1008;
2CFeeRate long_term_feerate = GetMinimumFeeRate(temp, ::mempool, ::feeEstimator, &feeCalc);

long_term_feerate will be some very small fee that guarantees send in 1008 blocks, right? Why is that used in the waste calculation?

Xekyo commented at 10:40 pm on September 30, 2017: member

Pieter pointed out that the algorithm doesn’t necessarily find the best solution when it discovers the first solution. However, it was then at first not clear how to make the trade-off between making the input set smaller or reducing the excess in the selection.

The idea is that during high fee rates, it might be beneficial to the user if a smaller input count is preferred in exchange for a higher excess, while at low fee rates, a higher input count might be acceptable to achieve a smaller excess.

We came up with the waste metric to combine both of these dimensions:

waste = excess + #inputs * (feeRate - longterm feeRate)

where excess is the amount that we overshoot the selection target, and the second term derives from how much more expensive it is to spend the inputs right now than we expect in the longterm.

The algorithm now doesn’t stop on the first solution, but continues to search for a solution with a lower waste metric (using that as another bound) until either it has searched all possibilities or runs into the maximum allowed tries.

in src/wallet/coinselection.cpp:83 in 0fb73ae532 outdated

60         if (tries <= 0) { // Too many tries, exit
61-            return false;
62+            break;
63         } else if (value_ret > target_value + cost_of_change) { // Selected value is out of range, go back and try other branch
64             backtrack = true;
65+        } else if (curr_waste > best_waste) { // Don't select things which we know will be more wasteful

Xekyo commented at 11:27 pm on September 30, 2017:

I believe this must be:

curr_waste > best_waste && (fee_vec[depth] - long_term_fee_vec[depth]) > 0

Otherwise, you’d be prematurely stopping when a transaction is created with fees below the long-term fee estimate.

karelbilek commented at 9:15 pm on October 1, 2017:

Maybe I misunderstand what long_term_fee is, but how can it be lower than long term fee estimate? I thought that long term fee looks for confirmation target 1008, thus all smart fee estimates will be only bigger than the long term estimate…

achow101 commented at 8:10 pm on October 2, 2017:

@Xekyo I agree with @runn1ng. I don’t see how the long term fee can be less than the current fee.

in src/wallet/coinselection.cpp:17 in 2ca869b0fa outdated

12+    {
13+        return a.txout.nValue > b.txout.nValue;
14+    }
15+} descending;
16+
17+struct CompareValueOnly

ryanofsky commented at 4:45 pm on October 2, 2017:

In commit “Coin selection function for Branch and Bound coin selection algo”

Maybe drop this and use descending instead of sorting in ascending order and reversing.

achow101 commented at 1:59 am on October 3, 2017:

Done

in src/wallet/coinselection.cpp:167 in 2ca869b0fa outdated

122+    }
123+
124+    return true;
125+}
126+
127+static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const CAmount& nTotalLower, const CAmount& nTargetValue,

ryanofsky commented at 4:57 pm on October 2, 2017:

Note for reviewers: This function is not new, just moved from wallet.cpp.

in src/wallet/coinselection.cpp:11 in 2ca869b0fa outdated

 6+#include "util.h"
 7+#include "utilmoneystr.h"
 8+
 9+// Descending order comparator
10+struct {
11+    bool operator()(CInputCoin a, CInputCoin b) const

ryanofsky commented at 6:16 pm on October 2, 2017:

Here and throughout the PR, probably would be better to pass CInputCoin by const reference to avoid copying the struct. Probably want for (const CInputCoin& utxo : utxo_pool) instead of for (CInputCoin utxo : utxo_pool) as well.

achow101 commented at 1:58 am on October 3, 2017:

Done.

in src/wallet/coinselection.cpp:64 in abf526092a outdated

39+    selection.assign(utxo_pool.size(), std::pair<bool, bool>(false, false));
40+    bool done = false;
41+    bool backtrack = false;
42+
43+    // Sort the utxo_pool
44+    std::sort(utxo_pool.begin(), utxo_pool.end(), descending);

ryanofsky commented at 6:24 pm on October 2, 2017:

Don’t you need to update input_fee_vec and long_term_fee_vec during the sort? Maybe it would be simpler to make input_fee and long_term_fee new fields in CInputCoin.

achow101 commented at 1:59 am on October 3, 2017:

Yeah, I do… I took your suggestion and added fields to CInputCoin for that coin’s fee and long_term_fee values.

in src/wallet/coinselection.cpp:97 in abf526092a outdated

69+                best_selection.assign(selection.begin(), selection.end());
70+                best_waste = curr_waste;
71+            }
72+            curr_waste -= (value_ret - target_value); // Remove the excess value as we will be selecting different coins now
73+            backtrack = true;
74+        } else if (depth >= (int)utxo_pool.size()) { // Reached a leaf node, no solution here

ryanofsky commented at 6:27 pm on October 2, 2017:

Could declare depth as size_t to avoid cast.

achow101 commented at 2:00 am on October 3, 2017:

depth can be negative, so I don’t think I an do that. It is only negative when all branches in the tree are exhausted.

in src/wallet/coinselection.cpp:89 in abf526092a outdated

84+            assert(utxo_pool.at(depth).txout.nValue >= 0);
85+
86+            // Remove this utxo from the lookahead utxo amount
87+            lookahead -= utxo_pool.at(depth).txout.nValue;
88+            // Increase waste
89+            curr_waste += input_fee_vec[depth] - long_term_fee_vec[depth];

ryanofsky commented at 6:28 pm on October 2, 2017:

Could use .at() consistently instead of .at() and []

achow101 commented at 2:00 am on October 3, 2017:

Done.

in src/wallet/fees.cpp:38 in abf526092a outdated

75@@ -76,6 +76,62 @@ CAmount GetMinimumFee(unsigned int nTxBytes, const CCoinControl& coin_control, c
76     return fee_needed;
77 }
78 
79+CFeeRate GetRequiredFeeRate()
80+{
81+    return std::max(CWallet::minTxFee, ::minRelayTxFee);
82+}
83+
84+CFeeRate GetMinimumFeeRate(const CCoinControl& coin_control, const CTxMemPool& pool, const CBlockPolicyEstimator& estimator, FeeCalculation *feeCalc)

ryanofsky commented at 6:38 pm on October 2, 2017:

Should just implement original GetMinimumFee & GetRequiredFee functions in terms of these new feerate functions. Not good to duplicate so much code.

instagibbs commented at 7:04 pm on October 2, 2017:

GetMinimumFee has maxTxFee logic that this doesn’t, so the wrapper would have to include that.

in src/wallet/coinselection.cpp:208 in abf526092a outdated

194+            }
195+        }
196+    }
197+}
198+
199+bool KnapsackSolver(std::vector<CInputCoin>& utxo_pool, const CAmount& nTargetValue, std::set<CInputCoin>& out_set, CAmount& value_ret)

ryanofsky commented at 6:44 pm on October 2, 2017:

Note for reviewers: Again this code is mostly not new. It’s moved from the previous SelectCoinsMinConf implementation in wallet.cpp

in src/wallet/coinselection.h:13 in abf526092a outdated

 8+#include "amount.h"
 9+#include "primitives/transaction.h"
10+#include "random.h"
11+#include "wallet/wallet.h"
12+
13+bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set,

ryanofsky commented at 6:46 pm on October 2, 2017:

This could use a comment saying what the arguments are and what bnb stands for, with maybe a sentence or two describing the algorithm, too.

achow101 commented at 2:00 am on October 3, 2017:

I have added a very long comment describing what this does and the arguments of the function.

ryanofsky commented at 6:56 pm on October 2, 2017: member

Started looking at this. Just some superficial comments so far.

karelbilek commented at 10:27 pm on October 2, 2017: contributor

I tried my javascript simulations with the additional code (the waste comparation) and it actually had slightly worse results (higher total cost)

BUT it might be some bug in the simulation, I don’t have that much time for experimenting right now

karelbilek commented at 10:31 pm on October 2, 2017: contributor

Some simulation that actually test the resulting total fees on a given scenario - similar to @Xekyo repo - but on actual bitcoin binary - would be probably nice. So the testing would be on this code and not on re-implementations.

I am thinking how hard would that be on regtest, with the current python qa testing framework.

achow101 force-pushed on Oct 3, 2017

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

achow101 force-pushed on Nov 30, 2017

achow101 commented at 5:08 pm on November 30, 2017: member

Rebased this.

I’ll try to fix up some of the fee estimation things wrt segwit. @runn1ng I’ll see if I can do any sort of simulation stuff.

karelbilek commented at 7:08 pm on November 30, 2017: contributor

@achow101 I will see what I can do

achow101 force-pushed on Dec 20, 2017

achow101 commented at 6:39 am on December 20, 2017: member

I have rebased this and added a new commit that uses an actual prototype change output and gets its size and spend size instead of hardcoding constants.

I finally have the time to work on simulations for this and will be doing so over the next few weeks. @karel-3d What are the axes of the simulation graphs that you posted earlier?

achow101 commented at 8:37 pm on December 21, 2017: member

See #10637 (comment) for updated results

I figured out how to run simulations with this. https://github.com/achow101/bitcoin/tree/bnb-simulate contains the modifications and script that I am using to simulate the behavior. It uses the test framework to setup 2 nodes. One node will then mine a bunch of blocks and send money to the other node as the scenarios specify. Then the other node will spend from those UTXOs as the scenario specifies. At the end, a bunch of data is printed out.

All of this is done in test/functional/simulate-coinselection.py. Modify that file as necessary if you wan to run simulations.

There is also a modification there to print to the debug.log about whether BnB was used or not. To calculate the BnB usage, grep through the debug.log file. This will require running the simulation with --nocleanup so that the datadir is not removed after it completes.

I simulated BnB and compared that to the current coin selection behavior (cherry-picked the above commit and removed the printing to debug.log part). I used set the following parameters: -dustrelayfee=0 -paytxfee=0.00001000. Setting the dust relay fee to 0 is to allow the dust UTXOs to be added. The transaction fee rate was set to be a fixed 1 sat/byte.

The data from the above simulation is as follows:

type	parameters	final value	mean #UTXO	final #UTXO	#received	#spent	#changes created	min change	max change	mean change	stDev of change	total fees	average fees	fees to spend remaining UTXO	total cost	min input set	max input set	mean size of input set	stdev of input set size	BnB usage
BnB+Core	-dustrelayfee=0 -paytxfee=0.00001000	55.87655934	26.98596647546917637328078853897750377655029296875	32	6097	17925	11860	0.00001974	10.29131674	0.30048583	0.75408013	-0.03577980	-0.0000030168465	-0.00004736000000000000734363958532213700891588814556598663330078125	−0.03582716	1	24	1.511382799325463821560333599336445331573486328125	1.178462287842233724433071984094567596912384033203125	325/11860
Core	-dustrelayfee=0 -paytxfee=0.00001000	55.87654898	28.122459208108256945024550077505409717559814453125	25	6097	17932	11860	0.00011634	10.30079774	0.30304566	0.71006768	-0.03579016	-0.0000030177201	-0.00003700000000000000489018547877861919914721511304378509521484375	−0.03582716	1	20	1.5119730185497470831279542835545726120471954345703125	1.2052006592284258967850973931490443646907806396484375	N/A

The results from this aren’t very impressive, and that’s likely because the BnB algorithm was used for a very small percentage of the coin selections, less than 3%. I will be doing more simulations with different parameters and the other datasets.

achow101 commented at 3:07 am on December 22, 2017: member

See #10637 (comment) for updated results

Another simulation with the same dataset but with a fee of 10 sat/byte instead of 1.

type	parameters	final value	mean #UTXO	final #UTXO	#received	#spent	#changes created	min change	max change	mean change	stDev of change	total fees	average fees	fees to spend remaining UTXO	total cost	min input set	max input set	mean size of input set	stdev of input set size	BnB usage
BnB+Core	-dustrelayfee=0 -paytxfee=0.00010000	55.55449734	26.089714317536337517822175868786871433258056640625	28	6097	17928	11859	0.00005561	10.29687740	0.30032770	0.71982810	-0.35784180	-0.000030172159	-0.0000414400000000000030375528481396685265281121246516704559326171875	-0.35788324	1	22	1.5116357504215851559337124854209832847118377685546875	1.19698986751473679390755933127366006374359130859375	644/11860
Core	-dustrelayfee=0 -paytxfee=0.00010000	55.55436354	29.10074065823912548012231127358973026275634765625	20	6097	17937	11860	0.00024407	10.06245446	0.30415764	0.71372324	-0.35797560	-0.000030183440	-0.000029600000000000001201642951809134274299140088260173797607421875	-0.35800520	1	38	1.5123946037099493810984540687059052288532257080078125	1.2489705008609279790476875859894789755344390869140625	N/A

The difference here is a bit more pronounced, but I’m not quite sure how to interpret this result. @Xekyo, can you comment?

One other thing I noticed is that, with these large datasets and trying to go through them as fast as possible, BnB does take a noticeably longer, but I think that is expected behavior. I don’t expect that to actually have that much of an impact in practice.

achow101 commented at 4:56 pm on December 26, 2017: member

See #10637 (comment) for updated results

I’ve done several more simulations. I did simulations at 4 feerates, 1 sat/byte, 10 sat/byte, 100 sat/byte and 500 sat/byte for the 3 moneypot scenarios provided at https://github.com/Xekyo/CoinSelectionSimulator/tree/master/src/main/resources/scenarios.

Results

Derived-1L-2O scenario

type	parameters	final value	mean #UTXO	final #UTXO	#received	#spent	#changes created	min change	max change	mean change	stDev of change	total fees	average fees	fees to spend remaining UTXO	total cost	min input set	max input set	mean size of input set	stdev of input set size	BnB usage
BnB+Core	-dustrelayfee=0 -paytxfee=0.00001000	55.87655934	26.98596647546917637328078853897750377655029296875	32	6097	17925	11860	0.00001974	10.29131674	0.30048583	0.75408013	-0.03577980	-0.0000030168465	-0.00004736000000000000734363958532213700891588814556598663330078125	−0.03582716	1	24	1.511382799325463821560333599336445331573486328125	1.178462287842233724433071984094567596912384033203125	325/11860
Core	-dustrelayfee=0 -paytxfee=0.00001000	55.87654898	28.122459208108256945024550077505409717559814453125	25	6097	17932	11860	0.00011634	10.30079774	0.30304566	0.71006768	-0.03579016	-0.0000030177201	-0.00003700000000000000489018547877861919914721511304378509521484375	−0.03582716	1	20	1.5119730185497470831279542835545726120471954345703125	1.2052006592284258967850973931490443646907806396484375	N/A
BnB+Core	-dustrelayfee=0 -paytxfee=0.00010000	55.55449734	26.089714317536337517822175868786871433258056640625	28	6097	17928	11859	0.00005561	10.29687740	0.30032770	0.71982810	-0.35784180	-0.000030172159	-0.0000414400000000000030375528481396685265281121246516704559326171875	-0.35788324	1	22	1.5116357504215851559337124854209832847118377685546875	1.19698986751473679390755933127366006374359130859375	644/11860
Core	-dustrelayfee=0 -paytxfee=0.00010000	55.55436354	29.10074065823912548012231127358973026275634765625	20	6097	17937	11860	0.00024407	10.06245446	0.30415764	0.71372324	-0.35797560	-0.000030183440	-0.000029600000000000001201642951809134274299140088260173797607421875	-0.35800520	1	38	1.5123946037099493810984540687059052288532257080078125	1.2489705008609279790476875859894789755344390869140625	N/A
BnB+Core	-dustrelayfee=0 -paytxfee=0.00100000	52.33302714	26.04159937628779886154006817378103733062744140625	23	6097	17934	11860	0.00011400	10.30047400	0.28552710	0.67883573	-3.5793120	-0.00030179696	-0.0000340399999999999993490103211701836016800370998680591583251953125	-3.5793460	1	24	1.512141652613828046725075182621367275714874267578125	1.195222366665799285101456916891038417816162109375	941/11860
Core	-dustrelayfee=0 -paytxfee=0.00100000	52.33243514	27.071559837389319369549411931075155735015869140625	19	6097	17938	11860	0.00010535	10.28757400	0.30504525	0.74629238	-3.5799040	-0.00030184688	-0.0000281200000000000018191871620221178318388410843908786773681640625	-3.5799321	1	28	1.51247892074198997391931698075495660305023193359375	1.2096651387256158738381373041193000972270965576171875	N/A
BnB+Core	-dustrelayfee=0 -paytxfee=0.00500000	38.01520914	24.4216739989976048263997654430568218231201171875	21	6097	17935	11859	0.00014570	10.29057000	0.30445610	0.71189306	-17.897130	-0.0015090329	-0.0000310800000000000005840987415961507167594390921294689178466796875	-17.897161	1	28	1.512225969645868417501333169639110565185546875	1.22346107662681991001818460063077509403228759765625	1616/11860
Core	-dustrelayfee=0 -paytxfee=0.00500000	38.01503914	25.713816339032131708108863676898181438446044921875	22	6097	17935	11860	0.00002000	10.10057000	0.30062341	0.74949322	-17.897300	-0.0015090472	-0.0000325600000000000067428181094175698717663181014358997344970703125	-17.897333	1	21	1.512225969645868417501333169639110565185546875	1.1709164727486285340063432158785872161388397216796875	N/A

derived-balanced.csv

type	parameters	final value	mean #UTXO	final #UTXO	#received	#spent	#changes created	min change	max change	mean change	stDev of change	total fees	average fees	fees to spend remaining UTXO	total cost	min input set	max input set	mean size of input set	stdev of input set size	BnB usage
BnB+Core	-dustrelayfee=0 -paytxfee=0.00001000	55.86752542	35.59017211274632330741951591335237026214599609375	29	12194	24022	11857	0.00000215	9.71099774	0.10588343	0.35890007	-0.04481372	-0.0000037785599	-0.0000429200000000000091962722159610876815349911339581012725830078125	-0.044856640	1	66	2.025463743676222616585391733678989112377166748046875	1.88707038897768342167182709090411663055419921875	923/11860
Core	-dustrelayfee=0 -paytxfee=0.00001000	55.86752212	39.19668246445497317154149641282856464385986328125	27	12194	24026	11859	0.00002149	8.74523932	0.10870898	0.36959846	-0.04481702	-0.0000037788381	-0.000039960000000000003655097058352652084067813120782375335693359375	-0.044856980	1	51	2.0258010118043845437796335318125784397125244140625	1.8630510400609858745468727647676132619380950927734375	N/A
BnB+Core	-dustrelayfee=0 -paytxfee=0.00010000	55.46426454	35.07499792134364469120555440895259380340576171875	28	12194	24025	11859	0.00002982	8.74521898	0.10850152	0.36248967	-0.44807460	-0.000037780320	-0.0000414400000000000030375528481396685265281121246516704559326171875	-0.44811604	1	35	2.025716694772344173003375544794835150241851806640625	1.740747319921828850652900655404664576053619384765625	1643/11860
Core	-dustrelayfee=0 -paytxfee=0.00010000	55.46419054	35.0832294005155063132406212389469146728515625	23	12194	24030	11859	0.00003200	9.91097740	0.11858778	0.38233123	-0.44814860	-0.000037786560	-0.0000340399999999999993490103211701836016800370998680591583251953125	-0.44818264	1	38	2.026138279932546470973875329946167767047882080078125	1.842291519120082821103778769611380994319915771484375	N/A
BnB+Core	-dustrelayfee=0 -paytxfee=0.00100000	51.43235175	35.5221169036334885049654985778033733367919921875	31	12194	24020	11857	0.00004084	9.27206431	0.11038883	0.36045124	-4.4799874	-0.00037773924	-0.000045880000000000001184920217500717853909009136259555816650390625	-4.4800333	1	38	2.025295109612141430943665909580886363983154296875	1.7907297866116194118291105041862465441226959228515625	2134/11860
Core	-dustrelayfee=0 -paytxfee=0.00100000	51.43111514	37.87802444499875065275773522444069385528564453125	26	12194	24028	11860	0.00012800	9.70077400	0.11358164	0.40684568	-4.4812240	-0.00037784351	-0.00003847999999999999749637769053123292906093411147594451904296875	-4.4812625	1	33	2.02596964586846528533214950584806501865386962890625	1.7820345960584622613254168754792772233486175537109375	N/A
BnB+Core	-dustrelayfee=0 -paytxfee=0.00500000	33.50870001	36.51820902968321291837128228507936000823974609375	21	12194	24026	11853	0.00002322	9.98787000	0.14353057	0.48030423	-22.403639	-0.0018890083	-0.0000310800000000000005840987415961507167594390921294689178466796875	-22.403670	1	53	2.0258010118043845437796335318125784397125244140625	1.91765082261940023045099223963916301727294921875	2713/11860
Core	-dustrelayfee=0 -paytxfee=0.00500000	35.10512145	40.9802935184800247725434019230306148529052734375	21	12194	24030	11857	0.00006718	8.81134658	0.13437727	0.44562374	-22.407218	-0.0018894694	-0.0000310800000000000005840987415961507167594390921294689178466796875	-22.407249	1	80	2.026309132304578763950075881439261138439178466796875	1.9456650214443909074901739586493931710720062255859375	N/A

moneypot.csv

type	parameters	final value	mean #UTXO	final #UTXO	#received	#spent	#changes created	min change	max change	mean change	stDev of change	total fees	average fees	fees to spend remaining UTXO	total cost	min input set	max input set	mean size of input set	stdev of input set size	BnB usage
BnB+Core	-dustrelayfee=0 -paytxfee=0.00001000	55.84951848	153.250165526373876900834147818386554718017578125	47	24388	36196	11855	0.00000262	4.99989478	0.045543204	0.21246908	-0.06282066	-0.0000052968516	-0.00006956000000000000485674001016178635836695320904254913330078125	-0.062890220	1	188	3.051939291736931014753508861758746206760406494140625	3.731750776560500693079802658758126199245452880859375	2627/11860
Core	-dustrelayfee=0 -paytxfee=0.00001000	55.84950297	208.239654601633191077780793420970439910888671875	49	24388	36190	11851	0.00000275	8.80499774	0.052897153	0.26685217	-0.06283617	-0.0000052981594	-0.000072520000000000003621651589735819243287551216781139373779296875	-0.062908690	1	400	3.051433389544687901917541239527054131031036376953125	5.65198237497643418691950500942766666412353515625	N/A
BnB+Core	-dustrelayfee=0 -paytxfee=0.00010000	55.28410854	147.34928823659237195897730998694896697998046875	37	24388	36195	11844	0.00002542	5.64857740	0.047474642	0.20586621	-0.62823060	-0.000052970540	-0.0000547600000000000042559185342572192212173831649124622344970703125	-0.62828536	1	182	3.051854974704890199888041024678386747837066650390625	3.549240546499367265909086199826560914516448974609375	3713/11860
Core	-dustrelayfee=0 -paytxfee=0.00010000	55.28405942	106.5413815934672214780221111141145229339599609375	43	24388	36197	11852	0.00002260	9.20997740	0.055779091	0.26602465	-0.62827972	-0.000052974681	-0.00006364000000000000732691685101372058852575719356536865234375	-0.62834336	1	92	3.0520236087689713855297668487764894962310791015625	3.277647281760728059651910371030680835247039794921875	N/A
BnB+Core	-dustrelayfee=0 -paytxfee=0.00100000	49.63267114	92.6900518649304814289280329830944538116455078125	34	24388	36186	11832	0.00002600	5.64837400	0.053024521	0.21690243	-6.2796680	-0.00052948297	-0.000050320000000000006108551164896169893836486153304576873779296875	-6.2797183	1	94	3.0510961214165259747232994413934648036956787109375	3.337635756349500493200821438222192227840423583984375	4111/11860
Core	-dustrelayfee=0 -paytxfee=0.00100000	49.63307290	146.35864047671594789790106005966663360595703125	50	24388	36180	11842	0.00002325	9.50585100	0.069900583	0.29034538	-6.2792663	-0.00052944910	-0.0000740000000000000097803709575572383982944302260875701904296875	-6.2793403	1	286	3.050590219224283305976541669224388897418975830078125	4.2989677473115310846196734928525984287261962890625	N/A
BnB+Core	-dustrelayfee=0 -paytxfee=0.00500000	25.79221870	86.052558973651542828520177863538265228271484375	22	24388	36168	11802	0.00005563	8.78387000	0.092277784	0.36701418	-31.364976	-0.0026452708	-0.0000325600000000000067428181094175698717663181014358997344970703125	-31.365009	1	155	3.0503500042169182648876812891103327274322509765625	3.72297890817267340679563858429901301860809326171875	4752/11860
Core	-dustrelayfee=0 -paytxfee=0.00500000	28.75267541	109.5738998482549249047224293462932109832763671875	31	24388	36179	11822	0.00002650	9.99457000	0.090254682	0.36953598	-31.391428	-0.0026475017	-0.000045880000000000001184920217500717853909009136259555816650390625	-31.391474	1	119	3.05127772623766535531331101083196699619293212890625	3.444553377559158580112352865398861467838287353515625	N/A

achow101 force-pushed on Jan 11, 2018

achow101 commented at 7:45 pm on January 11, 2018: member

Rebased

karelbilek commented at 1:06 pm on January 16, 2018: contributor

@achow101 the axes are - X is how “tight” the target is - by which I mean, I took the cost of change and I multiplied it by a factor. So I took cost of change just X% of the cost in the original algorithm.

Y is total cost from Murch thesis (what is spent + what it costs to spend the resulting utxos).

Btw. I wrote @Xekyo it would be nice to make a BIP with this algorithm, so we don’t have to write “Murch algorithm” and have the algorithm specified as a BIP. (There are already BIPs that don’t describe the protocol, just wallet behaviour.)

achow101 force-pushed on Jan 19, 2018

achow101 commented at 6:13 pm on January 22, 2018: member

See #10637 (comment) for updated results

I have done some more simulations, this time with a variable fee rate. The fee data I am using is pulled from https://bitcoinfees.info/. The fee files are available here.

There are two fee things, one of them has each fee rate repeated 8 times in a row, the other cycles through the list 8 times.

Results:

Derived-1L-2O scenario

type	parameters	final value	mean #UTXO	final #UTXO	#received	#spent	#changes created	min change	max change	mean change	stDev of change	total fees	average fees	fees to spend remaining UTXO	total cost	min input set	max input set	mean size of input set	stdev of input set size	BnB usage
BnB+Core Repeated Fees	-dustrelayfee=0	55.88712998	27.311299214790889067216994590125977993011474609375	28	6097	17927	11858	0.00019834	10.26679834	0.29848546	0.70127884	-0.02520916	-0.0000021255616	-0.0000414400000000000030375528481396685265281121246516704559326171875	-0.025250600	0	24	1.5115514333895447851574544984032399952411651611328125	1.201771518003559524601087105111218988895416259765625	344/11860
Core Repeated Fees	-dustrelayfee=0	55.88712329	27.506097900540179779227401013486087322235107421875	22	6097	17935	11860	0.00001005	10.30069834	0.29223202	0.72740965	-0.02521585	-0.0000021261256	-0.0000325600000000000067428181094175698717663181014358997344970703125	-0.025248410	1	21	1.512225969645868417501333169639110565185546875	1.2032374476285958575516588098253123462200164794921875	N/A
BnB+Core Cyclic Fees	-dustrelayfee=0	55.88712420	25.80497855989307964819090557284653186798095703125	23	6097	17934	11860	0.00001491	10.29169834	0.30822553	0.72970119	-0.02521494	-0.0000021260489	-0.0000340399999999999993490103211701836016800370998680591583251953125	-0.025248980	1	24	1.512141652613828046725075182621367275714874267578125	1.1820983771402058248867206202703528106212615966796875	199/11860
Core Cyclic Fees	-dustrelayfee=0	55.88712420	26.8401737483989535348882782272994518280029296875	23	6097	17934	11860	0.00002034	10.30069834	0.28121957	0.65214921	-0.02521494	-0.0000021260489	-0.0000340399999999999993490103211701836016800370998680591583251953125	-0.025248980	1	21	1.512141652613828046725075182621367275714874267578125	1.1730758242556362791475521589745767414569854736328125	N/A

derived-balanced.csv

type	parameters	final value	mean #UTXO	final #UTXO	#received	#spent	#changes created	min change	max change	mean change	stDev of change	total fees	average fees	fees to spend remaining UTXO	total cost	min input set	max input set	mean size of input set	stdev of input set size	BnB usage
BnB+Core Repeated Fees	-dustrelayfee=0	55.88157487	35.741664588010308989396435208618640899658203125	30	12194	24023	11859	0.00000275	9.98089834	0.10155991	0.34103056	-0.03076427	-0.0000025939519	-0.0000444000000000000018024644277137014114487101323902606964111328125	-0.030808670	1	34	2.02554806070826298736164972069673240184783935546875	1.7797442458699201939253953241859562695026397705078125	794/11860
Core Repeated Fees	-dustrelayfee=0	55.88158139	37.7370915440259437900749617256224155426025390625	29	12194	24025	11860	0.00030847	9.96073034	0.10688567	0.34970815	-0.03075775	-0.0000025934022	-0.0000429200000000000091962722159610876815349911339581012725830078125	-0.030800670	1	32	2.025716694772344173003375544794835150241851806640625	1.7385175900032934226402403510292060673236846923828125	N/A
BnB+Core Cyclic Fees	-dustrelayfee=0	55.88157262	36.30227820736676136448295437730848789215087890625	27	12194	24024	11857	0.00001834	9.30095665	0.10794268	0.37209381	-0.03076652	-0.0000025941417	-0.000039960000000000003655097058352652084067813120782375335693359375	-0.030806480	0	35	2.025632377740303358137907707714475691318511962890625	1.7570214448414578356505444389767944812774658203125	833/11860
Core Cyclic Fees	-dustrelayfee=0	55.88158048	36.26091294587178737174326670356094837188720703125	28	12194	24026	11860	0.00006546	9.91069834	0.12069723	0.41430597	-0.03075866	-0.0000025934789	-0.0000414400000000000030375528481396685265281121246516704559326171875	-0.030800100	1	44	2.0258010118043845437796335318125784397125244140625	1.8367955156429862650924178524292074143886566162109375	N/A

moneypot.csv

type	parameters	final value	mean #UTXO	final #UTXO	#received	#spent	#changes created	min change	max change	mean change	stDev of change	total fees	average fees	fees to spend remaining UTXO	total cost	min input set	max input set	mean size of input set	stdev of input set size	BnB usage
BnB+Core Repeated Fees	-dustrelayfee=0	55.87052207	225.20704590598103322918177582323551177978515625	57	24388	36177	11846	0.00000241	7.99999834	0.044079288	0.20855531	-0.04181707	-0.0000035258912	-0.000084359999999999998681297908031950782969943247735500335693359375	-0.041901430	1	382	3.050337268128161749558557858108542859554290771484375	5.099606130292382744073620415292680263519287109375	2280/11860
Core Repeated Fees	-dustrelayfee=0	55.87047548	208.39872544692121891785063780844211578369140625	29	24388	36214	11855	0.00001333	7.99999834	0.055334876	0.25061846	-0.04186366	-0.0000035298196	-0.0000429200000000000091962722159610876815349911339581012725830078125	-0.041906580	1	668	3.053456998313659465082992028328590095043182373046875	7.0470460073749308094193111173808574676513671875	N/A
BnB+Core Cyclic Fees	-dustrelayfee=0	55.87051115	178.7087563451776759393396787345409393310546875	45	24388	36189	11846	0.00000241	5.51999834	0.043100286	0.20021529	-0.04182799	-0.0000035268120	-0.000066600000000000006091828430587753473446355201303958892822265625	-0.041894590	1	451	3.05134907251264753114128325250931084156036376953125	5.24464904178873769780011571128852665424346923828125	2295/11860
Core Cyclic Fees	-dustrelayfee=0	55.87049772	218.065603619510028465811046771705150604248046875	49	24388	36197	11858	0.00000184	9.20999834	0.046778658	0.22037920	-0.04184142	-0.0000035279444	-0.000072520000000000003621651589735819243287551216781139373779296875	-0.041913940	1	338	3.0520236087689713855297668487764894962310791015625	5.70017745838109579636920898337848484516143798828125	N/A

achow101 force-pushed on Jan 26, 2018

achow101 commented at 3:16 am on January 26, 2018: member

So apparently there was a bug that was allowing change to still be made even with BnB. The latest commit should fix this, and I think that will significantly change the simulation results.

Xekyo commented at 7:21 pm on January 26, 2018: member

There is a mismatch here with the “#changes created” and “BnB usage”. Every time you use BnB, there should no change be created. I would suspect that the “excess” from BnB is not being dropped to the benefits of the fees, but instead put into a change output?

Edit: oh, saw your comment upon send. Good, curious about new results!

achow101 force-pushed on Jan 29, 2018

achow101 commented at 5:27 pm on February 4, 2018: member

See #10637 (comment) for updated results

Here are the new simulation results with all of the bugs fixed hopefully:

Fees file	Simulation File	final value	total sent	total deposited	mean #UTXO	final #UTXO	#received	#spent	#payments sent	#changes created	min change	max change	mean change	stDev of change	total fees	average fees	fees to spend remaining UTXO	total cost	min input set	max input set	mean size of input set	stdev of input set size	BnB Usage
fees-bitcoinfees-info-repeats.csv	derived-1I-2O.csv	55.88713405	-2484.3994	2540.3143409799973	19.85849529431419568936689756810665130615234375	17	6097	17913	11860	11833	0.00997809	4.15153434	0.10399897	0.28233767	-0.02520509	-0.0000021252184	-0.0000251600000000000030542755824480849469182430766522884368896484375	-0.025230250	1	24	1.510370994940978039977608204935677349567413330078125	1.0410142316722097444170458402368240058422088623046875	27/11860
fees-bitcoinfees-info-repeats.csv	derived-balanced.csv	55.88171750	-2484.3994	2540.3143409799864	27.267855658102600813208482577465474605560302734375	21	12194	23840	11860	11667	0.00221449	5.69999834	0.056819638	0.19930147	-0.03062164	-0.0000025819258	-0.0000310800000000000005840987415961507167594390921294689178466796875	-0.030652720	1	84	2.010118043844856483559624393819831311702728271484375	1.8262218049879537229429615763365291059017181396484375	193/11860
fees-bitcoinfees-info-repeats.csv	moneypot.csv	55.87130774	-2484.3994	2540.314340979981	131.06436217170602276382851414382457733154296875	33	24388	35121	11860	10766	0.00005428	4.69999834	0.036069275	0.13266262	-0.04103140	-0.0000034596459	-0.00004883999999999999994983179707475073882960714399814605712890625	-0.041080240	1	279	2.96129848229342318433054970228113234043121337890625	4.20967084360116938768214822630397975444793701171875	1094/11860
fees-bitcoinfees-info-cycle.csv	derived-1I-2O.csv	55.88713391	-2484.3994	2540.3143409799973	22.934844350392605605293283588252961635589599609375	19	6097	17909	11860	11831	0.00998908	9.14499834	0.10465966	0.28952080	-0.02520523	-0.0000021252302	-0.0000281200000000000018191871620221178318388410843908786773681640625	-0.025233350	0	27	1.5100337268128161127833664068020880222320556640625	1.05932493680624073562057674280367791652679443359375	28/11860
fees-bitcoinfees-info-cycle.csv	derived-balanced.csv	55.88173059	-2484.3994	2540.3143409799864	28.776419722291510794320856803096830844879150390625	20	12194	23831	11860	11657	0.00223019	5.69999834	0.056200963	0.19728515	-0.03060855	-0.0000025808221	-0.000029600000000000001201642951809134274299140088260173797607421875	-0.030638150	1	45	2.00935919055649225839488281053490936756134033203125	1.7222609388141678632422326700179837644100189208984375	203/11860
fees-bitcoinfees-info-cycle.csv	moneypot.csv	55.87119478	-2484.3994	2540.314340979981	64.370503200176557356826378963887691497802734375	29	24388	35312	11860	10953	0.00015309	4.69999834	0.035168758	0.12918029	-0.04114436	-0.0000034691703	-0.0000429200000000000091962722159610876815349911339581012725830078125	-0.041187280	1	92	2.977403035413153542521058625425212085247039794921875	2.898949450951935347120524966157972812652587890625	907/11860

achow101 force-pushed on Feb 4, 2018

instagibbs commented at 2:16 pm on February 5, 2018: member

@achow101 can you label the rows?

achow101 commented at 3:36 pm on February 5, 2018: member

@instagibbs They’re all BnB simulations. I moved the fees file and simulations file fields to the left (they were on the right side originally).

Xekyo commented at 0:08 am on February 15, 2018: member

@achow101: Row 4 has “min input set” of 0, but a transaction must have at least one input. Why do you think did the BnB usage almost halve? Are you using the solution of the RandomSelector if it has a lower waste metric? Otherwise, I’d expect the BnB usage to increase with higher fees since the target window for a solution without a change output increases.

The minChange of 0.00005428 also seems oddly low. Did the wallet balance dip to zero in your simulation?

I’ve had another idea for an optimization of the exploration: We see a lot of unspent values duplicated at round figures (e.g. 0.1 BTC, 10,000 sats). When exploring the combination tree, we should never allow a second branch to place the same value in the same position.

E.g. before, when you would have the unspent set of one UTXO with 1,000,000 and 100 UTXO with 100,000, and are looking for a target of 1,150,000, you’d explore: 1,000,000 /
100,000(A) /
0 100,000(B) —–> Σ=1,200,000 –> too much, cut branch
100,000(C) —–> Σ=1,200,000 –> too much, cut branch … and once you’ve tried all 99 other 100 with 100,000(A), you’d try the remaining 98 100,000s with 100,000(B) and so forth.

If we don’t allow expanding a branch that has the same value at the same position this becomes:

1,000,000 /
| 100,000(A) | /
| 0 100,000(B) —–> Σ=1,200,000 –> too much, cut branch |
| 100,000(C-CV) —–> don’t expand, already considered 100,000 in combo with this 0th and 1st | 100,000(B-CV) —–> don’t expand, already considered 100,000 in combo with this 0th Done, no solution.

In practice this could be implemented by remembering the value of the last item that we backtracked from and requiring that any new UTXO we consider for that position is at least one satoshi smaller.

achow101 commented at 3:04 am on February 15, 2018: member

Row 4 has “min input set” of 0, but a transaction must have at least one input.

That’s strange. I’ll rerun that simulation.

Why do you think did the BnB usage almost halve?

I think that’s a consequence of the bug I fixed. The BnB usage in the previous simulations was the number of times that BnB was hit, but BnB wasn’t actually used for the actual coin selection; the normal normal coin selector was used. So some inputs weren’t actually consumed, and additional change outputs were created which would then allow for more hits with BnB as there are more UTXOs.

Are you using the solution of the RandomSelector if it has a lower waste metric

No, the random selector is not implemented yet.

The minChange of 0.00005428 also seems oddly low. Did the wallet balance dip to zero in your simulation?

I believe it did. Such low values of min change do line up with the min change values for the normal coin selector though.

When exploring the combination tree, we should never allow a second branch to place the same value in the same position.

We still need to take into account the waste though; two outputs with the same effective value could still have different waste values which may make one output more desireable than another even with the same values. When we backtrack, we aren’t always cutting off a branch; we could have backtracked in order to find something else with a lower waste value.

achow101 commented at 6:56 pm on February 15, 2018: member

See #10637 (comment) for updated results

@Xekyo These are the new results for that one simulation. I think that was just a spurious error:

Fees file	Simulation File	final value	total sent	total deposited	mean #UTXO	final #UTXO	#received	#spent	#payments sent	#changes created	min change	max change	mean change	stDev of change	total fees	average fees	fees to spend remaining UTXO	total cost	min input set	max input set	mean size of input set	stdev of input set size	BnB Usage
fees-bitcoinfees-info-cycle.csv	derived-1I-2O.csv	55.88713708	-2484.3994	2540.3143409799973	20.622487052402963314534645178355276584625244140625	19	6097	17905	11860	11827	0.00999239	9.14499834	0.10454406	0.29314873	-0.02520206	-0.0000021249629	-0.0000281200000000000018191871620221178318388410843908786773681640625	-0.025230180	1	27	1.5096964586846544076337295336998067796230316162109375	1.0713591908561592713766685847076587378978729248046875	33/11860

achow101 commented at 7:43 pm on March 5, 2018: member

All of the valid results for varying fee rate simulations, but readable

Type	Fees file	Simulation File	final value	mean #UTXO	final #UTXO	#received	#spent	#changes created	min change	max change	mean change	stDev of change	total fees	average fees	total cost	min input set	max input set	mean size of input set	stdev of input set size	BnB Usage
BnB+Core	fees-bitcoinfees-info-repeats.csv	derived-1I-2O.csv	55.88713405	19.86	17	6097	17913	11833	0.00997809	4.15153434	0.10399897	0.28233767	-0.02520509	-0.00000213	-0.02523025	1	24	1.51	1.04	27/11860
Core	fees-bitcoinfees-info-repeats.csv	derived-1I-2O.csv	55.88712329	27.51	22	6097	17935	11860	0.00001005	10.30069834	0.29223202	0.72740965	-0.02521585	-0.00000213	-0.02524841	1	21	1.51	1.20	N/A
BnB+Core	fees-bitcoinfees-info-cycle.csv	derived-1I-2O.csv	55.88713391	22.93	19	6097	17909	11831	0.00998908	9.14499834	0.10465966	0.28952080	-0.02520523	-0.00000213	-0.02523335	0	27	1.51	1.05	28/11860
Core	fees-bitcoinfees-info-cycle.csv	derived-1I-2O.csv	55.88712420	26.84	23	6097	17934	11860	0.00002034	10.30069834	0.28121957	0.65214921	-0.02521494	-0.00000213	-0.02524898	1	21	1.51	1.17	N/A
BnB+Core	fees-bitcoinfees-info-repeats.csv	derived-balanced.csv	55.88171750	27.27	21	12194	23840	11667	0.00221449	5.69999834	0.056819638	0.19930147	-0.03062164	-0.00000258	-0.03065272	1	84	2.01	1.83	193/11860
Core	fees-bitcoinfees-info-repeats.csv	derived-balanced.csv	55.88158139	37.74	29	12194	24025	11860	0.00030847	9.96073034	0.10688567	0.34970815	-0.03075775	-0.00000259	-0.03080067	1	32	2.03	1.74	N/A
BnB+Core	fees-bitcoinfees-info-cycle.csv	derived-balanced.csv	55.88173059	28.78	20	12194	23831	11657	0.00223019	5.69999834	0.056200963	0.19728515	-0.03060855	-0.00000258	-0.03063815	1	45	2.01	1.72	203/11860
Core	fees-bitcoinfees-info-cycle.csv	derived-balanced.csv	55.88158048	36.26	28	12194	24026	11860	0.00006546	9.91069834	0.12069723	0.41430597	-0.03075866	-0.00000259	-0.03080010	1	44	2.026	1.84	N/A
BnB+Core	fees-bitcoinfees-info-repeats.csv	moneypot.csv	55.87130774	131.06	33	24388	35121	10766	0.00005428	4.69999834	0.036069275	0.13266262	-0.04103140	-0.00000346	-0.04108024	1	279	2.96	4.20	1094/11860
Core	fees-bitcoinfees-info-repeats.csv	moneypot.csv	55.87047548	208.40	29	24388	36214	11855	0.00001333	7.99999834	0.055334876	0.25061846	-0.04186366	-0.00000353	-0.04190658	1	668	3.05	7.05	N/A
BnB+Core	fees-bitcoinfees-info-cycle.csv	moneypot.csv	55.87119478	64.37	29	24388	35312	10953	0.00015309	4.69999834	0.035168758	0.12918029	-0.04114436	-0.00000347	-0.04118728	1	92	2.98	2.90	907/11860
Core	fees-bitcoinfees-info-cycle.csv	moneypot.csv	55.87049772	218.06	49	24388	36197	11858	0.00000184	9.20999834	0.046778658	0.22037920	-0.04184142	-0.00000353	-0.04191394	1	338	3.05	5.70	N/A

Xekyo commented at 8:42 pm on March 5, 2018: member

We still need to take into account the waste though; two outputs with the same effective value could still have different waste values which may make one output more desireable than another even with the same values. When we backtrack, we aren’t always cutting off a branch; we could have backtracked in order to find something else with a lower waste value.

Okay: We should not allow two outputs with the same effective value and same waste. I guess that would mean that we should potentially sort the UTXO for BnB by effective value first and then by waste.

in src/wallet/coinselection.cpp:1 in 6d4586d130 outdated

0@@ -0,0 +1,300 @@
1+// Copyright (c) 2012-2016 The Bitcoin Core developers

Xekyo commented at 8:49 pm on March 5, 2018:

Just curious, why 2012-2016?

achow101 commented at 10:50 pm on March 5, 2018:

Changed to 2017

in src/wallet/coinselection.cpp:13 in 6d4586d130 outdated

 8+
 9+// Descending order comparator
10+struct {
11+    bool operator()(const CInputCoin& a, const CInputCoin& b) const
12+    {
13+        return a.txout.nValue > b.txout.nValue;

Xekyo commented at 8:50 pm on March 5, 2018:

We may need to additionally sort by waste here.

achow101 commented at 10:45 pm on March 5, 2018:

Why?

Xekyo commented at 6:13 pm on March 6, 2018:

Withdrawn after personal conversation.

instagibbs commented at 7:08 pm on March 6, 2018:

waste is a tie-breaker or a short-circuit. Shouldn’t need it.

in src/wallet/coinselection.cpp:22 in 6d4586d130 outdated

17+/*
18+ * This is the Branch and Bound Coin Selection algorithm designed by Mark Erhardt. It is an exact match algorithm where the exact match
19+ * is a range with the lower bound being the value we want to spend and the upper bound being that value plus the additional cost
20+ * required to create and spend a change output. To do this, the algorithm builds a binary tree where each node is a UTXO and whether
21+ * that UTXO is included or not in the current coin selection. The tree is searched in include-first order. Each UTXO is first included
22+ * and the current selection is evaluated for whether it is within the current threshold. If it is over the threshold, we try excluding

Xekyo commented at 9:01 pm on March 5, 2018:

“within the current threshold” -> within the target range?

achow101 commented at 10:50 pm on March 5, 2018:

Fixed

in src/wallet/coinselection.cpp:41 in 6d4586d130 outdated

31+ * An additional optimization of this algorithm implemented here is a lookahead value which maintains the total value of the UTXO set
32+ * of all unexplored UTXOs (i.e. UTXOs that have not yet been included or excluded). This allows us to cut a branch if the remaining
33+ * amount is not sufficient to reach our target.
34+ *
35+ * SelectCoinsBnB Arguments:
36+ * const std::vector<CInputCoin>& utxo_pool -> The set of UTXOs that we are choosing from. These UTXOs will be sorted in descending order

Xekyo commented at 9:12 pm on March 5, 2018:

Nit: descending order by what metric ;)

achow101 commented at 10:50 pm on March 5, 2018:

fixed

achow101 force-pushed on Mar 5, 2018

in src/wallet/coinselection.cpp:96 in c2e2db1806 outdated

79+        if (remaining_tries <= 0) { // Too many tries, exit
80+            break;
81+        } else if (value_ret > target_value + cost_of_change) { // Selected value is out of range, go back and try other branch
82+            backtrack = true;
83+        } else if (curr_waste > best_waste) { // Don't select things which we know will be more wasteful
84+            backtrack = true;

Xekyo commented at 10:07 pm on March 5, 2018:

Do we have a test that checks whether this behaves correctly for fee rates below the longterm expected fee rate? (I seem to remember that we discussed that before, and we came to the conclusion that it is correct, but if we had a test I’d be more comfortable.)

in src/wallet/coinselection.cpp:156 in c2e2db1806 outdated

150+    if (best_selection.empty()) {
151+        return false;
152+    }
153+
154+    // Set output set
155+    value_ret = 0;

Xekyo commented at 10:16 pm on March 5, 2018:

Why are you recalculating value_ret, when you’ve been tracking it above before?

achow101 commented at 10:48 pm on March 5, 2018:

The value_ret above is not necessarily our best set. It is used for tracking our work during the selection so it may not actually be the value for the selection we want to use. It should probably be a different variable.

Xekyo commented at 4:08 pm on March 6, 2018:

Yeah, let’s make it two different variables with clear names.

in src/wallet/fees.cpp:25 in c2e2db1806 outdated

19@@ -20,6 +20,22 @@ CAmount GetRequiredFee(unsigned int nTxBytes)
20 
21 
22 CAmount GetMinimumFee(unsigned int nTxBytes, const CCoinControl& coin_control, const CTxMemPool& pool, const CBlockPolicyEstimator& estimator, FeeCalculation *feeCalc)
23+{
24+    CAmount fee_needed = GetMinimumFeeRate(coin_control, pool, estimator, feeCalc).GetFee(nTxBytes);
25+    // Aalways obey the maximum

Xekyo commented at 10:23 pm on March 5, 2018:

typo: Aalways

Note to self, got up to here.

achow101 commented at 10:50 pm on March 5, 2018:

Fixed

achow101 force-pushed on Mar 5, 2018

achow101 force-pushed on Mar 6, 2018

in src/wallet/coinselection.cpp:56 in 859160cfdb outdated

51+    if (utxo_pool.empty()) {
52+        return false;
53+    }
54+
55+    int depth = 0;
56+    int remaining_tries = 100000;

instagibbs commented at 7:11 pm on March 6, 2018:

this should be a constant

achow101 commented at 7:59 pm on March 6, 2018:

It can’t be a constant because it is being decremented.

instagibbs commented at 8:03 pm on March 6, 2018:

I meant static constant, but meh

in src/wallet/coinselection.cpp:37 in 859160cfdb outdated

32+ * of all unexplored UTXOs (i.e. UTXOs that have not yet been included or excluded). This allows us to cut a branch if the remaining
33+ * amount is not sufficient to reach our target.
34+ *
35+ * SelectCoinsBnB Arguments:
36+ * const std::vector<CInputCoin>& utxo_pool -> The set of UTXOs that we are choosing from. These UTXOs will be sorted in descending order
37+ *                                             by value and the CInputCoins' values are their effective values.

instagibbs commented at 7:14 pm on March 6, 2018:

just say effective value again to clear up ambiguity.

achow101 commented at 8:02 pm on March 6, 2018:

Fixed

in src/wallet/coinselection.cpp:83 in 859160cfdb outdated

78+    {
79+        if (remaining_tries <= 0) { // Too many tries, exit
80+            break;
81+        } else if (value_track + lookahead < target_value) { // Cannot possibly reach target with the amount remaining in the lookahead.
82+            // This also catches if we are at a leaf node and still have not met the target value
83+            if (depth == 0) { // At the first utxo, no possible selections, so exit

instagibbs commented at 7:52 pm on March 6, 2018:

This should just be a check after calculating the original value. Has no additional checking power here.

achow101 commented at 8:03 pm on March 6, 2018:

Removed. Also compacted the next 2 else ifs with this one to make one large else if with or.

achow101 force-pushed on Mar 6, 2018

in src/wallet/coinselection.cpp:113 in 235da3d4ec outdated

108+            --depth;
109+
110+            // Walk backwards to find the first utxo which has not has its second branch traversed
111+            while (!selection.at(depth)) {
112+                selection.at(depth) = false;
113+                selection.at(depth) = false;

morcos commented at 8:24 pm on March 6, 2018:

duplicate of prior line

morcos commented at 8:32 pm on March 6, 2018:

actually can remove both of these, selection.at(depth) is already false.

in src/wallet/coinselection.cpp:113 in bf280e4659 outdated

108+            --depth;
109+
110+            // Walk backwards to find the first utxo which has not has its second branch traversed
111+            while (!selection.at(depth)) {
112+                selection.at(depth) = false;
113+                selection.at(depth) = false;

Xekyo commented at 8:37 pm on March 6, 2018:

duplicate line

achow101 force-pushed on Mar 6, 2018

in src/wallet/coinselection.cpp:111 in 235da3d4ec outdated

106+        if (backtrack) {
107+            backtrack = false; // Reset
108+            --depth;
109+
110+            // Walk backwards to find the first utxo which has not has its second branch traversed
111+            while (!selection.at(depth)) {

morcos commented at 8:38 pm on March 6, 2018:

I’m not loving the way we track depth, it gets a bit confusing to make sure it stays in bounds. I don’t know if it’s possible to hit in practice, but if you are trying to pay 0 total value, then you’ll end up here trying to do selection.at(-1).

achow101 commented at 8:52 pm on March 6, 2018:

I agree, but we shouldn’t have a 0 value target in practice. I could just add a check to make sure that depth is greater than 0 before decrementing it.

morcos commented at 10:18 pm on March 6, 2018:

yeah we should do something. maybe change while loop to: while (depth >= 0 && !selection.at(depth)) { and then take the if (depth < 0) check out of the while loop and put it afterwards, and then it’s

0if (depth < 0) {
1    done = true;
2}
3else { 
4...
5}

and then you can get rid of the if (!done) and in fact you could actually break instead of setting done=true and get rid of done and have the while loop be a for loop over remaining tries instead

morcos commented at 8:38 pm on March 6, 2018: member

in progress

in src/wallet/coinselection.cpp:134 in bf280e4659 outdated

129+                curr_waste -= (utxo_pool.at(depth).fee - utxo_pool.at(depth).long_term_fee);
130+                ++depth;
131+            }
132+        } else { // Moving forwards, continuing down this branch
133+            // Assert that this utxo is not negative. It should never be negative, effective value calculation should have removed it
134+            assert(utxo_pool.at(depth).txout.nValue >= 0);

Xekyo commented at 8:39 pm on March 6, 2018:

I thought you’re filtering effective values to be strictly bigger than zero.

achow101 commented at 8:52 pm on March 6, 2018:

Fixed

achow101 force-pushed on Mar 6, 2018

in src/wallet/coinselection.cpp:84 in d55accd6e5 outdated

83+        if (remaining_tries <= 0) { // Too many tries, exit
84+            break;
85+        }
86+        // Conditions for starting a backtrack
87+        else if ( value_track + lookahead < target_value || // Cannot possibly reach target with the amount remaining in the lookahead.
88+                    value_track > target_value + cost_of_change || // Selected value is out of range, go back and try other branch

morcos commented at 10:07 pm on March 6, 2018:

nit: spacing

achow101 commented at 1:49 pm on March 7, 2018:

Fixed.

in src/wallet/coinselection.cpp:107 in d55accd6e5 outdated

105+        // Backtracking, moving backwards
106+        if (backtrack) {
107+            backtrack = false; // Reset
108+            --depth;
109+
110+            // Walk backwards to find the first utxo which has not has its second branch traversed

morcos commented at 10:11 pm on March 6, 2018:

typo: has not had

achow101 commented at 1:49 pm on March 7, 2018:

Fixed.

in src/wallet/wallet.cpp:1601 in a1b36b1e9e outdated

1596+    int totalBytes = CalculateMaximumSignedTxSize(txn, pwallet, txouts);
1597+    if (totalBytes == -1) return -1;
1598+    int witnessversion = 0;
1599+    std::vector<unsigned char> witnessprogram;
1600+    // We don't want to multi-count segwit empty vin and flag bytes
1601+    if (txout.scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) {

instagibbs commented at 10:16 pm on March 6, 2018:

This is wrong, we need to look for segwit spends directly, then decrements by 1 virtual byte, since these are witness bytes.

morcos commented at 10:19 pm on March 6, 2018: member

still in progress

achow101 force-pushed on Mar 6, 2018

in src/wallet/coinselection.cpp:46 in f41f751f2e outdated

41+ * std::set<CInputCoin>& out_set -> This is an output parameter for the set of CInputCoins that have been selected.
42+ * CAmount& value_ret -> This is an output parameter for the total value of the CInputCoins that were selected.
43+ * CAmount& fee_ret -> This is an output parameter for the value of the transaction fees for the CInputCoins that were selected.
44+ */
45+
46+static const int remaining_tries = 100000;

morcos commented at 10:43 pm on March 6, 2018:

ultra nit: variable name

achow101 commented at 1:50 pm on March 7, 2018:

Changed

in src/wallet/coinselection.cpp:113 in f41f751f2e outdated

108+            while (depth >= 0 && !selection.at(depth)) {
109+                // Step back one
110+                lookahead += utxo_pool.at(depth).txout.nValue;
111+                --depth;
112+            }
113+            if (depth < 0) { // We have walked back to the first utxo and no branch is untraversed. No solution, exit.

morcos commented at 10:43 pm on March 6, 2018:

Comment wrong. “Explored all possible solutions”, not “No solution”

achow101 commented at 1:50 pm on March 7, 2018:

Fixed

achow101 force-pushed on Mar 6, 2018

in src/wallet/coinselection.cpp:53 in f41f751f2e outdated

48+bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount& fee_ret)
49+{
50+    out_set.clear();
51+    CAmount value_track = 0;
52+
53+    if (utxo_pool.empty()) {

instagibbs commented at 1:43 pm on March 7, 2018:

I think this is redundant with https://github.com/bitcoin/bitcoin/pull/10637/commits/f41f751f2e3ad69470624a6f55db3c1683712182#diff-491a507b32a78f89c3e066deedc98171R72

perhaps move that check here, to avoid deferencencing an invalid iterator.

achow101 force-pushed on Mar 7, 2018

in src/wallet/wallet.cpp:2787 in 4eba2d5729 outdated

2782             bool pick_new_inputs = true;
2783             CAmount nValueIn = 0;
2784+
2785+            // BnB selector is the only selector used when this is true.
2786+            // That should only happen on the first pass through the loop.
2787+            bool use_bnb = true;

instagibbs commented at 3:17 pm on March 7, 2018:

bool use_bnb = nSubtractFeeFromAmount == 0

then you can remove the else case later.

in src/bench/coin_selection.cpp:68 in 51952ad62c outdated

59@@ -57,4 +60,48 @@ static void CoinSelection(benchmark::State& state)
60     }
61 }
62 
63+typedef std::set<CInputCoin> CoinSet;
64+
65+static void add_coin(const CAmount& nValue, int nInput, std::vector<CInputCoin>& set, const CWallet& wallet)
66+{
67+    CMutableTransaction tx;
68+    tx.vout.resize(nInput+1);

Xekyo commented at 3:30 pm on March 7, 2018:

Nit: Please add spaces around plus in your code.

achow101 force-pushed on Mar 7, 2018

in src/wallet/coinselection.cpp:208 in 5e64d67dc2 outdated

202+            }
203+        }
204+    }
205+}
206+
207+bool KnapsackSolver(std::vector<CInputCoin>& utxo_pool, const CAmount& nTargetValue, std::set<CInputCoin>& out_set, CAmount& value_ret)

ryanofsky commented at 4:09 pm on March 7, 2018:

In commit “Copy KnapsackSolver coin selection code to coinselection.cpp” (5e64d67dc2bf4961a7efc7e3e160fd2629072a20)

It would be a little easier to confirm there are no unintentional changes in behavior if this commit moved code instead of copying it. Doing this would also make the later “Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack” (f93ae0c1d3476bfe7d3460d46179998eeda0cd46) commit simpler.

As far as I can see, though, the main change here is dropping the output.fSpendable, output.nDepth, output.tx IsFromMe and TransactionWithinChainLimit checks that were in SelectCoinsMinConf. Other than that, changes made to this code are:

renaming setCoinsRet to out_set, nValueRet to value_ret, etc
sorting coins in descending order instead of sorting then reversing

ryanofsky commented at 4:14 pm on March 7, 2018: member

utACK e98badc2c519308949f7511201c38633fb32f8d9. Left various minor notes below, which you should feel free to ignore.

in src/wallet/coinselection.cpp:33 in 51952ad62c outdated

28+ * now minus the cost to spend the current inputs later, plus the amount exceeding the target value. We search the tree to find the
29+ * set of UTXOs which falls within our range and minimizes waste.
30+ *
31+ * An additional optimization of this algorithm implemented here is a lookahead value which maintains the total value of the UTXO set
32+ * of all unexplored UTXOs (i.e. UTXOs that have not yet been included or excluded). This allows us to cut a branch if the remaining
33+ * amount is not sufficient to reach our target.

Xekyo commented at 4:22 pm on March 7, 2018:

I’d like to suggest the following for the above description:

This is the Branch and Bound Coin Selection algorithm designed by Murch. It searches for an input set that can pay for the spending target and does not exceed the spending target by more than the cost of creating and spending a change output. The algorithm uses a depth-first search on a binary tree. In the binary tree, each node corresponds to the inclusion or the omission of a UTXO. UTXOs are sorted by their effective values and the trees is explored deterministically per the inclusion branch first. At each node, the algorithm checks whether the selection is within the target range. While the selection has not reached the target range, more UTXOs are included. When a selection’s value exceeds the target range, the complete subtree deriving from this selection can be omitted. At that point, the last included UTXO is deselected and the corresponding omission branch explored instead. The search ends after the complete tree has been searched or after a limited number of tries.

The search continues to search for better solutions after one solution has been found. The best solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to spend the current inputs at the given fee rate minus the long term expected cost to spend the inputs, plus the amount the selection exceeds the spending target:

waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)

The algorithm uses two additional optimizations. A lookahead keeps track of the total value of the unexplored UTXOs. A subtree is not explored if the lookahead indicates that the target range cannot be reached. Further, it is unnecessary to test equivalent combinations. This allows us to skip testing the inclusion of UTXOs that match the effective value and waste of an omitted predecessor.

The Branch and Bound algorithm is described in detail in Murch’s Master Thesis: https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf

Edit: Cherrypicked first and third of instagibbs changes from below. ;)

instagibbs commented at 4:35 pm on March 7, 2018:

s/unexlored/unexplored/

s/Further, it is unnecessary to test equivalent combinations./Further, it is unnecessary to test equivalent effective value combinations./

s/This allows to skip/This allows us to skip/

ACK otherwise

achow101 commented at 6:48 pm on March 7, 2018:

Using this

in src/wallet/coinselection.cpp:104 in 73cee79007 outdated

 99+        // Backtracking, moving backwards
100+        if (backtrack) {
101+            backtrack = false; // Reset
102+            --depth;
103+
104+            // Walk backwards to find the first utxo which had not has its second branch traversed

Xekyo commented at 4:55 pm on March 7, 2018:

This comment is sort of outdated. How about:

Walk backwards to find the last included UTXO that still needs to have its omission branch traversed.

achow101 commented at 6:48 pm on March 7, 2018:

Done

in src/wallet/wallet.cpp:2505 in 9c0c8777c1 outdated

2501     std::vector<COutput> vCoins(vAvailableCoins);
2502 
2503     // coin control -> return all selected outputs (we want all selected to go into the transaction for sure)
2504     if (coin_control.HasSelected() && !coin_control.fAllowOtherInputs)
2505     {
2506+        // For now, don't use BnB if preset inputs are selected. TODO: Enable this later

instagibbs commented at 5:45 pm on March 7, 2018:

this is not a TODO, if there is no coin selection to be had, you cannot do coin selection.

achow101 commented at 6:48 pm on March 7, 2018:

Done

morcos commented at 7:28 pm on March 8, 2018:

Huh?
There is still coin selection if you have preset inputs. Your preset inputs may not be sufficient, it just means use at least these coins.

instagibbs commented at 7:35 pm on March 8, 2018:

@morcos in this case the user has selected to not allow any other inputs?

morcos commented at 7:40 pm on March 8, 2018:

oops

instagibbs commented at 6:32 pm on March 7, 2018: member

needs rebase

achow101 force-pushed on Mar 7, 2018

achow101 commented at 6:48 pm on March 7, 2018: member

Rebased

in src/wallet/coinselection.cpp:51 in f87a620362 outdated

46+ * std::set<CInputCoin>& out_set -> This is an output parameter for the set of CInputCoins that have been selected.
47+ * CAmount& value_ret -> This is an output parameter for the total value of the CInputCoins that were selected.
48+ * CAmount not_input_fees -> The fees that need to be paid for the stuff that aren't inputs
49+ */
50+
51+static const int TOTAL_TRIES = 100000;

eklitzke commented at 9:12 pm on March 7, 2018:

nit: should use size_t

achow101 commented at 9:25 pm on March 8, 2018:

Done

in src/wallet/coinselection.cpp:82 in f87a620362 outdated

77+    CAmount curr_waste = 0;
78+    std::vector<bool> best_selection;
79+    CAmount best_waste = MAX_MONEY;
80+
81+    // Depth First search loop for choosing the UTXOs
82+    for (int i = 0; i < TOTAL_TRIES; ++i) {

eklitzke commented at 9:12 pm on March 7, 2018:

nit: size_t

achow101 commented at 9:26 pm on March 8, 2018:

Done

in src/wallet/coinselection.cpp:60 in f87a620362 outdated

55+    out_set.clear();
56+    CAmount value_track = 0;
57+
58+    int depth = 0;
59+    std::vector<bool> selection; // select the utxo at this index
60+    selection.assign(utxo_pool.size(), false);

eklitzke commented at 9:14 pm on March 7, 2018:

These two lines are equivalent to (but less efficient than):

0std::vector<bool> selection(utxo_pool.size());

achow101 commented at 9:26 pm on March 8, 2018:

Done

in src/wallet/coinselection.cpp:40 in f87a620362 outdated

35+ * equivalent combinations. This allows us to skip testing the inclusion of UTXOs that match the effective value and waste of an 
36+ * omitted predecessor.
37+ *
38+ * The Branch and Bound algorithm is described in detail in Murch's Master Thesis: https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
39+ *
40+ * SelectCoinsBnB Arguments:

eklitzke commented at 9:15 pm on March 7, 2018:

Please use doxygen docstring format.

achow101 commented at 9:31 pm on March 8, 2018:

Done (I think)

in src/wallet/coinselection.cpp:48 in f87a620362 outdated

43+ * const CAmount& target_value -> This is the value that we want to select. It is the lower bound of the range.
44+ * const CAmount& cost_of_change -> This is the cost of creating and spending a change output. This plus target_value is the upper bound
45+ *                                  of the range.
46+ * std::set<CInputCoin>& out_set -> This is an output parameter for the set of CInputCoins that have been selected.
47+ * CAmount& value_ret -> This is an output parameter for the total value of the CInputCoins that were selected.
48+ * CAmount not_input_fees -> The fees that need to be paid for the stuff that aren't inputs

eklitzke commented at 9:15 pm on March 7, 2018:

“stuff”?

achow101 commented at 9:26 pm on March 8, 2018:

Made clearer about what stuff is

in src/wallet/coinselection.cpp:73 in f87a620362 outdated

61+    bool backtrack = false;
62+    CAmount actual_target = not_input_fees + target_value;
63+
64+    // Calculate lookahead
65+    CAmount lookahead = 0;
66+    for (const CInputCoin& utxo : utxo_pool) {

eklitzke commented at 9:17 pm on March 7, 2018:

This loop can be replaced with:

0const CAmount lookahead = std::accumulate(utxo_pool.begin(), utxo_pool.end(), 0);

achow101 commented at 9:26 pm on March 8, 2018:

This doesn’t work since utxo_pool contains CInputCoins and not ints

in src/wallet/coinselection.cpp:154 in f87a620362 outdated

149+        return false;
150+    }
151+
152+    // Set output set
153+    value_ret = 0;
154+    for (unsigned int i = 0; i < best_selection.size(); ++i) {

eklitzke commented at 9:20 pm on March 7, 2018:

nit: size_t

achow101 commented at 9:26 pm on March 8, 2018:

done

in src/wallet/fees.h:31 in f87a620362 outdated

25@@ -26,6 +26,18 @@ CAmount GetRequiredFee(unsigned int nTxBytes);
26  */
27 CAmount GetMinimumFee(unsigned int nTxBytes, const CCoinControl& coin_control, const CTxMemPool& pool, const CBlockPolicyEstimator& estimator, FeeCalculation *feeCalc);
28 
29+/**
30+ * Return the minimum required fee taking into account the
31+ * floating relay fee and user set minimum transaction fee

eklitzke commented at 9:24 pm on March 7, 2018:

nit: end this sentence with a period

in src/wallet/fees.h:37 in f87a620362 outdated

32+ */
33+CFeeRate GetRequiredFeeRate();
34+
35+/**
36+ * Estimate the minimum fee rate considering user set parameters
37+ * and the required fee

eklitzke commented at 9:24 pm on March 7, 2018:

nit: end this sentence with a period

eklitzke commented at 9:25 pm on March 7, 2018: contributor

Just nits in this first pass.

instagibbs commented at 3:14 pm on March 8, 2018: member

linter failing the tests:

- equivalent combinations. This allows us to skip testing the inclusion of UTXOs that match the effective value and waste of an ^—- failure generated from contrib/devtools/lint-whitespace.sh

in src/wallet/coinselection.cpp:35 in f87a620362 outdated

30+ *
31+ * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
32+ *
33+ * The algorithm uses two additional optimizations. A lookahead keeps track of the total value of the unexplored UTXOs. A subtree
34+ * is not explored if the lookahead indicates that the target range cannot be reached. Further, it is unnecessary to test
35+ * equivalent combinations. This allows us to skip testing the inclusion of UTXOs that match the effective value and waste of an

MarcoFalke commented at 3:23 pm on March 8, 2018:

Trainling whitespace causes a travis failure.

achow101 commented at 7:35 pm on March 8, 2018:

Fixed

in src/wallet/wallet.cpp:1538 in dcf6d17c92 outdated

1534@@ -1535,6 +1535,77 @@ int CWalletTx::GetRequestCount() const
1535     return nRequests;
1536 }
1537 
1538+// Helper for producing a max-sized low-S signatures (eg 72 bytes)

ryanofsky commented at 5:49 pm on March 8, 2018:

In commit “Calculate and store the number of bytes required to spend an input” (dcf6d17c9269dcba1233ca696296ed8cee3ea3bf)

s/signatures/signature

achow101 commented at 9:27 pm on March 8, 2018:

Done

in src/wallet/wallet.cpp:1606 in dcf6d17c92 outdated

1599+int GetTxOutSpendSize(const CTxOut& txout, const CWallet* pwallet)
1600+{
1601+    CMutableTransaction txn;
1602+    txn.vin.push_back(CTxIn(COutPoint()));
1603+    if (!pwallet->DummySignInput(txn.vin[0], txout)) {
1604+        return -1;

ryanofsky commented at 6:00 pm on March 8, 2018:

In commit “Calculate and store the number of bytes required to spend an input” (dcf6d17c9269dcba1233ca696296ed8cee3ea3bf)

Can you add a comment saying when this is condition is expected to happen?

achow101 commented at 9:27 pm on March 8, 2018:

Done

in src/consensus/validation.h:107 in dcf6d17c92 outdated

100@@ -101,5 +101,9 @@ static inline int64_t GetBlockWeight(const CBlock& block)
101 {
102     return ::GetSerializeSize(block, SER_NETWORK, PROTOCOL_VERSION | SERIALIZE_TRANSACTION_NO_WITNESS) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(block, SER_NETWORK, PROTOCOL_VERSION);
103 }
104+static inline int64_t GetTransationInputWeight(const CTxIn& txin)
105+{
106+    return ::GetSerializeSize(txin, SER_NETWORK, PROTOCOL_VERSION | SERIALIZE_TRANSACTION_NO_WITNESS) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(txin, SER_NETWORK, PROTOCOL_VERSION) + ::GetSerializeSize(txin.scriptWitness.stack, SER_NETWORK, PROTOCOL_VERSION);

ryanofsky commented at 6:28 pm on March 8, 2018:

In commit “Calculate and store the number of bytes required to spend an input” (dcf6d17c9269dcba1233ca696296ed8cee3ea3bf)

Maybe add a comment here to explain scriptWitness part, like “scriptWitness size is added here because witnesses and txins are split up in segwit serialization.”

achow101 commented at 9:27 pm on March 8, 2018:

Done

in src/wallet/wallet.cpp:1570 in dcf6d17c92 outdated

1565+        nIn++;
1566+    }
1567+    return true;
1568+}
1569+
1570+int64_t CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *pWallet)

ryanofsky commented at 6:32 pm on March 8, 2018:

In commit “Calculate and store the number of bytes required to spend an input” (dcf6d17c9269dcba1233ca696296ed8cee3ea3bf)

Somehow wallet variables in the old code are getting replaced by pWallet variables in the new code (probably a bad rebase).

achow101 commented at 9:27 pm on March 8, 2018:

Done

in src/wallet/wallet.cpp:1587 in dcf6d17c92 outdated

1582+        txouts.emplace_back(mi->second.tx->vout[input.prevout.n]);
1583+    }
1584+    return CalculateMaximumSignedTxSize(tx, pWallet, txouts);
1585+}
1586+
1587+// txouts needs to be in the order of tx.vin

ryanofsky commented at 6:42 pm on March 8, 2018:

In commit “Calculate and store the number of bytes required to spend an input” (dcf6d17c9269dcba1233ca696296ed8cee3ea3bf)

Could just make this an assert()

achow101 commented at 9:27 pm on March 8, 2018:

How so?

ryanofsky commented at 1:06 am on March 9, 2018:

Never mind, misinterpreted “in the order of.” I was suggesting you could assert the two vectors were the same size.

in src/wallet/wallet.cpp:1588 in dcf6d17c92 outdated

1583+    }
1584+    return CalculateMaximumSignedTxSize(tx, pWallet, txouts);
1585+}
1586+
1587+// txouts needs to be in the order of tx.vin
1588+int64_t CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *pWallet, const std::vector<CTxOut> txouts)

ryanofsky commented at 6:46 pm on March 8, 2018:

In commit “Calculate and store the number of bytes required to spend an input” (dcf6d17c9269dcba1233ca696296ed8cee3ea3bf)

Would be good to add & to avoid copying the vector.

achow101 commented at 9:27 pm on March 8, 2018:

Done

in src/wallet/wallet.h:505 in dcf6d17c92 outdated

535@@ -527,6 +536,9 @@ class COutput
536     int i;
537     int nDepth;
538 
539+    /** Pre-computed estimated size of this output as a fully-signed input in a transaction */
540+    int nInputBytes;

ryanofsky commented at 6:49 pm on March 8, 2018:

In commit “Calculate and store the number of bytes required to spend an input” (dcf6d17c9269dcba1233ca696296ed8cee3ea3bf)

May want to mention this can be -1.

achow101 commented at 9:27 pm on March 8, 2018:

Done

in src/wallet/wallet.cpp:1599 in dcf6d17c92 outdated

1594+        return -1;
1595+    }
1596+    return GetVirtualTransactionSize(txNew);
1597+}
1598+
1599+int GetTxOutSpendSize(const CTxOut& txout, const CWallet* pwallet)

ryanofsky commented at 6:55 pm on March 8, 2018:

In commit “Calculate and store the number of bytes required to spend an input” (dcf6d17c9269dcba1233ca696296ed8cee3ea3bf)

Would be good to name GetTxOutSpendSize consistently with CalculateMaximumSignedTxSize() since they are basically doing the same thing. Maybe CalculateMaximumSignedInputSize.

achow101 commented at 9:27 pm on March 8, 2018:

Done

in src/wallet/fees.h:30 in b68ce5a0e6 outdated

25@@ -26,6 +26,18 @@ CAmount GetRequiredFee(unsigned int nTxBytes);
26  */
27 CAmount GetMinimumFee(unsigned int nTxBytes, const CCoinControl& coin_control, const CTxMemPool& pool, const CBlockPolicyEstimator& estimator, FeeCalculation *feeCalc);
28 
29+/**
30+ * Return the minimum required fee taking into account the

ryanofsky commented at 7:10 pm on March 8, 2018:

In commit “Add a GetMinimumFeeRate function which is wrapped by GetMinimumFee” (b68ce5a0e638c47140f350cbc40f9cfc85fb4c37)

Could s/fee/fee rate/

achow101 commented at 9:27 pm on March 8, 2018:

Done

morcos commented at 8:23 pm on March 8, 2018: member

c1f310c doesn’t compile because you changed the arguments to SelectCoins but didn’t change the call sites until the next two commits.

achow101 force-pushed on Mar 8, 2018

achow101 commented at 9:28 pm on March 8, 2018: member

@morcos

c1f310c doesn’t compile because you changed the arguments to SelectCoins but didn’t change the call sites until the next two commits.

That was done in order to make the changes clearer and easier to follow. Otherwise it would be very large commit that is not reviewer friendly IMO.

achow101 force-pushed on Mar 8, 2018

in src/wallet/wallet.cpp:2480 in 44657d0374 outdated

2572-            return false;
2573-        setCoinsRet.insert(coinLowestLarger.get());
2574-        nValueRet += coinLowestLarger->txout.nValue;
2575-        return true;
2576-    }
2577+            if (!output.fSpendable)

ryanofsky commented at 3:25 pm on March 9, 2018:

In commit “Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack” (44657d0374d7fb25cca5cd098b27a5163f139de6)

Would be nice to share spendable / depth / fromme / chainlimit checks between bnb and knapsack solvers. Maybe they could be factored out into a coin IsEligible function that both loops could call.

achow101 commented at 1:38 am on March 10, 2018:

Done

in src/wallet/wallet.cpp:2483 in 44657d0374 outdated

2580-    // Solve subset sum by stochastic approximation
2581-    std::sort(vValue.begin(), vValue.end(), CompareValueOnly());
2582-    std::reverse(vValue.begin(), vValue.end());
2583-    std::vector<char> vfBest;
2584-    CAmount nBest;
2585+            const CWalletTx *pcoin = output.tx;

ryanofsky commented at 3:27 pm on March 9, 2018:

In commit “Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack” (44657d0374d7fb25cca5cd098b27a5163f139de6)

I’m not sure having pcoin and i variables actually makes the code easier to read. It would seem simpler to drop these extra variables and just write output.tx and output.i directly.

achow101 commented at 1:38 am on March 10, 2018:

Done

in src/wallet/wallet.cpp:2557 in 44657d0374 outdated

2559-        (bSpendZeroConfChange && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 0, 1, 2, vCoins, setCoinsRet, nValueRet)) ||
2560-        (bSpendZeroConfChange && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 0, 1, std::min((size_t)4, nMaxChainLength/3), vCoins, setCoinsRet, nValueRet)) ||
2561-        (bSpendZeroConfChange && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 0, 1, nMaxChainLength/2, vCoins, setCoinsRet, nValueRet)) ||
2562-        (bSpendZeroConfChange && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 0, 1, nMaxChainLength, vCoins, setCoinsRet, nValueRet)) ||
2563-        (bSpendZeroConfChange && !fRejectLongChains && SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 0, 1, std::numeric_limits<uint64_t>::max(), vCoins, setCoinsRet, nValueRet));
2564+        SelectCoinsMinConf(nTargetValue - nValueFromPresetInputs, 1, 6, 0, vCoins, setCoinsRet, nValueRet, not_input_fees, effective_fee, use_bnb, change_output_size, change_spend_size) ||

ryanofsky commented at 3:52 pm on March 9, 2018:

In commit “Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack” (44657d0374d7fb25cca5cd098b27a5163f139de6)

Maybe some of these arguments could be moved to structs, since there are so many values that have to be passed along from CreateTransaction -> SelectCoins -> SelectCoinsMinConf, and SelectCoinsMinConf is pretty rewritten in this commit anyway.

achow101 commented at 1:38 am on March 10, 2018:

I’ve created two structs, one for the confirmation target and one for additional coin selection parameters.

ryanofsky commented at 4:07 pm on March 9, 2018: member

That was done in order to make the changes clearer and easier to follow. Otherwise it would be very large commit that is not reviewer friendly IMO.

My suggestion to move code to coinselection.cpp instead of copying it in #10637 (review) would make a combined SelectCoins / CreateTransaction commit smaller, and I think would make it easier to see how behavior is changing.

But I don’t think it’s worth spending much effort to restructure commits unless you are expecting to have a number of new reviewers look at this.

in src/wallet/wallet.cpp:2914 in 851f71b84b outdated

2908@@ -2889,20 +2909,12 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2909                     txNew.vin.push_back(CTxIn(coin.outpoint,CScript(),
2910                                               nSequence));
2911 
2912-                // Fill in dummy signatures for fee calculation.
2913-                if (!DummySignTx(txNew, setCoins)) {
2914+                nBytes = CalculateMaximumSignedTxSize(txNew, this);

ryanofsky commented at 4:35 pm on March 9, 2018:

In commit “Use BnB in CreateTransaction on the first pass through the loop” (851f71b84b12581cce933fd066ded98d213295ad)

This change and other nBytes updates in CreateTransaction would seem to make more sense as part of the “Calculate and store the number of bytes” commit instead of the “Use BnB” commit since they are refactorings that don’t change behavior.

in src/wallet/wallet.cpp:2853 in 851f71b84b outdated

2845@@ -2833,23 +2846,30 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2846                 if (pick_new_inputs) {
2847                     nValueIn = 0;
2848                     setCoins.clear();
2849-                    if (!SelectCoins(vAvailableCoins, nValueToSelect, setCoins, nValueIn, &coin_control))
2850+                    if (!SelectCoins(vAvailableCoins, nValueToSelect, setCoins, nValueIn, not_input_fees, nFeeRateNeeded, coin_control, use_bnb, change_prototype_size, CalculateMaximumSignedInputSize(change_prototype_txout, this)))
2851                     {
2852-                        strFailReason = _("Insufficient funds");
2853-                        return false;
2854+                        // If BnB was used, it was the first pass. No longer the first pass and continue loop with knapsack.

ryanofsky commented at 4:41 pm on March 9, 2018:

In commit “Use BnB in CreateTransaction on the first pass through the loop” (851f71b84b12581cce933fd066ded98d213295ad)

Would update comment to mention that SelectCoins call will change use_bnb to false if it was not used, since it’s not obvious that use_bnb is an input/output parameter. Could also split use_bnb into separate input and output parameters like bnb_used and disable_bnb.

achow101 commented at 1:38 am on March 10, 2018:

Done

sipa commented at 4:50 pm on March 9, 2018: member

@achow101 We have a policy that every commit in a pull request must compile and pass tests. This helps with review, if you know you can assume that every incremental change is a fully-functional codebase, and there aren’t things you need to understand from future commits to see how things fit together. It also helps with git bisects, making sure that things don’t accidentally get broken and unbroken somewhere in a codebase’s history, leading you on a goose chase.

Currently, none of your commits compile, except the last one. Fixing this would help review greatly.

in src/wallet/wallet.cpp:2826 in 851f71b84b outdated

2820@@ -2811,6 +2821,9 @@ bool CWallet::CreateTransaction(const std::vector<CRecipient>& vecSend, CWalletT
2821                             fFirst = false;
2822                             txout.nValue -= nFeeRet % nSubtractFeeFromAmount;
2823                         }
2824+                    } else if (use_bnb){
2825+                        // On the first pass BnB selector, include the fee cost for outputs
2826+                        not_input_fees +=  nFeeRateNeeded.GetFee(::GetSerializeSize(txout, SER_NETWORK, PROTOCOL_VERSION));

ryanofsky commented at 4:52 pm on March 9, 2018:

In commit “Use BnB in CreateTransaction on the first pass through the loop” (851f71b84b12581cce933fd066ded98d213295ad)

Might be safer/simpler to always compute not_input_fees correctly, instead of it leaving partially set depending on fSubtractFeeFromAmount and use_bnb values (in cases where it isn’t used).

achow101 commented at 1:39 am on March 10, 2018:

Done

in src/wallet/wallet.cpp:2499 in 44657d0374 outdated

2625-
2626-    return true;
2627 }
2628 
2629-bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CCoinControl* coinControl) const
2630+bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, CAmount not_input_fees, const CFeeRate effective_fee, const CCoinControl& coin_control, bool& use_bnb, int change_output_size, int change_spend_size) const

ryanofsky commented at 5:02 pm on March 9, 2018:

In commit “Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack” (44657d0374d7fb25cca5cd098b27a5163f139de6)

Seems like it would be a little simpler for the caller and more consistent as a way of passing params if a tx_noinputs_size value were passed instead of not_input_fees.

achow101 commented at 1:39 am on March 10, 2018:

Done

in src/wallet/test/coinselector_tests.cpp:31 in 35794f4fd9 outdated

26+
27+typedef std::set<CInputCoin> CoinSet;
28+
29+static std::vector<COutput> vCoins;
30+static const CWallet testWallet("dummy", CWalletDBWrapper::CreateDummy());
31+static CAmount balance = 0;

ryanofsky commented at 5:43 pm on March 9, 2018:

In commit “Add coin selection test cases and move the original test cases” (35794f4fd9ea54e4a77948e67feb08fb5af06959)

Maybe name this g_balance since it’s a new variable.

in src/wallet/test/coinselector_tests.cpp:201 in 35794f4fd9 outdated

196+    BOOST_CHECK(SelectCoinsBnB(utxo_pool, 30 * CENT, 5000, selection, value_ret, not_input_fees));
197+
198+    ////////////////////
199+    // Behavior tests //
200+    ////////////////////
201+    BOOST_TEST_MESSAGE("Testing behavior");

ryanofsky commented at 7:03 pm on March 9, 2018:

In commit “Add coin selection test cases and move the original test cases” (35794f4fd9ea54e4a77948e67feb08fb5af06959)

Maybe delete, looks like leftover example code.

achow101 commented at 1:39 am on March 10, 2018:

Done

in src/bench/coin_selection.cpp:74 in 05e5e77b12 outdated

69+    tx.vout[nInput].nValue = nValue;
70+    std::unique_ptr<CWalletTx> wtx(new CWalletTx(&wallet, MakeTransactionRef(std::move(tx))));
71+    set.emplace_back(wtx.get(), nInput);
72+}
73+
74+static CAmount make_hard_case(int utxos, std::vector<CInputCoin>& utxo_pool, const CWallet& wallet)

ryanofsky commented at 7:12 pm on March 9, 2018:

In commit “Benchmark BnB in the worst case where it exhausts” (05e5e77b12e79aee915e957f2be85ea3f2cb0e20)

Would be nice to deduplicate this, maybe by creating a wallet test util file. Or could just note that this is copied from code in coinselector_tests.

achow101 commented at 1:39 am on March 10, 2018:

I’ve added a comment.

in src/wallet/coinselection.cpp:85 in fe2ce81f30 outdated

70+
71+    // Sort the utxo_pool
72+    std::sort(utxo_pool.begin(), utxo_pool.end(), descending);
73+
74+    // Best solution
75+    CAmount curr_waste = 0;

ryanofsky commented at 8:07 pm on March 9, 2018:

In commit “Implement Branch and Bound coin selection in a new file” (fe2ce81f30c288b7caf16ffed3b270272d4b5818)

This line should probably be moved, “best solution” comment above it doesn’t apply to it.

ryanofsky commented at 8:10 pm on March 9, 2018:

In commit “Implement Branch and Bound coin selection in a new file” (fe2ce81)

Might be clarifying to add “curr” prefix to other variables besides curr_waste. E.g. you could rename value_track curr_value, selection curr_selection, lookahead curr_available_value.

achow101 commented at 1:39 am on March 10, 2018:

Unified to be curr_*

in src/wallet/coinselection.cpp:59 in fe2ce81f30 outdated

54+    out_set.clear();
55+    CAmount value_track = 0;
56+
57+    int depth = 0;
58+    std::vector<bool> selection(utxo_pool.size()); // select the utxo at this index
59+    bool backtrack = false;

ryanofsky commented at 8:11 pm on March 9, 2018:

In commit “Implement Branch and Bound coin selection in a new file” (fe2ce81f30c288b7caf16ffed3b270272d4b5818)

Seems like backtrack variable should just be declared inside the loop. It looks like it will always be false at the top of every iteration given if (backtrack) backtrack = false; below.

achow101 commented at 1:39 am on March 10, 2018:

Done

in src/wallet/coinselection.cpp:58 in fe2ce81f30 outdated

53+{
54+    out_set.clear();
55+    CAmount value_track = 0;
56+
57+    int depth = 0;
58+    std::vector<bool> selection(utxo_pool.size()); // select the utxo at this index

ryanofsky commented at 9:56 pm on March 9, 2018:

In commit “Implement Branch and Bound coin selection in a new file” (fe2ce81f30c288b7caf16ffed3b270272d4b5818)

It might be helpful if there was a comment explaining how selection gets updated during the loop. The way the code uses depth variable to select coins from beginning and backtrack variable to deselect coins from the end is pretty unusual (or at least is something I never encountered before). For example, if there are three coins, and no optimizations apply, the coin selections that get tested are:

achow101 commented at 0:58 am on March 10, 2018: member

I’ve addressed a lot of @ryanofsky’s comments.

I’m going to squash, rebase, and re-commit this in order to make each commit compilable and better organized. The original commits will be saved here: https://github.com/achow101/bitcoin/tree/bnb-orig. The ending diff between what I am going to do and the original should be the same, just reorganized.

Calculate and store the number of bytes required to spend an input 12ec29d3bb

Store effective value, fee, and long term fee in CInputCoin

Have CInputCOin store effective value information. This includes the effective
value itself, the fee, and the long term fee for the input

f84fed8eb6

achow101 force-pushed on Mar 10, 2018

achow101 commented at 6:58 am on March 10, 2018: member

I have gone through and reorganized the commits. Each commit should now be individually compilable. Additionally I have taken @ryanofsky’s suggestion of moving the code for the KnapsackSolver instead of copying it. The commits that change SelectCoins, SelectCoinsMinConf, and CreateTransaction to support BnB have been combined into one large-ish commit.

The code should be functionally the same as before; the only differences are some variable names and whitespace. The original code can be found in this branch: https://github.com/achow101/bitcoin/tree/bnb-orig. Diff’ing the diffs of the two branches will show the changes that were made.

achow101 force-pushed on Mar 10, 2018

in src/bench/coin_selection.cpp:65 in 328733eaf0 outdated

60@@ -57,4 +61,47 @@ static void CoinSelection(benchmark::State& state)
61     }
62 }
63 
64+typedef std::set<CInputCoin> CoinSet;

eklitzke commented at 3:23 pm on March 10, 2018:

nit: C++ code should prefer using rather than typedef (not important here, but it’s more flexible with templated types). Syntax would be:

0using CoinSet = std::set<CInputCoin>;

achow101 commented at 9:11 pm on March 12, 2018:

I would prefer to continue to use what is currently done in the codebase unless we agreed to change the style.

in src/wallet/coinselection.cpp:18 in 328733eaf0 outdated

13+        return a.effective_value > b.effective_value;
14+    }
15+} descending;
16+
17+/*
18+ * This is the Branch and Bound Coin Selection algorithm designed by Murch. It searches for an input set that can pay for the

eklitzke commented at 3:25 pm on March 10, 2018:

These long line doc strings don’t fit on my screen, even when my browser is maximized :-(

in src/wallet/coinselection.cpp:60 in 328733eaf0 outdated

45+ * @param std::set<CInputCoin>& out_set -> This is an output parameter for the set of CInputCoins that have been selected.
46+ * @param CAmount& value_ret -> This is an output parameter for the total value of the CInputCoins that were selected.
47+ * @param CAmount not_input_fees -> The fees that need to be paid for the outputs and fixed size overhead (version, locktime, marker and flag)
48+ */
49+
50+static const size_t TOTAL_TRIES = 100000;

eklitzke commented at 3:26 pm on March 10, 2018:

nit: The way you have this is consistent with the rest of the Bitcoin code base, but better is:

0constexpr size_t TOTAL_TRIES = 100000;

Declaring a global static variable reserves sizeof(size_t) space in the .bss section, whereas constexpr inlines the data.

achow101 commented at 9:12 pm on March 12, 2018:

I would prefer to continue to use what is currently done in the codebase unless we agreed to change the style.

in src/wallet/coinselection.h:21 in 328733eaf0 outdated

16+
17+class CInputCoin {
18+public:
19+    CInputCoin(const CTransactionRef& tx, unsigned int i)
20+    {
21+        if (!tx)

eklitzke commented at 3:31 pm on March 10, 2018:

Consider making these into asserts, as I don’t think the callers check for exceptions anyway.

achow101 commented at 9:56 pm on March 12, 2018:

I’d prefer to keep this move-only

in src/wallet/test/coinselector_tests.cpp:27 in 328733eaf0 outdated

22+// we repeat those tests this many times and only complain if all iterations of the test fail
23+#define RANDOM_REPEATS 5
24+
25+std::vector<std::unique_ptr<CWalletTx>> wtxn;
26+
27+typedef std::set<CInputCoin> CoinSet;

eklitzke commented at 3:32 pm on March 10, 2018:

same nit regarding typedef vs using

in src/wallet/test/coinselector_tests.cpp:23 in 328733eaf0 outdated

18+// how many times to run all the tests to have a chance to catch errors that only show up with particular random shuffles
19+#define RUN_TESTS 100
20+
21+// some tests fail 1% of the time due to bad luck.
22+// we repeat those tests this many times and only complain if all iterations of the test fail
23+#define RANDOM_REPEATS 5

eklitzke commented at 3:38 pm on March 10, 2018:

Can you explain to me how this works? I don’t understand which situation the random shuffle causes the test to fail in.

instagibbs commented at 7:09 pm on March 12, 2018:

yes please add a comment

achow101 commented at 9:10 pm on March 12, 2018:

I don’t understand it either. It was there originally, I just moved it.

in src/wallet/wallet.h:654 in 328733eaf0 outdated

649+    size_t change_spend_size;
650+    CFeeRate effective_fee;
651+    size_t tx_noinputs_size;
652+
653+    CoinSelectionParams(bool use_bnb, size_t change_output_size, size_t change_spend_size, CFeeRate effective_fee, size_t tx_noinputs_size) : use_bnb(use_bnb), change_output_size(change_output_size), change_spend_size(change_spend_size), effective_fee(effective_fee), tx_noinputs_size(tx_noinputs_size) {}
654+    CoinSelectionParams() : use_bnb(true), change_output_size(0), change_spend_size(0), effective_fee(CFeeRate(0)), tx_noinputs_size(0) {}

eklitzke commented at 3:40 pm on March 10, 2018:

nit: less boiler plate if you use a delegating ctor

achow101 commented at 9:13 pm on March 12, 2018:

How does that work?

ryanofsky commented at 9:32 pm on March 12, 2018:

How does that work?

He was suggesting you write:

0CoinSelectionParams() : CoinSelectionParams(true, 0, ...) {}

IMO, it would actually be better to use member initialization and write:

0bool use_bnb = true;
1size_t change_output_size = 0;
2...
3CoinSelectionParams(bool use_bnb, size_t change_output_size, ...) ...;
4CoinSelectionParams() {}

achow101 commented at 11:18 pm on March 12, 2018:

I’ve used @ryanofsky’s suggestion

eklitzke commented at 3:42 pm on March 10, 2018: contributor

More nits, and I think you should consider running these changes through clang-format. But this looks pretty good (at least the parts I understand).

The thing I’m most curious about is how the random shuffle can cause the test cases to fail. That’s probably due to a lack of understanding on my part about how BnB works, could you explain?

eklitzke commented at 3:44 pm on March 10, 2018: contributor

I will also try to run this locally to test it out.

achow101 commented at 5:19 pm on March 10, 2018: member

The random failure thing is part of the tests for the old coinselection stuff and is unrelated to BnB.

in src/wallet/wallet.cpp:2447 in 34145b6a02 outdated

2443@@ -2444,30 +2444,67 @@ bool CWallet::OutputEligibleForSpending(const COutput& output, const CoinEligibi
2444 }
2445 
2446 bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibilty_filter, std::vector<COutput> vCoins,
2447-                                 std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet) const
2448+                                 std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, CoinSelectionParams& coin_selection_params) const

ryanofsky commented at 3:34 pm on March 12, 2018:

In commit “Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack and use it” (34145b6a0237afd0160c9624339f49fd34e524ff)

coin_selection_params can be a const reference instead of a mutable reference here. This would make it clearer values don’t change.

achow101 commented at 11:19 pm on March 12, 2018:

Made const

in src/wallet/wallet.cpp:2498 in 34145b6a02 outdated

2502 }
2503 
2504-bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CCoinControl* coinControl) const
2505+// use_bnb is both an input param, and an output param. It indicates that BnB should be
2506+// used but also informs the caller whether BnB was used
2507+bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params) const

ryanofsky commented at 3:45 pm on March 12, 2018:

In commit “Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack and use it” (34145b6a0237afd0160c9624339f49fd34e524ff)

Might be worth pulling use_bnb parameter out of coin_selection_params, because it’s the only mutable member, and otherwise this be a const reference.

I do still think my previous suggestion of splitting use_bnb inout param up into separate disable_bnb (input) and used_bnb (output) params (https://github.com/bitcoin/bitcoin/pull/10637#discussion_r173502504)/ would make the logic most clear, and would obviate the need for the new comment above explaining dual meanings of use_bnb.

achow101 commented at 11:19 pm on March 12, 2018:

I added a variable and parameter bnb_used to be a return parameter that indicates whether bnb was used.

in src/wallet/coinselection.cpp:101 in a406c66f1b outdated

 96+            backtrack = true;
 97+        }
 98+
 99+        // Backtracking, moving backwards
100+        if (backtrack) {
101+            backtrack = false; // Reset

ryanofsky commented at 4:18 pm on March 12, 2018:

In commit “Implement Branch and Bound coin selection in a new file” (a406c66f1b113e6418eec3b03e0301017478634e)

Can delete this line, no need to reset since variable goes out of scope.

achow101 commented at 11:19 pm on March 12, 2018:

Done

in src/wallet/coinselection.cpp:57 in a406c66f1b outdated

52+bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees)
53+{
54+    out_set.clear();
55+    CAmount curr_value = 0;
56+
57+    int depth = 0;

ryanofsky commented at 6:12 pm on March 12, 2018:

In commit “Implement Branch and Bound coin selection in a new file” (a406c66f1b113e6418eec3b03e0301017478634e)

I think it would make the traversal code easier to understand to get rid of depth variable and the trailing false entries in the curr_selection vector. I implemented this in cf0a82d49112e204112b54d76e661a8e66a28c8b, (fetchable with git fetch -n https://github.com/ryanofsky/bitcoin pr/nodepth:nodepth).

achow101 commented at 11:19 pm on March 12, 2018:

I’ve used your commit. It will be squashed into a406c66

ryanofsky commented at 6:19 pm on March 12, 2018: member

utACK 328733eaf0b4dfcca0f58cc1062fe6bd51566281. Changes since previous review: reorganizing all the commits, implementing various suggestions like variable renames, grouping params into structs, factoring out output eligible function.

in src/wallet/wallet.cpp:2472 in 34145b6a02 outdated

2472+            if (!OutputEligibleForSpending(output, eligibilty_filter))
2473+                continue;
2474+
2475+            CInputCoin coin(output.tx->tx, output.i);
2476+            coin.effective_value = coin.txout.nValue - (output.nInputBytes < 0 ? 0 : coin_selection_params.effective_fee.GetFee(output.nInputBytes));
2477+            // Only include outputs that are not negative effective value (i.e. not dust)

instagibbs commented at 7:12 pm on March 12, 2018:

micro-nit: positive, not non-negative

achow101 commented at 11:20 pm on March 12, 2018:

Done

in src/wallet/wallet.cpp:2473 in 34145b6a02 outdated

2473+                continue;
2474+
2475+            CInputCoin coin(output.tx->tx, output.i);
2476+            coin.effective_value = coin.txout.nValue - (output.nInputBytes < 0 ? 0 : coin_selection_params.effective_fee.GetFee(output.nInputBytes));
2477+            // Only include outputs that are not negative effective value (i.e. not dust)
2478+            if (coin.txout.nValue > 0) {

instagibbs commented at 7:16 pm on March 12, 2018:

this should be coin.txout.effective_value…. which likely means there is no test for this.

instagibbs changes_requested

in src/wallet/wallet.cpp:2473 in 328733eaf0 outdated

2589-                setCoinsRet.insert(vValue[i]);
2590-                nValueRet += vValue[i].txout.nValue;
2591+            CInputCoin coin(output.tx->tx, output.i);
2592+            coin.effective_value = coin.txout.nValue - (output.nInputBytes < 0 ? 0 : coin_selection_params.effective_fee.GetFee(output.nInputBytes));
2593+            // Only include outputs that are not negative effective value (i.e. not dust)
2594+            if (coin.txout.nValue > 0) {

instagibbs commented at 7:44 pm on March 12, 2018:

github is seemingly hiding comments, so saying this here again:

this should be coin.txout.effective_value…. which likely means there is no test for this.

achow101 commented at 9:52 pm on March 12, 2018:

Suggestions for a test for this?

instagibbs commented at 10:56 pm on March 12, 2018:

SCMC, with use_bnb being true, two outputs which summed together reach the target? If you remove the negative effective value one, it overshoots the window.

achow101 commented at 11:20 pm on March 12, 2018:

Fixed. Will add a test next.

achow101 commented at 0:05 am on March 13, 2018:

I added a test that runs SelectCoinsMinConf with an input with negative effective value. If that input somehow makes it through into SelectCoinsBnB, it will trigger an assert causing the test to fail. That should be sufficient to check for this case.

achow101 force-pushed on Mar 12, 2018

in src/wallet/test/coinselector_tests.cpp:223 in 81e11bb029 outdated

223+    CoinSet setCoinsRet;
224+    CAmount nValueRet;
225+    bool bnb_used;
226+    empty_wallet();
227+    add_coin(1);
228+    vCoins.at(0).nInputBytes = 40; // Make sure that it has a egative effective value. The next check should assert if this somehow got through. Otherwise it will fail

instagibbs commented at 2:43 pm on March 13, 2018:

egative

achow101 commented at 4:47 pm on March 13, 2018:

Fixed

ryanofsky commented at 3:31 pm on March 13, 2018: member

utACK c3136ea7e936714886b1329402931a3ec514afaf with squash. Changes since last review: adding bnb_used variable, getting rid of depth variable, using coin effective value instead of nValue to check for dust and testing this, moving effective value assert out of search loop.

instagibbs approved

instagibbs commented at 3:37 pm on March 13, 2018: member

utACK

Implement Branch and Bound coin selection in a new file

Create a new file for coin selection logic and implement the BnB algorithm in it.

0185939be6

Move output eligibility to a separate function ce7435cf1e

Use a struct for output eligibility

Instead of specifying 3 parameters, use a struct for those parameters
in order to reduce the number of arguments to SelectCoinsMinConf.

7d77eb1a5b

Remove coinselection.h -> wallet.h circular dependency

Changes CInputCoin to coinselection and to use CTransactionRef in
order to avoid a circular dependency. Also moves other coin selection
specific variables out of wallet.h to coinselectoin.h

4b2716da46

Add tests for the Branch and Bound algorithm 4566ab75f2

Move current coin selection algorithm to coinselection.{cpp,h}

Moves the current coin selection algorithm out of SelectCoinsMinConf
and puts it in coinselection.{cpp,h}. The new function, KnapsackSolver,
instead of taking a vector of COutputs, will take a vector of CInputCoins
that is prepared by SelectCoinsMinConf.

fb716f7b25

Move original knapsack solver tests to coinselector_tests.cpp cd927ff328

Add a GetMinimumFeeRate function which is wrapped by GetMinimumFee fab04887c2

Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack and use it

Allows SelectCoinsMinConf and SelectCoins be able to switch between
using BnB or Knapsack for choosing coins.

Has SelectCoinsMinConf do the preprocessing necessary to support either
BnB or Knapsack. This includes calculating the filtering the effective
values for each input.

Uses BnB in CreateTransaction to find an exact match for the output.
If BnB fails, it will fallback to the Knapsack solver.

6a34ff5335

Benchmark BnB in the worst case where it exhausts 76d2f068a4

Add a test to make sure that negative effective values are filtered 73b5bf2cb4

achow101 force-pushed on Mar 13, 2018

achow101 commented at 4:47 pm on March 13, 2018: member

Squashed

ryanofsky commented at 5:25 pm on March 13, 2018: member

utACK 73b5bf2cb40720bb4e4436ea63b5badf3d89ceb9. Only change since last review is comment fix and squash.

instagibbs commented at 5:30 pm on March 13, 2018: member

utACK https://github.com/bitcoin/bitcoin/pull/10637/commits/73b5bf2cb40720bb4e4436ea63b5badf3d89ceb9

laanwj merged this on Mar 14, 2018

laanwj closed this on Mar 14, 2018

laanwj referenced this in commit e057589dc6 on Mar 14, 2018

ghost commented at 0:22 am on March 15, 2018: none

noice!

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

TheHolyRoger referenced this in commit b127150eab on Jul 31, 2020

TheHolyRoger referenced this in commit cb394b50d6 on Aug 1, 2020

TheHolyRoger referenced this in commit f9096e2157 on Aug 1, 2020

TheHolyRoger referenced this in commit 6952af0e6a on Aug 1, 2020

PastaPastaPasta referenced this in commit 6ae4d32b4b on Dec 18, 2020

MarcoFalke deleted a comment on Oct 31, 2021

MarcoFalke locked this on Oct 31, 2021

MarcoFalke deleted a comment on Oct 31, 2021

Coin Selection with Murch’s algorithm #10637

Results

Derived-1L-2O scenario

derived-balanced.csv

moneypot.csv

Derived-1L-2O scenario

derived-balanced.csv

moneypot.csv