aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/wallet/coinselection.cpp135
-rw-r--r--src/wallet/coinselection.h2
-rw-r--r--src/wallet/wallet.cpp130
3 files changed, 140 insertions, 127 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;
+}
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index bbfa08a242..4d1a43bc17 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -49,4 +49,6 @@ public:
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
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
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-01 07:45:54 +0000