Inside Bitcoin

251    miniscript::Availability SatHASH256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const { return SatHash(hash, preimage, ChallengeType::HASH256); }
252    miniscript::Availability SatHASH160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const { return SatHash(hash, preimage, ChallengeType::HASH160); }
253};
254
255/** Mocking signature/timelock checker.
256 *
257 * It holds a pointer to a Satisfier object, to determine which timelocks are supposed to be available.
258 */
259class TestSignatureChecker : public BaseSignatureChecker {
260    const Satisfier& ctx;
261
262public:
263    TestSignatureChecker(const Satisfier& in_ctx LIFETIMEBOUND) : ctx(in_ctx) {}
264
265    bool CheckECDSASignature(const std::vector<unsigned char>& sig, const std::vector<unsigned char>& pubkey, const CScript& scriptcode, SigVersion sigversion) const override {
266        CPubKey pk(pubkey);
267        if (!pk.IsValid()) return false;
268        // Instead of actually running signature validation, check if the signature matches the precomputed one for this key.
269        auto it = g_testdata->signatures.find(pk);
270        if (it == g_testdata->signatures.end()) return false;
271        return sig == it->second;
272    }
273
274    bool CheckSchnorrSignature(std::span<const unsigned char> sig, std::span<const unsigned char> pubkey, SigVersion,
275                               ScriptExecutionData&, ScriptError*) const override {
276        XOnlyPubKey pk{pubkey};
277        auto it = g_testdata->schnorr_signatures.find(pk);
278        if (it == g_testdata->schnorr_signatures.end()) return false;
279        return std::ranges::equal(sig, it->second);
280    }
281
282    bool CheckLockTime(const CScriptNum& locktime) const override {
283        // Delegate to Satisfier.
284        return ctx.CheckAfter(locktime.GetInt64());
285    }
286
287    bool CheckSequence(const CScriptNum& sequence) const override {
288        // Delegate to Satisfier.
289        return ctx.CheckOlder(sequence.GetInt64());
290    }
291};
292
293using Fragment = miniscript::Fragment;
294using miniscript::operator""_mst;
295using Node = miniscript::Node<CPubKey>;
296
297/** Compute all challenges (pubkeys, hashes, timelocks) that occur in a given Miniscript. */
298std::set<Challenge> FindChallenges(const Node& root)
299{
300    std::set<Challenge> chal;
301
302    for (std::vector stack{&root}; !stack.empty();) {
303        const auto* ref{stack.back()};
304        stack.pop_back();
305
306        for (const auto& key : ref->Keys()) {
307            chal.emplace(ChallengeType::PK, ChallengeNumber(key));
308        }
309        switch (ref->Fragment()) {
310        case Fragment::OLDER: chal.emplace(ChallengeType::OLDER, ref->K()); break;
311        case Fragment::AFTER: chal.emplace(ChallengeType::AFTER, ref->K()); break;
312        case Fragment::SHA256: chal.emplace(ChallengeType::SHA256, ChallengeNumber(ref->Data())); break;
313        case Fragment::RIPEMD160: chal.emplace(ChallengeType::RIPEMD160, ChallengeNumber(ref->Data())); break;
314        case Fragment::HASH256: chal.emplace(ChallengeType::HASH256, ChallengeNumber(ref->Data())); break;
315        case Fragment::HASH160: chal.emplace(ChallengeType::HASH160, ChallengeNumber(ref->Data())); break;
316        default: break;
317        }
318        for (const auto& sub : ref->Subs()) {
319            stack.push_back(&sub);
320        }
321    }
322    return chal;
323}
324
325//! The spk for this script under the given context. If it's a Taproot output also record the spend data.
326CScript ScriptPubKey(miniscript::MiniscriptContext ctx, const CScript& script, TaprootBuilder& builder)
327{
328    if (!miniscript::IsTapscript(ctx)) return CScript() << OP_0 << WitnessV0ScriptHash(script);
329
330    // For Taproot outputs we always use a tree with a single script and a dummy internal key.
331    builder.Add(0, script, TAPROOT_LEAF_TAPSCRIPT);
332    builder.Finalize(XOnlyPubKey::NUMS_H);
333    return GetScriptForDestination(builder.GetOutput());
334}
335
336//! Fill the witness with the data additional to the script satisfaction.
337void SatisfactionToWitness(miniscript::MiniscriptContext ctx, CScriptWitness& witness, const CScript& script, TaprootBuilder& builder) {
338    // For P2WSH, it's only the witness script.
339    witness.stack.emplace_back(script.begin(), script.end());
340    if (!miniscript::IsTapscript(ctx)) return;
341    // For Tapscript we also need the control block.
342    witness.stack.push_back(*builder.GetSpendData().scripts.begin()->second.begin());
343}
344
345struct MiniScriptTest : BasicTestingSetup {
346/** Run random satisfaction tests. */
347void TestSatisfy(const KeyConverter& converter, const Node& node)
348{
349    auto script = node.ToScript(converter);
350    const auto challenges{FindChallenges(node)}; // Find all challenges in the generated miniscript.
351    std::vector<Challenge> challist(challenges.begin(), challenges.end());
352    for (int iter = 0; iter < 3; ++iter) {
353        std::shuffle(challist.begin(), challist.end(), m_rng);
354        Satisfier satisfier(converter.MsContext());
355        TestSignatureChecker checker(satisfier);
356        bool prev_mal_success = false, prev_nonmal_success = false;
357        // Go over all challenges involved in this miniscript in random order.
358        for (int add = -1; add < (int)challist.size(); ++add) {
359            if (add >= 0) satisfier.supported.insert(challist[add]); // The first iteration does not add anything
360
361            // Get the ScriptPubKey for this script, filling spend data if it's Taproot.
362            TaprootBuilder builder;
363            const CScript script_pubkey{ScriptPubKey(converter.MsContext(), script, builder)};
364
365            // Run malleable satisfaction algorithm.
366            CScriptWitness witness_mal;
367            const bool mal_success = node.Satisfy(satisfier, witness_mal.stack, false) == miniscript::Availability::YES;
368            SatisfactionToWitness(converter.MsContext(), witness_mal, script, builder);
369
370            // Run non-malleable satisfaction algorithm.
371            CScriptWitness witness_nonmal;
372            const bool nonmal_success = node.Satisfy(satisfier, witness_nonmal.stack, true) == miniscript::Availability::YES;
373            // Compute witness size (excluding script push, control block, and witness count encoding).
374            const uint64_t wit_size{GetSerializeSize(witness_nonmal.stack) - GetSizeOfCompactSize(witness_nonmal.stack.size())};
375            SatisfactionToWitness(converter.MsContext(), witness_nonmal, script, builder);
376
377            if (nonmal_success) {
378                // Non-malleable satisfactions are bounded by the satisfaction size plus:
379                // - For P2WSH spends, the witness script
380                // - For Tapscript spends, both the witness script and the control block
381                const size_t max_stack_size{*node.GetStackSize() + 1 + miniscript::IsTapscript(converter.MsContext())};
382                BOOST_CHECK(witness_nonmal.stack.size() <= max_stack_size);
383                // If a non-malleable satisfaction exists, the malleable one must also exist, and be identical to it.
384                BOOST_CHECK(mal_success);
385                BOOST_CHECK(witness_nonmal.stack == witness_mal.stack);
386                assert(wit_size <= *node.GetWitnessSize());
387
388                // Test non-malleable satisfaction.
389                ScriptError serror;
390                bool res = VerifyScript(CScript(), script_pubkey, &witness_nonmal, STANDARD_SCRIPT_VERIFY_FLAGS, checker, &serror);
391                // Non-malleable satisfactions are guaranteed to be valid if ValidSatisfactions().
392                if (node.ValidSatisfactions()) BOOST_CHECK(res);
393                // More detailed: non-malleable satisfactions must be valid, or could fail with ops count error (if CheckOpsLimit failed),
394                // or with a stack size error (if CheckStackSize check fails).
395                BOOST_CHECK(res ||
396                            (!node.CheckOpsLimit() && serror == ScriptError::SCRIPT_ERR_OP_COUNT) ||
397                            (!node.CheckStackSize() && serror == ScriptError::SCRIPT_ERR_STACK_SIZE));
398            }
399
400            if (mal_success && (!nonmal_success || witness_mal.stack != witness_nonmal.stack)) {
401                // Test malleable satisfaction only if it's different from the non-malleable one.
402                ScriptError serror;
403                bool res = VerifyScript(CScript(), script_pubkey, &witness_mal, STANDARD_SCRIPT_VERIFY_FLAGS, checker, &serror);
404                // Malleable satisfactions are not guaranteed to be valid under any conditions, but they can only
405                // fail due to stack or ops limits.
406                BOOST_CHECK(res || serror == ScriptError::SCRIPT_ERR_OP_COUNT || serror == ScriptError::SCRIPT_ERR_STACK_SIZE);
407            }
408
409            if (node.IsSane()) {
410                // For sane nodes, the two algorithms behave identically.
411                BOOST_CHECK_EQUAL(mal_success, nonmal_success);
412            }
413
414            // Adding more satisfied conditions can never remove our ability to produce a satisfaction.
415            BOOST_CHECK(mal_success >= prev_mal_success);
416            // For nonmalleable solutions this is only true if the added condition is PK;
417            // for other conditions, adding one may make an valid satisfaction become malleable. If the script
418            // is sane, this cannot happen however.
419            if (node.IsSane() || add < 0 || challist[add].first == ChallengeType::PK) {
420                BOOST_CHECK(nonmal_success >= prev_nonmal_success);
421            }
422            // Remember results for the next added challenge.
423            prev_mal_success = mal_success;
424            prev_nonmal_success = nonmal_success;
425        }
426
427        bool satisfiable = node.IsSatisfiable([](const Node&) { return true; });
428        // If the miniscript was satisfiable at all, a satisfaction must be found after all conditions are added.
429        BOOST_CHECK_EQUAL(prev_mal_success, satisfiable);
430        // If the miniscript is sane and satisfiable, a nonmalleable satisfaction must eventually be found.
431        if (node.IsSane()) BOOST_CHECK_EQUAL(prev_nonmal_success, satisfiable);
432    }
433}
434
435enum TestMode : int {
436    //! Invalid under any context
437    TESTMODE_INVALID = 0,
438    //! Valid under any context unless overridden
439    TESTMODE_VALID = 1,
440    TESTMODE_NONMAL = 2,
441    TESTMODE_NEEDSIG = 4,
442    TESTMODE_TIMELOCKMIX = 8,
443    //! Invalid only under P2WSH context
444    TESTMODE_P2WSH_INVALID = 16,
445    //! Invalid only under Tapscript context
446    TESTMODE_TAPSCRIPT_INVALID = 32,
447};
448
449void Test(const std::string& ms, const std::string& hexscript, int mode, const KeyConverter& converter,
450          int opslimit = -1, int stacklimit = -1, std::optional<uint32_t> max_wit_size = std::nullopt,
451          std::optional<uint32_t> stack_exec = {})
452{
453    auto node = miniscript::FromString(ms, converter);
454    const bool is_tapscript{miniscript::IsTapscript(converter.MsContext())};
455    if (mode == TESTMODE_INVALID || ((mode & TESTMODE_P2WSH_INVALID) && !is_tapscript) || ((mode & TESTMODE_TAPSCRIPT_INVALID) && is_tapscript)) {
456        BOOST_CHECK_MESSAGE(!node || !node->IsValid(), "Unexpectedly valid: " + ms);
457    } else {
458        BOOST_CHECK_MESSAGE(node, "Unparseable: " + ms);
459        BOOST_CHECK_MESSAGE(node->IsValid(), "Invalid: " + ms);
460        BOOST_CHECK_MESSAGE(node->IsValidTopLevel(), "Invalid top level: " + ms);
461        auto computed_script = node->ToScript(converter);
462        BOOST_CHECK_MESSAGE(node->ScriptSize() == computed_script.size(), "Script size mismatch: " + ms);
463        if (hexscript != "?") BOOST_CHECK_MESSAGE(HexStr(computed_script) == hexscript, "Script mismatch: " + ms + " (" + HexStr(computed_script) + " vs " + hexscript + ")");
464        BOOST_CHECK_MESSAGE(node->IsNonMalleable() == !!(mode & TESTMODE_NONMAL), "Malleability mismatch: " + ms);
465        BOOST_CHECK_MESSAGE(node->NeedsSignature() == !!(mode & TESTMODE_NEEDSIG), "Signature necessity mismatch: " + ms);
466        BOOST_CHECK_MESSAGE((node->GetType() << "k"_mst) == !(mode & TESTMODE_TIMELOCKMIX), "Timelock mix mismatch: " + ms);
467        auto inferred_miniscript = miniscript::FromScript(computed_script, converter);
468        BOOST_CHECK_MESSAGE(inferred_miniscript, "Cannot infer miniscript from script: " + ms);
469        BOOST_CHECK_MESSAGE(inferred_miniscript->ToScript(converter) == computed_script, "Roundtrip failure: miniscript->script != miniscript->script->miniscript->script: " + ms);
470        if (opslimit != -1) BOOST_CHECK_MESSAGE((int)*node->GetOps() == opslimit, "Ops limit mismatch: " << ms << " (" << *node->GetOps() << " vs " << opslimit << ")");
471        if (stacklimit != -1) BOOST_CHECK_MESSAGE((int)*node->GetStackSize() == stacklimit, "Stack limit mismatch: " << ms << " (" << *node->GetStackSize() << " vs " << stacklimit << ")");
472        if (max_wit_size) BOOST_CHECK_MESSAGE(*node->GetWitnessSize() == *max_wit_size, "Witness size limit mismatch: " << ms << " (" << *node->GetWitnessSize() << " vs " << *max_wit_size << ")");
473        if (stack_exec) BOOST_CHECK_MESSAGE(*node->GetExecStackSize() == *stack_exec, "Stack execution limit mismatch: " << ms << " (" << *node->GetExecStackSize() << " vs " << *stack_exec << ")");
474        TestSatisfy(converter, *node);
475    }
476}
477
478void Test(const std::string& ms, const std::string& hexscript, const std::string& hextapscript, int mode,
479          int opslimit, int stacklimit, std::optional<uint32_t> max_wit_size,
480          std::optional<uint32_t> max_tap_wit_size,
481          std::optional<uint32_t> stack_exec)
482{
483    KeyConverter wsh_converter(miniscript::MiniscriptContext::P2WSH);
484    Test(ms, hexscript, mode, wsh_converter, opslimit, stacklimit, max_wit_size, stack_exec);
485    KeyConverter tap_converter(miniscript::MiniscriptContext::TAPSCRIPT);
486    Test(ms, hextapscript == "=" ? hexscript : hextapscript, mode, tap_converter, opslimit, stacklimit, max_tap_wit_size, stack_exec);
487}
488
489void Test(const std::string& ms, const std::string& hexscript, const std::string& hextapscript, int mode)
490{
491    Test(ms, hexscript, hextapscript, mode,
492         /*opslimit=*/-1, /*stacklimit=*/-1,
493         /*max_wit_size=*/std::nullopt, /*max_tap_wit_size=*/std::nullopt, /*stack_exec=*/std::nullopt);
494}
495}; // struct MiniScriptTest
496
497} // namespace
498
499BOOST_FIXTURE_TEST_SUITE(miniscript_tests, MiniScriptTest)
500