Merge bitcoin/bitcoin#27053: wallet: reuse change dest when re-creating TX with avoidpartialspends

14b4921a91920df25b19ff420bfe2bff8c56f71e wallet: reuse change dest when recreating TX with avoidpartialspends (Matthew Zipkin)

Pull request description:

  Closes https://github.com/bitcoin/bitcoin/issues/27051

  When the wallet creates a transaction internally, it will also create an alternative that spends using destination groups and see if the fee difference is negligible. If it costs the user the same to send the grouped version, we send it (even if the user has `avoidpartialspends` set to `false` which is default). This patch ensures that the second transaction creation attempt re-uses the change destination selected by the first attempt. Otherwise, the first change address remains reserved, will not be used in the second attempt, and then will never be used by the wallet, leaving gaps in the BIP44 chain.

  If the user had `avoidpartialspends` set to true, there is no second version of the created transaction and the change addresses are not affected.

  I believe this behavior was introduced in https://github.com/bitcoin/bitcoin/pull/14582

ACKs for top commit:
  achow101:
    ACK 14b4921a91920df25b19ff420bfe2bff8c56f71e

Tree-SHA512: a3d56f251ff4b333fc11325f30d05513e34ab0a2eb703fadd0ad98d167ae074493df1a24068298336c6ed2da6b31aa2befa490bc790bbc260ed357c8f2397659

3 files changed, 117 insertions, 7 deletions

diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py
index 0fe28b3855..26ebce039b 100755
--- a/test/functional/test_runner.py
+++ b/test/functional/test_runner.py
@@ -216,6 +216,8 @@ BASE_SCRIPTS = [
     'rpc_blockchain.py',
     'rpc_deprecated.py',
     'wallet_disable.py',
+    'wallet_change_address.py --legacy-wallet',
+    'wallet_change_address.py --descriptors',
     'p2p_addr_relay.py',
     'p2p_getaddr_caching.py',
     'p2p_getdata.py',
diff --git a/test/functional/wallet_change_address.py b/test/functional/wallet_change_address.py
new file mode 100755
index 0000000000..f8bfe9eebf
--- /dev/null
+++ b/test/functional/wallet_change_address.py
@@ -0,0 +1,108 @@
+#!/usr/bin/env python3
+# Copyright (c) 2023 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+"""Test wallet change address selection"""
+
+import re
+
+from test_framework.blocktools import COINBASE_MATURITY
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import (
+    assert_equal,
+)
+
+
+class WalletChangeAddressTest(BitcoinTestFramework):
+    def add_options(self, parser):
+        self.add_wallet_options(parser)
+
+    def set_test_params(self):
+        self.setup_clean_chain = True
+        self.num_nodes = 3
+        # discardfee is used to make change outputs less likely in the change_pos test
+        self.extra_args = [
+            [],
+            ["-discardfee=1"],
+            ["-avoidpartialspends", "-discardfee=1"]
+        ]
+
+    def skip_test_if_missing_module(self):
+        self.skip_if_no_wallet()
+
+    def assert_change_index(self, node, tx, index):
+        change_index = None
+        for vout in tx["vout"]:
+            info = node.getaddressinfo(vout["scriptPubKey"]["address"])
+            if (info["ismine"] and info["ischange"]):
+                change_index = int(re.findall(r'\d+', info["hdkeypath"])[-1])
+                break
+        assert_equal(change_index, index)
+
+    def assert_change_pos(self, wallet, tx, pos):
+        change_pos = None
+        for index, output in enumerate(tx["vout"]):
+            info = wallet.getaddressinfo(output["scriptPubKey"]["address"])
+            if (info["ismine"] and info["ischange"]):
+                change_pos = index
+                break
+        assert_equal(change_pos, pos)
+
+    def run_test(self):
+        self.log.info("Setting up")
+        # Mine some coins
+        self.generate(self.nodes[0], COINBASE_MATURITY + 1)
+
+        # Get some addresses from the two nodes
+        addr1 = [self.nodes[1].getnewaddress() for _ in range(3)]
+        addr2 = [self.nodes[2].getnewaddress() for _ in range(3)]
+        addrs = addr1 + addr2
+
+        # Send 1 + 0.5 coin to each address
+        [self.nodes[0].sendtoaddress(addr, 1.0) for addr in addrs]
+        [self.nodes[0].sendtoaddress(addr, 0.5) for addr in addrs]
+        self.generate(self.nodes[0], 1)
+
+        for i in range(20):
+            for n in [1, 2]:
+                self.log.debug(f"Send transaction from node {n}: expected change index {i}")
+                txid = self.nodes[n].sendtoaddress(self.nodes[0].getnewaddress(), 0.2)
+                tx = self.nodes[n].getrawtransaction(txid, True)
+                # find the change output and ensure that expected change index was used
+                self.assert_change_index(self.nodes[n], tx, i)
+
+        # Start next test with fresh wallets and new coins
+        self.nodes[1].createwallet("w1")
+        self.nodes[2].createwallet("w2")
+        w1 = self.nodes[1].get_wallet_rpc("w1")
+        w2 = self.nodes[2].get_wallet_rpc("w2")
+        addr1 = w1.getnewaddress()
+        addr2 = w2.getnewaddress()
+        self.nodes[0].sendtoaddress(addr1, 3.0)
+        self.nodes[0].sendtoaddress(addr1, 0.1)
+        self.nodes[0].sendtoaddress(addr2, 3.0)
+        self.nodes[0].sendtoaddress(addr2, 0.1)
+        self.generate(self.nodes[0], 1)
+
+        sendTo1 = self.nodes[0].getnewaddress()
+        sendTo2 = self.nodes[0].getnewaddress()
+        sendTo3 = self.nodes[0].getnewaddress()
+
+        # The avoid partial spends wallet will always create a change output
+        node = self.nodes[2]
+        res = w2.send({sendTo1: "1.0", sendTo2: "1.0", sendTo3: "0.9999"}, options={"change_position": 0})
+        tx = node.getrawtransaction(res["txid"], True)
+        self.assert_change_pos(w2, tx, 0)
+
+        # The default wallet will internally create a tx without change first,
+        # then create a second candidate using APS that requires a change output.
+        # Ensure that the user-configured change position is kept
+        node = self.nodes[1]
+        res = w1.send({sendTo1: "1.0", sendTo2: "1.0", sendTo3: "0.9999"}, options={"change_position": 0})
+        tx = node.getrawtransaction(res["txid"], True)
+        # If the wallet ignores the user's change_position there is still a 25%
+        # that the random change position passes the test
+        self.assert_change_pos(w1, tx, 0)
+
+if __name__ == '__main__':
+    WalletChangeAddressTest().main()
diff --git a/test/functional/wallet_importdescriptors.py b/test/functional/wallet_importdescriptors.py
index ca0209b61d..9e830088ac 100755
--- a/test/functional/wallet_importdescriptors.py
+++ b/test/functional/wallet_importdescriptors.py
@@ -448,14 +448,14 @@ class ImportDescriptorsTest(BitcoinTestFramework):
                             wallet=wmulti_priv)
 
         assert_equal(wmulti_priv.getwalletinfo()['keypoolsize'], 1001) # Range end (1000) is inclusive, so 1001 addresses generated
-        addr = wmulti_priv.getnewaddress('', 'bech32')
+        addr = wmulti_priv.getnewaddress('', 'bech32') # uses receive 0
         assert_equal(addr, 'bcrt1qdt0qy5p7dzhxzmegnn4ulzhard33s2809arjqgjndx87rv5vd0fq2czhy8') # Derived at m/84'/0'/0'/0
-        change_addr = wmulti_priv.getrawchangeaddress('bech32')
-        assert_equal(change_addr, 'bcrt1qt9uhe3a9hnq7vajl7a094z4s3crm9ttf8zw3f5v9gr2nyd7e3lnsy44n8e')
+        change_addr = wmulti_priv.getrawchangeaddress('bech32') # uses change 0
+        assert_equal(change_addr, 'bcrt1qt9uhe3a9hnq7vajl7a094z4s3crm9ttf8zw3f5v9gr2nyd7e3lnsy44n8e') # Derived at m/84'/1'/0'/0
         assert_equal(wmulti_priv.getwalletinfo()['keypoolsize'], 1000)
         txid = w0.sendtoaddress(addr, 10)
         self.generate(self.nodes[0], 6)
-        send_txid = wmulti_priv.sendtoaddress(w0.getnewaddress(), 8)
+        send_txid = wmulti_priv.sendtoaddress(w0.getnewaddress(), 8) # uses change 1
         decoded = wmulti_priv.gettransaction(txid=send_txid, verbose=True)['decoded']
         assert_equal(len(decoded['vin'][0]['txinwitness']), 4)
         self.sync_all()
@@ -481,10 +481,10 @@ class ImportDescriptorsTest(BitcoinTestFramework):
                             wallet=wmulti_pub)
 
         assert_equal(wmulti_pub.getwalletinfo()['keypoolsize'], 1000) # The first one was already consumed by previous import and is detected as used
-        addr = wmulti_pub.getnewaddress('', 'bech32')
+        addr = wmulti_pub.getnewaddress('', 'bech32') # uses receive 1
         assert_equal(addr, 'bcrt1qp8s25ckjl7gr6x2q3dx3tn2pytwp05upkjztk6ey857tt50r5aeqn6mvr9') # Derived at m/84'/0'/0'/1
-        change_addr = wmulti_pub.getrawchangeaddress('bech32')
-        assert_equal(change_addr, 'bcrt1qzxl0qz2t88kljdnkzg4n4gapr6kte26390gttrg79x66nt4p04fssj53nl')
+        change_addr = wmulti_pub.getrawchangeaddress('bech32') # uses change 2
+        assert_equal(change_addr, 'bcrt1qp6j3jw8yetefte7kw6v5pc89rkgakzy98p6gf7ayslaveaxqyjusnw580c') # Derived at m/84'/1'/0'/2
         assert send_txid in self.nodes[0].getrawmempool(True)
         assert send_txid in (x['txid'] for x in wmulti_pub.listunspent(0))
         assert_equal(wmulti_pub.getwalletinfo()['keypoolsize'], 999)