Merge bitcoin/bitcoin#27255: MiniTapscript: port Miniscript to Tapscript

ec0fc14a22f38b487929ec21145945966f301eb5 miniscript: remove P2WSH-specific part of GetStackSize doc comment (Antoine Poinsot)
128bc104ef07e1edaad5378e2ca53e97672a1652 qa: bound testing for TapMiniscript (Antoine Poinsot)
117927bd5f30c8bf09aaf91e62f5244990788084 miniscript: have a custom Node destructor (Antoine Poinsot)
b917c715ace19fb23661b4b245039da48cefc6bf qa: Tapscript Miniscript signing functional tests (Antoine Poinsot)
5dc341dfe672c7195bc71f2834152b86a710c313 qa: list descriptors in Miniscript signing functional tests (Antoine Poinsot)
4f473ea515bc77b9138323dab8a741c063d32e8f script/sign: Miniscript support in Tapscript (Antoine Poinsot)
febe2abc0e3f67b8b0ac9ece1890efb4a0bba83c MOVEONLY: script/sign: move Satisfier declaration above Tapscript signing (Antoine Poinsot)
bd4b11ee06096655b74586413efe40c14d9ef44c qa: functional test Miniscript inside Taproot descriptors (Antoine Poinsot)
8571b89a7fce50229242ef3c6d9f807949f716a3 descriptor: parse Miniscript expressions within Taproot descriptors (Antoine Poinsot)
8ff9489422009284967aeb9ff4232b135f5ddad8 descriptor: Tapscript-specific Miniscript key serialization / parsing (Antoine Poinsot)
5e76f3f0ddbce513c2b626b5ab45242f931d5d60 fuzz: miniscript: higher sensitivity for max stack size limit under Tapscript (Antoine Poinsot)
6f529cbaaf773dd77f3262b1fbd5039856434898 qa: test Miniscript max stack size tracking (Antoine Poinsot)
770ba5b51979b99de513d5a9d15e451b7d29b647 miniscript: check maximum stack size during execution (Antoine Poinsot)
574523dbe030f5fb8aca4d7fd41cdc304bd913d3 fuzz: adapt Miniscript targets to Tapscript (Antoine Poinsot)
84623722ef3a1ff6fc302517adc554ba6cb023a7 qa: Tapscript-Miniscript unit tests (Antoine Poinsot)
fcb6f13f442d6a3f27689a87e3ed2bb9b431a332 pubkey: introduce a GetEvenCorrespondingCPubKey helper (Antoine Poinsot)
ce8845f5dda403461178c08e7363978fda423999 miniscript: account for keys as being 32 bytes under Taproot context (Antoine Poinsot)
f4f978d38ee4920c5cd0de5d93b407ec37bfd9c0 miniscript: adapt resources checks depending on context (Antoine Poinsot)
9cb4c68b89a5715f82026f4aa446b876addd8472 serialize: make GetSizeOfCompactSize constexpr (Antoine Poinsot)
892436c7d575ffdb9bada5fe4e62d6c1f5053c42 miniscript: sanity asserts context in ComputeType (Antoine Poinsot)
e5aaa3d77af7459b37c0c4a37eb22c5fd0cda3e1 miniscript: make 'd:' have the 'u' property under Tapscript context (Antoine Poinsot)
687a0b0fa53ddd5632287b9e00ad8b0550830287 miniscript: introduce a multi_a fragment (Antoine Poinsot)
9164c2eca164d78cbae5351d383f39320711efb9 miniscript: restrict multi() usage to P2WSH context (Antoine Poinsot)
91b4db859023f5cf59f4b27f880484c863ccae66 miniscript: store the script context within the Node structure (Antoine Poinsot)
c3738d0344f589162b9ffb78b8e2d78f612d3786 miniscript: introduce a MsContext() helper to contexts (Antoine Poinsot)
bba9340a947446cd1c70852f58dcd8aee35be9ac miniscript: don't anticipate signature presence in CalcStackSize() (Antoine Poinsot)
a3793f2d1a43624631d6329f6c900a83e7dd0e98 miniscript: add a missing dup key check bypass in Parse() (Antoine Poinsot)

Pull request description:

  Miniscript was targeting P2WSH, and as such can currently only be used in `wsh()` descriptors. This pull request introduces support for Tapscript in Miniscript and makes Miniscript available inside `tr()` descriptors. It adds support for both watching *and* signing TapMiniscript descriptors.

  The main changes to Miniscript for Tapscript are the following:
  - A new `multi_a` fragment is introduced with the same semantics as `multi`. Like in other descriptors `multi` and `multi_a` can exclusively be used in respectively P2WSH and Tapscript.
  - The `d:` fragment has the `u` property under Tapscript, since the `MINIMALIF` rule is now consensus. See also https://github.com/bitcoin/bitcoin/pull/24906.
  - Keys are now serialized as 32 bytes. (Note this affects the key hashes.)
  - The resource consumption checks and calculation changed. Some limits were lifted in Tapscript, and signatures are now 64 bytes long.

  The largest amount of complexity probably lies in the last item. Scripts under Taproot can now run into the maximum stack size while executing a fragment. For instance if you've got a stack size of `999` due to the initial witness plus some execution that happened before and try to execute a `hash256` it would `DUP` (increasing the stack size `1000`), `HASH160` and then push the hash on the stack making the script fail.
  To make sure this does not happen on any of the spending paths of a sane Miniscript, we introduce a tracking of the maximum stack size during execution of a fragment. See the commits messages for details. Those commits were separated from the resource consumption change, and the fuzz target was tweaked to sometimes pad the witness so the script runs on the brink of the stack size limit to make sure the stack size was not underestimated.

  Existing Miniscript unit, functional and fuzz tests are extended with Tapscript logic and test cases. Care was taken for seed stability in the fuzz targets where we cared more about them.

  The design of Miniscript for Tapscript is the result of discussions between various people over the past year(s). To the extent of my knowledge at least Pieter Wuille, Sanket Kanjalkar, Andrew Poelstra and Andrew Chow contributed thoughts and ideas.

ACKs for top commit:
  sipa:
    ACK ec0fc14a22f38b487929ec21145945966f301eb5
  achow101:
    ACK ec0fc14a22f38b487929ec21145945966f301eb5

Tree-SHA512: f3cf98a3ec8e565650ccf51b7ee7e4b4c2b3949a1168bee16ec03d2942b4d9f20dedc2820457f67a3216161022263573d08419c8346d807a693169ad3a436e07

5 files changed, 761 insertions, 301 deletions

diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
index 896fb0b5b3..ba2334df49 100644
--- a/src/script/descriptor.cpp
+++ b/src/script/descriptor.cpp
@@ -1114,16 +1114,33 @@ public:
 class ScriptMaker {
     //! Keys contained in the Miniscript (the evaluation of DescriptorImpl::m_pubkey_args).
     const std::vector<CPubKey>& m_keys;
+    //! The script context we're operating within (Tapscript or P2WSH).
+    const miniscript::MiniscriptContext m_script_ctx;
+
+    //! Get the ripemd160(sha256()) hash of this key.
+    //! Any key that is valid in a descriptor serializes as 32 bytes within a Tapscript context. So we
+    //! must not hash the sign-bit byte in this case.
+    uint160 GetHash160(uint32_t key) const {
+        if (miniscript::IsTapscript(m_script_ctx)) {
+            return Hash160(XOnlyPubKey{m_keys[key]});
+        }
+        return m_keys[key].GetID();
+    }
 
 public:
-    ScriptMaker(const std::vector<CPubKey>& keys LIFETIMEBOUND) : m_keys(keys) {}
+    ScriptMaker(const std::vector<CPubKey>& keys LIFETIMEBOUND, const miniscript::MiniscriptContext script_ctx) : m_keys(keys), m_script_ctx{script_ctx} {}
 
     std::vector<unsigned char> ToPKBytes(uint32_t key) const {
-        return {m_keys[key].begin(), m_keys[key].end()};
+        // In Tapscript keys always serialize as x-only, whether an x-only key was used in the descriptor or not.
+        if (!miniscript::IsTapscript(m_script_ctx)) {
+            return {m_keys[key].begin(), m_keys[key].end()};
+        }
+        const XOnlyPubKey xonly_pubkey{m_keys[key]};
+        return {xonly_pubkey.begin(), xonly_pubkey.end()};
     }
 
     std::vector<unsigned char> ToPKHBytes(uint32_t key) const {
-        auto id = m_keys[key].GetID();
+        auto id = GetHash160(key);
         return {id.begin(), id.end()};
     }
 };
@@ -1164,8 +1181,15 @@ protected:
     std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript> scripts,
                                      FlatSigningProvider& provider) const override
     {
-        for (const auto& key : keys) provider.pubkeys.emplace(key.GetID(), key);
-        return Vector(m_node->ToScript(ScriptMaker(keys)));
+        const auto script_ctx{m_node->GetMsCtx()};
+        for (const auto& key : keys) {
+            if (miniscript::IsTapscript(script_ctx)) {
+                provider.pubkeys.emplace(Hash160(XOnlyPubKey{key}), key);
+            } else {
+                provider.pubkeys.emplace(key.GetID(), key);
+            }
+        }
+        return Vector(m_node->ToScript(ScriptMaker(keys, script_ctx)));
     }
 
 public:
@@ -1401,9 +1425,7 @@ std::unique_ptr<PubkeyProvider> InferPubkey(const CPubKey& pubkey, ParseScriptCo
 
 std::unique_ptr<PubkeyProvider> InferXOnlyPubkey(const XOnlyPubKey& xkey, ParseScriptContext ctx, const SigningProvider& provider)
 {
-    unsigned char full_key[CPubKey::COMPRESSED_SIZE] = {0x02};
-    std::copy(xkey.begin(), xkey.end(), full_key + 1);
-    CPubKey pubkey(full_key);
+    CPubKey pubkey{xkey.GetEvenCorrespondingCPubKey()};
     std::unique_ptr<PubkeyProvider> key_provider = std::make_unique<ConstPubkeyProvider>(0, pubkey, true);
     KeyOriginInfo info;
     if (provider.GetKeyOriginByXOnly(xkey, info)) {
@@ -1426,18 +1448,32 @@ struct KeyParser {
     mutable std::vector<std::unique_ptr<PubkeyProvider>> m_keys;
     //! Used to detect key parsing errors within a Miniscript.
     mutable std::string m_key_parsing_error;
+    //! The script context we're operating within (Tapscript or P2WSH).
+    const miniscript::MiniscriptContext m_script_ctx;
+    //! The number of keys that were parsed before starting to parse this Miniscript descriptor.
+    uint32_t m_offset;
 
-    KeyParser(FlatSigningProvider* out LIFETIMEBOUND, const SigningProvider* in LIFETIMEBOUND) : m_out(out), m_in(in) {}
+    KeyParser(FlatSigningProvider* out LIFETIMEBOUND, const SigningProvider* in LIFETIMEBOUND,
+              miniscript::MiniscriptContext ctx, uint32_t offset = 0)
+        : m_out(out), m_in(in), m_script_ctx(ctx), m_offset(offset) {}
 
     bool KeyCompare(const Key& a, const Key& b) const {
         return *m_keys.at(a) < *m_keys.at(b);
     }
 
+    ParseScriptContext ParseContext() const {
+        switch (m_script_ctx) {
+            case miniscript::MiniscriptContext::P2WSH: return ParseScriptContext::P2WSH;
+            case miniscript::MiniscriptContext::TAPSCRIPT: return ParseScriptContext::P2TR;
+        }
+        assert(false);
+    }
+
     template<typename I> std::optional<Key> FromString(I begin, I end) const
     {
         assert(m_out);
         Key key = m_keys.size();
-        auto pk = ParsePubkey(key, {&*begin, &*end}, ParseScriptContext::P2WSH, *m_out, m_key_parsing_error);
+        auto pk = ParsePubkey(m_offset + key, {&*begin, &*end}, ParseContext(), *m_out, m_key_parsing_error);
         if (!pk) return {};
         m_keys.push_back(std::move(pk));
         return key;
@@ -1451,11 +1487,18 @@ struct KeyParser {
     template<typename I> std::optional<Key> FromPKBytes(I begin, I end) const
     {
         assert(m_in);
-        CPubKey pubkey(begin, end);
-        if (pubkey.IsValidNonHybrid()) {
-            Key key = m_keys.size();
-            m_keys.push_back(InferPubkey(pubkey, ParseScriptContext::P2WSH, *m_in));
+        Key key = m_keys.size();
+        if (miniscript::IsTapscript(m_script_ctx) && end - begin == 32) {
+            XOnlyPubKey pubkey;
+            std::copy(begin, end, pubkey.begin());
+            m_keys.push_back(InferPubkey(pubkey.GetEvenCorrespondingCPubKey(), ParseContext(), *m_in));
             return key;
+        } else if (!miniscript::IsTapscript(m_script_ctx)) {
+            CPubKey pubkey{begin, end};
+            if (pubkey.IsValidNonHybrid()) {
+                m_keys.push_back(InferPubkey(pubkey, ParseContext(), *m_in));
+                return key;
+            }
         }
         return {};
     }
@@ -1470,11 +1513,15 @@ struct KeyParser {
         CPubKey pubkey;
         if (m_in->GetPubKey(keyid, pubkey)) {
             Key key = m_keys.size();
-            m_keys.push_back(InferPubkey(pubkey, ParseScriptContext::P2WSH, *m_in));
+            m_keys.push_back(InferPubkey(pubkey, ParseContext(), *m_in));
             return key;
         }
         return {};
     }
+
+    miniscript::MiniscriptContext MsContext() const {
+        return m_script_ctx;
+    }
 };
 
 /** Parse a script in a particular context. */
@@ -1500,8 +1547,9 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
         }
         ++key_exp_index;
         return std::make_unique<PKHDescriptor>(std::move(pubkey));
-    } else if (Func("pkh", expr)) {
-        error = "Can only have pkh at top level, in sh(), or in wsh()";
+    } else if (ctx != ParseScriptContext::P2TR && Func("pkh", expr)) {
+        // Under Taproot, always the Miniscript parser deal with it.
+        error = "Can only have pkh at top level, in sh(), wsh(), or in tr()";
         return nullptr;
     }
     if (ctx == ParseScriptContext::TOP && Func("combo", expr)) {
@@ -1714,11 +1762,12 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
     }
     // Process miniscript expressions.
     {
-        KeyParser parser(&out, nullptr);
+        const auto script_ctx{ctx == ParseScriptContext::P2WSH ? miniscript::MiniscriptContext::P2WSH : miniscript::MiniscriptContext::TAPSCRIPT};
+        KeyParser parser(/*out = */&out, /* in = */nullptr, /* ctx = */script_ctx, key_exp_index);
         auto node = miniscript::FromString(std::string(expr.begin(), expr.end()), parser);
         if (node) {
-            if (ctx != ParseScriptContext::P2WSH) {
-                error = "Miniscript expressions can only be used in wsh";
+            if (ctx != ParseScriptContext::P2WSH && ctx != ParseScriptContext::P2TR) {
+                error = "Miniscript expressions can only be used in wsh or tr.";
                 return nullptr;
             }
             if (parser.m_key_parsing_error != "") {
@@ -1753,6 +1802,7 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
             // A signature check is required for a miniscript to be sane. Therefore no sane miniscript
             // may have an empty list of public keys.
             CHECK_NONFATAL(!parser.m_keys.empty());
+            key_exp_index += parser.m_keys.size();
             return std::make_unique<MiniscriptDescriptor>(std::move(parser.m_keys), std::move(node));
         }
     }
@@ -1886,8 +1936,9 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
         }
     }
 
-    if (ctx == ParseScriptContext::P2WSH) {
-        KeyParser parser(nullptr, &provider);
+    if (ctx == ParseScriptContext::P2WSH || ctx == ParseScriptContext::P2TR) {
+        const auto script_ctx{ctx == ParseScriptContext::P2WSH ? miniscript::MiniscriptContext::P2WSH : miniscript::MiniscriptContext::TAPSCRIPT};
+        KeyParser parser(/* out = */nullptr, /* in = */&provider, /* ctx = */script_ctx);
         auto node = miniscript::FromScript(script, parser);
         if (node && node->IsSane()) {
             return std::make_unique<MiniscriptDescriptor>(std::move(parser.m_keys), std::move(node));
diff --git a/src/script/miniscript.cpp b/src/script/miniscript.cpp
index 19556a9775..344a81bdf0 100644
--- a/src/script/miniscript.cpp
+++ b/src/script/miniscript.cpp
@@ -6,6 +6,7 @@
 #include <vector>
 #include <script/script.h>
 #include <script/miniscript.h>
+#include <serialize.h>
 
 #include <assert.h>
 
@@ -32,7 +33,8 @@ Type SanitizeType(Type e) {
     return e;
 }
 
-Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys) {
+Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k,
+                 size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx) {
     // Sanity check on data
     if (fragment == Fragment::SHA256 || fragment == Fragment::HASH256) {
         assert(data_size == 32);
@@ -44,7 +46,7 @@ Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Ty
     // Sanity check on k
     if (fragment == Fragment::OLDER || fragment == Fragment::AFTER) {
         assert(k >= 1 && k < 0x80000000UL);
-    } else if (fragment == Fragment::MULTI) {
+    } else if (fragment == Fragment::MULTI || fragment == Fragment::MULTI_A) {
         assert(k >= 1 && k <= n_keys);
     } else if (fragment == Fragment::THRESH) {
         assert(k >= 1 && k <= n_subs);
@@ -68,7 +70,11 @@ Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Ty
     if (fragment == Fragment::PK_K || fragment == Fragment::PK_H) {
         assert(n_keys == 1);
     } else if (fragment == Fragment::MULTI) {
-        assert(n_keys >= 1 && n_keys <= 20);
+        assert(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTISIG);
+        assert(!IsTapscript(ms_ctx));
+    } else if (fragment == Fragment::MULTI_A) {
+        assert(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTI_A);
+        assert(IsTapscript(ms_ctx));
     } else {
         assert(n_keys == 0);
     }
@@ -113,7 +119,8 @@ Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Ty
             "e"_mst.If(x << "f"_mst) | // e=f_x
             (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
             (x & "ms"_mst) | // m=m_x, s=s_x
-            // NOTE: 'd:' is not 'u' under P2WSH as MINIMALIF is only a policy rule there.
+            // NOTE: 'd:' is 'u' under Tapscript but not P2WSH as MINIMALIF is only a policy rule there.
+            "u"_mst.If(IsTapscript(ms_ctx)) |
             "ndx"_mst; // n, d, x
         case Fragment::WRAP_V: return
             "V"_mst.If(x << "B"_mst) | // V=B_x
@@ -210,7 +217,12 @@ Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Ty
                 ((x << "h"_mst) && (y << "g"_mst)) ||
                 ((x << "i"_mst) && (y << "j"_mst)) ||
                 ((x << "j"_mst) && (y << "i"_mst)))); // k=k_x*k_y*k_z* !(g_x*h_y + h_x*g_y + i_x*j_y + j_x*i_y)
-        case Fragment::MULTI: return "Bnudemsk"_mst;
+        case Fragment::MULTI: {
+            return "Bnudemsk"_mst;
+        }
+        case Fragment::MULTI_A: {
+            return "Budemsk"_mst;
+        }
         case Fragment::THRESH: {
             bool all_e = true;
             bool all_m = true;
@@ -246,11 +258,12 @@ Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Ty
     assert(false);
 }
 
-size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys) {
+size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs,
+                        size_t n_keys, MiniscriptContext ms_ctx) {
     switch (fragment) {
         case Fragment::JUST_1:
         case Fragment::JUST_0: return 1;
-        case Fragment::PK_K: return 34;
+        case Fragment::PK_K: return IsTapscript(ms_ctx) ? 33 : 34;
         case Fragment::PK_H: return 3 + 21;
         case Fragment::OLDER:
         case Fragment::AFTER: return 1 + BuildScript(k).size();
@@ -259,6 +272,7 @@ size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_
         case Fragment::HASH160:
         case Fragment::RIPEMD160: return 4 + 2 + 21;
         case Fragment::MULTI: return 1 + BuildScript(n_keys).size() + BuildScript(k).size() + 34 * n_keys;
+        case Fragment::MULTI_A: return (1 + 32 + 1) * n_keys + BuildScript(k).size() + 1;
         case Fragment::AND_V: return subsize;
         case Fragment::WRAP_V: return subsize + (sub0typ << "x"_mst);
         case Fragment::WRAP_S:
@@ -372,9 +386,13 @@ std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script)
             // Decompose OP_EQUALVERIFY into OP_EQUAL OP_VERIFY
             out.emplace_back(OP_EQUAL, std::vector<unsigned char>());
             opcode = OP_VERIFY;
+        } else if (opcode == OP_NUMEQUALVERIFY) {
+            // Decompose OP_NUMEQUALVERIFY into OP_NUMEQUAL OP_VERIFY
+            out.emplace_back(OP_NUMEQUAL, std::vector<unsigned char>());
+            opcode = OP_VERIFY;
         } else if (IsPushdataOp(opcode)) {
             if (!CheckMinimalPush(push_data, opcode)) return {};
-        } else if (it != itend && (opcode == OP_CHECKSIG || opcode == OP_CHECKMULTISIG || opcode == OP_EQUAL) && (*it == OP_VERIFY)) {
+        } else if (it != itend && (opcode == OP_CHECKSIG || opcode == OP_CHECKMULTISIG || opcode == OP_EQUAL || opcode == OP_NUMEQUAL) && (*it == OP_VERIFY)) {
             // Rule out non minimal VERIFY sequences
             return {};
         }
diff --git a/src/script/miniscript.h b/src/script/miniscript.h
index 4c6bd0bb1d..d6bded959d 100644
--- a/src/script/miniscript.h
+++ b/src/script/miniscript.h
@@ -20,6 +20,7 @@
 #include <primitives/transaction.h>
 #include <script/script.h>
 #include <span.h>
+#include <util/check.h>
 #include <util/spanparsing.h>
 #include <util/strencodings.h>
 #include <util/string.h>
@@ -44,8 +45,8 @@ namespace miniscript {
  *   - When satisfied, pushes nothing.
  *   - Cannot be dissatisfied.
  *   - This can be obtained by adding an OP_VERIFY to a B, modifying the last opcode
- *     of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY
- *     and OP_EQUAL), or by combining a V fragment under some conditions.
+ *     of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY,
+ *     OP_NUMEQUAL and OP_EQUAL), or by combining a V fragment under some conditions.
  *   - For example vc:pk_k(key) = <key> OP_CHECKSIGVERIFY
  * - "K" Key:
  *   - Takes its inputs from the top of the stack.
@@ -216,7 +217,8 @@ enum class Fragment {
     OR_I,      //!< OP_IF [X] OP_ELSE [Y] OP_ENDIF
     ANDOR,     //!< [X] OP_NOTIF [Z] OP_ELSE [Y] OP_ENDIF
     THRESH,    //!< [X1] ([Xn] OP_ADD)* [k] OP_EQUAL
-    MULTI,     //!< [k] [key_n]* [n] OP_CHECKMULTISIG
+    MULTI,     //!< [k] [key_n]* [n] OP_CHECKMULTISIG (only available within P2WSH context)
+    MULTI_A,   //!< [key_0] OP_CHECKSIG ([key_n] OP_CHECKSIGADD)* [k] OP_NUMEQUAL (only within Tapscript ctx)
     // AND_N(X,Y) is represented as ANDOR(X,Y,0)
     // WRAP_T(X) is represented as AND_V(X,1)
     // WRAP_L(X) is represented as OR_I(0,X)
@@ -229,13 +231,56 @@ enum class Availability {
     MAYBE,
 };
 
+enum class MiniscriptContext {
+    P2WSH,
+    TAPSCRIPT,
+};
+
+/** Whether the context Tapscript, ensuring the only other possibility is P2WSH. */
+constexpr bool IsTapscript(MiniscriptContext ms_ctx)
+{
+    switch (ms_ctx) {
+        case MiniscriptContext::P2WSH: return false;
+        case MiniscriptContext::TAPSCRIPT: return true;
+    }
+    assert(false);
+}
+
 namespace internal {
 
+//! The maximum size of a witness item for a Miniscript under Tapscript context. (A BIP340 signature with a sighash type byte.)
+static constexpr uint32_t MAX_TAPMINISCRIPT_STACK_ELEM_SIZE{65};
+
+//! nVersion + nLockTime
+constexpr uint32_t TX_OVERHEAD{4 + 4};
+//! prevout + nSequence + scriptSig
+constexpr uint32_t TXIN_BYTES_NO_WITNESS{36 + 4 + 1};
+//! nValue + script len + OP_0 + pushdata 32.
+constexpr uint32_t P2WSH_TXOUT_BYTES{8 + 1 + 1 + 33};
+//! Data other than the witness in a transaction. Overhead + vin count + one vin + vout count + one vout + segwit marker
+constexpr uint32_t TX_BODY_LEEWAY_WEIGHT{(TX_OVERHEAD + GetSizeOfCompactSize(1) + TXIN_BYTES_NO_WITNESS + GetSizeOfCompactSize(1) + P2WSH_TXOUT_BYTES) * WITNESS_SCALE_FACTOR + 2};
+//! Maximum possible stack size to spend a Taproot output (excluding the script itself).
+constexpr uint32_t MAX_TAPSCRIPT_SAT_SIZE{GetSizeOfCompactSize(MAX_STACK_SIZE) + (GetSizeOfCompactSize(MAX_TAPMINISCRIPT_STACK_ELEM_SIZE) + MAX_TAPMINISCRIPT_STACK_ELEM_SIZE) * MAX_STACK_SIZE + GetSizeOfCompactSize(TAPROOT_CONTROL_MAX_SIZE) + TAPROOT_CONTROL_MAX_SIZE};
+/** The maximum size of a script depending on the context. */
+constexpr uint32_t MaxScriptSize(MiniscriptContext ms_ctx)
+{
+    if (IsTapscript(ms_ctx)) {
+        // Leaf scripts under Tapscript are not explicitly limited in size. They are only implicitly
+        // bounded by the maximum standard size of a spending transaction. Let the maximum script
+        // size conservatively be small enough such that even a maximum sized witness and a reasonably
+        // sized spending transaction can spend an output paying to this script without running into
+        // the maximum standard tx size limit.
+        constexpr auto max_size{MAX_STANDARD_TX_WEIGHT - TX_BODY_LEEWAY_WEIGHT - MAX_TAPSCRIPT_SAT_SIZE};
+        return max_size - GetSizeOfCompactSize(max_size);
+    }
+    return MAX_STANDARD_P2WSH_SCRIPT_SIZE;
+}
+
 //! Helper function for Node::CalcType.
-Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys);
+Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx);
 
 //! Helper function for Node::CalcScriptLen.
-size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys);
+size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx);
 
 //! A helper sanitizer/checker for the output of CalcType.
 Type SanitizeType(Type x);
@@ -328,13 +373,112 @@ struct Ops {
     Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {};
 };
 
+/** A data structure to help the calculation of stack size limits.
+ *
+ * Conceptually, every SatInfo object corresponds to a (possibly empty) set of script execution
+ * traces (sequences of opcodes).
+ * - SatInfo{} corresponds to the empty set.
+ * - SatInfo{n, e} corresponds to a single trace whose net effect is removing n elements from the
+ *   stack (may be negative for a net increase), and reaches a maximum of e stack elements more
+ *   than it ends with.
+ * - operator| is the union operation: (a | b) corresponds to the union of the traces in a and the
+ *   traces in b.
+ * - operator+ is the concatenation operator: (a + b) corresponds to the set of traces formed by
+ *   concatenating any trace in a with any trace in b.
+ *
+ * Its fields are:
+ * - valid is true if the set is non-empty.
+ * - netdiff (if valid) is the largest difference between stack size at the beginning and at the
+ *   end of the script across all traces in the set.
+ * - exec (if valid) is the largest difference between stack size anywhere during execution and at
+ *   the end of the script, across all traces in the set (note that this is not necessarily due
+ *   to the same trace as the one that resulted in the value for netdiff).
+ *
+ * This allows us to build up stack size limits for any script efficiently, by starting from the
+ * individual opcodes miniscripts correspond to, using concatenation to construct scripts, and
+ * using the union operation to choose between execution branches. Since any top-level script
+ * satisfaction ends with a single stack element, we know that for a full script:
+ * - netdiff+1 is the maximal initial stack size (relevant for P2WSH stack limits).
+ * - exec+1 is the maximal stack size reached during execution (relevant for P2TR stack limits).
+ *
+ * Mathematically, SatInfo forms a semiring:
+ * - operator| is the semiring addition operator, with identity SatInfo{}, and which is commutative
+ *   and associative.
+ * - operator+ is the semiring multiplication operator, with identity SatInfo{0}, and which is
+ *   associative.
+ * - operator+ is distributive over operator|, so (a + (b | c)) = (a+b | a+c). This means we do not
+ *   need to actually materialize all possible full execution traces over the whole script (which
+ *   may be exponential in the length of the script); instead we can use the union operation at the
+ *   individual subexpression level, and concatenate the result with subexpressions before and
+ *   after it.
+ * - It is not a commutative semiring, because a+b can differ from b+a. For example, "OP_1 OP_DROP"
+ *   has exec=1, while "OP_DROP OP_1" has exec=0.
+ */
+struct SatInfo {
+    //! Whether a canonical satisfaction/dissatisfaction is possible at all.
+    const bool valid;
+    //! How much higher the stack size at start of execution can be compared to at the end.
+    const int32_t netdiff;
+    //! Mow much higher the stack size can be during execution compared to at the end.
+    const int32_t exec;
+
+    /** Empty script set. */
+    constexpr SatInfo() noexcept : valid(false), netdiff(0), exec(0) {}
+
+    /** Script set with a single script in it, with specified netdiff and exec. */
+    constexpr SatInfo(int32_t in_netdiff, int32_t in_exec) noexcept :
+        valid{true}, netdiff{in_netdiff}, exec{in_exec} {}
+
+    /** Script set union. */
+    constexpr friend SatInfo operator|(const SatInfo& a, const SatInfo& b) noexcept
+    {
+        // Union with an empty set is itself.
+        if (!a.valid) return b;
+        if (!b.valid) return a;
+        // Otherwise the netdiff and exec of the union is the maximum of the individual values.
+        return {std::max(a.netdiff, b.netdiff), std::max(a.exec, b.exec)};
+    }
+
+    /** Script set concatenation. */
+    constexpr friend SatInfo operator+(const SatInfo& a, const SatInfo& b) noexcept
+    {
+        // Concatenation with an empty set yields an empty set.
+        if (!a.valid || !b.valid) return {};
+        // Otherwise, the maximum stack size difference for the combined scripts is the sum of the
+        // netdiffs, and the maximum stack size difference anywhere is either b.exec (if the
+        // maximum occurred in b) or b.netdiff+a.exec (if the maximum occurred in a).
+        return {a.netdiff + b.netdiff, std::max(b.exec, b.netdiff + a.exec)};
+    }
+
+    /** The empty script. */
+    static constexpr SatInfo Empty() noexcept { return {0, 0}; }
+    /** A script consisting of a single push opcode. */
+    static constexpr SatInfo Push() noexcept { return {-1, 0}; }
+    /** A script consisting of a single hash opcode. */
+    static constexpr SatInfo Hash() noexcept { return {0, 0}; }
+    /** A script consisting of just a repurposed nop (OP_CHECKLOCKTIMEVERIFY, OP_CHECKSEQUENCEVERIFY). */
+    static constexpr SatInfo Nop() noexcept { return {0, 0}; }
+    /** A script consisting of just OP_IF or OP_NOTIF. Note that OP_ELSE and OP_ENDIF have no stack effect. */
+    static constexpr SatInfo If() noexcept { return {1, 1}; }
+    /** A script consisting of just a binary operator (OP_BOOLAND, OP_BOOLOR, OP_ADD). */
+    static constexpr SatInfo BinaryOp() noexcept { return {1, 1}; }
+
+    // Scripts for specific individual opcodes.
+    static constexpr SatInfo OP_DUP() noexcept { return {-1, 0}; }
+    static constexpr SatInfo OP_IFDUP(bool nonzero) noexcept { return {nonzero ? -1 : 0, 0}; }
+    static constexpr SatInfo OP_EQUALVERIFY() noexcept { return {2, 2}; }
+    static constexpr SatInfo OP_EQUAL() noexcept { return {1, 1}; }
+    static constexpr SatInfo OP_SIZE() noexcept { return {-1, 0}; }
+    static constexpr SatInfo OP_CHECKSIG() noexcept { return {1, 1}; }
+    static constexpr SatInfo OP_0NOTEQUAL() noexcept { return {0, 0}; }
+    static constexpr SatInfo OP_VERIFY() noexcept { return {1, 1}; }
+};
+
 struct StackSize {
-    //! Maximum stack size to satisfy;
-    MaxInt<uint32_t> sat;
-    //! Maximum stack size to dissatisfy;
-    MaxInt<uint32_t> dsat;
+    const SatInfo sat, dsat;
 
-    StackSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
+    constexpr StackSize(SatInfo in_sat, SatInfo in_dsat) noexcept : sat(in_sat), dsat(in_dsat) {};
+    constexpr StackSize(SatInfo in_both) noexcept : sat(in_both), dsat(in_both) {};
 };
 
 struct WitnessSize {
@@ -362,7 +506,22 @@ struct Node {
     //! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD10).
     const std::vector<unsigned char> data;
     //! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
-    const std::vector<NodeRef<Key>> subs;
+    mutable std::vector<NodeRef<Key>> subs;
+    //! The Script context for this node. Either P2WSH or Tapscript.
+    const MiniscriptContext m_script_ctx;
+
+    /* Destroy the shared pointers iteratively to avoid a stack-overflow due to recursive calls
+     * to the subs' destructors. */
+    ~Node() {
+        while (!subs.empty()) {
+            auto node = std::move(subs.back());
+            subs.pop_back();
+            while (!node->subs.empty()) {
+                subs.push_back(std::move(node->subs.back()));
+                node->subs.pop_back();
+            }
+        }
+    }
 
 private:
     //! Cached ops counts.
@@ -390,7 +549,7 @@ private:
             subsize += sub->ScriptSize();
         }
         Type sub0type = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
-        return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size());
+        return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size(), m_script_ctx);
     }
 
     /* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls.
@@ -557,7 +716,7 @@ private:
         Type y = subs.size() > 1 ? subs[1]->GetType() : ""_mst;
         Type z = subs.size() > 2 ? subs[2]->GetType() : ""_mst;
 
-        return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size()));
+        return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size(), m_script_ctx));
     }
 
 public:
@@ -578,7 +737,8 @@ public:
         };
         // The upward function computes for a node, given its followed-by-OP_VERIFY status
         // and the CScripts of its child nodes, the CScript of the node.
-        auto upfn = [&ctx](bool verify, const Node& node, Span<CScript> subs) -> CScript {
+        const bool is_tapscript{IsTapscript(m_script_ctx)};
+        auto upfn = [&ctx, is_tapscript](bool verify, const Node& node, Span<CScript> subs) -> CScript {
             switch (node.fragment) {
                 case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0]));
                 case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY);
@@ -611,12 +771,21 @@ public:
                 case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
                 case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
                 case Fragment::MULTI: {
+                    CHECK_NONFATAL(!is_tapscript);
                     CScript script = BuildScript(node.k);
                     for (const auto& key : node.keys) {
                         script = BuildScript(std::move(script), ctx.ToPKBytes(key));
                     }
                     return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG);
                 }
+                case Fragment::MULTI_A: {
+                    CHECK_NONFATAL(is_tapscript);
+                    CScript script = BuildScript(ctx.ToPKBytes(*node.keys.begin()), OP_CHECKSIG);
+                    for (auto it = node.keys.begin() + 1; it != node.keys.end(); ++it) {
+                        script = BuildScript(std::move(script), ctx.ToPKBytes(*it), OP_CHECKSIGADD);
+                    }
+                    return BuildScript(std::move(script), node.k, verify ? OP_NUMEQUALVERIFY : OP_NUMEQUAL);
+                }
                 case Fragment::THRESH: {
                     CScript script = std::move(subs[0]);
                     for (size_t i = 1; i < subs.size(); ++i) {
@@ -646,7 +815,8 @@ public:
         };
         // The upward function computes for a node, given whether its parent is a wrapper,
         // and the string representations of its child nodes, the string representation of the node.
-        auto upfn = [&ctx](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
+        const bool is_tapscript{IsTapscript(m_script_ctx)};
+        auto upfn = [&ctx, is_tapscript](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
             std::string ret = wrapped ? ":" : "";
 
             switch (node.fragment) {
@@ -710,6 +880,7 @@ public:
                     if (node.subs[2]->fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
                     return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
                 case Fragment::MULTI: {
+                    CHECK_NONFATAL(!is_tapscript);
                     auto str = std::move(ret) + "multi(" + ::ToString(node.k);
                     for (const auto& key : node.keys) {
                         auto key_str = ctx.ToString(key);
@@ -718,6 +889,16 @@ public:
                     }
                     return std::move(str) + ")";
                 }
+                case Fragment::MULTI_A: {
+                    CHECK_NONFATAL(is_tapscript);
+                    auto str = std::move(ret) + "multi_a(" + ::ToString(node.k);
+                    for (const auto& key : node.keys) {
+                        auto key_str = ctx.ToString(key);
+                        if (!key_str) return {};
+                        str += "," + std::move(*key_str);
+                    }
+                    return std::move(str) + ")";
+                }
                 case Fragment::THRESH: {
                     auto str = std::move(ret) + "thresh(" + ::ToString(node.k);
                     for (auto& sub : subs) {
@@ -783,6 +964,7 @@ private:
                 return {count, sat, dsat};
             }
             case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()};
+            case Fragment::MULTI_A: return {(uint32_t)keys.size() + 1, 0, 0};
             case Fragment::WRAP_S:
             case Fragment::WRAP_C:
             case Fragment::WRAP_N: return {1 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
@@ -808,50 +990,115 @@ private:
     }
 
     internal::StackSize CalcStackSize() const {
+        using namespace internal;
         switch (fragment) {
-            case Fragment::JUST_0: return {{}, 0};
-            case Fragment::JUST_1:
+            case Fragment::JUST_0: return {{}, SatInfo::Push()};
+            case Fragment::JUST_1: return {SatInfo::Push(), {}};
             case Fragment::OLDER:
-            case Fragment::AFTER: return {0, {}};
-            case Fragment::PK_K: return {1, 1};
-            case Fragment::PK_H: return {2, 2};
+            case Fragment::AFTER: return {SatInfo::Push() + SatInfo::Nop(), {}};
+            case Fragment::PK_K: return {SatInfo::Push()};
+            case Fragment::PK_H: return {SatInfo::OP_DUP() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY()};
             case Fragment::SHA256:
             case Fragment::RIPEMD160:
             case Fragment::HASH256:
-            case Fragment::HASH160: return {1, {}};
+            case Fragment::HASH160: return {
+                SatInfo::OP_SIZE() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUAL(),
+                {}
+            };
             case Fragment::ANDOR: {
-                const auto sat{(subs[0]->ss.sat + subs[1]->ss.sat) | (subs[0]->ss.dsat + subs[2]->ss.sat)};
-                const auto dsat{subs[0]->ss.dsat + subs[2]->ss.dsat};
-                return {sat, dsat};
+                const auto& x{subs[0]->ss};
+                const auto& y{subs[1]->ss};
+                const auto& z{subs[2]->ss};
+                return {
+                    (x.sat + SatInfo::If() + y.sat) | (x.dsat + SatInfo::If() + z.sat),
+                    x.dsat + SatInfo::If() + z.dsat
+                };
+            }
+            case Fragment::AND_V: {
+                const auto& x{subs[0]->ss};
+                const auto& y{subs[1]->ss};
+                return {x.sat + y.sat, {}};
+            }
+            case Fragment::AND_B: {
+                const auto& x{subs[0]->ss};
+                const auto& y{subs[1]->ss};
+                return {x.sat + y.sat + SatInfo::BinaryOp(), x.dsat + y.dsat + SatInfo::BinaryOp()};
             }
-            case Fragment::AND_V: return {subs[0]->ss.sat + subs[1]->ss.sat, {}};
-            case Fragment::AND_B: return {subs[0]->ss.sat + subs[1]->ss.sat, subs[0]->ss.dsat + subs[1]->ss.dsat};
             case Fragment::OR_B: {
-                const auto sat{(subs[0]->ss.dsat + subs[1]->ss.sat) | (subs[0]->ss.sat + subs[1]->ss.dsat)};
-                const auto dsat{subs[0]->ss.dsat + subs[1]->ss.dsat};
-                return {sat, dsat};
+                const auto& x{subs[0]->ss};
+                const auto& y{subs[1]->ss};
+                return {
+                    ((x.sat + y.dsat) | (x.dsat + y.sat)) + SatInfo::BinaryOp(),
+                    x.dsat + y.dsat + SatInfo::BinaryOp()
+                };
             }
-            case Fragment::OR_C: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), {}};
-            case Fragment::OR_D: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), subs[0]->ss.dsat + subs[1]->ss.dsat};
-            case Fragment::OR_I: return {(subs[0]->ss.sat + 1) | (subs[1]->ss.sat + 1), (subs[0]->ss.dsat + 1) | (subs[1]->ss.dsat + 1)};
-            case Fragment::MULTI: return {k + 1, k + 1};
+            case Fragment::OR_C: {
+                const auto& x{subs[0]->ss};
+                const auto& y{subs[1]->ss};
+                return {(x.sat + SatInfo::If()) | (x.dsat + SatInfo::If() + y.sat), {}};
+            }
+            case Fragment::OR_D: {
+                const auto& x{subs[0]->ss};
+                const auto& y{subs[1]->ss};
+                return {
+                    (x.sat + SatInfo::OP_IFDUP(true) + SatInfo::If()) | (x.dsat + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.sat),
+                    x.dsat + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.dsat
+                };
+            }
+            case Fragment::OR_I: {
+                const auto& x{subs[0]->ss};
+                const auto& y{subs[1]->ss};
+                return {SatInfo::If() + (x.sat | y.sat), SatInfo::If() + (x.dsat | y.dsat)};
+            }
+            // multi(k, key1, key2, ..., key_n) starts off with k+1 stack elements (a 0, plus k
+            // signatures), then reaches n+k+3 stack elements after pushing the n keys, plus k and
+            // n itself, and ends with 1 stack element (success or failure). Thus, it net removes
+            // k elements (from k+1 to 1), while reaching k+n+2 more than it ends with.
+            case Fragment::MULTI: return {SatInfo(k, k + keys.size() + 2)};
+            // multi_a(k, key1, key2, ..., key_n) starts off with n stack elements (the
+            // signatures), reaches 1 more (after the first key push), and ends with 1. Thus it net
+            // removes n-1 elements (from n to 1) while reaching n more than it ends with.
+            case Fragment::MULTI_A: return {SatInfo(keys.size() - 1, keys.size())};
             case Fragment::WRAP_A:
             case Fragment::WRAP_N:
-            case Fragment::WRAP_S:
-            case Fragment::WRAP_C: return subs[0]->ss;
-            case Fragment::WRAP_D: return {1 + subs[0]->ss.sat, 1};
-            case Fragment::WRAP_V: return {subs[0]->ss.sat, {}};
-            case Fragment::WRAP_J: return {subs[0]->ss.sat, 1};
+            case Fragment::WRAP_S: return subs[0]->ss;
+            case Fragment::WRAP_C: return {
+                subs[0]->ss.sat + SatInfo::OP_CHECKSIG(),
+                subs[0]->ss.dsat + SatInfo::OP_CHECKSIG()
+            };
+            case Fragment::WRAP_D: return {
+                SatInfo::OP_DUP() + SatInfo::If() + subs[0]->ss.sat,
+                SatInfo::OP_DUP() + SatInfo::If()
+            };
+            case Fragment::WRAP_V: return {subs[0]->ss.sat + SatInfo::OP_VERIFY(), {}};
+            case Fragment::WRAP_J: return {
+                SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If() + subs[0]->ss.sat,
+                SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If()
+            };
             case Fragment::THRESH: {
-                auto sats = Vector(internal::MaxInt<uint32_t>(0));
-                for (const auto& sub : subs) {
-                    auto next_sats = Vector(sats[0] + sub->ss.dsat);
-                    for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ss.dsat) | (sats[j - 1] + sub->ss.sat));
-                    next_sats.push_back(sats[sats.size() - 1] + sub->ss.sat);
+                // sats[j] is the SatInfo corresponding to all traces reaching j satisfactions.
+                auto sats = Vector(SatInfo::Empty());
+                for (size_t i = 0; i < subs.size(); ++i) {
+                    // Loop over the subexpressions, processing them one by one. After adding
+                    // element i we need to add OP_ADD (if i>0).
+                    auto add = i ? SatInfo::BinaryOp() : SatInfo::Empty();
+                    // Construct a variable that will become the next sats, starting with index 0.
+                    auto next_sats = Vector(sats[0] + subs[i]->ss.dsat + add);
+                    // Then loop to construct next_sats[1..i].
+                    for (size_t j = 1; j < sats.size(); ++j) {
+                        next_sats.push_back(((sats[j] + subs[i]->ss.dsat) | (sats[j - 1] + subs[i]->ss.sat)) + add);
+                    }
+                    // Finally construct next_sats[i+1].
+                    next_sats.push_back(sats[sats.size() - 1] + subs[i]->ss.sat + add);
+                    // Switch over.
                     sats = std::move(next_sats);
                 }
-                assert(k <= sats.size());
-                return {sats[k], sats[0]};
+                // To satisfy thresh we need k satisfactions; to dissatisfy we need 0. In both
+                // cases a push of k and an OP_EQUAL follow.
+                return {
+                    sats[k] + SatInfo::Push() + SatInfo::OP_EQUAL(),
+                    sats[0] + SatInfo::Push() + SatInfo::OP_EQUAL()
+                };
             }
         }
         assert(false);
@@ -885,6 +1132,7 @@ private:
             case Fragment::OR_D: return {subs[0]->ws.sat | (subs[0]->ws.dsat + subs[1]->ws.sat), subs[0]->ws.dsat + subs[1]->ws.dsat};
             case Fragment::OR_I: return {(subs[0]->ws.sat + 1 + 1) | (subs[1]->ws.sat + 1), (subs[0]->ws.dsat + 1 + 1) | (subs[1]->ws.dsat + 1)};
             case Fragment::MULTI: return {k * (1 + 72) + 1, k + 1};
+            case Fragment::MULTI_A: return {k * (1 + 65) + static_cast<uint32_t>(keys.size()) - k, static_cast<uint32_t>(keys.size())};
             case Fragment::WRAP_A:
             case Fragment::WRAP_N:
             case Fragment::WRAP_S:
@@ -925,6 +1173,34 @@ private:
                     Availability avail = ctx.Sign(node.keys[0], sig);
                     return {ZERO + InputStack(key), (InputStack(std::move(sig)).SetWithSig() + InputStack(key)).SetAvailable(avail)};
                 }
+                case Fragment::MULTI_A: {
+                    // sats[j] represents the best stack containing j valid signatures (out of the first i keys).
+                    // In the loop below, these stacks are built up using a dynamic programming approach.
+                    std::vector<InputStack> sats = Vector(EMPTY);
+                    for (size_t i = 0; i < node.keys.size(); ++i) {
+                        // Get the signature for the i'th key in reverse order (the signature for the first key needs to
+                        // be at the top of the stack, contrary to CHECKMULTISIG's satisfaction).
+                        std::vector<unsigned char> sig;
+                        Availability avail = ctx.Sign(node.keys[node.keys.size() - 1 - i], sig);
+                        // Compute signature stack for just this key.
+                        auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail);
+                        // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further
+                        // next_sats[j] are equal to either the existing sats[j] + ZERO, or sats[j-1] plus a signature
+                        // for the current (i'th) key. The very last element needs all signatures filled.
+                        std::vector<InputStack> next_sats;
+                        next_sats.push_back(sats[0] + ZERO);
+                        for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + ZERO) | (std::move(sats[j - 1]) + sat));
+                        next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
+                        // Switch over.
+                        sats = std::move(next_sats);
+                    }
+                    // The dissatisfaction consists of as many empty vectors as there are keys, which is the same as
+                    // satisfying 0 keys.
+                    auto& nsat{sats[0]};
+                    assert(node.k != 0);
+                    assert(node.k <= sats.size());
+                    return {std::move(nsat), std::move(sats[node.k])};
+                }
                 case Fragment::MULTI: {
                     // sats[j] represents the best stack containing j valid signatures (out of the first i keys).
                     // In the loop below, these stacks are built up using a dynamic programming approach.
@@ -1205,19 +1481,36 @@ public:
 
     //! Check the ops limit of this script against the consensus limit.
     bool CheckOpsLimit() const {
+        if (IsTapscript(m_script_ctx)) return true;
         if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT;
         return true;
     }
 
-    /** Return the maximum number of stack elements needed to satisfy this script non-malleably.
-     * This does not account for the P2WSH script push. */
+    /** Whether this node is of type B, K or W. (That is, anything but V.) */
+    bool IsBKW() const {
+        return !((GetType() & "BKW"_mst) == ""_mst);
+    }
+
+    /** Return the maximum number of stack elements needed to satisfy this script non-malleably. */
     std::optional<uint32_t> GetStackSize() const {
         if (!ss.sat.valid) return {};
-        return ss.sat.value;
+        return ss.sat.netdiff + static_cast<int32_t>(IsBKW());
+    }
+
+    //! Return the maximum size of the stack during execution of this script.
+    std::optional<uint32_t> GetExecStackSize() const {
+        if (!ss.sat.valid) return {};
+        return ss.sat.exec + static_cast<int32_t>(IsBKW());
     }
 
     //! Check the maximum stack size for this script against the policy limit.
     bool CheckStackSize() const {
+        // Since in Tapscript there is no standardness limit on the script and witness sizes, we may run
+        // into the maximum stack size while executing the script. Make sure it doesn't happen.
+        if (IsTapscript(m_script_ctx)) {
+            if (const auto exec_ss = GetExecStackSize()) return exec_ss <= MAX_STACK_SIZE;
+            return true;
+        }
         if (const auto ss = GetStackSize()) return *ss <= MAX_STANDARD_P2WSH_STACK_ITEMS;
         return true;
     }
@@ -1235,6 +1528,9 @@ public:
     //! Return the expression type.
     Type GetType() const { return typ; }
 
+    //! Return the script context for this node.
+    MiniscriptContext GetMsCtx() const { return m_script_ctx; }
+
     //! Find an insane subnode which has no insane children. Nullptr if there is none.
     const Node* FindInsaneSub() const {
         return TreeEval<const Node*>([](const Node& node, Span<const Node*> subs) -> const Node* {
@@ -1259,6 +1555,7 @@ public:
                 case Fragment::PK_K:
                 case Fragment::PK_H:
                 case Fragment::MULTI:
+                case Fragment::MULTI_A:
                 case Fragment::AFTER:
                 case Fragment::OLDER:
                 case Fragment::HASH256:
@@ -1286,7 +1583,10 @@ public:
     }
 
     //! Check whether this node is valid at all.
-    bool IsValid() const { return !(GetType() == ""_mst) && ScriptSize() <= MAX_STANDARD_P2WSH_SCRIPT_SIZE; }
+    bool IsValid() const {
+        if (GetType() == ""_mst) return false;
+        return ScriptSize() <= internal::MaxScriptSize(m_script_ctx);
+    }
 
     //! Check whether this node is valid as a script on its own.
     bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; }
@@ -1328,20 +1628,32 @@ public:
     bool operator==(const Node<Key>& arg) const { return Compare(*this, arg) == 0; }
 
     // Constructors with various argument combinations, which bypass the duplicate key check.
-    Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : fragment(nt), k(val), data(std::move(arg)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
-    Node(internal::NoDupCheck, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : fragment(nt), k(val), data(std::move(arg)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
-    Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : fragment(nt), k(val), keys(std::move(key)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
-    Node(internal::NoDupCheck, Fragment nt, std::vector<Key> key, uint32_t val = 0) : fragment(nt), k(val), keys(std::move(key)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
-    Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : fragment(nt), k(val), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
-    Node(internal::NoDupCheck, Fragment nt, uint32_t val = 0) : fragment(nt), k(val), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+    Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0)
+        : fragment(nt), k(val), data(std::move(arg)), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+    Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0)
+        : fragment(nt), k(val), data(std::move(arg)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+    Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0)
+        : fragment(nt), k(val), keys(std::move(key)), m_script_ctx{script_ctx}, subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+    Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0)
+        : fragment(nt), k(val), keys(std::move(key)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+    Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0)
+        : fragment(nt), k(val), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+    Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, uint32_t val = 0)
+        : fragment(nt), k(val), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
 
     // Constructors with various argument combinations, which do perform the duplicate key check.
-    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), std::move(arg), val) { DuplicateKeyCheck(ctx); }
-    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(arg), val) { DuplicateKeyCheck(ctx);}
-    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), std::move(key), val) { DuplicateKeyCheck(ctx); }
-    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(key), val) { DuplicateKeyCheck(ctx); }
-    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), val) { DuplicateKeyCheck(ctx); }
-    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, val) { DuplicateKeyCheck(ctx); }
+    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0)
+        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(arg), val) { DuplicateKeyCheck(ctx); }
+    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0)
+        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(arg), val) { DuplicateKeyCheck(ctx);}
+    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0)
+        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(key), val) { DuplicateKeyCheck(ctx); }
+    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0)
+        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(key), val) { DuplicateKeyCheck(ctx); }
+    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0)
+        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), val) { DuplicateKeyCheck(ctx); }
+    template <typename Ctx> Node(const Ctx& ctx, Fragment nt, uint32_t val = 0)
+        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, val) { DuplicateKeyCheck(ctx); }
 };
 
 namespace internal {
@@ -1429,14 +1741,14 @@ std::optional<std::pair<std::vector<unsigned char>, int>> ParseHexStrEnd(Span<co
 
 /** BuildBack pops the last two elements off `constructed` and wraps them in the specified Fragment */
 template<typename Key>
-void BuildBack(Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
+void BuildBack(const MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
 {
     NodeRef<Key> child = std::move(constructed.back());
     constructed.pop_back();
     if (reverse) {
-        constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(child), std::move(constructed.back())));
+        constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(child), std::move(constructed.back())));
     } else {
-        constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(constructed.back()), std::move(child)));
+        constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(constructed.back()), std::move(child)));
     }
 }
 
@@ -1461,6 +1773,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
     //   (instead transforming another opcode into its VERIFY form). However, the v: wrapper has
     //   to be interleaved with other fragments to be valid, so this is not a concern.
     size_t script_size{1};
+    size_t max_size{internal::MaxScriptSize(ctx.MsContext())};
 
     // The two integers are used to hold state for thresh()
     std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
@@ -1468,8 +1781,43 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
 
     to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
 
+    // Parses a multi() or multi_a() from its string representation. Returns false on parsing error.
+    const auto parse_multi_exp = [&](Span<const char>& in, const bool is_multi_a) -> bool {
+        const auto max_keys{is_multi_a ? MAX_PUBKEYS_PER_MULTI_A : MAX_PUBKEYS_PER_MULTISIG};
+        const auto required_ctx{is_multi_a ? MiniscriptContext::TAPSCRIPT : MiniscriptContext::P2WSH};
+        if (ctx.MsContext() != required_ctx) return false;
+        // Get threshold
+        int next_comma = FindNextChar(in, ',');
+        if (next_comma < 1) return false;
+        int64_t k;
+        if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return false;
+        in = in.subspan(next_comma + 1);
+        // Get keys. It is compatible for both compressed and x-only keys.
+        std::vector<Key> keys;
+        while (next_comma != -1) {
+            next_comma = FindNextChar(in, ',');
+            int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
+            if (key_length < 1) return false;
+            auto key = ctx.FromString(in.begin(), in.begin() + key_length);
+            if (!key) return false;
+            keys.push_back(std::move(*key));
+            in = in.subspan(key_length + 1);
+        }
+        if (keys.size() < 1 || keys.size() > max_keys) return false;
+        if (k < 1 || k > (int64_t)keys.size()) return false;
+        if (is_multi_a) {
+            // (push + xonly-key + CHECKSIG[ADD]) * n + k + OP_NUMEQUAL(VERIFY), minus one.
+            script_size += (1 + 32 + 1) * keys.size() + BuildScript(k).size();
+            constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), k));
+        } else {
+            script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
+            constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), k));
+        }
+        return true;
+    };
+
     while (!to_parse.empty()) {
-        if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
+        if (script_size > max_size) return {};
 
         // Get the current context we are decoding within
         auto [cur_context, n, k] = to_parse.back();
@@ -1488,7 +1836,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
             // If there is no colon, this loop won't execute
             bool last_was_v{false};
             for (size_t j = 0; colon_index && j < *colon_index; ++j) {
-                if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
+                if (script_size > max_size) return {};
                 if (in[j] == 'a') {
                     script_size += 2;
                     to_parse.emplace_back(ParseContext::ALT, -1, -1);
@@ -1521,7 +1869,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
                 } else if (in[j] == 'l') {
                     // The l: wrapper is equivalent to or_i(0,X)
                     script_size += 4;
-                    constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
+                    constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0));
                     to_parse.emplace_back(ParseContext::OR_I, -1, -1);
                 } else {
                     return {};
@@ -1534,63 +1882,63 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
         }
         case ParseContext::EXPR: {
             if (Const("0", in)) {
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0));
             } else if (Const("1", in)) {
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1));
             } else if (Const("pk(", in)) {
                 auto res = ParseKeyEnd<Key, Ctx>(in, ctx);
                 if (!res) return {};
                 auto& [key, key_size] = *res;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))))));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(key))))));
                 in = in.subspan(key_size + 1);
-                script_size += 34;
+                script_size += IsTapscript(ctx.MsContext()) ? 33 : 34;
             } else if (Const("pkh(", in)) {
                 auto res = ParseKeyEnd<Key>(in, ctx);
                 if (!res) return {};
                 auto& [key, key_size] = *res;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))))));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(key))))));
                 in = in.subspan(key_size + 1);
                 script_size += 24;
             } else if (Const("pk_k(", in)) {
                 auto res = ParseKeyEnd<Key>(in, ctx);
                 if (!res) return {};
                 auto& [key, key_size] = *res;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(key))));
                 in = in.subspan(key_size + 1);
-                script_size += 33;
+                script_size += IsTapscript(ctx.MsContext()) ? 32 : 33;
             } else if (Const("pk_h(", in)) {
                 auto res = ParseKeyEnd<Key>(in, ctx);
                 if (!res) return {};
                 auto& [key, key_size] = *res;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(key))));
                 in = in.subspan(key_size + 1);
                 script_size += 23;
             } else if (Const("sha256(", in)) {
                 auto res = ParseHexStrEnd(in, 32, ctx);
                 if (!res) return {};
                 auto& [hash, hash_size] = *res;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, std::move(hash)));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, std::move(hash)));
                 in = in.subspan(hash_size + 1);
                 script_size += 38;
             } else if (Const("ripemd160(", in)) {
                 auto res = ParseHexStrEnd(in, 20, ctx);
                 if (!res) return {};
                 auto& [hash, hash_size] = *res;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, std::move(hash)));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, std::move(hash)));
                 in = in.subspan(hash_size + 1);
                 script_size += 26;
             } else if (Const("hash256(", in)) {
                 auto res = ParseHexStrEnd(in, 32, ctx);
                 if (!res) return {};
                 auto& [hash, hash_size] = *res;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, std::move(hash)));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, std::move(hash)));
                 in = in.subspan(hash_size + 1);
                 script_size += 38;
             } else if (Const("hash160(", in)) {
                 auto res = ParseHexStrEnd(in, 20, ctx);
                 if (!res) return {};
                 auto& [hash, hash_size] = *res;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, std::move(hash)));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, std::move(hash)));
                 in = in.subspan(hash_size + 1);
                 script_size += 26;
             } else if (Const("after(", in)) {
@@ -1599,7 +1947,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
                 int64_t num;
                 if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
                 if (num < 1 || num >= 0x80000000L) return {};
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, num));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, num));
                 in = in.subspan(arg_size + 1);
                 script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
             } else if (Const("older(", in)) {
@@ -1608,30 +1956,13 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
                 int64_t num;
                 if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
                 if (num < 1 || num >= 0x80000000L) return {};
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, num));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, num));
                 in = in.subspan(arg_size + 1);
                 script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
             } else if (Const("multi(", in)) {
-                // Get threshold
-                int next_comma = FindNextChar(in, ',');
-                if (next_comma < 1) return {};
-                if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
-                in = in.subspan(next_comma + 1);
-                // Get keys
-                std::vector<Key> keys;
-                while (next_comma != -1) {
-                    next_comma = FindNextChar(in, ',');
-                    int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
-                    if (key_length < 1) return {};
-                    auto key = ctx.FromString(in.begin(), in.begin() + key_length);
-                    if (!key) return {};
-                    keys.push_back(std::move(*key));
-                    in = in.subspan(key_length + 1);
-                }
-                if (keys.size() < 1 || keys.size() > 20) return {};
-                if (k < 1 || k > (int64_t)keys.size()) return {};
-                script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), k));
+                if (!parse_multi_exp(in, /* is_multi_a = */false)) return {};
+            } else if (Const("multi_a(", in)) {
+                if (!parse_multi_exp(in, /* is_multi_a = */true)) return {};
             } else if (Const("thresh(", in)) {
                 int next_comma = FindNextChar(in, ',');
                 if (next_comma < 1) return {};
@@ -1684,70 +2015,70 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
             break;
         }
         case ParseContext::ALT: {
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_A, Vector(std::move(constructed.back())));
             break;
         }
         case ParseContext::SWAP: {
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_S, Vector(std::move(constructed.back())));
             break;
         }
         case ParseContext::CHECK: {
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(std::move(constructed.back())));
             break;
         }
         case ParseContext::DUP_IF: {
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_D, Vector(std::move(constructed.back())));
             break;
         }
         case ParseContext::NON_ZERO: {
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_J, Vector(std::move(constructed.back())));
             break;
         }
         case ParseContext::ZERO_NOTEQUAL: {
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_N, Vector(std::move(constructed.back())));
             break;
         }
         case ParseContext::VERIFY: {
             script_size += (constructed.back()->GetType() << "x"_mst);
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_V, Vector(std::move(constructed.back())));
             break;
         }
         case ParseContext::WRAP_U: {
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0)));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0)));
             break;
         }
         case ParseContext::WRAP_T: {
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1)));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1)));
             break;
         }
         case ParseContext::AND_B: {
-            BuildBack(Fragment::AND_B, constructed);
+            BuildBack(ctx.MsContext(), Fragment::AND_B, constructed);
             break;
         }
         case ParseContext::AND_N: {
             auto mid = std::move(constructed.back());
             constructed.pop_back();
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), MakeNodeRef<Key>(ctx, Fragment::JUST_0)));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0)));
             break;
         }
         case ParseContext::AND_V: {
-            BuildBack(Fragment::AND_V, constructed);
+            BuildBack(ctx.MsContext(), Fragment::AND_V, constructed);
             break;
         }
         case ParseContext::OR_B: {
-            BuildBack(Fragment::OR_B, constructed);
+            BuildBack(ctx.MsContext(), Fragment::OR_B, constructed);
             break;
         }
         case ParseContext::OR_C: {
-            BuildBack(Fragment::OR_C, constructed);
+            BuildBack(ctx.MsContext(), Fragment::OR_C, constructed);
             break;
         }
         case ParseContext::OR_D: {
-            BuildBack(Fragment::OR_D, constructed);
+            BuildBack(ctx.MsContext(), Fragment::OR_D, constructed);
             break;
         }
         case ParseContext::OR_I: {
-            BuildBack(Fragment::OR_I, constructed);
+            BuildBack(ctx.MsContext(), Fragment::OR_I, constructed);
             break;
         }
         case ParseContext::ANDOR: {
@@ -1755,7 +2086,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
             constructed.pop_back();
             auto mid = std::move(constructed.back());
             constructed.pop_back();
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
             break;
         }
         case ParseContext::THRESH: {
@@ -1775,7 +2106,7 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
                     constructed.pop_back();
                 }
                 std::reverse(subs.begin(), subs.end());
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::THRESH, std::move(subs), k));
             } else {
                 return {};
             }
@@ -1808,8 +2139,8 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
  * Construct a vector with one element per opcode in the script, in reverse order.
  * Each element is a pair consisting of the opcode, as well as the data pushed by
  * the opcode (including OP_n), if any. OP_CHECKSIGVERIFY, OP_CHECKMULTISIGVERIFY,
- * and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG, OP_EQUAL
- * respectively, plus OP_VERIFY.
+ * OP_NUMEQUALVERIFY and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG,
+ * OP_EQUAL and OP_NUMEQUAL respectively, plus OP_VERIFY.
  */
 std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script);
 
@@ -1911,27 +2242,27 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
             // Constants
             if (in[0].first == OP_1) {
                 ++in;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1));
                 break;
             }
             if (in[0].first == OP_0) {
                 ++in;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0));
                 break;
             }
             // Public keys
-            if (in[0].second.size() == 33) {
+            if (in[0].second.size() == 33 || in[0].second.size() == 32) {
                 auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end());
                 if (!key) return {};
                 ++in;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(*key))));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key))));
                 break;
             }
             if (last - in >= 5 && in[0].first == OP_VERIFY && in[1].first == OP_EQUAL && in[3].first == OP_HASH160 && in[4].first == OP_DUP && in[2].second.size() == 20) {
                 auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end());
                 if (!key) return {};
                 in += 5;
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(*key))));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key))));
                 break;
             }
             // Time locks
@@ -1939,37 +2270,38 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
             if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && (num = ParseScriptNumber(in[1]))) {
                 in += 2;
                 if (*num < 1 || *num > 0x7FFFFFFFL) return {};
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, *num));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, *num));
                 break;
             }
             if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && (num = ParseScriptNumber(in[1]))) {
                 in += 2;
                 if (num < 1 || num > 0x7FFFFFFFL) return {};
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, *num));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, *num));
                 break;
             }
             // Hashes
             if (last - in >= 7 && in[0].first == OP_EQUAL && in[3].first == OP_VERIFY && in[4].first == OP_EQUAL && (num = ParseScriptNumber(in[5])) && num == 32 && in[6].first == OP_SIZE) {
                 if (in[2].first == OP_SHA256 && in[1].second.size() == 32) {
-                    constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, in[1].second));
+                    constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, in[1].second));
                     in += 7;
                     break;
                 } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) {
-                    constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, in[1].second));
+                    constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, in[1].second));
                     in += 7;
                     break;
                 } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) {
-                    constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, in[1].second));
+                    constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, in[1].second));
                     in += 7;
                     break;
                 } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) {
-                    constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, in[1].second));
+                    constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, in[1].second));
                     in += 7;
                     break;
                 }
             }
             // Multi
             if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) {
+                if (IsTapscript(ctx.MsContext())) return {};
                 std::vector<Key> keys;
                 const auto n = ParseScriptNumber(in[1]);
                 if (!n || last - in < 3 + *n) return {};
@@ -1984,7 +2316,37 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
                 if (!k || *k < 1 || *k > *n) return {};
                 in += 3 + *n;
                 std::reverse(keys.begin(), keys.end());
-                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), *k));
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), *k));
+                break;
+            }
+            // Tapscript's equivalent of multi
+            if (last - in >= 4 && in[0].first == OP_NUMEQUAL) {
+                if (!IsTapscript(ctx.MsContext())) return {};
+                // The necessary threshold of signatures.
+                const auto k = ParseScriptNumber(in[1]);
+                if (!k) return {};
+                if (*k < 1 || *k > MAX_PUBKEYS_PER_MULTI_A) return {};
+                if (last - in < 2 + *k * 2) return {};
+                std::vector<Key> keys;
+                keys.reserve(*k);
+                // Walk through the expected (pubkey, CHECKSIG[ADD]) pairs.
+                for (int pos = 2;; pos += 2) {
+                    if (last - in < pos + 2) return {};
+                    // Make sure it's indeed an x-only pubkey and a CHECKSIG[ADD], then parse the key.
+                    if (in[pos].first != OP_CHECKSIGADD && in[pos].first != OP_CHECKSIG) return {};
+                    if (in[pos + 1].second.size() != 32) return {};
+                    auto key = ctx.FromPKBytes(in[pos + 1].second.begin(), in[pos + 1].second.end());
+                    if (!key) return {};
+                    keys.push_back(std::move(*key));
+                    // Make sure early we don't parse an arbitrary large expression.
+                    if (keys.size() > MAX_PUBKEYS_PER_MULTI_A) return {};
+                    // OP_CHECKSIG means it was the last one to parse.
+                    if (in[pos].first == OP_CHECKSIG) break;
+                }
+                if (keys.size() < (size_t)*k) return {};
+                in += 2 + keys.size() * 2;
+                std::reverse(keys.begin(), keys.end());
+                constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), *k));
                 break;
             }
             /** In the following wrappers, we only need to push SINGLE_BKV_EXPR rather
@@ -2079,63 +2441,63 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
         case DecodeContext::SWAP: {
             if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {};
             ++in;
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_S, Vector(std::move(constructed.back())));
             break;
         }
         case DecodeContext::ALT: {
             if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {};
             ++in;
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_A, Vector(std::move(constructed.back())));
             break;
         }
         case DecodeContext::CHECK: {
             if (constructed.empty()) return {};
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(std::move(constructed.back())));
             break;
         }
         case DecodeContext::DUP_IF: {
             if (constructed.empty()) return {};
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_D, Vector(std::move(constructed.back())));
             break;
         }
         case DecodeContext::VERIFY: {
             if (constructed.empty()) return {};
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_V, Vector(std::move(constructed.back())));
             break;
         }
         case DecodeContext::NON_ZERO: {
             if (constructed.empty()) return {};
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_J, Vector(std::move(constructed.back())));
             break;
         }
         case DecodeContext::ZERO_NOTEQUAL: {
             if (constructed.empty()) return {};
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_N, Vector(std::move(constructed.back())));
             break;
         }
         case DecodeContext::AND_V: {
             if (constructed.size() < 2) return {};
-            BuildBack(Fragment::AND_V, constructed, /*reverse=*/true);
+            BuildBack(ctx.MsContext(), Fragment::AND_V, constructed, /*reverse=*/true);
             break;
         }
         case DecodeContext::AND_B: {
             if (constructed.size() < 2) return {};
-            BuildBack(Fragment::AND_B, constructed, /*reverse=*/true);
+            BuildBack(ctx.MsContext(), Fragment::AND_B, constructed, /*reverse=*/true);
             break;
         }
         case DecodeContext::OR_B: {
             if (constructed.size() < 2) return {};
-            BuildBack(Fragment::OR_B, constructed, /*reverse=*/true);
+            BuildBack(ctx.MsContext(), Fragment::OR_B, constructed, /*reverse=*/true);
             break;
         }
         case DecodeContext::OR_C: {
             if (constructed.size() < 2) return {};
-            BuildBack(Fragment::OR_C, constructed, /*reverse=*/true);
+            BuildBack(ctx.MsContext(), Fragment::OR_C, constructed, /*reverse=*/true);
             break;
         }
         case DecodeContext::OR_D: {
             if (constructed.size() < 2) return {};
-            BuildBack(Fragment::OR_D, constructed, /*reverse=*/true);
+            BuildBack(ctx.MsContext(), Fragment::OR_D, constructed, /*reverse=*/true);
             break;
         }
         case DecodeContext::ANDOR: {
@@ -2145,7 +2507,7 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
             NodeRef<Key> right = std::move(constructed.back());
             constructed.pop_back();
             NodeRef<Key> mid = std::move(constructed.back());
-            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
+            constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
             break;
         }
         case DecodeContext::THRESH_W: {
@@ -2169,7 +2531,7 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
                 constructed.pop_back();
                 subs.push_back(std::move(sub));
             }
-            constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
+            constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::THRESH, std::move(subs), k));
             break;
         }
         case DecodeContext::ENDIF: {
@@ -2219,7 +2581,7 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
             if (in >= last) return {};
             if (in[0].first == OP_IF) {
                 ++in;
-                BuildBack(Fragment::OR_I, constructed, /*reverse=*/true);
+                BuildBack(ctx.MsContext(), Fragment::OR_I, constructed, /*reverse=*/true);
             } else if (in[0].first == OP_NOTIF) {
                 ++in;
                 to_parse.emplace_back(DecodeContext::ANDOR, -1, -1);
@@ -2252,7 +2614,7 @@ template<typename Ctx>
 inline NodeRef<typename Ctx::Key> FromScript(const CScript& script, const Ctx& ctx) {
     using namespace internal;
     // A too large Script is necessarily invalid, don't bother parsing it.
-    if (script.size() > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
+    if (script.size() > MaxScriptSize(ctx.MsContext())) return {};
     auto decomposed = DecomposeScript(script);
     if (!decomposed) return {};
     auto it = decomposed->begin();
diff --git a/src/script/sign.cpp b/src/script/sign.cpp
index 92b7ad50b5..248ad780c3 100644
--- a/src/script/sign.cpp
+++ b/src/script/sign.cpp
@@ -114,12 +114,17 @@ static bool GetPubKey(const SigningProvider& provider, const SignatureData& sigd
         pubkey = it->second.first;
         return true;
     }
-    // Look for pubkey in pubkey list
+    // Look for pubkey in pubkey lists
     const auto& pk_it = sigdata.misc_pubkeys.find(address);
     if (pk_it != sigdata.misc_pubkeys.end()) {
         pubkey = pk_it->second.first;
         return true;
     }
+    const auto& tap_pk_it = sigdata.tap_pubkeys.find(address);
+    if (tap_pk_it != sigdata.tap_pubkeys.end()) {
+        pubkey = tap_pk_it->second.GetEvenCorrespondingCPubKey();
+        return true;
+    }
     // Query the underlying provider
     return provider.GetPubKey(address, pubkey);
 }
@@ -171,49 +176,158 @@ static bool CreateTaprootScriptSig(const BaseSignatureCreator& creator, Signatur
     return false;
 }
 
-static bool SignTaprootScript(const SigningProvider& provider, const BaseSignatureCreator& creator, SignatureData& sigdata, int leaf_version, Span<const unsigned char> script_bytes, std::vector<valtype>& result)
+template<typename M, typename K, typename V>
+miniscript::Availability MsLookupHelper(const M& map, const K& key, V& value)
 {
-    // Only BIP342 tapscript signing is supported for now.
-    if (leaf_version != TAPROOT_LEAF_TAPSCRIPT) return false;
-    SigVersion sigversion = SigVersion::TAPSCRIPT;
+    auto it = map.find(key);
+    if (it != map.end()) {
+        value = it->second;
+        return miniscript::Availability::YES;
+    }
+    return miniscript::Availability::NO;
+}
 
-    uint256 leaf_hash = ComputeTapleafHash(leaf_version, script_bytes);
-    CScript script = CScript(script_bytes.begin(), script_bytes.end());
+/**
+ * Context for solving a Miniscript.
+ * If enough material (access to keys, hash preimages, ..) is given, produces a valid satisfaction.
+ */
+template<typename Pk>
+struct Satisfier {
+    using Key = Pk;
 
-    // <xonly pubkey> OP_CHECKSIG
-    if (script.size() == 34 && script[33] == OP_CHECKSIG && script[0] == 0x20) {
-        XOnlyPubKey pubkey{Span{script}.subspan(1, 32)};
-        std::vector<unsigned char> sig;
-        if (CreateTaprootScriptSig(creator, sigdata, provider, sig, pubkey, leaf_hash, sigversion)) {
-            result = Vector(std::move(sig));
-            return true;
-        }
-        return false;
+    const SigningProvider& m_provider;
+    SignatureData& m_sig_data;
+    const BaseSignatureCreator& m_creator;
+    const CScript& m_witness_script;
+    //! The context of the script we are satisfying (either P2WSH or Tapscript).
+    const miniscript::MiniscriptContext m_script_ctx;
+
+    explicit Satisfier(const SigningProvider& provider LIFETIMEBOUND, SignatureData& sig_data LIFETIMEBOUND,
+                       const BaseSignatureCreator& creator LIFETIMEBOUND,
+                       const CScript& witscript LIFETIMEBOUND,
+                       miniscript::MiniscriptContext script_ctx) : m_provider(provider),
+                                                                   m_sig_data(sig_data),
+                                                                   m_creator(creator),
+                                                                   m_witness_script(witscript),
+                                                                   m_script_ctx(script_ctx) {}
+
+    static bool KeyCompare(const Key& a, const Key& b) {
+        return a < b;
     }
 
-    // multi_a scripts (<key> OP_CHECKSIG <key> OP_CHECKSIGADD <key> OP_CHECKSIGADD <k> OP_NUMEQUAL)
-    if (auto match = MatchMultiA(script)) {
-        std::vector<std::vector<unsigned char>> sigs;
-        int good_sigs = 0;
-        for (size_t i = 0; i < match->second.size(); ++i) {
-            XOnlyPubKey pubkey{*(match->second.rbegin() + i)};
-            std::vector<unsigned char> sig;
-            bool good_sig = CreateTaprootScriptSig(creator, sigdata, provider, sig, pubkey, leaf_hash, sigversion);
-            if (good_sig && good_sigs < match->first) {
-                ++good_sigs;
-                sigs.push_back(std::move(sig));
-            } else {
-                sigs.emplace_back();
-            }
+    //! Get a CPubKey from a key hash. Note the key hash may be of an xonly pubkey.
+    template<typename I>
+    std::optional<CPubKey> CPubFromPKHBytes(I first, I last) const {
+        assert(last - first == 20);
+        CPubKey pubkey;
+        CKeyID key_id;
+        std::copy(first, last, key_id.begin());
+        if (GetPubKey(m_provider, m_sig_data, key_id, pubkey)) return pubkey;
+        m_sig_data.missing_pubkeys.push_back(key_id);
+        return {};
+    }
+
+    //! Conversion to raw public key.
+    std::vector<unsigned char> ToPKBytes(const Key& key) const { return {key.begin(), key.end()}; }
+
+    //! Time lock satisfactions.
+    bool CheckAfter(uint32_t value) const { return m_creator.Checker().CheckLockTime(CScriptNum(value)); }
+    bool CheckOlder(uint32_t value) const { return m_creator.Checker().CheckSequence(CScriptNum(value)); }
+
+    //! Hash preimage satisfactions.
+    miniscript::Availability SatSHA256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
+        return MsLookupHelper(m_sig_data.sha256_preimages, hash, preimage);
+    }
+    miniscript::Availability SatRIPEMD160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
+        return MsLookupHelper(m_sig_data.ripemd160_preimages, hash, preimage);
+    }
+    miniscript::Availability SatHASH256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
+        return MsLookupHelper(m_sig_data.hash256_preimages, hash, preimage);
+    }
+    miniscript::Availability SatHASH160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
+        return MsLookupHelper(m_sig_data.hash160_preimages, hash, preimage);
+    }
+
+    miniscript::MiniscriptContext MsContext() const {
+        return m_script_ctx;
+    }
+};
+
+/** Miniscript satisfier specific to P2WSH context. */
+struct WshSatisfier: Satisfier<CPubKey> {
+    explicit WshSatisfier(const SigningProvider& provider LIFETIMEBOUND, SignatureData& sig_data LIFETIMEBOUND,
+                          const BaseSignatureCreator& creator LIFETIMEBOUND, const CScript& witscript LIFETIMEBOUND)
+                          : Satisfier(provider, sig_data, creator, witscript, miniscript::MiniscriptContext::P2WSH) {}
+
+    //! Conversion from a raw compressed public key.
+    template <typename I>
+    std::optional<CPubKey> FromPKBytes(I first, I last) const {
+        CPubKey pubkey{first, last};
+        if (pubkey.IsValid()) return pubkey;
+        return {};
+    }
+
+    //! Conversion from a raw compressed public key hash.
+    template<typename I>
+    std::optional<CPubKey> FromPKHBytes(I first, I last) const {
+        return Satisfier::CPubFromPKHBytes(first, last);
+    }
+
+    //! Satisfy an ECDSA signature check.
+    miniscript::Availability Sign(const CPubKey& key, std::vector<unsigned char>& sig) const {
+        if (CreateSig(m_creator, m_sig_data, m_provider, sig, key, m_witness_script, SigVersion::WITNESS_V0)) {
+            return miniscript::Availability::YES;
         }
-        if (good_sigs == match->first) {
-            result = std::move(sigs);
-            return true;
+        return miniscript::Availability::NO;
+    }
+};
+
+/** Miniscript satisfier specific to Tapscript context. */
+struct TapSatisfier: Satisfier<XOnlyPubKey> {
+    const uint256& m_leaf_hash;
+
+    explicit TapSatisfier(const SigningProvider& provider LIFETIMEBOUND, SignatureData& sig_data LIFETIMEBOUND,
+                          const BaseSignatureCreator& creator LIFETIMEBOUND, const CScript& script LIFETIMEBOUND,
+                          const uint256& leaf_hash LIFETIMEBOUND)
+                          : Satisfier(provider, sig_data, creator, script, miniscript::MiniscriptContext::TAPSCRIPT),
+                            m_leaf_hash(leaf_hash) {}
+
+    //! Conversion from a raw xonly public key.
+    template <typename I>
+    std::optional<XOnlyPubKey> FromPKBytes(I first, I last) const {
+        CHECK_NONFATAL(last - first == 32);
+        XOnlyPubKey pubkey;
+        std::copy(first, last, pubkey.begin());
+        return pubkey;
+    }
+
+    //! Conversion from a raw xonly public key hash.
+    template<typename I>
+    std::optional<XOnlyPubKey> FromPKHBytes(I first, I last) const {
+        if (auto pubkey = Satisfier::CPubFromPKHBytes(first, last)) return XOnlyPubKey{*pubkey};
+        return {};
+    }
+
+    //! Satisfy a BIP340 signature check.
+    miniscript::Availability Sign(const XOnlyPubKey& key, std::vector<unsigned char>& sig) const {
+        if (CreateTaprootScriptSig(m_creator, m_sig_data, m_provider, sig, key, m_leaf_hash, SigVersion::TAPSCRIPT)) {
+            return miniscript::Availability::YES;
         }
-        return false;
+        return miniscript::Availability::NO;
     }
+};
 
-    return false;
+static bool SignTaprootScript(const SigningProvider& provider, const BaseSignatureCreator& creator, SignatureData& sigdata, int leaf_version, Span<const unsigned char> script_bytes, std::vector<valtype>& result)
+{
+    // Only BIP342 tapscript signing is supported for now.
+    if (leaf_version != TAPROOT_LEAF_TAPSCRIPT) return false;
+
+    uint256 leaf_hash = ComputeTapleafHash(leaf_version, script_bytes);
+    CScript script = CScript(script_bytes.begin(), script_bytes.end());
+
+    TapSatisfier ms_satisfier{provider, sigdata, creator, script, leaf_hash};
+    const auto ms = miniscript::FromScript(script, ms_satisfier);
+    return ms && ms->Satisfy(ms_satisfier, result) == miniscript::Availability::YES;
 }
 
 static bool SignTaproot(const SigningProvider& provider, const BaseSignatureCreator& creator, const WitnessV1Taproot& output, SignatureData& sigdata, std::vector<valtype>& result)
@@ -382,92 +496,6 @@ static CScript PushAll(const std::vector<valtype>& values)
     return result;
 }
 
-template<typename M, typename K, typename V>
-miniscript::Availability MsLookupHelper(const M& map, const K& key, V& value)
-{
-    auto it = map.find(key);
-    if (it != map.end()) {
-        value = it->second;
-        return miniscript::Availability::YES;
-    }
-    return miniscript::Availability::NO;
-}
-
-/**
- * Context for solving a Miniscript.
- * If enough material (access to keys, hash preimages, ..) is given, produces a valid satisfaction.
- */
-struct Satisfier {
-    typedef CPubKey Key;
-
-    const SigningProvider& m_provider;
-    SignatureData& m_sig_data;
-    const BaseSignatureCreator& m_creator;
-    const CScript& m_witness_script;
-
-    explicit Satisfier(const SigningProvider& provider LIFETIMEBOUND, SignatureData& sig_data LIFETIMEBOUND,
-                       const BaseSignatureCreator& creator LIFETIMEBOUND,
-                       const CScript& witscript LIFETIMEBOUND) : m_provider(provider),
-                                                                 m_sig_data(sig_data),
-                                                                 m_creator(creator),
-                                                                 m_witness_script(witscript) {}
-
-    static bool KeyCompare(const Key& a, const Key& b) {
-        return a < b;
-    }
-
-    //! Conversion from a raw public key.
-    template <typename I>
-    std::optional<Key> FromPKBytes(I first, I last) const
-    {
-        Key pubkey{first, last};
-        if (pubkey.IsValid()) return pubkey;
-        return {};
-    }
-
-    //! Conversion from a raw public key hash.
-    template<typename I>
-    std::optional<Key> FromPKHBytes(I first, I last) const {
-        assert(last - first == 20);
-        Key pubkey;
-        CKeyID key_id;
-        std::copy(first, last, key_id.begin());
-        if (GetPubKey(m_provider, m_sig_data, key_id, pubkey)) return pubkey;
-        m_sig_data.missing_pubkeys.push_back(key_id);
-        return {};
-    }
-
-    //! Conversion to raw public key.
-    std::vector<unsigned char> ToPKBytes(const CPubKey& key) const { return {key.begin(), key.end()}; }
-
-    //! Satisfy a signature check.
-    miniscript::Availability Sign(const CPubKey& key, std::vector<unsigned char>& sig) const {
-        if (CreateSig(m_creator, m_sig_data, m_provider, sig, key, m_witness_script, SigVersion::WITNESS_V0)) {
-            return miniscript::Availability::YES;
-        }
-        return miniscript::Availability::NO;
-    }
-
-    //! Time lock satisfactions.
-    bool CheckAfter(uint32_t value) const { return m_creator.Checker().CheckLockTime(CScriptNum(value)); }
-    bool CheckOlder(uint32_t value) const { return m_creator.Checker().CheckSequence(CScriptNum(value)); }
-
-
-    //! Hash preimage satisfactions.
-    miniscript::Availability SatSHA256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
-        return MsLookupHelper(m_sig_data.sha256_preimages, hash, preimage);
-    }
-    miniscript::Availability SatRIPEMD160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
-        return MsLookupHelper(m_sig_data.ripemd160_preimages, hash, preimage);
-    }
-    miniscript::Availability SatHASH256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
-        return MsLookupHelper(m_sig_data.hash256_preimages, hash, preimage);
-    }
-    miniscript::Availability SatHASH160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
-        return MsLookupHelper(m_sig_data.hash160_preimages, hash, preimage);
-    }
-};
-
 bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreator& creator, const CScript& fromPubKey, SignatureData& sigdata)
 {
     if (sigdata.complete) return true;
@@ -512,7 +540,7 @@ bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreato
         // isn't fully solved. For instance the CHECKMULTISIG satisfaction in SignStep() pushes partial signatures
         // and the extractor relies on this behaviour to combine witnesses.
         if (!solved && result.empty()) {
-            Satisfier ms_satisfier{provider, sigdata, creator, witnessscript};
+            WshSatisfier ms_satisfier{provider, sigdata, creator, witnessscript};
             const auto ms = miniscript::FromScript(witnessscript, ms_satisfier);
             solved = ms && ms->Satisfy(ms_satisfier, result) == miniscript::Availability::YES;
         }
diff --git a/src/script/sign.h b/src/script/sign.h
index 4d7dade44e..ace2ba7856 100644
--- a/src/script/sign.h
+++ b/src/script/sign.h
@@ -79,6 +79,7 @@ struct SignatureData {
     std::vector<unsigned char> taproot_key_path_sig; /// Schnorr signature for key path spending
     std::map<std::pair<XOnlyPubKey, uint256>, std::vector<unsigned char>> taproot_script_sigs; ///< (Partial) schnorr signatures, indexed by XOnlyPubKey and leaf_hash.
     std::map<XOnlyPubKey, std::pair<std::set<uint256>, KeyOriginInfo>> taproot_misc_pubkeys; ///< Miscellaneous Taproot pubkeys involved in this input along with their leaf script hashes and key origin data. Also includes the Taproot internal key (may have no leaf script hashes).
+    std::map<CKeyID, XOnlyPubKey> tap_pubkeys; ///< Misc Taproot pubkeys involved in this input, by hash. (Equivalent of misc_pubkeys but for Taproot.)
     std::vector<CKeyID> missing_pubkeys; ///< KeyIDs of pubkeys which could not be found
     std::vector<CKeyID> missing_sigs; ///< KeyIDs of pubkeys for signatures which could not be found
     uint160 missing_redeem_script; ///< ScriptID of the missing redeemScript (if any)