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

5 files changed, 105 insertions, 2 deletions

diff --git a/test/functional/rpc_deriveaddresses.py b/test/functional/rpc_deriveaddresses.py
index c66d91713f..32fdfa350a 100755
--- a/test/functional/rpc_deriveaddresses.py
+++ b/test/functional/rpc_deriveaddresses.py
@@ -29,6 +29,9 @@ class DeriveaddressesTest(BitcoinTestFramework):
         assert_equal(self.nodes[0].deriveaddresses(ranged_descriptor, [1, 2]), ["bcrt1qhku5rq7jz8ulufe2y6fkcpnlvpsta7rq4442dy", "bcrt1qpgptk2gvshyl0s9lqshsmx932l9ccsv265tvaq"])
         assert_equal(self.nodes[0].deriveaddresses(ranged_descriptor, 2), [address, "bcrt1qhku5rq7jz8ulufe2y6fkcpnlvpsta7rq4442dy", "bcrt1qpgptk2gvshyl0s9lqshsmx932l9ccsv265tvaq"])
 
+        ranged_descriptor = descsum_create("wpkh(tprv8ZgxMBicQKsPd7Uf69XL1XwhmjHopUGep8GuEiJDZmbQz6o58LninorQAfcKZWARbtRtfnLcJ5MQ2AtHcQJCCRUcMRvmDUjyEmNUWwx8UbK/1/<0;1>/*)")
+        assert_equal(self.nodes[0].deriveaddresses(ranged_descriptor, [1, 2]), [["bcrt1q7c8mdmdktrzs8xgpjmqw90tjn65j5a3yj04m3n", "bcrt1qs6n37uzu0v0qfzf0r0csm0dwa7prc0v5uavgy0"], ["bcrt1qhku5rq7jz8ulufe2y6fkcpnlvpsta7rq4442dy", "bcrt1qpgptk2gvshyl0s9lqshsmx932l9ccsv265tvaq"]])
+
         assert_raises_rpc_error(-8, "Range should not be specified for an un-ranged descriptor", self.nodes[0].deriveaddresses, descsum_create("wpkh(tprv8ZgxMBicQKsPd7Uf69XL1XwhmjHopUGep8GuEiJDZmbQz6o58LninorQAfcKZWARbtRtfnLcJ5MQ2AtHcQJCCRUcMRvmDUjyEmNUWwx8UbK/1/1/0)"), [0, 2])
 
         assert_raises_rpc_error(-8, "Range must be specified for a ranged descriptor", self.nodes[0].deriveaddresses, descsum_create("wpkh(tprv8ZgxMBicQKsPd7Uf69XL1XwhmjHopUGep8GuEiJDZmbQz6o58LninorQAfcKZWARbtRtfnLcJ5MQ2AtHcQJCCRUcMRvmDUjyEmNUWwx8UbK/1/1/*)"))
diff --git a/test/functional/rpc_getdescriptorinfo.py b/test/functional/rpc_getdescriptorinfo.py
index c84928462d..e4e6d6f0f3 100755
--- a/test/functional/rpc_getdescriptorinfo.py
+++ b/test/functional/rpc_getdescriptorinfo.py
@@ -19,10 +19,15 @@ class DescriptorTest(BitcoinTestFramework):
         self.extra_args = [["-disablewallet"]]
         self.wallet_names = []
 
-    def test_desc(self, desc, isrange, issolvable, hasprivatekeys):
+    def test_desc(self, desc, isrange, issolvable, hasprivatekeys, expanded_descs=None):
         info = self.nodes[0].getdescriptorinfo(desc)
         assert_equal(info, self.nodes[0].getdescriptorinfo(descsum_create(desc)))
-        assert_equal(info['descriptor'], descsum_create(desc))
+        if expanded_descs is not None:
+            assert_equal(info["descriptor"], descsum_create(expanded_descs[0]))
+            assert_equal(info["multipath_expansion"], [descsum_create(x) for x in expanded_descs])
+        else:
+            assert_equal(info['descriptor'], descsum_create(desc))
+            assert "multipath_expansion" not in info
         assert_equal(info['isrange'], isrange)
         assert_equal(info['issolvable'], issolvable)
         assert_equal(info['hasprivatekeys'], hasprivatekeys)
@@ -60,6 +65,11 @@ class DescriptorTest(BitcoinTestFramework):
         self.test_desc("pkh([d34db33f/44h/0h/0h]tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/1/*)", isrange=True, issolvable=True, hasprivatekeys=False)
         # A set of *1-of-2* P2WSH multisig outputs where the first multisig key is the *1/0/`i`* child of the first specified xpub and the second multisig key is the *0/0/`i`* child of the second specified xpub, and `i` is any number in a configurable range (`0-1000` by default).
         self.test_desc("wsh(multi(1,tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/1/0/*,tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/0/0/*))", isrange=True, issolvable=True, hasprivatekeys=False)
+        # A multipath descriptor
+        self.test_desc("wpkh(tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/<0;1>/*)", isrange=True, issolvable=True, hasprivatekeys=False,
+            expanded_descs=["wpkh(tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/0/*)", "wpkh(tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/1/*)"])
+        self.test_desc("wsh(multi(1,tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/<1;2>/0/*,tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/<2;3>/0/*))", isrange=True, issolvable=True, hasprivatekeys=False,
+            expanded_descs=["wsh(multi(1,tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/1/0/*,tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/2/0/*))", "wsh(multi(1,tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/2/0/*,tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/3/0/*))"])
 
 
 if __name__ == '__main__':
diff --git a/test/functional/rpc_scantxoutset.py b/test/functional/rpc_scantxoutset.py
index e53e2fa910..a7b560ef57 100755
--- a/test/functional/rpc_scantxoutset.py
+++ b/test/functional/rpc_scantxoutset.py
@@ -110,6 +110,7 @@ class ScantxoutsetTest(BitcoinTestFramework):
         assert_equal(self.nodes[0].scantxoutset("start", [{"desc": "combo(tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/1/1/*)", "range": 1499}])['total_amount'], Decimal("12.288"))
         assert_equal(self.nodes[0].scantxoutset("start", [{"desc": "combo(tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/1/1/*)", "range": 1500}])['total_amount'], Decimal("28.672"))
         assert_equal(self.nodes[0].scantxoutset("start", [{"desc": "combo(tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/1/1/*)", "range": [1500, 1500]}])['total_amount'], Decimal("16.384"))
+        assert_equal(self.nodes[0].scantxoutset("start", [ {"desc": "pkh(tpubD6NzVbkrYhZ4WaWSyoBvQwbpLkojyoTZPRsgXELWz3Popb3qkjcJyJUGLnL4qHHoQvao8ESaAstxYSnhyswJ76uZPStJRJCTKvosUCJZL5B/1/1/<0;1>)"}])["total_amount"], Decimal("12.288"))
 
         # Test the reported descriptors for a few matches
         assert_equal(descriptors(self.nodes[0].scantxoutset("start", [{"desc": "combo(tprv8ZgxMBicQKsPd7Uf69XL1XwhmjHopUGep8GuEiJDZmbQz6o58LninorQAfcKZWARbtRtfnLcJ5MQ2AtHcQJCCRUcMRvmDUjyEmNUWwx8UbK/0h/0h/*)", "range": 1499}])), ["pkh([0c5f9a1e/0h/0h/0]026dbd8b2315f296d36e6b6920b1579ca75569464875c7ebe869b536a7d9503c8c)#rthll0rg", "pkh([0c5f9a1e/0h/0h/1]033e6f25d76c00bedb3a8993c7d5739ee806397f0529b1b31dda31ef890f19a60c)#mcjajulr"])
diff --git a/test/functional/wallet_importdescriptors.py b/test/functional/wallet_importdescriptors.py
index 6a69377c63..84c07b6a28 100755
--- a/test/functional/wallet_importdescriptors.py
+++ b/test/functional/wallet_importdescriptors.py
@@ -16,6 +16,7 @@ variants.
   and test the values returned."""
 
 import concurrent.futures
+import time
 
 from test_framework.authproxy import JSONRPCException
 from test_framework.blocktools import COINBASE_MATURITY
@@ -708,5 +709,56 @@ class ImportDescriptorsTest(BitcoinTestFramework):
 
         assert_equal(temp_wallet.getbalance(), encrypted_wallet.getbalance())
 
+        self.log.info("Multipath descriptors")
+        self.nodes[1].createwallet(wallet_name="multipath", descriptors=True, blank=True)
+        w_multipath = self.nodes[1].get_wallet_rpc("multipath")
+        self.nodes[1].createwallet(wallet_name="multipath_split", descriptors=True, blank=True)
+        w_multisplit = self.nodes[1].get_wallet_rpc("multipath_split")
+        timestamp = int(time.time())
+
+        self.test_importdesc({"desc": descsum_create(f"wpkh({xpriv}/<10;20>/0/*)"),
+                              "active": True,
+                              "range": 10,
+                              "timestamp": "now",
+                              "label": "some label"},
+                              success=False,
+                              error_code=-8,
+                              error_message="Multipath descriptors should not have a label",
+                              wallet=w_multipath)
+        self.test_importdesc({"desc": descsum_create(f"wpkh({xpriv}/<10;20>/0/*)"),
+                              "active": True,
+                              "range": 10,
+                              "timestamp": timestamp,
+                              "internal": True},
+                              success=False,
+                              error_code=-5,
+                              error_message="Cannot have multipath descriptor while also specifying \'internal\'",
+                              wallet=w_multipath)
+
+        self.test_importdesc({"desc": descsum_create(f"wpkh({xpriv}/<10;20>/0/*)"),
+                              "active": True,
+                              "range": 10,
+                              "timestamp": timestamp},
+                              success=True,
+                              wallet=w_multipath)
+
+        self.test_importdesc({"desc": descsum_create(f"wpkh({xpriv}/10/0/*)"),
+                              "active": True,
+                              "range": 10,
+                              "timestamp": timestamp},
+                              success=True,
+                              wallet=w_multisplit)
+        self.test_importdesc({"desc": descsum_create(f"wpkh({xpriv}/20/0/*)"),
+                              "active": True,
+                              "range": 10,
+                              "internal": True,
+                              "timestamp": timestamp},
+                              success=True,
+                              wallet=w_multisplit)
+        for _ in range(0, 10):
+            assert_equal(w_multipath.getnewaddress(address_type="bech32"), w_multisplit.getnewaddress(address_type="bech32"))
+            assert_equal(w_multipath.getrawchangeaddress(address_type="bech32"), w_multisplit.getrawchangeaddress(address_type="bech32"))
+        assert_equal(sorted(w_multipath.listdescriptors()["descriptors"], key=lambda x: x["desc"]), sorted(w_multisplit.listdescriptors()["descriptors"], key=lambda x: x["desc"]))
+
 if __name__ == '__main__':
     ImportDescriptorsTest(__file__).main()
diff --git a/test/functional/wallet_importmulti.py b/test/functional/wallet_importmulti.py
index 42b470bb97..3ce794dc2f 100755
--- a/test/functional/wallet_importmulti.py
+++ b/test/functional/wallet_importmulti.py
@@ -896,6 +896,43 @@ class ImportMultiTest(BitcoinTestFramework):
         )
         assert result[0]['success']
 
+        self.log.info("Multipath descriptors")
+        self.nodes[1].createwallet(wallet_name="multipath", blank=True, disable_private_keys=True)
+        w_multipath = self.nodes[1].get_wallet_rpc("multipath")
+        self.nodes[1].createwallet(wallet_name="multipath_split", blank=True, disable_private_keys=True)
+        w_multisplit = self.nodes[1].get_wallet_rpc("multipath_split")
+
+        res = w_multipath.importmulti([{"desc": descsum_create(f"wpkh({xpub}/<10;20>/0/*)"),
+                              "keypool": True,
+                              "range": 10,
+                              "timestamp": "now",
+                              "internal": True}])
+        assert_equal(res[0]["success"], False)
+        assert_equal(res[0]["error"]["code"], -5)
+        assert_equal(res[0]["error"]["message"], "Cannot have multipath descriptor while also specifying 'internal'")
+
+        res = w_multipath.importmulti([{"desc": descsum_create(f"wpkh({xpub}/<10;20>/0/*)"),
+                              "keypool": True,
+                              "range": 10,
+                              "timestamp": "now"}])
+        assert_equal(res[0]["success"], True)
+
+        res = w_multisplit.importmulti([{"desc": descsum_create(f"wpkh({xpub}/10/0/*)"),
+                              "keypool": True,
+                              "range": 10,
+                              "timestamp": "now"}])
+        assert_equal(res[0]["success"], True)
+        res = w_multisplit.importmulti([{"desc": descsum_create(f"wpkh({xpub}/20/0/*)"),
+                              "keypool": True,
+                              "range": 10,
+                              "internal": True,
+                              "timestamp": timestamp}])
+        assert_equal(res[0]["success"], True)
+
+        for _ in range(0, 9):
+            assert_equal(w_multipath.getnewaddress(address_type="bech32"), w_multisplit.getnewaddress(address_type="bech32"))
+            assert_equal(w_multipath.getrawchangeaddress(address_type="bech32"), w_multisplit.getrawchangeaddress(address_type="bech32"))
+
 
 if __name__ == '__main__':
     ImportMultiTest(__file__).main()