Inside Bitcoin

501        default:
502            break;
503    }
504    return {};
505}
506
507/* This structure contains a table which for each "target" Type a list of recipes
508 * to construct it, automatically inferred from the behavior of ComputeType.
509 * Note that the Types here are not the final types of the constructed Nodes, but
510 * just the subset that are required. For example, a recipe for the "Bo" type
511 * might construct a "Bondu" sha256() NodeInfo, but cannot construct a "Bz" older().
512 * Each recipe is a Fragment together with a list of required types for its subnodes.
513 */
514struct SmartInfo
515{
516    using recipe = std::pair<Fragment, std::vector<Type>>;
517    std::map<Type, std::vector<recipe>> wsh_table, tap_table;
518
519    void Init()
520    {
521        Init(wsh_table, MsCtx::P2WSH);
522        Init(tap_table, MsCtx::TAPSCRIPT);
523    }
524
525    void Init(std::map<Type, std::vector<recipe>>& table, MsCtx script_ctx)
526    {
527        /* Construct a set of interesting type requirements to reason with (sections of BKVWzondu). */
528        std::vector<Type> types;
529        for (int base = 0; base < 4; ++base) { /* select from B,K,V,W */
530            Type type_base = base == 0 ? "B"_mst : base == 1 ? "K"_mst : base == 2 ? "V"_mst : "W"_mst;
531            for (int zo = 0; zo < 3; ++zo) { /* select from z,o,(none) */
532                Type type_zo = zo == 0 ? "z"_mst : zo == 1 ? "o"_mst : ""_mst;
533                for (int n = 0; n < 2; ++n) { /* select from (none),n */
534                    if (zo == 0 && n == 1) continue; /* z conflicts with n */
535                    if (base == 3 && n == 1) continue; /* W conflicts with n */
536                    Type type_n = n == 0 ? ""_mst : "n"_mst;
537                    for (int d = 0; d < 2; ++d) { /* select from (none),d */
538                        if (base == 2 && d == 1) continue; /* V conflicts with d */
539                        Type type_d = d == 0 ? ""_mst : "d"_mst;
540                        for (int u = 0; u < 2; ++u) { /* select from (none),u */
541                            if (base == 2 && u == 1) continue; /* V conflicts with u */
542                            Type type_u = u == 0 ? ""_mst : "u"_mst;
543                            Type type = type_base | type_zo | type_n | type_d | type_u;
544                            types.push_back(type);
545                        }
546                    }
547                }
548            }
549        }
550
551        /* We define a recipe a to be a super-recipe of recipe b if they use the same
552         * fragment, the same number of subexpressions, and each of a's subexpression
553         * types is a supertype of the corresponding subexpression type of b.
554         * Within the set of recipes for the construction of a given type requirement,
555         * no recipe should be a super-recipe of another (as the super-recipe is
556         * applicable in every place the sub-recipe is, the sub-recipe is redundant). */
557        auto is_super_of = [](const recipe& a, const recipe& b) {
558            if (a.first != b.first) return false;
559            if (a.second.size() != b.second.size()) return false;
560            for (size_t i = 0; i < a.second.size(); ++i) {
561                if (!(b.second[i] << a.second[i])) return false;
562            }
563            return true;
564        };
565
566        /* Sort the type requirements. Subtypes will always sort later (e.g. Bondu will
567         * sort after Bo or Bu). As we'll be constructing recipes using these types, in
568         * order, in what follows, we'll construct super-recipes before sub-recipes.
569         * That means we never need to go back and delete a sub-recipe because a
570         * super-recipe got added. */
571        std::sort(types.begin(), types.end());
572
573        // Iterate over all possible fragments.
574        for (int fragidx = 0; fragidx <= int(Fragment::MULTI_A); ++fragidx) {
575            int sub_count = 0; //!< The minimum number of child nodes this recipe has.
576            int sub_range = 1; //!< The maximum number of child nodes for this recipe is sub_count+sub_range-1.
577            size_t data_size = 0;
578            size_t n_keys = 0;
579            uint32_t k = 0;
580            Fragment frag{fragidx};
581
582            // Only produce recipes valid in the given context.
583            if ((!miniscript::IsTapscript(script_ctx) && frag == Fragment::MULTI_A)
584                || (miniscript::IsTapscript(script_ctx) && frag == Fragment::MULTI)) {
585                continue;
586            }
587
588            // Based on the fragment, determine #subs/data/k/keys to pass to ComputeType. */
589            switch (frag) {
590                case Fragment::PK_K:
591                case Fragment::PK_H:
592                    n_keys = 1;
593                    break;
594                case Fragment::MULTI:
595                case Fragment::MULTI_A:
596                    n_keys = 1;
597                    k = 1;
598                    break;
599                case Fragment::OLDER:
600                case Fragment::AFTER:
601                    k = 1;
602                    break;
603                case Fragment::SHA256:
604                case Fragment::HASH256:
605                    data_size = 32;
606                    break;
607                case Fragment::RIPEMD160:
608                case Fragment::HASH160:
609                    data_size = 20;
610                    break;
611                case Fragment::JUST_0:
612                case Fragment::JUST_1:
613                    break;
614                case Fragment::WRAP_A:
615                case Fragment::WRAP_S:
616                case Fragment::WRAP_C:
617                case Fragment::WRAP_D:
618                case Fragment::WRAP_V:
619                case Fragment::WRAP_J:
620                case Fragment::WRAP_N:
621                    sub_count = 1;
622                    break;
623                case Fragment::AND_V:
624                case Fragment::AND_B:
625                case Fragment::OR_B:
626                case Fragment::OR_C:
627                case Fragment::OR_D:
628                case Fragment::OR_I:
629                    sub_count = 2;
630                    break;
631                case Fragment::ANDOR:
632                    sub_count = 3;
633                    break;
634                case Fragment::THRESH:
635                    // Thresh logic is executed for 1 and 2 arguments. Larger numbers use ad-hoc code to extend.
636                    sub_count = 1;
637                    sub_range = 2;
638                    k = 1;
639                    break;
640            }
641
642            // Iterate over the number of subnodes (sub_count...sub_count+sub_range-1).
643            std::vector<Type> subt;
644            for (int subs = sub_count; subs < sub_count + sub_range; ++subs) {
645                // Iterate over the possible subnode types (at most 3).
646                for (Type x : types) {
647                    for (Type y : types) {
648                        for (Type z : types) {
649                            // Compute the resulting type of a node with the selected fragment / subnode types.
650                            subt.clear();
651                            if (subs > 0) subt.push_back(x);
652                            if (subs > 1) subt.push_back(y);
653                            if (subs > 2) subt.push_back(z);
654                            Type res = miniscript::internal::ComputeType(frag, x, y, z, subt, k, data_size, subs, n_keys, script_ctx);
655                            // Continue if the result is not a valid node.
656                            if ((res << "K"_mst) + (res << "V"_mst) + (res << "B"_mst) + (res << "W"_mst) != 1) continue;
657
658                            recipe entry{frag, subt};
659                            auto super_of_entry = [&](const recipe& rec) { return is_super_of(rec, entry); };
660                            // Iterate over all supertypes of res (because if e.g. our selected fragment/subnodes result
661                            // in a Bondu, they can form a recipe that is also applicable for constructing a B, Bou, Bdu, ...).
662                            for (Type s : types) {
663                                if ((res & "BKVWzondu"_mst) << s) {
664                                    auto& recipes = table[s];
665                                    // If we don't already have a super-recipe to the new one, add it.
666                                    if (!std::any_of(recipes.begin(), recipes.end(), super_of_entry)) {
667                                        recipes.push_back(entry);
668                                    }
669                                }
670                            }
671
672                            if (subs <= 2) break;
673                        }
674                        if (subs <= 1) break;
675                    }
676                    if (subs <= 0) break;
677                }
678            }
679        }
680
681        /* Find which types are useful. The fuzzer logic only cares about constructing
682         * B,V,K,W nodes, so any type that isn't needed in any recipe (directly or
683         * indirectly) for the construction of those is uninteresting. */
684        std::set<Type> useful_types{"B"_mst, "V"_mst, "K"_mst, "W"_mst};
685        // Find the transitive closure by adding types until the set of types does not change.
686        while (true) {
687            size_t set_size = useful_types.size();
688            for (const auto& [type, recipes] : table) {
689                if (useful_types.contains(type)) {
690                    for (const auto& [_, subtypes] : recipes) {
691                        for (auto subtype : subtypes) useful_types.insert(subtype);
692                    }
693                }
694            }
695            if (useful_types.size() == set_size) break;
696        }
697        // Remove all rules that construct uninteresting types.
698        for (auto type_it = table.begin(); type_it != table.end();) {
699            if (!useful_types.contains(type_it->first)) {
700                type_it = table.erase(type_it);
701            } else {
702                ++type_it;
703            }
704        }
705
706        /* Find which types are constructible. A type is constructible if there is a leaf
707         * node recipe for constructing it, or a recipe whose subnodes are all constructible.
708         * Types can be non-constructible because they have no recipes to begin with,
709         * because they can only be constructed using recipes that involve otherwise
710         * non-constructible types, or because they require infinite recursion. */
711        std::set<Type> constructible_types{};
712        auto known_constructible = [&](Type type) { return constructible_types.contains(type); };
713        // Find the transitive closure by adding types until the set of types does not change.
714        while (true) {
715            size_t set_size = constructible_types.size();
716            // Iterate over all types we have recipes for.
717            for (const auto& [type, recipes] : table) {
718                if (!known_constructible(type)) {
719                    // For not (yet known to be) constructible types, iterate over their recipes.
720                    for (const auto& [_, subt] : recipes) {
721                        // If any recipe involves only (already known to be) constructible types,
722                        // add the recipe's type to the set.
723                        if (std::all_of(subt.begin(), subt.end(), known_constructible)) {
724                            constructible_types.insert(type);
725                            break;
726                        }
727                    }
728                }
729            }
730            if (constructible_types.size() == set_size) break;
731        }
732        for (auto type_it = table.begin(); type_it != table.end();) {
733            // Remove all recipes which involve non-constructible types.
734            type_it->second.erase(std::remove_if(type_it->second.begin(), type_it->second.end(),
735                [&](const recipe& rec) {
736                    return !std::all_of(rec.second.begin(), rec.second.end(), known_constructible);
737                }), type_it->second.end());
738            // Delete types entirely which have no recipes left.
739            if (type_it->second.empty()) {
740                type_it = table.erase(type_it);
741            } else {
742                ++type_it;
743            }
744        }
745
746        for (auto& [type, recipes] : table) {
747            // Sort recipes for determinism, and place those using fewer subnodes first.
748            // This avoids runaway expansion (when reaching the end of the fuzz input,
749            // all zeroes are read, resulting in the first available recipe being picked).
750            std::sort(recipes.begin(), recipes.end(),