Differential D3289 Diff 9388 src/wallet/coinselection.cpp

Changeset View

Standalone View

src/wallet/coinselection.cpp

Show First 20 Lines • Show All 197 Lines • ▼ Show 20 Lines	for (size_t i = 0; i < best_selection.size(); ++i) {
if (best_selection.at(i)) {		if (best_selection.at(i)) {
out_set.insert(utxo_pool.at(i));		out_set.insert(utxo_pool.at(i));
value_ret += utxo_pool.at(i).txout.nValue;		value_ret += utxo_pool.at(i).txout.nValue;
}		}
}		}

return true;		return true;
}		}

		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 KnapsackSolver(const Amount nTargetValue, std::vector<CInputCoin> &vCoins,
		std::set<CInputCoin> &setCoinsRet, Amount &nValueRet) {
		setCoinsRet.clear();
		nValueRet = Amount::zero();

		// List of values less than target
		boost::optional<CInputCoin> coinLowestLarger;
		std::vector<CInputCoin> vValue;
		Amount nTotalLower = Amount::zero();

		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;
		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 (size_t 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;
		}