miniscript: introduce a multi_a fragment

It is the equivalent of multi() but for Tapscript, using CHECKSIGADD
instead of CHECKMULTISIG.

It shares the same properties as multi() but for 'n', since a threshold
multi_a() may have an empty vector as the top element of its
satisfaction. It could also have the 'o' property when it only has a
single key, but in this case a 'pk()' is always preferable anyways.

3 files changed, 147 insertions, 29 deletions

diff --git a/src/script/miniscript.cpp b/src/script/miniscript.cpp
index 28c79eab30..82f65e5dde 100644
--- a/src/script/miniscript.cpp
+++ b/src/script/miniscript.cpp
@@ -45,7 +45,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);
@@ -69,7 +69,9 @@ 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);
+    } else if (fragment == Fragment::MULTI_A) {
+        assert(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTI_A);
     } else {
         assert(n_keys == 0);
     }
@@ -212,6 +214,7 @@ Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Ty
                 ((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_A: return "Budemsk"_mst;
         case Fragment::THRESH: {
             bool all_e = true;
             bool all_m = true;
@@ -260,6 +263,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:
@@ -373,9 +377,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 95ff10be2a..bb75f3e52e 100644
--- a/src/script/miniscript.h
+++ b/src/script/miniscript.h
@@ -45,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.
@@ -217,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)
@@ -637,6 +638,14 @@ public:
                     }
                     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) {
@@ -740,6 +749,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) {
@@ -805,6 +824,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};
@@ -857,6 +877,7 @@ private:
             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::MULTI_A: return {keys.size(), keys.size()};
             case Fragment::WRAP_A:
             case Fragment::WRAP_N:
             case Fragment::WRAP_S: return subs[0]->ss;
@@ -907,6 +928,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:
@@ -947,6 +969,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.
@@ -1281,6 +1331,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:
@@ -1502,6 +1553,41 @@ 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 {};
 
@@ -1646,27 +1732,9 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
                 in = in.subspan(arg_size + 1);
                 script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
             } else if (Const("multi(", in)) {
-                if (IsTapscript(ctx.MsContext())) return {};
-                // 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{}, ctx.MsContext(), 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 {};
@@ -1843,8 +1911,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);
 
@@ -2023,6 +2091,36 @@ inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
                 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
              * than BKV_EXPR, because and_v commutes with these wrappers. For example,
              * c:and_v(X,Y) produces the same script as and_v(X,c:Y). */
diff --git a/src/test/fuzz/miniscript.cpp b/src/test/fuzz/miniscript.cpp
index d85ed707bd..1099e2a00f 100644
--- a/src/test/fuzz/miniscript.cpp
+++ b/src/test/fuzz/miniscript.cpp
@@ -514,6 +514,9 @@ struct SmartInfo
 
             // Based on the fragment, determine #subs/data/k/keys to pass to ComputeType. */
             switch (frag) {
+                case Fragment::MULTI_A:
+                    // TODO: Tapscript support.
+                    assert(false);
                 case Fragment::PK_K:
                 case Fragment::PK_H:
                     n_keys = 1;
@@ -703,6 +706,9 @@ std::optional<NodeInfo> ConsumeNodeSmart(FuzzedDataProvider& provider, Type type
 
     // Based on the fragment the recipe uses, fill in other data (k, keys, data).
     switch (frag) {
+        case Fragment::MULTI_A:
+            // TODO: Tapscript support.
+            assert(false);
         case Fragment::PK_K:
         case Fragment::PK_H:
             return {{frag, ConsumePubKey(provider)}};
@@ -793,6 +799,9 @@ NodeRef GenNode(F ConsumeNode, Type root_type, bool strict_valid = false) {
             scriptsize += miniscript::internal::ComputeScriptLen(node_info->fragment, ""_mst, node_info->subtypes.size(), node_info->k, node_info->subtypes.size(), node_info->keys.size()) - 1;
             if (scriptsize > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
             switch (node_info->fragment) {
+            case Fragment::MULTI_A:
+                // TODO: Tapscript support.
+                assert(false);
             case Fragment::JUST_0:
             case Fragment::JUST_1:
                 break;
@@ -1019,6 +1028,9 @@ void TestNode(const NodeRef& node, FuzzedDataProvider& provider)
     // satisfaction will also match the expected policy.
     bool satisfiable = node->IsSatisfiable([](const Node& node) -> bool {
         switch (node.fragment) {
+        case Fragment::MULTI_A:
+            // TODO: Tapscript support.
+            assert(false);
         case Fragment::PK_K:
         case Fragment::PK_H: {
             auto it = TEST_DATA.dummy_sigs.find(node.keys[0]);