Privacy: randomized coin selection (BnB changeless + single random draw) (#3408)

diff --git a/.github/workflows/pr_test_build_linux.yml b/.github/workflows/pr_test_build_linux.yml
index addce55..37c2bcf 100644
--- a/.github/workflows/pr_test_build_linux.yml
+++ b/.github/workflows/pr_test_build_linux.yml
@@ -12,6 +12,10 @@ defaults:
 
 jobs:
   PR_test_build:
+    # Fork PRs don't have access to repository secrets, so the generated
+    # lib/.secrets.g.dart would be empty and the build fails to compile.
+    # Skip for forks, mirroring the Android workflow's internal-build guard.
+    if: github.event.pull_request.head.repo.fork == false
     runs-on: [Linux, amd64, forlinux]
     container:
       image: ghcr.io/cake-tech/cake_wallet:debian13-flutter3.41.9-ndkr28-go1.24.1-ruststablenightly
diff --git a/cw_bitcoin/lib/coin_selection.dart b/cw_bitcoin/lib/coin_selection.dart
new file mode 100644
index 0000000..4db86e1
--- /dev/null
+++ b/cw_bitcoin/lib/coin_selection.dart
@@ -0,0 +1,88 @@
+import 'dart:math';
+
+int effectiveValue(int value, int inputCost) => value - inputCost;
+
+class SelectedCoins {
+  final List<int> indices;
+  final bool hasChange;
+  const SelectedCoins(this.indices, this.hasChange);
+}
+
+SelectedCoins? branchAndBound(List<int> effValues, int target, int costOfChange,
+    {int maxTries = 100000}) {
+  final n = effValues.length;
+  final order = List<int>.generate(n, (i) => i)
+    ..sort((a, b) => effValues[b].compareTo(effValues[a]));
+  final sorted = [for (final i in order) effValues[i]];
+  final suffix = List<int>.filled(n + 1, 0);
+  for (var i = n - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + sorted[i];
+  final upper = target + costOfChange;
+  List<int>? best;
+  final picked = <int>[];
+  var tries = 0;
+  void dfs(int i, int sum) {
+    if (best != null || tries++ >= maxTries) return;
+    if (sum > upper) return;
+    if (sum >= target) { best = List.of(picked); return; }
+    if (i >= n || sum + suffix[i] < target) return;
+    picked.add(order[i]); dfs(i + 1, sum + sorted[i]); picked.removeLast();
+    dfs(i + 1, sum);
+  }
+  dfs(0, 0);
+  return best == null ? null : SelectedCoins(best!, false);
+}
+
+SelectedCoins? singleRandomDraw(List<int> effValues, int target, int minChange, Random rng) {
+  final order = List<int>.generate(effValues.length, (i) => i)..shuffle(rng);
+  final picked = <int>[]; var sum = 0;
+  for (final i in order) {
+    picked.add(i); sum += effValues[i];
+    if (sum >= target + minChange) return SelectedCoins(picked, true);
+  }
+  return null;
+}
+
+/// Branch-and-bound over effective values (value minus the cost of spending the
+/// input at the current fee rate). [inputCosts] is parallel to [values] so each
+/// input pays for its own script type's size. A match means the excess over
+/// [target] stays within [window], so the remainder can be absorbed into the fee
+/// instead of creating a change output. Returns null when no such subset exists.
+SelectedCoins? changelessMatch({
+  required List<int> values,
+  required int target,
+  required List<int> inputCosts,
+  required int window,
+  int maxTries = 100000,
+}) {
+  assert(values.length == inputCosts.length);
+  final keep = <int>[];
+  final eff = <int>[];
+  for (var i = 0; i < values.length; i++) {
+    final e = effectiveValue(values[i], inputCosts[i]);
+    if (e > 0) {
+      keep.add(i);
+      eff.add(e);
+    }
+  }
+  final match = branchAndBound(eff, target, window, maxTries: maxTries);
+  if (match == null) return null;
+  return SelectedCoins([for (final i in match.indices) keep[i]], false);
+}
+
+class InsufficientFundsException implements Exception { const InsufficientFundsException(); }
+
+SelectedCoins selectCoins({required List<int> values, required int target,
+    required int inputCost, required int costOfChange, required int minChange, Random? rng}) {
+  final keep = <int>[]; final eff = <int>[];
+  for (var i = 0; i < values.length; i++) {
+    final e = effectiveValue(values[i], inputCost);
+    if (e > 0) { keep.add(i); eff.add(e); }
+  }
+  SelectedCoins? map(SelectedCoins? s) =>
+      s == null ? null : SelectedCoins([for (final i in s.indices) keep[i]], s.hasChange);
+  final bnb = map(branchAndBound(eff, target, costOfChange));
+  if (bnb != null) return bnb;
+  final srd = map(singleRandomDraw(eff, target, minChange, rng ?? Random.secure()));
+  if (srd != null) return srd;
+  throw const InsufficientFundsException();
+}
diff --git a/cw_bitcoin/lib/electrum_wallet.dart b/cw_bitcoin/lib/electrum_wallet.dart
index b69fec5..c82ac8e 100644
--- a/cw_bitcoin/lib/electrum_wallet.dart
+++ b/cw_bitcoin/lib/electrum_wallet.dart
@@ -1,6 +1,7 @@
 import 'dart:async';
 import 'dart:convert';
 import 'dart:isolate';
+import 'dart:math' show Random;
 
 import 'package:bitcoin_base/bitcoin_base.dart';
 import 'package:cw_bitcoin/lightning/lightning_wallet.dart';
@@ -10,6 +11,7 @@ import 'package:cw_core/root_dir.dart';
 import 'package:cw_core/utils/proxy_wrapper.dart';
 import 'package:cw_core/utils/print_verbose.dart';
 import 'package:cw_bitcoin/bitcoin_wallet.dart';
+import 'package:cw_bitcoin/coin_selection.dart';
 import 'package:cw_bitcoin/litecoin_wallet.dart';
 import 'package:shared_preferences/shared_preferences.dart';
 import 'package:blockchain_utils/blockchain_utils.dart';
@@ -261,6 +263,29 @@ abstract class ElectrumWalletBase
   static int estimatedTransactionSize(int inputsCount, int outputsCounts) =>
       inputsCount * 68 + outputsCounts * 34 + 10;
 
+  // vbytes an input of the given script type adds to a transaction. The generic
+  // estimate above assumes P2WPKH (68); legacy and taproot inputs differ enough
+  // to break changeless-match arithmetic if not accounted for.
+  static int estimatedInputSize(BitcoinAddressType type) {
+    if (type == P2pkhAddressType.p2pkh) return 148;
+    if (type == P2shAddressType.p2wpkhInP2sh) return 91;
+    if (type == SegwitAddresType.p2tr) return 58;
+    if (type == SegwitAddresType.p2wsh) return 105;
+    if (type == SilentPaymentsAddresType.p2sp) return 58; // spent via taproot
+    return 68;
+  }
+
+  // vbytes an output of the given script type adds to a transaction. Silent
+  // payment outputs are delivered as taproot.
+  static int estimatedOutputSize(BitcoinAddressType type) {
+    if (type == P2pkhAddressType.p2pkh) return 34;
+    if (type == P2shAddressType.p2wpkhInP2sh) return 32;
+    if (type == SegwitAddresType.p2tr) return 43;
+    if (type == SegwitAddresType.p2wsh) return 43;
+    if (type == SilentPaymentsAddresType.p2sp) return 43;
+    return 31;
+  }
+
   // Parses the account index from a BIP-44/49/84/86 derivation path.
   // e.g. "m/84'/0'/1'" → 1.  Returns 0 for unrecognised formats.
   static int _parseAccountIndex(String? derivationPath) {
@@ -881,11 +906,23 @@ abstract class ElectrumWalletBase
   bool _isBelowDust(BigInt amount) =>
       amount <= networkDustAmount && network != BitcoinNetwork.testnet;
 
+  // Random draw priority per outpoint. Assigned lazily with a secure RNG and kept
+  // until the next createTransaction call, so the recursive estimate passes of one
+  // transaction build all see the same input order (reshuffling between passes made
+  // fee estimation unstable). Cleared per transaction so each send is a fresh draw.
+  final Random _coinSelectionRng = Random.secure();
+  final Map<String, int> _coinSelectionOrder = {};
+
+  int _coinSelectionPriority(BitcoinUnspent utx) => _coinSelectionOrder.putIfAbsent(
+      '${utx.hash}:${utx.vout}', () => _coinSelectionRng.nextInt(1 << 32));
+
   UtxoDetails _createUTXOS({
     required bool sendAll,
     required bool paysToSilentPayment,
     int credentialsAmount = 0,
     int? inputsCount,
+    int feeRate = 0,
+    int? outputsVBytes,
     UnspentCoinType coinTypeToSpendFrom = UnspentCoinType.any,
   }) {
     List<UtxoWithAddress> utxos = [];
@@ -914,8 +951,52 @@ abstract class ElectrumWalletBase
     }).toList();
     final unconfirmedCoins = availableInputs.where((utx) => utx.confirmations == 0).toList();
 
-    // sort the unconfirmed coins so that mweb coins are last:
-    availableInputs.sort((a, b) => a.bitcoinAddressRecord.type == SegwitAddresType.mweb ? 1 : -1);
+    // Single Random Draw: order the pool by each coin's random priority so selection is
+    // non-deterministic, removing the predictable address/scan order (a fingerprint).
+    // The priority is stable across the repeated calls of one transaction build.
+    // MWEB coins are kept last afterwards.
+    availableInputs.sort((a, b) {
+      final byPriority = _coinSelectionPriority(a).compareTo(_coinSelectionPriority(b));
+      if (byPriority != 0) return byPriority;
+      return '${a.hash}:${a.vout}'.compareTo('${b.hash}:${b.vout}');
+    });
+    availableInputs = [
+      ...availableInputs.where((u) => u.bitcoinAddressRecord.type != SegwitAddresType.mweb),
+      ...availableInputs.where((u) => u.bitcoinAddressRecord.type == SegwitAddresType.mweb),
+    ];
+
+    // Branch-and-bound: prefer an input set whose excess over the amount plus its own fee
+    // stays below dust, so the caller drops the change output and the send is changeless.
+    // When no such set exists, the shuffled pool below acts as a single random draw.
+    final canTryChangeless = !sendAll &&
+        inputsCount == null &&
+        credentialsAmount > 0 &&
+        feeRate > 0 &&
+        outputsVBytes != null &&
+        outputsVBytes > 0 &&
+        !availableInputs.any((u) => u.bitcoinAddressRecord.type == SegwitAddresType.mweb);
+    if (canTryChangeless) {
+      final match = changelessMatch(
+        values: [for (final u in availableInputs) u.value],
+        // estimatedTransactionSize(0, 0) is the fixed tx overhead (version,
+        // counters, locktime); the outputs' own vbytes come pre-computed per type.
+        target: credentialsAmount + (estimatedTransactionSize(0, 0) + outputsVBytes!) * feeRate,
+        inputCosts: [
+          for (final u in availableInputs)
+            estimatedInputSize(u.bitcoinAddressRecord.type) * feeRate
+        ],
+        window: networkDustAmount.toInt(),
+      );
+      if (match != null) {
+        final chosen = match.indices.toSet();
+        availableInputs = [
+          for (final i in match.indices) availableInputs[i],
+          for (var i = 0; i < availableInputs.length; i++)
+            if (!chosen.contains(i)) availableInputs[i],
+        ];
+        inputsCount = match.indices.length;
+      }
+    }
 
     for (int i = 0; i < availableInputs.length; i++) {
       final utx = availableInputs[i];
@@ -1131,10 +1212,25 @@ abstract class ElectrumWalletBase
       }
     }
 
+    // Per-type output sizes for the changeless target. MWEB outputs follow a
+    // different size model entirely, so they disable the changeless path (null).
+    int? outputsVBytes = 0;
+    for (final out in outputs) {
+      final type =
+          out.isSilentPayment == true ? SilentPaymentsAddresType.p2sp : _getScriptType(out.address);
+      if (type == SegwitAddresType.mweb) {
+        outputsVBytes = null;
+        break;
+      }
+      outputsVBytes = outputsVBytes! + estimatedOutputSize(type);
+    }
+
     final utxoDetails = _createUTXOS(
       sendAll: false,
       credentialsAmount: credentialsAmount.amount.toInt(),
       inputsCount: inputsCount,
+      feeRate: feeRate,
+      outputsVBytes: outputsVBytes,
       paysToSilentPayment: hasSilentPayment,
       coinTypeToSpendFrom: coinTypeToSpendFrom,
     );
@@ -1397,6 +1493,10 @@ abstract class ElectrumWalletBase
   @override
   Future<PendingTransaction> createTransaction(Object credentials) async {
     try {
+      // New transaction, new random draw: drop the previous input ordering so this
+      // build gets fresh priorities, then keep them fixed for all estimate passes.
+      _coinSelectionOrder.clear();
+
       // start by updating unspent coins
       await updateAllUnspents();
 
@@ -2220,11 +2320,13 @@ abstract class ElectrumWalletBase
         }
       }
 
-      // If still not enough, add UTXOs until the fee is covered
+      // If still not enough, add UTXOs until the fee is covered, drawing them at
+      // random instead of in the predictable wallet scan order (address, then age).
       if (remainingFee > BigInt.zero) {
         final unusedUtxos = unspentCoins
             .where((utxo) => utxo.isSending && !utxo.isFrozen && utxo.confirmations! > 0)
-            .toList();
+            .toList()
+          ..shuffle(Random.secure());
 
         for (final utxo in unusedUtxos) {
           final address = RegexUtils.addressTypeFromStr(utxo.address, network);
diff --git a/cw_bitcoin/lib/payjoin/manager.dart b/cw_bitcoin/lib/payjoin/manager.dart
index efa120f..ba0d616 100644
--- a/cw_bitcoin/lib/payjoin/manager.dart
+++ b/cw_bitcoin/lib/payjoin/manager.dart
@@ -295,6 +295,9 @@ class PayjoinManager {
                 await _wallet.updateAllUnspents();
                 utxos = _wallet.getUtxoWithPrivateKeys(confirmedOnly: true);
               }
+              // Candidates arrive in wallet scan order (address, then age), which is
+              // predictable; shuffle so the receiver's input choice can't mirror it.
+              utxos.shuffle(Random.secure());
               mainToIsolateSendPort?.send({
                 'requestId': message['requestId'],
                 'result': utxos,
diff --git a/cw_bitcoin/test/coin_selection_test.dart b/cw_bitcoin/test/coin_selection_test.dart
new file mode 100644
index 0000000..8708075
--- /dev/null
+++ b/cw_bitcoin/test/coin_selection_test.dart
@@ -0,0 +1,100 @@
+import 'dart:math';
+import "package:cw_bitcoin/coin_selection.dart";
+import "package:flutter_test/flutter_test.dart";
+void main() {
+  test('effectiveValue', () {
+    expect(effectiveValue(10000, 136), 9864);
+    expect(effectiveValue(100, 136), -36);
+  });
+  test('BnB finds changeless match in window', () {
+    final r = branchAndBound([200,100,90,80], 300, 50);
+    expect(r, isNotNull); expect(r!.hasChange, isFalse);
+    final vals=[200,100,90,80]; final sum=r.indices.map((i)=>vals[i]).reduce((a,b)=>a+b);
+    expect(sum>=300 && sum<=350, isTrue);
+  });
+  test('BnB null when no subset in window', () {
+    expect(branchAndBound([1000,900], 300, 5), isNull);
+  });
+  test('SRD with change', () {
+    final r = singleRandomDraw([500,500,500,500], 700, 50, Random(1));
+    expect(r, isNotNull); expect(r!.hasChange, isTrue);
+  });
+  test('SRD randomizes across seeds', () {
+    final a = (singleRandomDraw([100,101,102,103,104,105],150,10,Random(1))!.indices..sort());
+    final b = (singleRandomDraw([100,101,102,103,104,105],150,10,Random(9))!.indices..sort());
+    expect(a, isNot(equals(b)));
+  });
+  test('SRD null on insufficient funds', () {
+    expect(singleRandomDraw([100,100], 500, 10, Random(1)), isNull);
+  });
+  test('selectCoins prefers changeless BnB, else SRD', () {
+    expect(selectCoins(values:[200,100,90],target:300,inputCost:0,costOfChange:20,minChange:10).hasChange, isFalse);
+    expect(selectCoins(values:[500,500,500],target:700,inputCost:0,costOfChange:5,minChange:10,rng:Random(1)).hasChange, isTrue);
+  });
+  test('selectCoins drops non-positive effective values', () {
+    // coin of value 50 with inputCost 136 -> effective -86 -> dropped; only the 1000 usable
+    final r = selectCoins(values:[50,1000],target:500,inputCost:136,costOfChange:5,minChange:10,rng:Random(1));
+    expect(r.indices, equals([1]));
+  });
+  test('changelessMatch finds a set whose effective sum lands in the window', () {
+    // inputCost 100: values [50, 400, 300, 200] -> eff [dropped, 300, 200, 100]
+    // target 500, window 46: eff {300, 200} = 500, exact
+    final r = changelessMatch(
+        values: [50, 400, 300, 200], target: 500, inputCosts: [100, 100, 100, 100], window: 46);
+    expect(r, isNotNull);
+    expect(r!.hasChange, isFalse);
+    final effSum = r.indices.map((i) => [50, 400, 300, 200][i] - 100).reduce((a, b) => a + b);
+    expect(effSum >= 500 && effSum <= 546, isTrue);
+    expect(r.indices.contains(0), isFalse); // negative-eff coin never selected
+  });
+  test('changelessMatch returns null when no subset lands in the window', () {
+    expect(
+        changelessMatch(values: [10000, 9000], target: 500, inputCosts: [100, 100], window: 46),
+        isNull);
+  });
+  test('selectCoins throws when insufficient', () {
+    expect(() => selectCoins(values:[100,100],target:500,inputCost:0,costOfChange:5,minChange:10),
+        throwsA(isA<InsufficientFundsException>()));
+  });
+  test('changeless pipeline: leftover absorbed into fee is non-negative and below dust', () {
+    // Mirrors the _createUTXOS / estimateTxForAmount arithmetic with the wallet's
+    // 68*inputs + 34*outputs + 10 vBytes model, at 10 sat/vB with 1 recipient output.
+    const feeRate = 10;
+    const amount = 50000;
+    final values = [60700, 30000, 21800, 9000, 5000];
+    const target = amount + (34 * 1 + 10) * feeRate;
+    final r = changelessMatch(
+        values: values,
+        target: target,
+        inputCosts: List.filled(values.length, 68 * feeRate),
+        window: 546);
+    expect(r, isNotNull);
+    final inAmount = r!.indices.map((i) => values[i]).reduce((a, b) => a + b);
+    final feeNoChange = (68 * r.indices.length + 34 * 1 + 10) * feeRate;
+    final leftover = inAmount - amount - feeNoChange;
+    expect(leftover >= 0, isTrue); // the caller never recurses for more inputs
+    expect(leftover <= 546, isTrue); // fee overpay is bounded by the dust limit
+  });
+  test('BnB terminates and returns null on large pools with no possible match', () {
+    // 300 even effective values, odd target, zero window: no subset can ever match,
+    // so the search must stop at maxTries instead of exploring 2^300 branches.
+    final values = List<int>.generate(300, (i) => 1000000 + i * 2);
+    final r = changelessMatch(
+        values: values, target: 1500001, inputCosts: List.filled(300, 10), window: 0);
+    expect(r, isNull);
+  });
+  test('changelessMatch charges each input its own script-type cost', () {
+    // Legacy input (148 vB) vs segwit input (68 vB) at 10 sat/vB: same value, but
+    // the legacy coin's effective value is 800 lower. Target only reachable when
+    // the cheaper segwit coin is chosen: eff segwit = 10000-680 = 9320.
+    const feeRate = 10;
+    final r = changelessMatch(
+      values: [10000, 10000],
+      target: 9320,
+      inputCosts: [148 * feeRate, 68 * feeRate],
+      window: 0,
+    );
+    expect(r, isNotNull);
+    expect(r!.indices, equals([1]));
+  });
+}