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, 54 insertions, 0 deletions

diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
new file mode 100644
index 0000000000..4d1a43bc17
--- /dev/null
+++ b/src/wallet/coinselection.h
@@ -0,0 +1,54 @@
+// Copyright (c) 2017 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_COINSELECTION_H
+#define BITCOIN_COINSELECTION_H
+
+#include <amount.h>
+#include <primitives/transaction.h>
+#include <random.h>
+
+//! target minimum change amount
+static const CAmount MIN_CHANGE = CENT;
+//! final minimum change amount after paying for fees
+static const CAmount MIN_FINAL_CHANGE = MIN_CHANGE/2;
+
+class CInputCoin {
+public:
+    CInputCoin(const CTransactionRef& tx, unsigned int i)
+    {
+        if (!tx)
+            throw std::invalid_argument("tx should not be null");
+        if (i >= tx->vout.size())
+            throw std::out_of_range("The output index is out of range");
+
+        outpoint = COutPoint(tx->GetHash(), i);
+        txout = tx->vout[i];
+        effective_value = txout.nValue;
+    }
+
+    COutPoint outpoint;
+    CTxOut txout;
+    CAmount effective_value;
+    CAmount fee = 0;
+    CAmount long_term_fee = 0;
+
+    bool operator<(const CInputCoin& rhs) const {
+        return outpoint < rhs.outpoint;
+    }
+
+    bool operator!=(const CInputCoin& rhs) const {
+        return outpoint != rhs.outpoint;
+    }
+
+    bool operator==(const CInputCoin& rhs) const {
+        return outpoint == rhs.outpoint;
+    }
+};
+
+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);
+
+// Original coin selection algorithm as a fallback
+bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet);
+#endif // BITCOIN_COINSELECTION_H