Merge #10637: Coin Selection with Murch's algorithm

73b5bf2cb Add a test to make sure that negative effective values are filtered (Andrew Chow)
76d2f068a Benchmark BnB in the worst case where it exhausts (Andrew Chow)
6a34ff533 Have SelectCoinsMinConf and SelectCoins use BnB or Knapsack and use it (Andrew Chow)
fab04887c Add a GetMinimumFeeRate function which is wrapped by GetMinimumFee (Andrew Chow)
cd927ff32 Move original knapsack solver tests to coinselector_tests.cpp (Andrew Chow)
fb716f7b2 Move current coin selection algorithm to coinselection.{cpp,h} (Andrew Chow)
4566ab75f Add tests for the Branch and Bound algorithm (Andrew Chow)
4b2716da4 Remove coinselection.h -> wallet.h circular dependency (Andrew Chow)
7d77eb1a5 Use a struct for output eligibility (Andrew Chow)
ce7435cf1 Move output eligibility to a separate function (Andrew Chow)
0185939be Implement Branch and Bound coin selection in a new file (Andrew Chow)
f84fed8eb Store effective value, fee, and long term fee in CInputCoin (Andrew Chow)
12ec29d3b Calculate and store the number of bytes required to spend an input (Andrew Chow)

Pull request description:

  This is an implementation of the [Branch and Bound coin selection algorithm written by Murch](http://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf) (@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.

Tree-SHA512: b0500f406bf671e74984fae78e2d0fbc5e321ddf4f06182c5855e9d1984c4ef2764c7586d03e16fa4b578c340b21710324926f9ca472d5447a0d1ed43eb4357e

1 files changed, 31 insertions, 21 deletions

diff --git a/src/wallet/fees.cpp b/src/wallet/fees.cpp
index 385fdc963a..03c32d3b97 100644
--- a/src/wallet/fees.cpp
+++ b/src/wallet/fees.cpp
@@ -21,6 +21,22 @@ CAmount GetRequiredFee(unsigned int nTxBytes)
 
 CAmount GetMinimumFee(unsigned int nTxBytes, const CCoinControl& coin_control, const CTxMemPool& pool, const CBlockPolicyEstimator& estimator, FeeCalculation *feeCalc)
 {
+    CAmount fee_needed = GetMinimumFeeRate(coin_control, pool, estimator, feeCalc).GetFee(nTxBytes);
+    // Always obey the maximum
+    if (fee_needed > maxTxFee) {
+        fee_needed = maxTxFee;
+        if (feeCalc) feeCalc->reason = FeeReason::MAXTXFEE;
+    }
+    return fee_needed;
+}
+
+CFeeRate GetRequiredFeeRate()
+{
+    return std::max(CWallet::minTxFee, ::minRelayTxFee);
+}
+
+CFeeRate GetMinimumFeeRate(const CCoinControl& coin_control, const CTxMemPool& pool, const CBlockPolicyEstimator& estimator, FeeCalculation *feeCalc)
+{
     /* User control of how to calculate fee uses the following parameter precedence:
        1. coin_control.m_feerate
        2. coin_control.m_confirm_target
@@ -28,15 +44,15 @@ CAmount GetMinimumFee(unsigned int nTxBytes, const CCoinControl& coin_control, c
        4. nTxConfirmTarget (user-set global variable)
        The first parameter that is set is used.
     */
-    CAmount fee_needed;
+    CFeeRate feerate_needed ;
     if (coin_control.m_feerate) { // 1.
-        fee_needed = coin_control.m_feerate->GetFee(nTxBytes);
+        feerate_needed = *(coin_control.m_feerate);
         if (feeCalc) feeCalc->reason = FeeReason::PAYTXFEE;
         // Allow to override automatic min/max check over coin control instance
-        if (coin_control.fOverrideFeeRate) return fee_needed;
+        if (coin_control.fOverrideFeeRate) return feerate_needed;
     }
     else if (!coin_control.m_confirm_target && ::payTxFee != CFeeRate(0)) { // 3. TODO: remove magic value of 0 for global payTxFee
-        fee_needed = ::payTxFee.GetFee(nTxBytes);
+        feerate_needed = ::payTxFee;
         if (feeCalc) feeCalc->reason = FeeReason::PAYTXFEE;
     }
     else { // 2. or 4.
@@ -48,38 +64,32 @@ CAmount GetMinimumFee(unsigned int nTxBytes, const CCoinControl& coin_control, c
         if (coin_control.m_fee_mode == FeeEstimateMode::CONSERVATIVE) conservative_estimate = true;
         else if (coin_control.m_fee_mode == FeeEstimateMode::ECONOMICAL) conservative_estimate = false;
 
-        fee_needed = estimator.estimateSmartFee(target, feeCalc, conservative_estimate).GetFee(nTxBytes);
-        if (fee_needed == 0) {
+        feerate_needed = estimator.estimateSmartFee(target, feeCalc, conservative_estimate);
+        if (feerate_needed == CFeeRate(0)) {
             // if we don't have enough data for estimateSmartFee, then use fallbackFee
-            fee_needed = CWallet::fallbackFee.GetFee(nTxBytes);
+            feerate_needed = CWallet::fallbackFee;
             if (feeCalc) feeCalc->reason = FeeReason::FALLBACK;
 
             // directly return if fallback fee is disabled (feerate 0 == disabled)
-            if (CWallet::fallbackFee.GetFee(1000) == 0) return fee_needed;
+            if (CWallet::fallbackFee == CFeeRate(0)) return feerate_needed;
         }
         // Obey mempool min fee when using smart fee estimation
-        CAmount min_mempool_fee = pool.GetMinFee(gArgs.GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000).GetFee(nTxBytes);
-        if (fee_needed < min_mempool_fee) {
-            fee_needed = min_mempool_fee;
+        CFeeRate min_mempool_feerate = pool.GetMinFee(gArgs.GetArg("-maxmempool", DEFAULT_MAX_MEMPOOL_SIZE) * 1000000);
+        if (feerate_needed < min_mempool_feerate) {
+            feerate_needed = min_mempool_feerate;
             if (feeCalc) feeCalc->reason = FeeReason::MEMPOOL_MIN;
         }
     }
 
     // prevent user from paying a fee below minRelayTxFee or minTxFee
-    CAmount required_fee = GetRequiredFee(nTxBytes);
-    if (required_fee > fee_needed) {
-        fee_needed = required_fee;
+    CFeeRate required_feerate = GetRequiredFeeRate();
+    if (required_feerate > feerate_needed) {
+        feerate_needed = required_feerate;
         if (feeCalc) feeCalc->reason = FeeReason::REQUIRED;
     }
-    // But always obey the maximum
-    if (fee_needed > maxTxFee) {
-        fee_needed = maxTxFee;
-        if (feeCalc) feeCalc->reason = FeeReason::MAXTXFEE;
-    }
-    return fee_needed;
+    return feerate_needed;
 }
 
-
 CFeeRate GetDiscardRate(const CBlockPolicyEstimator& estimator)
 {
     unsigned int highest_target = estimator.HighestTargetTracked(FeeEstimateHorizon::LONG_HALFLIFE);