From 1bf4a62cb61bd4b91d9cd4e379fea2b914786342 Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Thu, 6 May 2021 14:12:13 -0400 Subject: scripted-diff: rename some variables actual_target -> selection_target nChange -> change_and_fee -BEGIN VERIFY SCRIPT- sed -i -e 's/actual_target/selection_target/g' src/wallet/coinselection.cpp sed -i -e '2801,3691s/nChange /change_and_fee /g' src/wallet/wallet.cpp sed -i -e '2801,3691s/nChange,/change_and_fee,/g' src/wallet/wallet.cpp sed -i -e '2801,3691s/nChange;/change_and_fee;/g' src/wallet/wallet.cpp -END VERIFY SCRIPT- --- src/wallet/coinselection.cpp | 14 +++++++------- src/wallet/wallet.cpp | 10 +++++----- 2 files changed, 12 insertions(+), 12 deletions(-) diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 5a18308a73..2228536f29 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -70,7 +70,7 @@ bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& target_v std::vector curr_selection; // select the utxo at this index curr_selection.reserve(utxo_pool.size()); - CAmount actual_target = not_input_fees + target_value; + CAmount selection_target = not_input_fees + target_value; // Calculate curr_available_value CAmount curr_available_value = 0; @@ -79,7 +79,7 @@ bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& target_v assert(utxo.effective_value > 0); curr_available_value += utxo.effective_value; } - if (curr_available_value < actual_target) { + if (curr_available_value < selection_target) { return false; } @@ -94,12 +94,12 @@ bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& target_v for (size_t i = 0; i < TOTAL_TRIES; ++i) { // Conditions for starting a backtrack bool backtrack = false; - if (curr_value + curr_available_value < actual_target || // Cannot possibly reach target with the amount remaining in the curr_available_value. - curr_value > actual_target + cost_of_change || // Selected value is out of range, go back and try other branch + if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value. + curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch (curr_waste > best_waste && (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0)) { // Don't select things which we know will be more wasteful if the waste is increasing backtrack = true; - } else if (curr_value >= actual_target) { // Selected value is within range - curr_waste += (curr_value - actual_target); // This is the excess value which is added to the waste for the below comparison + } else if (curr_value >= selection_target) { // Selected value is within range + curr_waste += (curr_value - selection_target); // This is the excess value which is added to the waste for the below comparison // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee. // However we are not going to explore that because this optimization for the waste is only done when we have hit our target // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to @@ -112,7 +112,7 @@ bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& target_v break; } } - curr_waste -= (curr_value - actual_target); // Remove the excess value as we will be selecting different coins now + curr_waste -= (curr_value - selection_target); // Remove the excess value as we will be selecting different coins now backtrack = true; } diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 456c26ea31..35805bc4c9 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2990,19 +2990,19 @@ bool CWallet::CreateTransactionInternal( bnb_used = false; } - const CAmount nChange = nValueIn - nValueToSelect; - if (nChange > 0) + const CAmount change_and_fee = nValueIn - nValueToSelect; + if (change_and_fee > 0) { // Fill a vout to ourself - CTxOut newTxOut(nChange, scriptChange); + CTxOut newTxOut(change_and_fee, scriptChange); // Never create dust outputs; if we would, just // add the dust to the fee. - // The nChange when BnB is used is always going to go to fees. + // The change_and_fee when BnB is used is always going to go to fees. if (IsDust(newTxOut, coin_selection_params.m_discard_feerate) || bnb_used) { nChangePosInOut = -1; - nFeeRet += nChange; + nFeeRet += change_and_fee; } else { -- cgit v1.2.3 From af5867c89688b06173b295b7c32a42845ea455da Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Thu, 6 May 2021 13:52:28 -0400 Subject: Move some calculations to common code in SelectCoinsMinConf To prepare for KnapsackSolver to use effective values, these calculations are moved out of the BnB if block to allow for them to be shared with KnapsackSolver in the future. --- src/wallet/wallet.cpp | 32 +++++++++++++++++++------------- 1 file changed, 19 insertions(+), 13 deletions(-) diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 35805bc4c9..b6dc867dcb 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2399,24 +2399,30 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil setCoinsRet.clear(); nValueRet = 0; - if (coin_selection_params.use_bnb) { - // Get the feerate for effective value. - // When subtracting the fee from the outputs, we want the effective feerate to be 0 - CFeeRate effective_feerate{0}; - if (!coin_selection_params.m_subtract_fee_outputs) { - effective_feerate = coin_selection_params.m_effective_feerate; - } + // Calculate the fees for things that aren't inputs, excluding the change output + const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size); - std::vector groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, true /* positive_only */); + // Get the feerate for effective value. + // When subtracting the fee from the outputs, we want the effective feerate to be 0 + CFeeRate effective_feerate{0}; + if (!coin_selection_params.m_subtract_fee_outputs) { + effective_feerate = coin_selection_params.m_effective_feerate; + } - // Calculate cost of change - CAmount cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size); + // Cost of change is the cost of creating the change output + cost of spending the change output in the future. + // For creating the change output now, we use the effective feerate. + // For spending the change output in the future, we use the discard feerate for now. + // So cost of change = (change output size * effective feerate) + (size of spending change output * discard feerate) + const CAmount change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size); + const CAmount cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + change_fee; - // Calculate the fees for things that aren't inputs - CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size); + if (coin_selection_params.use_bnb) { + std::vector positive_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, true /* positive_only */); bnb_used = true; - return SelectCoinsBnB(groups, nTargetValue, cost_of_change, setCoinsRet, nValueRet, not_input_fees); + return SelectCoinsBnB(positive_groups, nTargetValue, cost_of_change, setCoinsRet, nValueRet, not_input_fees); } else { + // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here. + // The knapsack solver currently does not use effective values, so we give GroupOutputs feerates of 0 so it sets the effective values to be the same as the real value. std::vector groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, CFeeRate(0), CFeeRate(0), eligibility_filter, false /* positive_only */); bnb_used = false; -- cgit v1.2.3 From d97d25d95006725e705635530b27643363d6b2a4 Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Fri, 7 May 2021 18:13:40 -0400 Subject: Make cost_of_change part of CoinSelectionParams --- src/wallet/wallet.cpp | 35 +++++++++++++++++++---------------- src/wallet/wallet.h | 4 ++++ 2 files changed, 23 insertions(+), 16 deletions(-) diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index b6dc867dcb..e848145a51 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2409,17 +2409,10 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil effective_feerate = coin_selection_params.m_effective_feerate; } - // Cost of change is the cost of creating the change output + cost of spending the change output in the future. - // For creating the change output now, we use the effective feerate. - // For spending the change output in the future, we use the discard feerate for now. - // So cost of change = (change output size * effective feerate) + (size of spending change output * discard feerate) - const CAmount change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size); - const CAmount cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + change_fee; - if (coin_selection_params.use_bnb) { std::vector positive_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, true /* positive_only */); bnb_used = true; - return SelectCoinsBnB(positive_groups, nTargetValue, cost_of_change, setCoinsRet, nValueRet, not_input_fees); + return SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, setCoinsRet, nValueRet, not_input_fees); } else { // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here. // The knapsack solver currently does not use effective values, so we give GroupOutputs feerates of 0 so it sets the effective values to be the same as the real value. @@ -2885,6 +2878,16 @@ bool CWallet::CreateTransactionInternal( CTxOut change_prototype_txout(0, scriptChange); coin_selection_params.change_output_size = GetSerializeSize(change_prototype_txout); + // Get size of spending the change output + int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this); + // If the wallet doesn't know how to sign change output, assume p2sh-p2wpkh + // as lower-bound to allow BnB to do it's thing + if (change_spend_size == -1) { + coin_selection_params.change_spend_size = DUMMY_NESTED_P2WPKH_INPUT_SIZE; + } else { + coin_selection_params.change_spend_size = (size_t)change_spend_size; + } + // Set discard feerate coin_selection_params.m_discard_feerate = GetDiscardRate(*this); @@ -2907,6 +2910,14 @@ bool CWallet::CreateTransactionInternal( cc_temp.m_confirm_target = chain().estimateMaxBlocks(); coin_selection_params.m_long_term_feerate = GetMinimumFeeRate(*this, cc_temp, nullptr); + // Calculate the cost of change + // Cost of change is the cost of creating the change output + cost of spending the change output in the future. + // For creating the change output now, we use the effective feerate. + // For spending the change output in the future, we use the discard feerate for now. + // So cost of change = (change output size * effective feerate) + (size of spending change output * discard feerate) + coin_selection_params.m_change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size); + coin_selection_params.m_cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + coin_selection_params.m_change_fee; + nFeeRet = 0; bool pick_new_inputs = true; CAmount nValueIn = 0; @@ -2972,14 +2983,6 @@ bool CWallet::CreateTransactionInternal( if (pick_new_inputs) { nValueIn = 0; setCoins.clear(); - int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this); - // If the wallet doesn't know how to sign change output, assume p2sh-p2wpkh - // as lower-bound to allow BnB to do it's thing - if (change_spend_size == -1) { - coin_selection_params.change_spend_size = DUMMY_NESTED_P2WPKH_INPUT_SIZE; - } else { - coin_selection_params.change_spend_size = (size_t)change_spend_size; - } if (!SelectCoins(vAvailableCoins, nValueToSelect, setCoins, nValueIn, coin_control, coin_selection_params, bnb_used)) { // If BnB was used, it was the first pass. No longer the first pass and continue loop with knapsack. diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h index 5a36d92784..242aea6715 100644 --- a/src/wallet/wallet.h +++ b/src/wallet/wallet.h @@ -621,6 +621,10 @@ struct CoinSelectionParams size_t change_output_size = 0; /** Size of the input to spend a change output in virtual bytes. */ size_t change_spend_size = 0; + /** Cost of creating the change output. */ + CAmount m_change_fee{0}; + /** Cost of creating the change output + cost of spending the change output in the future. */ + CAmount m_cost_of_change{0}; /** The targeted feerate of the transaction being built. */ CFeeRate m_effective_feerate; /** The feerate estimate used to estimate an upper bound on what should be sufficient to spend -- cgit v1.2.3 From cc3f14b27c06b7a0da1472f5c7100c3f0b76fd98 Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Fri, 7 May 2021 20:53:48 -0400 Subject: Move output reductions for fee to after coin selection Simplifies CreateTransactionInternal without changing behavior. Removes the pick_new_inputs variable by moving the subtract fee from amount implementation to later in the loop to where it is possible to calculate the fee for the transaction. This allows the fee to be subtracted from the outputs within a single iteration, instead of calculating the fee in the first iteration, and subtracting the fee in the second. This also removes another scenario where a second iteration of the loop finds a smaller input set (and thus smaller fees than the first iteration) with no change and so a third iteration of the loop is done in order to make a change output that contains the excess fees. To handle these cases, we always create a change output which contains the difference between selected input values and the recipient amounts. Once the transaction fee is calculated, the change output is reduced (in the normal case) or the recipient amounts are reduced (in the subtract fee from amount case). All of this is done in a single iteration of the loop. --- src/wallet/wallet.cpp | 224 +++++++++++++++++++++----------------------------- 1 file changed, 94 insertions(+), 130 deletions(-) diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index e848145a51..51ff683c2e 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2834,7 +2834,6 @@ bool CWallet::CreateTransactionInternal( CMutableTransaction txNew; FeeCalculation feeCalc; - CAmount nFeeNeeded; std::pair tx_sizes; int nBytes; { @@ -2919,7 +2918,6 @@ bool CWallet::CreateTransactionInternal( coin_selection_params.m_cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + coin_selection_params.m_change_fee; nFeeRet = 0; - bool pick_new_inputs = true; CAmount nValueIn = 0; // BnB selector is the only selector used when this is true. @@ -2932,7 +2930,6 @@ bool CWallet::CreateTransactionInternal( nChangePosInOut = nChangePosRequest; txNew.vin.clear(); txNew.vout.clear(); - bool fFirst = true; CAmount nValueToSelect = nValue; if (nSubtractFeeFromAmount == 0) @@ -2946,33 +2943,14 @@ bool CWallet::CreateTransactionInternal( { CTxOut txout(recipient.nAmount, recipient.scriptPubKey); - if (recipient.fSubtractFeeFromAmount) - { - assert(nSubtractFeeFromAmount != 0); - txout.nValue -= nFeeRet / nSubtractFeeFromAmount; // Subtract fee equally from each selected recipient - - if (fFirst) // first receiver pays the remainder not divisible by output count - { - fFirst = false; - txout.nValue -= nFeeRet % nSubtractFeeFromAmount; - } - } - // Include the fee cost for outputs. Note this is only used for BnB right now + // Include the fee cost for outputs. if (!coin_selection_params.m_subtract_fee_outputs) { coin_selection_params.tx_noinputs_size += ::GetSerializeSize(txout, PROTOCOL_VERSION); } if (IsDust(txout, chain().relayDustFee())) { - if (recipient.fSubtractFeeFromAmount && nFeeRet > 0) - { - if (txout.nValue < 0) - error = _("The transaction amount is too small to pay the fee"); - else - error = _("The transaction amount is too small to send after the fee has been deducted"); - } - else - error = _("Transaction amount too small"); + error = _("Transaction amount too small"); return false; } txNew.vout.push_back(txout); @@ -2980,58 +2958,40 @@ bool CWallet::CreateTransactionInternal( // Choose coins to use bool bnb_used = false; - if (pick_new_inputs) { - nValueIn = 0; - setCoins.clear(); - if (!SelectCoins(vAvailableCoins, nValueToSelect, setCoins, nValueIn, coin_control, coin_selection_params, bnb_used)) - { - // If BnB was used, it was the first pass. No longer the first pass and continue loop with knapsack. - if (bnb_used) { - coin_selection_params.use_bnb = false; - continue; - } - else { - error = _("Insufficient funds"); - return false; - } + nValueIn = 0; + setCoins.clear(); + if (!SelectCoins(vAvailableCoins, nValueToSelect, setCoins, nValueIn, coin_control, coin_selection_params, bnb_used)) + { + // If BnB was used, it was the first pass. No longer the first pass and continue loop with knapsack. + if (bnb_used) { + coin_selection_params.use_bnb = false; + continue; + } + else { + error = _("Insufficient funds"); + return false; } - } else { - bnb_used = false; } - const CAmount change_and_fee = nValueIn - nValueToSelect; - if (change_and_fee > 0) - { - // Fill a vout to ourself - CTxOut newTxOut(change_and_fee, scriptChange); - - // Never create dust outputs; if we would, just - // add the dust to the fee. - // The change_and_fee when BnB is used is always going to go to fees. - if (IsDust(newTxOut, coin_selection_params.m_discard_feerate) || bnb_used) - { - nChangePosInOut = -1; - nFeeRet += change_and_fee; - } - else - { - if (nChangePosInOut == -1) - { - // Insert change txn at random position: - nChangePosInOut = GetRandInt(txNew.vout.size()+1); - } - else if ((unsigned int)nChangePosInOut > txNew.vout.size()) - { - error = _("Change index out of range"); - return false; - } + // Always make a change output + // We will reduce the fee from this change output later, and remove the output if it is too small. + const CAmount change_and_fee = nValueIn - nValue; + assert(change_and_fee >= 0); + CTxOut newTxOut(change_and_fee, scriptChange); - std::vector::iterator position = txNew.vout.begin()+nChangePosInOut; - txNew.vout.insert(position, newTxOut); - } - } else { - nChangePosInOut = -1; + if (nChangePosInOut == -1) + { + // Insert change txn at random position: + nChangePosInOut = GetRandInt(txNew.vout.size()+1); } + else if ((unsigned int)nChangePosInOut > txNew.vout.size()) + { + error = _("Change index out of range"); + return false; + } + + assert(nChangePosInOut != -1); + auto change_position = txNew.vout.insert(txNew.vout.begin() + nChangePosInOut, newTxOut); // Dummy fill vin for maximum size estimation // @@ -3039,76 +2999,80 @@ bool CWallet::CreateTransactionInternal( txNew.vin.push_back(CTxIn(coin.outpoint,CScript())); } + // Calculate the transaction fee tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly); nBytes = tx_sizes.first; if (nBytes < 0) { error = _("Signing transaction failed"); return false; } + nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes); - nFeeNeeded = coin_selection_params.m_effective_feerate.GetFee(nBytes); - if (nFeeRet >= nFeeNeeded) { - // Reduce fee to only the needed amount if possible. This - // prevents potential overpayment in fees if the coins - // selected to meet nFeeNeeded result in a transaction that - // requires less fee than the prior iteration. - - // If we have no change and a big enough excess fee, then - // try to construct transaction again only without picking - // new inputs. We now know we only need the smaller fee - // (because of reduced tx size) and so we should add a - // change output. Only try this once. - if (nChangePosInOut == -1 && nSubtractFeeFromAmount == 0 && pick_new_inputs) { - unsigned int tx_size_with_change = nBytes + coin_selection_params.change_output_size + 2; // Add 2 as a buffer in case increasing # of outputs changes compact size - CAmount fee_needed_with_change = coin_selection_params.m_effective_feerate.GetFee(tx_size_with_change); - CAmount minimum_value_for_change = GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate); - if (nFeeRet >= fee_needed_with_change + minimum_value_for_change) { - pick_new_inputs = false; - nFeeRet = fee_needed_with_change; - continue; - } - } - - // If we have change output already, just increase it - if (nFeeRet > nFeeNeeded && nChangePosInOut != -1 && nSubtractFeeFromAmount == 0) { - CAmount extraFeePaid = nFeeRet - nFeeNeeded; - std::vector::iterator change_position = txNew.vout.begin()+nChangePosInOut; - change_position->nValue += extraFeePaid; - nFeeRet -= extraFeePaid; - } - break; // Done, enough fee included. - } - else if (!pick_new_inputs) { - // This shouldn't happen, we should have had enough excess - // fee to pay for the new output and still meet nFeeNeeded - // Or we should have just subtracted fee from recipients and - // nFeeNeeded should not have changed - error = _("Transaction fee and change calculation failed"); - return false; + // Subtract fee from the change output if not subtrating it from recipient outputs + CAmount fee_needed = nFeeRet; + if (nSubtractFeeFromAmount == 0) { + change_position->nValue -= fee_needed; } - // Try to reduce change to include necessary fee - if (nChangePosInOut != -1 && nSubtractFeeFromAmount == 0) { - CAmount additionalFeeNeeded = nFeeNeeded - nFeeRet; - std::vector::iterator change_position = txNew.vout.begin()+nChangePosInOut; - // Only reduce change if remaining amount is still a large enough output. - if (change_position->nValue >= MIN_FINAL_CHANGE + additionalFeeNeeded) { - change_position->nValue -= additionalFeeNeeded; - nFeeRet += additionalFeeNeeded; - break; // Done, able to increase fee from change - } + // We want to drop the change to fees if: + // 1. The change output would be dust + // 2. The change is within the (almost) exact match window, i.e. it is less than or equal to the cost of the change output (cost_of_change) + CAmount change_amount = change_position->nValue; + if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_amount <= coin_selection_params.m_cost_of_change) + { + nChangePosInOut = -1; + change_amount = 0; + txNew.vout.erase(change_position); + + // Because we have dropped this change, the tx size and required fee will be different, so let's recalculate those + tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly); + nBytes = tx_sizes.first; + fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes); } - // If subtracting fee from recipients, we now know what fee we - // need to subtract, we have no reason to reselect inputs - if (nSubtractFeeFromAmount > 0) { - pick_new_inputs = false; + // If the fee is covered, there's no need to loop or subtract from recipients + if (fee_needed <= change_and_fee - change_amount) { + nFeeRet = change_and_fee - change_amount; + break; } - // Include more fee and try again. - nFeeRet = nFeeNeeded; - coin_selection_params.use_bnb = false; - continue; + // Reduce output values for subtractFeeFromAmount + if (nSubtractFeeFromAmount != 0) { + CAmount to_reduce = fee_needed + change_amount - change_and_fee; + int i = 0; + bool fFirst = true; + for (const auto& recipient : vecSend) + { + if (i == nChangePosInOut) { + ++i; + } + CTxOut& txout = txNew.vout[i]; + + if (recipient.fSubtractFeeFromAmount) + { + txout.nValue -= to_reduce / nSubtractFeeFromAmount; // Subtract fee equally from each selected recipient + + if (fFirst) // first receiver pays the remainder not divisible by output count + { + fFirst = false; + txout.nValue -= to_reduce % nSubtractFeeFromAmount; + } + + // Error if this output is reduced to be below dust + if (IsDust(txout, chain().relayDustFee())) { + if (txout.nValue < 0) { + error = _("The transaction amount is too small to pay the fee"); + } else { + error = _("The transaction amount is too small to send after the fee has been deducted"); + } + return false; + } + } + ++i; + } + nFeeRet = fee_needed; + break; // The fee has been deducted from the recipients, nothing left to do here + } } // Give up if change keypool ran out and change is required @@ -3170,8 +3134,8 @@ bool CWallet::CreateTransactionInternal( reservedest.KeepDestination(); fee_calc_out = feeCalc; - WalletLogPrintf("Fee Calculation: Fee:%d Bytes:%u Needed:%d Tgt:%d (requested %d) Reason:\"%s\" Decay %.5f: Estimation: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n", - nFeeRet, nBytes, nFeeNeeded, feeCalc.returnedTarget, feeCalc.desiredTarget, StringForFeeReason(feeCalc.reason), feeCalc.est.decay, + WalletLogPrintf("Fee Calculation: Fee:%d Bytes:%u Tgt:%d (requested %d) Reason:\"%s\" Decay %.5f: Estimation: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n", + nFeeRet, nBytes, feeCalc.returnedTarget, feeCalc.desiredTarget, StringForFeeReason(feeCalc.reason), feeCalc.est.decay, feeCalc.est.pass.start, feeCalc.est.pass.end, (feeCalc.est.pass.totalConfirmed + feeCalc.est.pass.inMempool + feeCalc.est.pass.leftMempool) > 0.0 ? 100 * feeCalc.est.pass.withinTarget / (feeCalc.est.pass.totalConfirmed + feeCalc.est.pass.inMempool + feeCalc.est.pass.leftMempool) : 0.0, feeCalc.est.pass.withinTarget, feeCalc.est.pass.totalConfirmed, feeCalc.est.pass.inMempool, feeCalc.est.pass.leftMempool, -- cgit v1.2.3 From bf26e018de33216d6f0ed0d6ff822b93536f7cc1 Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Wed, 30 Oct 2019 18:41:13 -0400 Subject: Roll static tx fees into nValueToSelect instead of having it be separate The fees for transaction overhead and recipient outputs are now included in nTargetValue instead of being a separate parameter. For the coin selection algorithms, it doesn't matter that these are separate as in either case, the algorithm needs to select enough to cover these fees. Note that setting nValueToSelect is changed as it now includes not_input_fees. Without the change to how nValueToSelect is increased for KnapsackSolver, this would result in overpaying fees. The change to increase by the difference between nFeeRet and not_input_fees allows this to have the same behavior as previously. Additionally, because we assume that KnapsackSolver will always find a solution that requires change (we assume that BnB always finds a non-change solution), we also include the fee for the change output in KnapsackSolver's target. As part of this, we also use the changeless nFeeRet when iterating for KnapsackSolver. This is because we include the change fee when doing KnapsackSolver, so nFeeRet on further iterations won't include the change fee. --- src/bench/coin_selection.cpp | 3 +-- src/wallet/coinselection.cpp | 9 +++------ src/wallet/coinselection.h | 2 +- src/wallet/test/coinselector_tests.cpp | 29 ++++++++++++++--------------- src/wallet/wallet.cpp | 26 ++++++++++++++++---------- 5 files changed, 35 insertions(+), 34 deletions(-) diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index 80acdec044..b42939ffdc 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -101,12 +101,11 @@ static void BnBExhaustion(benchmark::Bench& bench) std::vector utxo_pool; CoinSet selection; CAmount value_ret = 0; - CAmount not_input_fees = 0; bench.run([&] { // Benchmark CAmount target = make_hard_case(17, utxo_pool); - SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret, not_input_fees); // Should exhaust + SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret); // Should exhaust // Cleanup utxo_pool.clear(); diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 2228536f29..db770f6a45 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -49,28 +49,25 @@ struct { * @param const std::vector& utxo_pool The set of UTXOs that we are choosing from. * These UTXOs will be sorted in descending order by effective value and the CInputCoins' * values are their effective values. - * @param const CAmount& target_value This is the value that we want to select. It is the lower + * @param const CAmount& selection_target This is the value that we want to select. It is the lower * bound of the range. * @param const CAmount& cost_of_change This is the cost of creating and spending a change output. - * This plus target_value is the upper bound of the range. + * This plus selection_target is the upper bound of the range. * @param std::set& out_set -> This is an output parameter for the set of CInputCoins * that have been selected. * @param CAmount& value_ret -> This is an output parameter for the total value of the CInputCoins * that were selected. - * @param CAmount not_input_fees -> The fees that need to be paid for the outputs and fixed size - * overhead (version, locktime, marker and flag) */ static const size_t TOTAL_TRIES = 100000; -bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set& out_set, CAmount& value_ret, CAmount not_input_fees) +bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set& out_set, CAmount& value_ret) { out_set.clear(); CAmount curr_value = 0; std::vector curr_selection; // select the utxo at this index curr_selection.reserve(utxo_pool.size()); - CAmount selection_target = not_input_fees + target_value; // Calculate curr_available_value CAmount curr_available_value = 0; diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index 5645e6db46..af23178d04 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -120,7 +120,7 @@ struct OutputGroup bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const; }; -bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set& out_set, CAmount& value_ret, CAmount not_input_fees); +bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set& out_set, CAmount& value_ret); // Original coin selection algorithm as a fallback bool KnapsackSolver(const CAmount& nTargetValue, std::vector& groups, std::set& setCoinsRet, CAmount& nValueRet); diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index 7eff6e592d..1a2454479d 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -148,14 +148,13 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) CoinSet selection; CoinSet actual_selection; CAmount value_ret = 0; - CAmount not_input_fees = 0; ///////////////////////// // Known Outcome tests // ///////////////////////// // Empty utxo pool - BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees)); + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret)); selection.clear(); // Add utxos @@ -166,7 +165,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) // Select 1 Cent add_coin(1 * CENT, 1, actual_selection); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees)); + BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret)); BOOST_CHECK(equal_sets(selection, actual_selection)); BOOST_CHECK_EQUAL(value_ret, 1 * CENT); actual_selection.clear(); @@ -174,7 +173,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) // Select 2 Cent add_coin(2 * CENT, 2, actual_selection); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 2 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees)); + BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 2 * CENT, 0.5 * CENT, selection, value_ret)); BOOST_CHECK(equal_sets(selection, actual_selection)); BOOST_CHECK_EQUAL(value_ret, 2 * CENT); actual_selection.clear(); @@ -183,27 +182,27 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) // Select 5 Cent add_coin(4 * CENT, 4, actual_selection); add_coin(1 * CENT, 1, actual_selection); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees)); + BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, 0.5 * CENT, selection, value_ret)); BOOST_CHECK(equal_sets(selection, actual_selection)); BOOST_CHECK_EQUAL(value_ret, 5 * CENT); actual_selection.clear(); selection.clear(); // Select 11 Cent, not possible - BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees)); + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT, selection, value_ret)); actual_selection.clear(); selection.clear(); // Cost of change is greater than the difference between target value and utxo sum add_coin(1 * CENT, 1, actual_selection); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees)); + BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0.5 * CENT, selection, value_ret)); BOOST_CHECK_EQUAL(value_ret, 1 * CENT); BOOST_CHECK(equal_sets(selection, actual_selection)); actual_selection.clear(); selection.clear(); // Cost of change is less than the difference between target value and utxo sum - BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0, selection, value_ret, not_input_fees)); + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0, selection, value_ret)); actual_selection.clear(); selection.clear(); @@ -212,7 +211,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) add_coin(5 * CENT, 5, actual_selection); add_coin(4 * CENT, 4, actual_selection); add_coin(1 * CENT, 1, actual_selection); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees)); + BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 0.5 * CENT, selection, value_ret)); BOOST_CHECK(equal_sets(selection, actual_selection)); BOOST_CHECK_EQUAL(value_ret, 10 * CENT); actual_selection.clear(); @@ -223,21 +222,21 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) add_coin(5 * CENT, 5, actual_selection); add_coin(3 * CENT, 3, actual_selection); add_coin(2 * CENT, 2, actual_selection); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 5000, selection, value_ret, not_input_fees)); + BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 5000, selection, value_ret)); BOOST_CHECK_EQUAL(value_ret, 10 * CENT); // FIXME: this test is redundant with the above, because 1 Cent is selected, not "too small" // BOOST_CHECK(equal_sets(selection, actual_selection)); // Select 0.25 Cent, not possible - BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.25 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees)); + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.25 * CENT, 0.5 * CENT, selection, value_ret)); actual_selection.clear(); selection.clear(); // Iteration exhaustion test CAmount target = make_hard_case(17, utxo_pool); - BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret, not_input_fees)); // Should exhaust + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret)); // Should exhaust target = make_hard_case(14, utxo_pool); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret, not_input_fees)); // Should not exhaust + BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret)); // Should not exhaust // Test same value early bailout optimization utxo_pool.clear(); @@ -254,7 +253,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) for (int i = 0; i < 50000; ++i) { add_coin(5 * CENT, 7, utxo_pool); } - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 30 * CENT, 5000, selection, value_ret, not_input_fees)); + BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 30 * CENT, 5000, selection, value_ret)); BOOST_CHECK_EQUAL(value_ret, 30 * CENT); BOOST_CHECK(equal_sets(selection, actual_selection)); @@ -268,7 +267,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) } // Run 100 times, to make sure it is never finding a solution for (int i = 0; i < 100; ++i) { - BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 2 * CENT, selection, value_ret, not_input_fees)); + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 2 * CENT, selection, value_ret)); } // Make sure that effective value is working in SelectCoinsMinConf when BnB is used diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 51ff683c2e..3383b3e96b 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2399,9 +2399,6 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil setCoinsRet.clear(); nValueRet = 0; - // Calculate the fees for things that aren't inputs, excluding the change output - const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size); - // Get the feerate for effective value. // When subtracting the fee from the outputs, we want the effective feerate to be 0 CFeeRate effective_feerate{0}; @@ -2412,14 +2409,17 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil if (coin_selection_params.use_bnb) { std::vector positive_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, true /* positive_only */); bnb_used = true; - return SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, setCoinsRet, nValueRet, not_input_fees); + // Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output. + return SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, setCoinsRet, nValueRet); } else { // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here. // The knapsack solver currently does not use effective values, so we give GroupOutputs feerates of 0 so it sets the effective values to be the same as the real value. std::vector groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, CFeeRate(0), CFeeRate(0), eligibility_filter, false /* positive_only */); bnb_used = false; - return KnapsackSolver(nTargetValue, groups, setCoinsRet, nValueRet); + // While nTargetValue includes the transaction fees for non-input things, it does not include the fee for creating a change output. + // So we need to include that for KnapsackSolver as well, as we are expecting to create a change output. + return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, groups, setCoinsRet, nValueRet); } } @@ -2931,10 +2931,6 @@ bool CWallet::CreateTransactionInternal( txNew.vin.clear(); txNew.vout.clear(); - CAmount nValueToSelect = nValue; - if (nSubtractFeeFromAmount == 0) - nValueToSelect += nFeeRet; - // vouts to the payees if (!coin_selection_params.m_subtract_fee_outputs) { coin_selection_params.tx_noinputs_size = 11; // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 output count, 1 witness overhead (dummy, flag, stack size) @@ -2956,11 +2952,21 @@ bool CWallet::CreateTransactionInternal( txNew.vout.push_back(txout); } + // Include the fees for things that aren't inputs, excluding the change output + const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size); + CAmount nValueToSelect = nValue + not_input_fees; + + // For KnapsackSolver, when we are not subtracting the fee from the recipients, we also want to include the fees for the + // inputs that we found in the previous iteration. + if (!coin_selection_params.use_bnb && nSubtractFeeFromAmount == 0) { + nValueToSelect += std::max(CAmount(0), nFeeRet - not_input_fees); + } + // Choose coins to use bool bnb_used = false; nValueIn = 0; setCoins.clear(); - if (!SelectCoins(vAvailableCoins, nValueToSelect, setCoins, nValueIn, coin_control, coin_selection_params, bnb_used)) + if (!SelectCoins(vAvailableCoins, /* nTargetValue */ nValueToSelect, setCoins, nValueIn, coin_control, coin_selection_params, bnb_used)) { // If BnB was used, it was the first pass. No longer the first pass and continue loop with knapsack. if (bnb_used) { -- cgit v1.2.3 From 01dc8ebda50a382d45d3d169b2c3f3965869dcae Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Thu, 6 May 2021 13:54:22 -0400 Subject: Have KnapsackSolver actually use effective values Although the CreateTransaction loop currently remains, it should be largely unused. KnapsackSolver will now account for transaction fees when doing its selection. In the previous commit, SelectCoinsMinConf was refactored to have some calculations become shared for KnapsackSolver and SelectCoinsBnB. In this commit, KnapsackSolver will now use the not_input_fees and effective_feerate so that it include the fee for non-input things (excluding a change output) so that the algorithm will select enough to cover those fees. This is necessary for selecting on effective values. Additionally, the OutputGroups created for KnapsackSolver will actually have their effective values calculated and set, and KnapsackSolver will do its selection on those effective values. Lastly, SelectCoins is modified to use the same value for preselected inputs for BnB and KnapsackSolver. While it will still use the real value when subtracting the fee from outputs, this behavior will be the same regardless of the algo used for selecting additional inputs. --- src/wallet/coinselection.cpp | 10 +++++----- src/wallet/wallet.cpp | 18 +++++------------- 2 files changed, 10 insertions(+), 18 deletions(-) diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index db770f6a45..af88bf85dd 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -227,14 +227,14 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector& group Shuffle(groups.begin(), groups.end(), FastRandomContext()); for (const OutputGroup& group : groups) { - if (group.m_value == nTargetValue) { + if (group.effective_value == nTargetValue) { util::insert(setCoinsRet, group.m_outputs); nValueRet += group.m_value; return true; - } else if (group.m_value < nTargetValue + MIN_CHANGE) { + } else if (group.effective_value < nTargetValue + MIN_CHANGE) { applicable_groups.push_back(group); - nTotalLower += group.m_value; - } else if (!lowest_larger || group.m_value < lowest_larger->m_value) { + nTotalLower += group.effective_value; + } else if (!lowest_larger || group.effective_value < lowest_larger->effective_value) { lowest_larger = group; } } @@ -267,7 +267,7 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector& group // 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 (lowest_larger && - ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->m_value <= nBest)) { + ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->effective_value <= nBest)) { util::insert(setCoinsRet, lowest_larger->m_outputs); nValueRet += lowest_larger->m_value; } else { diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 3383b3e96b..b229d8ad63 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2413,13 +2413,11 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil return SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, setCoinsRet, nValueRet); } else { // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here. - // The knapsack solver currently does not use effective values, so we give GroupOutputs feerates of 0 so it sets the effective values to be the same as the real value. - std::vector groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, CFeeRate(0), CFeeRate(0), eligibility_filter, false /* positive_only */); - + std::vector all_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, false /* positive_only */); bnb_used = false; // While nTargetValue includes the transaction fees for non-input things, it does not include the fee for creating a change output. // So we need to include that for KnapsackSolver as well, as we are expecting to create a change output. - return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, groups, setCoinsRet, nValueRet); + return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, setCoinsRet, nValueRet); } } @@ -2467,10 +2465,10 @@ bool CWallet::SelectCoins(const std::vector& vAvailableCoins, const CAm return false; // Not solvable, can't estimate size for fee } coin.effective_value = coin.txout.nValue - coin_selection_params.m_effective_feerate.GetFee(coin.m_input_bytes); - if (coin_selection_params.use_bnb) { - value_to_select -= coin.effective_value; - } else { + if (coin_selection_params.m_subtract_fee_outputs) { value_to_select -= coin.txout.nValue; + } else { + value_to_select -= coin.effective_value; } setPresetCoins.insert(coin); } else { @@ -2956,12 +2954,6 @@ bool CWallet::CreateTransactionInternal( const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size); CAmount nValueToSelect = nValue + not_input_fees; - // For KnapsackSolver, when we are not subtracting the fee from the recipients, we also want to include the fees for the - // inputs that we found in the previous iteration. - if (!coin_selection_params.use_bnb && nSubtractFeeFromAmount == 0) { - nValueToSelect += std::max(CAmount(0), nFeeRet - not_input_fees); - } - // Choose coins to use bool bnb_used = false; nValueIn = 0; -- cgit v1.2.3 From de26eb0e1fa2b6f03c58ba104d00f7a8ffead39c Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Wed, 30 Oct 2019 16:08:55 -0400 Subject: Do both BnB and Knapsack coin selection in SelectCoinsMinConf Instead of switching which algorithm to use based on use_bnb, just run both in SelectCoinsMinConf. If BnB fails, do Knapsack. --- src/wallet/test/coinselector_tests.cpp | 22 +++++++++++----------- src/wallet/wallet.cpp | 21 ++++++++++----------- 2 files changed, 21 insertions(+), 22 deletions(-) diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index 1a2454479d..55b73cd1f0 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -287,9 +287,9 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) empty_wallet(); add_coin(1 * CENT); vCoins.at(0).nInputBytes = 40; - BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used)); coin_selection_params_bnb.m_subtract_fee_outputs = true; BOOST_CHECK(testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used)); + BOOST_CHECK(bnb_used); BOOST_CHECK_EQUAL(nValueRet, 1 * CENT); // Make sure that can use BnB when there are preset inputs @@ -549,17 +549,19 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) for (int i = 0; i < RUN_TESTS; i++) { // picking 50 from 100 coins doesn't depend on the shuffle, // but does depend on randomness in the stochastic approximation code - BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used)); - BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(KnapsackSolver(50 * COIN, GroupCoins(vCoins), setCoinsRet, nValueRet)); + BOOST_CHECK(KnapsackSolver(50 * COIN, GroupCoins(vCoins), setCoinsRet2, nValueRet)); BOOST_CHECK(!equal_sets(setCoinsRet, setCoinsRet2)); int fails = 0; for (int j = 0; j < RANDOM_REPEATS; j++) { - // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time - // run the test RANDOM_REPEATS times and only complain if all of them fail - BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used)); - BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used)); + // Test that the KnapsackSolver selects randomly from equivalent coins (same value and same input size). + // When choosing 1 from 100 identical coins, 1% of the time, this test will choose the same coin twice + // which will cause it to fail. + // To avoid that issue, run the test RANDOM_REPEATS times and only complain if all of them fail + BOOST_CHECK(KnapsackSolver(COIN, GroupCoins(vCoins), setCoinsRet, nValueRet)); + BOOST_CHECK(KnapsackSolver(COIN, GroupCoins(vCoins), setCoinsRet2, nValueRet)); if (equal_sets(setCoinsRet, setCoinsRet2)) fails++; } @@ -579,10 +581,8 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) int fails = 0; for (int j = 0; j < RANDOM_REPEATS; j++) { - // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time - // run the test RANDOM_REPEATS times and only complain if all of them fail - BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used)); - BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(KnapsackSolver(90*CENT, GroupCoins(vCoins), setCoinsRet, nValueRet)); + BOOST_CHECK(KnapsackSolver(90*CENT, GroupCoins(vCoins), setCoinsRet2, nValueRet)); if (equal_sets(setCoinsRet, setCoinsRet2)) fails++; } diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index b229d8ad63..a5b9c844c7 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2406,19 +2406,18 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil effective_feerate = coin_selection_params.m_effective_feerate; } - if (coin_selection_params.use_bnb) { - std::vector positive_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, true /* positive_only */); + std::vector positive_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, true /* positive_only */); + // Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output. + if (SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, setCoinsRet, nValueRet)) { bnb_used = true; - // Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output. - return SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, setCoinsRet, nValueRet); - } else { - // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here. - std::vector all_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, false /* positive_only */); - bnb_used = false; - // While nTargetValue includes the transaction fees for non-input things, it does not include the fee for creating a change output. - // So we need to include that for KnapsackSolver as well, as we are expecting to create a change output. - return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, setCoinsRet, nValueRet); + return true; } + // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here. + std::vector all_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, false /* positive_only */); + bnb_used = false; + // While nTargetValue includes the transaction fees for non-input things, it does not include the fee for creating a change output. + // So we need to include that for KnapsackSolver as well, as we are expecting to create a change output. + return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, setCoinsRet, nValueRet); } bool CWallet::SelectCoins(const std::vector& vAvailableCoins, const CAmount& nTargetValue, std::set& setCoinsRet, CAmount& nValueRet, const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params, bool& bnb_used) const -- cgit v1.2.3 From 6f0d5189af4c881fe8b97a0c28ce1ffa33480715 Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Wed, 30 Oct 2019 16:28:46 -0400 Subject: Remove use_bnb and bnb_used These booleans are no longer needed --- src/bench/coin_selection.cpp | 5 +- src/wallet/test/coinselector_tests.cpp | 87 ++++++++++++++++------------------ src/wallet/wallet.cpp | 42 +++++----------- src/wallet/wallet.h | 9 ++-- 4 files changed, 58 insertions(+), 85 deletions(-) diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index b42939ffdc..c279a9af2f 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -49,15 +49,14 @@ static void CoinSelection(benchmark::Bench& bench) } const CoinEligibilityFilter filter_standard(1, 6, 0); - const CoinSelectionParams coin_selection_params(/* use_bnb= */ true, /* change_output_size= */ 34, + const CoinSelectionParams coin_selection_params(/* change_output_size= */ 34, /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0), /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0), /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false); bench.run([&] { std::set setCoinsRet; CAmount nValueRet; - bool bnb_used; - bool success = wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, coins, setCoinsRet, nValueRet, coin_selection_params, bnb_used); + bool success = wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, coins, setCoinsRet, nValueRet, coin_selection_params); assert(success); assert(nValueRet == 1003 * COIN); assert(setCoinsRet.size() == 2); diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index 55b73cd1f0..26e17eeb8a 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -35,7 +35,7 @@ static CAmount balance = 0; CoinEligibilityFilter filter_standard(1, 6, 0); CoinEligibilityFilter filter_confirmed(1, 1, 0); CoinEligibilityFilter filter_standard_extra(6, 6, 0); -CoinSelectionParams coin_selection_params(/* use_bnb= */ false, /* change_output_size= */ 0, +CoinSelectionParams coin_selection_params(/* change_output_size= */ 0, /* change_spend_size= */ 0, /* effective_feerate= */ CFeeRate(0), /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0), /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false); @@ -271,25 +271,23 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) } // Make sure that effective value is working in SelectCoinsMinConf when BnB is used - CoinSelectionParams coin_selection_params_bnb(/* use_bnb= */ true, /* change_output_size= */ 0, + CoinSelectionParams coin_selection_params_bnb(/* change_output_size= */ 0, /* change_spend_size= */ 0, /* effective_feerate= */ CFeeRate(3000), /* long_term_feerate= */ CFeeRate(1000), /* discard_feerate= */ CFeeRate(1000), /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false); CoinSet setCoinsRet; CAmount nValueRet; - bool bnb_used; empty_wallet(); add_coin(1); vCoins.at(0).nInputBytes = 40; // Make sure that it has a negative effective value. The next check should assert if this somehow got through. Otherwise it will fail - BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb)); // Test fees subtracted from output: empty_wallet(); add_coin(1 * CENT); vCoins.at(0).nInputBytes = 40; coin_selection_params_bnb.m_subtract_fee_outputs = true; - BOOST_CHECK(testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used)); - BOOST_CHECK(bnb_used); + BOOST_CHECK(testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb)); BOOST_CHECK_EQUAL(nValueRet, 1 * CENT); // Make sure that can use BnB when there are preset inputs @@ -307,9 +305,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) coin_control.fAllowOtherInputs = true; coin_control.Select(COutPoint(vCoins.at(0).tx->GetHash(), vCoins.at(0).i)); coin_selection_params_bnb.m_effective_feerate = CFeeRate(0); - BOOST_CHECK(wallet->SelectCoins(vCoins, 10 * CENT, setCoinsRet, nValueRet, coin_control, coin_selection_params_bnb, bnb_used)); - BOOST_CHECK(bnb_used); - BOOST_CHECK(coin_selection_params_bnb.use_bnb); + BOOST_CHECK(wallet->SelectCoins(vCoins, 10 * CENT, setCoinsRet, nValueRet, coin_control, coin_selection_params_bnb)); } } @@ -317,7 +313,6 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) { CoinSet setCoinsRet, setCoinsRet2; CAmount nValueRet; - bool bnb_used; LOCK(testWallet.cs_wallet); testWallet.SetupLegacyScriptPubKeyMan(); @@ -328,24 +323,24 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) empty_wallet(); // with an empty wallet we can't even pay one cent - BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params)); add_coin(1*CENT, 4); // add a new 1 cent coin // with a new 1 cent coin, we still can't find a mature 1 cent - BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params)); // but we can find a new 1 cent - BOOST_CHECK( testWallet.SelectCoinsMinConf( 1 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf( 1 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 1 * CENT); add_coin(2*CENT); // add a mature 2 cent coin // we can't make 3 cents of mature coins - BOOST_CHECK(!testWallet.SelectCoinsMinConf( 3 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf( 3 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params)); // we can make 3 cents of new coins - BOOST_CHECK( testWallet.SelectCoinsMinConf( 3 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf( 3 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 3 * CENT); add_coin(5*CENT); // add a mature 5 cent coin, @@ -355,33 +350,33 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // now we have new: 1+10=11 (of which 10 was self-sent), and mature: 2+5+20=27. total = 38 // we can't make 38 cents only if we disallow new coins: - BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params)); // we can't even make 37 cents if we don't allow new coins even if they're from us - BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard_extra, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard_extra, vCoins, setCoinsRet, nValueRet, coin_selection_params)); // but we can make 37 cents if we accept new coins from ourself - BOOST_CHECK( testWallet.SelectCoinsMinConf(37 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(37 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 37 * CENT); // and we can make 38 cents if we accept all new coins - BOOST_CHECK( testWallet.SelectCoinsMinConf(38 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(38 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 38 * CENT); // try making 34 cents from 1,2,5,10,20 - we can't do it exactly - BOOST_CHECK( testWallet.SelectCoinsMinConf(34 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(34 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 35 * CENT); // but 35 cents is closest BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U); // the best should be 20+10+5. it's incredibly unlikely the 1 or 2 got included (but possible) // when we try making 7 cents, the smaller coins (1,2,5) are enough. We should see just 2+5 - BOOST_CHECK( testWallet.SelectCoinsMinConf( 7 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf( 7 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 7 * CENT); BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); // when we try making 8 cents, the smaller coins (1,2,5) are exactly enough. - BOOST_CHECK( testWallet.SelectCoinsMinConf( 8 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf( 8 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK(nValueRet == 8 * CENT); BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U); // when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10) - BOOST_CHECK( testWallet.SelectCoinsMinConf( 9 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf( 9 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 10 * CENT); BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); @@ -395,30 +390,30 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin(30*CENT); // now we have 6+7+8+20+30 = 71 cents total // check that we have 71 and not 72 - BOOST_CHECK( testWallet.SelectCoinsMinConf(71 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); - BOOST_CHECK(!testWallet.SelectCoinsMinConf(72 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(71 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); + BOOST_CHECK(!testWallet.SelectCoinsMinConf(72 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); // now try making 16 cents. the best smaller coins can do is 6+7+8 = 21; not as good at the next biggest coin, 20 - BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 20 * CENT); // we should get 20 in one coin BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); add_coin( 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total // now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, better than the next biggest coin, 20 - BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 18 * CENT); // we should get 18 in 3 coins BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U); add_coin( 18*CENT); // now we have 5+6+7+8+18+20+30 // and now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, the same as the next biggest coin, 18 - BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 18 * CENT); // we should get 18 in 1 coin BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); // because in the event of a tie, the biggest coin wins // now try making 11 cents. we should get 5+6 - BOOST_CHECK( testWallet.SelectCoinsMinConf(11 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(11 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 11 * CENT); BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); @@ -427,11 +422,11 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin( 2*COIN); add_coin( 3*COIN); add_coin( 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents - BOOST_CHECK( testWallet.SelectCoinsMinConf(95 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(95 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 1 * COIN); // we should get 1 BTC in 1 coin BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); - BOOST_CHECK( testWallet.SelectCoinsMinConf(195 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(195 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 2 * COIN); // we should get 2 BTC in 1 coin BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); @@ -446,14 +441,14 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // try making 1 * MIN_CHANGE from the 1.5 * MIN_CHANGE // we'll get change smaller than MIN_CHANGE whatever happens, so can expect MIN_CHANGE exactly - BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE); // but if we add a bigger coin, small change is avoided add_coin(1111*MIN_CHANGE); // try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5 - BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount // if we add more small coins: @@ -461,7 +456,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin(MIN_CHANGE * 7 / 10); // and try again to make 1.0 * MIN_CHANGE - BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount // run the 'mtgox' test (see https://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf) @@ -470,7 +465,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) for (int j = 0; j < 20; j++) add_coin(50000 * COIN); - BOOST_CHECK( testWallet.SelectCoinsMinConf(500000 * COIN, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(500000 * COIN, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 500000 * COIN); // we should get the exact amount BOOST_CHECK_EQUAL(setCoinsRet.size(), 10U); // in ten coins @@ -483,7 +478,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin(MIN_CHANGE * 6 / 10); add_coin(MIN_CHANGE * 7 / 10); add_coin(1111 * MIN_CHANGE); - BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 1111 * MIN_CHANGE); // we get the bigger coin BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); @@ -493,7 +488,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin(MIN_CHANGE * 6 / 10); add_coin(MIN_CHANGE * 8 / 10); add_coin(1111 * MIN_CHANGE); - BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE); // we should get the exact amount BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); // in two coins 0.4+0.6 @@ -504,12 +499,12 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) add_coin(MIN_CHANGE * 100); // trying to make 100.01 from these three coins - BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 10001 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 10001 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE * 10105 / 100); // we should get all coins BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U); // but if we try to make 99.9, we should take the bigger of the two small coins to avoid small change - BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 9990 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 9990 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 101 * MIN_CHANGE); BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); } @@ -523,7 +518,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) // We only create the wallet once to save time, but we still run the coin selection RUN_TESTS times. for (int i = 0; i < RUN_TESTS; i++) { - BOOST_CHECK(testWallet.SelectCoinsMinConf(2000, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(2000, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)); if (amt - 2000 < MIN_CHANGE) { // needs more than one input: @@ -597,7 +592,6 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset) { CoinSet setCoinsRet; CAmount nValueRet; - bool bnb_used; LOCK(testWallet.cs_wallet); testWallet.SetupLegacyScriptPubKeyMan(); @@ -609,7 +603,7 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset) add_coin(1000 * COIN); add_coin(3 * COIN); - BOOST_CHECK(testWallet.SelectCoinsMinConf(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params)); BOOST_CHECK_EQUAL(nValueRet, 1003 * COIN); BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); @@ -644,19 +638,18 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test) CAmount target = rand.randrange(balance - 1000) + 1000; // Perform selection - CoinSelectionParams coin_selection_params_knapsack(/* use_bnb= */ false, /* change_output_size= */ 34, + CoinSelectionParams coin_selection_params_knapsack(/* change_output_size= */ 34, /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0), /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0), /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false); - CoinSelectionParams coin_selection_params_bnb(/* use_bnb= */ true, /* change_output_size= */ 34, + CoinSelectionParams coin_selection_params_bnb(/* change_output_size= */ 34, /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0), /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0), /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false); CoinSet out_set; CAmount out_value = 0; - bool bnb_used = false; - BOOST_CHECK(testWallet.SelectCoinsMinConf(target, filter_standard, vCoins, out_set, out_value, coin_selection_params_bnb, bnb_used) || - testWallet.SelectCoinsMinConf(target, filter_standard, vCoins, out_set, out_value, coin_selection_params_knapsack, bnb_used)); + BOOST_CHECK(testWallet.SelectCoinsMinConf(target, filter_standard, vCoins, out_set, out_value, coin_selection_params_bnb) || + testWallet.SelectCoinsMinConf(target, filter_standard, vCoins, out_set, out_value, coin_selection_params_knapsack)); BOOST_CHECK_GE(out_value, target); } } diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index a5b9c844c7..c1e58a949f 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2394,7 +2394,7 @@ const CTxOut& CWallet::FindNonChangeParentOutput(const CTransaction& tx, int out } bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector coins, - std::set& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params, bool& bnb_used) const + std::set& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params) const { setCoinsRet.clear(); nValueRet = 0; @@ -2409,25 +2409,20 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil std::vector positive_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, true /* positive_only */); // Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output. if (SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, setCoinsRet, nValueRet)) { - bnb_used = true; return true; } // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here. std::vector all_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, false /* positive_only */); - bnb_used = false; // While nTargetValue includes the transaction fees for non-input things, it does not include the fee for creating a change output. // So we need to include that for KnapsackSolver as well, as we are expecting to create a change output. return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, setCoinsRet, nValueRet); } -bool CWallet::SelectCoins(const std::vector& vAvailableCoins, const CAmount& nTargetValue, std::set& setCoinsRet, CAmount& nValueRet, const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params, bool& bnb_used) const +bool CWallet::SelectCoins(const std::vector& vAvailableCoins, const CAmount& nTargetValue, std::set& setCoinsRet, CAmount& nValueRet, const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params) const { std::vector vCoins(vAvailableCoins); CAmount value_to_select = nTargetValue; - // Default to bnb was not used. If we use it, we set it later - bnb_used = false; - // coin control -> return all selected outputs (we want all selected to go into the transaction for sure) if (coin_control.HasSelected() && !coin_control.fAllowOtherInputs) { @@ -2509,26 +2504,26 @@ bool CWallet::SelectCoins(const std::vector& vAvailableCoins, const CAm // If possible, fund the transaction with confirmed UTXOs only. Prefer at least six // confirmations on outputs received from other wallets and only spend confirmed change. - if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) return true; - if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) return true; + if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true; + if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true; // Fall back to using zero confirmation change (but with as few ancestors in the mempool as // possible) if we cannot fund the transaction otherwise. if (m_spend_zero_conf_change) { - if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) return true; + if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true; if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)), - vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) { + vCoins, setCoinsRet, nValueRet, coin_selection_params)) { return true; } if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2), - vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) { + vCoins, setCoinsRet, nValueRet, coin_selection_params)) { return true; } // If partial groups are allowed, relax the requirement of spending OutputGroups (groups // of UTXOs sent to the same address, which are obviously controlled by a single wallet) // in their entirety. if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */), - vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) { + vCoins, setCoinsRet, nValueRet, coin_selection_params)) { return true; } // Try with unsafe inputs if they are allowed. This may spend unconfirmed outputs @@ -2536,7 +2531,7 @@ bool CWallet::SelectCoins(const std::vector& vAvailableCoins, const CAm if (coin_control.m_include_unsafe_inputs && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0 /* conf_mine */, 0 /* conf_theirs */, max_ancestors-1, max_descendants-1, true /* include_partial_groups */), - vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) { + vCoins, setCoinsRet, nValueRet, coin_selection_params)) { return true; } // Try with unlimited ancestors/descendants. The transaction will still need to meet @@ -2544,7 +2539,7 @@ bool CWallet::SelectCoins(const std::vector& vAvailableCoins, const CAm // OutputGroups use heuristics that may overestimate ancestor/descendant counts. if (!fRejectLongChains && SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::numeric_limits::max(), std::numeric_limits::max(), true /* include_partial_groups */), - vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) { + vCoins, setCoinsRet, nValueRet, coin_selection_params)) { return true; } } @@ -2917,9 +2912,6 @@ bool CWallet::CreateTransactionInternal( nFeeRet = 0; CAmount nValueIn = 0; - // BnB selector is the only selector used when this is true. - // That should only happen on the first pass through the loop. - coin_selection_params.use_bnb = true; coin_selection_params.m_subtract_fee_outputs = nSubtractFeeFromAmount != 0; // If we are doing subtract fee from recipient, don't use effective values // Start with no fee and loop until there is enough fee while (true) @@ -2954,20 +2946,12 @@ bool CWallet::CreateTransactionInternal( CAmount nValueToSelect = nValue + not_input_fees; // Choose coins to use - bool bnb_used = false; nValueIn = 0; setCoins.clear(); - if (!SelectCoins(vAvailableCoins, /* nTargetValue */ nValueToSelect, setCoins, nValueIn, coin_control, coin_selection_params, bnb_used)) + if (!SelectCoins(vAvailableCoins, /* nTargetValue */ nValueToSelect, setCoins, nValueIn, coin_control, coin_selection_params)) { - // If BnB was used, it was the first pass. No longer the first pass and continue loop with knapsack. - if (bnb_used) { - coin_selection_params.use_bnb = false; - continue; - } - else { - error = _("Insufficient funds"); - return false; - } + error = _("Insufficient funds"); + return false; } // Always make a change output diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h index 242aea6715..028131174f 100644 --- a/src/wallet/wallet.h +++ b/src/wallet/wallet.h @@ -615,8 +615,6 @@ public: /** Parameters for one iteration of Coin Selection. */ struct CoinSelectionParams { - /** Toggles use of Branch and Bound instead of Knapsack solver. */ - bool use_bnb = true; /** Size of a change output in bytes, determined by the output type. */ size_t change_output_size = 0; /** Size of the input to spend a change output in virtual bytes. */ @@ -642,9 +640,8 @@ struct CoinSelectionParams * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */ bool m_avoid_partial_spends = false; - CoinSelectionParams(bool use_bnb, size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate, + CoinSelectionParams(size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate, CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial) : - use_bnb(use_bnb), change_output_size(change_output_size), change_spend_size(change_spend_size), m_effective_feerate(effective_feerate), @@ -789,7 +786,7 @@ public: * from coin_control and Coin Selection if successful. */ bool SelectCoins(const std::vector& vAvailableCoins, const CAmount& nTargetValue, std::set& setCoinsRet, CAmount& nValueRet, - const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params, bool& bnb_used) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); + const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); /** Get a name for this wallet for logging/debugging purposes. */ @@ -878,7 +875,7 @@ public: * param@[out] nValueRet Used to return the total value of selected coins. */ bool SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector coins, - std::set& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params, bool& bnb_used) const; + std::set& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params) const; bool IsSpent(const uint256& hash, unsigned int n) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); -- cgit v1.2.3 From 9d3bd74ab4430532d6e53eef8cf77ad999044b14 Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Wed, 30 Oct 2019 16:39:59 -0400 Subject: Remove CreateTransaction while loop and some related variables Remove the CreateTransaction while loop. Removes variables that were only needed because of that loop. Also renames a few variables and moves their declarations to where they are used. Some subtractFeeFromOutputs handling is moved to after coin selection in order to reduce their amounts once the fee is known. If subtracting the fee reduces the change to dust, we will also now remove the change output --- src/wallet/wallet.cpp | 221 ++++++++++++++++++++++++-------------------------- 1 file changed, 104 insertions(+), 117 deletions(-) diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index c1e58a949f..303823695e 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2804,7 +2804,6 @@ bool CWallet::CreateTransactionInternal( CAmount nValue = 0; const OutputType change_type = TransactionChangeType(coin_control.m_change_type ? *coin_control.m_change_type : m_default_change_type, vecSend); ReserveDestination reservedest(this, change_type); - int nChangePosRequest = nChangePosInOut; unsigned int nSubtractFeeFromAmount = 0; for (const auto& recipient : vecSend) { @@ -2909,151 +2908,139 @@ bool CWallet::CreateTransactionInternal( coin_selection_params.m_change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size); coin_selection_params.m_cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + coin_selection_params.m_change_fee; - nFeeRet = 0; - CAmount nValueIn = 0; - coin_selection_params.m_subtract_fee_outputs = nSubtractFeeFromAmount != 0; // If we are doing subtract fee from recipient, don't use effective values - // Start with no fee and loop until there is enough fee - while (true) + + // vouts to the payees + if (!coin_selection_params.m_subtract_fee_outputs) { + coin_selection_params.tx_noinputs_size = 11; // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 output count, 1 witness overhead (dummy, flag, stack size) + } + for (const auto& recipient : vecSend) { - nChangePosInOut = nChangePosRequest; - txNew.vin.clear(); - txNew.vout.clear(); + CTxOut txout(recipient.nAmount, recipient.scriptPubKey); - // vouts to the payees + // Include the fee cost for outputs. if (!coin_selection_params.m_subtract_fee_outputs) { - coin_selection_params.tx_noinputs_size = 11; // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 output count, 1 witness overhead (dummy, flag, stack size) + coin_selection_params.tx_noinputs_size += ::GetSerializeSize(txout, PROTOCOL_VERSION); } - for (const auto& recipient : vecSend) + + if (IsDust(txout, chain().relayDustFee())) { - CTxOut txout(recipient.nAmount, recipient.scriptPubKey); + error = _("Transaction amount too small"); + return false; + } + txNew.vout.push_back(txout); + } - // Include the fee cost for outputs. - if (!coin_selection_params.m_subtract_fee_outputs) { - coin_selection_params.tx_noinputs_size += ::GetSerializeSize(txout, PROTOCOL_VERSION); - } + // Include the fees for things that aren't inputs, excluding the change output + const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size); + CAmount nValueToSelect = nValue + not_input_fees; - if (IsDust(txout, chain().relayDustFee())) - { - error = _("Transaction amount too small"); - return false; - } - txNew.vout.push_back(txout); - } + // Choose coins to use + CAmount inputs_sum = 0; + setCoins.clear(); + if (!SelectCoins(vAvailableCoins, /* nTargetValue */ nValueToSelect, setCoins, inputs_sum, coin_control, coin_selection_params)) + { + error = _("Insufficient funds"); + return false; + } - // Include the fees for things that aren't inputs, excluding the change output - const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size); - CAmount nValueToSelect = nValue + not_input_fees; + // Always make a change output + // We will reduce the fee from this change output later, and remove the output if it is too small. + const CAmount change_and_fee = inputs_sum - nValue; + assert(change_and_fee >= 0); + CTxOut newTxOut(change_and_fee, scriptChange); - // Choose coins to use - nValueIn = 0; - setCoins.clear(); - if (!SelectCoins(vAvailableCoins, /* nTargetValue */ nValueToSelect, setCoins, nValueIn, coin_control, coin_selection_params)) - { - error = _("Insufficient funds"); - return false; - } + if (nChangePosInOut == -1) + { + // Insert change txn at random position: + nChangePosInOut = GetRandInt(txNew.vout.size()+1); + } + else if ((unsigned int)nChangePosInOut > txNew.vout.size()) + { + error = _("Change index out of range"); + return false; + } - // Always make a change output - // We will reduce the fee from this change output later, and remove the output if it is too small. - const CAmount change_and_fee = nValueIn - nValue; - assert(change_and_fee >= 0); - CTxOut newTxOut(change_and_fee, scriptChange); + assert(nChangePosInOut != -1); + auto change_position = txNew.vout.insert(txNew.vout.begin() + nChangePosInOut, newTxOut); - if (nChangePosInOut == -1) - { - // Insert change txn at random position: - nChangePosInOut = GetRandInt(txNew.vout.size()+1); - } - else if ((unsigned int)nChangePosInOut > txNew.vout.size()) - { - error = _("Change index out of range"); - return false; - } + // Dummy fill vin for maximum size estimation + // + for (const auto& coin : setCoins) { + txNew.vin.push_back(CTxIn(coin.outpoint,CScript())); + } - assert(nChangePosInOut != -1); - auto change_position = txNew.vout.insert(txNew.vout.begin() + nChangePosInOut, newTxOut); + // Calculate the transaction fee + tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly); + nBytes = tx_sizes.first; + if (nBytes < 0) { + error = _("Signing transaction failed"); + return false; + } + nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes); - // Dummy fill vin for maximum size estimation - // - for (const auto& coin : setCoins) { - txNew.vin.push_back(CTxIn(coin.outpoint,CScript())); - } + // Subtract fee from the change output if not subtrating it from recipient outputs + CAmount fee_needed = nFeeRet; + if (nSubtractFeeFromAmount == 0) { + change_position->nValue -= fee_needed; + } - // Calculate the transaction fee + // We want to drop the change to fees if: + // 1. The change output would be dust + // 2. The change is within the (almost) exact match window, i.e. it is less than or equal to the cost of the change output (cost_of_change) + CAmount change_amount = change_position->nValue; + if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_amount <= coin_selection_params.m_cost_of_change) + { + nChangePosInOut = -1; + change_amount = 0; + txNew.vout.erase(change_position); + + // Because we have dropped this change, the tx size and required fee will be different, so let's recalculate those tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly); nBytes = tx_sizes.first; - if (nBytes < 0) { - error = _("Signing transaction failed"); - return false; - } - nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes); + fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes); + } - // Subtract fee from the change output if not subtrating it from recipient outputs - CAmount fee_needed = nFeeRet; - if (nSubtractFeeFromAmount == 0) { - change_position->nValue -= fee_needed; - } + // Update nFeeRet in case fee_needed changed due to dropping the change output + if (fee_needed <= change_and_fee - change_amount) { + nFeeRet = change_and_fee - change_amount; + } - // We want to drop the change to fees if: - // 1. The change output would be dust - // 2. The change is within the (almost) exact match window, i.e. it is less than or equal to the cost of the change output (cost_of_change) - CAmount change_amount = change_position->nValue; - if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_amount <= coin_selection_params.m_cost_of_change) + // Reduce output values for subtractFeeFromAmount + if (nSubtractFeeFromAmount != 0) { + CAmount to_reduce = fee_needed + change_amount - change_and_fee; + int i = 0; + bool fFirst = true; + for (const auto& recipient : vecSend) { - nChangePosInOut = -1; - change_amount = 0; - txNew.vout.erase(change_position); - - // Because we have dropped this change, the tx size and required fee will be different, so let's recalculate those - tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly); - nBytes = tx_sizes.first; - fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes); - } - - // If the fee is covered, there's no need to loop or subtract from recipients - if (fee_needed <= change_and_fee - change_amount) { - nFeeRet = change_and_fee - change_amount; - break; - } + if (i == nChangePosInOut) { + ++i; + } + CTxOut& txout = txNew.vout[i]; - // Reduce output values for subtractFeeFromAmount - if (nSubtractFeeFromAmount != 0) { - CAmount to_reduce = fee_needed + change_amount - change_and_fee; - int i = 0; - bool fFirst = true; - for (const auto& recipient : vecSend) + if (recipient.fSubtractFeeFromAmount) { - if (i == nChangePosInOut) { - ++i; - } - CTxOut& txout = txNew.vout[i]; + txout.nValue -= to_reduce / nSubtractFeeFromAmount; // Subtract fee equally from each selected recipient - if (recipient.fSubtractFeeFromAmount) + if (fFirst) // first receiver pays the remainder not divisible by output count { - txout.nValue -= to_reduce / nSubtractFeeFromAmount; // Subtract fee equally from each selected recipient - - if (fFirst) // first receiver pays the remainder not divisible by output count - { - fFirst = false; - txout.nValue -= to_reduce % nSubtractFeeFromAmount; - } + fFirst = false; + txout.nValue -= to_reduce % nSubtractFeeFromAmount; + } - // Error if this output is reduced to be below dust - if (IsDust(txout, chain().relayDustFee())) { - if (txout.nValue < 0) { - error = _("The transaction amount is too small to pay the fee"); - } else { - error = _("The transaction amount is too small to send after the fee has been deducted"); - } - return false; + // Error if this output is reduced to be below dust + if (IsDust(txout, chain().relayDustFee())) { + if (txout.nValue < 0) { + error = _("The transaction amount is too small to pay the fee"); + } else { + error = _("The transaction amount is too small to send after the fee has been deducted"); } + return false; } - ++i; } - nFeeRet = fee_needed; - break; // The fee has been deducted from the recipients, nothing left to do here + ++i; } + nFeeRet = fee_needed; } // Give up if change keypool ran out and change is required -- cgit v1.2.3 From 6d6d2784759878ef0c4ac128d12aac68add1edca Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Mon, 16 Nov 2020 16:57:29 -0500 Subject: Change SelectCoins_test to actually test SelectCoins This was originally modified to use SelectCoinsMinConf in order to test both BnB and Knapsack at the same time. But since SelectCoins does both now, this is no longer necessary and we can revert back to actually testing SelectCoins. --- src/wallet/test/coinselector_tests.cpp | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-) diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index 26e17eeb8a..ad6a4351db 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -613,6 +613,7 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset) // Tests that with the ideal conditions, the coin selector will always be able to find a solution that can pay the target value BOOST_AUTO_TEST_CASE(SelectCoins_test) { + LOCK(testWallet.cs_wallet); testWallet.SetupLegacyScriptPubKeyMan(); // Random generator stuff @@ -638,18 +639,14 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test) CAmount target = rand.randrange(balance - 1000) + 1000; // Perform selection - CoinSelectionParams coin_selection_params_knapsack(/* change_output_size= */ 34, - /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0), - /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0), - /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false); - CoinSelectionParams coin_selection_params_bnb(/* change_output_size= */ 34, - /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0), - /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0), - /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false); + CoinSelectionParams cs_params(/* change_output_size= */ 34, + /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0), + /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0), + /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false); CoinSet out_set; CAmount out_value = 0; - BOOST_CHECK(testWallet.SelectCoinsMinConf(target, filter_standard, vCoins, out_set, out_value, coin_selection_params_bnb) || - testWallet.SelectCoinsMinConf(target, filter_standard, vCoins, out_set, out_value, coin_selection_params_knapsack)); + CCoinControl cc; + BOOST_CHECK(testWallet.SelectCoins(vCoins, target, out_set, out_value, cc, cs_params)); BOOST_CHECK_GE(out_value, target); } } -- cgit v1.2.3 From 51a3ac242c92e69b59df26f8f9e287b31e5c3b0f Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Fri, 23 Apr 2021 15:14:41 -0400 Subject: Have OutputGroup determine the value to use Instead of hijacking the effective_feerate to use the correct value during coin selection, have OutputGroup be aware of whether we are subtracting the fee from the outputs and provide the correct value to use for selection. To do this, OutputGroup now takes CoinSelectionParams and has a new function GetSelectionAmount(). --- src/wallet/coinselection.cpp | 31 +++++++++++++++----------- src/wallet/coinselection.h | 52 +++++++++++++++++++++++++++++++++++++++++--- src/wallet/wallet.cpp | 27 +++++++++-------------- src/wallet/wallet.h | 43 +----------------------------------- 4 files changed, 78 insertions(+), 75 deletions(-) diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index af88bf85dd..6d502e1df1 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -14,7 +14,7 @@ struct { bool operator()(const OutputGroup& a, const OutputGroup& b) const { - return a.effective_value > b.effective_value; + return a.GetSelectionAmount() > b.GetSelectionAmount(); } } descending; @@ -73,8 +73,8 @@ bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selectio CAmount curr_available_value = 0; for (const OutputGroup& utxo : utxo_pool) { // Assert that this utxo is not negative. It should never be negative, effective value calculation should have removed it - assert(utxo.effective_value > 0); - curr_available_value += utxo.effective_value; + assert(utxo.GetSelectionAmount() > 0); + curr_available_value += utxo.GetSelectionAmount(); } if (curr_available_value < selection_target) { return false; @@ -118,7 +118,7 @@ bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selectio // Walk backwards to find the last included UTXO that still needs to have its omission branch traversed. while (!curr_selection.empty() && !curr_selection.back()) { curr_selection.pop_back(); - curr_available_value += utxo_pool.at(curr_selection.size()).effective_value; + curr_available_value += utxo_pool.at(curr_selection.size()).GetSelectionAmount(); } if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched @@ -128,24 +128,24 @@ bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selectio // Output was included on previous iterations, try excluding now. curr_selection.back() = false; OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1); - curr_value -= utxo.effective_value; + curr_value -= utxo.GetSelectionAmount(); curr_waste -= utxo.fee - utxo.long_term_fee; } else { // Moving forwards, continuing down this branch OutputGroup& utxo = utxo_pool.at(curr_selection.size()); // Remove this utxo from the curr_available_value utxo amount - curr_available_value -= utxo.effective_value; + curr_available_value -= utxo.GetSelectionAmount(); // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded. Since the ratio of fee to // long term fee is the same, we only need to check if one of those values match in order to know that the waste is the same. if (!curr_selection.empty() && !curr_selection.back() && - utxo.effective_value == utxo_pool.at(curr_selection.size() - 1).effective_value && + utxo.GetSelectionAmount() == utxo_pool.at(curr_selection.size() - 1).GetSelectionAmount() && utxo.fee == utxo_pool.at(curr_selection.size() - 1).fee) { curr_selection.push_back(false); } else { // Inclusion branch first (Largest First Exploration) curr_selection.push_back(true); - curr_value += utxo.effective_value; + curr_value += utxo.GetSelectionAmount(); curr_waste += utxo.fee - utxo.long_term_fee; } } @@ -227,14 +227,14 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector& group Shuffle(groups.begin(), groups.end(), FastRandomContext()); for (const OutputGroup& group : groups) { - if (group.effective_value == nTargetValue) { + if (group.GetSelectionAmount() == nTargetValue) { util::insert(setCoinsRet, group.m_outputs); nValueRet += group.m_value; return true; - } else if (group.effective_value < nTargetValue + MIN_CHANGE) { + } else if (group.GetSelectionAmount() < nTargetValue + MIN_CHANGE) { applicable_groups.push_back(group); - nTotalLower += group.effective_value; - } else if (!lowest_larger || group.effective_value < lowest_larger->effective_value) { + nTotalLower += group.GetSelectionAmount(); + } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) { lowest_larger = group; } } @@ -267,7 +267,7 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector& group // 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 (lowest_larger && - ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->effective_value <= nBest)) { + ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->GetSelectionAmount() <= nBest)) { util::insert(setCoinsRet, lowest_larger->m_outputs); nValueRet += lowest_larger->m_value; } else { @@ -336,3 +336,8 @@ bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_f && m_ancestors <= eligibility_filter.max_ancestors && m_descendants <= eligibility_filter.max_descendants; } + +CAmount OutputGroup::GetSelectionAmount() const +{ + return m_subtract_fee_outputs ? m_value : effective_value; +} diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index af23178d04..7a3fb82139 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -57,6 +57,47 @@ public: } }; +/** Parameters for one iteration of Coin Selection. */ +struct CoinSelectionParams +{ + /** Size of a change output in bytes, determined by the output type. */ + size_t change_output_size = 0; + /** Size of the input to spend a change output in virtual bytes. */ + size_t change_spend_size = 0; + /** Cost of creating the change output. */ + CAmount m_change_fee{0}; + /** Cost of creating the change output + cost of spending the change output in the future. */ + CAmount m_cost_of_change{0}; + /** The targeted feerate of the transaction being built. */ + CFeeRate m_effective_feerate; + /** The feerate estimate used to estimate an upper bound on what should be sufficient to spend + * the change output sometime in the future. */ + CFeeRate m_long_term_feerate; + /** If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees. */ + CFeeRate m_discard_feerate; + /** Size of the transaction before coin selection, consisting of the header and recipient + * output(s), excluding the inputs and change output(s). */ + size_t tx_noinputs_size = 0; + /** Indicate that we are subtracting the fee from outputs */ + bool m_subtract_fee_outputs = false; + /** When true, always spend all (up to OUTPUT_GROUP_MAX_ENTRIES) or none of the outputs + * associated with the same address. This helps reduce privacy leaks resulting from address + * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */ + bool m_avoid_partial_spends = false; + + CoinSelectionParams(size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate, + CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial) : + change_output_size(change_output_size), + change_spend_size(change_spend_size), + m_effective_feerate(effective_feerate), + m_long_term_feerate(long_term_feerate), + m_discard_feerate(discard_feerate), + tx_noinputs_size(tx_noinputs_size), + m_avoid_partial_spends(avoid_partial) + {} + CoinSelectionParams() {} +}; + /** Parameters for filtering which OutputGroups we may use in coin selection. * We start by being very selective and requiring multiple confirmations and * then get more permissive if we cannot fund the transaction. */ @@ -109,15 +150,20 @@ struct OutputGroup * a lower feerate). Calculated using long term fee estimate. This is used to decide whether * it could be economical to create a change output. */ CFeeRate m_long_term_feerate{0}; + /** Indicate that we are subtracting the fee from outputs. + * When true, the value that is used for coin selection is the UTXO's real value rather than effective value */ + bool m_subtract_fee_outputs{false}; OutputGroup() {} - OutputGroup(const CFeeRate& effective_feerate, const CFeeRate& long_term_feerate) : - m_effective_feerate(effective_feerate), - m_long_term_feerate(long_term_feerate) + OutputGroup(const CoinSelectionParams& params) : + m_effective_feerate(params.m_effective_feerate), + m_long_term_feerate(params.m_long_term_feerate), + m_subtract_fee_outputs(params.m_subtract_fee_outputs) {} void Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only); bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const; + CAmount GetSelectionAmount() const; }; bool SelectCoinsBnB(std::vector& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set& out_set, CAmount& value_ret); diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 303823695e..78243a0136 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -2399,20 +2399,13 @@ bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibil setCoinsRet.clear(); nValueRet = 0; - // Get the feerate for effective value. - // When subtracting the fee from the outputs, we want the effective feerate to be 0 - CFeeRate effective_feerate{0}; - if (!coin_selection_params.m_subtract_fee_outputs) { - effective_feerate = coin_selection_params.m_effective_feerate; - } - - std::vector positive_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, true /* positive_only */); // Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output. + std::vector positive_groups = GroupOutputs(coins, coin_selection_params, eligibility_filter, true /* positive_only */); if (SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, setCoinsRet, nValueRet)) { return true; } // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here. - std::vector all_groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, false /* positive_only */); + std::vector all_groups = GroupOutputs(coins, coin_selection_params, eligibility_filter, false /* positive_only */); // While nTargetValue includes the transaction fees for non-input things, it does not include the fee for creating a change output. // So we need to include that for KnapsackSolver as well, as we are expecting to create a change output. return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, setCoinsRet, nValueRet); @@ -4223,12 +4216,12 @@ bool CWalletTx::IsImmatureCoinBase() const return GetBlocksToMaturity() > 0; } -std::vector CWallet::GroupOutputs(const std::vector& outputs, bool separate_coins, const CFeeRate& effective_feerate, const CFeeRate& long_term_feerate, const CoinEligibilityFilter& filter, bool positive_only) const +std::vector CWallet::GroupOutputs(const std::vector& outputs, const CoinSelectionParams& coin_sel_params, const CoinEligibilityFilter& filter, bool positive_only) const { std::vector groups_out; - if (separate_coins) { - // Single coin means no grouping. Each COutput gets its own OutputGroup. + if (!coin_sel_params.m_avoid_partial_spends) { + // Allowing partial spends means no grouping. Each COutput gets its own OutputGroup. for (const COutput& output : outputs) { // Skip outputs we cannot spend if (!output.fSpendable) continue; @@ -4238,11 +4231,11 @@ std::vector CWallet::GroupOutputs(const std::vector& outpu CInputCoin input_coin = output.GetInputCoin(); // Make an OutputGroup containing just this output - OutputGroup group{effective_feerate, long_term_feerate}; + OutputGroup group{coin_sel_params}; group.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants, positive_only); // Check the OutputGroup's eligibility. Only add the eligible ones. - if (positive_only && group.effective_value <= 0) continue; + if (positive_only && group.GetSelectionAmount() <= 0) continue; if (group.m_outputs.size() > 0 && group.EligibleForSpending(filter)) groups_out.push_back(group); } return groups_out; @@ -4268,7 +4261,7 @@ std::vector CWallet::GroupOutputs(const std::vector& outpu if (groups.size() == 0) { // No OutputGroups for this scriptPubKey yet, add one - groups.emplace_back(effective_feerate, long_term_feerate); + groups.emplace_back(coin_sel_params); } // Get the last OutputGroup in the vector so that we can add the CInputCoin to it @@ -4279,7 +4272,7 @@ std::vector CWallet::GroupOutputs(const std::vector& outpu // to avoid surprising users with very high fees. if (group->m_outputs.size() >= OUTPUT_GROUP_MAX_ENTRIES) { // The last output group is full, add a new group to the vector and use that group for the insertion - groups.emplace_back(effective_feerate, long_term_feerate); + groups.emplace_back(coin_sel_params); group = &groups.back(); } @@ -4301,7 +4294,7 @@ std::vector CWallet::GroupOutputs(const std::vector& outpu } // Check the OutputGroup's eligibility. Only add the eligible ones. - if (positive_only && group.effective_value <= 0) continue; + if (positive_only && group.GetSelectionAmount() <= 0) continue; if (group.m_outputs.size() > 0 && group.EligibleForSpending(filter)) groups_out.push_back(group); } } diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h index 028131174f..1f4150b702 100644 --- a/src/wallet/wallet.h +++ b/src/wallet/wallet.h @@ -612,47 +612,6 @@ public: } }; -/** Parameters for one iteration of Coin Selection. */ -struct CoinSelectionParams -{ - /** Size of a change output in bytes, determined by the output type. */ - size_t change_output_size = 0; - /** Size of the input to spend a change output in virtual bytes. */ - size_t change_spend_size = 0; - /** Cost of creating the change output. */ - CAmount m_change_fee{0}; - /** Cost of creating the change output + cost of spending the change output in the future. */ - CAmount m_cost_of_change{0}; - /** The targeted feerate of the transaction being built. */ - CFeeRate m_effective_feerate; - /** The feerate estimate used to estimate an upper bound on what should be sufficient to spend - * the change output sometime in the future. */ - CFeeRate m_long_term_feerate; - /** If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees. */ - CFeeRate m_discard_feerate; - /** Size of the transaction before coin selection, consisting of the header and recipient - * output(s), excluding the inputs and change output(s). */ - size_t tx_noinputs_size = 0; - /** Indicate that we are subtracting the fee from outputs */ - bool m_subtract_fee_outputs = false; - /** When true, always spend all (up to OUTPUT_GROUP_MAX_ENTRIES) or none of the outputs - * associated with the same address. This helps reduce privacy leaks resulting from address - * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */ - bool m_avoid_partial_spends = false; - - CoinSelectionParams(size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate, - CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial) : - change_output_size(change_output_size), - change_spend_size(change_spend_size), - m_effective_feerate(effective_feerate), - m_long_term_feerate(long_term_feerate), - m_discard_feerate(discard_feerate), - tx_noinputs_size(tx_noinputs_size), - m_avoid_partial_spends(avoid_partial) - {} - CoinSelectionParams() {} -}; - class WalletRescanReserver; //forward declarations for ScanForWalletTransactions/RescanFromTime /** * A CWallet maintains a set of transactions and balances, and provides the ability to create new transactions. @@ -883,7 +842,7 @@ public: bool IsSpentKey(const uint256& hash, unsigned int n) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); void SetSpentKeyState(WalletBatch& batch, const uint256& hash, unsigned int n, bool used, std::set& tx_destinations) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); - std::vector GroupOutputs(const std::vector& outputs, bool separate_coins, const CFeeRate& effective_feerate, const CFeeRate& long_term_feerate, const CoinEligibilityFilter& filter, bool positive_only) const; + std::vector GroupOutputs(const std::vector& outputs, const CoinSelectionParams& coin_sel_params, const CoinEligibilityFilter& filter, bool positive_only) const; /** Display address on an external signer. Returns false if external signer support is not compiled */ bool DisplayAddress(const CTxDestination& dest) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet); -- cgit v1.2.3