wallet: use descriptor satisfaction size to estimate inputs size

Instead of using the dummysigner to compute a placeholder satisfaction,
infer a descriptor on the scriptPubKey of the coin being spent and use
the estimation of the satisfaction size given by the descriptor
directly.

Note this (almost, see next paragraph) exactly conserves the previous
behaviour. For instance CalculateMaximumSignedInputSize was previously
assuming the input to be spent in a transaction that spends at least one
Segwit coin, since it was always accounting for the serialization of the
number of witness elements.

In this commit we use a placeholder for the size of the serialization of
the witness stack size (1 byte). Since the logic in this commit is
already tricky enough to review, and that it is only a very tiny
approximation not observable through the existing tests, it is addressed
in the next commit.

6 files changed, 118 insertions, 163 deletions

diff --git a/src/consensus/validation.h b/src/consensus/validation.h
index d5bf08cd61..8fb638abcf 100644
--- a/src/consensus/validation.h
+++ b/src/consensus/validation.h
@@ -158,6 +158,10 @@ static inline int64_t GetTransactionInputWeight(const CTxIn& txin)
     // scriptWitness size is added here because witnesses and txins are split up in segwit serialization.
     return ::GetSerializeSize(txin, PROTOCOL_VERSION | SERIALIZE_TRANSACTION_NO_WITNESS) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(txin, PROTOCOL_VERSION) + ::GetSerializeSize(txin.scriptWitness.stack, PROTOCOL_VERSION);
 }
+static inline int64_t GetTransactionOutputWeight(const CTxOut& txout)
+{
+    return ::GetSerializeSize(txout, PROTOCOL_VERSION | SERIALIZE_TRANSACTION_NO_WITNESS) * (WITNESS_SCALE_FACTOR - 1) + ::GetSerializeSize(txout, PROTOCOL_VERSION);
+}
 
 /** Compute at which vout of the block's coinbase transaction the witness commitment occurs, or -1 if not found */
 inline int GetWitnessCommitmentIndex(const CBlock& block)
diff --git a/src/test/descriptor_tests.cpp b/src/test/descriptor_tests.cpp
index 62e436f34b..c2c3988f0d 100644
--- a/src/test/descriptor_tests.cpp
+++ b/src/test/descriptor_tests.cpp
@@ -152,10 +152,10 @@ void DoCheck(std::string prv, std::string pub, const std::string& norm_pub, int
 
     // We must be able to estimate the max satisfaction size for any solvable descriptor top descriptor (but combo).
     const bool is_nontop_or_nonsolvable{!parse_priv->IsSolvable() || !parse_priv->GetOutputType()};
-    for (const bool use_max_sig: {true, false}) {
-        BOOST_CHECK_MESSAGE(parse_priv->MaxSatisfactionWeight(use_max_sig) || is_nontop_or_nonsolvable, prv);
-        BOOST_CHECK_MESSAGE(parse_pub->MaxSatisfactionWeight(use_max_sig) || is_nontop_or_nonsolvable, pub);
-    }
+    const auto max_sat_maxsig{parse_priv->MaxSatisfactionWeight(true)};
+    const auto max_sat_nonmaxsig{parse_priv->MaxSatisfactionWeight(true)};
+    const bool is_input_size_info_set{max_sat_maxsig && max_sat_nonmaxsig};
+    BOOST_CHECK_MESSAGE(is_input_size_info_set || is_nontop_or_nonsolvable, prv);
 
     // The ScriptSize() must match the size of the Script string. (ScriptSize() is set for all descs but 'combo()'.)
     const bool is_combo{!parse_priv->IsSingleType()};
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index c0ee00e097..81dd033177 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -34,14 +34,60 @@ using interfaces::FoundBlock;
 namespace wallet {
 static constexpr size_t OUTPUT_GROUP_MAX_ENTRIES{100};
 
+/** Whether the descriptor represents, directly or not, a witness program. */
+static bool IsSegwit(const Descriptor& desc) {
+    if (const auto typ = desc.GetOutputType()) return *typ != OutputType::LEGACY;
+    return false;
+}
+
+/** Whether to assume ECDSA signatures' will be high-r. */
+static bool UseMaxSig(const std::optional<CTxIn>& txin, const CCoinControl* coin_control) {
+    // Use max sig if watch only inputs were used or if this particular input is an external input
+    // to ensure a sufficient fee is attained for the requested feerate.
+    return coin_control && (coin_control->fAllowWatchOnly || (txin && coin_control->IsExternalSelected(txin->prevout)));
+}
+
+/** Get the size of an input (in witness units) once it's signed.
+ *
+ * @param desc The output script descriptor of the coin spent by this input.
+ * @param txin Optionally the txin to estimate the size of. Used to determine the size of ECDSA signatures.
+ * @param coin_control Information about the context to determine the size of ECDSA signatures.
+ * @param tx_is_segwit Whether the transaction has at least a single input spending a segwit coin.
+ * @param can_grind_r Whether the signer will be able to grind the R of the signature.
+ */
+static std::optional<int64_t> MaxInputWeight(const Descriptor& desc, const std::optional<CTxIn>& txin,
+                                             const CCoinControl* coin_control, const bool tx_is_segwit,
+                                             const bool can_grind_r) {
+    if (const auto sat_weight = desc.MaxSatisfactionWeight(!can_grind_r || UseMaxSig(txin, coin_control))) {
+        const bool is_segwit = IsSegwit(desc);
+        // Account for the size of the scriptsig and the number of elements on the witness stack. Note
+        // that if any input in the transaction is spending a witness program, we need to specify the
+        // witness stack size for every input regardless of whether it is segwit itself.
+        // NOTE: this also works in case of mixed scriptsig-and-witness such as in p2sh-wrapped segwit v0
+        // outputs. In this case the size of the scriptsig length will always be one (since the redeemScript
+        // is always a push of the witness program in this case, which is smaller than 253 bytes).
+        const int64_t scriptsig_len = is_segwit ? 1 : GetSizeOfCompactSize(*sat_weight / WITNESS_SCALE_FACTOR);
+        // FIXME: use the real number of stack elements instead of the "1" placeholder.
+        const int64_t witstack_len = is_segwit ? GetSizeOfCompactSize(1) : (tx_is_segwit ? 1 : 0);
+        // previous txid + previous vout + sequence + scriptsig len + witstack size + scriptsig or witness
+        // NOTE: sat_weight already accounts for the witness discount accordingly.
+        return (32 + 4 + 4 + scriptsig_len) * WITNESS_SCALE_FACTOR + witstack_len + *sat_weight;
+    }
+
+    return {};
+}
+
 int CalculateMaximumSignedInputSize(const CTxOut& txout, const COutPoint outpoint, const SigningProvider* provider, bool can_grind_r, const CCoinControl* coin_control)
 {
-    CMutableTransaction txn;
-    txn.vin.push_back(CTxIn(outpoint));
-    if (!provider || !DummySignInput(*provider, txn.vin[0], txout, can_grind_r, coin_control)) {
-        return -1;
+    if (!provider) return -1;
+
+    if (const auto desc = InferDescriptor(txout.scriptPubKey, *provider)) {
+        if (const auto weight = MaxInputWeight(*desc, {}, coin_control, true, can_grind_r)) {
+            return static_cast<int>(GetVirtualTransactionSize(*weight, 0, 0));
+        }
     }
-    return GetVirtualTransactionInputSize(txn.vin[0]);
+
+    return -1;
 }
 
 int CalculateMaximumSignedInputSize(const CTxOut& txout, const CWallet* wallet, const CCoinControl* coin_control)
@@ -50,15 +96,65 @@ int CalculateMaximumSignedInputSize(const CTxOut& txout, const CWallet* wallet,
     return CalculateMaximumSignedInputSize(txout, COutPoint(), provider.get(), wallet->CanGrindR(), coin_control);
 }
 
+/** Infer a descriptor for the given output script. */
+static std::unique_ptr<Descriptor> GetDescriptor(const CWallet* wallet, const CCoinControl* coin_control,
+                                                 const CScript script_pubkey)
+{
+    MultiSigningProvider providers;
+    for (const auto spkman: wallet->GetScriptPubKeyMans(script_pubkey)) {
+        providers.AddProvider(spkman->GetSolvingProvider(script_pubkey));
+    }
+    if (coin_control) {
+        providers.AddProvider(std::make_unique<FlatSigningProvider>(coin_control->m_external_provider));
+    }
+    return InferDescriptor(script_pubkey, providers);
+}
+
+/** Infer the maximum size of this input after it will be signed. */
+static std::optional<int64_t> GetSignedTxinWeight(const CWallet* wallet, const CCoinControl* coin_control,
+                                                  const CTxIn& txin, const CTxOut& txo, const bool tx_is_segwit,
+                                                  const bool can_grind_r)
+{
+    // If weight was provided, use that.
+    if (coin_control && coin_control->HasInputWeight(txin.prevout)) {
+        return coin_control->GetInputWeight(txin.prevout);
+    }
+
+    // Otherwise, use the maximum satisfaction size provided by the descriptor.
+    std::unique_ptr<Descriptor> desc{GetDescriptor(wallet, coin_control, txo.scriptPubKey)};
+    if (desc) return MaxInputWeight(*desc, {txin}, coin_control, tx_is_segwit, can_grind_r);
+
+    return {};
+}
+
 // txouts needs to be in the order of tx.vin
 TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, const std::vector<CTxOut>& txouts, const CCoinControl* coin_control)
 {
-    CMutableTransaction txNew(tx);
-    if (!wallet->DummySignTx(txNew, txouts, coin_control)) return TxSize{-1, -1};
-    CTransaction ctx(txNew);
-    int64_t vsize = GetVirtualTransactionSize(ctx);
-    int64_t weight = GetTransactionWeight(ctx);
-    return TxSize{vsize, weight};
+    // nVersion + nLockTime + input count + output count
+    int64_t weight = (4 + 4 + GetSizeOfCompactSize(tx.vin.size()) + GetSizeOfCompactSize(tx.vout.size())) * WITNESS_SCALE_FACTOR;
+    // Whether any input spends a witness program. Necessary to run before the next loop over the
+    // inputs in order to accurately compute the compactSize length for the witness data per input.
+    bool is_segwit = std::any_of(txouts.begin(), txouts.end(), [&](const CTxOut& txo) {
+        std::unique_ptr<Descriptor> desc{GetDescriptor(wallet, coin_control, txo.scriptPubKey)};
+        if (desc) return IsSegwit(*desc);
+        return false;
+    });
+    // Segwit marker and flag
+    if (is_segwit) weight += 2;
+
+    // Add the size of the transaction outputs.
+    for (const auto& txo : tx.vout) weight += GetTransactionOutputWeight(txo);
+
+    // Add the size of the transaction inputs as if they were signed.
+    for (uint32_t i = 0; i < txouts.size(); i++) {
+        const auto txin_weight = GetSignedTxinWeight(wallet, coin_control, tx.vin[i], txouts[i], is_segwit, wallet->CanGrindR());
+        if (!txin_weight) return TxSize{-1, -1};
+        assert(*txin_weight > -1);
+        weight += *txin_weight;
+    }
+
+    // It's ok to use 0 as the number of sigops since we never create any pathological transaction.
+    return TxSize{GetVirtualTransactionSize(weight, 0, 0), weight};
 }
 
 TxSize CalculateMaximumSignedTxSize(const CTransaction &tx, const CWallet *wallet, const CCoinControl* coin_control)
@@ -309,7 +405,9 @@ CoinsResult AvailableCoins(const CWallet& wallet,
             std::unique_ptr<SigningProvider> provider = wallet.GetSolvingProvider(output.scriptPubKey);
 
             int input_bytes = CalculateMaximumSignedInputSize(output, COutPoint(), provider.get(), can_grind_r, coinControl);
-            bool solvable = provider ? InferDescriptor(output.scriptPubKey, *provider)->IsSolvable() : false;
+            // Because CalculateMaximumSignedInputSize infers a solvable descriptor to get the satisfaction size,
+            // it is safe to assume that this input is solvable if input_bytes is greater than -1.
+            bool solvable = input_bytes > -1;
             bool spendable = ((mine & ISMINE_SPENDABLE) != ISMINE_NO) || (((mine & ISMINE_WATCH_ONLY) != ISMINE_NO) && (coinControl && coinControl->fAllowWatchOnly && solvable));
 
             // Filter by spendable outputs only
diff --git a/src/wallet/test/spend_tests.cpp b/src/wallet/test/spend_tests.cpp
index b5ea275bcb..eca1d74cf6 100644
--- a/src/wallet/test/spend_tests.cpp
+++ b/src/wallet/test/spend_tests.cpp
@@ -62,57 +62,6 @@ BOOST_FIXTURE_TEST_CASE(SubtractFee, TestChain100Setup)
     BOOST_CHECK_EQUAL(fee, check_tx(fee + 123));
 }
 
-static void TestFillInputToWeight(int64_t additional_weight, std::vector<int64_t> expected_stack_sizes)
-{
-    static const int64_t EMPTY_INPUT_WEIGHT = GetTransactionInputWeight(CTxIn());
-
-    CTxIn input;
-    int64_t target_weight = EMPTY_INPUT_WEIGHT + additional_weight;
-    BOOST_CHECK(FillInputToWeight(input, target_weight));
-    BOOST_CHECK_EQUAL(GetTransactionInputWeight(input), target_weight);
-    BOOST_CHECK_EQUAL(input.scriptWitness.stack.size(), expected_stack_sizes.size());
-    for (unsigned int i = 0; i < expected_stack_sizes.size(); ++i) {
-        BOOST_CHECK_EQUAL(input.scriptWitness.stack[i].size(), expected_stack_sizes[i]);
-    }
-}
-
-BOOST_FIXTURE_TEST_CASE(FillInputToWeightTest, BasicTestingSetup)
-{
-    {
-        // Less than or equal minimum of 165 should not add any witness data
-        CTxIn input;
-        BOOST_CHECK(!FillInputToWeight(input, -1));
-        BOOST_CHECK_EQUAL(GetTransactionInputWeight(input), 165);
-        BOOST_CHECK_EQUAL(input.scriptWitness.stack.size(), 0);
-        BOOST_CHECK(!FillInputToWeight(input, 0));
-        BOOST_CHECK_EQUAL(GetTransactionInputWeight(input), 165);
-        BOOST_CHECK_EQUAL(input.scriptWitness.stack.size(), 0);
-        BOOST_CHECK(!FillInputToWeight(input, 164));
-        BOOST_CHECK_EQUAL(GetTransactionInputWeight(input), 165);
-        BOOST_CHECK_EQUAL(input.scriptWitness.stack.size(), 0);
-        BOOST_CHECK(FillInputToWeight(input, 165));
-        BOOST_CHECK_EQUAL(GetTransactionInputWeight(input), 165);
-        BOOST_CHECK_EQUAL(input.scriptWitness.stack.size(), 0);
-    }
-
-    // Make sure we can add at least one weight
-    TestFillInputToWeight(1, {0});
-
-    // 1 byte compact size uint boundary
-    TestFillInputToWeight(252, {251});
-    TestFillInputToWeight(253, {83, 168});
-    TestFillInputToWeight(262, {86, 174});
-    TestFillInputToWeight(263, {260});
-
-    // 3 byte compact size uint boundary
-    TestFillInputToWeight(65535, {65532});
-    TestFillInputToWeight(65536, {21842, 43688});
-    TestFillInputToWeight(65545, {21845, 43694});
-    TestFillInputToWeight(65546, {65541});
-
-    // Note: We don't test the next boundary because of memory allocation constraints.
-}
-
 BOOST_FIXTURE_TEST_CASE(wallet_duplicated_preset_inputs_test, TestChain100Setup)
 {
     // Verify that the wallet's Coin Selection process does not include pre-selected inputs twice in a transaction.
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index 52f6e8e243..faf04ef598 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -1672,96 +1672,6 @@ void CWallet::InitWalletFlags(uint64_t flags)
     if (!LoadWalletFlags(flags)) assert(false);
 }
 
-// Helper for producing a max-sized low-S low-R signature (eg 71 bytes)
-// or a max-sized low-S signature (e.g. 72 bytes) depending on coin_control
-bool DummySignInput(const SigningProvider& provider, CTxIn &tx_in, const CTxOut &txout, bool can_grind_r, const CCoinControl* coin_control)
-{
-    // Fill in dummy signatures for fee calculation.
-    const CScript& scriptPubKey = txout.scriptPubKey;
-    SignatureData sigdata;
-
-    // Use max sig if watch only inputs were used, if this particular input is an external input,
-    // or if this wallet uses an external signer, to ensure a sufficient fee is attained for the requested feerate.
-    const bool use_max_sig = coin_control && (coin_control->fAllowWatchOnly || coin_control->IsExternalSelected(tx_in.prevout) || !can_grind_r);
-    if (!ProduceSignature(provider, use_max_sig ? DUMMY_MAXIMUM_SIGNATURE_CREATOR : DUMMY_SIGNATURE_CREATOR, scriptPubKey, sigdata)) {
-        return false;
-    }
-    UpdateInput(tx_in, sigdata);
-    return true;
-}
-
-bool FillInputToWeight(CTxIn& txin, int64_t target_weight)
-{
-    assert(txin.scriptSig.empty());
-    assert(txin.scriptWitness.IsNull());
-
-    int64_t txin_weight = GetTransactionInputWeight(txin);
-
-    // Do nothing if the weight that should be added is less than the weight that already exists
-    if (target_weight < txin_weight) {
-        return false;
-    }
-    if (target_weight == txin_weight) {
-        return true;
-    }
-
-    // Subtract current txin weight, which should include empty witness stack
-    int64_t add_weight = target_weight - txin_weight;
-    assert(add_weight > 0);
-
-    // We will want to subtract the size of the Compact Size UInt that will also be serialized.
-    // However doing so when the size is near a boundary can result in a problem where it is not
-    // possible to have a stack element size and combination to exactly equal a target.
-    // To avoid this possibility, if the weight to add is less than 10 bytes greater than
-    // a boundary, the size will be split so that 2/3rds will be in one stack element, and
-    // the remaining 1/3rd in another. Using 3rds allows us to avoid additional boundaries.
-    // 10 bytes is used because that accounts for the maximum size. This does not need to be super precise.
-    if ((add_weight >= 253 && add_weight < 263)
-        || (add_weight > std::numeric_limits<uint16_t>::max() && add_weight <= std::numeric_limits<uint16_t>::max() + 10)
-        || (add_weight > std::numeric_limits<uint32_t>::max() && add_weight <= std::numeric_limits<uint32_t>::max() + 10)) {
-        int64_t first_weight = add_weight / 3;
-        add_weight -= first_weight;
-
-        first_weight -= GetSizeOfCompactSize(first_weight);
-        txin.scriptWitness.stack.emplace(txin.scriptWitness.stack.end(), first_weight, 0);
-    }
-
-    add_weight -= GetSizeOfCompactSize(add_weight);
-    txin.scriptWitness.stack.emplace(txin.scriptWitness.stack.end(), add_weight, 0);
-    assert(GetTransactionInputWeight(txin) == target_weight);
-
-    return true;
-}
-
-// Helper for producing a bunch of max-sized low-S low-R signatures (eg 71 bytes)
-bool CWallet::DummySignTx(CMutableTransaction &txNew, const std::vector<CTxOut> &txouts, const CCoinControl* coin_control) const
-{
-    // Fill in dummy signatures for fee calculation.
-    int nIn = 0;
-    const bool can_grind_r = CanGrindR();
-    for (const auto& txout : txouts)
-    {
-        CTxIn& txin = txNew.vin[nIn];
-        // If weight was provided, fill the input to that weight
-        if (coin_control && coin_control->HasInputWeight(txin.prevout)) {
-            if (!FillInputToWeight(txin, coin_control->GetInputWeight(txin.prevout))) {
-                return false;
-            }
-            nIn++;
-            continue;
-        }
-        const std::unique_ptr<SigningProvider> provider = GetSolvingProvider(txout.scriptPubKey);
-        if (!provider || !DummySignInput(*provider, txin, txout, can_grind_r, coin_control)) {
-            if (!coin_control || !DummySignInput(coin_control->m_external_provider, txin, txout, can_grind_r, coin_control)) {
-                return false;
-            }
-        }
-
-        nIn++;
-    }
-    return true;
-}
-
 bool CWallet::ImportScripts(const std::set<CScript> scripts, int64_t timestamp)
 {
     auto spk_man = GetLegacyScriptPubKeyMan();
diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
index e2be6a206a..df337758e8 100644
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -650,8 +650,6 @@ public:
     bool SubmitTxMemoryPoolAndRelay(CWalletTx& wtx, std::string& err_string, bool relay) const
         EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
 
-    bool DummySignTx(CMutableTransaction &txNew, const std::vector<CTxOut> &txouts, const CCoinControl* coin_control = nullptr) const;
-
     bool ImportScripts(const std::set<CScript> scripts, int64_t timestamp) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
     bool ImportPrivKeys(const std::map<CKeyID, CKey>& privkey_map, const int64_t timestamp) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
     bool ImportPubKeys(const std::vector<CKeyID>& ordered_pubkeys, const std::map<CKeyID, CPubKey>& pubkey_map, const std::map<CKeyID, std::pair<CPubKey, KeyOriginInfo>>& key_origins, const bool add_keypool, const bool internal, const int64_t timestamp) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
@@ -1064,10 +1062,6 @@ bool AddWalletSetting(interfaces::Chain& chain, const std::string& wallet_name);
 //! Remove wallet name from persistent configuration so it will not be loaded on startup.
 bool RemoveWalletSetting(interfaces::Chain& chain, const std::string& wallet_name);
 
-bool DummySignInput(const SigningProvider& provider, CTxIn &tx_in, const CTxOut &txout, bool can_grind_r, const CCoinControl* coin_control);
-
-bool FillInputToWeight(CTxIn& txin, int64_t target_weight);
-
 struct MigrationResult {
     std::string wallet_name;
     std::shared_ptr<CWallet> watchonly_wallet;