Inside Bitcoin

2251    /** ZERO_NOTEQUAL wraps the top constructed node with n: */
2252    ZERO_NOTEQUAL,
2253
2254    /** MAYBE_AND_V will check if the next part of the script could be a valid
2255     * miniscript sub-expression, and if so it will push AND_V and SINGLE_BKV_EXPR
2256     * to decode it and construct the and_v node. This is recursive, to deal with
2257     * multiple and_v nodes inside each other. */
2258    MAYBE_AND_V,
2259    /** AND_V will construct an and_v node from the last two constructed nodes. */
2260    AND_V,
2261    /** AND_B will construct an and_b node from the last two constructed nodes. */
2262    AND_B,
2263    /** ANDOR will construct an andor node from the last three constructed nodes. */
2264    ANDOR,
2265    /** OR_B will construct an or_b node from the last two constructed nodes. */
2266    OR_B,
2267    /** OR_C will construct an or_c node from the last two constructed nodes. */
2268    OR_C,
2269    /** OR_D will construct an or_d node from the last two constructed nodes. */
2270    OR_D,
2271
2272    /** In a thresh expression, all sub-expressions other than the first are W-type,
2273     * and end in OP_ADD. THRESH_W will check for this OP_ADD and either push a W_EXPR
2274     * or a SINGLE_BKV_EXPR and jump to THRESH_E accordingly. */
2275    THRESH_W,
2276    /** THRESH_E constructs a thresh node from the appropriate number of constructed
2277     * children. */
2278    THRESH_E,
2279
2280    /** ENDIF signals that we are inside some sort of OP_IF structure, which could be
2281     * or_d, or_c, or_i, andor, d:, or j: wrapper, depending on what follows. We read
2282     * a BKV_EXPR and then deal with the next opcode case-by-case. */
2283    ENDIF,
2284    /** If, inside an ENDIF context, we find an OP_NOTIF before finding an OP_ELSE,
2285     * we could either be in an or_d or an or_c node. We then check for IFDUP to
2286     * distinguish these cases. */
2287    ENDIF_NOTIF,
2288    /** If, inside an ENDIF context, we find an OP_ELSE, then we could be in either an
2289     * or_i or an andor node. Read the next BKV_EXPR and find either an OP_IF or an
2290     * OP_NOTIF. */
2291    ENDIF_ELSE,
2292};
2293
2294//! Parse a miniscript from a bitcoin script
2295template <typename Key, typename Ctx, typename I>
2296inline std::optional<Node<Key>> DecodeScript(I& in, I last, const Ctx& ctx)
2297{
2298    // The two integers are used to hold state for thresh()
2299    std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse;
2300    std::vector<Node<Key>> constructed;
2301
2302    // This is the top level, so we assume the type is B
2303    // (in particular, disallowing top level W expressions)
2304    to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2305
2306    while (!to_parse.empty()) {
2307        // Exit early if the Miniscript is not going to be valid.
2308        if (!constructed.empty() && !constructed.back().IsValid()) return {};
2309
2310        // Get the current context we are decoding within
2311        auto [cur_context, n, k] = to_parse.back();
2312        to_parse.pop_back();
2313
2314        switch(cur_context) {
2315        case DecodeContext::SINGLE_BKV_EXPR: {
2316            if (in >= last) return {};
2317
2318            // Constants
2319            if (in[0].first == OP_1) {
2320                ++in;
2321                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1);
2322                break;
2323            }
2324            if (in[0].first == OP_0) {
2325                ++in;
2326                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0);
2327                break;
2328            }
2329            // Public keys
2330            if (in[0].second.size() == 33 || in[0].second.size() == 32) {
2331                auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end());
2332                if (!key) return {};
2333                ++in;
2334                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key)));
2335                break;
2336            }
2337            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) {
2338                auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end());
2339                if (!key) return {};
2340                in += 5;
2341                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key)));
2342                break;
2343            }
2344            // Time locks
2345            std::optional<int64_t> num;
2346            if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && (num = ParseScriptNumber(in[1]))) {
2347                in += 2;
2348                if (*num < 1 || *num > 0x7FFFFFFFL) return {};
2349                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, *num);
2350                break;
2351            }
2352            if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && (num = ParseScriptNumber(in[1]))) {
2353                in += 2;
2354                if (num < 1 || num > 0x7FFFFFFFL) return {};
2355                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, *num);
2356                break;
2357            }
2358            // Hashes
2359            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) {
2360                if (in[2].first == OP_SHA256 && in[1].second.size() == 32) {
2361                    constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, in[1].second);
2362                    in += 7;
2363                    break;
2364                } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) {
2365                    constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, in[1].second);
2366                    in += 7;
2367                    break;
2368                } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) {
2369                    constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, in[1].second);
2370                    in += 7;
2371                    break;
2372                } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) {
2373                    constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, in[1].second);
2374                    in += 7;
2375                    break;
2376                }
2377            }
2378            // Multi
2379            if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) {
2380                if (IsTapscript(ctx.MsContext())) return {};
2381                std::vector<Key> keys;
2382                const auto n = ParseScriptNumber(in[1]);
2383                if (!n || last - in < 3 + *n) return {};
2384                if (*n < 1 || *n > 20) return {};
2385                for (int i = 0; i < *n; ++i) {
2386                    if (in[2 + i].second.size() != 33) return {};
2387                    auto key = ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end());
2388                    if (!key) return {};
2389                    keys.push_back(std::move(*key));
2390                }
2391                const auto k = ParseScriptNumber(in[2 + *n]);
2392                if (!k || *k < 1 || *k > *n) return {};
2393                in += 3 + *n;
2394                std::reverse(keys.begin(), keys.end());
2395                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), *k);
2396                break;
2397            }
2398            // Tapscript's equivalent of multi
2399            if (last - in >= 4 && in[0].first == OP_NUMEQUAL) {
2400                if (!IsTapscript(ctx.MsContext())) return {};
2401                // The necessary threshold of signatures.
2402                const auto k = ParseScriptNumber(in[1]);
2403                if (!k) return {};
2404                if (*k < 1 || *k > MAX_PUBKEYS_PER_MULTI_A) return {};
2405                if (last - in < 2 + *k * 2) return {};
2406                std::vector<Key> keys;
2407                keys.reserve(*k);
2408                // Walk through the expected (pubkey, CHECKSIG[ADD]) pairs.
2409                for (int pos = 2;; pos += 2) {
2410                    if (last - in < pos + 2) return {};
2411                    // Make sure it's indeed an x-only pubkey and a CHECKSIG[ADD], then parse the key.
2412                    if (in[pos].first != OP_CHECKSIGADD && in[pos].first != OP_CHECKSIG) return {};
2413                    if (in[pos + 1].second.size() != 32) return {};
2414                    auto key = ctx.FromPKBytes(in[pos + 1].second.begin(), in[pos + 1].second.end());
2415                    if (!key) return {};
2416                    keys.push_back(std::move(*key));
2417                    // Make sure early we don't parse an arbitrary large expression.
2418                    if (keys.size() > MAX_PUBKEYS_PER_MULTI_A) return {};
2419                    // OP_CHECKSIG means it was the last one to parse.
2420                    if (in[pos].first == OP_CHECKSIG) break;
2421                }
2422                if (keys.size() < (size_t)*k) return {};
2423                in += 2 + keys.size() * 2;
2424                std::reverse(keys.begin(), keys.end());
2425                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), *k);
2426                break;
2427            }
2428            /** In the following wrappers, we only need to push SINGLE_BKV_EXPR rather
2429             * than BKV_EXPR, because and_v commutes with these wrappers. For example,
2430             * c:and_v(X,Y) produces the same script as and_v(X,c:Y). */
2431            // c: wrapper
2432            if (in[0].first == OP_CHECKSIG) {
2433                ++in;
2434                to_parse.emplace_back(DecodeContext::CHECK, -1, -1);
2435                to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2436                break;
2437            }
2438            // v: wrapper
2439            if (in[0].first == OP_VERIFY) {
2440                ++in;
2441                to_parse.emplace_back(DecodeContext::VERIFY, -1, -1);
2442                to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2443                break;
2444            }
2445            // n: wrapper
2446            if (in[0].first == OP_0NOTEQUAL) {
2447                ++in;
2448                to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1);
2449                to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2450                break;
2451            }
2452            // Thresh
2453            if (last - in >= 3 && in[0].first == OP_EQUAL && (num = ParseScriptNumber(in[1]))) {
2454                if (*num < 1) return {};
2455                in += 2;
2456                to_parse.emplace_back(DecodeContext::THRESH_W, 0, *num);
2457                break;
2458            }
2459            // OP_ENDIF can be WRAP_J, WRAP_D, ANDOR, OR_C, OR_D, or OR_I
2460            if (in[0].first == OP_ENDIF) {
2461                ++in;
2462                to_parse.emplace_back(DecodeContext::ENDIF, -1, -1);
2463                to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2464                break;
2465            }
2466            /** In and_b and or_b nodes, we only look for SINGLE_BKV_EXPR, because
2467             * or_b(and_v(X,Y),Z) has script [X] [Y] [Z] OP_BOOLOR, the same as
2468             * and_v(X,or_b(Y,Z)). In this example, the former of these is invalid as
2469             * miniscript, while the latter is valid. So we leave the and_v "outside"
2470             * while decoding. */
2471            // and_b
2472            if (in[0].first == OP_BOOLAND) {
2473                ++in;
2474                to_parse.emplace_back(DecodeContext::AND_B, -1, -1);
2475                to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2476                to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2477                break;
2478            }
2479            // or_b
2480            if (in[0].first == OP_BOOLOR) {
2481                ++in;
2482                to_parse.emplace_back(DecodeContext::OR_B, -1, -1);
2483                to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2484                to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2485                break;
2486            }
2487            // Unrecognised expression
2488            return {};
2489        }
2490        case DecodeContext::BKV_EXPR: {
2491            to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1);
2492            to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2493            break;
2494        }
2495        case DecodeContext::W_EXPR: {
2496            // a: wrapper
2497            if (in >= last) return {};
2498            if (in[0].first == OP_FROMALTSTACK) {
2499                ++in;
2500                to_parse.emplace_back(DecodeContext::ALT, -1, -1);