Add `MaxInputCount` parameter to restrict maximum number of coins in the final selection
MODIFY
WalletWasabi.Fluent/ViewModels/Wallets/Send/ChangeAvoidanceSuggestionViewModel.cs
WalletWasabi.Fluent/ViewModels/Wallets/Send/ChangeAvoidanceSuggestionViewModel.cs
+using NBitcoin;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Threading;
using System.Threading.Tasks;
-using NBitcoin;
using WalletWasabi.Blockchain.TransactionBuilding;
-using WalletWasabi.Blockchain.TransactionBuilding.BnB;
-using WalletWasabi.Blockchain.TransactionOutputs;
using WalletWasabi.Fluent.Helpers;
using WalletWasabi.Wallets;
@@ -46,12 +44,14 @@ public partial class ChangeAvoidanceSuggestionViewModel : SuggestionViewModel
TransactionInfo transactionInfo,
BitcoinAddress destination,
Wallet wallet,
+ int maxInputCount,
[EnumeratorCancellation] CancellationToken cancellationToken)
{
var selections = ChangelessTransactionCoinSelector.GetAllStrategyResultsAsync(
transactionInfo.Coins,
transactionInfo.FeeRate,
new TxOut(transactionInfo.Amount, destination),
+ maxInputCount,
cancellationToken).ConfigureAwait(false);
await foreach (var selection in selections)

MODIFY
WalletWasabi.Fluent/ViewModels/Wallets/Send/PrivacySuggestionsFlyoutViewModel.cs
WalletWasabi.Fluent/ViewModels/Wallets/Send/PrivacySuggestionsFlyoutViewModel.cs
+using NBitcoin;
+using ReactiveUI;
+using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
-using NBitcoin;
-using ReactiveUI;
using WalletWasabi.Blockchain.Analysis.Clustering;
using WalletWasabi.Blockchain.TransactionBuilding;
using WalletWasabi.Fluent.Helpers;
-using WalletWasabi.Logging;
using WalletWasabi.Wallets;
namespace WalletWasabi.Fluent.ViewModels.Wallets.Send;
@@ -58,8 +58,13 @@ public partial class PrivacySuggestionsFlyoutViewModel : ViewModelBase
if (hasChange && !isFixedAmount && !info.IsPayJoin)
{
- var suggestions =
- ChangeAvoidanceSuggestionViewModel.GenerateSuggestionsAsync(info, destination, wallet, linkedCts.Token);
+ int originalInputCount = transaction.SpentCoins.Count();
+
+ // Use at most 5 coins.
+ int maxInputCount = originalInputCount < 5 ? originalInputCount : 5;
+
+ IAsyncEnumerable<ChangeAvoidanceSuggestionViewModel> suggestions =
+ ChangeAvoidanceSuggestionViewModel.GenerateSuggestionsAsync(info, destination, wallet, maxInputCount, linkedCts.Token);
await foreach (var suggestion in suggestions)
{

MODIFY
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
@@ -118,6 +118,31 @@ public class BranchAndBoundTests
Assert.Equal(new long[] { 1_000_000 }, actualSelection);
}
+
+ [Fact]
+ public void MoreSelection_MaxInputCountTest()
+ {
+ using CancellationTokenSource cts = new(TimeSpan.FromSeconds(30));
+
+ long[] inputValues = new long[] { 20, 10, 10, 10, 5, 5, 5, 1, 1 };
+ long[] inputCosts = new long[] { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
+
+ long target = 52;
+
+ BranchAndBound algorithm = new();
+ StrategyParameters parameters = new(target, inputValues, inputCosts, maxInputCount: 5);
+ MoreSelectionStrategy moreStrategy = new(parameters);
+ _ = algorithm.TryGetMatch(moreStrategy, out _, cts.Token);
+
+ long[] result = moreStrategy.GetBestSelectionFound()!;
+
+ Assert.NotNull(result);
+
+ // BnB should have chosen { 20, 10, 10, 10, 1, 1 } but with the MaxInputCount this is the best we can get.
+ Assert.Equal(new long[] { 20, 10, 10, 10, 5 }, result);
+ Assert.Equal(5, result.Length);
+ }
+
[Fact]
public void LessSelection_RemainingAmountOptimization()
{
@@ -213,4 +238,26 @@ public class BranchAndBoundTests
// Total costs: (17 + 2) + (10 + 3) + (3 + 1) + (2 + 1) = 39
Assert.Equal(new long[] { 17, 10, 3, 2 }, actualSelection);
}
+
+ [Fact]
+ public void LesserSelection_MaxInputCountTest()
+ {
+ using CancellationTokenSource cts = new(TimeSpan.FromSeconds(30));
+
+ long[] inputValues = new long[] { 1, 1, 1, 1, 1, 1, 1, 1, 1 };
+ long[] inputCosts = new long[] { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
+
+ long target = 9;
+
+ BranchAndBound algorithm = new();
+ StrategyParameters parameters = new(target, inputValues, inputCosts, maxInputCount: 5);
+ LessSelectionStrategy lessStrategy = new(parameters);
+ _ = algorithm.TryGetMatch(lessStrategy, out _, cts.Token);
+
+ long[] actualSelection = lessStrategy.GetBestSelectionFound()!;
+
+ Assert.NotNull(actualSelection);
+ Assert.Equal(new long[] { 1, 1, 1, 1, 1, }, actualSelection);
+ Assert.Equal(5, actualSelection.Length);
+ }
}

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/LessSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/LessSelectionStrategy.cs
@@ -25,6 +25,12 @@ public class LessSelectionStrategy : SelectionStrategy
{
long totalCost = sum + CurrentInputCosts;
+ if (IncludedCoinsCount > Parameters.MaxInputCount)
+ {
+ // Too many coins in the selection. Cut the branch.
+ return EvaluationResult.SkipBranch;
+ }
+
if (sum > Target)
{
// Excessive funds, cut the branch.

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/MoreSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/MoreSelectionStrategy.cs
@@ -25,6 +25,12 @@ public class MoreSelectionStrategy : SelectionStrategy
{
long totalCost = sum + CurrentInputCosts;
+ if (IncludedCoinsCount > Parameters.MaxInputCount)
+ {
+ // Too many coins in the selection. Cut the branch.
+ return EvaluationResult.SkipBranch;
+ }
+
if (sum > BestSelection.PaymentAmount || sum > MaximumTarget)
{
// Our solution is already better than what we might get here.

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/StrategyParameters.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/StrategyParameters.cs
@@ -15,10 +15,14 @@ public record StrategyParameters
/// <remarks>Costs corresponding to <see cref="InputValues"/> values. So the arrays has to have the same lengths.</remarks>
public long[] InputCosts { get; }
+ /// <summary>Maximum number of coins that can be included in a selection.</summary>
+ public int MaxInputCount { get; }
+
/// <param name="target">Target value (in satoshis) we want to, ideally, sum up from the input values.</param>
/// <param name="inputValues">Values in satoshis of the coins the user has (in descending order).</param>
/// <param name="inputCosts">Costs of spending coins in satoshis.</param>
- public StrategyParameters(long target, long[] inputValues, long[] inputCosts)
+ /// <param name="maxInputCount">Optionally, maximum number of coins that can be included in a selection, or "infinity".</param>
+ public StrategyParameters(long target, long[] inputValues, long[] inputCosts, int maxInputCount = int.MaxValue)
{
if (inputValues.Length != inputCosts.Length)
{
@@ -28,5 +32,6 @@ public record StrategyParameters
Target = target;
InputValues = inputValues;
InputCosts = inputCosts;
+ MaxInputCount = maxInputCount;
}
}

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelector.cs
WalletWasabi/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelector.cs
@@ -17,6 +17,7 @@ public static class ChangelessTransactionCoinSelector
IEnumerable<SmartCoin> availableCoins,
FeeRate feeRate,
TxOut txOut,
+ int maxInputCount = int.MaxValue,
[EnumeratorCancellation] CancellationToken cancellationToken = default)
{
// target = target amount + output cost
@@ -33,7 +34,7 @@ public static class ChangelessTransactionCoinSelector
// Pass smart coins' effective values in descending order.
long[] inputValues = inputEffectiveValues.Values.ToArray();
- StrategyParameters parameters = new(target, inputValues, inputCosts);
+ StrategyParameters parameters = new(target, inputValues, inputCosts, maxInputCount);
var strategies = new SelectionStrategy[]
{

Add `MaxInputCount` parameter to restrict maximum number of coins in the final selection