Inside Bitcoin

751            [](DummyState, const Node&, size_t) { return DummyState{}; },
752            [&upfn](DummyState, const Node& node, std::span<Result> subs) {
753                Result res{upfn(node, subs)};
754                return std::optional<Result>(std::move(res));
755            }
756        ));
757    }
758
759    /** Compare two miniscript subtrees, using a non-recursive algorithm. */
760    friend int Compare(const Node<Key>& node1, const Node<Key>& node2)
761    {
762        std::vector<std::pair<const Node<Key>&, const Node<Key>&>> queue;
763        queue.emplace_back(node1, node2);
764        while (!queue.empty()) {
765            const auto& [a, b] = queue.back();
766            queue.pop_back();
767            if (std::tie(a.fragment, a.k, a.keys, a.data) < std::tie(b.fragment, b.k, b.keys, b.data)) return -1;
768            if (std::tie(b.fragment, b.k, b.keys, b.data) < std::tie(a.fragment, a.k, a.keys, a.data)) return 1;
769            if (a.subs.size() < b.subs.size()) return -1;
770            if (b.subs.size() < a.subs.size()) return 1;
771            size_t n = a.subs.size();
772            for (size_t i = 0; i < n; ++i) {
773                queue.emplace_back(a.subs[n - 1 - i], b.subs[n - 1 - i]);
774            }
775        }
776        return 0;
777    }
778
779    //! Compute the type for this miniscript.
780    Type CalcType() const {
781        using namespace internal;
782
783        // THRESH has a variable number of subexpressions
784        std::vector<Type> sub_types;
785        if (fragment == Fragment::THRESH) {
786            for (const auto& sub : subs) sub_types.push_back(sub.GetType());
787        }
788        // All other nodes than THRESH can be computed just from the types of the 0-3 subexpressions.
789        Type x = subs.size() > 0 ? subs[0].GetType() : ""_mst;
790        Type y = subs.size() > 1 ? subs[1].GetType() : ""_mst;
791        Type z = subs.size() > 2 ? subs[2].GetType() : ""_mst;
792
793        return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size(), m_script_ctx));
794    }
795
796public:
797    template<typename Ctx>
798    CScript ToScript(const Ctx& ctx) const
799    {
800        // To construct the CScript for a Miniscript object, we use the TreeEval algorithm.
801        // The State is a boolean: whether or not the node's script expansion is followed
802        // by an OP_VERIFY (which may need to be combined with the last script opcode).
803        auto downfn = [](bool verify, const Node& node, size_t index) {
804            // For WRAP_V, the subexpression is certainly followed by OP_VERIFY.
805            if (node.fragment == Fragment::WRAP_V) return true;
806            // The subexpression of WRAP_S, and the last subexpression of AND_V
807            // inherit the followed-by-OP_VERIFY property from the parent.
808            if (node.fragment == Fragment::WRAP_S ||
809                (node.fragment == Fragment::AND_V && index == 1)) return verify;
810            return false;
811        };
812        // The upward function computes for a node, given its followed-by-OP_VERIFY status
813        // and the CScripts of its child nodes, the CScript of the node.
814        const bool is_tapscript{IsTapscript(m_script_ctx)};
815        auto upfn = [&ctx, is_tapscript](bool verify, const Node& node, std::span<CScript> subs) -> CScript {
816            switch (node.fragment) {
817                case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0]));
818                case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY);
819                case Fragment::OLDER: return BuildScript(node.k, OP_CHECKSEQUENCEVERIFY);
820                case Fragment::AFTER: return BuildScript(node.k, OP_CHECKLOCKTIMEVERIFY);
821                case Fragment::SHA256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_SHA256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
822                case Fragment::RIPEMD160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_RIPEMD160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
823                case Fragment::HASH256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
824                case Fragment::HASH160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
825                case Fragment::WRAP_A: return BuildScript(OP_TOALTSTACK, subs[0], OP_FROMALTSTACK);
826                case Fragment::WRAP_S: return BuildScript(OP_SWAP, subs[0]);
827                case Fragment::WRAP_C: return BuildScript(std::move(subs[0]), verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG);
828                case Fragment::WRAP_D: return BuildScript(OP_DUP, OP_IF, subs[0], OP_ENDIF);
829                case Fragment::WRAP_V: {
830                    if (node.subs[0].GetType() << "x"_mst) {
831                        return BuildScript(std::move(subs[0]), OP_VERIFY);
832                    } else {
833                        return std::move(subs[0]);
834                    }
835                }
836                case Fragment::WRAP_J: return BuildScript(OP_SIZE, OP_0NOTEQUAL, OP_IF, subs[0], OP_ENDIF);
837                case Fragment::WRAP_N: return BuildScript(std::move(subs[0]), OP_0NOTEQUAL);
838                case Fragment::JUST_1: return BuildScript(OP_1);
839                case Fragment::JUST_0: return BuildScript(OP_0);
840                case Fragment::AND_V: return BuildScript(std::move(subs[0]), subs[1]);
841                case Fragment::AND_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLAND);
842                case Fragment::OR_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLOR);
843                case Fragment::OR_D: return BuildScript(std::move(subs[0]), OP_IFDUP, OP_NOTIF, subs[1], OP_ENDIF);
844                case Fragment::OR_C: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[1], OP_ENDIF);
845                case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
846                case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
847                case Fragment::MULTI: {
848                    CHECK_NONFATAL(!is_tapscript);
849                    CScript script = BuildScript(node.k);
850                    for (const auto& key : node.keys) {
851                        script = BuildScript(std::move(script), ctx.ToPKBytes(key));
852                    }
853                    return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG);
854                }
855                case Fragment::MULTI_A: {
856                    CHECK_NONFATAL(is_tapscript);
857                    CScript script = BuildScript(ctx.ToPKBytes(*node.keys.begin()), OP_CHECKSIG);
858                    for (auto it = node.keys.begin() + 1; it != node.keys.end(); ++it) {
859                        script = BuildScript(std::move(script), ctx.ToPKBytes(*it), OP_CHECKSIGADD);
860                    }
861                    return BuildScript(std::move(script), node.k, verify ? OP_NUMEQUALVERIFY : OP_NUMEQUAL);
862                }
863                case Fragment::THRESH: {
864                    CScript script = std::move(subs[0]);
865                    for (size_t i = 1; i < subs.size(); ++i) {
866                        script = BuildScript(std::move(script), subs[i], OP_ADD);
867                    }
868                    return BuildScript(std::move(script), node.k, verify ? OP_EQUALVERIFY : OP_EQUAL);
869                }
870            }
871            assert(false);
872        };
873        return TreeEval<CScript>(false, downfn, upfn);
874    }
875
876    template<typename CTx>
877    std::optional<std::string> ToString(const CTx& ctx) const {
878        bool dummy{false};
879        return ToString(ctx, dummy);
880    }
881
882    template<typename CTx>
883    std::optional<std::string> ToString(const CTx& ctx, bool& has_priv_key) const {
884        // To construct the std::string representation for a Miniscript object, we use
885        // the TreeEvalMaybe algorithm. The State is a boolean: whether the parent node is a
886        // wrapper. If so, non-wrapper expressions must be prefixed with a ":".
887        auto downfn = [](bool, const Node& node, size_t) {
888            return (node.fragment == Fragment::WRAP_A || node.fragment == Fragment::WRAP_S ||
889                    node.fragment == Fragment::WRAP_D || node.fragment == Fragment::WRAP_V ||
890                    node.fragment == Fragment::WRAP_J || node.fragment == Fragment::WRAP_N ||
891                    node.fragment == Fragment::WRAP_C ||
892                    (node.fragment == Fragment::AND_V && node.subs[1].fragment == Fragment::JUST_1) ||
893                    (node.fragment == Fragment::OR_I && node.subs[0].fragment == Fragment::JUST_0) ||
894                    (node.fragment == Fragment::OR_I && node.subs[1].fragment == Fragment::JUST_0));
895        };
896        auto toString = [&ctx, &has_priv_key](Key key) -> std::optional<std::string> {
897            bool fragment_has_priv_key{false};
898            auto key_str{ctx.ToString(key, fragment_has_priv_key)};
899            if (key_str) has_priv_key = has_priv_key || fragment_has_priv_key;
900            return key_str;
901        };
902        // The upward function computes for a node, given whether its parent is a wrapper,
903        // and the string representations of its child nodes, the string representation of the node.
904        const bool is_tapscript{IsTapscript(m_script_ctx)};
905        auto upfn = [is_tapscript, &toString](bool wrapped, const Node& node, std::span<std::string> subs) -> std::optional<std::string> {
906            std::string ret = wrapped ? ":" : "";
907
908            switch (node.fragment) {
909                case Fragment::WRAP_A: return "a" + std::move(subs[0]);
910                case Fragment::WRAP_S: return "s" + std::move(subs[0]);
911                case Fragment::WRAP_C:
912                    if (node.subs[0].fragment == Fragment::PK_K) {
913                        // pk(K) is syntactic sugar for c:pk_k(K)
914                        auto key_str = toString(node.subs[0].keys[0]);
915                        if (!key_str) return {};
916                        return std::move(ret) + "pk(" + std::move(*key_str) + ")";
917                    }
918                    if (node.subs[0].fragment == Fragment::PK_H) {
919                        // pkh(K) is syntactic sugar for c:pk_h(K)
920                        auto key_str = toString(node.subs[0].keys[0]);
921                        if (!key_str) return {};
922                        return std::move(ret) + "pkh(" + std::move(*key_str) + ")";
923                    }
924                    return "c" + std::move(subs[0]);
925                case Fragment::WRAP_D: return "d" + std::move(subs[0]);
926                case Fragment::WRAP_V: return "v" + std::move(subs[0]);
927                case Fragment::WRAP_J: return "j" + std::move(subs[0]);
928                case Fragment::WRAP_N: return "n" + std::move(subs[0]);
929                case Fragment::AND_V:
930                    // t:X is syntactic sugar for and_v(X,1).
931                    if (node.subs[1].fragment == Fragment::JUST_1) return "t" + std::move(subs[0]);
932                    break;
933                case Fragment::OR_I:
934                    if (node.subs[0].fragment == Fragment::JUST_0) return "l" + std::move(subs[1]);
935                    if (node.subs[1].fragment == Fragment::JUST_0) return "u" + std::move(subs[0]);
936                    break;
937                default: break;
938            }
939            switch (node.fragment) {
940                case Fragment::PK_K: {
941                    auto key_str = toString(node.keys[0]);
942                    if (!key_str) return {};
943                    return std::move(ret) + "pk_k(" + std::move(*key_str) + ")";
944                }
945                case Fragment::PK_H: {
946                    auto key_str = toString(node.keys[0]);
947                    if (!key_str) return {};
948                    return std::move(ret) + "pk_h(" + std::move(*key_str) + ")";
949                }
950                case Fragment::AFTER: return std::move(ret) + "after(" + util::ToString(node.k) + ")";
951                case Fragment::OLDER: return std::move(ret) + "older(" + util::ToString(node.k) + ")";
952                case Fragment::HASH256: return std::move(ret) + "hash256(" + HexStr(node.data) + ")";
953                case Fragment::HASH160: return std::move(ret) + "hash160(" + HexStr(node.data) + ")";
954                case Fragment::SHA256: return std::move(ret) + "sha256(" + HexStr(node.data) + ")";
955                case Fragment::RIPEMD160: return std::move(ret) + "ripemd160(" + HexStr(node.data) + ")";
956                case Fragment::JUST_1: return std::move(ret) + "1";
957                case Fragment::JUST_0: return std::move(ret) + "0";
958                case Fragment::AND_V: return std::move(ret) + "and_v(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
959                case Fragment::AND_B: return std::move(ret) + "and_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
960                case Fragment::OR_B: return std::move(ret) + "or_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
961                case Fragment::OR_D: return std::move(ret) + "or_d(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
962                case Fragment::OR_C: return std::move(ret) + "or_c(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
963                case Fragment::OR_I: return std::move(ret) + "or_i(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
964                case Fragment::ANDOR:
965                    // and_n(X,Y) is syntactic sugar for andor(X,Y,0).
966                    if (node.subs[2].fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
967                    return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
968                case Fragment::MULTI: {
969                    CHECK_NONFATAL(!is_tapscript);
970                    auto str = std::move(ret) + "multi(" + util::ToString(node.k);
971                    for (const auto& key : node.keys) {
972                        auto key_str = toString(key);
973                        if (!key_str) return {};
974                        str += "," + std::move(*key_str);
975                    }
976                    return std::move(str) + ")";
977                }
978                case Fragment::MULTI_A: {
979                    CHECK_NONFATAL(is_tapscript);
980                    auto str = std::move(ret) + "multi_a(" + util::ToString(node.k);
981                    for (const auto& key : node.keys) {
982                        auto key_str = toString(key);
983                        if (!key_str) return {};
984                        str += "," + std::move(*key_str);
985                    }
986                    return std::move(str) + ")";
987                }
988                case Fragment::THRESH: {
989                    auto str = std::move(ret) + "thresh(" + util::ToString(node.k);
990                    for (auto& sub : subs) {
991                        str += "," + std::move(sub);
992                    }
993                    return std::move(str) + ")";
994                }
995                default: break;
996            }
997            assert(false);
998        };
999
1000        return TreeEvalMaybe<std::string>(false, downfn, upfn);