aboutsummaryrefslogtreecommitdiff
path: root/src/wallet/wallet.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/wallet/wallet.cpp')
-rw-r--r--src/wallet/wallet.cpp130
1 files changed, 3 insertions, 127 deletions
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index fbd515c47f..ae882d7bd2 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2438,52 +2438,6 @@ const CTxOut& CWallet::FindNonChangeParentOutput(const CTransaction& tx, int out
return ptx->vout[n];
}
-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 CWallet::OutputEligibleForSpending(const COutput& output, const CoinEligibilityFilter& eligibilty_filter) const
{
if (!output.fSpendable)
@@ -2504,94 +2458,16 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil
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);
-
+ std::vector<CInputCoin> utxo_pool;
for (const COutput &output : vCoins)
{
if (!OutputEligibleForSpending(output, eligibilty_filter))
continue;
CInputCoin coin = CInputCoin(output.tx->tx, output.i);
-
- 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(), CompareValueOnly());
- std::reverse(vValue.begin(), vValue.end());
- 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;
+ utxo_pool.push_back(coin);
}
- 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;
+ return KnapsackSolver(nTargetValue, utxo_pool, setCoinsRet, nValueRet);
}
bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CCoinControl* coinControl) const