1 // Copyright (c) 2021 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 <consensus/validation.h>
6 #include <interfaces/chain.h>
7 #include <policy/policy.h>
8 #include <util/check.h>
9 #include <util/fees.h>
10 #include <util/moneystr.h>
11 #include <util/rbf.h>
12 #include <util/translation.h>
13 #include <wallet/coincontrol.h>
14 #include <wallet/fees.h>
15 #include <wallet/receive.h>
16 #include <wallet/spend.h>
17 #include <wallet/transaction.h>
18 #include <wallet/wallet.h>
19
20 using interfaces::FoundBlock;
21
22 static constexpr size_t OUTPUT_GROUP_MAX_ENTRIES{100};
23
ToString() const24 std::string COutput::ToString() const
25 {
26 return strprintf("COutput(%s, %d, %d) [%s]", tx->GetHash().ToString(), i, nDepth, FormatMoney(tx->tx->vout[i].nValue));
27 }
28
CalculateMaximumSignedInputSize(const CTxOut & txout,const CWallet * wallet,bool use_max_sig)29 int CalculateMaximumSignedInputSize(const CTxOut& txout, const CWallet* wallet, bool use_max_sig)
30 {
31 CMutableTransaction txn;
32 txn.vin.push_back(CTxIn(COutPoint()));
33 if (!wallet->DummySignInput(txn.vin[0], txout, use_max_sig)) {
34 return -1;
35 }
36 return GetVirtualTransactionInputSize(txn.vin[0]);
37 }
38
39 // txouts needs to be in the order of tx.vin
CalculateMaximumSignedTxSize(const CTransaction & tx,const CWallet * wallet,const std::vector<CTxOut> & txouts,bool use_max_sig)40 TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, const std::vector<CTxOut>& txouts, bool use_max_sig)
41 {
42 CMutableTransaction txNew(tx);
43 if (!wallet->DummySignTx(txNew, txouts, use_max_sig)) {
44 return TxSize{-1, -1};
45 }
46 CTransaction ctx(txNew);
47 int64_t vsize = GetVirtualTransactionSize(ctx);
48 int64_t weight = GetTransactionWeight(ctx);
49 return TxSize{vsize, weight};
50 }
51
CalculateMaximumSignedTxSize(const CTransaction & tx,const CWallet * wallet,bool use_max_sig)52 TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, bool use_max_sig)
53 {
54 std::vector<CTxOut> txouts;
55 for (const CTxIn& input : tx.vin) {
56 const auto mi = wallet->mapWallet.find(input.prevout.hash);
57 // Can not estimate size without knowing the input details
58 if (mi == wallet->mapWallet.end()) {
59 return TxSize{-1, -1};
60 }
61 assert(input.prevout.n < mi->second.tx->vout.size());
62 txouts.emplace_back(mi->second.tx->vout[input.prevout.n]);
63 }
64 return CalculateMaximumSignedTxSize(tx, wallet, txouts, use_max_sig);
65 }
66
AvailableCoins(std::vector<COutput> & vCoins,const CCoinControl * coinControl,const CAmount & nMinimumAmount,const CAmount & nMaximumAmount,const CAmount & nMinimumSumAmount,const uint64_t nMaximumCount) const67 void CWallet::AvailableCoins(std::vector<COutput>& vCoins, const CCoinControl* coinControl, const CAmount& nMinimumAmount, const CAmount& nMaximumAmount, const CAmount& nMinimumSumAmount, const uint64_t nMaximumCount) const
68 {
69 AssertLockHeld(cs_wallet);
70
71 vCoins.clear();
72 CAmount nTotal = 0;
73 // 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
74 // a coin control object is provided, and has the avoid address reuse flag set to false, do we allow already used addresses
75 bool allow_used_addresses = !IsWalletFlagSet(WALLET_FLAG_AVOID_REUSE) || (coinControl && !coinControl->m_avoid_address_reuse);
76 const int min_depth = {coinControl ? coinControl->m_min_depth : DEFAULT_MIN_DEPTH};
77 const int max_depth = {coinControl ? coinControl->m_max_depth : DEFAULT_MAX_DEPTH};
78 const bool only_safe = {coinControl ? !coinControl->m_include_unsafe_inputs : true};
79
80 std::set<uint256> trusted_parents;
81 for (const auto& entry : mapWallet)
82 {
83 const uint256& wtxid = entry.first;
84 const CWalletTx& wtx = entry.second;
85
86 if (!chain().checkFinalTx(*wtx.tx)) {
87 continue;
88 }
89
90 if (wtx.IsImmatureCoinBase())
91 continue;
92
93 int nDepth = wtx.GetDepthInMainChain();
94 if (nDepth < 0)
95 continue;
96
97 // We should not consider coins which aren't at least in our mempool
98 // It's possible for these to be conflicted via ancestors which we may never be able to detect
99 if (nDepth == 0 && !wtx.InMempool())
100 continue;
101
102 bool safeTx = IsTrusted(wtx, trusted_parents);
103
104 // We should not consider coins from transactions that are replacing
105 // other transactions.
106 //
107 // Example: There is a transaction A which is replaced by bumpfee
108 // transaction B. In this case, we want to prevent creation of
109 // a transaction B' which spends an output of B.
110 //
111 // Reason: If transaction A were initially confirmed, transactions B
112 // and B' would no longer be valid, so the user would have to create
113 // a new transaction C to replace B'. However, in the case of a
114 // one-block reorg, transactions B' and C might BOTH be accepted,
115 // when the user only wanted one of them. Specifically, there could
116 // be a 1-block reorg away from the chain where transactions A and C
117 // were accepted to another chain where B, B', and C were all
118 // accepted.
119 if (nDepth == 0 && wtx.mapValue.count("replaces_txid")) {
120 safeTx = false;
121 }
122
123 // Similarly, we should not consider coins from transactions that
124 // have been replaced. In the example above, we would want to prevent
125 // creation of a transaction A' spending an output of A, because if
126 // transaction B were initially confirmed, conflicting with A and
127 // A', we wouldn't want to the user to create a transaction D
128 // intending to replace A', but potentially resulting in a scenario
129 // where A, A', and D could all be accepted (instead of just B and
130 // D, or just A and A' like the user would want).
131 if (nDepth == 0 && wtx.mapValue.count("replaced_by_txid")) {
132 safeTx = false;
133 }
134
135 if (only_safe && !safeTx) {
136 continue;
137 }
138
139 if (nDepth < min_depth || nDepth > max_depth) {
140 continue;
141 }
142
143 for (unsigned int i = 0; i < wtx.tx->vout.size(); i++) {
144 // Only consider selected coins if add_inputs is false
145 if (coinControl && !coinControl->m_add_inputs && !coinControl->IsSelected(COutPoint(entry.first, i))) {
146 continue;
147 }
148
149 if (wtx.tx->vout[i].nValue < nMinimumAmount || wtx.tx->vout[i].nValue > nMaximumAmount)
150 continue;
151
152 if (coinControl && coinControl->HasSelected() && !coinControl->fAllowOtherInputs && !coinControl->IsSelected(COutPoint(entry.first, i)))
153 continue;
154
155 if (IsLockedCoin(entry.first, i))
156 continue;
157
158 if (IsSpent(wtxid, i))
159 continue;
160
161 isminetype mine = IsMine(wtx.tx->vout[i]);
162
163 if (mine == ISMINE_NO) {
164 continue;
165 }
166
167 if (!allow_used_addresses && IsSpentKey(wtxid, i)) {
168 continue;
169 }
170
171 std::unique_ptr<SigningProvider> provider = GetSolvingProvider(wtx.tx->vout[i].scriptPubKey);
172
173 bool solvable = provider ? IsSolvable(*provider, wtx.tx->vout[i].scriptPubKey) : false;
174 bool spendable = ((mine & ISMINE_SPENDABLE) != ISMINE_NO) || (((mine & ISMINE_WATCH_ONLY) != ISMINE_NO) && (coinControl && coinControl->fAllowWatchOnly && solvable));
175
176 vCoins.push_back(COutput(&wtx, i, nDepth, spendable, solvable, safeTx, (coinControl && coinControl->fAllowWatchOnly)));
177
178 // Checks the sum amount of all UTXO's.
179 if (nMinimumSumAmount != MAX_MONEY) {
180 nTotal += wtx.tx->vout[i].nValue;
181
182 if (nTotal >= nMinimumSumAmount) {
183 return;
184 }
185 }
186
187 // Checks the maximum number of UTXO's.
188 if (nMaximumCount > 0 && vCoins.size() >= nMaximumCount) {
189 return;
190 }
191 }
192 }
193 }
194
GetAvailableBalance(const CCoinControl * coinControl) const195 CAmount CWallet::GetAvailableBalance(const CCoinControl* coinControl) const
196 {
197 LOCK(cs_wallet);
198
199 CAmount balance = 0;
200 std::vector<COutput> vCoins;
201 AvailableCoins(vCoins, coinControl);
202 for (const COutput& out : vCoins) {
203 if (out.fSpendable) {
204 balance += out.tx->tx->vout[out.i].nValue;
205 }
206 }
207 return balance;
208 }
209
FindNonChangeParentOutput(const CTransaction & tx,int output) const210 const CTxOut& CWallet::FindNonChangeParentOutput(const CTransaction& tx, int output) const
211 {
212 AssertLockHeld(cs_wallet);
213 const CTransaction* ptx = &tx;
214 int n = output;
215 while (IsChange(ptx->vout[n]) && ptx->vin.size() > 0) {
216 const COutPoint& prevout = ptx->vin[0].prevout;
217 auto it = mapWallet.find(prevout.hash);
218 if (it == mapWallet.end() || it->second.tx->vout.size() <= prevout.n ||
219 !IsMine(it->second.tx->vout[prevout.n])) {
220 break;
221 }
222 ptx = it->second.tx.get();
223 n = prevout.n;
224 }
225 return ptx->vout[n];
226 }
227
ListCoins() const228 std::map<CTxDestination, std::vector<COutput>> CWallet::ListCoins() const
229 {
230 AssertLockHeld(cs_wallet);
231
232 std::map<CTxDestination, std::vector<COutput>> result;
233 std::vector<COutput> availableCoins;
234
235 AvailableCoins(availableCoins);
236
237 for (const COutput& coin : availableCoins) {
238 CTxDestination address;
239 if ((coin.fSpendable || (IsWalletFlagSet(WALLET_FLAG_DISABLE_PRIVATE_KEYS) && coin.fSolvable)) &&
240 ExtractDestination(FindNonChangeParentOutput(*coin.tx->tx, coin.i).scriptPubKey, address)) {
241 result[address].emplace_back(std::move(coin));
242 }
243 }
244
245 std::vector<COutPoint> lockedCoins;
246 ListLockedCoins(lockedCoins);
247 // Include watch-only for LegacyScriptPubKeyMan wallets without private keys
248 const bool include_watch_only = GetLegacyScriptPubKeyMan() && IsWalletFlagSet(WALLET_FLAG_DISABLE_PRIVATE_KEYS);
249 const isminetype is_mine_filter = include_watch_only ? ISMINE_WATCH_ONLY : ISMINE_SPENDABLE;
250 for (const COutPoint& output : lockedCoins) {
251 auto it = mapWallet.find(output.hash);
252 if (it != mapWallet.end()) {
253 int depth = it->second.GetDepthInMainChain();
254 if (depth >= 0 && output.n < it->second.tx->vout.size() &&
255 IsMine(it->second.tx->vout[output.n]) == is_mine_filter
256 ) {
257 CTxDestination address;
258 if (ExtractDestination(FindNonChangeParentOutput(*it->second.tx, output.n).scriptPubKey, address)) {
259 result[address].emplace_back(
260 &it->second, output.n, depth, true /* spendable */, true /* solvable */, false /* safe */);
261 }
262 }
263 }
264 }
265
266 return result;
267 }
268
GroupOutputs(const std::vector<COutput> & outputs,const CoinSelectionParams & coin_sel_params,const CoinEligibilityFilter & filter,bool positive_only) const269 std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outputs, const CoinSelectionParams& coin_sel_params, const CoinEligibilityFilter& filter, bool positive_only) const
270 {
271 std::vector<OutputGroup> groups_out;
272
273 if (!coin_sel_params.m_avoid_partial_spends) {
274 // Allowing partial spends means no grouping. Each COutput gets its own OutputGroup.
275 for (const COutput& output : outputs) {
276 // Skip outputs we cannot spend
277 if (!output.fSpendable) continue;
278
279 size_t ancestors, descendants;
280 chain().getTransactionAncestry(output.tx->GetHash(), ancestors, descendants);
281 CInputCoin input_coin = output.GetInputCoin();
282
283 // Make an OutputGroup containing just this output
284 OutputGroup group{coin_sel_params};
285 group.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants, positive_only);
286
287 // Check the OutputGroup's eligibility. Only add the eligible ones.
288 if (positive_only && group.GetSelectionAmount() <= 0) continue;
289 if (group.m_outputs.size() > 0 && group.EligibleForSpending(filter)) groups_out.push_back(group);
290 }
291 return groups_out;
292 }
293
294 // We want to combine COutputs that have the same scriptPubKey into single OutputGroups
295 // except when there are more than OUTPUT_GROUP_MAX_ENTRIES COutputs grouped in an OutputGroup.
296 // To do this, we maintain a map where the key is the scriptPubKey and the value is a vector of OutputGroups.
297 // For each COutput, we check if the scriptPubKey is in the map, and if it is, the COutput's CInputCoin is added
298 // to the last OutputGroup in the vector for the scriptPubKey. When the last OutputGroup has
299 // OUTPUT_GROUP_MAX_ENTRIES CInputCoins, a new OutputGroup is added to the end of the vector.
300 std::map<CScript, std::vector<OutputGroup>> spk_to_groups_map;
301 for (const auto& output : outputs) {
302 // Skip outputs we cannot spend
303 if (!output.fSpendable) continue;
304
305 size_t ancestors, descendants;
306 chain().getTransactionAncestry(output.tx->GetHash(), ancestors, descendants);
307 CInputCoin input_coin = output.GetInputCoin();
308 CScript spk = input_coin.txout.scriptPubKey;
309
310 std::vector<OutputGroup>& groups = spk_to_groups_map[spk];
311
312 if (groups.size() == 0) {
313 // No OutputGroups for this scriptPubKey yet, add one
314 groups.emplace_back(coin_sel_params);
315 }
316
317 // Get the last OutputGroup in the vector so that we can add the CInputCoin to it
318 // A pointer is used here so that group can be reassigned later if it is full.
319 OutputGroup* group = &groups.back();
320
321 // Check if this OutputGroup is full. We limit to OUTPUT_GROUP_MAX_ENTRIES when using -avoidpartialspends
322 // to avoid surprising users with very high fees.
323 if (group->m_outputs.size() >= OUTPUT_GROUP_MAX_ENTRIES) {
324 // The last output group is full, add a new group to the vector and use that group for the insertion
325 groups.emplace_back(coin_sel_params);
326 group = &groups.back();
327 }
328
329 // Add the input_coin to group
330 group->Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants, positive_only);
331 }
332
333 // Now we go through the entire map and pull out the OutputGroups
334 for (const auto& spk_and_groups_pair: spk_to_groups_map) {
335 const std::vector<OutputGroup>& groups_per_spk= spk_and_groups_pair.second;
336
337 // Go through the vector backwards. This allows for the first item we deal with being the partial group.
338 for (auto group_it = groups_per_spk.rbegin(); group_it != groups_per_spk.rend(); group_it++) {
339 const OutputGroup& group = *group_it;
340
341 // Don't include partial groups if there are full groups too and we don't want partial groups
342 if (group_it == groups_per_spk.rbegin() && groups_per_spk.size() > 1 && !filter.m_include_partial_groups) {
343 continue;
344 }
345
346 // Check the OutputGroup's eligibility. Only add the eligible ones.
347 if (positive_only && group.GetSelectionAmount() <= 0) continue;
348 if (group.m_outputs.size() > 0 && group.EligibleForSpending(filter)) groups_out.push_back(group);
349 }
350 }
351
352 return groups_out;
353 }
354
AttemptSelection(const CAmount & nTargetValue,const CoinEligibilityFilter & eligibility_filter,std::vector<COutput> coins,std::set<CInputCoin> & setCoinsRet,CAmount & nValueRet,const CoinSelectionParams & coin_selection_params) const355 bool CWallet::AttemptSelection(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
356 std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params) const
357 {
358 setCoinsRet.clear();
359 nValueRet = 0;
360
361 // Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output.
362 std::vector<OutputGroup> positive_groups = GroupOutputs(coins, coin_selection_params, eligibility_filter, true /* positive_only */);
363 if (SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, setCoinsRet, nValueRet)) {
364 return true;
365 }
366 // 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.
367 std::vector<OutputGroup> all_groups = GroupOutputs(coins, coin_selection_params, eligibility_filter, false /* positive_only */);
368 // While nTargetValue includes the transaction fees for non-input things, it does not include the fee for creating a change output.
369 // So we need to include that for KnapsackSolver as well, as we are expecting to create a change output.
370 return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, setCoinsRet, nValueRet);
371 }
372
SelectCoins(const std::vector<COutput> & vAvailableCoins,const CAmount & nTargetValue,std::set<CInputCoin> & setCoinsRet,CAmount & nValueRet,const CCoinControl & coin_control,CoinSelectionParams & coin_selection_params) const373 bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params) const
374 {
375 std::vector<COutput> vCoins(vAvailableCoins);
376 CAmount value_to_select = nTargetValue;
377
378 // coin control -> return all selected outputs (we want all selected to go into the transaction for sure)
379 if (coin_control.HasSelected() && !coin_control.fAllowOtherInputs)
380 {
381 for (const COutput& out : vCoins)
382 {
383 if (!out.fSpendable)
384 continue;
385 nValueRet += out.tx->tx->vout[out.i].nValue;
386 setCoinsRet.insert(out.GetInputCoin());
387 }
388 return (nValueRet >= nTargetValue);
389 }
390
391 // calculate value from preset inputs and store them
392 std::set<CInputCoin> setPresetCoins;
393 CAmount nValueFromPresetInputs = 0;
394
395 std::vector<COutPoint> vPresetInputs;
396 coin_control.ListSelected(vPresetInputs);
397 for (const COutPoint& outpoint : vPresetInputs)
398 {
399 std::map<uint256, CWalletTx>::const_iterator it = mapWallet.find(outpoint.hash);
400 if (it != mapWallet.end())
401 {
402 const CWalletTx& wtx = it->second;
403 // Clearly invalid input, fail
404 if (wtx.tx->vout.size() <= outpoint.n) {
405 return false;
406 }
407 // Just to calculate the marginal byte size
408 CInputCoin coin(wtx.tx, outpoint.n, wtx.GetSpendSize(outpoint.n, false));
409 nValueFromPresetInputs += coin.txout.nValue;
410 if (coin.m_input_bytes <= 0) {
411 return false; // Not solvable, can't estimate size for fee
412 }
413 coin.effective_value = coin.txout.nValue - coin_selection_params.m_effective_feerate.GetFee(coin.m_input_bytes);
414 if (coin_selection_params.m_subtract_fee_outputs) {
415 value_to_select -= coin.txout.nValue;
416 } else {
417 value_to_select -= coin.effective_value;
418 }
419 setPresetCoins.insert(coin);
420 } else {
421 return false; // TODO: Allow non-wallet inputs
422 }
423 }
424
425 // remove preset inputs from vCoins so that Coin Selection doesn't pick them.
426 for (std::vector<COutput>::iterator it = vCoins.begin(); it != vCoins.end() && coin_control.HasSelected();)
427 {
428 if (setPresetCoins.count(it->GetInputCoin()))
429 it = vCoins.erase(it);
430 else
431 ++it;
432 }
433
434 unsigned int limit_ancestor_count = 0;
435 unsigned int limit_descendant_count = 0;
436 chain().getPackageLimits(limit_ancestor_count, limit_descendant_count);
437 const size_t max_ancestors = (size_t)std::max<int64_t>(1, limit_ancestor_count);
438 const size_t max_descendants = (size_t)std::max<int64_t>(1, limit_descendant_count);
439 const bool fRejectLongChains = gArgs.GetBoolArg("-walletrejectlongchains", DEFAULT_WALLET_REJECT_LONG_CHAINS);
440
441 // form groups from remaining coins; note that preset coins will not
442 // automatically have their associated (same address) coins included
443 if (coin_control.m_avoid_partial_spends && vCoins.size() > OUTPUT_GROUP_MAX_ENTRIES) {
444 // Cases where we have 101+ outputs all pointing to the same destination may result in
445 // privacy leaks as they will potentially be deterministically sorted. We solve that by
446 // explicitly shuffling the outputs before processing
447 Shuffle(vCoins.begin(), vCoins.end(), FastRandomContext());
448 }
449
450 // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the
451 // transaction at a target feerate. If an attempt fails, more attempts may be made using a more
452 // permissive CoinEligibilityFilter.
453 const bool res = [&] {
454 // Pre-selected inputs already cover the target amount.
455 if (value_to_select <= 0) return true;
456
457 // If possible, fund the transaction with confirmed UTXOs only. Prefer at least six
458 // confirmations on outputs received from other wallets and only spend confirmed change.
459 if (AttemptSelection(value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
460 if (AttemptSelection(value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
461
462 // Fall back to using zero confirmation change (but with as few ancestors in the mempool as
463 // possible) if we cannot fund the transaction otherwise.
464 if (m_spend_zero_conf_change) {
465 if (AttemptSelection(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
466 if (AttemptSelection(value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)),
467 vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
468 return true;
469 }
470 if (AttemptSelection(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2),
471 vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
472 return true;
473 }
474 // If partial groups are allowed, relax the requirement of spending OutputGroups (groups
475 // of UTXOs sent to the same address, which are obviously controlled by a single wallet)
476 // in their entirety.
477 if (AttemptSelection(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
478 vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
479 return true;
480 }
481 // Try with unsafe inputs if they are allowed. This may spend unconfirmed outputs
482 // received from other wallets.
483 if (coin_control.m_include_unsafe_inputs
484 && AttemptSelection(value_to_select,
485 CoinEligibilityFilter(0 /* conf_mine */, 0 /* conf_theirs */, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
486 vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
487 return true;
488 }
489 // Try with unlimited ancestors/descendants. The transaction will still need to meet
490 // mempool ancestor/descendant policy to be accepted to mempool and broadcasted, but
491 // OutputGroups use heuristics that may overestimate ancestor/descendant counts.
492 if (!fRejectLongChains && AttemptSelection(value_to_select,
493 CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::max(), true /* include_partial_groups */),
494 vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
495 return true;
496 }
497 }
498 // Coin Selection failed.
499 return false;
500 }();
501
502 // AttemptSelection clears setCoinsRet, so add the preset inputs from coin_control to the coinset
503 util::insert(setCoinsRet, setPresetCoins);
504
505 // add preset inputs to the total value selected
506 nValueRet += nValueFromPresetInputs;
507
508 return res;
509 }
510
IsCurrentForAntiFeeSniping(interfaces::Chain & chain,const uint256 & block_hash)511 static bool IsCurrentForAntiFeeSniping(interfaces::Chain& chain, const uint256& block_hash)
512 {
513 if (chain.isInitialBlockDownload()) {
514 return false;
515 }
516 constexpr int64_t MAX_ANTI_FEE_SNIPING_TIP_AGE = 8 * 60 * 60; // in seconds
517 int64_t block_time;
518 CHECK_NONFATAL(chain.findBlock(block_hash, FoundBlock().time(block_time)));
519 if (block_time < (GetTime() - MAX_ANTI_FEE_SNIPING_TIP_AGE)) {
520 return false;
521 }
522 return true;
523 }
524
525 /**
526 * Return a height-based locktime for new transactions (uses the height of the
527 * current chain tip unless we are not synced with the current chain
528 */
GetLocktimeForNewTransaction(interfaces::Chain & chain,const uint256 & block_hash,int block_height)529 static uint32_t GetLocktimeForNewTransaction(interfaces::Chain& chain, const uint256& block_hash, int block_height)
530 {
531 uint32_t locktime;
532 // Discourage fee sniping.
533 //
534 // For a large miner the value of the transactions in the best block and
535 // the mempool can exceed the cost of deliberately attempting to mine two
536 // blocks to orphan the current best block. By setting nLockTime such that
537 // only the next block can include the transaction, we discourage this
538 // practice as the height restricted and limited blocksize gives miners
539 // considering fee sniping fewer options for pulling off this attack.
540 //
541 // A simple way to think about this is from the wallet's point of view we
542 // always want the blockchain to move forward. By setting nLockTime this
543 // way we're basically making the statement that we only want this
544 // transaction to appear in the next block; we don't want to potentially
545 // encourage reorgs by allowing transactions to appear at lower heights
546 // than the next block in forks of the best chain.
547 //
548 // Of course, the subsidy is high enough, and transaction volume low
549 // enough, that fee sniping isn't a problem yet, but by implementing a fix
550 // now we ensure code won't be written that makes assumptions about
551 // nLockTime that preclude a fix later.
552 if (IsCurrentForAntiFeeSniping(chain, block_hash)) {
553 locktime = block_height;
554
555 // Secondly occasionally randomly pick a nLockTime even further back, so
556 // that transactions that are delayed after signing for whatever reason,
557 // e.g. high-latency mix networks and some CoinJoin implementations, have
558 // better privacy.
559 if (GetRandInt(10) == 0)
560 locktime = std::max(0, (int)locktime - GetRandInt(100));
561 } else {
562 // If our chain is lagging behind, we can't discourage fee sniping nor help
563 // the privacy of high-latency transactions. To avoid leaking a potentially
564 // unique "nLockTime fingerprint", set nLockTime to a constant.
565 locktime = 0;
566 }
567 assert(locktime < LOCKTIME_THRESHOLD);
568 return locktime;
569 }
570
CreateTransactionInternal(const std::vector<CRecipient> & vecSend,CTransactionRef & tx,CAmount & nFeeRet,int & nChangePosInOut,bilingual_str & error,const CCoinControl & coin_control,FeeCalculation & fee_calc_out,bool sign)571 bool CWallet::CreateTransactionInternal(
572 const std::vector<CRecipient>& vecSend,
573 CTransactionRef& tx,
574 CAmount& nFeeRet,
575 int& nChangePosInOut,
576 bilingual_str& error,
577 const CCoinControl& coin_control,
578 FeeCalculation& fee_calc_out,
579 bool sign)
580 {
581 AssertLockHeld(cs_wallet);
582
583 CMutableTransaction txNew; // The resulting transaction that we make
584 txNew.nLockTime = GetLocktimeForNewTransaction(chain(), GetLastBlockHash(), GetLastBlockHeight());
585
586 CoinSelectionParams coin_selection_params; // Parameters for coin selection, init with dummy
587 coin_selection_params.m_avoid_partial_spends = coin_control.m_avoid_partial_spends;
588
589 CAmount recipients_sum = 0;
590 const OutputType change_type = TransactionChangeType(coin_control.m_change_type ? *coin_control.m_change_type : m_default_change_type, vecSend);
591 ReserveDestination reservedest(this, change_type);
592 unsigned int outputs_to_subtract_fee_from = 0; // The number of outputs which we are subtracting the fee from
593 for (const auto& recipient : vecSend) {
594 recipients_sum += recipient.nAmount;
595
596 if (recipient.fSubtractFeeFromAmount) {
597 outputs_to_subtract_fee_from++;
598 coin_selection_params.m_subtract_fee_outputs = true;
599 }
600 }
601
602 // Create change script that will be used if we need change
603 // TODO: pass in scriptChange instead of reservedest so
604 // change transaction isn't always pay-to-bitcoin-address
605 CScript scriptChange;
606
607 // coin control: send change to custom address
608 if (!std::get_if<CNoDestination>(&coin_control.destChange)) {
609 scriptChange = GetScriptForDestination(coin_control.destChange);
610 } else { // no coin control: send change to newly generated address
611 // Note: We use a new key here to keep it from being obvious which side is the change.
612 // The drawback is that by not reusing a previous key, the change may be lost if a
613 // backup is restored, if the backup doesn't have the new private key for the change.
614 // If we reused the old key, it would be possible to add code to look for and
615 // rediscover unknown transactions that were written with keys of ours to recover
616 // post-backup change.
617
618 // Reserve a new key pair from key pool. If it fails, provide a dummy
619 // destination in case we don't need change.
620 CTxDestination dest;
621 std::string dest_err;
622 if (!reservedest.GetReservedDestination(dest, true, dest_err)) {
623 error = strprintf(_("Transaction needs a change address, but we can't generate it. %s"), dest_err);
624 }
625 scriptChange = GetScriptForDestination(dest);
626 // A valid destination implies a change script (and
627 // vice-versa). An empty change script will abort later, if the
628 // change keypool ran out, but change is required.
629 CHECK_NONFATAL(IsValidDestination(dest) != scriptChange.empty());
630 }
631 CTxOut change_prototype_txout(0, scriptChange);
632 coin_selection_params.change_output_size = GetSerializeSize(change_prototype_txout);
633
634 // Get size of spending the change output
635 int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this);
636 // If the wallet doesn't know how to sign change output, assume p2sh-p2wpkh
637 // as lower-bound to allow BnB to do it's thing
638 if (change_spend_size == -1) {
639 coin_selection_params.change_spend_size = DUMMY_NESTED_P2WPKH_INPUT_SIZE;
640 } else {
641 coin_selection_params.change_spend_size = (size_t)change_spend_size;
642 }
643
644 // Set discard feerate
645 coin_selection_params.m_discard_feerate = GetDiscardRate(*this);
646
647 // Get the fee rate to use effective values in coin selection
648 FeeCalculation feeCalc;
649 coin_selection_params.m_effective_feerate = GetMinimumFeeRate(*this, coin_control, &feeCalc);
650 // Do not, ever, assume that it's fine to change the fee rate if the user has explicitly
651 // provided one
652 if (coin_control.m_feerate && coin_selection_params.m_effective_feerate > *coin_control.m_feerate) {
653 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));
654 return false;
655 }
656 if (feeCalc.reason == FeeReason::FALLBACK && !m_allow_fallback_fee) {
657 // eventually allow a fallback fee
658 error = _("Fee estimation failed. Fallbackfee is disabled. Wait a few blocks or enable -fallbackfee.");
659 return false;
660 }
661
662 // Get long term estimate
663 CCoinControl cc_temp;
664 cc_temp.m_confirm_target = chain().estimateMaxBlocks();
665 coin_selection_params.m_long_term_feerate = GetMinimumFeeRate(*this, cc_temp, nullptr);
666
667 // Calculate the cost of change
668 // Cost of change is the cost of creating the change output + cost of spending the change output in the future.
669 // For creating the change output now, we use the effective feerate.
670 // For spending the change output in the future, we use the discard feerate for now.
671 // So cost of change = (change output size * effective feerate) + (size of spending change output * discard feerate)
672 coin_selection_params.m_change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);
673 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;
674
675 // vouts to the payees
676 if (!coin_selection_params.m_subtract_fee_outputs) {
677 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)
678 }
679 for (const auto& recipient : vecSend)
680 {
681 CTxOut txout(recipient.nAmount, recipient.scriptPubKey);
682
683 // Include the fee cost for outputs.
684 if (!coin_selection_params.m_subtract_fee_outputs) {
685 coin_selection_params.tx_noinputs_size += ::GetSerializeSize(txout, PROTOCOL_VERSION);
686 }
687
688 if (IsDust(txout, chain().relayDustFee()))
689 {
690 error = _("Transaction amount too small");
691 return false;
692 }
693 txNew.vout.push_back(txout);
694 }
695
696 // Include the fees for things that aren't inputs, excluding the change output
697 const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);
698 CAmount selection_target = recipients_sum + not_input_fees;
699
700 // Get available coins
701 std::vector<COutput> vAvailableCoins;
702 AvailableCoins(vAvailableCoins, &coin_control, 1, MAX_MONEY, MAX_MONEY, 0);
703
704 // Choose coins to use
705 CAmount inputs_sum = 0;
706 std::set<CInputCoin> setCoins;
707 if (!SelectCoins(vAvailableCoins, /* nTargetValue */ selection_target, setCoins, inputs_sum, coin_control, coin_selection_params))
708 {
709 error = _("Insufficient funds");
710 return false;
711 }
712
713 // Always make a change output
714 // We will reduce the fee from this change output later, and remove the output if it is too small.
715 const CAmount change_and_fee = inputs_sum - recipients_sum;
716 assert(change_and_fee >= 0);
717 CTxOut newTxOut(change_and_fee, scriptChange);
718
719 if (nChangePosInOut == -1)
720 {
721 // Insert change txn at random position:
722 nChangePosInOut = GetRandInt(txNew.vout.size()+1);
723 }
724 else if ((unsigned int)nChangePosInOut > txNew.vout.size())
725 {
726 error = _("Change index out of range");
727 return false;
728 }
729
730 assert(nChangePosInOut != -1);
731 auto change_position = txNew.vout.insert(txNew.vout.begin() + nChangePosInOut, newTxOut);
732
733 // Shuffle selected coins and fill in final vin
734 std::vector<CInputCoin> selected_coins(setCoins.begin(), setCoins.end());
735 Shuffle(selected_coins.begin(), selected_coins.end(), FastRandomContext());
736
737 // Note how the sequence number is set to non-maxint so that
738 // the nLockTime set above actually works.
739 //
740 // BIP125 defines opt-in RBF as any nSequence < maxint-1, so
741 // we use the highest possible value in that range (maxint-2)
742 // to avoid conflicting with other possible uses of nSequence,
743 // and in the spirit of "smallest possible change from prior
744 // behavior."
745 const uint32_t nSequence = coin_control.m_signal_bip125_rbf.value_or(m_signal_rbf) ? MAX_BIP125_RBF_SEQUENCE : (CTxIn::SEQUENCE_FINAL - 1);
746 for (const auto& coin : selected_coins) {
747 txNew.vin.push_back(CTxIn(coin.outpoint, CScript(), nSequence));
748 }
749
750 // Calculate the transaction fee
751 TxSize tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly);
752 int nBytes = tx_sizes.vsize;
753 if (nBytes < 0) {
754 error = _("Signing transaction failed");
755 return false;
756 }
757 nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes);
758
759 // Subtract fee from the change output if not subtracting it from recipient outputs
760 CAmount fee_needed = nFeeRet;
761 if (!coin_selection_params.m_subtract_fee_outputs) {
762 change_position->nValue -= fee_needed;
763 }
764
765 // We want to drop the change to fees if:
766 // 1. The change output would be dust
767 // 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)
768 CAmount change_amount = change_position->nValue;
769 if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_amount <= coin_selection_params.m_cost_of_change)
770 {
771 nChangePosInOut = -1;
772 change_amount = 0;
773 txNew.vout.erase(change_position);
774
775 // Because we have dropped this change, the tx size and required fee will be different, so let's recalculate those
776 tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly);
777 nBytes = tx_sizes.vsize;
778 fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes);
779 }
780
781 // The only time that fee_needed should be less than the amount available for fees (in change_and_fee - change_amount) is when
782 // we are subtracting the fee from the outputs. If this occurs at any other time, it is a bug.
783 assert(coin_selection_params.m_subtract_fee_outputs || fee_needed <= change_and_fee - change_amount);
784
785 // Update nFeeRet in case fee_needed changed due to dropping the change output
786 if (fee_needed <= change_and_fee - change_amount) {
787 nFeeRet = change_and_fee - change_amount;
788 }
789
790 // Reduce output values for subtractFeeFromAmount
791 if (coin_selection_params.m_subtract_fee_outputs) {
792 CAmount to_reduce = fee_needed + change_amount - change_and_fee;
793 int i = 0;
794 bool fFirst = true;
795 for (const auto& recipient : vecSend)
796 {
797 if (i == nChangePosInOut) {
798 ++i;
799 }
800 CTxOut& txout = txNew.vout[i];
801
802 if (recipient.fSubtractFeeFromAmount)
803 {
804 txout.nValue -= to_reduce / outputs_to_subtract_fee_from; // Subtract fee equally from each selected recipient
805
806 if (fFirst) // first receiver pays the remainder not divisible by output count
807 {
808 fFirst = false;
809 txout.nValue -= to_reduce % outputs_to_subtract_fee_from;
810 }
811
812 // Error if this output is reduced to be below dust
813 if (IsDust(txout, chain().relayDustFee())) {
814 if (txout.nValue < 0) {
815 error = _("The transaction amount is too small to pay the fee");
816 } else {
817 error = _("The transaction amount is too small to send after the fee has been deducted");
818 }
819 return false;
820 }
821 }
822 ++i;
823 }
824 nFeeRet = fee_needed;
825 }
826
827 // Give up if change keypool ran out and change is required
828 if (scriptChange.empty() && nChangePosInOut != -1) {
829 return false;
830 }
831
832 if (sign && !SignTransaction(txNew)) {
833 error = _("Signing transaction failed");
834 return false;
835 }
836
837 // Return the constructed transaction data.
838 tx = MakeTransactionRef(std::move(txNew));
839
840 // Limit size
841 if ((sign && GetTransactionWeight(*tx) > MAX_STANDARD_TX_WEIGHT) ||
842 (!sign && tx_sizes.weight > MAX_STANDARD_TX_WEIGHT))
843 {
844 error = _("Transaction too large");
845 return false;
846 }
847
848 if (nFeeRet > m_default_max_tx_fee) {
849 error = TransactionErrorString(TransactionError::MAX_FEE_EXCEEDED);
850 return false;
851 }
852
853 if (gArgs.GetBoolArg("-walletrejectlongchains", DEFAULT_WALLET_REJECT_LONG_CHAINS)) {
854 // Lastly, ensure this tx will pass the mempool's chain limits
855 if (!chain().checkChainLimits(tx)) {
856 error = _("Transaction has too long of a mempool chain");
857 return false;
858 }
859 }
860
861 // Before we return success, we assume any change key will be used to prevent
862 // accidental re-use.
863 reservedest.KeepDestination();
864 fee_calc_out = feeCalc;
865
866 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",
867 nFeeRet, nBytes, feeCalc.returnedTarget, feeCalc.desiredTarget, StringForFeeReason(feeCalc.reason), feeCalc.est.decay,
868 feeCalc.est.pass.start, feeCalc.est.pass.end,
869 (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,
870 feeCalc.est.pass.withinTarget, feeCalc.est.pass.totalConfirmed, feeCalc.est.pass.inMempool, feeCalc.est.pass.leftMempool,
871 feeCalc.est.fail.start, feeCalc.est.fail.end,
872 (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,
873 feeCalc.est.fail.withinTarget, feeCalc.est.fail.totalConfirmed, feeCalc.est.fail.inMempool, feeCalc.est.fail.leftMempool);
874 return true;
875 }
876
CreateTransaction(const std::vector<CRecipient> & vecSend,CTransactionRef & tx,CAmount & nFeeRet,int & nChangePosInOut,bilingual_str & error,const CCoinControl & coin_control,FeeCalculation & fee_calc_out,bool sign)877 bool CWallet::CreateTransaction(
878 const std::vector<CRecipient>& vecSend,
879 CTransactionRef& tx,
880 CAmount& nFeeRet,
881 int& nChangePosInOut,
882 bilingual_str& error,
883 const CCoinControl& coin_control,
884 FeeCalculation& fee_calc_out,
885 bool sign)
886 {
887 if (vecSend.empty()) {
888 error = _("Transaction must have at least one recipient");
889 return false;
890 }
891
892 if (std::any_of(vecSend.cbegin(), vecSend.cend(), [](const auto& recipient){ return recipient.nAmount < 0; })) {
893 error = _("Transaction amounts must not be negative");
894 return false;
895 }
896
897 LOCK(cs_wallet);
898
899 int nChangePosIn = nChangePosInOut;
900 Assert(!tx); // tx is an out-param. TODO change the return type from bool to tx (or nullptr)
901 bool res = CreateTransactionInternal(vecSend, tx, nFeeRet, nChangePosInOut, error, coin_control, fee_calc_out, sign);
902 // try with avoidpartialspends unless it's enabled already
903 if (res && nFeeRet > 0 /* 0 means non-functional fee rate estimation */ && m_max_aps_fee > -1 && !coin_control.m_avoid_partial_spends) {
904 CCoinControl tmp_cc = coin_control;
905 tmp_cc.m_avoid_partial_spends = true;
906 CAmount nFeeRet2;
907 CTransactionRef tx2;
908 int nChangePosInOut2 = nChangePosIn;
909 bilingual_str error2; // fired and forgotten; if an error occurs, we discard the results
910 if (CreateTransactionInternal(vecSend, tx2, nFeeRet2, nChangePosInOut2, error2, tmp_cc, fee_calc_out, sign)) {
911 // if fee of this alternative one is within the range of the max fee, we use this one
912 const bool use_aps = nFeeRet2 <= nFeeRet + m_max_aps_fee;
913 WalletLogPrintf("Fee non-grouped = %lld, grouped = %lld, using %s\n", nFeeRet, nFeeRet2, use_aps ? "grouped" : "non-grouped");
914 if (use_aps) {
915 tx = tx2;
916 nFeeRet = nFeeRet2;
917 nChangePosInOut = nChangePosInOut2;
918 }
919 }
920 }
921 return res;
922 }
923
FundTransaction(CMutableTransaction & tx,CAmount & nFeeRet,int & nChangePosInOut,bilingual_str & error,bool lockUnspents,const std::set<int> & setSubtractFeeFromOutputs,CCoinControl coinControl)924 bool CWallet::FundTransaction(CMutableTransaction& tx, CAmount& nFeeRet, int& nChangePosInOut, bilingual_str& error, bool lockUnspents, const std::set<int>& setSubtractFeeFromOutputs, CCoinControl coinControl)
925 {
926 std::vector<CRecipient> vecSend;
927
928 // Turn the txout set into a CRecipient vector.
929 for (size_t idx = 0; idx < tx.vout.size(); idx++) {
930 const CTxOut& txOut = tx.vout[idx];
931 CRecipient recipient = {txOut.scriptPubKey, txOut.nValue, setSubtractFeeFromOutputs.count(idx) == 1};
932 vecSend.push_back(recipient);
933 }
934
935 coinControl.fAllowOtherInputs = true;
936
937 for (const CTxIn& txin : tx.vin) {
938 coinControl.Select(txin.prevout);
939 }
940
941 // Acquire the locks to prevent races to the new locked unspents between the
942 // CreateTransaction call and LockCoin calls (when lockUnspents is true).
943 LOCK(cs_wallet);
944
945 CTransactionRef tx_new;
946 FeeCalculation fee_calc_out;
947 if (!CreateTransaction(vecSend, tx_new, nFeeRet, nChangePosInOut, error, coinControl, fee_calc_out, false)) {
948 return false;
949 }
950
951 if (nChangePosInOut != -1) {
952 tx.vout.insert(tx.vout.begin() + nChangePosInOut, tx_new->vout[nChangePosInOut]);
953 }
954
955 // Copy output sizes from new transaction; they may have had the fee
956 // subtracted from them.
957 for (unsigned int idx = 0; idx < tx.vout.size(); idx++) {
958 tx.vout[idx].nValue = tx_new->vout[idx].nValue;
959 }
960
961 // Add new txins while keeping original txin scriptSig/order.
962 for (const CTxIn& txin : tx_new->vin) {
963 if (!coinControl.IsSelected(txin.prevout)) {
964 tx.vin.push_back(txin);
965
966 }
967 if (lockUnspents) {
968 LockCoin(txin.prevout);
969 }
970
971 }
972
973 return true;
974 }
975