251    }
252    const auto& tap_pk_it = sigdata.tap_pubkeys.find(address);
253    if (tap_pk_it != sigdata.tap_pubkeys.end()) {
254        pubkey = tap_pk_it->second.GetEvenCorrespondingCPubKey();
255        return true;
256    }
257    // Query the underlying provider
258    return provider.GetPubKey(address, pubkey);
259}
260
261static bool CreateSig(const BaseSignatureCreator& creator, SignatureData& sigdata, const SigningProvider& provider, std::vector<unsigned char>& sig_out, const CPubKey& pubkey, const CScript& scriptcode, SigVersion sigversion)
262{
263    CKeyID keyid = pubkey.GetID();
264    const auto it = sigdata.signatures.find(keyid);
265    if (it != sigdata.signatures.end()) {
266        sig_out = it->second.second;
267        return true;
268    }
269    KeyOriginInfo info;
270    if (provider.GetKeyOrigin(keyid, info)) {
271        sigdata.misc_pubkeys.emplace(keyid, std::make_pair(pubkey, std::move(info)));
272    }
273    if (creator.CreateSig(provider, sig_out, keyid, scriptcode, sigversion)) {
274        auto i = sigdata.signatures.emplace(keyid, SigPair(pubkey, sig_out));
275        assert(i.second);
276        return true;
277    }
278    // Could not make signature or signature not found, add keyid to missing
279    sigdata.missing_sigs.push_back(keyid);
280    return false;
281}
282
283static bool SignMuSig2(const BaseSignatureCreator& creator, SignatureData& sigdata, const SigningProvider& provider, std::vector<unsigned char>& sig_out, const XOnlyPubKey& script_pubkey, const uint256* merkle_root, const uint256* leaf_hash, SigVersion sigversion)
284{
285    Assert(sigversion == SigVersion::TAPROOT || sigversion == SigVersion::TAPSCRIPT);
286
287    // Lookup derivation paths for the script pubkey
288    KeyOriginInfo agg_info;
289    auto misc_pk_it = sigdata.taproot_misc_pubkeys.find(script_pubkey);
290    if (misc_pk_it != sigdata.taproot_misc_pubkeys.end()) {
291        agg_info = misc_pk_it->second.second;
292    }
293
294    for (const auto& [agg_pub, part_pks] : sigdata.musig2_pubkeys) {
295        if (part_pks.empty()) continue;
296
297        // Fill participant derivation path info
298        for (const auto& part_pk : part_pks) {
299            KeyOriginInfo part_info;
300            if (provider.GetKeyOrigin(part_pk.GetID(), part_info)) {
301                XOnlyPubKey xonly_part(part_pk);
302                auto it = sigdata.taproot_misc_pubkeys.find(xonly_part);
303                if (it == sigdata.taproot_misc_pubkeys.end()) {
304                    it = sigdata.taproot_misc_pubkeys.emplace(xonly_part, std::make_pair(std::set<uint256>(), part_info)).first;
305                }
306                if (leaf_hash) it->second.first.insert(*leaf_hash);
307            }
308        }
309
310        // The pubkey in the script may not be the actual aggregate of the participants, but derived from it.
311        // Check the derivation, and compute the BIP 32 derivation tweaks
312        std::vector<std::pair<uint256, bool>> tweaks;
313        CPubKey plain_pub = agg_pub;
314        if (XOnlyPubKey(agg_pub) != script_pubkey) {
315            if (agg_info.path.empty()) continue;
316            if (agg_info.fingerprint != agg_pub.GetID().fingerprint()) {
317                continue;
318            }
319            // Get the BIP32 derivation tweaks
320            CExtPubKey extpub = CreateMuSig2SyntheticXpub(agg_pub);
321            for (const uint32_t i : agg_info.path) {
322                if (i >> 31) return false; // Hardened derivation is not possible from a public key
323                auto& [t, xonly] = tweaks.emplace_back();
324                xonly = false;
325                if (!extpub.Derive(extpub, i, &t)) {
326                    return false;
327                }
328            }
329            if (XOnlyPubKey(extpub.pubkey) != script_pubkey) continue;
330            plain_pub = extpub.pubkey;
331        }
332
333        // Add the merkle root tweak
334        if (sigversion == SigVersion::TAPROOT && merkle_root) {
335            tweaks.emplace_back(script_pubkey.ComputeTapTweakHash(merkle_root->IsNull() ? nullptr : merkle_root), true);
336            std::optional<std::pair<XOnlyPubKey, bool>> tweaked = script_pubkey.CreateTapTweak(merkle_root->IsNull() ? nullptr : merkle_root);
337            if (!Assume(tweaked)) return false;
338            plain_pub = tweaked->first.GetCPubKeys().at(tweaked->second ? 1 : 0);
339        }
340
341        // First try to aggregate
342        if (creator.CreateMuSig2AggregateSig(part_pks, sig_out, agg_pub, plain_pub, leaf_hash, tweaks, sigversion, sigdata)) {
343            if (sigversion == SigVersion::TAPROOT) {
344                sigdata.taproot_key_path_sig = sig_out;
345            } else {
346                auto lookup_key = std::make_pair(script_pubkey, leaf_hash ? *leaf_hash : uint256());
347                sigdata.taproot_script_sigs[lookup_key] = sig_out;
348            }
349            continue;
350        }
351        // Cannot aggregate, try making partial sigs for every participant
352        auto pub_key_leaf_hash = std::make_pair(plain_pub, leaf_hash ? *leaf_hash : uint256());
353        for (const CPubKey& part_pk : part_pks) {
354            uint256 partial_sig;
355            if (creator.CreateMuSig2PartialSig(provider, partial_sig, agg_pub, plain_pub, part_pk, leaf_hash, tweaks, sigversion, sigdata) && Assume(!partial_sig.IsNull())) {
356                sigdata.musig2_partial_sigs[pub_key_leaf_hash].emplace(part_pk, partial_sig);
357            }
358        }
359        // If there are any partial signatures, continue with next aggregate pubkey
360        auto partial_sigs_it = sigdata.musig2_partial_sigs.find(pub_key_leaf_hash);
361        if (partial_sigs_it != sigdata.musig2_partial_sigs.end() && !partial_sigs_it->second.empty()) {
362            continue;
363        }
364        // No partial sigs, try to make pubnonces
365        std::map<CPubKey, std::vector<uint8_t>>& pubnonces = sigdata.musig2_pubnonces[pub_key_leaf_hash];
366        for (const CPubKey& part_pk : part_pks) {
367            if (pubnonces.contains(part_pk)) continue;
368            std::vector<uint8_t> pubnonce = creator.CreateMuSig2Nonce(provider, agg_pub, plain_pub, part_pk, leaf_hash, merkle_root, sigversion, sigdata);
369            if (pubnonce.empty()) continue;
370            pubnonces[part_pk] = std::move(pubnonce);
371        }
372    }
373    return true;
374}
375
376static bool CreateTaprootScriptSig(const BaseSignatureCreator& creator, SignatureData& sigdata, const SigningProvider& provider, std::vector<unsigned char>& sig_out, const XOnlyPubKey& pubkey, const uint256& leaf_hash, SigVersion sigversion)
377{
378    KeyOriginInfo info;
379    if (provider.GetKeyOriginByXOnly(pubkey, info)) {
380        auto it = sigdata.taproot_misc_pubkeys.find(pubkey);
381        if (it == sigdata.taproot_misc_pubkeys.end()) {
382            sigdata.taproot_misc_pubkeys.emplace(pubkey, std::make_pair(std::set<uint256>({leaf_hash}), info));
383        } else {
384            it->second.first.insert(leaf_hash);
385        }
386    }
387
388    auto lookup_key = std::make_pair(pubkey, leaf_hash);
389    auto it = sigdata.taproot_script_sigs.find(lookup_key);
390    if (it != sigdata.taproot_script_sigs.end()) {
391        sig_out = it->second;
392        return true;
393    }
394
395    if (creator.CreateSchnorrSig(provider, sig_out, pubkey, &leaf_hash, nullptr, sigversion)) {
396        sigdata.taproot_script_sigs[lookup_key] = sig_out;
397    } else if (!SignMuSig2(creator, sigdata, provider, sig_out, pubkey, /*merkle_root=*/nullptr, &leaf_hash, sigversion)) {
398        return false;
399    }
400
401    return sigdata.taproot_script_sigs.contains(lookup_key);
402}
403
404template<typename M, typename K, typename V>
405miniscript::Availability MsLookupHelper(const M& map, const K& key, V& value)
406{
407    auto it = map.find(key);
408    if (it != map.end()) {
409        value = it->second;
410        return miniscript::Availability::YES;
411    }
412    return miniscript::Availability::NO;
413}
414
415/**
416 * Context for solving a Miniscript.
417 * If enough material (access to keys, hash preimages, ..) is given, produces a valid satisfaction.
418 */
419template<typename Pk>
420struct Satisfier {
421    using Key = Pk;
422
423    const SigningProvider& m_provider;
424    SignatureData& m_sig_data;
425    const BaseSignatureCreator& m_creator;
426    const CScript& m_witness_script;
427    //! The context of the script we are satisfying (either P2WSH or Tapscript).
428    const miniscript::MiniscriptContext m_script_ctx;
429
430    explicit Satisfier(const SigningProvider& provider LIFETIMEBOUND, SignatureData& sig_data LIFETIMEBOUND,
431                       const BaseSignatureCreator& creator LIFETIMEBOUND,
432                       const CScript& witscript LIFETIMEBOUND,
433                       miniscript::MiniscriptContext script_ctx) : m_provider(provider),
434                                                                   m_sig_data(sig_data),
435                                                                   m_creator(creator),
436                                                                   m_witness_script(witscript),
437                                                                   m_script_ctx(script_ctx) {}
438
439    static bool KeyCompare(const Key& a, const Key& b) {
440        return a < b;
441    }
442
443    //! Get a CPubKey from a key hash. Note the key hash may be of an xonly pubkey.
444    template<typename I>
445    std::optional<CPubKey> CPubFromPKHBytes(I first, I last) const {
446        assert(last - first == 20);
447        CPubKey pubkey;
448        CKeyID key_id;
449        std::copy(first, last, key_id.begin());
450        if (GetPubKey(m_provider, m_sig_data, key_id, pubkey)) return pubkey;
451        m_sig_data.missing_pubkeys.push_back(key_id);
452        return {};
453    }
454
455    //! Conversion to raw public key.
456    std::vector<unsigned char> ToPKBytes(const Key& key) const { return {key.begin(), key.end()}; }
457
458    //! Time lock satisfactions.
459    bool CheckAfter(uint32_t value) const { return m_creator.Checker().CheckLockTime(CScriptNum(value)); }
460    bool CheckOlder(uint32_t value) const { return m_creator.Checker().CheckSequence(CScriptNum(value)); }
461
462    //! Hash preimage satisfactions.
463    miniscript::Availability SatSHA256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
464        return MsLookupHelper(m_sig_data.sha256_preimages, hash, preimage);
465    }
466    miniscript::Availability SatRIPEMD160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
467        return MsLookupHelper(m_sig_data.ripemd160_preimages, hash, preimage);
468    }
469    miniscript::Availability SatHASH256(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
470        return MsLookupHelper(m_sig_data.hash256_preimages, hash, preimage);
471    }
472    miniscript::Availability SatHASH160(const std::vector<unsigned char>& hash, std::vector<unsigned char>& preimage) const {
473        return MsLookupHelper(m_sig_data.hash160_preimages, hash, preimage);
474    }
475
476    miniscript::MiniscriptContext MsContext() const {
477        return m_script_ctx;
478    }
479};
480
481/** Miniscript satisfier specific to P2WSH context. */
482struct WshSatisfier: Satisfier<CPubKey> {
483    explicit WshSatisfier(const SigningProvider& provider LIFETIMEBOUND, SignatureData& sig_data LIFETIMEBOUND,
484                          const BaseSignatureCreator& creator LIFETIMEBOUND, const CScript& witscript LIFETIMEBOUND)
485                          : Satisfier(provider, sig_data, creator, witscript, miniscript::MiniscriptContext::P2WSH) {}
486
487    //! Conversion from a raw compressed public key.
488    template <typename I>
489    std::optional<CPubKey> FromPKBytes(I first, I last) const {
490        CPubKey pubkey{first, last};
491        if (pubkey.IsValid()) return pubkey;
492        return {};
493    }
494
495    //! Conversion from a raw compressed public key hash.
496    template<typename I>
497    std::optional<CPubKey> FromPKHBytes(I first, I last) const {
498        return Satisfier::CPubFromPKHBytes(first, last);
499    }
500