Inside Bitcoin

1001    }
1002    assert(stack.size() == 1);
1003    assert(stack[0].GetStaticOps() == ops);
1004    assert(stack[0].ScriptSize() == scriptsize);
1005    stack[0].DuplicateKeyCheck(KEY_COMP);
1006    return std::move(stack[0]);
1007}
1008
1009//! The spk for this script under the given context. If it's a Taproot output also record the spend data.
1010CScript ScriptPubKey(MsCtx ctx, const CScript& script, TaprootBuilder& builder)
1011{
1012    if (!miniscript::IsTapscript(ctx)) return CScript() << OP_0 << WitnessV0ScriptHash(script);
1013
1014    // For Taproot outputs we always use a tree with a single script and a dummy internal key.
1015    builder.Add(0, script, TAPROOT_LEAF_TAPSCRIPT);
1016    builder.Finalize(XOnlyPubKey::NUMS_H);
1017    return GetScriptForDestination(builder.GetOutput());
1018}
1019
1020//! Fill the witness with the data additional to the script satisfaction.
1021void SatisfactionToWitness(MsCtx ctx, CScriptWitness& witness, const CScript& script, TaprootBuilder& builder) {
1022    // For P2WSH, it's only the witness script.
1023    witness.stack.emplace_back(script.begin(), script.end());
1024    if (!miniscript::IsTapscript(ctx)) return;
1025    // For Tapscript we also need the control block.
1026    witness.stack.push_back(*builder.GetSpendData().scripts.begin()->second.begin());
1027}
1028
1029/** Perform various applicable tests on a miniscript Node. */
1030void TestNode(const MsCtx script_ctx, const std::optional<Node>& node, FuzzedDataProvider& provider)
1031{
1032    if (!node) return;
1033
1034    // Check that it roundtrips to text representation
1035    const ParserContext parser_ctx{script_ctx};
1036    std::optional<std::string> str{node->ToString(parser_ctx)};
1037    assert(str);
1038    auto parsed = miniscript::FromString(*str, parser_ctx);
1039    assert(parsed);
1040    assert(*parsed == *node);
1041
1042    // Check consistency between script size estimation and real size.
1043    auto script = node->ToScript(parser_ctx);
1044    assert(node->ScriptSize() == script.size());
1045
1046    // Check consistency of "x" property with the script (type K is excluded, because it can end
1047    // with a push of a key, which could match these opcodes).
1048    if (!(node->GetType() << "K"_mst)) {
1049        bool ends_in_verify = !(node->GetType() << "x"_mst);
1050        assert(ends_in_verify == (script.back() == OP_CHECKSIG || script.back() == OP_CHECKMULTISIG || script.back() == OP_EQUAL || script.back() == OP_NUMEQUAL));
1051    }
1052
1053    // The rest of the checks only apply when testing a valid top-level script.
1054    if (!node->IsValidTopLevel()) return;
1055
1056    // Check roundtrip to script
1057    auto decoded = miniscript::FromScript(script, parser_ctx);
1058    assert(decoded);
1059    // Note we can't use *decoded == *node because the miniscript representation may differ, so we check that:
1060    // - The script corresponding to that decoded form matches exactly
1061    // - The type matches exactly
1062    assert(decoded->ToScript(parser_ctx) == script);
1063    assert(decoded->GetType() == node->GetType());
1064
1065    // Optionally pad the script or the witness in order to increase the sensitivity of the tests of
1066    // the resources limits logic.
1067    CScriptWitness witness_mal, witness_nonmal;
1068    if (provider.ConsumeBool()) {
1069        // Under P2WSH, optionally pad the script with OP_NOPs to max op the ops limit of the constructed script.
1070        // This makes the script obviously not actually miniscript-compatible anymore, but the
1071        // signatures constructed in this test don't commit to the script anyway, so the same
1072        // miniscript satisfier will work. This increases the sensitivity of the test to the ops
1073        // counting logic being too low, especially for simple scripts.
1074        // Do this optionally because we're not solely interested in cases where the number of ops is
1075        // maximal.
1076        // Do not pad more than what would cause MAX_STANDARD_P2WSH_SCRIPT_SIZE to be reached, however,
1077        // as that also invalidates scripts.
1078        const auto node_ops{node->GetOps()};
1079        if (!IsTapscript(script_ctx) && node_ops && *node_ops < MAX_OPS_PER_SCRIPT
1080            && node->ScriptSize() < MAX_STANDARD_P2WSH_SCRIPT_SIZE) {
1081            int add = std::min<int>(
1082                MAX_OPS_PER_SCRIPT - *node_ops,
1083                MAX_STANDARD_P2WSH_SCRIPT_SIZE - node->ScriptSize());
1084            for (int i = 0; i < add; ++i) script.push_back(OP_NOP);
1085        }
1086
1087        // Under Tapscript, optionally pad the stack up to the limit minus the calculated maximum execution stack
1088        // size to assert a Miniscript would never add more elements to the stack during execution than anticipated.
1089        const auto node_exec_ss{node->GetExecStackSize()};
1090        if (miniscript::IsTapscript(script_ctx) && node_exec_ss && *node_exec_ss < MAX_STACK_SIZE) {
1091            unsigned add{(unsigned)MAX_STACK_SIZE - *node_exec_ss};
1092            witness_mal.stack.resize(add);
1093            witness_nonmal.stack.resize(add);
1094            script.reserve(add);
1095            for (unsigned i = 0; i < add; ++i) script.push_back(OP_NIP);
1096        }
1097    }
1098
1099    const SatisfierContext satisfier_ctx{script_ctx};
1100
1101    // Get the ScriptPubKey for this script, filling spend data if it's Taproot.
1102    TaprootBuilder builder;
1103    const CScript script_pubkey{ScriptPubKey(script_ctx, script, builder)};
1104
1105    // Run malleable satisfaction algorithm.
1106    std::vector<std::vector<unsigned char>> stack_mal;
1107    const bool mal_success = node->Satisfy(satisfier_ctx, stack_mal, false) == miniscript::Availability::YES;
1108
1109    // Run non-malleable satisfaction algorithm.
1110    std::vector<std::vector<unsigned char>> stack_nonmal;
1111    const bool nonmal_success = node->Satisfy(satisfier_ctx, stack_nonmal, true) == miniscript::Availability::YES;
1112
1113    if (nonmal_success) {
1114        // Non-malleable satisfactions are bounded by the satisfaction size plus:
1115        // - For P2WSH spends, the witness script
1116        // - For Tapscript spends, both the witness script and the control block
1117        const size_t max_stack_size{*node->GetStackSize() + 1 + miniscript::IsTapscript(script_ctx)};
1118        assert(stack_nonmal.size() <= max_stack_size);
1119        // If a non-malleable satisfaction exists, the malleable one must also exist, and be identical to it.
1120        assert(mal_success);
1121        assert(stack_nonmal == stack_mal);
1122        // Compute witness size (excluding script push, control block, and witness count encoding).
1123        const uint64_t wit_size{GetSerializeSize(stack_nonmal) - GetSizeOfCompactSize(stack_nonmal.size())};
1124        assert(wit_size <= *node->GetWitnessSize());
1125
1126        // Test non-malleable satisfaction.
1127        witness_nonmal.stack.insert(witness_nonmal.stack.end(), std::make_move_iterator(stack_nonmal.begin()), std::make_move_iterator(stack_nonmal.end()));
1128        SatisfactionToWitness(script_ctx, witness_nonmal, script, builder);
1129        ScriptError serror;
1130        bool res = VerifyScript(DUMMY_SCRIPTSIG, script_pubkey, &witness_nonmal, STANDARD_SCRIPT_VERIFY_FLAGS, CHECKER_CTX, &serror);
1131        // Non-malleable satisfactions are guaranteed to be valid if ValidSatisfactions().
1132        if (node->ValidSatisfactions()) assert(res);
1133        // More detailed: non-malleable satisfactions must be valid, or could fail with ops count error (if CheckOpsLimit failed),
1134        // or with a stack size error (if CheckStackSize check failed).
1135        assert(res ||
1136               (!node->CheckOpsLimit() && serror == ScriptError::SCRIPT_ERR_OP_COUNT) ||
1137               (!node->CheckStackSize() && serror == ScriptError::SCRIPT_ERR_STACK_SIZE));
1138    }
1139
1140    if (mal_success && (!nonmal_success || witness_mal.stack != witness_nonmal.stack)) {
1141        // Test malleable satisfaction only if it's different from the non-malleable one.
1142        witness_mal.stack.insert(witness_mal.stack.end(), std::make_move_iterator(stack_mal.begin()), std::make_move_iterator(stack_mal.end()));
1143        SatisfactionToWitness(script_ctx, witness_mal, script, builder);
1144        ScriptError serror;
1145        bool res = VerifyScript(DUMMY_SCRIPTSIG, script_pubkey, &witness_mal, STANDARD_SCRIPT_VERIFY_FLAGS, CHECKER_CTX, &serror);
1146        // Malleable satisfactions are not guaranteed to be valid under any conditions, but they can only
1147        // fail due to stack or ops limits.
1148        assert(res || serror == ScriptError::SCRIPT_ERR_OP_COUNT || serror == ScriptError::SCRIPT_ERR_STACK_SIZE);
1149    }
1150
1151    if (node->IsSane()) {
1152        // For sane nodes, the two algorithms behave identically.
1153        assert(mal_success == nonmal_success);
1154    }
1155
1156    // Verify that if a node is policy-satisfiable, the malleable satisfaction
1157    // algorithm succeeds. Given that under IsSane() both satisfactions
1158    // are identical, this implies that for such nodes, the non-malleable
1159    // satisfaction will also match the expected policy.
1160    const auto is_key_satisfiable = [script_ctx](const CPubKey& pubkey) -> bool {
1161        auto sig_ptr{TEST_DATA.GetSig(script_ctx, pubkey)};
1162        return sig_ptr != nullptr && sig_ptr->second;
1163    };
1164    bool satisfiable = node->IsSatisfiable([&](const Node& node) -> bool {
1165        switch (node.Fragment()) {
1166        case Fragment::PK_K:
1167        case Fragment::PK_H:
1168            return is_key_satisfiable(node.Keys()[0]);
1169        case Fragment::MULTI:
1170        case Fragment::MULTI_A: {
1171            size_t sats = std::ranges::count_if(node.Keys(), [&](const auto& key) {
1172                return size_t(is_key_satisfiable(key));
1173            });
1174            return sats >= node.K();
1175        }
1176        case Fragment::OLDER:
1177        case Fragment::AFTER:
1178            return node.K() & 1;
1179        case Fragment::SHA256:
1180            return TEST_DATA.sha256_preimages.contains(node.Data());
1181        case Fragment::HASH256:
1182            return TEST_DATA.hash256_preimages.contains(node.Data());
1183        case Fragment::RIPEMD160:
1184            return TEST_DATA.ripemd160_preimages.contains(node.Data());
1185        case Fragment::HASH160:
1186            return TEST_DATA.hash160_preimages.contains(node.Data());
1187        default:
1188            assert(false);
1189        }
1190        return false;
1191    });
1192    assert(mal_success == satisfiable);
1193}
1194
1195} // namespace
1196
1197void FuzzInit()
1198{
1199    static ECC_Context ecc_context{};
1200    TEST_DATA.Init();
1201}
1202
1203void FuzzInitSmart()
1204{
1205    FuzzInit();
1206    SMARTINFO.Init();
1207}
1208
1209/** Fuzz target that runs TestNode on nodes generated using ConsumeNodeStable. */
1210FUZZ_TARGET(miniscript_stable, .init = FuzzInit)
1211{
1212    // Run it under both P2WSH and Tapscript contexts.
1213    for (const auto script_ctx: {MsCtx::P2WSH, MsCtx::TAPSCRIPT}) {
1214        FuzzedDataProvider provider(buffer.data(), buffer.size());
1215        TestNode(script_ctx, GenNode(script_ctx, [&](Type needed_type) {
1216            return ConsumeNodeStable(script_ctx, provider, needed_type);
1217        }, ""_mst), provider);
1218    }
1219}
1220
1221/** Fuzz target that runs TestNode on nodes generated using ConsumeNodeSmart. */
1222FUZZ_TARGET(miniscript_smart, .init = FuzzInitSmart)
1223{
1224    /** The set of types we aim to construct nodes for. Together they cover all. */
1225    static constexpr std::array<Type, 4> BASE_TYPES{"B"_mst, "V"_mst, "K"_mst, "W"_mst};
1226
1227    FuzzedDataProvider provider(buffer.data(), buffer.size());
1228    const auto script_ctx{(MsCtx)provider.ConsumeBool()};
1229    TestNode(script_ctx, GenNode(script_ctx, [&](Type needed_type) {
1230        return ConsumeNodeSmart(script_ctx, provider, needed_type);
1231    }, PickValue(provider, BASE_TYPES), true), provider);
1232}
1233
1234/* Fuzz tests that test parsing from a string, and roundtripping via string. */
1235FUZZ_TARGET(miniscript_string, .init = FuzzInit)
1236{
1237    constexpr auto is_too_expensive{[](std::span<const uint8_t> buf) { return HasTooManySubFrag(buf) || HasTooManyWrappers(buf); }};
1238
1239    if (buffer.empty()) return;
1240    FuzzedDataProvider provider(buffer.data(), buffer.size());
1241    auto str = provider.ConsumeBytesAsString(provider.remaining_bytes() - 1);
1242    if (is_too_expensive(MakeUCharSpan(str))) return;
1243    const ParserContext parser_ctx{(MsCtx)provider.ConsumeBool()};
1244    auto parsed = miniscript::FromString(str, parser_ctx);
1245    if (!parsed) return;
1246
1247    const auto str2 = parsed->ToString(parser_ctx);
1248    assert(str2);
1249    auto parsed2 = miniscript::FromString(*str2, parser_ctx);
1250    assert(parsed2);