Inside Bitcoin

1501    {
1502        // We cannot use a lambda here, as lambdas are non assignable, and the set operations
1503        // below require moving the comparators around.
1504        struct Comp {
1505            const Ctx* ctx_ptr;
1506            Comp(const Ctx& ctx) : ctx_ptr(&ctx) {}
1507            bool operator()(const Key& a, const Key& b) const { return ctx_ptr->KeyCompare(a, b); }
1508        };
1509
1510        // state in the recursive computation:
1511        // - std::nullopt means "this node has duplicates"
1512        // - an std::set means "this node has no duplicate keys, and they are: ...".
1513        using keyset = std::set<Key, Comp>;
1514        using state = std::optional<keyset>;
1515
1516        auto upfn = [&ctx](const Node& node, std::span<state> subs) -> state {
1517            // If this node is already known to have duplicates, nothing left to do.
1518            if (node.has_duplicate_keys.has_value() && *node.has_duplicate_keys) return {};
1519
1520            // Check if one of the children is already known to have duplicates.
1521            for (auto& sub : subs) {
1522                if (!sub.has_value()) {
1523                    node.has_duplicate_keys = true;
1524                    return {};
1525                }
1526            }
1527
1528            // Start building the set of keys involved in this node and children.
1529            // Start by keys in this node directly.
1530            size_t keys_count = node.keys.size();
1531            keyset key_set{node.keys.begin(), node.keys.end(), Comp(ctx)};
1532            if (key_set.size() != keys_count) {
1533                // It already has duplicates; bail out.
1534                node.has_duplicate_keys = true;
1535                return {};
1536            }
1537
1538            // Merge the keys from the children into this set.
1539            for (auto& sub : subs) {
1540                keys_count += sub->size();
1541                // Small optimization: std::set::merge is linear in the size of the second arg but
1542                // logarithmic in the size of the first.
1543                if (key_set.size() < sub->size()) std::swap(key_set, *sub);
1544                key_set.merge(*sub);
1545                if (key_set.size() != keys_count) {
1546                    node.has_duplicate_keys = true;
1547                    return {};
1548                }
1549            }
1550
1551            node.has_duplicate_keys = false;
1552            return key_set;
1553        };
1554
1555        TreeEval<state>(upfn);
1556    }
1557
1558    //! Return the size of the script for this expression (faster than ToScript().size()).
1559    size_t ScriptSize() const { return scriptlen; }
1560
1561    //! Return the maximum number of ops needed to satisfy this script non-malleably.
1562    std::optional<uint32_t> GetOps() const {
1563        if (!ops.sat.Valid()) return {};
1564        return ops.count + ops.sat.Value();
1565    }
1566
1567    //! Return the number of ops in the script (not counting the dynamic ones that depend on execution).
1568    uint32_t GetStaticOps() const { return ops.count; }
1569
1570    //! Check the ops limit of this script against the consensus limit.
1571    bool CheckOpsLimit() const {
1572        if (IsTapscript(m_script_ctx)) return true;
1573        if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT;
1574        return true;
1575    }
1576
1577    /** Whether this node is of type B, K or W. (That is, anything but V.) */
1578    bool IsBKW() const {
1579        return !((GetType() & "BKW"_mst) == ""_mst);
1580    }
1581
1582    /** Return the maximum number of stack elements needed to satisfy this script non-malleably. */
1583    std::optional<uint32_t> GetStackSize() const {
1584        if (!ss.Sat().Valid()) return {};
1585        return ss.Sat().NetDiff() + static_cast<int32_t>(IsBKW());
1586    }
1587
1588    //! Return the maximum size of the stack during execution of this script.
1589    std::optional<uint32_t> GetExecStackSize() const {
1590        if (!ss.Sat().Valid()) return {};
1591        return ss.Sat().Exec() + static_cast<int32_t>(IsBKW());
1592    }
1593
1594    //! Check the maximum stack size for this script against the policy limit.
1595    bool CheckStackSize() const {
1596        // Since in Tapscript there is no standardness limit on the script and witness sizes, we may run
1597        // into the maximum stack size while executing the script. Make sure it doesn't happen.
1598        if (IsTapscript(m_script_ctx)) {
1599            if (const auto exec_ss = GetExecStackSize()) return exec_ss <= MAX_STACK_SIZE;
1600            return true;
1601        }
1602        if (const auto ss = GetStackSize()) return *ss <= MAX_STANDARD_P2WSH_STACK_ITEMS;
1603        return true;
1604    }
1605
1606    //! Whether no satisfaction exists for this node.
1607    bool IsNotSatisfiable() const { return !GetStackSize(); }
1608
1609    /** Return the maximum size in bytes of a witness to satisfy this script non-malleably. Note this does
1610     * not include the witness script push. */
1611    std::optional<uint32_t> GetWitnessSize() const {
1612        if (!ws.sat.Valid()) return {};
1613        return ws.sat.Value();
1614    }
1615
1616    //! Return the expression type.
1617    Type GetType() const { return typ; }
1618
1619    //! Return the script context for this node.
1620    MiniscriptContext GetMsCtx() const { return m_script_ctx; }
1621
1622    //! Find an insane subnode which has no insane children. Nullptr if there is none.
1623    const Node* FindInsaneSub() const {
1624        return TreeEval<const Node*>([](const Node& node, std::span<const Node*> subs) -> const Node* {
1625            for (auto& sub: subs) if (sub) return sub;
1626            if (!node.IsSaneSubexpression()) return &node;
1627            return nullptr;
1628        });
1629    }
1630
1631    //! Determine whether a Miniscript node is satisfiable. fn(node) will be invoked for all
1632    //! key, time, and hashing nodes, and should return their satisfiability.
1633    template<typename F>
1634    bool IsSatisfiable(F fn) const
1635    {
1636        // TreeEval() doesn't support bool as NodeType, so use int instead.
1637        return TreeEval<int>([&fn](const Node& node, std::span<int> subs) -> bool {
1638            switch (node.fragment) {
1639                case Fragment::JUST_0:
1640                    return false;
1641                case Fragment::JUST_1:
1642                    return true;
1643                case Fragment::PK_K:
1644                case Fragment::PK_H:
1645                case Fragment::MULTI:
1646                case Fragment::MULTI_A:
1647                case Fragment::AFTER:
1648                case Fragment::OLDER:
1649                case Fragment::HASH256:
1650                case Fragment::HASH160:
1651                case Fragment::SHA256:
1652                case Fragment::RIPEMD160:
1653                    return bool{fn(node)};
1654                case Fragment::ANDOR:
1655                    return (subs[0] && subs[1]) || subs[2];
1656                case Fragment::AND_V:
1657                case Fragment::AND_B:
1658                    return subs[0] && subs[1];
1659                case Fragment::OR_B:
1660                case Fragment::OR_C:
1661                case Fragment::OR_D:
1662                case Fragment::OR_I:
1663                    return subs[0] || subs[1];
1664                case Fragment::THRESH:
1665                    return static_cast<uint32_t>(std::count(subs.begin(), subs.end(), true)) >= node.k;
1666                default: // wrappers
1667                    assert(subs.size() >= 1);
1668                    CHECK_NONFATAL(subs.size() == 1);
1669                    return subs[0];
1670            }
1671        });
1672    }
1673
1674    //! Check whether this node is valid at all.
1675    bool IsValid() const {
1676        if (GetType() == ""_mst) return false;
1677        return ScriptSize() <= internal::MaxScriptSize(m_script_ctx);
1678    }
1679
1680    //! Check whether this node is valid as a script on its own.
1681    bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; }
1682
1683    //! Check whether this script can always be satisfied in a non-malleable way.
1684    bool IsNonMalleable() const { return GetType() << "m"_mst; }
1685
1686    //! Check whether this script always needs a signature.
1687    bool NeedsSignature() const { return GetType() << "s"_mst; }
1688
1689    //! Check whether there is no satisfaction path that contains both timelocks and heightlocks
1690    bool CheckTimeLocksMix() const { return GetType() << "k"_mst; }
1691
1692    //! Check whether there is no duplicate key across this fragment and all its sub-fragments.
1693    bool CheckDuplicateKey() const { return has_duplicate_keys && !*has_duplicate_keys; }
1694
1695    //! Whether successful non-malleable satisfactions are guaranteed to be valid.
1696    bool ValidSatisfactions() const { return IsValid() && CheckOpsLimit() && CheckStackSize(); }
1697
1698    //! Whether the apparent policy of this node matches its script semantics. Doesn't guarantee it is a safe script on its own.
1699    bool IsSaneSubexpression() const { return ValidSatisfactions() && IsNonMalleable() && CheckTimeLocksMix() && CheckDuplicateKey(); }
1700
1701    //! Check whether this node is safe as a script on its own.
1702    bool IsSane() const { return IsValidTopLevel() && IsSaneSubexpression() && NeedsSignature(); }
1703
1704    //! Produce a witness for this script, if possible and given the information available in the context.
1705    //! The non-malleable satisfaction is guaranteed to be valid if it exists, and ValidSatisfaction()
1706    //! is true. If IsSane() holds, this satisfaction is guaranteed to succeed in case the node's
1707    //! conditions are satisfied (private keys and hash preimages available, locktimes satisfied).
1708    template<typename Ctx>
1709    Availability Satisfy(const Ctx& ctx, std::vector<std::vector<unsigned char>>& stack, bool nonmalleable = true) const {
1710        auto ret = ProduceInput(ctx);
1711        if (nonmalleable && (ret.sat.malleable || !ret.sat.has_sig)) return Availability::NO;
1712        stack = std::move(ret.sat.stack);
1713        return ret.sat.available;
1714    }
1715
1716    //! Equality testing.
1717    bool operator==(const Node<Key>& arg) const { return Compare(*this, arg) == 0; }
1718
1719    // Constructors with various argument combinations, which bypass the duplicate key check.
1720    Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Node> sub, std::vector<unsigned char> arg, uint32_t val = 0)
1721        : fragment(nt), k(val), data(std::move(arg)), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1722    Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0)
1723        : fragment(nt), k(val), data(std::move(arg)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1724    Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Node> sub, std::vector<Key> key, uint32_t val = 0)
1725        : fragment(nt), k(val), keys(std::move(key)), m_script_ctx{script_ctx}, subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1726    Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Key> key, uint32_t val = 0)
1727        : fragment(nt), k(val), keys(std::move(key)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1728    Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Node> sub, uint32_t val = 0)
1729        : fragment(nt), k(val), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1730    Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, uint32_t val = 0)
1731        : fragment(nt), k(val), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1732
1733    // Constructors with various argument combinations, which do perform the duplicate key check.
1734    template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Node> sub, std::vector<unsigned char> arg, uint32_t val = 0)
1735        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(arg), val) { DuplicateKeyCheck(ctx); }
1736    template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0)
1737        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(arg), val) { DuplicateKeyCheck(ctx);}
1738    template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Node> sub, std::vector<Key> key, uint32_t val = 0)
1739        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(key), val) { DuplicateKeyCheck(ctx); }
1740    template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Key> key, uint32_t val = 0)
1741        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(key), val) { DuplicateKeyCheck(ctx); }
1742    template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Node> sub, uint32_t val = 0)
1743        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), val) { DuplicateKeyCheck(ctx); }
1744    template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, uint32_t val = 0)
1745        : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, val) { DuplicateKeyCheck(ctx); }
1746
1747    // Delete copy constructor and assignment operator, use Clone() instead
1748    Node(const Node&) = delete;
1749    Node& operator=(const Node&) = delete;
1750