aboutsummaryrefslogtreecommitdiff
path: root/src/wallet/coinselection.cpp
diff options
context:
space:
mode:
authorAndrew Chow <achow101-github@achow101.com>2018-03-09 22:51:39 -0500
committerAndrew Chow <achow101-github@achow101.com>2018-03-13 12:39:26 -0400
commitfb716f7b25927e377f73b904a88ab67facfe3e55 (patch)
tree80dd5c4d3fb2c13031611f2ab5f11e23c8510e45 /src/wallet/coinselection.cpp
parent4566ab75f277612425337bf7786c1d3a410d894a (diff)
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.
Diffstat (limited to 'src/wallet/coinselection.cpp')
-rw-r--r--src/wallet/coinselection.cpp135
1 files changed, 135 insertions, 0 deletions
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 05bcdc12bb..8596ad2adc 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -163,3 +163,138 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va
return true;
}
+
+static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const CAmount& nTotalLower, const CAmount& nTargetValue,
+ std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
+{
+ std::vector<char> vfIncluded;
+
+ vfBest.assign(vValue.size(), true);
+ nBest = nTotalLower;
+
+ FastRandomContext insecure_rand;
+
+ for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
+ {
+ vfIncluded.assign(vValue.size(), false);
+ CAmount nTotal = 0;
+ bool fReachedTarget = false;
+ for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
+ {
+ for (unsigned int i = 0; i < vValue.size(); i++)
+ {
+ //The solver here uses a randomized algorithm,
+ //the randomness serves no real security purpose but is just
+ //needed to prevent degenerate behavior and it is important
+ //that the rng is fast. We do not use a constant random sequence,
+ //because there may be some privacy improvement by making
+ //the selection random.
+ if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
+ {
+ nTotal += vValue[i].txout.nValue;
+ vfIncluded[i] = true;
+ if (nTotal >= nTargetValue)
+ {
+ fReachedTarget = true;
+ if (nTotal < nBest)
+ {
+ nBest = nTotal;
+ vfBest = vfIncluded;
+ }
+ nTotal -= vValue[i].txout.nValue;
+ vfIncluded[i] = false;
+ }
+ }
+ }
+ }
+ }
+}
+
+bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet)
+{
+ setCoinsRet.clear();
+ nValueRet = 0;
+
+ // List of values less than target
+ boost::optional<CInputCoin> coinLowestLarger;
+ std::vector<CInputCoin> vValue;
+ CAmount nTotalLower = 0;
+
+ random_shuffle(vCoins.begin(), vCoins.end(), GetRandInt);
+
+ for (const CInputCoin &coin : vCoins)
+ {
+ if (coin.txout.nValue == nTargetValue)
+ {
+ setCoinsRet.insert(coin);
+ nValueRet += coin.txout.nValue;
+ return true;
+ }
+ else if (coin.txout.nValue < nTargetValue + MIN_CHANGE)
+ {
+ vValue.push_back(coin);
+ nTotalLower += coin.txout.nValue;
+ }
+ else if (!coinLowestLarger || coin.txout.nValue < coinLowestLarger->txout.nValue)
+ {
+ coinLowestLarger = coin;
+ }
+ }
+
+ if (nTotalLower == nTargetValue)
+ {
+ for (const auto& input : vValue)
+ {
+ setCoinsRet.insert(input);
+ nValueRet += input.txout.nValue;
+ }
+ return true;
+ }
+
+ if (nTotalLower < nTargetValue)
+ {
+ if (!coinLowestLarger)
+ return false;
+ setCoinsRet.insert(coinLowestLarger.get());
+ nValueRet += coinLowestLarger->txout.nValue;
+ return true;
+ }
+
+ // Solve subset sum by stochastic approximation
+ std::sort(vValue.begin(), vValue.end(), descending);
+ std::vector<char> vfBest;
+ CAmount nBest;
+
+ ApproximateBestSubset(vValue, nTotalLower, nTargetValue, vfBest, nBest);
+ if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE)
+ ApproximateBestSubset(vValue, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest);
+
+ // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
+ // or the next bigger coin is closer), return the bigger coin
+ if (coinLowestLarger &&
+ ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || coinLowestLarger->txout.nValue <= nBest))
+ {
+ setCoinsRet.insert(coinLowestLarger.get());
+ nValueRet += coinLowestLarger->txout.nValue;
+ }
+ else {
+ for (unsigned int i = 0; i < vValue.size(); i++)
+ if (vfBest[i])
+ {
+ setCoinsRet.insert(vValue[i]);
+ nValueRet += vValue[i].txout.nValue;
+ }
+
+ if (LogAcceptCategory(BCLog::SELECTCOINS)) {
+ LogPrint(BCLog::SELECTCOINS, "SelectCoins() best subset: ");
+ for (unsigned int i = 0; i < vValue.size(); i++) {
+ if (vfBest[i]) {
+ LogPrint(BCLog::SELECTCOINS, "%s ", FormatMoney(vValue[i].txout.nValue));
+ }
+ }
+ LogPrint(BCLog::SELECTCOINS, "total %s\n", FormatMoney(nBest));
+ }
+ }
+
+ return true;
+}