Inside Bitcoin

751                [](const recipe& a, const recipe& b) {
752                    if (a.second.size() < b.second.size()) return true;
753                    if (a.second.size() > b.second.size()) return false;
754                    return a < b;
755                }
756            );
757        }
758    }
759} SMARTINFO;
760
761/**
762 * Consume a Miniscript node from the fuzzer's output.
763 *
764 * This is similar to ConsumeNodeStable, but uses a precomputed table with permitted
765 * fragments/subnode type for each required type. It is intended to more quickly explore
766 * interesting miniscripts, at the cost of higher implementation complexity (which could
767 * cause it miss things if incorrect), and with less regard for stability of the seeds
768 * (as improvements to the tables or changes to the typing rules could invalidate
769 * everything).
770 */
771std::optional<NodeInfo> ConsumeNodeSmart(MsCtx script_ctx, FuzzedDataProvider& provider, Type type_needed) {
772    /** Table entry for the requested type. */
773    const auto& table{IsTapscript(script_ctx) ? SMARTINFO.tap_table : SMARTINFO.wsh_table};
774    auto recipes_it = table.find(type_needed);
775    assert(recipes_it != table.end());
776    /** Pick one recipe from the available ones for that type. */
777    const auto& [frag, subt] = PickValue(provider, recipes_it->second);
778
779    // Based on the fragment the recipe uses, fill in other data (k, keys, data).
780    switch (frag) {
781        case Fragment::PK_K:
782        case Fragment::PK_H:
783            return {{frag, ConsumePubKey(provider)}};
784        case Fragment::MULTI: {
785            const auto n_keys = provider.ConsumeIntegralInRange<uint8_t>(1, 20);
786            const auto k = provider.ConsumeIntegralInRange<uint8_t>(1, n_keys);
787            std::vector<CPubKey> keys{n_keys};
788            for (auto& key: keys) key = ConsumePubKey(provider);
789            return {{frag, k, std::move(keys)}};
790        }
791        case Fragment::MULTI_A: {
792            const auto n_keys = provider.ConsumeIntegralInRange<uint16_t>(1, 999);
793            const auto k = provider.ConsumeIntegralInRange<uint16_t>(1, n_keys);
794            std::vector<CPubKey> keys{n_keys};
795            for (auto& key: keys) key = ConsumePubKey(provider);
796            return {{frag, k, std::move(keys)}};
797        }
798        case Fragment::OLDER:
799        case Fragment::AFTER:
800            return {{frag, provider.ConsumeIntegralInRange<uint32_t>(1, 0x7FFFFFF)}};
801        case Fragment::SHA256:
802            return {{frag, PickValue(provider, TEST_DATA.sha256)}};
803        case Fragment::HASH256:
804            return {{frag, PickValue(provider, TEST_DATA.hash256)}};
805        case Fragment::RIPEMD160:
806            return {{frag, PickValue(provider, TEST_DATA.ripemd160)}};
807        case Fragment::HASH160:
808            return {{frag, PickValue(provider, TEST_DATA.hash160)}};
809        case Fragment::JUST_0:
810        case Fragment::JUST_1:
811        case Fragment::WRAP_A:
812        case Fragment::WRAP_S:
813        case Fragment::WRAP_C:
814        case Fragment::WRAP_D:
815        case Fragment::WRAP_V:
816        case Fragment::WRAP_J:
817        case Fragment::WRAP_N:
818        case Fragment::AND_V:
819        case Fragment::AND_B:
820        case Fragment::OR_B:
821        case Fragment::OR_C:
822        case Fragment::OR_D:
823        case Fragment::OR_I:
824        case Fragment::ANDOR:
825            return {{subt, frag}};
826        case Fragment::THRESH: {
827            uint32_t children;
828            if (subt.size() < 2) {
829                children = subt.size();
830            } else {
831                // If we hit a thresh with 2 subnodes, artificially extend it to any number
832                // (2 or larger) by replicating the type of the last subnode.
833                children = provider.ConsumeIntegralInRange<uint32_t>(2, MAX_OPS_PER_SCRIPT / 2);
834            }
835            auto k = provider.ConsumeIntegralInRange<uint32_t>(1, children);
836            std::vector<Type> subs = subt;
837            while (subs.size() < children) subs.push_back(subs.back());
838            return {{std::move(subs), frag, k}};
839        }
840    }
841
842    assert(false);
843}
844
845/**
846 * Generate a Miniscript node based on the fuzzer's input.
847 *
848 * - ConsumeNode is a function object taking a Type, and returning an std::optional<NodeInfo>.
849 * - root_type is the required type properties of the constructed Node.
850 * - strict_valid sets whether ConsumeNode is expected to guarantee a NodeInfo that results in
851 *   a Node whose Type() matches the type fed to ConsumeNode.
852 */
853template <typename F>
854std::optional<Node> GenNode(MsCtx script_ctx, F ConsumeNode, Type root_type, bool strict_valid = false)
855{
856    /** A stack of miniscript Nodes being built up. */
857    std::vector<Node> stack;
858    /** The queue of instructions. */
859    std::vector<std::pair<Type, std::optional<NodeInfo>>> todo{{root_type, {}}};
860    /** Predict the number of (static) script ops. */
861    uint32_t ops{0};
862    /** Predict the total script size (every unexplored subnode is counted as one, as every leaf is
863     *  at least one script byte). */
864    uint32_t scriptsize{1};
865
866    while (!todo.empty()) {
867        // The expected type we have to construct.
868        auto type_needed = todo.back().first;
869        if (!todo.back().second) {
870            // Fragment/children have not been decided yet. Decide them.
871            auto node_info = ConsumeNode(type_needed);
872            if (!node_info) return {};
873            // Update predicted resource limits. Since every leaf Miniscript node is at least one
874            // byte long, we move one byte from each child to their parent. A similar technique is
875            // used in the miniscript::internal::Parse function to prevent runaway string parsing.
876            scriptsize += miniscript::internal::ComputeScriptLen(node_info->fragment, ""_mst, node_info->subtypes.size(), node_info->k, node_info->subtypes.size(),
877                                                                 node_info->keys.size(), script_ctx) - 1;
878            if (scriptsize > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
879            switch (node_info->fragment) {
880            case Fragment::JUST_0:
881            case Fragment::JUST_1:
882                break;
883            case Fragment::PK_K:
884                break;
885            case Fragment::PK_H:
886                ops += 3;
887                break;
888            case Fragment::OLDER:
889            case Fragment::AFTER:
890                ops += 1;
891                break;
892            case Fragment::RIPEMD160:
893            case Fragment::SHA256:
894            case Fragment::HASH160:
895            case Fragment::HASH256:
896                ops += 4;
897                break;
898            case Fragment::ANDOR:
899                ops += 3;
900                break;
901            case Fragment::AND_V:
902                break;
903            case Fragment::AND_B:
904            case Fragment::OR_B:
905                ops += 1;
906                break;
907            case Fragment::OR_C:
908                ops += 2;
909                break;
910            case Fragment::OR_D:
911                ops += 3;
912                break;
913            case Fragment::OR_I:
914                ops += 3;
915                break;
916            case Fragment::THRESH:
917                ops += node_info->subtypes.size();
918                break;
919            case Fragment::MULTI:
920                ops += 1;
921                break;
922            case Fragment::MULTI_A:
923                ops += node_info->keys.size() + 1;
924                break;
925            case Fragment::WRAP_A:
926                ops += 2;
927                break;
928            case Fragment::WRAP_S:
929                ops += 1;
930                break;
931            case Fragment::WRAP_C:
932                ops += 1;
933                break;
934            case Fragment::WRAP_D:
935                ops += 3;
936                break;
937            case Fragment::WRAP_V:
938                // We don't account for OP_VERIFY here; that will be corrected for when the actual
939                // node is constructed below.
940                break;
941            case Fragment::WRAP_J:
942                ops += 4;
943                break;
944            case Fragment::WRAP_N:
945                ops += 1;
946                break;
947            }
948            if (ops > MAX_OPS_PER_SCRIPT) return {};
949            auto subtypes = node_info->subtypes;
950            todo.back().second = std::move(node_info);
951            todo.reserve(todo.size() + subtypes.size());
952            // As elements on the todo stack are processed back to front, construct
953            // them in reverse order (so that the first subnode is generated first).
954            for (size_t i = 0; i < subtypes.size(); ++i) {
955                todo.emplace_back(*(subtypes.rbegin() + i), std::nullopt);
956            }
957        } else {
958            // The back of todo has fragment and number of children decided, and
959            // those children have been constructed at the back of stack. Pop
960            // that entry off todo, and use it to construct a new Node on
961            // stack.
962            NodeInfo& info = *todo.back().second;
963            // Gather children from the back of stack.
964            std::vector<Node> sub;
965            sub.reserve(info.subtypes.size());
966            for (size_t i = 0; i < info.subtypes.size(); ++i) {
967                sub.push_back(std::move(*(stack.end() - info.subtypes.size() + i)));
968            }
969            stack.erase(stack.end() - info.subtypes.size(), stack.end());
970            // Construct new Node.
971            Node node{[&] {
972                if (info.keys.empty()) {
973                    return Node{miniscript::internal::NoDupCheck{}, script_ctx, info.fragment, std::move(sub), std::move(info.hash), info.k};
974                }
975                assert(sub.empty());
976                assert(info.hash.empty());
977                return Node{miniscript::internal::NoDupCheck{}, script_ctx, info.fragment, std::move(info.keys), info.k};
978            }()};
979            // Verify acceptability.
980            if ((node.GetType() & "KVWB"_mst) == ""_mst) {
981                assert(!strict_valid);
982                return {};
983            }
984            if (!(type_needed == ""_mst)) {
985                assert(node.GetType() << type_needed);
986            }
987            if (!node.IsValid()) return {};
988            // Update resource predictions.
989            if (node.Fragment() == Fragment::WRAP_V && node.Subs()[0].GetType() << "x"_mst) {
990                ops += 1;
991                scriptsize += 1;
992            }
993            if (!miniscript::IsTapscript(script_ctx) && ops > MAX_OPS_PER_SCRIPT) return {};
994            if (scriptsize > miniscript::internal::MaxScriptSize(script_ctx)) {
995                return {};
996            }
997            // Move it to the stack.
998            stack.push_back(std::move(node));
999            todo.pop_back();
1000        }