Changeset View
Changeset View
Standalone View
Standalone View
src/wallet/wallet.cpp
Show First 20 Lines • Show All 2,580 Lines • ▼ Show 20 Lines | while (IsChange(ptx->vout[n]) && ptx->vin.size() > 0) { | ||||
break; | break; | ||||
} | } | ||||
ptx = it->second.tx.get(); | ptx = it->second.tx.get(); | ||||
n = prevout.GetN(); | n = prevout.GetN(); | ||||
} | } | ||||
return ptx->vout[n]; | return ptx->vout[n]; | ||||
} | } | ||||
static void ApproximateBestSubset(const std::vector<CInputCoin> &vValue, | |||||
const Amount &nTotalLower, | |||||
const Amount &nTargetValue, | |||||
std::vector<char> &vfBest, Amount &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); | |||||
Amount nTotal = Amount::zero(); | |||||
bool fReachedTarget = false; | |||||
for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++) { | |||||
for (size_t 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( | bool CWallet::OutputEligibleForSpending( | ||||
const COutput &output, | const COutput &output, | ||||
const CoinEligibilityFilter &eligibility_filter) const { | const CoinEligibilityFilter &eligibility_filter) const { | ||||
if (!output.fSpendable) { | if (!output.fSpendable) { | ||||
return false; | return false; | ||||
} | } | ||||
if (output.nDepth < (output.tx->IsFromMe(ISMINE_ALL) | if (output.nDepth < (output.tx->IsFromMe(ISMINE_ALL) | ||||
Show All 12 Lines | |||||
bool CWallet::SelectCoinsMinConf( | bool CWallet::SelectCoinsMinConf( | ||||
const Amount nTargetValue, const CoinEligibilityFilter &eligibility_filter, | const Amount nTargetValue, const CoinEligibilityFilter &eligibility_filter, | ||||
std::vector<COutput> vCoins, std::set<CInputCoin> &setCoinsRet, | std::vector<COutput> vCoins, std::set<CInputCoin> &setCoinsRet, | ||||
Amount &nValueRet) const { | Amount &nValueRet) const { | ||||
setCoinsRet.clear(); | setCoinsRet.clear(); | ||||
nValueRet = Amount::zero(); | nValueRet = Amount::zero(); | ||||
// List of values less than target | std::vector<CInputCoin> utxo_pool; | ||||
boost::optional<CInputCoin> coinLowestLarger; | |||||
std::vector<CInputCoin> vValue; | |||||
Amount nTotalLower = Amount::zero(); | |||||
random_shuffle(vCoins.begin(), vCoins.end(), GetRandInt); | |||||
for (const COutput &output : vCoins) { | for (const COutput &output : vCoins) { | ||||
if (!OutputEligibleForSpending(output, eligibility_filter)) { | if (!OutputEligibleForSpending(output, eligibility_filter)) { | ||||
continue; | continue; | ||||
} | } | ||||
CInputCoin coin = CInputCoin(output.tx->tx, output.i); | CInputCoin coin = CInputCoin(output.tx->tx, output.i); | ||||
utxo_pool.push_back(coin); | |||||
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 (unsigned int i = 0; i < vValue.size(); ++i) { | |||||
setCoinsRet.insert(vValue[i]); | |||||
nValueRet += vValue[i].txout.nValue; | |||||
} | } | ||||
return KnapsackSolver(nTargetValue, utxo_pool, setCoinsRet, nValueRet); | |||||
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; | |||||
Amount 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 (size_t 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; | |||||
} | } | ||||
bool CWallet::SelectCoins(const std::vector<COutput> &vAvailableCoins, | bool CWallet::SelectCoins(const std::vector<COutput> &vAvailableCoins, | ||||
const Amount nTargetValue, | const Amount nTargetValue, | ||||
std::set<CInputCoin> &setCoinsRet, Amount &nValueRet, | std::set<CInputCoin> &setCoinsRet, Amount &nValueRet, | ||||
const CCoinControl *coinControl) const { | const CCoinControl *coinControl) const { | ||||
std::vector<COutput> vCoins(vAvailableCoins); | std::vector<COutput> vCoins(vAvailableCoins); | ||||
▲ Show 20 Lines • Show All 1,865 Lines • Show Last 20 Lines |