Inside Bitcoin

2001                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key)));
2002                script_size += 23;
2003            } else if (Const("sha256(", in, /*skip=*/false)) {
2004                std::optional<std::vector<unsigned char>> hash = ParseHexStr("sha256", in, 32);
2005                if (!hash) return {};
2006                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, std::move(*hash));
2007                script_size += 38;
2008            } else if (Const("ripemd160(", in, /*skip=*/false)) {
2009                std::optional<std::vector<unsigned char>> hash = ParseHexStr("ripemd160", in, 20);
2010                if (!hash) return {};
2011                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, std::move(*hash));
2012                script_size += 26;
2013            } else if (Const("hash256(", in, /*skip=*/false)) {
2014                std::optional<std::vector<unsigned char>> hash = ParseHexStr("hash256", in, 32);
2015                if (!hash) return {};
2016                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, std::move(*hash));
2017                script_size += 38;
2018            } else if (Const("hash160(", in, /*skip=*/false)) {
2019                std::optional<std::vector<unsigned char>> hash = ParseHexStr("hash160", in, 20);
2020                if (!hash) return {};
2021                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, std::move(*hash));
2022                script_size += 26;
2023            } else if (Const("after(", in, /*skip=*/false)) {
2024                auto expr = Expr(in);
2025                if (!Func("after", expr)) return {};
2026                const auto num{ToIntegral<int64_t>(std::string_view(expr.begin(), expr.end()))};
2027                if (!num.has_value() || *num < 1 || *num >= 0x80000000L) return {};
2028                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, *num);
2029                script_size += 1 + (*num > 16) + (*num > 0x7f) + (*num > 0x7fff) + (*num > 0x7fffff);
2030            } else if (Const("older(", in, /*skip=*/false)) {
2031                auto expr = Expr(in);
2032                if (!Func("older", expr)) return {};
2033                const auto num{ToIntegral<int64_t>(std::string_view(expr.begin(), expr.end()))};
2034                if (!num.has_value() || *num < 1 || *num >= 0x80000000L) return {};
2035                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, *num);
2036                script_size += 1 + (*num > 16) + (*num > 0x7f) + (*num > 0x7fff) + (*num > 0x7fffff);
2037            } else if (Const("multi(", in)) {
2038                if (!parse_multi_exp(in, /* is_multi_a = */false)) return {};
2039            } else if (Const("multi_a(", in)) {
2040                if (!parse_multi_exp(in, /* is_multi_a = */true)) return {};
2041            } else if (Const("thresh(", in)) {
2042                int next_comma = FindNextChar(in, ',');
2043                if (next_comma < 1) return {};
2044                const auto k{ToIntegral<int64_t>(std::string_view(in.data(), next_comma))};
2045                if (!k.has_value() || *k < 1) return {};
2046                in = in.subspan(next_comma + 1);
2047                // n = 1 here because we read the first WRAPPED_EXPR before reaching THRESH
2048                to_parse.emplace_back(ParseContext::THRESH, 1, *k);
2049                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2050                script_size += 2 + (*k > 16) + (*k > 0x7f) + (*k > 0x7fff) + (*k > 0x7fffff);
2051            } else if (Const("andor(", in)) {
2052                to_parse.emplace_back(ParseContext::ANDOR, -1, -1);
2053                to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
2054                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2055                to_parse.emplace_back(ParseContext::COMMA, -1, -1);
2056                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2057                to_parse.emplace_back(ParseContext::COMMA, -1, -1);
2058                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2059                script_size += 5;
2060            } else {
2061                if (Const("and_n(", in)) {
2062                    to_parse.emplace_back(ParseContext::AND_N, -1, -1);
2063                    script_size += 5;
2064                } else if (Const("and_b(", in)) {
2065                    to_parse.emplace_back(ParseContext::AND_B, -1, -1);
2066                    script_size += 2;
2067                } else if (Const("and_v(", in)) {
2068                    to_parse.emplace_back(ParseContext::AND_V, -1, -1);
2069                    script_size += 1;
2070                } else if (Const("or_b(", in)) {
2071                    to_parse.emplace_back(ParseContext::OR_B, -1, -1);
2072                    script_size += 2;
2073                } else if (Const("or_c(", in)) {
2074                    to_parse.emplace_back(ParseContext::OR_C, -1, -1);
2075                    script_size += 3;
2076                } else if (Const("or_d(", in)) {
2077                    to_parse.emplace_back(ParseContext::OR_D, -1, -1);
2078                    script_size += 4;
2079                } else if (Const("or_i(", in)) {
2080                    to_parse.emplace_back(ParseContext::OR_I, -1, -1);
2081                    script_size += 4;
2082                } else {
2083                    return {};
2084                }
2085                to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
2086                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2087                to_parse.emplace_back(ParseContext::COMMA, -1, -1);
2088                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2089            }
2090            break;
2091        }
2092        case ParseContext::ALT: {
2093            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_A, Vector(std::move(constructed.back()))};
2094            break;
2095        }
2096        case ParseContext::SWAP: {
2097            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_S, Vector(std::move(constructed.back()))};
2098            break;
2099        }
2100        case ParseContext::CHECK: {
2101            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(std::move(constructed.back()))};
2102            break;
2103        }
2104        case ParseContext::DUP_IF: {
2105            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_D, Vector(std::move(constructed.back()))};
2106            break;
2107        }
2108        case ParseContext::NON_ZERO: {
2109            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_J, Vector(std::move(constructed.back()))};
2110            break;
2111        }
2112        case ParseContext::ZERO_NOTEQUAL: {
2113            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_N, Vector(std::move(constructed.back()))};
2114            break;
2115        }
2116        case ParseContext::VERIFY: {
2117            script_size += (constructed.back().GetType() << "x"_mst);
2118            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_V, Vector(std::move(constructed.back()))};
2119            break;
2120        }
2121        case ParseContext::WRAP_U: {
2122            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::OR_I, Vector(std::move(constructed.back()), Node<Key>{internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0})};
2123            break;
2124        }
2125        case ParseContext::WRAP_T: {
2126            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::AND_V, Vector(std::move(constructed.back()), Node<Key>{internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1})};
2127            break;
2128        }
2129        case ParseContext::AND_B: {
2130            BuildBack(ctx.MsContext(), Fragment::AND_B, constructed);
2131            break;
2132        }
2133        case ParseContext::AND_N: {
2134            auto mid = std::move(constructed.back());
2135            constructed.pop_back();
2136            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), Node<Key>{internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0})};
2137            break;
2138        }
2139        case ParseContext::AND_V: {
2140            BuildBack(ctx.MsContext(), Fragment::AND_V, constructed);
2141            break;
2142        }
2143        case ParseContext::OR_B: {
2144            BuildBack(ctx.MsContext(), Fragment::OR_B, constructed);
2145            break;
2146        }
2147        case ParseContext::OR_C: {
2148            BuildBack(ctx.MsContext(), Fragment::OR_C, constructed);
2149            break;
2150        }
2151        case ParseContext::OR_D: {
2152            BuildBack(ctx.MsContext(), Fragment::OR_D, constructed);
2153            break;
2154        }
2155        case ParseContext::OR_I: {
2156            BuildBack(ctx.MsContext(), Fragment::OR_I, constructed);
2157            break;
2158        }
2159        case ParseContext::ANDOR: {
2160            auto right = std::move(constructed.back());
2161            constructed.pop_back();
2162            auto mid = std::move(constructed.back());
2163            constructed.pop_back();
2164            constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right))};
2165            break;
2166        }
2167        case ParseContext::THRESH: {
2168            if (in.size() < 1) return {};
2169            if (in[0] == ',') {
2170                in = in.subspan(1);
2171                to_parse.emplace_back(ParseContext::THRESH, n+1, k);
2172                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2173                script_size += 2;
2174            } else if (in[0] == ')') {
2175                if (k > n) return {};
2176                in = in.subspan(1);
2177                // Children are constructed in reverse order, so iterate from end to beginning
2178                std::vector<Node<Key>> subs;
2179                for (int i = 0; i < n; ++i) {
2180                    subs.push_back(std::move(constructed.back()));
2181                    constructed.pop_back();
2182                }
2183                std::reverse(subs.begin(), subs.end());
2184                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::THRESH, std::move(subs), k);
2185            } else {
2186                return {};
2187            }
2188            break;
2189        }
2190        case ParseContext::COMMA: {
2191            if (in.size() < 1 || in[0] != ',') return {};
2192            in = in.subspan(1);
2193            break;
2194        }
2195        case ParseContext::CLOSE_BRACKET: {
2196            if (in.size() < 1 || in[0] != ')') return {};
2197            in = in.subspan(1);
2198            break;
2199        }
2200        }
2201    }
2202
2203    // Sanity checks on the produced miniscript
2204    assert(constructed.size() >= 1);
2205    CHECK_NONFATAL(constructed.size() == 1);
2206    assert(constructed[0].ScriptSize() == script_size);
2207    if (in.size() > 0) return {};
2208    Node<Key> tl_node{std::move(constructed.front())};
2209    tl_node.DuplicateKeyCheck(ctx);
2210    return tl_node;
2211}
2212
2213/** Decode a script into opcode/push pairs.
2214 *
2215 * Construct a vector with one element per opcode in the script, in reverse order.
2216 * Each element is a pair consisting of the opcode, as well as the data pushed by
2217 * the opcode (including OP_n), if any. OP_CHECKSIGVERIFY, OP_CHECKMULTISIGVERIFY,
2218 * OP_NUMEQUALVERIFY and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG,
2219 * OP_EQUAL and OP_NUMEQUAL respectively, plus OP_VERIFY.
2220 */
2221std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script);
2222
2223/** Determine whether the passed pair (created by DecomposeScript) is pushing a number. */
2224std::optional<int64_t> ParseScriptNumber(const Opcode& in);
2225
2226enum class DecodeContext {
2227    /** A single expression of type B, K, or V. Specifically, this can't be an
2228     * and_v or an expression of type W (a: and s: wrappers). */
2229    SINGLE_BKV_EXPR,
2230    /** Potentially multiple SINGLE_BKV_EXPRs as children of (potentially multiple)
2231     * and_v expressions. Syntactic sugar for MAYBE_AND_V + SINGLE_BKV_EXPR. */
2232    BKV_EXPR,
2233    /** An expression of type W (a: or s: wrappers). */
2234    W_EXPR,
2235
2236    /** SWAP expects the next element to be OP_SWAP (inside a W-type expression that
2237     * didn't end with FROMALTSTACK), and wraps the top of the constructed stack
2238     * with s: */
2239    SWAP,
2240    /** ALT expects the next element to be TOALTSTACK (we must have already read a
2241     * FROMALTSTACK earlier), and wraps the top of the constructed stack with a: */
2242    ALT,
2243    /** CHECK wraps the top constructed node with c: */
2244    CHECK,
2245    /** DUP_IF wraps the top constructed node with d: */
2246    DUP_IF,
2247    /** VERIFY wraps the top constructed node with v: */
2248    VERIFY,
2249    /** NON_ZERO wraps the top constructed node with j: */
2250    NON_ZERO,