501    //! Satisfy an ECDSA signature check.
502    miniscript::Availability Sign(const CPubKey& key, std::vector<unsigned char>& sig) const {
503        if (CreateSig(m_creator, m_sig_data, m_provider, sig, key, m_witness_script, SigVersion::WITNESS_V0)) {
504            return miniscript::Availability::YES;
505        }
506        return miniscript::Availability::NO;
507    }
508};
509
510/** Miniscript satisfier specific to Tapscript context. */
511struct TapSatisfier: Satisfier<XOnlyPubKey> {
512    const uint256& m_leaf_hash;
513
514    explicit TapSatisfier(const SigningProvider& provider LIFETIMEBOUND, SignatureData& sig_data LIFETIMEBOUND,
515                          const BaseSignatureCreator& creator LIFETIMEBOUND, const CScript& script LIFETIMEBOUND,
516                          const uint256& leaf_hash LIFETIMEBOUND)
517                          : Satisfier(provider, sig_data, creator, script, miniscript::MiniscriptContext::TAPSCRIPT),
518                            m_leaf_hash(leaf_hash) {}
519
520    //! Conversion from a raw xonly public key.
521    template <typename I>
522    std::optional<XOnlyPubKey> FromPKBytes(I first, I last) const {
523        if (last - first != 32) return {};
524        XOnlyPubKey pubkey;
525        std::copy(first, last, pubkey.begin());
526        return pubkey;
527    }
528
529    //! Conversion from a raw xonly public key hash.
530    template<typename I>
531    std::optional<XOnlyPubKey> FromPKHBytes(I first, I last) const {
532        if (auto pubkey = Satisfier::CPubFromPKHBytes(first, last)) return XOnlyPubKey{*pubkey};
533        return {};
534    }
535
536    //! Satisfy a BIP340 signature check.
537    miniscript::Availability Sign(const XOnlyPubKey& key, std::vector<unsigned char>& sig) const {
538        if (CreateTaprootScriptSig(m_creator, m_sig_data, m_provider, sig, key, m_leaf_hash, SigVersion::TAPSCRIPT)) {
539            return miniscript::Availability::YES;
540        }
541        return miniscript::Availability::NO;
542    }
543};
544
545static bool SignTaprootScript(const SigningProvider& provider, const BaseSignatureCreator& creator, SignatureData& sigdata, int leaf_version, std::span<const unsigned char> script_bytes, std::vector<valtype>& result)
546{
547    // Only BIP342 tapscript signing is supported for now.
548    if (leaf_version != TAPROOT_LEAF_TAPSCRIPT) return false;
549
550    uint256 leaf_hash = ComputeTapleafHash(leaf_version, script_bytes);
551    CScript script = CScript(script_bytes.begin(), script_bytes.end());
552
553    TapSatisfier ms_satisfier{provider, sigdata, creator, script, leaf_hash};
554    const auto ms = miniscript::FromScript(script, ms_satisfier);
555    return ms && ms->Satisfy(ms_satisfier, result) == miniscript::Availability::YES;
556}
557
558static bool SignTaproot(const SigningProvider& provider, const BaseSignatureCreator& creator, const WitnessV1Taproot& output, SignatureData& sigdata, std::vector<valtype>& result)
559{
560    TaprootSpendData spenddata;
561    TaprootBuilder builder;
562
563    // Gather information about this output.
564    if (provider.GetTaprootSpendData(output, spenddata)) {
565        sigdata.tr_spenddata.Merge(spenddata);
566    }
567    if (provider.GetTaprootBuilder(output, builder)) {
568        sigdata.tr_builder = builder;
569    }
570    if (auto agg_keys = provider.GetAllMuSig2ParticipantPubkeys(); !agg_keys.empty()) {
571        sigdata.musig2_pubkeys.insert(agg_keys.begin(), agg_keys.end());
572    }
573
574
575    // Try key path spending.
576    {
577        KeyOriginInfo internal_key_info;
578        if (provider.GetKeyOriginByXOnly(sigdata.tr_spenddata.internal_key, internal_key_info)) {
579            auto it = sigdata.taproot_misc_pubkeys.find(sigdata.tr_spenddata.internal_key);
580            if (it == sigdata.taproot_misc_pubkeys.end()) {
581                sigdata.taproot_misc_pubkeys.emplace(sigdata.tr_spenddata.internal_key, std::make_pair(std::set<uint256>(), internal_key_info));
582            }
583        }
584
585        KeyOriginInfo output_key_info;
586        if (provider.GetKeyOriginByXOnly(output, output_key_info)) {
587            auto it = sigdata.taproot_misc_pubkeys.find(output);
588            if (it == sigdata.taproot_misc_pubkeys.end()) {
589                sigdata.taproot_misc_pubkeys.emplace(output, std::make_pair(std::set<uint256>(), output_key_info));
590            }
591        }
592
593        auto make_keypath_sig = [&](const XOnlyPubKey& pk, const uint256* merkle_root) {
594            std::vector<unsigned char> sig;
595            if (creator.CreateSchnorrSig(provider, sig, pk, nullptr, merkle_root, SigVersion::TAPROOT)) {
596                sigdata.taproot_key_path_sig = sig;
597            } else {
598                SignMuSig2(creator, sigdata, provider, sig, pk, merkle_root, /*leaf_hash=*/nullptr, SigVersion::TAPROOT);
599            }
600        };
601
602        // First try signing with internal key
603        if (sigdata.taproot_key_path_sig.size() == 0) {
604            make_keypath_sig(sigdata.tr_spenddata.internal_key, &sigdata.tr_spenddata.merkle_root);
605        }
606        // Try signing with output key if still no signature
607        if (sigdata.taproot_key_path_sig.size() == 0) {
608            make_keypath_sig(output, nullptr);
609        }
610        if (sigdata.taproot_key_path_sig.size()) {
611            result = Vector(sigdata.taproot_key_path_sig);
612            return true;
613        }
614    }
615
616    // Try script path spending.
617    std::vector<std::vector<unsigned char>> smallest_result_stack;
618    for (const auto& [key, control_blocks] : sigdata.tr_spenddata.scripts) {
619        const auto& [script, leaf_ver] = key;
620        std::vector<std::vector<unsigned char>> result_stack;
621        if (SignTaprootScript(provider, creator, sigdata, leaf_ver, script, result_stack)) {
622            result_stack.emplace_back(std::begin(script), std::end(script)); // Push the script
623            result_stack.push_back(*control_blocks.begin()); // Push the smallest control block
624            if (smallest_result_stack.size() == 0 ||
625                GetSerializeSize(result_stack) < GetSerializeSize(smallest_result_stack)) {
626                smallest_result_stack = std::move(result_stack);
627            }
628        }
629    }
630    if (smallest_result_stack.size() != 0) {
631        result = std::move(smallest_result_stack);
632        return true;
633    }
634
635    return false;
636}
637
638/**
639 * Sign scriptPubKey using signature made with creator.
640 * Signatures are returned in scriptSigRet (or returns false if scriptPubKey can't be signed),
641 * unless whichTypeRet is TxoutType::SCRIPTHASH, in which case scriptSigRet is the redemption script.
642 * Returns false if scriptPubKey could not be completely satisfied.
643 */
644static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator& creator, const CScript& scriptPubKey,
645                     std::vector<valtype>& ret, TxoutType& whichTypeRet, SigVersion sigversion, SignatureData& sigdata)
646{
647    CScript scriptRet;
648    ret.clear();
649    std::vector<unsigned char> sig;
650
651    std::vector<valtype> vSolutions;
652    whichTypeRet = Solver(scriptPubKey, vSolutions);
653
654    switch (whichTypeRet) {
655    case TxoutType::NONSTANDARD:
656    case TxoutType::NULL_DATA:
657    case TxoutType::WITNESS_UNKNOWN:
658        return false;
659    case TxoutType::PUBKEY:
660        if (!CreateSig(creator, sigdata, provider, sig, CPubKey(vSolutions[0]), scriptPubKey, sigversion)) return false;
661        ret.push_back(std::move(sig));
662        return true;
663    case TxoutType::PUBKEYHASH: {
664        CKeyID keyID = CKeyID(uint160(vSolutions[0]));
665        CPubKey pubkey;
666        if (!GetPubKey(provider, sigdata, keyID, pubkey)) {
667            // Pubkey could not be found, add to missing
668            sigdata.missing_pubkeys.push_back(keyID);
669            return false;
670        }
671        if (!CreateSig(creator, sigdata, provider, sig, pubkey, scriptPubKey, sigversion)) return false;
672        ret.push_back(std::move(sig));
673        ret.push_back(ToByteVector(pubkey));
674        return true;
675    }
676    case TxoutType::SCRIPTHASH: {
677        uint160 h160{vSolutions[0]};
678        if (GetCScript(provider, sigdata, CScriptID{h160}, scriptRet)) {
679            ret.emplace_back(scriptRet.begin(), scriptRet.end());
680            return true;
681        }
682        // Could not find redeemScript, add to missing
683        sigdata.missing_redeem_script = h160;
684        return false;
685    }
686    case TxoutType::MULTISIG: {
687        size_t required = vSolutions.front()[0];
688        ret.emplace_back(); // workaround CHECKMULTISIG bug
689        for (size_t i = 1; i < vSolutions.size() - 1; ++i) {
690            CPubKey pubkey = CPubKey(vSolutions[i]);
691            // We need to always call CreateSig in order to fill sigdata with all
692            // possible signatures that we can create. This will allow further PSBT
693            // processing to work as it needs all possible signature and pubkey pairs
694            if (CreateSig(creator, sigdata, provider, sig, pubkey, scriptPubKey, sigversion)) {
695                if (ret.size() < required + 1) {
696                    ret.push_back(std::move(sig));
697                }
698            }
699        }
700        bool ok = ret.size() == required + 1;
701        for (size_t i = 0; i + ret.size() < required + 1; ++i) {
702            ret.emplace_back();
703        }
704        return ok;
705    }
706    case TxoutType::WITNESS_V0_KEYHASH:
707        ret.push_back(vSolutions[0]);
708        return true;
709
710    case TxoutType::WITNESS_V0_SCRIPTHASH:
711        if (GetCScript(provider, sigdata, CScriptID{RIPEMD160(vSolutions[0])}, scriptRet)) {
712            ret.emplace_back(scriptRet.begin(), scriptRet.end());
713            return true;
714        }
715        // Could not find witnessScript, add to missing
716        sigdata.missing_witness_script = uint256(vSolutions[0]);
717        return false;
718
719    case TxoutType::WITNESS_V1_TAPROOT:
720        return SignTaproot(provider, creator, WitnessV1Taproot(XOnlyPubKey{vSolutions[0]}), sigdata, ret);
721
722    case TxoutType::ANCHOR:
723        return true;
724    } // no default case, so the compiler can warn about missing cases
725    assert(false);
726}
727
728static CScript PushAll(const std::vector<valtype>& values)
729{
730    CScript result;
731    for (const valtype& v : values) {
732        if (v.size() == 0) {
733            result << OP_0;
734        } else if (v.size() == 1 && v[0] >= 1 && v[0] <= 16) {
735            result << CScript::EncodeOP_N(v[0]);
736        } else if (v.size() == 1 && v[0] == 0x81) {
737            result << OP_1NEGATE;
738        } else {
739            result << v;
740        }
741    }
742    return result;
743}
744
745bool ProduceSignature(const SigningProvider& provider, const BaseSignatureCreator& creator, const CScript& fromPubKey, SignatureData& sigdata)
746{
747    if (sigdata.complete) return true;
748
749    std::vector<valtype> result;
750    TxoutType whichType;