spend.cpp
1 // Copyright (c) 2021-2022 The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #include <algorithm> 6 #include <common/args.h> 7 #include <common/system.h> 8 #include <consensus/amount.h> 9 #include <consensus/validation.h> 10 #include <interfaces/chain.h> 11 #include <numeric> 12 #include <policy/policy.h> 13 #include <primitives/transaction.h> 14 #include <script/script.h> 15 #include <script/signingprovider.h> 16 #include <script/solver.h> 17 #include <util/check.h> 18 #include <util/fees.h> 19 #include <util/moneystr.h> 20 #include <util/rbf.h> 21 #include <util/trace.h> 22 #include <util/translation.h> 23 #include <wallet/coincontrol.h> 24 #include <wallet/fees.h> 25 #include <wallet/receive.h> 26 #include <wallet/spend.h> 27 #include <wallet/transaction.h> 28 #include <wallet/wallet.h> 29 30 #include <cmath> 31 32 using interfaces::FoundBlock; 33 34 namespace wallet { 35 static constexpr size_t OUTPUT_GROUP_MAX_ENTRIES{100}; 36 37 /** Whether the descriptor represents, directly or not, a witness program. */ 38 static bool IsSegwit(const Descriptor& desc) { 39 if (const auto typ = desc.GetOutputType()) return *typ != OutputType::LEGACY; 40 return false; 41 } 42 43 /** Whether to assume ECDSA signatures' will be high-r. */ 44 static bool UseMaxSig(const std::optional<CTxIn>& txin, const CCoinControl* coin_control) { 45 // Use max sig if watch only inputs were used or if this particular input is an external input 46 // to ensure a sufficient fee is attained for the requested feerate. 47 return coin_control && (coin_control->fAllowWatchOnly || (txin && coin_control->IsExternalSelected(txin->prevout))); 48 } 49 50 /** Get the size of an input (in witness units) once it's signed. 51 * 52 * @param desc The output script descriptor of the coin spent by this input. 53 * @param txin Optionally the txin to estimate the size of. Used to determine the size of ECDSA signatures. 54 * @param coin_control Information about the context to determine the size of ECDSA signatures. 55 * @param tx_is_segwit Whether the transaction has at least a single input spending a segwit coin. 56 * @param can_grind_r Whether the signer will be able to grind the R of the signature. 57 */ 58 static std::optional<int64_t> MaxInputWeight(const Descriptor& desc, const std::optional<CTxIn>& txin, 59 const CCoinControl* coin_control, const bool tx_is_segwit, 60 const bool can_grind_r) { 61 if (const auto sat_weight = desc.MaxSatisfactionWeight(!can_grind_r || UseMaxSig(txin, coin_control))) { 62 if (const auto elems_count = desc.MaxSatisfactionElems()) { 63 const bool is_segwit = IsSegwit(desc); 64 // Account for the size of the scriptsig and the number of elements on the witness stack. Note 65 // that if any input in the transaction is spending a witness program, we need to specify the 66 // witness stack size for every input regardless of whether it is segwit itself. 67 // NOTE: this also works in case of mixed scriptsig-and-witness such as in p2sh-wrapped segwit v0 68 // outputs. In this case the size of the scriptsig length will always be one (since the redeemScript 69 // is always a push of the witness program in this case, which is smaller than 253 bytes). 70 const int64_t scriptsig_len = is_segwit ? 1 : GetSizeOfCompactSize(*sat_weight / WITNESS_SCALE_FACTOR); 71 const int64_t witstack_len = is_segwit ? GetSizeOfCompactSize(*elems_count) : (tx_is_segwit ? 1 : 0); 72 // previous txid + previous vout + sequence + scriptsig len + witstack size + scriptsig or witness 73 // NOTE: sat_weight already accounts for the witness discount accordingly. 74 return (32 + 4 + 4 + scriptsig_len) * WITNESS_SCALE_FACTOR + witstack_len + *sat_weight; 75 } 76 } 77 78 return {}; 79 } 80 81 int CalculateMaximumSignedInputSize(const CTxOut& txout, const COutPoint outpoint, const SigningProvider* provider, bool can_grind_r, const CCoinControl* coin_control) 82 { 83 if (!provider) return -1; 84 85 if (const auto desc = InferDescriptor(txout.scriptPubKey, *provider)) { 86 if (const auto weight = MaxInputWeight(*desc, {}, coin_control, true, can_grind_r)) { 87 return static_cast<int>(GetVirtualTransactionSize(*weight, 0, 0)); 88 } 89 } 90 91 return -1; 92 } 93 94 int CalculateMaximumSignedInputSize(const CTxOut& txout, const CWallet* wallet, const CCoinControl* coin_control) 95 { 96 const std::unique_ptr<SigningProvider> provider = wallet->GetSolvingProvider(txout.scriptPubKey); 97 return CalculateMaximumSignedInputSize(txout, COutPoint(), provider.get(), wallet->CanGrindR(), coin_control); 98 } 99 100 /** Infer a descriptor for the given output script. */ 101 static std::unique_ptr<Descriptor> GetDescriptor(const CWallet* wallet, const CCoinControl* coin_control, 102 const CScript script_pubkey) 103 { 104 MultiSigningProvider providers; 105 for (const auto spkman: wallet->GetScriptPubKeyMans(script_pubkey)) { 106 providers.AddProvider(spkman->GetSolvingProvider(script_pubkey)); 107 } 108 if (coin_control) { 109 providers.AddProvider(std::make_unique<FlatSigningProvider>(coin_control->m_external_provider)); 110 } 111 return InferDescriptor(script_pubkey, providers); 112 } 113 114 /** Infer the maximum size of this input after it will be signed. */ 115 static std::optional<int64_t> GetSignedTxinWeight(const CWallet* wallet, const CCoinControl* coin_control, 116 const CTxIn& txin, const CTxOut& txo, const bool tx_is_segwit, 117 const bool can_grind_r) 118 { 119 // If weight was provided, use that. 120 std::optional<int64_t> weight; 121 if (coin_control && (weight = coin_control->GetInputWeight(txin.prevout))) { 122 return weight.value(); 123 } 124 125 // Otherwise, use the maximum satisfaction size provided by the descriptor. 126 std::unique_ptr<Descriptor> desc{GetDescriptor(wallet, coin_control, txo.scriptPubKey)}; 127 if (desc) return MaxInputWeight(*desc, {txin}, coin_control, tx_is_segwit, can_grind_r); 128 129 return {}; 130 } 131 132 // txouts needs to be in the order of tx.vin 133 TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, const std::vector<CTxOut>& txouts, const CCoinControl* coin_control) 134 { 135 // nVersion + nLockTime + input count + output count 136 int64_t weight = (4 + 4 + GetSizeOfCompactSize(tx.vin.size()) + GetSizeOfCompactSize(tx.vout.size())) * WITNESS_SCALE_FACTOR; 137 // Whether any input spends a witness program. Necessary to run before the next loop over the 138 // inputs in order to accurately compute the compactSize length for the witness data per input. 139 bool is_segwit = std::any_of(txouts.begin(), txouts.end(), [&](const CTxOut& txo) { 140 std::unique_ptr<Descriptor> desc{GetDescriptor(wallet, coin_control, txo.scriptPubKey)}; 141 if (desc) return IsSegwit(*desc); 142 return false; 143 }); 144 // Segwit marker and flag 145 if (is_segwit) weight += 2; 146 147 // Add the size of the transaction outputs. 148 for (const auto& txo : tx.vout) weight += GetSerializeSize(txo) * WITNESS_SCALE_FACTOR; 149 150 // Add the size of the transaction inputs as if they were signed. 151 for (uint32_t i = 0; i < txouts.size(); i++) { 152 const auto txin_weight = GetSignedTxinWeight(wallet, coin_control, tx.vin[i], txouts[i], is_segwit, wallet->CanGrindR()); 153 if (!txin_weight) return TxSize{-1, -1}; 154 assert(*txin_weight > -1); 155 weight += *txin_weight; 156 } 157 158 // It's ok to use 0 as the number of sigops since we never create any pathological transaction. 159 return TxSize{GetVirtualTransactionSize(weight, 0, 0), weight}; 160 } 161 162 TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, const CCoinControl* coin_control) 163 { 164 std::vector<CTxOut> txouts; 165 // Look up the inputs. The inputs are either in the wallet, or in coin_control. 166 for (const CTxIn& input : tx.vin) { 167 const auto mi = wallet->mapWallet.find(input.prevout.hash); 168 // Can not estimate size without knowing the input details 169 if (mi != wallet->mapWallet.end()) { 170 assert(input.prevout.n < mi->second.tx->vout.size()); 171 txouts.emplace_back(mi->second.tx->vout.at(input.prevout.n)); 172 } else if (coin_control) { 173 const auto& txout{coin_control->GetExternalOutput(input.prevout)}; 174 if (!txout) return TxSize{-1, -1}; 175 txouts.emplace_back(*txout); 176 } else { 177 return TxSize{-1, -1}; 178 } 179 } 180 return CalculateMaximumSignedTxSize(tx, wallet, txouts, coin_control); 181 } 182 183 size_t CoinsResult::Size() const 184 { 185 size_t size{0}; 186 for (const auto& it : coins) { 187 size += it.second.size(); 188 } 189 return size; 190 } 191 192 std::vector<COutput> CoinsResult::All() const 193 { 194 std::vector<COutput> all; 195 all.reserve(coins.size()); 196 for (const auto& it : coins) { 197 all.insert(all.end(), it.second.begin(), it.second.end()); 198 } 199 return all; 200 } 201 202 void CoinsResult::Clear() { 203 coins.clear(); 204 } 205 206 void CoinsResult::Erase(const std::unordered_set<COutPoint, SaltedOutpointHasher>& coins_to_remove) 207 { 208 for (auto& [type, vec] : coins) { 209 auto remove_it = std::remove_if(vec.begin(), vec.end(), [&](const COutput& coin) { 210 // remove it if it's on the set 211 if (coins_to_remove.count(coin.outpoint) == 0) return false; 212 213 // update cached amounts 214 total_amount -= coin.txout.nValue; 215 if (coin.HasEffectiveValue()) total_effective_amount = *total_effective_amount - coin.GetEffectiveValue(); 216 return true; 217 }); 218 vec.erase(remove_it, vec.end()); 219 } 220 } 221 222 void CoinsResult::Shuffle(FastRandomContext& rng_fast) 223 { 224 for (auto& it : coins) { 225 ::Shuffle(it.second.begin(), it.second.end(), rng_fast); 226 } 227 } 228 229 void CoinsResult::Add(OutputType type, const COutput& out) 230 { 231 coins[type].emplace_back(out); 232 total_amount += out.txout.nValue; 233 if (out.HasEffectiveValue()) { 234 total_effective_amount = total_effective_amount.has_value() ? 235 *total_effective_amount + out.GetEffectiveValue() : out.GetEffectiveValue(); 236 } 237 } 238 239 static OutputType GetOutputType(TxoutType type, bool is_from_p2sh) 240 { 241 switch (type) { 242 case TxoutType::WITNESS_V1_TAPROOT: 243 return OutputType::BECH32M; 244 case TxoutType::WITNESS_V0_KEYHASH: 245 case TxoutType::WITNESS_V0_SCRIPTHASH: 246 if (is_from_p2sh) return OutputType::P2SH_SEGWIT; 247 else return OutputType::BECH32; 248 case TxoutType::SCRIPTHASH: 249 case TxoutType::PUBKEYHASH: 250 return OutputType::LEGACY; 251 default: 252 return OutputType::UNKNOWN; 253 } 254 } 255 256 // Fetch and validate the coin control selected inputs. 257 // Coins could be internal (from the wallet) or external. 258 util::Result<PreSelectedInputs> FetchSelectedInputs(const CWallet& wallet, const CCoinControl& coin_control, 259 const CoinSelectionParams& coin_selection_params) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet) 260 { 261 PreSelectedInputs result; 262 const bool can_grind_r = wallet.CanGrindR(); 263 std::map<COutPoint, CAmount> map_of_bump_fees = wallet.chain().calculateIndividualBumpFees(coin_control.ListSelected(), coin_selection_params.m_effective_feerate); 264 for (const COutPoint& outpoint : coin_control.ListSelected()) { 265 int64_t input_bytes = coin_control.GetInputWeight(outpoint).value_or(-1); 266 if (input_bytes != -1) { 267 input_bytes = GetVirtualTransactionSize(input_bytes, 0, 0); 268 } 269 CTxOut txout; 270 if (auto ptr_wtx = wallet.GetWalletTx(outpoint.hash)) { 271 // Clearly invalid input, fail 272 if (ptr_wtx->tx->vout.size() <= outpoint.n) { 273 return util::Error{strprintf(_("Invalid pre-selected input %s"), outpoint.ToString())}; 274 } 275 txout = ptr_wtx->tx->vout.at(outpoint.n); 276 if (input_bytes == -1) { 277 input_bytes = CalculateMaximumSignedInputSize(txout, &wallet, &coin_control); 278 } 279 } else { 280 // The input is external. We did not find the tx in mapWallet. 281 const auto out{coin_control.GetExternalOutput(outpoint)}; 282 if (!out) { 283 return util::Error{strprintf(_("Not found pre-selected input %s"), outpoint.ToString())}; 284 } 285 286 txout = *out; 287 } 288 289 if (input_bytes == -1) { 290 input_bytes = CalculateMaximumSignedInputSize(txout, outpoint, &coin_control.m_external_provider, can_grind_r, &coin_control); 291 } 292 293 if (input_bytes == -1) { 294 return util::Error{strprintf(_("Not solvable pre-selected input %s"), outpoint.ToString())}; // Not solvable, can't estimate size for fee 295 } 296 297 /* Set some defaults for depth, spendable, solvable, safe, time, and from_me as these don't matter for preset inputs since no selection is being done. */ 298 COutput output(outpoint, txout, /*depth=*/ 0, input_bytes, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, coin_selection_params.m_effective_feerate); 299 output.ApplyBumpFee(map_of_bump_fees.at(output.outpoint)); 300 result.Insert(output, coin_selection_params.m_subtract_fee_outputs); 301 } 302 return result; 303 } 304 305 CoinsResult AvailableCoins(const CWallet& wallet, 306 const CCoinControl* coinControl, 307 std::optional<CFeeRate> feerate, 308 const CoinFilterParams& params) 309 { 310 AssertLockHeld(wallet.cs_wallet); 311 312 CoinsResult result; 313 // Either the WALLET_FLAG_AVOID_REUSE flag is not set (in which case we always allow), or we default to avoiding, and only in the case where 314 // a coin control object is provided, and has the avoid address reuse flag set to false, do we allow already used addresses 315 bool allow_used_addresses = !wallet.IsWalletFlagSet(WALLET_FLAG_AVOID_REUSE) || (coinControl && !coinControl->m_avoid_address_reuse); 316 const int min_depth = {coinControl ? coinControl->m_min_depth : DEFAULT_MIN_DEPTH}; 317 const int max_depth = {coinControl ? coinControl->m_max_depth : DEFAULT_MAX_DEPTH}; 318 const bool only_safe = {coinControl ? !coinControl->m_include_unsafe_inputs : true}; 319 const bool can_grind_r = wallet.CanGrindR(); 320 std::vector<COutPoint> outpoints; 321 322 std::set<uint256> trusted_parents; 323 for (const auto& entry : wallet.mapWallet) 324 { 325 const uint256& txid = entry.first; 326 const CWalletTx& wtx = entry.second; 327 328 if (wallet.IsTxImmatureCoinBase(wtx) && !params.include_immature_coinbase) 329 continue; 330 331 int nDepth = wallet.GetTxDepthInMainChain(wtx); 332 if (nDepth < 0) 333 continue; 334 335 // We should not consider coins which aren't at least in our mempool 336 // It's possible for these to be conflicted via ancestors which we may never be able to detect 337 if (nDepth == 0 && !wtx.InMempool()) 338 continue; 339 340 bool safeTx = CachedTxIsTrusted(wallet, wtx, trusted_parents); 341 342 // We should not consider coins from transactions that are replacing 343 // other transactions. 344 // 345 // Example: There is a transaction A which is replaced by bumpfee 346 // transaction B. In this case, we want to prevent creation of 347 // a transaction B' which spends an output of B. 348 // 349 // Reason: If transaction A were initially confirmed, transactions B 350 // and B' would no longer be valid, so the user would have to create 351 // a new transaction C to replace B'. However, in the case of a 352 // one-block reorg, transactions B' and C might BOTH be accepted, 353 // when the user only wanted one of them. Specifically, there could 354 // be a 1-block reorg away from the chain where transactions A and C 355 // were accepted to another chain where B, B', and C were all 356 // accepted. 357 if (nDepth == 0 && wtx.mapValue.count("replaces_txid")) { 358 safeTx = false; 359 } 360 361 // Similarly, we should not consider coins from transactions that 362 // have been replaced. In the example above, we would want to prevent 363 // creation of a transaction A' spending an output of A, because if 364 // transaction B were initially confirmed, conflicting with A and 365 // A', we wouldn't want to the user to create a transaction D 366 // intending to replace A', but potentially resulting in a scenario 367 // where A, A', and D could all be accepted (instead of just B and 368 // D, or just A and A' like the user would want). 369 if (nDepth == 0 && wtx.mapValue.count("replaced_by_txid")) { 370 safeTx = false; 371 } 372 373 if (only_safe && !safeTx) { 374 continue; 375 } 376 377 if (nDepth < min_depth || nDepth > max_depth) { 378 continue; 379 } 380 381 bool tx_from_me = CachedTxIsFromMe(wallet, wtx, ISMINE_ALL); 382 383 for (unsigned int i = 0; i < wtx.tx->vout.size(); i++) { 384 const CTxOut& output = wtx.tx->vout[i]; 385 const COutPoint outpoint(Txid::FromUint256(txid), i); 386 387 if (output.nValue < params.min_amount || output.nValue > params.max_amount) 388 continue; 389 390 // Skip manually selected coins (the caller can fetch them directly) 391 if (coinControl && coinControl->HasSelected() && coinControl->IsSelected(outpoint)) 392 continue; 393 394 if (wallet.IsLockedCoin(outpoint) && params.skip_locked) 395 continue; 396 397 if (wallet.IsSpent(outpoint)) 398 continue; 399 400 isminetype mine = wallet.IsMine(output); 401 402 if (mine == ISMINE_NO) { 403 continue; 404 } 405 406 if (!allow_used_addresses && wallet.IsSpentKey(output.scriptPubKey)) { 407 continue; 408 } 409 410 std::unique_ptr<SigningProvider> provider = wallet.GetSolvingProvider(output.scriptPubKey); 411 412 int input_bytes = CalculateMaximumSignedInputSize(output, COutPoint(), provider.get(), can_grind_r, coinControl); 413 // Because CalculateMaximumSignedInputSize infers a solvable descriptor to get the satisfaction size, 414 // it is safe to assume that this input is solvable if input_bytes is greater than -1. 415 bool solvable = input_bytes > -1; 416 bool spendable = ((mine & ISMINE_SPENDABLE) != ISMINE_NO) || (((mine & ISMINE_WATCH_ONLY) != ISMINE_NO) && (coinControl && coinControl->fAllowWatchOnly && solvable)); 417 418 // Filter by spendable outputs only 419 if (!spendable && params.only_spendable) continue; 420 421 // Obtain script type 422 std::vector<std::vector<uint8_t>> script_solutions; 423 TxoutType type = Solver(output.scriptPubKey, script_solutions); 424 425 // If the output is P2SH and solvable, we want to know if it is 426 // a P2SH (legacy) or one of P2SH-P2WPKH, P2SH-P2WSH (P2SH-Segwit). We can determine 427 // this from the redeemScript. If the output is not solvable, it will be classified 428 // as a P2SH (legacy), since we have no way of knowing otherwise without the redeemScript 429 bool is_from_p2sh{false}; 430 if (type == TxoutType::SCRIPTHASH && solvable) { 431 CScript script; 432 if (!provider->GetCScript(CScriptID(uint160(script_solutions[0])), script)) continue; 433 type = Solver(script, script_solutions); 434 is_from_p2sh = true; 435 } 436 437 result.Add(GetOutputType(type, is_from_p2sh), 438 COutput(outpoint, output, nDepth, input_bytes, spendable, solvable, safeTx, wtx.GetTxTime(), tx_from_me, feerate)); 439 440 outpoints.push_back(outpoint); 441 442 // Checks the sum amount of all UTXO's. 443 if (params.min_sum_amount != MAX_MONEY) { 444 if (result.GetTotalAmount() >= params.min_sum_amount) { 445 return result; 446 } 447 } 448 449 // Checks the maximum number of UTXO's. 450 if (params.max_count > 0 && result.Size() >= params.max_count) { 451 return result; 452 } 453 } 454 } 455 456 if (feerate.has_value()) { 457 std::map<COutPoint, CAmount> map_of_bump_fees = wallet.chain().calculateIndividualBumpFees(outpoints, feerate.value()); 458 459 for (auto& [_, outputs] : result.coins) { 460 for (auto& output : outputs) { 461 output.ApplyBumpFee(map_of_bump_fees.at(output.outpoint)); 462 } 463 } 464 } 465 466 return result; 467 } 468 469 CoinsResult AvailableCoinsListUnspent(const CWallet& wallet, const CCoinControl* coinControl, CoinFilterParams params) 470 { 471 params.only_spendable = false; 472 return AvailableCoins(wallet, coinControl, /*feerate=*/ std::nullopt, params); 473 } 474 475 const CTxOut& FindNonChangeParentOutput(const CWallet& wallet, const COutPoint& outpoint) 476 { 477 AssertLockHeld(wallet.cs_wallet); 478 const CWalletTx* wtx{Assert(wallet.GetWalletTx(outpoint.hash))}; 479 480 const CTransaction* ptx = wtx->tx.get(); 481 int n = outpoint.n; 482 while (OutputIsChange(wallet, ptx->vout[n]) && ptx->vin.size() > 0) { 483 const COutPoint& prevout = ptx->vin[0].prevout; 484 const CWalletTx* it = wallet.GetWalletTx(prevout.hash); 485 if (!it || it->tx->vout.size() <= prevout.n || 486 !wallet.IsMine(it->tx->vout[prevout.n])) { 487 break; 488 } 489 ptx = it->tx.get(); 490 n = prevout.n; 491 } 492 return ptx->vout[n]; 493 } 494 495 std::map<CTxDestination, std::vector<COutput>> ListCoins(const CWallet& wallet) 496 { 497 AssertLockHeld(wallet.cs_wallet); 498 499 std::map<CTxDestination, std::vector<COutput>> result; 500 501 CCoinControl coin_control; 502 // Include watch-only for LegacyScriptPubKeyMan wallets without private keys 503 coin_control.fAllowWatchOnly = wallet.GetLegacyScriptPubKeyMan() && wallet.IsWalletFlagSet(WALLET_FLAG_DISABLE_PRIVATE_KEYS); 504 CoinFilterParams coins_params; 505 coins_params.only_spendable = false; 506 coins_params.skip_locked = false; 507 for (const COutput& coin : AvailableCoins(wallet, &coin_control, /*feerate=*/std::nullopt, coins_params).All()) { 508 CTxDestination address; 509 if ((coin.spendable || (wallet.IsWalletFlagSet(WALLET_FLAG_DISABLE_PRIVATE_KEYS) && coin.solvable))) { 510 if (!ExtractDestination(FindNonChangeParentOutput(wallet, coin.outpoint).scriptPubKey, address)) { 511 // For backwards compatibility, we convert P2PK output scripts into PKHash destinations 512 if (auto pk_dest = std::get_if<PubKeyDestination>(&address)) { 513 address = PKHash(pk_dest->GetPubKey()); 514 } else { 515 continue; 516 } 517 } 518 result[address].emplace_back(coin); 519 } 520 } 521 return result; 522 } 523 524 FilteredOutputGroups GroupOutputs(const CWallet& wallet, 525 const CoinsResult& coins, 526 const CoinSelectionParams& coin_sel_params, 527 const std::vector<SelectionFilter>& filters, 528 std::vector<OutputGroup>& ret_discarded_groups) 529 { 530 FilteredOutputGroups filtered_groups; 531 532 if (!coin_sel_params.m_avoid_partial_spends) { 533 // Allowing partial spends means no grouping. Each COutput gets its own OutputGroup 534 for (const auto& [type, outputs] : coins.coins) { 535 for (const COutput& output : outputs) { 536 // Get mempool info 537 size_t ancestors, descendants; 538 wallet.chain().getTransactionAncestry(output.outpoint.hash, ancestors, descendants); 539 540 // Create a new group per output and add it to the all groups vector 541 OutputGroup group(coin_sel_params); 542 group.Insert(std::make_shared<COutput>(output), ancestors, descendants); 543 544 // Each filter maps to a different set of groups 545 bool accepted = false; 546 for (const auto& sel_filter : filters) { 547 const auto& filter = sel_filter.filter; 548 if (!group.EligibleForSpending(filter)) continue; 549 filtered_groups[filter].Push(group, type, /*insert_positive=*/true, /*insert_mixed=*/true); 550 accepted = true; 551 } 552 if (!accepted) ret_discarded_groups.emplace_back(group); 553 } 554 } 555 return filtered_groups; 556 } 557 558 // We want to combine COutputs that have the same scriptPubKey into single OutputGroups 559 // except when there are more than OUTPUT_GROUP_MAX_ENTRIES COutputs grouped in an OutputGroup. 560 // To do this, we maintain a map where the key is the scriptPubKey and the value is a vector of OutputGroups. 561 // For each COutput, we check if the scriptPubKey is in the map, and if it is, the COutput is added 562 // to the last OutputGroup in the vector for the scriptPubKey. When the last OutputGroup has 563 // OUTPUT_GROUP_MAX_ENTRIES COutputs, a new OutputGroup is added to the end of the vector. 564 typedef std::map<std::pair<CScript, OutputType>, std::vector<OutputGroup>> ScriptPubKeyToOutgroup; 565 const auto& insert_output = [&]( 566 const std::shared_ptr<COutput>& output, OutputType type, size_t ancestors, size_t descendants, 567 ScriptPubKeyToOutgroup& groups_map) { 568 std::vector<OutputGroup>& groups = groups_map[std::make_pair(output->txout.scriptPubKey,type)]; 569 570 if (groups.size() == 0) { 571 // No OutputGroups for this scriptPubKey yet, add one 572 groups.emplace_back(coin_sel_params); 573 } 574 575 // Get the last OutputGroup in the vector so that we can add the COutput to it 576 // A pointer is used here so that group can be reassigned later if it is full. 577 OutputGroup* group = &groups.back(); 578 579 // Check if this OutputGroup is full. We limit to OUTPUT_GROUP_MAX_ENTRIES when using -avoidpartialspends 580 // to avoid surprising users with very high fees. 581 if (group->m_outputs.size() >= OUTPUT_GROUP_MAX_ENTRIES) { 582 // The last output group is full, add a new group to the vector and use that group for the insertion 583 groups.emplace_back(coin_sel_params); 584 group = &groups.back(); 585 } 586 587 group->Insert(output, ancestors, descendants); 588 }; 589 590 ScriptPubKeyToOutgroup spk_to_groups_map; 591 ScriptPubKeyToOutgroup spk_to_positive_groups_map; 592 for (const auto& [type, outs] : coins.coins) { 593 for (const COutput& output : outs) { 594 size_t ancestors, descendants; 595 wallet.chain().getTransactionAncestry(output.outpoint.hash, ancestors, descendants); 596 597 const auto& shared_output = std::make_shared<COutput>(output); 598 // Filter for positive only before adding the output 599 if (output.GetEffectiveValue() > 0) { 600 insert_output(shared_output, type, ancestors, descendants, spk_to_positive_groups_map); 601 } 602 603 // 'All' groups 604 insert_output(shared_output, type, ancestors, descendants, spk_to_groups_map); 605 } 606 } 607 608 // Now we go through the entire maps and pull out the OutputGroups 609 const auto& push_output_groups = [&](const ScriptPubKeyToOutgroup& groups_map, bool positive_only) { 610 for (const auto& [script, groups] : groups_map) { 611 // Go through the vector backwards. This allows for the first item we deal with being the partial group. 612 for (auto group_it = groups.rbegin(); group_it != groups.rend(); group_it++) { 613 const OutputGroup& group = *group_it; 614 615 // Each filter maps to a different set of groups 616 bool accepted = false; 617 for (const auto& sel_filter : filters) { 618 const auto& filter = sel_filter.filter; 619 if (!group.EligibleForSpending(filter)) continue; 620 621 // Don't include partial groups if there are full groups too and we don't want partial groups 622 if (group_it == groups.rbegin() && groups.size() > 1 && !filter.m_include_partial_groups) { 623 continue; 624 } 625 626 OutputType type = script.second; 627 // Either insert the group into the positive-only groups or the mixed ones. 628 filtered_groups[filter].Push(group, type, positive_only, /*insert_mixed=*/!positive_only); 629 accepted = true; 630 } 631 if (!accepted) ret_discarded_groups.emplace_back(group); 632 } 633 } 634 }; 635 636 push_output_groups(spk_to_groups_map, /*positive_only=*/ false); 637 push_output_groups(spk_to_positive_groups_map, /*positive_only=*/ true); 638 639 return filtered_groups; 640 } 641 642 FilteredOutputGroups GroupOutputs(const CWallet& wallet, 643 const CoinsResult& coins, 644 const CoinSelectionParams& params, 645 const std::vector<SelectionFilter>& filters) 646 { 647 std::vector<OutputGroup> unused; 648 return GroupOutputs(wallet, coins, params, filters, unused); 649 } 650 651 // Returns true if the result contains an error and the message is not empty 652 static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); } 653 654 util::Result<SelectionResult> AttemptSelection(interfaces::Chain& chain, const CAmount& nTargetValue, OutputGroupTypeMap& groups, 655 const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types) 656 { 657 // Run coin selection on each OutputType and compute the Waste Metric 658 std::vector<SelectionResult> results; 659 for (auto& [type, group] : groups.groups_by_type) { 660 auto result{ChooseSelectionResult(chain, nTargetValue, group, coin_selection_params)}; 661 // If any specific error message appears here, then something particularly wrong happened. 662 if (HasErrorMsg(result)) return result; // So let's return the specific error. 663 // Append the favorable result. 664 if (result) results.push_back(*result); 665 } 666 // If we have at least one solution for funding the transaction without mixing, choose the minimum one according to waste metric 667 // and return the result 668 if (results.size() > 0) return *std::min_element(results.begin(), results.end()); 669 670 // If we can't fund the transaction from any individual OutputType, run coin selection one last time 671 // over all available coins, which would allow mixing. 672 // If TypesCount() <= 1, there is nothing to mix. 673 if (allow_mixed_output_types && groups.TypesCount() > 1) { 674 return ChooseSelectionResult(chain, nTargetValue, groups.all_groups, coin_selection_params); 675 } 676 // Either mixing is not allowed and we couldn't find a solution from any single OutputType, or mixing was allowed and we still couldn't 677 // find a solution using all available coins 678 return util::Error(); 679 }; 680 681 util::Result<SelectionResult> ChooseSelectionResult(interfaces::Chain& chain, const CAmount& nTargetValue, Groups& groups, const CoinSelectionParams& coin_selection_params) 682 { 683 // Vector of results. We will choose the best one based on waste. 684 std::vector<SelectionResult> results; 685 std::vector<util::Result<SelectionResult>> errors; 686 auto append_error = [&] (const util::Result<SelectionResult>& result) { 687 // If any specific error message appears here, then something different from a simple "no selection found" happened. 688 // Let's save it, so it can be retrieved to the user if no other selection algorithm succeeded. 689 if (HasErrorMsg(result)) { 690 errors.emplace_back(result); 691 } 692 }; 693 694 // Maximum allowed weight 695 int max_inputs_weight = MAX_STANDARD_TX_WEIGHT - (coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR); 696 697 // SFFO frequently causes issues in the context of changeless input sets: skip BnB when SFFO is active 698 if (!coin_selection_params.m_subtract_fee_outputs) { 699 if (auto bnb_result{SelectCoinsBnB(groups.positive_group, nTargetValue, coin_selection_params.m_cost_of_change, max_inputs_weight)}) { 700 results.push_back(*bnb_result); 701 } else append_error(bnb_result); 702 } 703 704 // As Knapsack and SRD can create change, also deduce change weight. 705 max_inputs_weight -= (coin_selection_params.change_output_size * WITNESS_SCALE_FACTOR); 706 707 // 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. 708 if (auto knapsack_result{KnapsackSolver(groups.mixed_group, nTargetValue, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast, max_inputs_weight)}) { 709 results.push_back(*knapsack_result); 710 } else append_error(knapsack_result); 711 712 if (coin_selection_params.m_effective_feerate > CFeeRate{3 * coin_selection_params.m_long_term_feerate}) { // Minimize input set for feerates of at least 3×LTFRE (default: 30 ṩ/vB+) 713 if (auto cg_result{CoinGrinder(groups.positive_group, nTargetValue, coin_selection_params.m_min_change_target, max_inputs_weight)}) { 714 cg_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee); 715 results.push_back(*cg_result); 716 } else { 717 append_error(cg_result); 718 } 719 } 720 721 if (auto srd_result{SelectCoinsSRD(groups.positive_group, nTargetValue, coin_selection_params.m_change_fee, coin_selection_params.rng_fast, max_inputs_weight)}) { 722 results.push_back(*srd_result); 723 } else append_error(srd_result); 724 725 if (results.empty()) { 726 // No solution found, retrieve the first explicit error (if any). 727 // future: add 'severity level' to errors so the worst one can be retrieved instead of the first one. 728 return errors.empty() ? util::Error() : errors.front(); 729 } 730 731 // If the chosen input set has unconfirmed inputs, check for synergies from overlapping ancestry 732 for (auto& result : results) { 733 std::vector<COutPoint> outpoints; 734 std::set<std::shared_ptr<COutput>> coins = result.GetInputSet(); 735 CAmount summed_bump_fees = 0; 736 for (auto& coin : coins) { 737 if (coin->depth > 0) continue; // Bump fees only exist for unconfirmed inputs 738 outpoints.push_back(coin->outpoint); 739 summed_bump_fees += coin->ancestor_bump_fees; 740 } 741 std::optional<CAmount> combined_bump_fee = chain.calculateCombinedBumpFee(outpoints, coin_selection_params.m_effective_feerate); 742 if (!combined_bump_fee.has_value()) { 743 return util::Error{_("Failed to calculate bump fees, because unconfirmed UTXOs depend on enormous cluster of unconfirmed transactions.")}; 744 } 745 CAmount bump_fee_overestimate = summed_bump_fees - combined_bump_fee.value(); 746 if (bump_fee_overestimate) { 747 result.SetBumpFeeDiscount(bump_fee_overestimate); 748 } 749 result.ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee); 750 } 751 752 // Choose the result with the least waste 753 // If the waste is the same, choose the one which spends more inputs. 754 return *std::min_element(results.begin(), results.end()); 755 } 756 757 util::Result<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& available_coins, const PreSelectedInputs& pre_set_inputs, 758 const CAmount& nTargetValue, const CCoinControl& coin_control, 759 const CoinSelectionParams& coin_selection_params) 760 { 761 // Deduct preset inputs amount from the search target 762 CAmount selection_target = nTargetValue - pre_set_inputs.total_amount; 763 764 // Return if automatic coin selection is disabled, and we don't cover the selection target 765 if (!coin_control.m_allow_other_inputs && selection_target > 0) { 766 return util::Error{_("The preselected coins total amount does not cover the transaction target. " 767 "Please allow other inputs to be automatically selected or include more coins manually")}; 768 } 769 770 // Return if we can cover the target only with the preset inputs 771 if (selection_target <= 0) { 772 SelectionResult result(nTargetValue, SelectionAlgorithm::MANUAL); 773 result.AddInputs(pre_set_inputs.coins, coin_selection_params.m_subtract_fee_outputs); 774 result.ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee); 775 return result; 776 } 777 778 // Return early if we cannot cover the target with the wallet's UTXO. 779 // We use the total effective value if we are not subtracting fee from outputs and 'available_coins' contains the data. 780 CAmount available_coins_total_amount = coin_selection_params.m_subtract_fee_outputs ? available_coins.GetTotalAmount() : 781 (available_coins.GetEffectiveTotalAmount().has_value() ? *available_coins.GetEffectiveTotalAmount() : 0); 782 if (selection_target > available_coins_total_amount) { 783 return util::Error(); // Insufficient funds 784 } 785 786 // Start wallet Coin Selection procedure 787 auto op_selection_result = AutomaticCoinSelection(wallet, available_coins, selection_target, coin_selection_params); 788 if (!op_selection_result) return op_selection_result; 789 790 // If needed, add preset inputs to the automatic coin selection result 791 if (!pre_set_inputs.coins.empty()) { 792 SelectionResult preselected(pre_set_inputs.total_amount, SelectionAlgorithm::MANUAL); 793 preselected.AddInputs(pre_set_inputs.coins, coin_selection_params.m_subtract_fee_outputs); 794 op_selection_result->Merge(preselected); 795 op_selection_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, 796 coin_selection_params.m_cost_of_change, 797 coin_selection_params.m_change_fee); 798 } 799 return op_selection_result; 800 } 801 802 util::Result<SelectionResult> AutomaticCoinSelection(const CWallet& wallet, CoinsResult& available_coins, const CAmount& value_to_select, const CoinSelectionParams& coin_selection_params) 803 { 804 unsigned int limit_ancestor_count = 0; 805 unsigned int limit_descendant_count = 0; 806 wallet.chain().getPackageLimits(limit_ancestor_count, limit_descendant_count); 807 const size_t max_ancestors = (size_t)std::max<int64_t>(1, limit_ancestor_count); 808 const size_t max_descendants = (size_t)std::max<int64_t>(1, limit_descendant_count); 809 const bool fRejectLongChains = gArgs.GetBoolArg("-walletrejectlongchains", DEFAULT_WALLET_REJECT_LONG_CHAINS); 810 811 // Cases where we have 101+ outputs all pointing to the same destination may result in 812 // privacy leaks as they will potentially be deterministically sorted. We solve that by 813 // explicitly shuffling the outputs before processing 814 if (coin_selection_params.m_avoid_partial_spends && available_coins.Size() > OUTPUT_GROUP_MAX_ENTRIES) { 815 available_coins.Shuffle(coin_selection_params.rng_fast); 816 } 817 818 // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the 819 // transaction at a target feerate. If an attempt fails, more attempts may be made using a more 820 // permissive CoinEligibilityFilter. 821 util::Result<SelectionResult> res = [&] { 822 // Place coins eligibility filters on a scope increasing order. 823 std::vector<SelectionFilter> ordered_filters{ 824 // If possible, fund the transaction with confirmed UTXOs only. Prefer at least six 825 // confirmations on outputs received from other wallets and only spend confirmed change. 826 {CoinEligibilityFilter(1, 6, 0), /*allow_mixed_output_types=*/false}, 827 {CoinEligibilityFilter(1, 1, 0)}, 828 }; 829 // Fall back to using zero confirmation change (but with as few ancestors in the mempool as 830 // possible) if we cannot fund the transaction otherwise. 831 if (wallet.m_spend_zero_conf_change) { 832 ordered_filters.push_back({CoinEligibilityFilter(0, 1, 2)}); 833 ordered_filters.push_back({CoinEligibilityFilter(0, 1, std::min(size_t{4}, max_ancestors/3), std::min(size_t{4}, max_descendants/3))}); 834 ordered_filters.push_back({CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2)}); 835 // If partial groups are allowed, relax the requirement of spending OutputGroups (groups 836 // of UTXOs sent to the same address, which are obviously controlled by a single wallet) 837 // in their entirety. 838 ordered_filters.push_back({CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, /*include_partial=*/true)}); 839 // Try with unsafe inputs if they are allowed. This may spend unconfirmed outputs 840 // received from other wallets. 841 if (coin_selection_params.m_include_unsafe_inputs) { 842 ordered_filters.push_back({CoinEligibilityFilter(/*conf_mine=*/0, /*conf_theirs*/0, max_ancestors-1, max_descendants-1, /*include_partial=*/true)}); 843 } 844 // Try with unlimited ancestors/descendants. The transaction will still need to meet 845 // mempool ancestor/descendant policy to be accepted to mempool and broadcasted, but 846 // OutputGroups use heuristics that may overestimate ancestor/descendant counts. 847 if (!fRejectLongChains) { 848 ordered_filters.push_back({CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(), 849 std::numeric_limits<uint64_t>::max(), 850 /*include_partial=*/true)}); 851 } 852 } 853 854 // Group outputs and map them by coin eligibility filter 855 std::vector<OutputGroup> discarded_groups; 856 FilteredOutputGroups filtered_groups = GroupOutputs(wallet, available_coins, coin_selection_params, ordered_filters, discarded_groups); 857 858 // Check if we still have enough balance after applying filters (some coins might be discarded) 859 CAmount total_discarded = 0; 860 CAmount total_unconf_long_chain = 0; 861 for (const auto& group : discarded_groups) { 862 total_discarded += group.GetSelectionAmount(); 863 if (group.m_ancestors >= max_ancestors || group.m_descendants >= max_descendants) total_unconf_long_chain += group.GetSelectionAmount(); 864 } 865 866 if (CAmount total_amount = available_coins.GetTotalAmount() - total_discarded < value_to_select) { 867 // Special case, too-long-mempool cluster. 868 if (total_amount + total_unconf_long_chain > value_to_select) { 869 return util::Result<SelectionResult>({_("Unconfirmed UTXOs are available, but spending them creates a chain of transactions that will be rejected by the mempool")}); 870 } 871 return util::Result<SelectionResult>(util::Error()); // General "Insufficient Funds" 872 } 873 874 // Walk-through the filters until the solution gets found. 875 // If no solution is found, return the first detailed error (if any). 876 // future: add "error level" so the worst one can be picked instead. 877 std::vector<util::Result<SelectionResult>> res_detailed_errors; 878 for (const auto& select_filter : ordered_filters) { 879 auto it = filtered_groups.find(select_filter.filter); 880 if (it == filtered_groups.end()) continue; 881 if (auto res{AttemptSelection(wallet.chain(), value_to_select, it->second, 882 coin_selection_params, select_filter.allow_mixed_output_types)}) { 883 return res; // result found 884 } else { 885 // If any specific error message appears here, then something particularly wrong might have happened. 886 // Save the error and continue the selection process. So if no solutions gets found, we can return 887 // the detailed error to the upper layers. 888 if (HasErrorMsg(res)) res_detailed_errors.emplace_back(res); 889 } 890 } 891 892 // Return right away if we have a detailed error 893 if (!res_detailed_errors.empty()) return res_detailed_errors.front(); 894 895 896 // General "Insufficient Funds" 897 return util::Result<SelectionResult>(util::Error()); 898 }(); 899 900 return res; 901 } 902 903 static bool IsCurrentForAntiFeeSniping(interfaces::Chain& chain, const uint256& block_hash) 904 { 905 if (chain.isInitialBlockDownload()) { 906 return false; 907 } 908 constexpr int64_t MAX_ANTI_FEE_SNIPING_TIP_AGE = 8 * 60 * 60; // in seconds 909 int64_t block_time; 910 CHECK_NONFATAL(chain.findBlock(block_hash, FoundBlock().time(block_time))); 911 if (block_time < (GetTime() - MAX_ANTI_FEE_SNIPING_TIP_AGE)) { 912 return false; 913 } 914 return true; 915 } 916 917 /** 918 * Set a height-based locktime for new transactions (uses the height of the 919 * current chain tip unless we are not synced with the current chain 920 */ 921 static void DiscourageFeeSniping(CMutableTransaction& tx, FastRandomContext& rng_fast, 922 interfaces::Chain& chain, const uint256& block_hash, int block_height) 923 { 924 // All inputs must be added by now 925 assert(!tx.vin.empty()); 926 // Discourage fee sniping. 927 // 928 // For a large miner the value of the transactions in the best block and 929 // the mempool can exceed the cost of deliberately attempting to mine two 930 // blocks to orphan the current best block. By setting nLockTime such that 931 // only the next block can include the transaction, we discourage this 932 // practice as the height restricted and limited blocksize gives miners 933 // considering fee sniping fewer options for pulling off this attack. 934 // 935 // A simple way to think about this is from the wallet's point of view we 936 // always want the blockchain to move forward. By setting nLockTime this 937 // way we're basically making the statement that we only want this 938 // transaction to appear in the next block; we don't want to potentially 939 // encourage reorgs by allowing transactions to appear at lower heights 940 // than the next block in forks of the best chain. 941 // 942 // Of course, the subsidy is high enough, and transaction volume low 943 // enough, that fee sniping isn't a problem yet, but by implementing a fix 944 // now we ensure code won't be written that makes assumptions about 945 // nLockTime that preclude a fix later. 946 if (IsCurrentForAntiFeeSniping(chain, block_hash)) { 947 tx.nLockTime = block_height; 948 949 // Secondly occasionally randomly pick a nLockTime even further back, so 950 // that transactions that are delayed after signing for whatever reason, 951 // e.g. high-latency mix networks and some CoinJoin implementations, have 952 // better privacy. 953 if (rng_fast.randrange(10) == 0) { 954 tx.nLockTime = std::max(0, int(tx.nLockTime) - int(rng_fast.randrange(100))); 955 } 956 } else { 957 // If our chain is lagging behind, we can't discourage fee sniping nor help 958 // the privacy of high-latency transactions. To avoid leaking a potentially 959 // unique "nLockTime fingerprint", set nLockTime to a constant. 960 tx.nLockTime = 0; 961 } 962 // Sanity check all values 963 assert(tx.nLockTime < LOCKTIME_THRESHOLD); // Type must be block height 964 assert(tx.nLockTime <= uint64_t(block_height)); 965 for (const auto& in : tx.vin) { 966 // Can not be FINAL for locktime to work 967 assert(in.nSequence != CTxIn::SEQUENCE_FINAL); 968 // May be MAX NONFINAL to disable both BIP68 and BIP125 969 if (in.nSequence == CTxIn::MAX_SEQUENCE_NONFINAL) continue; 970 // May be MAX BIP125 to disable BIP68 and enable BIP125 971 if (in.nSequence == MAX_BIP125_RBF_SEQUENCE) continue; 972 // The wallet does not support any other sequence-use right now. 973 assert(false); 974 } 975 } 976 977 static util::Result<CreatedTransactionResult> CreateTransactionInternal( 978 CWallet& wallet, 979 const std::vector<CRecipient>& vecSend, 980 std::optional<unsigned int> change_pos, 981 const CCoinControl& coin_control, 982 bool sign) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet) 983 { 984 AssertLockHeld(wallet.cs_wallet); 985 986 FastRandomContext rng_fast; 987 CMutableTransaction txNew; // The resulting transaction that we make 988 989 if (coin_control.m_version) { 990 txNew.nVersion = coin_control.m_version.value(); 991 } 992 993 CoinSelectionParams coin_selection_params{rng_fast}; // Parameters for coin selection, init with dummy 994 coin_selection_params.m_avoid_partial_spends = coin_control.m_avoid_partial_spends; 995 coin_selection_params.m_include_unsafe_inputs = coin_control.m_include_unsafe_inputs; 996 997 // Set the long term feerate estimate to the wallet's consolidate feerate 998 coin_selection_params.m_long_term_feerate = wallet.m_consolidate_feerate; 999 1000 CAmount recipients_sum = 0; 1001 const OutputType change_type = wallet.TransactionChangeType(coin_control.m_change_type ? *coin_control.m_change_type : wallet.m_default_change_type, vecSend); 1002 ReserveDestination reservedest(&wallet, change_type); 1003 unsigned int outputs_to_subtract_fee_from = 0; // The number of outputs which we are subtracting the fee from 1004 for (const auto& recipient : vecSend) { 1005 recipients_sum += recipient.nAmount; 1006 1007 if (recipient.fSubtractFeeFromAmount) { 1008 outputs_to_subtract_fee_from++; 1009 coin_selection_params.m_subtract_fee_outputs = true; 1010 } 1011 } 1012 1013 // Create change script that will be used if we need change 1014 CScript scriptChange; 1015 bilingual_str error; // possible error str 1016 1017 // coin control: send change to custom address 1018 if (!std::get_if<CNoDestination>(&coin_control.destChange)) { 1019 scriptChange = GetScriptForDestination(coin_control.destChange); 1020 } else { // no coin control: send change to newly generated address 1021 // Note: We use a new key here to keep it from being obvious which side is the change. 1022 // The drawback is that by not reusing a previous key, the change may be lost if a 1023 // backup is restored, if the backup doesn't have the new private key for the change. 1024 // If we reused the old key, it would be possible to add code to look for and 1025 // rediscover unknown transactions that were written with keys of ours to recover 1026 // post-backup change. 1027 1028 // Reserve a new key pair from key pool. If it fails, provide a dummy 1029 // destination in case we don't need change. 1030 CTxDestination dest; 1031 auto op_dest = reservedest.GetReservedDestination(true); 1032 if (!op_dest) { 1033 error = _("Transaction needs a change address, but we can't generate it.") + Untranslated(" ") + util::ErrorString(op_dest); 1034 } else { 1035 dest = *op_dest; 1036 scriptChange = GetScriptForDestination(dest); 1037 } 1038 // A valid destination implies a change script (and 1039 // vice-versa). An empty change script will abort later, if the 1040 // change keypool ran out, but change is required. 1041 CHECK_NONFATAL(IsValidDestination(dest) != scriptChange.empty()); 1042 } 1043 CTxOut change_prototype_txout(0, scriptChange); 1044 coin_selection_params.change_output_size = GetSerializeSize(change_prototype_txout); 1045 1046 // Get size of spending the change output 1047 int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, &wallet, /*coin_control=*/nullptr); 1048 // If the wallet doesn't know how to sign change output, assume p2sh-p2wpkh 1049 // as lower-bound to allow BnB to do it's thing 1050 if (change_spend_size == -1) { 1051 coin_selection_params.change_spend_size = DUMMY_NESTED_P2WPKH_INPUT_SIZE; 1052 } else { 1053 coin_selection_params.change_spend_size = (size_t)change_spend_size; 1054 } 1055 1056 // Set discard feerate 1057 coin_selection_params.m_discard_feerate = GetDiscardRate(wallet); 1058 1059 // Get the fee rate to use effective values in coin selection 1060 FeeCalculation feeCalc; 1061 coin_selection_params.m_effective_feerate = GetMinimumFeeRate(wallet, coin_control, &feeCalc); 1062 // Do not, ever, assume that it's fine to change the fee rate if the user has explicitly 1063 // provided one 1064 if (coin_control.m_feerate && coin_selection_params.m_effective_feerate > *coin_control.m_feerate) { 1065 return util::Error{strprintf(_("Fee rate (%s) is lower than the minimum fee rate setting (%s)"), coin_control.m_feerate->ToString(FeeEstimateMode::SAT_VB), coin_selection_params.m_effective_feerate.ToString(FeeEstimateMode::SAT_VB))}; 1066 } 1067 if (feeCalc.reason == FeeReason::FALLBACK && !wallet.m_allow_fallback_fee) { 1068 // eventually allow a fallback fee 1069 return util::Error{strprintf(_("Fee estimation failed. Fallbackfee is disabled. Wait a few blocks or enable %s."), "-fallbackfee")}; 1070 } 1071 1072 // Calculate the cost of change 1073 // Cost of change is the cost of creating the change output + cost of spending the change output in the future. 1074 // For creating the change output now, we use the effective feerate. 1075 // For spending the change output in the future, we use the discard feerate for now. 1076 // So cost of change = (change output size * effective feerate) + (size of spending change output * discard feerate) 1077 coin_selection_params.m_change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size); 1078 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; 1079 1080 coin_selection_params.m_min_change_target = GenerateChangeTarget(std::floor(recipients_sum / vecSend.size()), coin_selection_params.m_change_fee, rng_fast); 1081 1082 // The smallest change amount should be: 1083 // 1. at least equal to dust threshold 1084 // 2. at least 1 sat greater than fees to spend it at m_discard_feerate 1085 const auto dust = GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate); 1086 const auto change_spend_fee = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size); 1087 coin_selection_params.min_viable_change = std::max(change_spend_fee + 1, dust); 1088 1089 // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 witness overhead (dummy, flag, stack size) 1090 coin_selection_params.tx_noinputs_size = 10 + GetSizeOfCompactSize(vecSend.size()); // bytes for output count 1091 1092 // vouts to the payees 1093 for (const auto& recipient : vecSend) 1094 { 1095 CTxOut txout(recipient.nAmount, GetScriptForDestination(recipient.dest)); 1096 1097 // Include the fee cost for outputs. 1098 coin_selection_params.tx_noinputs_size += ::GetSerializeSize(txout); 1099 1100 if (IsDust(txout, wallet.chain().relayDustFee())) { 1101 return util::Error{_("Transaction amount too small")}; 1102 } 1103 txNew.vout.push_back(txout); 1104 } 1105 1106 // Include the fees for things that aren't inputs, excluding the change output 1107 const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.tx_noinputs_size); 1108 CAmount selection_target = recipients_sum + not_input_fees; 1109 1110 // This can only happen if feerate is 0, and requested destinations are value of 0 (e.g. OP_RETURN) 1111 // and no pre-selected inputs. This will result in 0-input transaction, which is consensus-invalid anyways 1112 if (selection_target == 0 && !coin_control.HasSelected()) { 1113 return util::Error{_("Transaction requires one destination of non-0 value, a non-0 feerate, or a pre-selected input")}; 1114 } 1115 1116 // Fetch manually selected coins 1117 PreSelectedInputs preset_inputs; 1118 if (coin_control.HasSelected()) { 1119 auto res_fetch_inputs = FetchSelectedInputs(wallet, coin_control, coin_selection_params); 1120 if (!res_fetch_inputs) return util::Error{util::ErrorString(res_fetch_inputs)}; 1121 preset_inputs = *res_fetch_inputs; 1122 } 1123 1124 // Fetch wallet available coins if "other inputs" are 1125 // allowed (coins automatically selected by the wallet) 1126 CoinsResult available_coins; 1127 if (coin_control.m_allow_other_inputs) { 1128 available_coins = AvailableCoins(wallet, &coin_control, coin_selection_params.m_effective_feerate); 1129 } 1130 1131 // Choose coins to use 1132 auto select_coins_res = SelectCoins(wallet, available_coins, preset_inputs, /*nTargetValue=*/selection_target, coin_control, coin_selection_params); 1133 if (!select_coins_res) { 1134 // 'SelectCoins' either returns a specific error message or, if empty, means a general "Insufficient funds". 1135 const bilingual_str& err = util::ErrorString(select_coins_res); 1136 return util::Error{err.empty() ?_("Insufficient funds") : err}; 1137 } 1138 const SelectionResult& result = *select_coins_res; 1139 TRACE5(coin_selection, selected_coins, 1140 wallet.GetName().c_str(), 1141 GetAlgorithmName(result.GetAlgo()).c_str(), 1142 result.GetTarget(), 1143 result.GetWaste(), 1144 result.GetSelectedValue()); 1145 1146 const CAmount change_amount = result.GetChange(coin_selection_params.min_viable_change, coin_selection_params.m_change_fee); 1147 if (change_amount > 0) { 1148 CTxOut newTxOut(change_amount, scriptChange); 1149 if (!change_pos) { 1150 // Insert change txn at random position: 1151 change_pos = rng_fast.randrange(txNew.vout.size() + 1); 1152 } else if ((unsigned int)*change_pos > txNew.vout.size()) { 1153 return util::Error{_("Transaction change output index out of range")}; 1154 } 1155 txNew.vout.insert(txNew.vout.begin() + *change_pos, newTxOut); 1156 } else { 1157 change_pos = std::nullopt; 1158 } 1159 1160 // Shuffle selected coins and fill in final vin 1161 std::vector<std::shared_ptr<COutput>> selected_coins = result.GetShuffledInputVector(); 1162 1163 if (coin_control.HasSelected() && coin_control.HasSelectedOrder()) { 1164 // When there are preselected inputs, we need to move them to be the first UTXOs 1165 // and have them be in the order selected. We can use stable_sort for this, where we 1166 // compare with the positions stored in coin_control. The COutputs that have positions 1167 // will be placed before those that don't, and those positions will be in order. 1168 std::stable_sort(selected_coins.begin(), selected_coins.end(), 1169 [&coin_control](const std::shared_ptr<COutput>& a, const std::shared_ptr<COutput>& b) { 1170 auto a_pos = coin_control.GetSelectionPos(a->outpoint); 1171 auto b_pos = coin_control.GetSelectionPos(b->outpoint); 1172 if (a_pos.has_value() && b_pos.has_value()) { 1173 return a_pos.value() < b_pos.value(); 1174 } else if (a_pos.has_value() && !b_pos.has_value()) { 1175 return true; 1176 } else { 1177 return false; 1178 } 1179 }); 1180 } 1181 1182 // The sequence number is set to non-maxint so that DiscourageFeeSniping 1183 // works. 1184 // 1185 // BIP125 defines opt-in RBF as any nSequence < maxint-1, so 1186 // we use the highest possible value in that range (maxint-2) 1187 // to avoid conflicting with other possible uses of nSequence, 1188 // and in the spirit of "smallest possible change from prior 1189 // behavior." 1190 bool use_anti_fee_sniping = true; 1191 const uint32_t default_sequence{coin_control.m_signal_bip125_rbf.value_or(wallet.m_signal_rbf) ? MAX_BIP125_RBF_SEQUENCE : CTxIn::MAX_SEQUENCE_NONFINAL}; 1192 for (const auto& coin : selected_coins) { 1193 std::optional<uint32_t> sequence = coin_control.GetSequence(coin->outpoint); 1194 if (sequence) { 1195 // If an input has a preset sequence, we can't do anti-fee-sniping 1196 use_anti_fee_sniping = false; 1197 } 1198 txNew.vin.emplace_back(coin->outpoint, CScript{}, sequence.value_or(default_sequence)); 1199 1200 auto scripts = coin_control.GetScripts(coin->outpoint); 1201 if (scripts.first) { 1202 txNew.vin.back().scriptSig = *scripts.first; 1203 } 1204 if (scripts.second) { 1205 txNew.vin.back().scriptWitness = *scripts.second; 1206 } 1207 } 1208 if (coin_control.m_locktime) { 1209 txNew.nLockTime = coin_control.m_locktime.value(); 1210 // If we have a locktime set, we can't use anti-fee-sniping 1211 use_anti_fee_sniping = false; 1212 } 1213 if (use_anti_fee_sniping) { 1214 DiscourageFeeSniping(txNew, rng_fast, wallet.chain(), wallet.GetLastBlockHash(), wallet.GetLastBlockHeight()); 1215 } 1216 1217 // Calculate the transaction fee 1218 TxSize tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), &wallet, &coin_control); 1219 int nBytes = tx_sizes.vsize; 1220 if (nBytes == -1) { 1221 return util::Error{_("Missing solving data for estimating transaction size")}; 1222 } 1223 CAmount fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes) + result.GetTotalBumpFees(); 1224 const CAmount output_value = CalculateOutputValue(txNew); 1225 Assume(recipients_sum + change_amount == output_value); 1226 CAmount current_fee = result.GetSelectedValue() - output_value; 1227 1228 // Sanity check that the fee cannot be negative as that means we have more output value than input value 1229 if (current_fee < 0) { 1230 return util::Error{Untranslated(STR_INTERNAL_BUG("Fee paid < 0"))}; 1231 } 1232 1233 // If there is a change output and we overpay the fees then increase the change to match the fee needed 1234 if (change_pos && fee_needed < current_fee) { 1235 auto& change = txNew.vout.at(*change_pos); 1236 change.nValue += current_fee - fee_needed; 1237 current_fee = result.GetSelectedValue() - CalculateOutputValue(txNew); 1238 if (fee_needed != current_fee) { 1239 return util::Error{Untranslated(STR_INTERNAL_BUG("Change adjustment: Fee needed != fee paid"))}; 1240 } 1241 } 1242 1243 // Reduce output values for subtractFeeFromAmount 1244 if (coin_selection_params.m_subtract_fee_outputs) { 1245 CAmount to_reduce = fee_needed - current_fee; 1246 unsigned int i = 0; 1247 bool fFirst = true; 1248 for (const auto& recipient : vecSend) 1249 { 1250 if (change_pos && i == *change_pos) { 1251 ++i; 1252 } 1253 CTxOut& txout = txNew.vout[i]; 1254 1255 if (recipient.fSubtractFeeFromAmount) 1256 { 1257 txout.nValue -= to_reduce / outputs_to_subtract_fee_from; // Subtract fee equally from each selected recipient 1258 1259 if (fFirst) // first receiver pays the remainder not divisible by output count 1260 { 1261 fFirst = false; 1262 txout.nValue -= to_reduce % outputs_to_subtract_fee_from; 1263 } 1264 1265 // Error if this output is reduced to be below dust 1266 if (IsDust(txout, wallet.chain().relayDustFee())) { 1267 if (txout.nValue < 0) { 1268 return util::Error{_("The transaction amount is too small to pay the fee")}; 1269 } else { 1270 return util::Error{_("The transaction amount is too small to send after the fee has been deducted")}; 1271 } 1272 } 1273 } 1274 ++i; 1275 } 1276 current_fee = result.GetSelectedValue() - CalculateOutputValue(txNew); 1277 if (fee_needed != current_fee) { 1278 return util::Error{Untranslated(STR_INTERNAL_BUG("SFFO: Fee needed != fee paid"))}; 1279 } 1280 } 1281 1282 // fee_needed should now always be less than or equal to the current fees that we pay. 1283 // If it is not, it is a bug. 1284 if (fee_needed > current_fee) { 1285 return util::Error{Untranslated(STR_INTERNAL_BUG("Fee needed > fee paid"))}; 1286 } 1287 1288 // Give up if change keypool ran out and change is required 1289 if (scriptChange.empty() && change_pos) { 1290 return util::Error{error}; 1291 } 1292 1293 if (sign && !wallet.SignTransaction(txNew)) { 1294 return util::Error{_("Signing transaction failed")}; 1295 } 1296 1297 // Return the constructed transaction data. 1298 CTransactionRef tx = MakeTransactionRef(std::move(txNew)); 1299 1300 // Limit size 1301 if ((sign && GetTransactionWeight(*tx) > MAX_STANDARD_TX_WEIGHT) || 1302 (!sign && tx_sizes.weight > MAX_STANDARD_TX_WEIGHT)) 1303 { 1304 return util::Error{_("Transaction too large")}; 1305 } 1306 1307 if (current_fee > wallet.m_default_max_tx_fee) { 1308 return util::Error{TransactionErrorString(TransactionError::MAX_FEE_EXCEEDED)}; 1309 } 1310 1311 if (gArgs.GetBoolArg("-walletrejectlongchains", DEFAULT_WALLET_REJECT_LONG_CHAINS)) { 1312 // Lastly, ensure this tx will pass the mempool's chain limits 1313 auto result = wallet.chain().checkChainLimits(tx); 1314 if (!result) { 1315 return util::Error{util::ErrorString(result)}; 1316 } 1317 } 1318 1319 // Before we return success, we assume any change key will be used to prevent 1320 // accidental reuse. 1321 reservedest.KeepDestination(); 1322 1323 wallet.WalletLogPrintf("Coin Selection: Algorithm:%s, Waste Metric Score:%d\n", GetAlgorithmName(result.GetAlgo()), result.GetWaste()); 1324 wallet.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", 1325 current_fee, nBytes, feeCalc.returnedTarget, feeCalc.desiredTarget, StringForFeeReason(feeCalc.reason), feeCalc.est.decay, 1326 feeCalc.est.pass.start, feeCalc.est.pass.end, 1327 (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, 1328 feeCalc.est.pass.withinTarget, feeCalc.est.pass.totalConfirmed, feeCalc.est.pass.inMempool, feeCalc.est.pass.leftMempool, 1329 feeCalc.est.fail.start, feeCalc.est.fail.end, 1330 (feeCalc.est.fail.totalConfirmed + feeCalc.est.fail.inMempool + feeCalc.est.fail.leftMempool) > 0.0 ? 100 * feeCalc.est.fail.withinTarget / (feeCalc.est.fail.totalConfirmed + feeCalc.est.fail.inMempool + feeCalc.est.fail.leftMempool) : 0.0, 1331 feeCalc.est.fail.withinTarget, feeCalc.est.fail.totalConfirmed, feeCalc.est.fail.inMempool, feeCalc.est.fail.leftMempool); 1332 return CreatedTransactionResult(tx, current_fee, change_pos, feeCalc); 1333 } 1334 1335 util::Result<CreatedTransactionResult> CreateTransaction( 1336 CWallet& wallet, 1337 const std::vector<CRecipient>& vecSend, 1338 std::optional<unsigned int> change_pos, 1339 const CCoinControl& coin_control, 1340 bool sign) 1341 { 1342 if (vecSend.empty()) { 1343 return util::Error{_("Transaction must have at least one recipient")}; 1344 } 1345 1346 if (std::any_of(vecSend.cbegin(), vecSend.cend(), [](const auto& recipient){ return recipient.nAmount < 0; })) { 1347 return util::Error{_("Transaction amounts must not be negative")}; 1348 } 1349 1350 LOCK(wallet.cs_wallet); 1351 1352 auto res = CreateTransactionInternal(wallet, vecSend, change_pos, coin_control, sign); 1353 TRACE4(coin_selection, normal_create_tx_internal, 1354 wallet.GetName().c_str(), 1355 bool(res), 1356 res ? res->fee : 0, 1357 res && res->change_pos.has_value() ? int32_t(*res->change_pos) : -1); 1358 if (!res) return res; 1359 const auto& txr_ungrouped = *res; 1360 // try with avoidpartialspends unless it's enabled already 1361 if (txr_ungrouped.fee > 0 /* 0 means non-functional fee rate estimation */ && wallet.m_max_aps_fee > -1 && !coin_control.m_avoid_partial_spends) { 1362 TRACE1(coin_selection, attempting_aps_create_tx, wallet.GetName().c_str()); 1363 CCoinControl tmp_cc = coin_control; 1364 tmp_cc.m_avoid_partial_spends = true; 1365 1366 // Reuse the change destination from the first creation attempt to avoid skipping BIP44 indexes 1367 if (txr_ungrouped.change_pos) { 1368 ExtractDestination(txr_ungrouped.tx->vout[*txr_ungrouped.change_pos].scriptPubKey, tmp_cc.destChange); 1369 } 1370 1371 auto txr_grouped = CreateTransactionInternal(wallet, vecSend, change_pos, tmp_cc, sign); 1372 // if fee of this alternative one is within the range of the max fee, we use this one 1373 const bool use_aps{txr_grouped.has_value() ? (txr_grouped->fee <= txr_ungrouped.fee + wallet.m_max_aps_fee) : false}; 1374 TRACE5(coin_selection, aps_create_tx_internal, 1375 wallet.GetName().c_str(), 1376 use_aps, 1377 txr_grouped.has_value(), 1378 txr_grouped.has_value() ? txr_grouped->fee : 0, 1379 txr_grouped.has_value() && txr_grouped->change_pos.has_value() ? int32_t(*txr_grouped->change_pos) : -1); 1380 if (txr_grouped) { 1381 wallet.WalletLogPrintf("Fee non-grouped = %lld, grouped = %lld, using %s\n", 1382 txr_ungrouped.fee, txr_grouped->fee, use_aps ? "grouped" : "non-grouped"); 1383 if (use_aps) return txr_grouped; 1384 } 1385 } 1386 return res; 1387 } 1388 1389 util::Result<CreatedTransactionResult> FundTransaction(CWallet& wallet, const CMutableTransaction& tx, const std::vector<CRecipient>& vecSend, std::optional<unsigned int> change_pos, bool lockUnspents, CCoinControl coinControl) 1390 { 1391 // We want to make sure tx.vout is not used now that we are passing outputs as a vector of recipients. 1392 // This sets us up to remove tx completely in a future PR in favor of passing the inputs directly. 1393 assert(tx.vout.empty()); 1394 1395 // Set the user desired locktime 1396 coinControl.m_locktime = tx.nLockTime; 1397 1398 // Set the user desired version 1399 coinControl.m_version = tx.nVersion; 1400 1401 // Acquire the locks to prevent races to the new locked unspents between the 1402 // CreateTransaction call and LockCoin calls (when lockUnspents is true). 1403 LOCK(wallet.cs_wallet); 1404 1405 // Fetch specified UTXOs from the UTXO set to get the scriptPubKeys and values of the outputs being selected 1406 // and to match with the given solving_data. Only used for non-wallet outputs. 1407 std::map<COutPoint, Coin> coins; 1408 for (const CTxIn& txin : tx.vin) { 1409 coins[txin.prevout]; // Create empty map entry keyed by prevout. 1410 } 1411 wallet.chain().findCoins(coins); 1412 1413 for (const CTxIn& txin : tx.vin) { 1414 const auto& outPoint = txin.prevout; 1415 PreselectedInput& preset_txin = coinControl.Select(outPoint); 1416 if (!wallet.IsMine(outPoint)) { 1417 if (coins[outPoint].out.IsNull()) { 1418 return util::Error{_("Unable to find UTXO for external input")}; 1419 } 1420 1421 // The input was not in the wallet, but is in the UTXO set, so select as external 1422 preset_txin.SetTxOut(coins[outPoint].out); 1423 } 1424 preset_txin.SetSequence(txin.nSequence); 1425 preset_txin.SetScriptSig(txin.scriptSig); 1426 preset_txin.SetScriptWitness(txin.scriptWitness); 1427 } 1428 1429 auto res = CreateTransaction(wallet, vecSend, change_pos, coinControl, false); 1430 if (!res) { 1431 return res; 1432 } 1433 1434 if (lockUnspents) { 1435 for (const CTxIn& txin : res->tx->vin) { 1436 wallet.LockCoin(txin.prevout); 1437 } 1438 } 1439 1440 return res; 1441 } 1442 } // namespace wallet