Merge bitcoin/bitcoin#22838: descriptors: Be able to specify change and receiving in a single descriptor string

a0abcbd3822bd17a1d73c42ccd5b040a150b0501 doc: Mention multipath specifier (Ava Chow)
0019f61fc546b4d5f42eb4086f42560863fe0efb tests: Test importing of multipath descriptors (Ava Chow)
f97d5c137d605ac48f1122a836c9aa5f834957ba wallet, rpc: Allow importdescriptors to import multipath descriptors (Ava Chow)
32dcbca3fb918bc899a0637f876db31c3419aafd rpc: Allow importmulti to import multipath descriptors correctly (Ava Chow)
64dfe3ce4bed9ac168d0b08def8af7485db94ef1 wallet: Move internal to be per key when importing (Ava Chow)
16922455253f47fae0466c4ec6c3adfadcfe9182 tests: Multipath descriptors for scantxoutset and deriveaddresses (Ava Chow)
cddc0ba9a9dca3ca5873d768b3b504cdb2ab947b rpc: Have deriveaddresses derive receiving and change (Ava Chow)
360456cd221501fde3efe11bdba5c6d999dbb323 tests: Multipath descriptors for getdescriptorinfo (Ava Chow)
a90eee444c965bbd7bcddf9656eca9cee14c3aec tests: Add unit tests for multipath descriptors (Ava Chow)
1bbf46e2dae4599d04c79aaacf7c5db00b2e707f descriptors: Change Parse to return vector of descriptors (Ava Chow)
0d640c6f02bc20e5c1be773443dd74d8806d953b descriptors: Have ParseKeypath handle multipath specifiers (Ava Chow)
a5f39b103461a98689fd5d382e8da29037f55bea descriptors: Change ParseScript to return vector of descriptors (Ava Chow)
0d55deae157f4f8226b2419d55e7dc0dfb6e4aec descriptors: Add DescriptorImpl::Clone (Ava Chow)
7e86541f723d62c7ec6768f7f592c09ba2047d9e descriptors: Add PubkeyProvider::Clone (Ava Chow)

Pull request description:

  It is convenient to have a descriptor which specifies both receiving and change addresses in a single string. However, as discussed in https://github.com/bitcoin/bitcoin/issues/17190#issuecomment-895515768, it is not feasible to use a generic multipath specification like BIP 88 due to combinatorial blow up and that it would result in unexpected descriptors.

  To resolve that problem, this PR proposes a targeted solution which allows only a single pair of 2 derivation indexes to be inserted in the place of a single derivation index. So instead of two descriptor `wpkh(xpub.../0/0/*)` and `wpkh(xpub.../0/1/*)` to represent receive and change addresses, this could be written as `wpkh(xpub.../0/<0;1>/*)`. The multipath specifier is of the form `<NUM;NUM>`. Each `NUM` can have its own hardened specifier, e.g. `<0;1h>` is valid. The multipath specifier can also only appear in one path index in the derivation path.

  This results in the parser returning two descriptors. The first descriptor uses the first `NUM` in all pairs present, and the second uses the second `NUM`. In our implementation, if a multipath descriptor is not provided, a pair is still returned, but the second element is just `nullptr`.

  The wallet will not output the multipath descriptors (yet). Furthermore, when a multipath descriptor is imported, it is expanded to the two descriptors and each imported on its own, with the second descriptor being implicitly for internal (change) addresses. There is no change to how the wallet stores or outputs descriptors (yet).

  Note that the path specifier is different from what was proposed. It uses angle brackets and the semicolon because these are unused characters available in the character set and I wanted to avoid conflicts with characters already in use in descriptors.

  Closes #17190

ACKs for top commit:
  darosior:
    re-ACK a0abcbd3822bd17a1d73c42ccd5b040a150b0501
  mjdietzx:
    reACK a0abcbd3822bd17a1d73c42ccd5b040a150b0501
  pythcoiner:
    reACK a0abcbd
  furszy:
    Code review ACK a0abcbd
  glozow:
    light code review ACK a0abcbd3822

Tree-SHA512: 84ea40b3fd1b762194acd021cae018c2f09b98e595f5e87de5c832c265cfe8a6d0bc4dae25785392fa90db0f6301ddf9aea787980a29c74f81d04b711ac446c2

1 files changed, 120 insertions, 82 deletions

diff --git a/src/wallet/rpc/backup.cpp b/src/wallet/rpc/backup.cpp
index 0d0e86ed24..20d09b1d9a 100644
--- a/src/wallet/rpc/backup.cpp
+++ b/src/wallet/rpc/backup.cpp
@@ -471,7 +471,7 @@ RPCHelpMan importpubkey()
 
         pwallet->ImportScriptPubKeys(strLabel, script_pub_keys, /*have_solving_data=*/true, /*apply_label=*/true, /*timestamp=*/1);
 
-        pwallet->ImportPubKeys({pubKey.GetID()}, {{pubKey.GetID(), pubKey}} , /*key_origins=*/{}, /*add_keypool=*/false, /*internal=*/false, /*timestamp=*/1);
+        pwallet->ImportPubKeys({{pubKey.GetID(), false}}, {{pubKey.GetID(), pubKey}} , /*key_origins=*/{}, /*add_keypool=*/false, /*timestamp=*/1);
     }
     if (fRescan)
     {
@@ -916,7 +916,7 @@ static std::string RecurseImportData(const CScript& script, ImportData& import_d
     NONFATAL_UNREACHABLE();
 }
 
-static UniValue ProcessImportLegacy(ImportData& import_data, std::map<CKeyID, CPubKey>& pubkey_map, std::map<CKeyID, CKey>& privkey_map, std::set<CScript>& script_pub_keys, bool& have_solving_data, const UniValue& data, std::vector<CKeyID>& ordered_pubkeys)
+static UniValue ProcessImportLegacy(ImportData& import_data, std::map<CKeyID, CPubKey>& pubkey_map, std::map<CKeyID, CKey>& privkey_map, std::set<CScript>& script_pub_keys, bool& have_solving_data, const UniValue& data, std::vector<std::pair<CKeyID, bool>>& ordered_pubkeys)
 {
     UniValue warnings(UniValue::VARR);
 
@@ -982,7 +982,7 @@ static UniValue ProcessImportLegacy(ImportData& import_data, std::map<CKeyID, CP
     for (size_t i = 0; i < pubKeys.size(); ++i) {
         CPubKey pubkey = HexToPubKey(pubKeys[i].get_str());
         pubkey_map.emplace(pubkey.GetID(), pubkey);
-        ordered_pubkeys.push_back(pubkey.GetID());
+        ordered_pubkeys.emplace_back(pubkey.GetID(), internal);
     }
     for (size_t i = 0; i < keys.size(); ++i) {
         const auto& str = keys[i].get_str();
@@ -1055,28 +1055,36 @@ static UniValue ProcessImportLegacy(ImportData& import_data, std::map<CKeyID, CP
     return warnings;
 }
 
-static UniValue ProcessImportDescriptor(ImportData& import_data, std::map<CKeyID, CPubKey>& pubkey_map, std::map<CKeyID, CKey>& privkey_map, std::set<CScript>& script_pub_keys, bool& have_solving_data, const UniValue& data, std::vector<CKeyID>& ordered_pubkeys)
+static UniValue ProcessImportDescriptor(ImportData& import_data, std::map<CKeyID, CPubKey>& pubkey_map, std::map<CKeyID, CKey>& privkey_map, std::set<CScript>& script_pub_keys, bool& have_solving_data, const UniValue& data, std::vector<std::pair<CKeyID, bool>>& ordered_pubkeys)
 {
     UniValue warnings(UniValue::VARR);
 
     const std::string& descriptor = data["desc"].get_str();
     FlatSigningProvider keys;
     std::string error;
-    auto parsed_desc = Parse(descriptor, keys, error, /* require_checksum = */ true);
-    if (!parsed_desc) {
+    auto parsed_descs = Parse(descriptor, keys, error, /* require_checksum = */ true);
+    if (parsed_descs.empty()) {
         throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, error);
     }
-    if (parsed_desc->GetOutputType() == OutputType::BECH32M) {
+    if (parsed_descs.at(0)->GetOutputType() == OutputType::BECH32M) {
         throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, "Bech32m descriptors cannot be imported into legacy wallets");
     }
 
-    have_solving_data = parsed_desc->IsSolvable();
+    std::optional<bool> internal;
+    if (data.exists("internal")) {
+        if (parsed_descs.size() > 1) {
+            throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, "Cannot have multipath descriptor while also specifying \'internal\'");
+        }
+        internal = data["internal"].get_bool();
+    }
+
+    have_solving_data = parsed_descs.at(0)->IsSolvable();
     const bool watch_only = data.exists("watchonly") ? data["watchonly"].get_bool() : false;
 
     int64_t range_start = 0, range_end = 0;
-    if (!parsed_desc->IsRange() && data.exists("range")) {
+    if (!parsed_descs.at(0)->IsRange() && data.exists("range")) {
         throw JSONRPCError(RPC_INVALID_PARAMETER, "Range should not be specified for an un-ranged descriptor");
-    } else if (parsed_desc->IsRange()) {
+    } else if (parsed_descs.at(0)->IsRange()) {
         if (!data.exists("range")) {
             throw JSONRPCError(RPC_INVALID_PARAMETER, "Descriptor is ranged, please specify the range");
         }
@@ -1085,25 +1093,34 @@ static UniValue ProcessImportDescriptor(ImportData& import_data, std::map<CKeyID
 
     const UniValue& priv_keys = data.exists("keys") ? data["keys"].get_array() : UniValue();
 
-    // Expand all descriptors to get public keys and scripts, and private keys if available.
-    for (int i = range_start; i <= range_end; ++i) {
-        FlatSigningProvider out_keys;
-        std::vector<CScript> scripts_temp;
-        parsed_desc->Expand(i, keys, scripts_temp, out_keys);
-        std::copy(scripts_temp.begin(), scripts_temp.end(), std::inserter(script_pub_keys, script_pub_keys.end()));
-        for (const auto& key_pair : out_keys.pubkeys) {
-            ordered_pubkeys.push_back(key_pair.first);
-        }
+    for (size_t j = 0; j < parsed_descs.size(); ++j) {
+        const auto& parsed_desc = parsed_descs.at(j);
+        bool desc_internal = internal.has_value() && internal.value();
+        if (parsed_descs.size() == 2) {
+            desc_internal = j == 1;
+        } else if (parsed_descs.size() > 2) {
+            CHECK_NONFATAL(!desc_internal);
+        }
+        // Expand all descriptors to get public keys and scripts, and private keys if available.
+        for (int i = range_start; i <= range_end; ++i) {
+            FlatSigningProvider out_keys;
+            std::vector<CScript> scripts_temp;
+            parsed_desc->Expand(i, keys, scripts_temp, out_keys);
+            std::copy(scripts_temp.begin(), scripts_temp.end(), std::inserter(script_pub_keys, script_pub_keys.end()));
+            for (const auto& key_pair : out_keys.pubkeys) {
+                ordered_pubkeys.emplace_back(key_pair.first, desc_internal);
+            }
 
-        for (const auto& x : out_keys.scripts) {
-            import_data.import_scripts.emplace(x.second);
-        }
+            for (const auto& x : out_keys.scripts) {
+                import_data.import_scripts.emplace(x.second);
+            }
 
-        parsed_desc->ExpandPrivate(i, keys, out_keys);
+            parsed_desc->ExpandPrivate(i, keys, out_keys);
 
-        std::copy(out_keys.pubkeys.begin(), out_keys.pubkeys.end(), std::inserter(pubkey_map, pubkey_map.end()));
-        std::copy(out_keys.keys.begin(), out_keys.keys.end(), std::inserter(privkey_map, privkey_map.end()));
-        import_data.key_origins.insert(out_keys.origins.begin(), out_keys.origins.end());
+            std::copy(out_keys.pubkeys.begin(), out_keys.pubkeys.end(), std::inserter(pubkey_map, pubkey_map.end()));
+            std::copy(out_keys.keys.begin(), out_keys.keys.end(), std::inserter(privkey_map, privkey_map.end()));
+            import_data.key_origins.insert(out_keys.origins.begin(), out_keys.origins.end());
+        }
     }
 
     for (size_t i = 0; i < priv_keys.size(); ++i) {
@@ -1167,7 +1184,7 @@ static UniValue ProcessImport(CWallet& wallet, const UniValue& data, const int64
         std::map<CKeyID, CPubKey> pubkey_map;
         std::map<CKeyID, CKey> privkey_map;
         std::set<CScript> script_pub_keys;
-        std::vector<CKeyID> ordered_pubkeys;
+        std::vector<std::pair<CKeyID, bool>> ordered_pubkeys;
         bool have_solving_data;
 
         if (data.exists("scriptPubKey") && data.exists("desc")) {
@@ -1200,7 +1217,7 @@ static UniValue ProcessImport(CWallet& wallet, const UniValue& data, const int64
         if (!wallet.ImportPrivKeys(privkey_map, timestamp)) {
             throw JSONRPCError(RPC_WALLET_ERROR, "Error adding key to wallet");
         }
-        if (!wallet.ImportPubKeys(ordered_pubkeys, pubkey_map, import_data.key_origins, add_keypool, internal, timestamp)) {
+        if (!wallet.ImportPubKeys(ordered_pubkeys, pubkey_map, import_data.key_origins, add_keypool, timestamp)) {
             throw JSONRPCError(RPC_WALLET_ERROR, "Error adding address to wallet");
         }
         if (!wallet.ImportScriptPubKeys(label, script_pub_keys, have_solving_data, !internal, timestamp)) {
@@ -1447,22 +1464,28 @@ static UniValue ProcessDescriptorImport(CWallet& wallet, const UniValue& data, c
 
         const std::string& descriptor = data["desc"].get_str();
         const bool active = data.exists("active") ? data["active"].get_bool() : false;
-        const bool internal = data.exists("internal") ? data["internal"].get_bool() : false;
         const std::string label{LabelFromValue(data["label"])};
 
         // Parse descriptor string
         FlatSigningProvider keys;
         std::string error;
-        auto parsed_desc = Parse(descriptor, keys, error, /* require_checksum = */ true);
-        if (!parsed_desc) {
+        auto parsed_descs = Parse(descriptor, keys, error, /* require_checksum = */ true);
+        if (parsed_descs.empty()) {
             throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, error);
         }
+        std::optional<bool> internal;
+        if (data.exists("internal")) {
+            if (parsed_descs.size() > 1) {
+                throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, "Cannot have multipath descriptor while also specifying \'internal\'");
+            }
+            internal = data["internal"].get_bool();
+        }
 
         // Range check
         int64_t range_start = 0, range_end = 1, next_index = 0;
-        if (!parsed_desc->IsRange() && data.exists("range")) {
+        if (!parsed_descs.at(0)->IsRange() && data.exists("range")) {
             throw JSONRPCError(RPC_INVALID_PARAMETER, "Range should not be specified for an un-ranged descriptor");
-        } else if (parsed_desc->IsRange()) {
+        } else if (parsed_descs.at(0)->IsRange()) {
             if (data.exists("range")) {
                 auto range = ParseDescriptorRange(data["range"]);
                 range_start = range.first;
@@ -1484,10 +1507,15 @@ static UniValue ProcessDescriptorImport(CWallet& wallet, const UniValue& data, c
         }
 
         // Active descriptors must be ranged
-        if (active && !parsed_desc->IsRange()) {
+        if (active && !parsed_descs.at(0)->IsRange()) {
             throw JSONRPCError(RPC_INVALID_PARAMETER, "Active descriptors must be ranged");
         }
 
+        // Multipath descriptors should not have a label
+        if (parsed_descs.size() > 1 && data.exists("label")) {
+            throw JSONRPCError(RPC_INVALID_PARAMETER, "Multipath descriptors should not have a label");
+        }
+
         // Ranged descriptors should not have a label
         if (data.exists("range") && data.exists("label")) {
             throw JSONRPCError(RPC_INVALID_PARAMETER, "Ranged descriptors should not have a label");
@@ -1499,7 +1527,7 @@ static UniValue ProcessDescriptorImport(CWallet& wallet, const UniValue& data, c
         }
 
         // Combo descriptor check
-        if (active && !parsed_desc->IsSingleType()) {
+        if (active && !parsed_descs.at(0)->IsSingleType()) {
             throw JSONRPCError(RPC_WALLET_ERROR, "Combo descriptors cannot be set to active");
         }
 
@@ -1508,61 +1536,70 @@ static UniValue ProcessDescriptorImport(CWallet& wallet, const UniValue& data, c
             throw JSONRPCError(RPC_WALLET_ERROR, "Cannot import private keys to a wallet with private keys disabled");
         }
 
-        // Need to ExpandPrivate to check if private keys are available for all pubkeys
-        FlatSigningProvider expand_keys;
-        std::vector<CScript> scripts;
-        if (!parsed_desc->Expand(0, keys, scripts, expand_keys)) {
-            throw JSONRPCError(RPC_WALLET_ERROR, "Cannot expand descriptor. Probably because of hardened derivations without private keys provided");
-        }
-        parsed_desc->ExpandPrivate(0, keys, expand_keys);
-
-        // Check if all private keys are provided
-        bool have_all_privkeys = !expand_keys.keys.empty();
-        for (const auto& entry : expand_keys.origins) {
-            const CKeyID& key_id = entry.first;
-            CKey key;
-            if (!expand_keys.GetKey(key_id, key)) {
-                have_all_privkeys = false;
-                break;
+        for (size_t j = 0; j < parsed_descs.size(); ++j) {
+            auto parsed_desc = std::move(parsed_descs[j]);
+            bool desc_internal = internal.has_value() && internal.value();
+            if (parsed_descs.size() == 2) {
+                desc_internal = j == 1;
+            } else if (parsed_descs.size() > 2) {
+                CHECK_NONFATAL(!desc_internal);
+            }
+            // Need to ExpandPrivate to check if private keys are available for all pubkeys
+            FlatSigningProvider expand_keys;
+            std::vector<CScript> scripts;
+            if (!parsed_desc->Expand(0, keys, scripts, expand_keys)) {
+                throw JSONRPCError(RPC_WALLET_ERROR, "Cannot expand descriptor. Probably because of hardened derivations without private keys provided");
+            }
+            parsed_desc->ExpandPrivate(0, keys, expand_keys);
+
+            // Check if all private keys are provided
+            bool have_all_privkeys = !expand_keys.keys.empty();
+            for (const auto& entry : expand_keys.origins) {
+                const CKeyID& key_id = entry.first;
+                CKey key;
+                if (!expand_keys.GetKey(key_id, key)) {
+                    have_all_privkeys = false;
+                    break;
+                }
             }
-        }
 
-        // If private keys are enabled, check some things.
-        if (!wallet.IsWalletFlagSet(WALLET_FLAG_DISABLE_PRIVATE_KEYS)) {
-           if (keys.keys.empty()) {
-                throw JSONRPCError(RPC_WALLET_ERROR, "Cannot import descriptor without private keys to a wallet with private keys enabled");
-           }
-           if (!have_all_privkeys) {
-               warnings.push_back("Not all private keys provided. Some wallet functionality may return unexpected errors");
-           }
-        }
+            // If private keys are enabled, check some things.
+            if (!wallet.IsWalletFlagSet(WALLET_FLAG_DISABLE_PRIVATE_KEYS)) {
+               if (keys.keys.empty()) {
+                    throw JSONRPCError(RPC_WALLET_ERROR, "Cannot import descriptor without private keys to a wallet with private keys enabled");
+               }
+               if (!have_all_privkeys) {
+                   warnings.push_back("Not all private keys provided. Some wallet functionality may return unexpected errors");
+               }
+            }
 
-        WalletDescriptor w_desc(std::move(parsed_desc), timestamp, range_start, range_end, next_index);
+            WalletDescriptor w_desc(std::move(parsed_desc), timestamp, range_start, range_end, next_index);
 
-        // Check if the wallet already contains the descriptor
-        auto existing_spk_manager = wallet.GetDescriptorScriptPubKeyMan(w_desc);
-        if (existing_spk_manager) {
-            if (!existing_spk_manager->CanUpdateToWalletDescriptor(w_desc, error)) {
-                throw JSONRPCError(RPC_INVALID_PARAMETER, error);
+            // Check if the wallet already contains the descriptor
+            auto existing_spk_manager = wallet.GetDescriptorScriptPubKeyMan(w_desc);
+            if (existing_spk_manager) {
+                if (!existing_spk_manager->CanUpdateToWalletDescriptor(w_desc, error)) {
+                    throw JSONRPCError(RPC_INVALID_PARAMETER, error);
+                }
             }
-        }
 
-        // Add descriptor to the wallet
-        auto spk_manager = wallet.AddWalletDescriptor(w_desc, keys, label, internal);
-        if (spk_manager == nullptr) {
-            throw JSONRPCError(RPC_WALLET_ERROR, strprintf("Could not add descriptor '%s'", descriptor));
-        }
+            // Add descriptor to the wallet
+            auto spk_manager = wallet.AddWalletDescriptor(w_desc, keys, label, desc_internal);
+            if (spk_manager == nullptr) {
+                throw JSONRPCError(RPC_WALLET_ERROR, strprintf("Could not add descriptor '%s'", descriptor));
+            }
 
-        // Set descriptor as active if necessary
-        if (active) {
-            if (!w_desc.descriptor->GetOutputType()) {
-                warnings.push_back("Unknown output type, cannot set descriptor to active.");
+            // Set descriptor as active if necessary
+            if (active) {
+                if (!w_desc.descriptor->GetOutputType()) {
+                    warnings.push_back("Unknown output type, cannot set descriptor to active.");
+                } else {
+                    wallet.AddActiveScriptPubKeyMan(spk_manager->GetID(), *w_desc.descriptor->GetOutputType(), desc_internal);
+                }
             } else {
-                wallet.AddActiveScriptPubKeyMan(spk_manager->GetID(), *w_desc.descriptor->GetOutputType(), internal);
-            }
-        } else {
-            if (w_desc.descriptor->GetOutputType()) {
-                wallet.DeactivateScriptPubKeyMan(spk_manager->GetID(), *w_desc.descriptor->GetOutputType(), internal);
+                if (w_desc.descriptor->GetOutputType()) {
+                    wallet.DeactivateScriptPubKeyMan(spk_manager->GetID(), *w_desc.descriptor->GetOutputType(), desc_internal);
+                }
             }
         }
 
@@ -1579,6 +1616,7 @@ RPCHelpMan importdescriptors()
 {
     return RPCHelpMan{"importdescriptors",
                 "\nImport descriptors. This will trigger a rescan of the blockchain based on the earliest timestamp of all descriptors being imported. Requires a new wallet backup.\n"
+            "When importing descriptors with multipath key expressions, if the multipath specifier contains exactly two elements, the descriptor produced from the second elements will be imported as an internal descriptor.\n"
             "\nNote: This call can take over an hour to complete if using an early timestamp; during that time, other rpc calls\n"
             "may report that the imported keys, addresses or scripts exist but related transactions are still missing.\n"
             "The rescan is significantly faster if block filters are available (using startup option \"-blockfilterindex=1\").\n",