descriptors: MuSig2 #31244

86@@ -82,13 +87,21 @@ bool FlatSigningProvider::GetTaprootBuilder(const XOnlyPubKey& output_key, Tapro
87     return LookupHelper(tr_trees, output_key, builder);
88 }
89 
90+std::vector<CPubKey> FlatSigningProvider::GetAggregateParticipantPubkeys(const CPubKey& pubkey) const
91+{
92+    const auto& it = aggregate_pubkeys.find(pubkey);
93+    if (it == aggregate_pubkeys.end()) return {};
94+    return it->second;

 5+#ifndef BITCOIN_MUSIG_H
 6+#define BITCOIN_MUSIG_H
 7+
 8+#include <pubkey.h>
 9+
10+#include <vector>

598+    bool IsRangedParticipants() const
599+    {
600+        for (const auto& pubkey : m_participants) {
601+            if (pubkey->IsRange()) return true;
602+        }
603+        return false;

788+        // musig() can only be a BIP 32 key if all participants are bip32 too
789+        bool all_bip32 = true;
790+        for (const auto& pk : m_participants) {
791+            all_bip32 &= pk->IsBIP32();
792+        }
793+        return all_bip32;

638+                // Make the synthetic xpub and construct the BIP32PubkeyProvider
639+                CExtPubKey extpub;
640+                extpub.nDepth = 0;
641+                std::memset(extpub.vchFingerprint, 0, 4);
642+                extpub.nChild = 0;
643+                extpub.chaincode.FromHex("6589e367712c6200e367717145cb322d76576bc3248959c474f9a602ca878086");

11+#include <vector>
12+
13+struct secp256k1_musig_keyagg_cache;
14+
15+bool GetMuSig2KeyAggCache(const std::vector<CPubKey>& pubkeys, secp256k1_musig_keyagg_cache& keyagg_cache);
16+std::optional<CPubKey> GetCPubKeyFromMuSig2KeyAggCache(secp256k1_musig_keyagg_cache& cache);

285@@ -286,6 +286,7 @@ class XOnlyPubKey
286      * This is needed for key lookups since keys are indexed by CKeyID.
287      */
288     std::vector<CKeyID> GetKeyIDs() const;
289+    std::vector<CPubKey> GetCPubKeys() const;

12@@ -13,10 +13,10 @@ namespace script {
13 
14 /** Parse a constant.
15  *
16- * If sp's initial part matches str, sp is updated to skip that part, and true is returned.
17+ * If sp's initial part matches str, sp is optionally updated to skip that part, and true is returned.

 99@@ -100,18 +100,27 @@ void ReplaceAll(std::string& in_out, const std::string& search, const std::strin
100  *
101  * If sep does not occur in sp, a singleton with the entirety of sp is returned.
102  *
103+ * @param[in] include_sep Whether to include the separator at the end of the left side of the splits.

104+ *
105  * Note that this function does not care about braces, so splitting
106  * "foo(bar(1),2),3) on ',' will return {"foo(bar(1)", "2)", "3)"}.
107+ *
108+ * If include_sep == true, splitting "foo(bar(1),2),3) on ','
109+ * will return {"foo(bar(1),", "2),", "3)"}.

220@@ -221,6 +221,9 @@ struct PubkeyProvider
221 
222     /** Make a deep copy of this PubkeyProvider */
223     virtual std::unique_ptr<PubkeyProvider> Clone() const = 0;
224+
225+    /** Whether this PubkeyProvider can be a BIP 32 extended key that can be derived from */

12+
13+struct secp256k1_musig_keyagg_cache;
14+
15+bool GetMuSig2KeyAggCache(const std::vector<CPubKey>& pubkeys, secp256k1_musig_keyagg_cache& keyagg_cache);
16+std::optional<CPubKey> GetCPubKeyFromMuSig2KeyAggCache(secp256k1_musig_keyagg_cache& cache);
17+std::optional<CPubKey> MuSig2AggregatePubkeys(const std::vector<CPubKey>& pubkeys);

10+#include <optional>
11+#include <vector>
12+
13+struct secp256k1_musig_keyagg_cache;
14+
15+bool GetMuSig2KeyAggCache(const std::vector<CPubKey>& pubkeys, secp256k1_musig_keyagg_cache& keyagg_cache);

761+        // If there is not, then the participant privkeys will be included directly
762+        for (const auto& prov : m_participants) {
763+            prov->GetPrivKey(pos, arg, out);
764+        }
765+    }
766+    std::optional<CPubKey> GetRootPubKey() const override

754+        return true;
755+    }
756+
757+    void GetPrivKey(int pos, const SigningProvider& arg, FlatSigningProvider& out) const override
758+    {
759+        // Get the private keys for all participants

725+            } else {
726+                out += pubkey->ToString();
727+            }
728+        }
729+        out += ")";
730+        out += FormatHDKeypath(m_path, /*apostrophe=*/true);

664+            // Either way, we can passthrough to it's GetPubKey
665+            std::optional<CPubKey> pub = m_aggregate_provider->GetPubKey(pos, arg, out, read_cache, write_cache);
666+            if (!pub) return std::nullopt;
667+            pubout = *pub;
668+            out.aggregate_pubkeys.emplace(m_aggregate_pubkey.value(), pubkeys);
669+        } else if (IsRangedParticipants()) {

11@@ -12,6 +12,10 @@
12 
13 struct secp256k1_musig_keyagg_cache;
14 
15+//! MuSig2 chaincode as defined by BIP 328
16+//! uint256 will byteswap the hex
17+constexpr uint256 MUSIG_CHAINCODE{"6589e367712c6200e367717145cb322d76576bc3248959c474f9a602ca878086"};

15+//! MuSig2 chaincode as defined by BIP 328
16+//! uint256 will byteswap the hex
17+using namespace util::hex_literals;
18+constexpr uint256 MUSIG_CHAINCODE{"868087ca02a6f974c4598924c36b57762d32cb45717167e300622c7167e38965"_hex_u8};
19+
20+//! Create a secp56k1_musig_keyagg_cache from the pubkeys in their current order. This is necessary for most MuSig2 operations

782+    std::unique_ptr<PubkeyProvider> Clone() const override
783+    {
784+        std::vector<std::unique_ptr<PubkeyProvider>> providers;
785+        providers.reserve(m_participants.size());
786+        for (const std::unique_ptr<PubkeyProvider>& p : m_participants) {
787+            providers.emplace_back(p->Clone());

715+    bool ToPrivateString(const SigningProvider& arg, std::string& out) const override
716+    {
717+        bool any_privkeys = false;
718+        out = "musig(";
719+        for (size_t i = 0; i < m_participants.size(); ++i) {
720+            const auto& pubkey = m_participants.at(i);

613+        m_derive(derive)
614+    {}
615+
616+    std::optional<CPubKey> GetPubKey(int pos, const SigningProvider& arg, FlatSigningProvider& out, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) const override
617+    {
618+        // If the participants are not ranged, we can compute and cache the aggregate pubkey by creating a PubkeyProvider for it

11@@ -12,6 +12,11 @@
12 
13 struct secp256k1_musig_keyagg_cache;
14 
15+//! MuSig2 chaincode as defined by BIP 328
16+//! uint256 will byteswap the hex
17+using namespace util::hex_literals;
18+constexpr uint256 MUSIG_CHAINCODE{"868087ca02a6f974c4598924c36b57762d32cb45717167e300622c7167e38965"_hex_u8};

632+            // Aggregate the pubkey
633+            m_aggregate_pubkey = MuSig2AggregatePubkeys(pubkeys);
634+            if (!Assume(m_aggregate_pubkey.has_value())) return std::nullopt;
635+
636+            // Make our pubkey provider
637+            if (m_derive != DeriveType::NO || !m_path.empty()) {

1657@@ -1653,7 +1658,7 @@ std::optional<uint32_t> ParseKeyPathNum(std::span<const char> elem, bool& apostr
1658  * @param[in] allow_multipath Allows the parsed path to use the multipath specifier
1659  * @returns false if parsing failed
1660  **/
1661-[[nodiscard]] bool ParseKeyPath(const std::vector<std::span<const char>>& split, std::vector<KeyPath>& out, bool& apostrophe, std::string& error, bool allow_multipath)
1662+[[nodiscard]] bool ParseKeyPath(const std::vector<std::span<const char>>& split, std::vector<KeyPath>& out, bool& apostrophe, std::string& error, bool allow_multipath, bool allow_hardened = true)

1806@@ -1802,9 +1807,153 @@ std::vector<std::unique_ptr<PubkeyProvider>> ParsePubkeyInner(uint32_t key_exp_i
1807 }
1808 
1809 /** Parse a public key including origin information (if enabled). */
1810-std::vector<std::unique_ptr<PubkeyProvider>> ParsePubkey(uint32_t key_exp_index, const std::span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)
1811+// NOLINTNEXTLINE(misc-no-recursion)
1812+std::vector<std::unique_ptr<PubkeyProvider>> ParsePubkey(uint32_t& key_exp_index, const std::span<const char>& sp, ParseScriptContext ctx, FlatSigningProvider& out, std::string& error)

611+        m_participants(std::move(providers)),
612+        m_path(std::move(path)),
613+        m_derive(derive)
614+    {
615+        if (!Assume(!(IsRangedParticipants() && IsRangedDerivation()))) {
616+            throw std::runtime_error("musig(): Cannot have both ranged participatns and ranged derivation");

705+                    break;
706+                case StringType::COMPAT:
707+                    tmp = pubkey->ToString(PubkeyProvider::StringType::COMPAT);
708+                    break;
709+            }
710+            out += tmp;

586+{
587+private:
588+    //! PubkeyProvider for the participants
589+    const std::vector<std::unique_ptr<PubkeyProvider>> m_participants;
590+    //! Derivation path if this is ranged
591+    const KeyPath m_path;

1827+            return {};
1828+        }
1829+        std::span<const char> sp_musig(split.at(0).begin(), split.at(0).end());
1830+
1831+        auto expr = Expr(sp_musig);
1832+        if (!Func("musig", expr)) {

1875+        // Parse any derivation
1876+        DeriveType deriv_type = DeriveType::NO;
1877+        std::vector<KeyPath> paths;
1878+        if (split.size() == 2 && Const("/", split.at(1), /*skip=*/false)) {
1879+            if (!all_bip32) {
1880+                error = "musig(): Ranged musig() requires all participants to be xpubs";

1855+            }
1856+            const auto& [_, inserted] = key_exprs.emplace(arg.begin(), arg.end());
1857+            if (!inserted) {
1858+                error = strprintf("musig(): Cannot have repeated participant key expressions");
1859+                return {};
1860+            }

1813+
1814+    // musig cannot be nested inside of an origin
1815+    std::span<const char> span = sp;
1816+    if (Const("musig(", span, /*skip=*/false)) {
1817+        if (ctx != ParseScriptContext::P2TR) {
1818+            error = "musig() is only allowed in tr()";

1873+        // Parse any derivation
1874+        DeriveType deriv_type = DeriveType::NO;
1875+        std::vector<KeyPath> paths;
1876+        if (split.size() == 2 && Const("/", split.at(1), /*skip=*/false)) {
1877+            if (!all_bip32) {
1878+                error = "musig(): musig() derivation requires all participants to be xpubs";

1856+                error = strprintf("musig(): Cannot have repeated participant key expressions");
1857+                return {};
1858+            }
1859+
1860+            any_ranged |= pk.at(0)->IsRange();
1861+            all_bip32 &= pk.at(0)->IsBIP32();

1925+            }
1926+            ret.emplace_back(std::make_unique<MuSigPubkeyProvider>(key_exp_index, std::move(pubs), path, deriv_type));
1927+        };
1928+
1929+        if (max_providers_len > 1 && paths.size() > 1) {
1930+            error = "musig(): Cannot have multipath participant keys if musig() is also multipath";

596+
597+    bool IsRangedDerivation() const { return m_derive != DeriveType::NO; }
598+    bool IsRangedParticipants() const
599+    {
600+        return std::any_of(m_participants.begin(), m_participants.end(), [](const auto& pubkey) { return pubkey->IsRange(); });
601+    }

603+public:
604+    MuSigPubkeyProvider(
605+        uint32_t exp_index,
606+        std::vector<std::unique_ptr<PubkeyProvider>> providers,
607+        KeyPath path,
608+        DeriveType derive

663+        std::sort(pubkeys.begin(), pubkeys.end());
664+
665+        CPubKey pubout;
666+        if (m_aggregate_provider) {
667+            // When we have a cached aggregate key, we are either returning it or deriving from it
668+            // Either way, we can passthrough to it's GetPubKey

649+
650+                m_aggregate_provider = std::make_unique<BIP32PubkeyProvider>(m_expr_index, extpub, m_path, m_derive, /*apostrophe=*/false);
651+            } else {
652+                m_aggregate_provider = std::make_unique<ConstPubkeyProvider>(m_expr_index, m_aggregate_pubkey.value(), /*xonly=*/false);
653+            }
654+        }

665+
666+        CPubKey pubout;
667+        if (m_aggregate_provider) {
668+            // When we have a cached aggregate key, we are either returning it or deriving from it
669+            // Either way, we can passthrough to its GetPubKey
670+            std::optional<CPubKey> pub = m_aggregate_provider->GetPubKey(pos, arg, out, read_cache, write_cache);

681+            KeyOriginInfo info;
682+            CKeyID keyid = aggregate_pubkey->GetID();
683+            std::copy(keyid.begin(), keyid.begin() + sizeof(info.fingerprint), info.fingerprint);
684+            out.origins.emplace(keyid, std::make_pair(*aggregate_pubkey, info));
685+            out.pubkeys.emplace(aggregate_pubkey->GetID(), *aggregate_pubkey);
686+            out.aggregate_pubkeys.emplace(pubout, pubkeys);

612+    {
613+        if (!Assume(!(m_ranged_participants && IsRangedDerivation()))) {
614+            throw std::runtime_error("musig(): Cannot have both ranged participants and ranged derivation");
615+        }
616+        if (!Assume(m_derive != DeriveType::HARDENED)) {
617+            throw std::runtime_error("musig(): Cannot have hardened hardened derivation");

611+        m_ranged_participants(std::any_of(m_participants.begin(), m_participants.end(), [](const auto& pubkey) { return pubkey->IsRange(); }))
612+    {
613+        if (!Assume(!(m_ranged_participants && IsRangedDerivation()))) {
614+            throw std::runtime_error("musig(): Cannot have both ranged participants and ranged derivation");
615+        }
616+        if (!Assume(m_derive != DeriveType::HARDENED)) {

671+            if (!pub) return std::nullopt;
672+            pubout = *pub;
673+            out.aggregate_pubkeys.emplace(m_aggregate_pubkey.value(), pubkeys);
674+        } else {
675+            if (!Assume(m_ranged_participants)) return std::nullopt;
676+            // Derive participants and compute new aggregate key

659+        for (const auto& prov : m_participants) {
660+            std::optional<CPubKey> pub = prov->GetPubKey(pos, arg, out, read_cache, write_cache);
661+            if (!pub) return std::nullopt;
662+            pubkeys.emplace_back(*pub);
663+        }
664+        std::sort(pubkeys.begin(), pubkeys.end());

12@@ -13,10 +13,10 @@ namespace script {
13 
14 /** Parse a constant.
15  *
16- * If sp's initial part matches str, sp is updated to skip that part, and true is returned.
17+ * If sp's initial part matches str, sp is optionally updated to skip that part, and true is returned.
18  * Otherwise sp is unmodified and false is returned.
19  */
20-bool Const(const std::string& str, std::span<const char>& sp);
21+bool Const(const std::string& str, std::span<const char>& sp, bool skip = true);

160@@ -161,6 +161,7 @@ class SigningProvider
161     virtual bool GetKeyOrigin(const CKeyID& keyid, KeyOriginInfo& info) const { return false; }
162     virtual bool GetTaprootSpendData(const XOnlyPubKey& output_key, TaprootSpendData& spenddata) const { return false; }
163     virtual bool GetTaprootBuilder(const XOnlyPubKey& output_key, TaprootBuilder& builder) const { return false; }
164+    virtual std::vector<CPubKey> GetAggregateParticipantPubkeys(const CPubKey& pubkey) const { return {}; }

20+    for (const secp256k1_pubkey& p : secp_pubkeys) {
21+        pubkey_ptrs.push_back(&p);
22+    }
23+
24+    // Aggregate the pubkey
25+    if (!secp256k1_musig_pubkey_agg(secp256k1_context_static, nullptr, &keyagg_cache, pubkey_ptrs.data(), pubkey_ptrs.size())) {

630+                if (!pubkey.has_value()) {
631+                    return std::nullopt;
632+                }
633+                pubkeys.push_back(pubkey.value());
634+            }
635+            std::sort(pubkeys.begin(), pubkeys.end());

641+            // Make our pubkey provider
642+            if (IsRangedDerivation() || !m_path.empty()) {
643+                // Make the synthetic xpub and construct the BIP32PubkeyProvider
644+                CExtPubKey extpub;
645+                extpub.nDepth = 0;
646+                std::memset(extpub.vchFingerprint, 0, 4);

214@@ -213,6 +215,7 @@ struct FlatSigningProvider final : public SigningProvider
215     std::map<CKeyID, std::pair<CPubKey, KeyOriginInfo>> origins;
216     std::map<CKeyID, CKey> keys;
217     std::map<XOnlyPubKey, TaprootBuilder> tr_trees; /** Map from output key to Taproot tree (which can then make the TaprootSpendData */
218+    std::map<CPubKey, std::vector<CPubKey>> aggregate_pubkeys; /** MuSig2 aggregate pubkeys */

788+    }
789+    bool IsBIP32() const override
790+    {
791+        // musig() can only be a BIP 32 key if all participants are bip32 too
792+        return std::all_of(m_participants.begin(), m_participants.end(), [](const auto& pubkey) { return pubkey->IsBIP32(); });
793+    }

1892+            } else if (std::ranges::equal(deriv_split.back(), std::span{"*'"}.first(2)) || std::ranges::equal(deriv_split.back(), std::span{"*h"}.first(2))) {
1893+                error = "musig(): Cannot have hardened child derivation";
1894+                return {};
1895+            }
1896+            bool dummy = false;
1897+            if (!ParseKeyPath(deriv_split, paths, dummy, error, /*allow_multipath=*/true, /*allow_hardened=*/false)) {

1941+            if (!clone_providers(max_providers_len)) {
1942+                error = strprintf("musig(): Multipath derivation paths have mismatched lengths");
1943+                return {};
1944+            }
1945+            for (size_t i = 0; i < max_providers_len; ++i) {
1946+                // Final MuSigPubkeyProvider use participant pubkey providers at each multipath position, and the first (and only) path

1955+            for (size_t i = 0; i < paths.size(); ++i) {
1956+                // Final MuSigPubkeyProvider uses cloned participant pubkey providers, and the multipath derivation paths
1957+                emplace_final_provider(i, i);
1958+            }
1959+        } else {
1960+            // No multipath derivation MuSigPubkeyProvider uses the first (and only) participant pubkey providers, and the first (and only) path

1877+        // Parse any derivation
1878+        DeriveType deriv_type = DeriveType::NO;
1879+        std::vector<KeyPath> paths;
1880+        if (split.size() == 2 && Const("/", split.at(1), /*skip=*/false)) {
1881+            if (!all_bip32) {
1882+                error = "musig(): derivation requires all participants to be xpubs";

1821+
1822+    using namespace script;
1823+
1824+    // musig cannot be nested inside of an origin
1825+    std::span<const char> span = sp;
1826+    if (Const("musig(", span, /*skip=*/false)) {

1799@@ -1799,10 +1800,168 @@ std::vector<std::unique_ptr<PubkeyProvider>> ParsePubkeyInner(uint32_t key_exp_i
1800     return ret;
1801 }
1802 
1803+static bool IsKeyPathsHardened(const std::vector<KeyPath>& paths)

1888+            }
1889+            auto deriv_split = Split(split.at(1), '/');
1890+            if (std::ranges::equal(deriv_split.back(), std::span{"*"}.first(1))) {
1891+                deriv_split.pop_back();
1892+                deriv_type = DeriveType::UNHARDENED;
1893+            } else if (std::ranges::equal(deriv_split.back(), std::span{"*'"}.first(2)) || std::ranges::equal(deriv_split.back(), std::span{"*h"}.first(2))) {

613+        if (!Assume(!(m_ranged_participants && IsRangedDerivation()))) {
614+            throw std::runtime_error("musig(): Cannot have both ranged participants and ranged derivation");
615+        }
616+        if (!Assume(m_derive != DeriveType::HARDENED)) {
617+            throw std::runtime_error("musig(): Cannot have hardened derivation");
618+        }

1881+            if (!all_bip32) {
1882+                error = "musig(): derivation requires all participants to be xpubs";
1883+                return {};
1884+            }
1885+            if (any_ranged) {
1886+                error = "musig(): Cannot have ranged participant keys if musig() also has derivation";

1851+        while (expr.size()) {
1852+            if (!first && !Const(",", expr)) {
1853+                error = strprintf("musig(): expected ',', got '%c'", expr[0]);
1854+                return {};
1855+            }
1856+            first = false;

1900+                return {};
1901+            }
1902+            if (IsKeyPathsHardened(paths)) {
1903+                error = "musig(): cannot have hardened derivation steps";
1904+                return {};
1905+            }

1949+        } else if (paths.size() > 1) {
1950+            // All key provider vectors should be length 1. Clone them until they have the same length as paths
1951+            if (!clone_providers(paths.size())) {
1952+                error = "musig(): Multipath derivation path with multipath participants is disallowed"; // This error is unreachable due to earlier check
1953+                return {};
1954+            }

1932+                pubs.emplace_back(std::move(vec.at(vec_idx)));
1933+            }
1934+            ret.emplace_back(std::make_unique<MuSigPubkeyProvider>(key_exp_index, std::move(pubs), path, deriv_type));
1935+        };
1936+
1937+        if (max_providers_len > 1 && paths.size() > 1) {