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

diff --git a/src/wallet/feebumper.cpp b/src/wallet/feebumper.cpp
index 0c6d782e38..82a5017de0 100644
--- a/src/wallet/feebumper.cpp
+++ b/src/wallet/feebumper.cpp
@@ -16,33 +16,6 @@
 #include <util.h>
 #include <net.h>
 
-// Calculate the size of the transaction assuming all signatures are max size
-// Use DummySignatureCreator, which inserts 72 byte signatures everywhere.
-// TODO: re-use this in CWallet::CreateTransaction (right now
-// CreateTransaction uses the constructed dummy-signed tx to do a priority
-// calculation, but we should be able to refactor after priority is removed).
-// NOTE: this requires that all inputs must be in mapWallet (eg the tx should
-// be IsAllFromMe).
-static int64_t CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet)
-{
-    CMutableTransaction txNew(tx);
-    std::vector<CInputCoin> vCoins;
-    // Look up the inputs.  We should have already checked that this transaction
-    // IsAllFromMe(ISMINE_SPENDABLE), so every input should already be in our
-    // wallet, with a valid index into the vout array.
-    for (auto& input : tx.vin) {
-        const auto mi = wallet->mapWallet.find(input.prevout.hash);
-        assert(mi != wallet->mapWallet.end() && input.prevout.n < mi->second.tx->vout.size());
-        vCoins.emplace_back(CInputCoin(&(mi->second), input.prevout.n));
-    }
-    if (!wallet->DummySignTx(txNew, vCoins)) {
-        // This should never happen, because IsAllFromMe(ISMINE_SPENDABLE)
-        // implies that we can sign for every input.
-        return -1;
-    }
-    return GetVirtualTransactionSize(txNew);
-}
-
 //! Check whether transaction has descendant in wallet or mempool, or has been
 //! mined, or conflicts with a mined transaction. Return a feebumper::Result.
 static feebumper::Result PreconditionChecks(const CWallet* wallet, const CWalletTx& wtx, std::vector<std::string>& errors)