251    virtual bool CanSelfExpand() const = 0;
252
253protected:
254    static bool DetermineApostropheUse(StringType type, bool normalized, bool public_apostrophe)
255    {
256        bool use_apostrophe{false};
257        switch (type) {
258        case StringType::COMPAT:
259            // COMPAT always uses apostrophe to stay compatible with previous versions
260            use_apostrophe = true;
261            break;
262        case StringType::CANONICAL:
263            // CANONICAL always uses h
264            use_apostrophe = false;
265            break;
266        case StringType::PUBLIC:
267            use_apostrophe = !normalized && public_apostrophe;
268            break;
269        } // no default case, so the compiler can warn about missing cases
270        return use_apostrophe;
271    }
272};
273
274class OriginPubkeyProvider final : public PubkeyProvider
275{
276    KeyOriginInfo m_origin;
277    std::unique_ptr<PubkeyProvider> m_provider;
278    bool m_apostrophe;
279
280    std::string OriginString(StringType type, bool normalized=false) const
281    {
282        bool use_apostrophe{DetermineApostropheUse(type, normalized, m_apostrophe)};
283        return HexStr(m_origin.fingerprint) + FormatHDKeypath(m_origin.path, use_apostrophe);
284    }
285
286public:
287    OriginPubkeyProvider(uint32_t exp_index, KeyOriginInfo info, std::unique_ptr<PubkeyProvider> provider, bool apostrophe) : PubkeyProvider(exp_index), m_origin(std::move(info)), m_provider(std::move(provider)), m_apostrophe(apostrophe) {}
288    std::optional<CPubKey> GetPubKey(int pos, const SigningProvider& arg, FlatSigningProvider& out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
289    {
290        // Derive into a temporary provider. Another key expression may have already put this
291        // key into out with its origin prefixed, and prefixing that entry would double it up.
292        FlatSigningProvider subprovider;
293        std::optional<CPubKey> pub = m_provider->GetPubKey(pos, arg, subprovider, read_cache, write_cache);
294        if (!pub) return std::nullopt;
295        const CKeyID keyid{pub->GetID()};
296        Assert(subprovider.pubkeys.contains(keyid));
297        auto& [pubkey, suborigin] = subprovider.origins[keyid];
298        Assert(pubkey == *pub); // m_provider must have a valid origin by this point.
299        suborigin.fingerprint = m_origin.fingerprint;
300        suborigin.path.insert(suborigin.path.begin(), m_origin.path.begin(), m_origin.path.end());
301        auto origin{subprovider.origins.extract(keyid)};
302        out.Merge(std::move(subprovider));
303        // An explicit origin takes precedence over an implicit one for the same key.
304        out.origins.insert_or_assign(keyid, std::move(origin.mapped()));
305        return pub;
306    }
307    bool IsRange() const override { return m_provider->IsRange(); }
308    size_t GetSize() const override { return m_provider->GetSize(); }
309    bool IsBIP32() const override { return m_provider->IsBIP32(); }
310    std::string ToString(StringType type) const override { return "[" + OriginString(type) + "]" + m_provider->ToString(type); }
311    bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override
312    {
313        std::string sub;
314        bool has_priv_key{m_provider->ToPrivateString(arg, sub)};
315        ret = "[" + OriginString(StringType::PUBLIC) + "]" + std::move(sub);
316        return has_priv_key;
317    }
318    bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override
319    {
320        std::string sub;
321        if (!m_provider->ToNormalizedString(arg, sub, cache)) return false;
322        // If m_provider is a BIP32PubkeyProvider, we may get a string formatted like a OriginPubkeyProvider
323        // In that case, we need to strip out the leading square bracket and fingerprint from the substring,
324        // and append that to our own origin string.
325        if (sub[0] == '[') {
326            sub = sub.substr(9);
327            ret = "[" + OriginString(StringType::PUBLIC, /*normalized=*/true) + std::move(sub);
328        } else {
329            ret = "[" + OriginString(StringType::PUBLIC, /*normalized=*/true) + "]" + std::move(sub);
330        }
331        return true;
332    }
333    void GetPrivKey(int pos, const SigningProvider& arg, FlatSigningProvider& out) const override
334    {
335        m_provider->GetPrivKey(pos, arg, out);
336    }
337    std::optional<CPubKey> GetRootPubKey() const override
338    {
339        return m_provider->GetRootPubKey();
340    }
341    std::optional<CExtPubKey> GetRootExtPubKey() const override
342    {
343        return m_provider->GetRootExtPubKey();
344    }
345    std::unique_ptr<PubkeyProvider> Clone() const override
346    {
347        return std::make_unique<OriginPubkeyProvider>(m_expr_index, m_origin, m_provider->Clone(), m_apostrophe);
348    }
349    bool CanSelfExpand() const override { return m_provider->CanSelfExpand(); }
350};
351
352/** An object representing a parsed constant public key in a descriptor. */
353class ConstPubkeyProvider final : public PubkeyProvider
354{
355    CPubKey m_pubkey;
356    bool m_xonly;
357
358    std::optional<CKey> GetPrivKey(const SigningProvider& arg) const
359    {
360        CKey key;
361        if (!(m_xonly ? arg.GetKeyByXOnly(XOnlyPubKey(m_pubkey), key) :
362                        arg.GetKey(m_pubkey.GetID(), key))) return std::nullopt;
363        return key;
364    }
365
366public:
367    ConstPubkeyProvider(uint32_t exp_index, const CPubKey& pubkey, bool xonly) : PubkeyProvider(exp_index), m_pubkey(pubkey), m_xonly(xonly) {}
368    std::optional<CPubKey> GetPubKey(int pos, const SigningProvider&, FlatSigningProvider& out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
369    {
370        KeyOriginInfo info;
371        CKeyID keyid = m_pubkey.GetID();
372        info.fingerprint = keyid.fingerprint();
373        out.origins.emplace(keyid, std::make_pair(m_pubkey, info));
374        out.pubkeys.emplace(keyid, m_pubkey);
375        return m_pubkey;
376    }
377    bool IsRange() const override { return false; }
378    size_t GetSize() const override { return m_pubkey.size(); }
379    bool IsBIP32() const override { return false; }
380    std::string ToString(StringType type) const override { return m_xonly ? HexStr(m_pubkey).substr(2) : HexStr(m_pubkey); }
381    bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override
382    {
383        std::optional<CKey> key = GetPrivKey(arg);
384        if (!key) {
385            ret = ToString(StringType::PUBLIC);
386            return false;
387        }
388        ret = EncodeSecret(*key);
389        return true;
390    }
391    bool ToNormalizedString(const SigningProvider& arg, std::string& ret, const DescriptorCache* cache) const override
392    {
393        ret = ToString(StringType::PUBLIC);
394        return true;
395    }
396    void GetPrivKey(int pos, const SigningProvider& arg, FlatSigningProvider& out) const override
397    {
398        std::optional<CKey> key = GetPrivKey(arg);
399        if (!key) return;
400        out.keys.emplace(key->GetPubKey().GetID(), *key);
401    }
402    std::optional<CPubKey> GetRootPubKey() const override
403    {
404        return m_pubkey;
405    }
406    std::optional<CExtPubKey> GetRootExtPubKey() const override
407    {
408        return std::nullopt;
409    }
410    std::unique_ptr<PubkeyProvider> Clone() const override
411    {
412        return std::make_unique<ConstPubkeyProvider>(m_expr_index, m_pubkey, m_xonly);
413    }
414    bool CanSelfExpand() const final { return true; }
415};
416
417enum class DeriveType {
418    NON_RANGED,
419    UNHARDENED_RANGED,
420    HARDENED_RANGED,
421};
422
423/** An object representing a parsed extended public key in a descriptor. */
424class BIP32PubkeyProvider final : public PubkeyProvider
425{
426    // Root xpub, path, and final derivation step type being used, if any
427    CExtPubKey m_root_extkey;
428    KeyPath m_path;
429    DeriveType m_derive;
430    // Whether ' or h is used in harded derivation
431    bool m_apostrophe;
432
433    bool GetExtKey(const SigningProvider& arg, CExtKey& ret) const
434    {
435        CKey key;
436        if (!arg.GetKey(m_root_extkey.pubkey.GetID(), key)) return false;
437        ret.nDepth = m_root_extkey.nDepth;
438        ret.fingerprint = m_root_extkey.fingerprint;
439        ret.nChild = m_root_extkey.nChild;
440        ret.chaincode = m_root_extkey.chaincode;
441        ret.key = key;
442        return true;
443    }
444
445    // Derives the last xprv
446    bool GetDerivedExtKey(const SigningProvider& arg, CExtKey& xprv, CExtKey& last_hardened) const
447    {
448        if (!GetExtKey(arg, xprv)) return false;
449        for (auto entry : m_path) {
450            if (!xprv.Derive(xprv, entry)) return false;
451            if (entry >> 31) {
452                last_hardened = xprv;
453            }
454        }
455        return true;
456    }
457
458    bool IsHardened() const
459    {
460        if (m_derive == DeriveType::HARDENED_RANGED) return true;
461        return HasHardenedDerivation(m_path);
462    }
463
464public:
465    BIP32PubkeyProvider(uint32_t exp_index, const CExtPubKey& extkey, KeyPath path, DeriveType derive, bool apostrophe) : PubkeyProvider(exp_index), m_root_extkey(extkey), m_path(std::move(path)), m_derive(derive), m_apostrophe(apostrophe) {}
466    bool IsRange() const override { return m_derive != DeriveType::NON_RANGED; }
467    size_t GetSize() const override { return 33; }
468    bool IsBIP32() const override { return true; }
469    std::optional<CPubKey> GetPubKey(int pos, const SigningProvider& arg, FlatSigningProvider& out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
470    {
471        KeyOriginInfo info;
472        info.fingerprint = m_root_extkey.id_key_fingerprint();
473        info.path = m_path;
474        if (m_derive == DeriveType::UNHARDENED_RANGED) info.path.push_back((uint32_t)pos);
475        if (m_derive == DeriveType::HARDENED_RANGED) info.path.push_back(((uint32_t)pos) | BIP32_HARDENED_FLAG);
476
477        // Derive keys or fetch them from cache
478        CExtPubKey final_extkey = m_root_extkey;
479        CExtPubKey parent_extkey = m_root_extkey;
480        CExtPubKey last_hardened_extkey;
481        bool der = true;
482        if (read_cache) {
483            if (!read_cache->GetCachedDerivedExtPubKey(m_expr_index, pos, final_extkey)) {
484                if (m_derive == DeriveType::HARDENED_RANGED) return std::nullopt;
485                // Try to get the derivation parent
486                if (!read_cache->GetCachedParentExtPubKey(m_expr_index, parent_extkey)) return std::nullopt;
487                final_extkey = parent_extkey;
488                if (m_derive == DeriveType::UNHARDENED_RANGED) der = parent_extkey.Derive(final_extkey, pos);
489            }
490        } else if (IsHardened()) {
491            CExtKey xprv;
492            CExtKey lh_xprv;
493            if (!GetDerivedExtKey(arg, xprv, lh_xprv)) return std::nullopt;
494            parent_extkey = xprv.Neuter();
495            if (m_derive == DeriveType::UNHARDENED_RANGED) der = xprv.Derive(xprv, pos);
496            if (m_derive == DeriveType::HARDENED_RANGED) der = xprv.Derive(xprv, pos | BIP32_HARDENED_FLAG);
497            final_extkey = xprv.Neuter();
498            if (lh_xprv.key.IsValid()) {
499                last_hardened_extkey = lh_xprv.Neuter();
500            }