wallet: reuse change dest when recreating TX with avoidpartialspends

Github-Pull: #27053
Rebased-From: 14b4921a91920df25b19ff420bfe2bff8c56f71e

4 files changed, 123 insertions, 9 deletions

diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index f534e10799..1807a98db1 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -1074,6 +1074,13 @@ util::Result<CreatedTransactionResult> CreateTransaction(
         TRACE1(coin_selection, attempting_aps_create_tx, wallet.GetName().c_str());
         CCoinControl tmp_cc = coin_control;
         tmp_cc.m_avoid_partial_spends = true;
+
+        // Re-use the change destination from the first creation attempt to avoid skipping BIP44 indexes
+        const int ungrouped_change_pos = txr_ungrouped.change_pos;
+        if (ungrouped_change_pos != -1) {
+            ExtractDestination(txr_ungrouped.tx->vout[ungrouped_change_pos].scriptPubKey, tmp_cc.destChange);
+        }
+
         auto txr_grouped = CreateTransactionInternal(wallet, vecSend, change_pos, tmp_cc, sign);
         // if fee of this alternative one is within the range of the max fee, we use this one
         const bool use_aps{txr_grouped.has_value() ? (txr_grouped->fee <= txr_ungrouped.fee + wallet.m_max_aps_fee) : false};
diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py
index caa4af957a..b9233ef2cb 100755
--- a/test/functional/test_runner.py
+++ b/test/functional/test_runner.py
@@ -199,6 +199,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..1c0dd09c82
--- /dev/null
+++ b/test/functional/wallet_change_address.py
@@ -0,0 +1,105 @@
+#!/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 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(outputs=[{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(outputs=[{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 9744009af8..ffc3c51bbf 100755
--- a/test/functional/wallet_importdescriptors.py
+++ b/test/functional/wallet_importdescriptors.py
@@ -447,14 +447,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()
@@ -480,12 +480,12 @@ 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')
-        assert(send_txid in self.nodes[0].getrawmempool(True))
-        assert(send_txid in (x['txid'] for x in wmulti_pub.listunspent(0)))
+        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)
 
         # generate some utxos for next tests