1// Copyright (c) 2021-present 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/messages.h>
8#include <common/system.h>
9#include <consensus/amount.h>
10#include <consensus/validation.h>
11#include <interfaces/chain.h>
12#include <node/types.h>
13#include <numeric>
14#include <policy/policy.h>
15#include <policy/truc_policy.h>
16#include <primitives/transaction.h>
17#include <primitives/transaction_identifier.h>
18#include <script/script.h>
19#include <script/signingprovider.h>
20#include <script/solver.h>
21#include <util/check.h>
22#include <util/moneystr.h>
23#include <util/rbf.h>
24#include <util/trace.h>
25#include <util/translation.h>
26#include <wallet/coincontrol.h>
27#include <wallet/fees.h>
28#include <wallet/receive.h>
29#include <wallet/spend.h>
30#include <wallet/transaction.h>
31#include <wallet/wallet.h>
32
33#include <cmath>
34
35using common::StringForFeeReason;
36using common::TransactionErrorString;
37using interfaces::FoundBlock;
38using node::TransactionError;
39
40TRACEPOINT_SEMAPHORE(coin_selection, selected_coins);
41TRACEPOINT_SEMAPHORE(coin_selection, normal_create_tx_internal);
42TRACEPOINT_SEMAPHORE(coin_selection, attempting_aps_create_tx);
43TRACEPOINT_SEMAPHORE(coin_selection, aps_create_tx_internal);
44
45namespace wallet {
46static constexpr size_t OUTPUT_GROUP_MAX_ENTRIES{100};
47
48/** Whether the descriptor represents, directly or not, a witness program. */
49static bool IsSegwit(const Descriptor& desc) {
50    if (const auto typ = desc.GetOutputType()) return *typ != OutputType::LEGACY;
51    return false;
52}
53
54/** Whether to assume ECDSA signatures' will be high-r. */
55static bool UseMaxSig(const std::optional<CTxIn>& txin, const CCoinControl* coin_control) {
56    // Use max sig if watch only inputs were used or if this particular input is an external input
57    // to ensure a sufficient fee is attained for the requested feerate.
58    return coin_control && txin && coin_control->IsExternalSelected(txin->prevout);
59}
60
61/** Get the size of an input (in witness units) once it's signed.
62 *
63 * @param desc The output script descriptor of the coin spent by this input.
64 * @param txin Optionally the txin to estimate the size of. Used to determine the size of ECDSA signatures.
65 * @param coin_control Information about the context to determine the size of ECDSA signatures.
66 * @param tx_is_segwit Whether the transaction has at least a single input spending a segwit coin.
67 * @param can_grind_r Whether the signer will be able to grind the R of the signature.
68 */
69static std::optional<int64_t> MaxInputWeight(const Descriptor& desc, const std::optional<CTxIn>& txin,
70                                             const CCoinControl* coin_control, const bool tx_is_segwit,
71                                             const bool can_grind_r) {
72    if (const auto sat_weight = desc.MaxSatisfactionWeight(!can_grind_r || UseMaxSig(txin, coin_control))) {
73        if (const auto elems_count = desc.MaxSatisfactionElems()) {
74            const bool is_segwit = IsSegwit(desc);
75            // Account for the size of the scriptsig and the number of elements on the witness stack. Note
76            // that if any input in the transaction is spending a witness program, we need to specify the
77            // witness stack size for every input regardless of whether it is segwit itself.
78            // NOTE: this also works in case of mixed scriptsig-and-witness such as in p2sh-wrapped segwit v0
79            // outputs. In this case the size of the scriptsig length will always be one (since the redeemScript
80            // is always a push of the witness program in this case, which is smaller than 253 bytes).
81            const int64_t scriptsig_len = is_segwit ? 1 : GetSizeOfCompactSize(*sat_weight / WITNESS_SCALE_FACTOR);
82            const int64_t witstack_len = is_segwit ? GetSizeOfCompactSize(*elems_count) : (tx_is_segwit ? 1 : 0);
83            // previous txid + previous vout + sequence + scriptsig len + witstack size + scriptsig or witness
84            // NOTE: sat_weight already accounts for the witness discount accordingly.
85            return (32 + 4 + 4 + scriptsig_len) * WITNESS_SCALE_FACTOR + witstack_len + *sat_weight;
86        }
87    }
88
89    return {};
90}
91
92int CalculateMaximumSignedInputSize(const CTxOut& txout, const COutPoint outpoint, const SigningProvider* provider, bool can_grind_r, const CCoinControl* coin_control)
93{
94    if (!provider) return -1;
95
96    if (const auto desc = InferDescriptor(txout.scriptPubKey, *provider)) {
97        if (const auto weight = MaxInputWeight(*desc, CTxIn{outpoint}, coin_control, true, can_grind_r)) {
98            return static_cast<int>(GetVirtualTransactionSize(*weight, 0, 0));
99        }
100    }
101
102    return -1;
103}
104
105int CalculateMaximumSignedInputSize(const CTxOut& txout, const CWallet* wallet, const CCoinControl* coin_control)
106{
107    const std::unique_ptr<SigningProvider> provider = wallet->GetSolvingProvider(txout.scriptPubKey);
108    return CalculateMaximumSignedInputSize(txout, COutPoint(), provider.get(), wallet->CanGrindR(), coin_control);
109}
110
111/** Infer a descriptor for the given output script. */
112static std::unique_ptr<Descriptor> GetDescriptor(const CWallet* wallet, const CCoinControl* coin_control,
113                                                 const CScript script_pubkey)
114{
115    MultiSigningProvider providers;
116    for (const auto spkman: wallet->GetScriptPubKeyMans(script_pubkey)) {
117        providers.AddProvider(spkman->GetSolvingProvider(script_pubkey));
118    }
119    if (coin_control) {
120        providers.AddProvider(std::make_unique<FlatSigningProvider>(coin_control->m_external_provider));
121    }
122    return InferDescriptor(script_pubkey, providers);
123}
124
125/** Infer the maximum size of this input after it will be signed. */
126static std::optional<int64_t> GetSignedTxinWeight(const CWallet* wallet, const CCoinControl* coin_control,
127                                                  const CTxIn& txin, const CTxOut& txo, const bool tx_is_segwit,
128                                                  const bool can_grind_r)
129{
130    // If weight was provided, use that.
131    std::optional<int64_t> weight;
132    if (coin_control && (weight = coin_control->GetInputWeight(txin.prevout))) {
133        return weight.value();
134    }
135
136    // Otherwise, use the maximum satisfaction size provided by the descriptor.
137    std::unique_ptr<Descriptor> desc{GetDescriptor(wallet, coin_control, txo.scriptPubKey)};
138    if (desc) return MaxInputWeight(*desc, {txin}, coin_control, tx_is_segwit, can_grind_r);
139
140    return {};
141}
142
143// txouts needs to be in the order of tx.vin
144TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, const std::vector<CTxOut>& txouts, const CCoinControl* coin_control)
145{
146    // version + nLockTime + input count + output count
147    int64_t weight = (4 + 4 + GetSizeOfCompactSize(tx.vin.size()) + GetSizeOfCompactSize(tx.vout.size())) * WITNESS_SCALE_FACTOR;
148    // Whether any input spends a witness program. Necessary to run before the next loop over the
149    // inputs in order to accurately compute the compactSize length for the witness data per input.
150    bool is_segwit = std::any_of(txouts.begin(), txouts.end(), [&](const CTxOut& txo) {
151        std::unique_ptr<Descriptor> desc{GetDescriptor(wallet, coin_control, txo.scriptPubKey)};
152        if (desc) return IsSegwit(*desc);
153        return false;
154    });
155    // Segwit marker and flag
156    if (is_segwit) weight += 2;
157
158    // Add the size of the transaction outputs.
159    for (const auto& txo : tx.vout) weight += GetSerializeSize(txo) * WITNESS_SCALE_FACTOR;
160
161    // Add the size of the transaction inputs as if they were signed.
162    for (uint32_t i = 0; i < txouts.size(); i++) {
163        const auto txin_weight = GetSignedTxinWeight(wallet, coin_control, tx.vin[i], txouts[i], is_segwit, wallet->CanGrindR());
164        if (!txin_weight) return TxSize{-1, -1};
165        assert(*txin_weight > -1);
166        weight += *txin_weight;
167    }
168
169    // It's ok to use 0 as the number of sigops since we never create any pathological transaction.
170    return TxSize{GetVirtualTransactionSize(weight, 0, 0), weight};
171}
172
173TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, const CCoinControl* coin_control)
174{
175    std::vector<CTxOut> txouts;
176    // Look up the inputs. The inputs are either in the wallet, or in coin_control.
177    for (const CTxIn& input : tx.vin) {
178        const auto mi = wallet->mapWallet.find(input.prevout.hash);
179        // Can not estimate size without knowing the input details
180        if (mi != wallet->mapWallet.end()) {
181            assert(input.prevout.n < mi->second.GetTx()->vout.size());
182            txouts.emplace_back(mi->second.GetTx()->vout.at(input.prevout.n));
183        } else if (coin_control) {
184            const auto& txout{coin_control->GetExternalOutput(input.prevout)};
185            if (!txout) return TxSize{-1, -1};
186            txouts.emplace_back(*txout);
187        } else {
188            return TxSize{-1, -1};
189        }
190    }
191    return CalculateMaximumSignedTxSize(tx, wallet, txouts, coin_control);
192}
193
194size_t CoinsResult::Size() const
195{
196    size_t size{0};
197    for (const auto& it : coins) {
198        size += it.second.size();
199    }
200    return size;
201}
202
203std::vector<COutput> CoinsResult::All() const
204{
205    std::vector<COutput> all;
206    all.reserve(Size());
207    for (const auto& it : coins) {
208        all.insert(all.end(), it.second.begin(), it.second.end());
209    }
210    return all;
211}
212
213void CoinsResult::Erase(const std::unordered_set<COutPoint, SaltedOutpointHasher>& coins_to_remove)
214{
215    for (auto& [type, vec] : coins) {
216        auto remove_it = std::remove_if(vec.begin(), vec.end(), [&](const COutput& coin) {
217            // remove it if it's on the set
218            if (!coins_to_remove.contains(coin.outpoint)) return false;
219
220            // update cached amounts
221            total_amount -= coin.txout.nValue;
222            if (coin.HasEffectiveValue() && total_effective_amount.has_value()) total_effective_amount = *total_effective_amount - coin.GetEffectiveValue();
223            return true;
224        });
225        vec.erase(remove_it, vec.end());
226    }
227}
228
229void CoinsResult::Shuffle(FastRandomContext& rng_fast)
230{
231    for (auto& it : coins) {
232        std::shuffle(it.second.begin(), it.second.end(), rng_fast);
233    }
234}
235
236void CoinsResult::Add(OutputType type, const COutput& out)
237{
238    coins[type].emplace_back(out);
239    total_amount += out.txout.nValue;
240    if (out.HasEffectiveValue()) {
241        total_effective_amount = total_effective_amount.has_value() ?
242                *total_effective_amount + out.GetEffectiveValue() : out.GetEffectiveValue();
243    }
244}
245
246static OutputType GetOutputType(TxoutType type, bool is_from_p2sh)
247{
248    switch (type) {
249        case TxoutType::WITNESS_V1_TAPROOT:
250            return OutputType::BECH32M;