Inside Bitcoin

1751    // subs is movable, circumventing recursion, so these are permitted.
1752    Node(Node&&) noexcept = default;
1753    Node& operator=(Node&&) noexcept = default;
1754};
1755
1756namespace internal {
1757
1758enum class ParseContext {
1759    /** An expression which may be begin with wrappers followed by a colon. */
1760    WRAPPED_EXPR,
1761    /** A miniscript expression which does not begin with wrappers. */
1762    EXPR,
1763
1764    /** SWAP wraps the top constructed node with s: */
1765    SWAP,
1766    /** ALT wraps the top constructed node with a: */
1767    ALT,
1768    /** CHECK wraps the top constructed node with c: */
1769    CHECK,
1770    /** DUP_IF wraps the top constructed node with d: */
1771    DUP_IF,
1772    /** VERIFY wraps the top constructed node with v: */
1773    VERIFY,
1774    /** NON_ZERO wraps the top constructed node with j: */
1775    NON_ZERO,
1776    /** ZERO_NOTEQUAL wraps the top constructed node with n: */
1777    ZERO_NOTEQUAL,
1778    /** WRAP_U will construct an or_i(X,0) node from the top constructed node. */
1779    WRAP_U,
1780    /** WRAP_T will construct an and_v(X,1) node from the top constructed node. */
1781    WRAP_T,
1782
1783    /** AND_N will construct an andor(X,Y,0) node from the last two constructed nodes. */
1784    AND_N,
1785    /** AND_V will construct an and_v node from the last two constructed nodes. */
1786    AND_V,
1787    /** AND_B will construct an and_b node from the last two constructed nodes. */
1788    AND_B,
1789    /** ANDOR will construct an andor node from the last three constructed nodes. */
1790    ANDOR,
1791    /** OR_B will construct an or_b node from the last two constructed nodes. */
1792    OR_B,
1793    /** OR_C will construct an or_c node from the last two constructed nodes. */
1794    OR_C,
1795    /** OR_D will construct an or_d node from the last two constructed nodes. */
1796    OR_D,
1797    /** OR_I will construct an or_i node from the last two constructed nodes. */
1798    OR_I,
1799
1800    /** THRESH will read a wrapped expression, and then look for a COMMA. If
1801     * no comma follows, it will construct a thresh node from the appropriate
1802     * number of constructed children. Otherwise, it will recurse with another
1803     * THRESH. */
1804    THRESH,
1805
1806    /** COMMA expects the next element to be ',' and fails if not. */
1807    COMMA,
1808    /** CLOSE_BRACKET expects the next element to be ')' and fails if not. */
1809    CLOSE_BRACKET,
1810};
1811
1812int FindNextChar(std::span<const char> in, char m);
1813
1814/** Parse a key expression fully contained within a fragment with the name given by 'func' */
1815template<typename Key, typename Ctx>
1816std::optional<Key> ParseKey(const std::string& func, std::span<const char>& in, const Ctx& ctx)
1817{
1818    std::span<const char> expr = script::Expr(in);
1819    if (!script::Func(func, expr)) return {};
1820    return ctx.FromString(expr);
1821}
1822
1823/** Parse a hex string fully contained within a fragment with the name given by 'func' */
1824inline std::optional<std::vector<unsigned char>> ParseHexStr(const std::string& func, std::span<const char>& in, const size_t expected_size)
1825{
1826    std::span<const char> expr = script::Expr(in);
1827    if (!script::Func(func, expr)) return {};
1828    std::string val = std::string(expr.begin(), expr.end());
1829    if (!IsHex(val)) return {};
1830    auto hash = ParseHex(val);
1831    if (hash.size() != expected_size) return {};
1832    return hash;
1833}
1834
1835/** BuildBack pops the last two elements off `constructed` and wraps them in the specified Fragment */
1836template<typename Key>
1837void BuildBack(const MiniscriptContext script_ctx, Fragment nt, std::vector<Node<Key>>& constructed, const bool reverse = false)
1838{
1839    Node<Key> child{std::move(constructed.back())};
1840    constructed.pop_back();
1841    if (reverse) {
1842        constructed.back() = Node<Key>{internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(child), std::move(constructed.back()))};
1843    } else {
1844        constructed.back() = Node<Key>{internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(constructed.back()), std::move(child))};
1845    }
1846}
1847
1848/**
1849 * Parse a miniscript from its textual descriptor form.
1850 * This does not check whether the script is valid, let alone sane. The caller is expected to use
1851 * the `IsValidTopLevel()` and `IsSaneTopLevel()` to check for these properties on the node.
1852 */
1853template <typename Key, typename Ctx>
1854inline std::optional<Node<Key>> Parse(std::span<const char> in, const Ctx& ctx)
1855{
1856    using namespace script;
1857
1858    // Account for the minimum script size for all parsed fragments so far. It "borrows" 1
1859    // script byte from all leaf nodes, counting it instead whenever a space for a recursive
1860    // expression is added (through andor, and_*, or_*, thresh). This guarantees that all fragments
1861    // increment the script_size by at least one, except for:
1862    // - "0", "1": these leafs are only a single byte, so their subtracted-from increment is 0.
1863    //   This is not an issue however, as "space" for them has to be created by combinators,
1864    //   which do increment script_size.
1865    // - "v:": the v wrapper adds nothing as in some cases it results in no opcode being added
1866    //   (instead transforming another opcode into its VERIFY form). However, the v: wrapper has
1867    //   to be interleaved with other fragments to be valid, so this is not a concern.
1868    size_t script_size{1};
1869    size_t max_size{internal::MaxScriptSize(ctx.MsContext())};
1870
1871    // The two integers are used to hold state for thresh()
1872    std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
1873    std::vector<Node<Key>> constructed;
1874
1875    to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1876
1877    // Parses a multi() or multi_a() from its string representation. Returns false on parsing error.
1878    const auto parse_multi_exp = [&](std::span<const char>& in, const bool is_multi_a) -> bool {
1879        const auto max_keys{is_multi_a ? MAX_PUBKEYS_PER_MULTI_A : MAX_PUBKEYS_PER_MULTISIG};
1880        const auto required_ctx{is_multi_a ? MiniscriptContext::TAPSCRIPT : MiniscriptContext::P2WSH};
1881        if (ctx.MsContext() != required_ctx) return false;
1882        // Get threshold
1883        int next_comma = FindNextChar(in, ',');
1884        if (next_comma < 1) return false;
1885        const auto k_to_integral{ToIntegral<int64_t>(std::string_view(in.data(), next_comma))};
1886        if (!k_to_integral.has_value()) return false;
1887        const int64_t k{k_to_integral.value()};
1888        in = in.subspan(next_comma + 1);
1889        // Get keys. It is compatible for both compressed and x-only keys.
1890        std::vector<Key> keys;
1891        while (next_comma != -1) {
1892            next_comma = FindNextChar(in, ',');
1893            int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
1894            if (key_length < 1) return false;
1895            std::span<const char> sp{in.begin(), in.begin() + key_length};
1896            auto key = ctx.FromString(sp);
1897            if (!key) return false;
1898            keys.push_back(std::move(*key));
1899            in = in.subspan(key_length + 1);
1900        }
1901        if (keys.size() < 1 || keys.size() > max_keys) return false;
1902        if (k < 1 || k > (int64_t)keys.size()) return false;
1903        if (is_multi_a) {
1904            // (push + xonly-key + CHECKSIG[ADD]) * n + k + OP_NUMEQUAL(VERIFY), minus one.
1905            script_size += (1 + 32 + 1) * keys.size() + BuildScript(k).size();
1906            constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), k);
1907        } else {
1908            script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
1909            constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), k);
1910        }
1911        return true;
1912    };
1913
1914    while (!to_parse.empty()) {
1915        if (script_size > max_size) return {};
1916
1917        // Get the current context we are decoding within
1918        auto [cur_context, n, k] = to_parse.back();
1919        to_parse.pop_back();
1920
1921        switch (cur_context) {
1922        case ParseContext::WRAPPED_EXPR: {
1923            std::optional<size_t> colon_index{};
1924            for (size_t i = 1; i < in.size(); ++i) {
1925                if (in[i] == ':') {
1926                    colon_index = i;
1927                    break;
1928                }
1929                if (in[i] < 'a' || in[i] > 'z') break;
1930            }
1931            // If there is no colon, this loop won't execute
1932            bool last_was_v{false};
1933            for (size_t j = 0; colon_index && j < *colon_index; ++j) {
1934                if (script_size > max_size) return {};
1935                if (in[j] == 'a') {
1936                    script_size += 2;
1937                    to_parse.emplace_back(ParseContext::ALT, -1, -1);
1938                } else if (in[j] == 's') {
1939                    script_size += 1;
1940                    to_parse.emplace_back(ParseContext::SWAP, -1, -1);
1941                } else if (in[j] == 'c') {
1942                    script_size += 1;
1943                    to_parse.emplace_back(ParseContext::CHECK, -1, -1);
1944                } else if (in[j] == 'd') {
1945                    script_size += 3;
1946                    to_parse.emplace_back(ParseContext::DUP_IF, -1, -1);
1947                } else if (in[j] == 'j') {
1948                    script_size += 4;
1949                    to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1);
1950                } else if (in[j] == 'n') {
1951                    script_size += 1;
1952                    to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1);
1953                } else if (in[j] == 'v') {
1954                    // do not permit "...vv...:"; it's not valid, and also doesn't trigger early
1955                    // failure as script_size isn't incremented.
1956                    if (last_was_v) return {};
1957                    to_parse.emplace_back(ParseContext::VERIFY, -1, -1);
1958                } else if (in[j] == 'u') {
1959                    script_size += 4;
1960                    to_parse.emplace_back(ParseContext::WRAP_U, -1, -1);
1961                } else if (in[j] == 't') {
1962                    script_size += 1;
1963                    to_parse.emplace_back(ParseContext::WRAP_T, -1, -1);
1964                } else if (in[j] == 'l') {
1965                    // The l: wrapper is equivalent to or_i(0,X)
1966                    script_size += 4;
1967                    constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0);
1968                    to_parse.emplace_back(ParseContext::OR_I, -1, -1);
1969                } else {
1970                    return {};
1971                }
1972                last_was_v = (in[j] == 'v');
1973            }
1974            to_parse.emplace_back(ParseContext::EXPR, -1, -1);
1975            if (colon_index) in = in.subspan(*colon_index + 1);
1976            break;
1977        }
1978        case ParseContext::EXPR: {
1979            if (Const("0", in)) {
1980                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0);
1981            } else if (Const("1", in)) {
1982                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1);
1983            } else if (Const("pk(", in, /*skip=*/false)) {
1984                std::optional<Key> key = ParseKey<Key, Ctx>("pk", in, ctx);
1985                if (!key) return {};
1986                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(Node<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key)))));
1987                script_size += IsTapscript(ctx.MsContext()) ? 33 : 34;
1988            } else if (Const("pkh(", in, /*skip=*/false)) {
1989                std::optional<Key> key = ParseKey<Key, Ctx>("pkh", in, ctx);
1990                if (!key) return {};
1991                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(Node<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key)))));
1992                script_size += 24;
1993            } else if (Const("pk_k(", in, /*skip=*/false)) {
1994                std::optional<Key> key = ParseKey<Key, Ctx>("pk_k", in, ctx);
1995                if (!key) return {};
1996                constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key)));
1997                script_size += IsTapscript(ctx.MsContext()) ? 32 : 33;
1998            } else if (Const("pk_h(", in, /*skip=*/false)) {
1999                std::optional<Key> key = ParseKey<Key, Ctx>("pk_h", in, ctx);
2000                if (!key) return {};