/tmp/bitcoin/src/script/miniscript.cpp

Source
// Copyright (c) 2019-present The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <limits>
#include <vector>

#include <primitives/transaction.h>
#include <script/miniscript.h>
#include <script/script.h>
#include <script/solver.h>
#include <span.h>
#include <util/check.h>
#include <util/vector.h>

namespace miniscript {
namespace internal {

Type SanitizeType(Type e) {
    int num_types = (e << "K"_mst) + (e << "V"_mst) + (e << "B"_mst) + (e << "W"_mst);
    if (num_types == 0) return ""_mst; // No valid type, don't care about the rest
    CHECK_NONFATAL(num_types == 1); // K, V, B, W all conflict with each other
    CHECK_NONFATAL(!(e << "z"_mst) || !(e << "o"_mst)); // z conflicts with o
    CHECK_NONFATAL(!(e << "n"_mst) || !(e << "z"_mst)); // n conflicts with z
    CHECK_NONFATAL(!(e << "n"_mst) || !(e << "W"_mst)); // n conflicts with W
    CHECK_NONFATAL(!(e << "V"_mst) || !(e << "d"_mst)); // V conflicts with d
    CHECK_NONFATAL(!(e << "K"_mst) ||  (e << "u"_mst)); // K implies u
    CHECK_NONFATAL(!(e << "V"_mst) || !(e << "u"_mst)); // V conflicts with u
    CHECK_NONFATAL(!(e << "e"_mst) || !(e << "f"_mst)); // e conflicts with f
    CHECK_NONFATAL(!(e << "e"_mst) ||  (e << "d"_mst)); // e implies d
    CHECK_NONFATAL(!(e << "V"_mst) || !(e << "e"_mst)); // V conflicts with e
    CHECK_NONFATAL(!(e << "d"_mst) || !(e << "f"_mst)); // d conflicts with f
    CHECK_NONFATAL(!(e << "V"_mst) ||  (e << "f"_mst)); // V implies f
    CHECK_NONFATAL(!(e << "K"_mst) ||  (e << "s"_mst)); // K implies s
    CHECK_NONFATAL(!(e << "z"_mst) ||  (e << "m"_mst)); // z implies m
    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, MiniscriptContext ms_ctx) {
    // Sanity check on data
    if (fragment == Fragment::SHA256 || fragment == Fragment::HASH256) {
        CHECK_NONFATAL(data_size == 32);
    } else if (fragment == Fragment::RIPEMD160 || fragment == Fragment::HASH160) {
        CHECK_NONFATAL(data_size == 20);
    } else {
        CHECK_NONFATAL(data_size == 0);
    }
    // Sanity check on k
    if (fragment == Fragment::OLDER || fragment == Fragment::AFTER) {
        CHECK_NONFATAL(k >= 1 && k < 0x80000000UL);
    } else if (fragment == Fragment::MULTI || fragment == Fragment::MULTI_A) {
        CHECK_NONFATAL(k >= 1 && k <= n_keys);
    } else if (fragment == Fragment::THRESH) {
        CHECK_NONFATAL(k >= 1 && k <= n_subs);
    } else {
        CHECK_NONFATAL(k == 0);
    }
    // Sanity check on subs
    if (fragment == Fragment::AND_V || fragment == Fragment::AND_B || fragment == Fragment::OR_B ||
        fragment == Fragment::OR_C || fragment == Fragment::OR_I || fragment == Fragment::OR_D) {
        CHECK_NONFATAL(n_subs == 2);
    } else if (fragment == Fragment::ANDOR) {
        CHECK_NONFATAL(n_subs == 3);
    } else if (fragment == Fragment::WRAP_A || fragment == Fragment::WRAP_S || fragment == Fragment::WRAP_C ||
               fragment == Fragment::WRAP_D || fragment == Fragment::WRAP_V || fragment == Fragment::WRAP_J ||
               fragment == Fragment::WRAP_N) {
        CHECK_NONFATAL(n_subs == 1);
    } else if (fragment != Fragment::THRESH) {
        CHECK_NONFATAL(n_subs == 0);
    }
    // Sanity check on keys
    if (fragment == Fragment::PK_K || fragment == Fragment::PK_H) {
        CHECK_NONFATAL(n_keys == 1);
    } else if (fragment == Fragment::MULTI) {
        CHECK_NONFATAL(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTISIG);
        CHECK_NONFATAL(!IsTapscript(ms_ctx));
    } else if (fragment == Fragment::MULTI_A) {
        CHECK_NONFATAL(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTI_A);
        CHECK_NONFATAL(IsTapscript(ms_ctx));
    } else {
        CHECK_NONFATAL(n_keys == 0);
    }

    // Below is the per-fragment logic for computing the expression types.
    // It heavily relies on Type's << operator (where "X << a_mst" means
    // "X has all properties listed in a").
    switch (fragment) {
        case Fragment::PK_K: return "Konudemsxk"_mst;
        case Fragment::PK_H: return "Knudemsxk"_mst;
        case Fragment::OLDER: return
            "g"_mst.If(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) |
            "h"_mst.If(!(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG)) |
            "Bzfmxk"_mst;
        case Fragment::AFTER: return
            "i"_mst.If(k >= LOCKTIME_THRESHOLD) |
            "j"_mst.If(k < LOCKTIME_THRESHOLD) |
            "Bzfmxk"_mst;
        case Fragment::SHA256: return "Bonudmk"_mst;
        case Fragment::RIPEMD160: return "Bonudmk"_mst;
        case Fragment::HASH256: return "Bonudmk"_mst;
        case Fragment::HASH160: return "Bonudmk"_mst;
        case Fragment::JUST_1: return "Bzufmxk"_mst;
        case Fragment::JUST_0: return "Bzudemsxk"_mst;
        case Fragment::WRAP_A: return
            "W"_mst.If(x << "B"_mst) | // W=B_x
            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
            (x & "udfems"_mst) | // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
            "x"_mst; // x
        case Fragment::WRAP_S: return
            "W"_mst.If(x << "Bo"_mst) | // W=B_x*o_x
            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
            (x & "udfemsx"_mst); // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x, x=x_x
        case Fragment::WRAP_C: return
            "B"_mst.If(x << "K"_mst) | // B=K_x
            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
            (x & "ondfem"_mst) | // o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x
            "us"_mst; // u, s
        case Fragment::WRAP_D: return
            "B"_mst.If(x << "Vz"_mst) | // B=V_x*z_x
            "o"_mst.If(x << "z"_mst) | // o=z_x
            "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 '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
            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
            (x & "zonms"_mst) | // z=z_x, o=o_x, n=n_x, m=m_x, s=s_x
            "fx"_mst; // f, x
        case Fragment::WRAP_J: return
            "B"_mst.If(x << "Bn"_mst) | // B=B_x*n_x
            "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 & "oums"_mst) | // o=o_x, u=u_x, m=m_x, s=s_x
            "ndx"_mst; // n, d, x
        case Fragment::WRAP_N: return
            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
            (x & "Bzondfems"_mst) | // B=B_x, z=z_x, o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
            "ux"_mst; // u, x
        case Fragment::AND_V: return
            (y & "KVB"_mst).If(x << "V"_mst) | // B=V_x*B_y, V=V_x*V_y, K=V_x*K_y
            (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
            ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
            (x & y & "mz"_mst) | // m=m_x*m_y, z=z_x*z_y
            ((x | y) & "s"_mst) | // s=s_x+s_y
            "f"_mst.If((y << "f"_mst) || (x << "s"_mst)) | // f=f_y+s_x
            (y & "ux"_mst) | // u=u_y, x=x_y
            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
            "k"_mst.If(((x & y) << "k"_mst) &&
                !(((x << "g"_mst) && (y << "h"_mst)) ||
                ((x << "h"_mst) && (y << "g"_mst)) ||
                ((x << "i"_mst) && (y << "j"_mst)) ||
                ((x << "j"_mst) && (y << "i"_mst)))); // k=k_x*k_y*!(g_x*h_y + h_x*g_y + i_x*j_y + j_x*i_y)
        case Fragment::AND_B: return
            (x & "B"_mst).If(y << "W"_mst) | // B=B_x*W_y
            ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
            (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
            (x & y & "e"_mst).If((x & y) << "s"_mst) | // e=e_x*e_y*s_x*s_y
            (x & y & "dzm"_mst) | // d=d_x*d_y, z=z_x*z_y, m=m_x*m_y
            "f"_mst.If(((x & y) << "f"_mst) || (x << "sf"_mst) || (y << "sf"_mst)) | // f=f_x*f_y + f_x*s_x + f_y*s_y
            ((x | y) & "s"_mst) | // s=s_x+s_y
            "ux"_mst | // u, x
            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
            "k"_mst.If(((x & y) << "k"_mst) &&
                !(((x << "g"_mst) && (y << "h"_mst)) ||
                ((x << "h"_mst) && (y << "g"_mst)) ||
                ((x << "i"_mst) && (y << "j"_mst)) ||
                ((x << "j"_mst) && (y << "i"_mst)))); // k=k_x*k_y*!(g_x*h_y + h_x*g_y + i_x*j_y + j_x*i_y)
        case Fragment::OR_B: return
            "B"_mst.If(x << "Bd"_mst && y << "Wd"_mst) | // B=B_x*d_x*W_x*d_y
            ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
            (x & y & "m"_mst).If((x | y) << "s"_mst && (x & y) << "e"_mst) | // m=m_x*m_y*e_x*e_y*(s_x+s_y)
            (x & y & "zse"_mst) | // z=z_x*z_y, s=s_x*s_y, e=e_x*e_y
            "dux"_mst | // d, u, x
            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
            (x & y & "k"_mst); // k=k_x*k_y
        case Fragment::OR_D: return
            (y & "B"_mst).If(x << "Bdu"_mst) | // B=B_y*B_x*d_x*u_x
            (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
            (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
            (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
            (y & "ufde"_mst) | // u=u_y, f=f_y, d=d_y, e=e_y
            "x"_mst | // x
            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
            (x & y & "k"_mst); // k=k_x*k_y
        case Fragment::OR_C: return
            (y & "V"_mst).If(x << "Bdu"_mst) | // V=V_y*B_x*u_x*d_x
            (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
            (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
            (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
            "fx"_mst | // f, x
            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
            (x & y & "k"_mst); // k=k_x*k_y
        case Fragment::OR_I: return
            (x & y & "VBKufs"_mst) | // V=V_x*V_y, B=B_x*B_y, K=K_x*K_y, u=u_x*u_y, f=f_x*f_y, s=s_x*s_y
            "o"_mst.If((x & y) << "z"_mst) | // o=z_x*z_y
            ((x | y) & "e"_mst).If((x | y) << "f"_mst) | // e=e_x*f_y+f_x*e_y
            (x & y & "m"_mst).If((x | y) << "s"_mst) | // m=m_x*m_y*(s_x+s_y)
            ((x | y) & "d"_mst) | // d=d_x+d_y
            "x"_mst | // x
            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
            (x & y & "k"_mst); // k=k_x*k_y
        case Fragment::ANDOR: return
            (y & z & "BKV"_mst).If(x << "Bdu"_mst) | // B=B_x*d_x*u_x*B_y*B_z, K=B_x*d_x*u_x*K_y*K_z, V=B_x*d_x*u_x*V_y*V_z
            (x & y & z & "z"_mst) | // z=z_x*z_y*z_z
            ((x | (y & z)) & "o"_mst).If((x | (y & z)) << "z"_mst) | // o=o_x*z_y*z_z+z_x*o_y*o_z
            (y & z & "u"_mst) | // u=u_y*u_z
            (z & "f"_mst).If((x << "s"_mst) || (y << "f"_mst)) | // f=(s_x+f_y)*f_z
            (z & "d"_mst) | // d=d_z
            (z & "e"_mst).If(x << "s"_mst || y << "f"_mst) | // e=e_z*(s_x+f_y)
            (x & y & z & "m"_mst).If(x << "e"_mst && (x | y | z) << "s"_mst) | // m=m_x*m_y*m_z*e_x*(s_x+s_y+s_z)
            (z & (x | y) & "s"_mst) | // s=s_z*(s_x+s_y)
            "x"_mst | // x
            ((x | y | z) & "ghij"_mst) | // g=g_x+g_y+g_z, h=h_x+h_y+h_z, i=i_x+i_y+i_z, j=j_x+j_y_j_z
            "k"_mst.If(((x & y & z) << "k"_mst) &&
                !(((x << "g"_mst) && (y << "h"_mst)) ||
                ((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_A: {
            return "Budemsk"_mst;
        }
        case Fragment::THRESH: {
            bool all_e = true;
            bool all_m = true;
            uint32_t args = 0;
            uint32_t num_s = 0;
            Type acc_tl = "k"_mst;
            for (size_t i = 0; i < sub_types.size(); ++i) {
                Type t = sub_types[i];
                if (!(t << (i ? "Wdu"_mst : "Bdu"_mst))) return ""_mst; // Require Bdu, Wdu, Wdu, ...
                if (!(t << "e"_mst)) all_e = false;
                if (!(t << "m"_mst)) all_m = false;
                if (t << "s"_mst) num_s += 1;
                args += (t << "z"_mst) ? 0 : (t << "o"_mst) ? 1 : 2;
                acc_tl = ((acc_tl | t) & "ghij"_mst) |
                    // Thresh contains a combination of timelocks if it has threshold > 1 and
                    // it contains two different children that have different types of timelocks
                    // Note how if any of the children don't have "k", the parent also does not have "k"
                    "k"_mst.If(((acc_tl & t) << "k"_mst) && ((k <= 1) ||
                        ((k > 1) && !(((acc_tl << "g"_mst) && (t << "h"_mst)) ||
                        ((acc_tl << "h"_mst) && (t << "g"_mst)) ||
                        ((acc_tl << "i"_mst) && (t << "j"_mst)) ||
                        ((acc_tl << "j"_mst) && (t << "i"_mst))))));
            }
            return "Bdu"_mst |
                   "z"_mst.If(args == 0) | // z=all z
                   "o"_mst.If(args == 1) | // o=all z except one o
                   "e"_mst.If(all_e && num_s == n_subs) | // e=all e and all s
                   "m"_mst.If(all_e && all_m && num_s >= n_subs - k) | // m=all e, >=(n-k) s
                   "s"_mst.If(num_s >= n_subs - k + 1) |  // s= >=(n-k+1) s
                   acc_tl; // timelock info
            }
    }
    assert(false);
}

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 IsTapscript(ms_ctx) ? 33 : 34;
        case Fragment::PK_H: return 3 + 21;
        case Fragment::OLDER:
        case Fragment::AFTER: return 1 + BuildScript(k).size();
        case Fragment::HASH256:
        case Fragment::SHA256: return 4 + 2 + 33;
        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:
        case Fragment::WRAP_C:
        case Fragment::WRAP_N:
        case Fragment::AND_B:
        case Fragment::OR_B: return subsize + 1;
        case Fragment::WRAP_A:
        case Fragment::OR_C: return subsize + 2;
        case Fragment::WRAP_D:
        case Fragment::OR_D:
        case Fragment::OR_I:
        case Fragment::ANDOR: return subsize + 3;
        case Fragment::WRAP_J: return subsize + 4;
        case Fragment::THRESH: return subsize + n_subs + BuildScript(k).size();
    }
    assert(false);
}

InputStack& InputStack::SetAvailable(Availability avail) {
    available = avail;
    if (avail == Availability::NO) {
        stack.clear();
        size = std::numeric_limits<size_t>::max();
        has_sig = false;
        malleable = false;
        non_canon = false;
    }
    return *this;
}

InputStack& InputStack::SetWithSig() {
    has_sig = true;
    return *this;
}

InputStack& InputStack::SetNonCanon() {
    non_canon = true;
    return *this;
}

InputStack& InputStack::SetMalleable(bool x) {
    malleable = x;
    return *this;
}

InputStack operator+(InputStack a, InputStack b) {
    a.stack = Cat(std::move(a.stack), std::move(b.stack));
    if (a.available != Availability::NO && b.available != Availability::NO) a.size += b.size;
    a.has_sig |= b.has_sig;
    a.malleable |= b.malleable;
    a.non_canon |= b.non_canon;
    if (a.available == Availability::NO || b.available == Availability::NO) {
        a.SetAvailable(Availability::NO);
    } else if (a.available == Availability::MAYBE || b.available == Availability::MAYBE) {
        a.SetAvailable(Availability::MAYBE);
    }
    return a;
}

InputStack operator|(InputStack a, InputStack b) {
    // If only one is invalid, pick the other one. If both are invalid, pick an arbitrary one.
    if (a.available == Availability::NO) return b;
    if (b.available == Availability::NO) return a;
    // If only one of the solutions has a signature, we must pick the other one.
    if (!a.has_sig && b.has_sig) return a;
    if (!b.has_sig && a.has_sig) return b;
    if (!a.has_sig && !b.has_sig) {
        // If neither solution requires a signature, the result is inevitably malleable.
        a.malleable = true;
        b.malleable = true;
    } else {
        // If both options require a signature, prefer the non-malleable one.
        if (b.malleable && !a.malleable) return a;
        if (a.malleable && !b.malleable) return b;
    }
    // Between two malleable or two non-malleable solutions, pick the smaller one between
    // YESes, and the bigger ones between MAYBEs. Prefer YES over MAYBE.
    if (a.available == Availability::YES && b.available == Availability::YES) {
        return std::move(a.size <= b.size ? a : b);
    } else if (a.available == Availability::MAYBE && b.available == Availability::MAYBE) {
        return std::move(a.size >= b.size ? a : b);
    } else if (a.available == Availability::YES) {
        return a;
    } else {
        return b;
    }
}

std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script)
{
    std::vector<Opcode> out;
    CScript::const_iterator it = script.begin(), itend = script.end();
    while (it != itend) {
        std::vector<unsigned char> push_data;
        opcodetype opcode;
        if (!script.GetOp(it, opcode, push_data)) {
            return {};
        } else if (opcode >= OP_1 && opcode <= OP_16) {
            // Deal with OP_n (GetOp does not turn them into pushes).
            push_data.assign(1, CScript::DecodeOP_N(opcode));
        } else if (opcode == OP_CHECKSIGVERIFY) {
            // Decompose OP_CHECKSIGVERIFY into OP_CHECKSIG OP_VERIFY
            out.emplace_back(OP_CHECKSIG, std::vector<unsigned char>());
            opcode = OP_VERIFY;
        } else if (opcode == OP_CHECKMULTISIGVERIFY) {
            // Decompose OP_CHECKMULTISIGVERIFY into OP_CHECKMULTISIG OP_VERIFY
            out.emplace_back(OP_CHECKMULTISIG, std::vector<unsigned char>());
            opcode = OP_VERIFY;
        } else if (opcode == OP_EQUALVERIFY) {
            // 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 || opcode == OP_NUMEQUAL) && (*it == OP_VERIFY)) {
            // Rule out non minimal VERIFY sequences
            return {};
        }
        out.emplace_back(opcode, std::move(push_data));
    }
    std::reverse(out.begin(), out.end());
    return out;
}

std::optional<int64_t> ParseScriptNumber(const Opcode& in) {
    if (in.first == OP_0) {
        return 0;
    }
    if (!in.second.empty()) {
        if (IsPushdataOp(in.first) && !CheckMinimalPush(in.second, in.first)) return {};
        try {
            return CScriptNum(in.second, true).GetInt64();
        } catch(const scriptnum_error&) {}
    }
    return {};
}

int FindNextChar(std::span<const char> sp, const char m)
{
    for (int i = 0; i < (int)sp.size(); ++i) {
        if (sp[i] == m) return i;
        // We only search within the current parentheses
        if (sp[i] == ')') break;
    }
    return -1;
}

} // namespace internal
} // namespace miniscript

Coverage Report

Created: 2026-04-29 19:21

Line	Count	Source
1		// Copyright (c) 2019-present The Bitcoin Core developers
2		// Distributed under the MIT software license, see the accompanying
3		// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5		#include <limits>
6		#include <vector>
7
8		#include <primitives/transaction.h>
9		#include <script/miniscript.h>
10		#include <script/script.h>
11		#include <script/solver.h>
12		#include <span.h>
13		#include <util/check.h>
14		#include <util/vector.h>
15
16		namespace miniscript {
17		namespace internal {
18
19	7.03M	Type SanitizeType(Type e) {
20	7.03M	int num_types = (e << "K"_mst) + (e << "V"_mst) + (e << "B"_mst) + (e << "W"_mst);
21	7.03M	if (num_types == 0) return ""_mst; // No valid type, don't care about the rest
22	7.03M	CHECK_NONFATAL(num_types == 1); // K, V, B, W all conflict with each other
23	7.03M	CHECK_NONFATAL(!(e << "z"_mst) \|\| !(e << "o"_mst)); // z conflicts with o
24	7.03M	CHECK_NONFATAL(!(e << "n"_mst) \|\| !(e << "z"_mst)); // n conflicts with z
25	7.03M	CHECK_NONFATAL(!(e << "n"_mst) \|\| !(e << "W"_mst)); // n conflicts with W
26	7.03M	CHECK_NONFATAL(!(e << "V"_mst) \|\| !(e << "d"_mst)); // V conflicts with d
27	7.03M	CHECK_NONFATAL(!(e << "K"_mst) \|\| (e << "u"_mst)); // K implies u
28	7.03M	CHECK_NONFATAL(!(e << "V"_mst) \|\| !(e << "u"_mst)); // V conflicts with u
29	7.03M	CHECK_NONFATAL(!(e << "e"_mst) \|\| !(e << "f"_mst)); // e conflicts with f
30	7.03M	CHECK_NONFATAL(!(e << "e"_mst) \|\| (e << "d"_mst)); // e implies d
31	7.03M	CHECK_NONFATAL(!(e << "V"_mst) \|\| !(e << "e"_mst)); // V conflicts with e
32	7.03M	CHECK_NONFATAL(!(e << "d"_mst) \|\| !(e << "f"_mst)); // d conflicts with f
33	7.03M	CHECK_NONFATAL(!(e << "V"_mst) \|\| (e << "f"_mst)); // V implies f
34	7.03M	CHECK_NONFATAL(!(e << "K"_mst) \|\| (e << "s"_mst)); // K implies s
35	7.03M	CHECK_NONFATAL(!(e << "z"_mst) \|\| (e << "m"_mst)); // z implies m
36	7.03M	return e;
37	7.03M	}
38
39		Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k,
40	7.03M	size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx) {
41		// Sanity check on data
42	7.03M	if (fragment == Fragment::SHA256 \|\| fragment == Fragment::HASH256) {
43	219	CHECK_NONFATAL(data_size == 32);
44	7.03M	} else if (fragment == Fragment::RIPEMD160 \|\| fragment == Fragment::HASH160) {
45	176	CHECK_NONFATAL(data_size == 20);
46	7.03M	} else {
47	7.03M	CHECK_NONFATAL(data_size == 0);
48	7.03M	}
49		// Sanity check on k
50	7.03M	if (fragment == Fragment::OLDER \|\| fragment == Fragment::AFTER) {
51	9.05k	CHECK_NONFATAL(k >= 1 && k < 0x80000000UL);
52	7.02M	} else if (fragment == Fragment::MULTI \|\| fragment == Fragment::MULTI_A) {
53	985	CHECK_NONFATAL(k >= 1 && k <= n_keys);
54	7.02M	} else if (fragment == Fragment::THRESH) {
55	404	CHECK_NONFATAL(k >= 1 && k <= n_subs);
56	7.02M	} else {
57	7.02M	CHECK_NONFATAL(k == 0);
58	7.02M	}
59		// Sanity check on subs
60	7.03M	if (fragment == Fragment::AND_V \|\| fragment == Fragment::AND_B \|\| fragment == Fragment::OR_B \|\|
61	7.03M	fragment == Fragment::OR_C \|\| fragment == Fragment::OR_I \|\| fragment == Fragment::OR_D) {
62	9.55k	CHECK_NONFATAL(n_subs == 2);
63	7.02M	} else if (fragment == Fragment::ANDOR) {
64	248	CHECK_NONFATAL(n_subs == 3);
65	7.02M	} else if (fragment == Fragment::WRAP_A \|\| fragment == Fragment::WRAP_S \|\| fragment == Fragment::WRAP_C \|\|
66	7.02M	fragment == Fragment::WRAP_D \|\| fragment == Fragment::WRAP_V \|\| fragment == Fragment::WRAP_J \|\|
67	7.02M	fragment == Fragment::WRAP_N) {
68	7.00M	CHECK_NONFATAL(n_subs == 1);
69	7.00M	} else if (fragment != Fragment::THRESH) {
70	17.5k	CHECK_NONFATAL(n_subs == 0);
71	17.5k	}
72		// Sanity check on keys
73	7.03M	if (fragment == Fragment::PK_K \|\| fragment == Fragment::PK_H) {
74	6.12k	CHECK_NONFATAL(n_keys == 1);
75	7.02M	} else if (fragment == Fragment::MULTI) {
76	177	CHECK_NONFATAL(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTISIG);
77	177	CHECK_NONFATAL(!IsTapscript(ms_ctx));
78	7.02M	} else if (fragment == Fragment::MULTI_A) {
79	808	CHECK_NONFATAL(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTI_A);
80	808	CHECK_NONFATAL(IsTapscript(ms_ctx));
81	7.02M	} else {
82	7.02M	CHECK_NONFATAL(n_keys == 0);
83	7.02M	}
84
85		// Below is the per-fragment logic for computing the expression types.
86		// It heavily relies on Type's << operator (where "X << a_mst" means
87		// "X has all properties listed in a").
88	7.03M	switch (fragment) {
89	5.35k	case Fragment::PK_K: return "Konudemsxk"_mst;
90	775	case Fragment::PK_H: return "Knudemsxk"_mst;
91	7.95k	case Fragment::OLDER: return
92	7.95k	"g"_mst.If(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) \|
93	7.95k	"h"_mst.If(!(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG)) \|
94	7.95k	"Bzfmxk"_mst;
95	1.10k	case Fragment::AFTER: return
96	1.10k	"i"_mst.If(k >= LOCKTIME_THRESHOLD) \|
97	1.10k	"j"_mst.If(k < LOCKTIME_THRESHOLD) \|
98	1.10k	"Bzfmxk"_mst;
99	103	case Fragment::SHA256: return "Bonudmk"_mst;
100	77	case Fragment::RIPEMD160: return "Bonudmk"_mst;
101	116	case Fragment::HASH256: return "Bonudmk"_mst;
102	99	case Fragment::HASH160: return "Bonudmk"_mst;
103	245	case Fragment::JUST_1: return "Bzufmxk"_mst;
104	709	case Fragment::JUST_0: return "Bzudemsxk"_mst;
105	7.54k	case Fragment::WRAP_A: return
106	7.54k	"W"_mst.If(x << "B"_mst) \| // W=B_x
107	7.54k	(x & "ghijk"_mst) \| // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
108	7.54k	(x & "udfems"_mst) \| // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
109	7.54k	"x"_mst; // x
110	879	case Fragment::WRAP_S: return
111	879	"W"_mst.If(x << "Bo"_mst) \| // W=B_x*o_x
112	879	(x & "ghijk"_mst) \| // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
113	879	(x & "udfemsx"_mst); // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x, x=x_x
114	6.05k	case Fragment::WRAP_C: return
115	6.05k	"B"_mst.If(x << "K"_mst) \| // B=K_x
116	6.05k	(x & "ghijk"_mst) \| // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
117	6.05k	(x & "ondfem"_mst) \| // o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x
118	6.05k	"us"_mst; // u, s
119	115	case Fragment::WRAP_D: return
120	115	"B"_mst.If(x << "Vz"_mst) \| // B=V_x*z_x
121	115	"o"_mst.If(x << "z"_mst) \| // o=z_x
122	115	"e"_mst.If(x << "f"_mst) \| // e=f_x
123	115	(x & "ghijk"_mst) \| // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
124	115	(x & "ms"_mst) \| // m=m_x, s=s_x
125		// NOTE: 'd:' is 'u' under Tapscript but not P2WSH as MINIMALIF is only a policy rule there.
126	115	"u"_mst.If(IsTapscript(ms_ctx)) \|
127	115	"ndx"_mst; // n, d, x
128	1.60k	case Fragment::WRAP_V: return
129	1.60k	"V"_mst.If(x << "B"_mst) \| // V=B_x
130	1.60k	(x & "ghijk"_mst) \| // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
131	1.60k	(x & "zonms"_mst) \| // z=z_x, o=o_x, n=n_x, m=m_x, s=s_x
132	1.60k	"fx"_mst; // f, x
133	16	case Fragment::WRAP_J: return
134	16	"B"_mst.If(x << "Bn"_mst) \| // B=B_x*n_x
135	16	"e"_mst.If(x << "f"_mst) \| // e=f_x
136	16	(x & "ghijk"_mst) \| // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
137	16	(x & "oums"_mst) \| // o=o_x, u=u_x, m=m_x, s=s_x
138	16	"ndx"_mst; // n, d, x
139	6.98M	case Fragment::WRAP_N: return
140	6.98M	(x & "ghijk"_mst) \| // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
141	6.98M	(x & "Bzondfems"_mst) \| // B=B_x, z=z_x, o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
142	6.98M	"ux"_mst; // u, x
143	1.46k	case Fragment::AND_V: return
144	1.46k	(y & "KVB"_mst).If(x << "V"_mst) \| // B=V_xB_y, V=V_xV_y, K=V_x*K_y
145	1.46k	(x & "n"_mst) \| (y & "n"_mst).If(x << "z"_mst) \| // n=n_x+z_x*n_y
146	1.46k	((x \| y) & "o"_mst).If((x \| y) << "z"_mst) \| // o=o_xz_y+z_xo_y
147	1.46k	(x & y & "mz"_mst) \| // m=m_xm_y, z=z_xz_y
148	1.46k	((x \| y) & "s"_mst) \| // s=s_x+s_y
149	1.46k	"f"_mst.If((y << "f"_mst) \|\| (x << "s"_mst)) \| // f=f_y+s_x
150	1.46k	(y & "ux"_mst) \| // u=u_y, x=x_y
151	1.46k	((x \| y) & "ghij"_mst) \| // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
152	1.46k	"k"_mst.If(((x & y) << "k"_mst) &&
153	1.46k	!(((x << "g"_mst) && (y << "h"_mst)) \|\|
154	1.45k	((x << "h"_mst) && (y << "g"_mst)) \|\|
155	1.45k	((x << "i"_mst) && (y << "j"_mst)) \|\|
156	1.45k	((x << "j"_mst) && (y << "i"_mst)))); // k=k_xk_y!(g_xh_y + h_xg_y + i_xj_y + j_xi_y)
157	7.15k	case Fragment::AND_B: return
158	7.15k	(x & "B"_mst).If(y << "W"_mst) \| // B=B_x*W_y
159	7.15k	((x \| y) & "o"_mst).If((x \| y) << "z"_mst) \| // o=o_xz_y+z_xo_y
160	7.15k	(x & "n"_mst) \| (y & "n"_mst).If(x << "z"_mst) \| // n=n_x+z_x*n_y
161	7.15k	(x & y & "e"_mst).If((x & y) << "s"_mst) \| // e=e_xe_ys_x*s_y
162	7.15k	(x & y & "dzm"_mst) \| // d=d_xd_y, z=z_xz_y, m=m_x*m_y
163	7.15k	"f"_mst.If(((x & y) << "f"_mst) \|\| (x << "sf"_mst) \|\| (y << "sf"_mst)) \| // f=f_xf_y + f_xs_x + f_y*s_y
164	7.15k	((x \| y) & "s"_mst) \| // s=s_x+s_y
165	7.15k	"ux"_mst \| // u, x
166	7.15k	((x \| y) & "ghij"_mst) \| // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
167	7.15k	"k"_mst.If(((x & y) << "k"_mst) &&
168	7.15k	!(((x << "g"_mst) && (y << "h"_mst)) \|\|
169	7.15k	((x << "h"_mst) && (y << "g"_mst)) \|\|
170	7.15k	((x << "i"_mst) && (y << "j"_mst)) \|\|
171	7.15k	((x << "j"_mst) && (y << "i"_mst)))); // k=k_xk_y!(g_xh_y + h_xg_y + i_xj_y + j_xi_y)
172	93	case Fragment::OR_B: return
173	93	"B"_mst.If(x << "Bd"_mst && y << "Wd"_mst) \| // B=B_xd_xW_x*d_y
174	93	((x \| y) & "o"_mst).If((x \| y) << "z"_mst) \| // o=o_xz_y+z_xo_y
175	93	(x & y & "m"_mst).If((x \| y) << "s"_mst && (x & y) << "e"_mst) \| // m=m_xm_ye_xe_y(s_x+s_y)
176	93	(x & y & "zse"_mst) \| // z=z_xz_y, s=s_xs_y, e=e_x*e_y
177	93	"dux"_mst \| // d, u, x
178	93	((x \| y) & "ghij"_mst) \| // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
179	93	(x & y & "k"_mst); // k=k_x*k_y
180	132	case Fragment::OR_D: return
181	132	(y & "B"_mst).If(x << "Bdu"_mst) \| // B=B_yB_xd_x*u_x
182	132	(x & "o"_mst).If(y << "z"_mst) \| // o=o_x*z_y
183	132	(x & y & "m"_mst).If(x << "e"_mst && (x \| y) << "s"_mst) \| // m=m_xm_ye_x*(s_x+s_y)
184	132	(x & y & "zs"_mst) \| // z=z_xz_y, s=s_xs_y
185	132	(y & "ufde"_mst) \| // u=u_y, f=f_y, d=d_y, e=e_y
186	132	"x"_mst \| // x
187	132	((x \| y) & "ghij"_mst) \| // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
188	132	(x & y & "k"_mst); // k=k_x*k_y
189	62	case Fragment::OR_C: return
190	62	(y & "V"_mst).If(x << "Bdu"_mst) \| // V=V_yB_xu_x*d_x
191	62	(x & "o"_mst).If(y << "z"_mst) \| // o=o_x*z_y
192	62	(x & y & "m"_mst).If(x << "e"_mst && (x \| y) << "s"_mst) \| // m=m_xm_ye_x*(s_x+s_y)
193	62	(x & y & "zs"_mst) \| // z=z_xz_y, s=s_xs_y
194	62	"fx"_mst \| // f, x
195	62	((x \| y) & "ghij"_mst) \| // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
196	62	(x & y & "k"_mst); // k=k_x*k_y
197	647	case Fragment::OR_I: return
198	647	(x & y & "VBKufs"_mst) \| // V=V_xV_y, B=B_xB_y, K=K_xK_y, u=u_xu_y, f=f_xf_y, s=s_xs_y
199	647	"o"_mst.If((x & y) << "z"_mst) \| // o=z_x*z_y
200	647	((x \| y) & "e"_mst).If((x \| y) << "f"_mst) \| // e=e_xf_y+f_xe_y
201	647	(x & y & "m"_mst).If((x \| y) << "s"_mst) \| // m=m_xm_y(s_x+s_y)
202	647	((x \| y) & "d"_mst) \| // d=d_x+d_y
203	647	"x"_mst \| // x
204	647	((x \| y) & "ghij"_mst) \| // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
205	647	(x & y & "k"_mst); // k=k_x*k_y
206	248	case Fragment::ANDOR: return
207	248	(y & z & "BKV"_mst).If(x << "Bdu"_mst) \| // B=B_xd_xu_xB_yB_z, K=B_xd_xu_xK_yK_z, V=B_xd_xu_xV_yV_z
208	248	(x & y & z & "z"_mst) \| // z=z_xz_yz_z
209	248	((x \| (y & z)) & "o"_mst).If((x \| (y & z)) << "z"_mst) \| // o=o_xz_yz_z+z_xo_yo_z
210	248	(y & z & "u"_mst) \| // u=u_y*u_z
211	248	(z & "f"_mst).If((x << "s"_mst) \|\| (y << "f"_mst)) \| // f=(s_x+f_y)*f_z
212	248	(z & "d"_mst) \| // d=d_z
213	248	(z & "e"_mst).If(x << "s"_mst \|\| y << "f"_mst) \| // e=e_z*(s_x+f_y)
214	248	(x & y & z & "m"_mst).If(x << "e"_mst && (x \| y \| z) << "s"_mst) \| // m=m_xm_ym_ze_x(s_x+s_y+s_z)
215	248	(z & (x \| y) & "s"_mst) \| // s=s_z*(s_x+s_y)
216	248	"x"_mst \| // x
217	248	((x \| y \| z) & "ghij"_mst) \| // g=g_x+g_y+g_z, h=h_x+h_y+h_z, i=i_x+i_y+i_z, j=j_x+j_y_j_z
218	248	"k"_mst.If(((x & y & z) << "k"_mst) &&
219	248	!(((x << "g"_mst) && (y << "h"_mst)) \|\|
220	242	((x << "h"_mst) && (y << "g"_mst)) \|\|
221	242	((x << "i"_mst) && (y << "j"_mst)) \|\|
222	242	((x << "j"_mst) && (y << "i"_mst)))); // k=k_xk_yk_z* !(g_xh_y + h_xg_y + i_xj_y + j_xi_y)
223	177	case Fragment::MULTI: {
224	177	return "Bnudemsk"_mst;
225	0	}
226	808	case Fragment::MULTI_A: {
227	808	return "Budemsk"_mst;
228	0	}
229	404	case Fragment::THRESH: {
230	404	bool all_e = true;
231	404	bool all_m = true;
232	404	uint32_t args = 0;
233	404	uint32_t num_s = 0;
234	404	Type acc_tl = "k"_mst;
235	1.96k	for (size_t i = 0; i < sub_types.size(); ++i) {
236	1.55k	Type t = sub_types[i];
237	1.55k	if (!(t << (i ? "Wdu"_mst : "Bdu"_mst))) return ""_mst; // Require Bdu, Wdu, Wdu, ...
238	1.55k	if (!(t << "e"_mst)) all_e = false;
239	1.55k	if (!(t << "m"_mst)) all_m = false;
240	1.55k	if (t << "s"_mst) num_s += 1;
241	1.55k	args += (t << "z"_mst) ? 0 : (t << "o"_mst) ? 1 : 2;
242	1.55k	acc_tl = ((acc_tl \| t) & "ghij"_mst) \|
243		// Thresh contains a combination of timelocks if it has threshold > 1 and
244		// it contains two different children that have different types of timelocks
245		// Note how if any of the children don't have "k", the parent also does not have "k"
246	1.55k	"k"_mst.If(((acc_tl & t) << "k"_mst) && ((k <= 1) \|\|
247	1.55k	((k > 1) && !(((acc_tl << "g"_mst) && (t << "h"_mst)) \|\|
248	1.40k	((acc_tl << "h"_mst) && (t << "g"_mst)) \|\|
249	1.40k	((acc_tl << "i"_mst) && (t << "j"_mst)) \|\|
250	1.40k	((acc_tl << "j"_mst) && (t << "i"_mst))))));
251	1.55k	}
252	402	return "Bdu"_mst \|
253	402	"z"_mst.If(args == 0) \| // z=all z
254	402	"o"_mst.If(args == 1) \| // o=all z except one o
255	402	"e"_mst.If(all_e && num_s == n_subs) \| // e=all e and all s
256	402	"m"_mst.If(all_e && all_m && num_s >= n_subs - k) \| // m=all e, >=(n-k) s
257	402	"s"_mst.If(num_s >= n_subs - k + 1) \| // s= >=(n-k+1) s
258	402	acc_tl; // timelock info
259	404	}
260	7.03M	}
261	7.03M	assert(false);
262	0	}
263
264		size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs,
265	7.03M	size_t n_keys, MiniscriptContext ms_ctx) {
266	7.03M	switch (fragment) {
267	245	case Fragment::JUST_1:
268	954	case Fragment::JUST_0: return 1;
269	5.35k	case Fragment::PK_K: return IsTapscript(ms_ctx) ? 33 : 34;
270	775	case Fragment::PK_H: return 3 + 21;
271	7.95k	case Fragment::OLDER:
272	9.05k	case Fragment::AFTER: return 1 + BuildScript(k).size();
273	116	case Fragment::HASH256:
274	219	case Fragment::SHA256: return 4 + 2 + 33;
275	99	case Fragment::HASH160:
276	176	case Fragment::RIPEMD160: return 4 + 2 + 21;
277	177	case Fragment::MULTI: return 1 + BuildScript(n_keys).size() + BuildScript(k).size() + 34 * n_keys;
278	808	case Fragment::MULTI_A: return (1 + 32 + 1) * n_keys + BuildScript(k).size() + 1;
279	1.46k	case Fragment::AND_V: return subsize;
280	1.60k	case Fragment::WRAP_V: return subsize + (sub0typ << "x"_mst);
281	879	case Fragment::WRAP_S:
282	6.93k	case Fragment::WRAP_C:
283	6.99M	case Fragment::WRAP_N:
284	7.00M	case Fragment::AND_B:
285	7.00M	case Fragment::OR_B: return subsize + 1;
286	7.54k	case Fragment::WRAP_A:
287	7.60k	case Fragment::OR_C: return subsize + 2;
288	115	case Fragment::WRAP_D:
289	247	case Fragment::OR_D:
290	894	case Fragment::OR_I:
291	1.14k	case Fragment::ANDOR: return subsize + 3;
292	16	case Fragment::WRAP_J: return subsize + 4;
293	404	case Fragment::THRESH: return subsize + n_subs + BuildScript(k).size();
294	7.03M	}
295	7.03M	assert(false);
296	0	}
297
298	90.3M	InputStack& InputStack::SetAvailable(Availability avail) {
299	90.3M	available = avail;
300	90.3M	if (avail == Availability::NO) {
301	90.1M	stack.clear();
302	90.1M	size = std::numeric_limits<size_t>::max();
303	90.1M	has_sig = false;
304	90.1M	malleable = false;
305	90.1M	non_canon = false;
306	90.1M	}
307	90.3M	return *this;
308	90.3M	}
309
310	472k	InputStack& InputStack::SetWithSig() {
311	472k	has_sig = true;
312	472k	return *this;
313	472k	}
314
315	819k	InputStack& InputStack::SetNonCanon() {
316	819k	non_canon = true;
317	819k	return *this;
318	819k	}
319
320	821k	InputStack& InputStack::SetMalleable(bool x) {
321	821k	malleable = x;
322	821k	return *this;
323	821k	}
324
325	90.6M	InputStack operator+(InputStack a, InputStack b) {
326	90.6M	a.stack = Cat(std::move(a.stack), std::move(b.stack));
327	90.6M	if (a.available != Availability::NO && b.available != Availability::NO) a.size += b.size;
328	90.6M	a.has_sig \|= b.has_sig;
329	90.6M	a.malleable \|= b.malleable;
330	90.6M	a.non_canon \|= b.non_canon;
331	90.6M	if (a.available == Availability::NO \|\| b.available == Availability::NO) {
332	89.8M	a.SetAvailable(Availability::NO);
333	89.8M	} else if (a.available == Availability::MAYBE \|\| b.available == Availability::MAYBE) {
334	0	a.SetAvailable(Availability::MAYBE);
335	0	}
336	90.6M	return a;
337	90.6M	}
338
339	45.2M	InputStack operator\|(InputStack a, InputStack b) {
340		// If only one is invalid, pick the other one. If both are invalid, pick an arbitrary one.
341	45.2M	if (a.available == Availability::NO) return b;
342	790k	if (b.available == Availability::NO) return a;
343		// If only one of the solutions has a signature, we must pick the other one.
344	209k	if (!a.has_sig && b.has_sig) return a;
345	11.3k	if (!b.has_sig && a.has_sig) return b;
346	11.1k	if (!a.has_sig && !b.has_sig) {
347		// If neither solution requires a signature, the result is inevitably malleable.
348	1.12k	a.malleable = true;
349	1.12k	b.malleable = true;
350	9.98k	} else {
351		// If both options require a signature, prefer the non-malleable one.
352	9.98k	if (b.malleable && !a.malleable) return a;
353	9.95k	if (a.malleable && !b.malleable) return b;
354	9.95k	}
355		// Between two malleable or two non-malleable solutions, pick the smaller one between
356		// YESes, and the bigger ones between MAYBEs. Prefer YES over MAYBE.
357	11.0k	if (a.available == Availability::YES && b.available == Availability::YES) {
358	11.0k	return std::move(a.size <= b.size ? a : b);
359	11.0k	} else if (a.available == Availability::MAYBE && b.available == Availability::MAYBE) {
360	0	return std::move(a.size >= b.size ? a : b);
361	0	} else if (a.available == Availability::YES) {
362	0	return a;
363	0	} else {
364	0	return b;
365	0	}
366	11.0k	}
367
368		std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script)
369	4.02k	{
370	4.02k	std::vector<Opcode> out;
371	4.02k	CScript::const_iterator it = script.begin(), itend = script.end();
372	6.15M	while (it != itend) {
373	6.14M	std::vector<unsigned char> push_data;
374	6.14M	opcodetype opcode;
375	6.14M	if (!script.GetOp(it, opcode, push_data)) {
376	0	return {};
377	6.14M	} else if (opcode >= OP_1 && opcode <= OP_16) {
378		// Deal with OP_n (GetOp does not turn them into pushes).
379	4.07k	push_data.assign(1, CScript::DecodeOP_N(opcode));
380	6.14M	} else if (opcode == OP_CHECKSIGVERIFY) {
381		// Decompose OP_CHECKSIGVERIFY into OP_CHECKSIG OP_VERIFY
382	693	out.emplace_back(OP_CHECKSIG, std::vector<unsigned char>());
383	693	opcode = OP_VERIFY;
384	6.14M	} else if (opcode == OP_CHECKMULTISIGVERIFY) {
385		// Decompose OP_CHECKMULTISIGVERIFY into OP_CHECKMULTISIG OP_VERIFY
386	20	out.emplace_back(OP_CHECKMULTISIG, std::vector<unsigned char>());
387	20	opcode = OP_VERIFY;
388	6.14M	} else if (opcode == OP_EQUALVERIFY) {
389		// Decompose OP_EQUALVERIFY into OP_EQUAL OP_VERIFY
390	1.12k	out.emplace_back(OP_EQUAL, std::vector<unsigned char>());
391	1.12k	opcode = OP_VERIFY;
392	6.14M	} else if (opcode == OP_NUMEQUALVERIFY) {
393		// Decompose OP_NUMEQUALVERIFY into OP_NUMEQUAL OP_VERIFY
394	1	out.emplace_back(OP_NUMEQUAL, std::vector<unsigned char>());
395	1	opcode = OP_VERIFY;
396	6.14M	} else if (IsPushdataOp(opcode)) {
397	96.6k	if (!CheckMinimalPush(push_data, opcode)) return {};
398	6.04M	} else if (it != itend && (opcode == OP_CHECKSIG \|\| opcode == OP_CHECKMULTISIG \|\| opcode == OP_EQUAL \|\| opcode == OP_NUMEQUAL) && (*it == OP_VERIFY)) {
399		// Rule out non minimal VERIFY sequences
400	2	return {};
401	2	}
402	6.14M	out.emplace_back(opcode, std::move(push_data));
403	6.14M	}
404	4.02k	std::reverse(out.begin(), out.end());
405	4.02k	return out;
406	4.02k	}
407
408	4.88k	std::optional<int64_t> ParseScriptNumber(const Opcode& in) {
409	4.88k	if (in.first == OP_0) {
410	0	return 0;
411	0	}
412	4.88k	if (!in.second.empty()) {
413	4.88k	if (IsPushdataOp(in.first) && !CheckMinimalPush(in.second, in.first)) return {};
414	4.88k	try {
415	4.88k	return CScriptNum(in.second, true).GetInt64();
416	4.88k	} catch(const scriptnum_error&) {}
417	4.88k	}
418	4	return {};
419	4.88k	}
420
421		int FindNextChar(std::span<const char> sp, const char m)
422	280	{
423	14.9k	for (int i = 0; i < (int)sp.size(); ++i) {
424	14.9k	if (sp[i] == m) return i;
425		// We only search within the current parentheses
426	14.7k	if (sp[i] == ')') break;
427	14.7k	}
428	46	return -1;
429	280	}
430
431		} // namespace internal
432		} // namespace miniscript