Merge bitcoin/bitcoin#24584: wallet: avoid mixing different `OutputTypes` during coin selection

71d1d13627ccd27319f347e2d8167c8fe8a433f4 test: add unit test for AvailableCoins (josibake)
da03cb41a4ce15ebceee7fa4a4fdd2d3602fe284 test: functional test for new coin selection logic (josibake)
438e04845bf3302b7f459a50e88a1b772527f1e6 wallet: run coin selection by `OutputType` (josibake)
77b07072061c59f50c69be29fbcddf0d433e1077 refactor: use CoinsResult struct in SelectCoins (josibake)
2e67291ca3ab2d8f498fa910738ca655fde11c5e refactor: store by OutputType in CoinsResult (josibake)

Pull request description:

  # Concept

  Following https://github.com/bitcoin/bitcoin/pull/23789, Bitcoin Core wallet will now generate a change address that matches the payment address type. This improves privacy by not revealing which of the outputs is the change at the time of the transaction in scenarios where the input address types differ from the payment address type. However, information about the change can be leaked in a later transaction. This proposal attempts to address that concern.

  ## Leaking information in a later transaction

  Consider the following scenario:

  ![mix input types(1)](https://user-images.githubusercontent.com/7444140/158597086-788339b0-c698-4b60-bd45-9ede4cd3a483.png)

  1. Alice has a wallet with bech32 type UTXOs and pays Bob, who gives her a P2SH address
  2. Alice's wallet generates a P2SH change output, preserving her privacy in `txid: a`
  3. Alice then pays Carol, who gives her a bech32 address
  4. Alice's wallet combines the P2SH UTXO with a bech32 UTXO and `txid: b` has two bech32 outputs

  From a chain analysis perspective, it is reasonable to infer that the P2SH input in `txid: b` was the change from `txid: a`. To avoid leaking information in this scenario, Alice's wallet should avoid picking the P2SH output and instead fund the transaction with only bech32 Outputs. If the payment to Carol can be funded with just the P2SH output, it should be preferred over the bech32 outputs as this will convert the P2SH UTXO to bech32 UTXOs via the payment and change outputs of the new transaction.

  **TLDR;** Avoid mixing output types, spend non-default `OutputTypes` when it is economical to do so.

  # Approach

  `AvailableCoins` now populates a struct, which makes it easier to access coins by `OutputType`. Coin selection tries to find a funding solution by each output type and chooses the most economical by waste metric. If a solution can't be found without mixing, coin selection runs over the entire wallet, allowing mixing, which is the same as the current behavior.

  I've also added a functional test (`test/functional/wallet_avoid_mixing_output_types.py`) and unit test (`src/wallet/test/availablecoins_tests.cpp`.

ACKs for top commit:
  achow101:
    re-ACK 71d1d13627ccd27319f347e2d8167c8fe8a433f4
  aureleoules:
    ACK 71d1d13627ccd27319f347e2d8167c8fe8a433f4.
  Xekyo:
    reACK 71d1d13627ccd27319f347e2d8167c8fe8a433f4 via `git range-diff master 6530d19 71d1d13`
  LarryRuane:
    ACK 71d1d13627ccd27319f347e2d8167c8fe8a433f4

Tree-SHA512: 2e0716efdae5adf5479446fabc731ae81d595131d3b8bade98b64ba323d0e0c6d964a67f8c14c89c428998bda47993fa924f3cfca1529e2bd49eaa4e31b7e426

2 files changed, 177 insertions, 0 deletions

diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py
index c5a69afa6e..e5784eb614 100755
--- a/test/functional/test_runner.py
+++ b/test/functional/test_runner.py
@@ -156,6 +156,7 @@ BASE_SCRIPTS = [
     'mempool_spend_coinbase.py',
     'wallet_avoidreuse.py --legacy-wallet',
     'wallet_avoidreuse.py --descriptors',
+    'wallet_avoid_mixing_output_types.py --descriptors',
     'mempool_reorg.py',
     'mempool_persist.py',
     'p2p_block_sync.py',
diff --git a/test/functional/wallet_avoid_mixing_output_types.py b/test/functional/wallet_avoid_mixing_output_types.py
new file mode 100755
index 0000000000..46f41d9c22
--- /dev/null
+++ b/test/functional/wallet_avoid_mixing_output_types.py
@@ -0,0 +1,176 @@
+#!/usr/bin/env python3
+# Copyright (c) 2022 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or https://www.opensource.org/licenses/mit-license.php.
+"""Test output type mixing during coin selection
+
+A wallet may have different types of UTXOs to choose from during coin selection,
+where output type is one of the following:
+    - BECH32M
+    - BECH32
+    - P2SH-SEGWIT
+    - LEGACY
+
+This test verifies that mixing different output types is avoided unless
+absolutely necessary. Both wallets start with zero funds. Alice mines
+enough blocks to have spendable coinbase outputs. Alice sends three
+random value payments which sum to 10BTC for each output type to Bob,
+for a total of 40BTC in Bob's wallet.
+
+Bob then sends random valued payments back to Alice, some of which need
+unconfirmed change, and we verify that none of these payments contain mixed
+inputs. Finally, Bob sends the remainder of his funds, which requires mixing.
+
+The payment values are random, but chosen such that they sum up to a specified
+total. This ensures we are not relying on specific values for the UTXOs,
+but still know when to expect mixing due to the wallet being close to empty.
+
+"""
+
+import random
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.blocktools import COINBASE_MATURITY
+
+ADDRESS_TYPES = [
+    "bech32m",
+    "bech32",
+    "p2sh-segwit",
+    "legacy",
+]
+
+
+def is_bech32_address(node, addr):
+    """Check if an address contains a bech32 output."""
+    addr_info = node.getaddressinfo(addr)
+    return addr_info['desc'].startswith('wpkh(')
+
+
+def is_bech32m_address(node, addr):
+    """Check if an address contains a bech32m output."""
+    addr_info = node.getaddressinfo(addr)
+    return addr_info['desc'].startswith('tr(')
+
+
+def is_p2sh_segwit_address(node, addr):
+    """Check if an address contains a P2SH-Segwit output.
+       Note: this function does not actually determine the type
+       of P2SH output, but is sufficient for this test in that
+       we are only generating P2SH-Segwit outputs.
+    """
+    addr_info = node.getaddressinfo(addr)
+    return addr_info['desc'].startswith('sh(wpkh(')
+
+
+def is_legacy_address(node, addr):
+    """Check if an address contains a legacy output."""
+    addr_info = node.getaddressinfo(addr)
+    return addr_info['desc'].startswith('pkh(')
+
+
+def is_same_type(node, tx):
+    """Check that all inputs are of the same OutputType"""
+    vins = node.getrawtransaction(tx, True)['vin']
+    inputs = []
+    for vin in vins:
+        prev_tx, n = vin['txid'], vin['vout']
+        inputs.append(
+            node.getrawtransaction(
+                prev_tx,
+                True,
+            )['vout'][n]['scriptPubKey']['address']
+        )
+    has_legacy = False
+    has_p2sh = False
+    has_bech32 = False
+    has_bech32m = False
+
+    for addr in inputs:
+        if is_legacy_address(node, addr):
+            has_legacy = True
+        if is_p2sh_segwit_address(node, addr):
+            has_p2sh = True
+        if is_bech32_address(node, addr):
+            has_bech32 = True
+        if is_bech32m_address(node, addr):
+            has_bech32m = True
+
+    return (sum([has_legacy, has_p2sh, has_bech32, has_bech32m]) == 1)
+
+
+def generate_payment_values(n, m):
+    """Return a randomly chosen list of n positive integers summing to m.
+    Each such list is equally likely to occur."""
+
+    dividers = sorted(random.sample(range(1, m), n - 1))
+    return [a - b for a, b in zip(dividers + [m], [0] + dividers)]
+
+
+class AddressInputTypeGrouping(BitcoinTestFramework):
+    def set_test_params(self):
+        self.setup_clean_chain = True
+        self.num_nodes = 2
+        self.extra_args = [
+            [
+                "-addresstype=bech32",
+                "-whitelist=noban@127.0.0.1",
+                "-txindex",
+            ],
+            [
+                "-addresstype=p2sh-segwit",
+                "-whitelist=noban@127.0.0.1",
+                "-txindex",
+            ],
+        ]
+
+    def skip_test_if_missing_module(self):
+        self.skip_if_no_wallet()
+
+    def make_payment(self, A, B, v, addr_type):
+        fee_rate = random.randint(1, 20)
+        self.log.debug(f"Making payment of {v} BTC at fee_rate {fee_rate}")
+        tx = B.sendtoaddress(
+            address=A.getnewaddress(address_type=addr_type),
+            amount=v,
+            fee_rate=fee_rate,
+        )
+        return tx
+
+    def run_test(self):
+
+        # alias self.nodes[i] to A, B for readability
+        A, B = self.nodes[0], self.nodes[1]
+        self.generate(A, COINBASE_MATURITY + 5)
+
+        self.log.info("Creating mixed UTXOs in B's wallet")
+        for v in generate_payment_values(3, 10):
+            self.log.debug(f"Making payment of {v} BTC to legacy")
+            A.sendtoaddress(B.getnewaddress(address_type="legacy"), v)
+
+        for v in generate_payment_values(3, 10):
+            self.log.debug(f"Making payment of {v} BTC to p2sh")
+            A.sendtoaddress(B.getnewaddress(address_type="p2sh-segwit"), v)
+
+        for v in generate_payment_values(3, 10):
+            self.log.debug(f"Making payment of {v} BTC to bech32")
+            A.sendtoaddress(B.getnewaddress(address_type="bech32"), v)
+
+        for v in generate_payment_values(3, 10):
+            self.log.debug(f"Making payment of {v} BTC to bech32m")
+            A.sendtoaddress(B.getnewaddress(address_type="bech32m"), v)
+
+        self.generate(A, 1)
+
+        self.log.info("Sending payments from B to A")
+        for v in generate_payment_values(5, 9):
+            tx = self.make_payment(
+                A, B, v, random.choice(ADDRESS_TYPES)
+            )
+            self.generate(A, 1)
+            assert is_same_type(B, tx)
+
+        tx = self.make_payment(A, B, 30.99, random.choice(ADDRESS_TYPES))
+        assert not is_same_type(B, tx)
+
+
+if __name__ == '__main__':
+    AddressInputTypeGrouping().main()