Fix bug in LessSelectionStrategy where `MinPaymentThreshold` parameter was not properly respected
MODIFY
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
@@ -148,17 +148,17 @@ public class BranchAndBoundTests
{
using CancellationTokenSource cts = new(TimeSpan.FromSeconds(30));
- long[] inputValues = new long[] { 20 };
- long[] inputCosts = new long[] { 0 };
+ // Minimum we can get is 40, but that is more than the allowed maximum (i.e. 25 * 1.25 = 31.25).
+ long[] inputValues = new long[] { 60, 50, 40 };
+ long[] inputCosts = new long[] { 0, 0, 0 };
- long target = 10;
+ long target = 25;
BranchAndBound algorithm = new();
- StrategyParameters parameters = new(target, inputValues, inputCosts);
+ StrategyParameters parameters = new(target, inputValues, inputCosts, maxInputCount: 2);
MoreSelectionStrategy strategy = new(parameters);
_ = algorithm.TryGetMatch(strategy, out _, cts.Token);
- // 20 is more than allowed by the "max extra payment" parameter.
long[] result = strategy.GetBestSelectionFound()!;
Assert.Null(result);
}
@@ -271,7 +271,7 @@ public class BranchAndBoundTests
BranchAndBound algorithm = new();
StrategyParameters parameters = new(target, inputValues, inputCosts, maxInputCount: 5);
- LessSelectionStrategy strategy = new(parameters);
+ LessSelectionStrategy strategy = new(parameters, minPaymentThreshold: 0.0);
_ = algorithm.TryGetMatch(strategy, out _, cts.Token);
long[] actualSelection = strategy.GetBestSelectionFound()!;
@@ -287,17 +287,19 @@ public class BranchAndBoundTests
{
using CancellationTokenSource cts = new(TimeSpan.FromSeconds(30));
- long[] inputValues = new long[] { 10 };
- long[] inputCosts = new long[] { 0 };
+ // BnB is set to allow only two-coin selections, so we get selections summing to 20 as best candidates.
+ // However, taking the minimum payment threshold limit into account (i.e. 40 * 1.75 = 30),
+ // thus we cannot accept any selection lower than 30.
+ long[] inputValues = new long[] { 10, 10, 10, 1, 1, 1, 1, 1, 1 };
+ long[] inputCosts = new long[] { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
- long target = 20;
+ long target = 40;
BranchAndBound algorithm = new();
- StrategyParameters parameters = new(target, inputValues, inputCosts);
+ StrategyParameters parameters = new(target, inputValues, inputCosts, maxInputCount: 2);
LessSelectionStrategy strategy = new(parameters);
_ = algorithm.TryGetMatch(strategy, out _, cts.Token);
- // 10 is more than allowed by the "min payment threshold" parameter.
long[] result = strategy.GetBestSelectionFound()!;
Assert.Null(result);
}

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/CoinSelection.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/CoinSelection.cs
@@ -8,9 +8,9 @@ namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
/// </summary>
public class CoinSelection
{
- public CoinSelection(long sum, long sumWithCosts)
+ public CoinSelection(long paymentAmount, long sumWithCosts)
{
- PaymentAmount = sum;
+ PaymentAmount = paymentAmount;
TotalCosts = sumWithCosts;
IncludedCoinsCount = 0;
}

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/LessSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/LessSelectionStrategy.cs
@@ -11,16 +11,28 @@ public class LessSelectionStrategy : SelectionStrategy
public const double MinPaymentThreshold = 0.75;
/// <inheritdoc/>
- public LessSelectionStrategy(StrategyParameters parameters)
+ public LessSelectionStrategy(StrategyParameters parameters, double minPaymentThreshold = MinPaymentThreshold)
: base(parameters, new CoinSelection(long.MinValue, long.MinValue))
{
- MinimumTarget = (long)(parameters.Target * MinPaymentThreshold);
+ MinimumTarget = (long)(parameters.Target * minPaymentThreshold);
}
/// <summary>Minimum acceptable target (inclusive).</summary>
/// <seealso cref="SelectionStrategy.Target"/>
public long MinimumTarget { get; }
+ /// <inheritdoc/>
+ public override long[]? GetBestSelectionFound()
+ {
+ if (BestSelection.PaymentAmount < MinimumTarget)
+ {
+ return null;
+ }
+
+ return BestSelection.GetSolutionArray();
+ }
+
+ /// <inheritdoc/>
public override EvaluationResult Evaluate(long[] selection, int depth, long sum)
{
long totalCost = sum + CurrentInputCosts;

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/MoreSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/MoreSelectionStrategy.cs
@@ -11,16 +11,17 @@ public class MoreSelectionStrategy : SelectionStrategy
public const double MaxExtraPayment = 1.25;
/// <inheritdoc/>
- public MoreSelectionStrategy(StrategyParameters parameters)
+ public MoreSelectionStrategy(StrategyParameters parameters, double maxExtraPayment = MaxExtraPayment)
: base(parameters, new CoinSelection(long.MaxValue, long.MaxValue))
{
- MaximumTarget = (long)(parameters.Target * MaxExtraPayment);
+ MaximumTarget = (long)(parameters.Target * maxExtraPayment);
}
/// <summary>Maximum acceptable target (inclusive).</summary>
/// <seealso cref="SelectionStrategy.Target"/>
public long MaximumTarget { get; }
+ /// <inheritdoc/>
public override EvaluationResult Evaluate(long[] selection, int depth, long sum)
{
long totalCost = sum + CurrentInputCosts;

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/SelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/SelectionStrategy.cs
@@ -46,8 +46,8 @@ public abstract class SelectionStrategy
/// <remarks>Each i-th element represents a sum of all <c>i+1, i+2, ..., n</c> input values.</remarks>
protected long[] RemainingAmounts { get; set; }
- /// <summary>Gets best found selection as an array of effective values, or <c>null</c> if none was found.</summary>
- public long[]? GetBestSelectionFound() => BestSelection.GetSolutionArray();
+ /// <summary>Gets best valid found selection as an array of effective values, or <c>null</c> if none was found.</summary>
+ public virtual long[]? GetBestSelectionFound() => BestSelection.GetSolutionArray();
/// <summary>
/// Modifies selection sum so that we don't need to recompute it.

Fix bug in LessSelectionStrategy where `MinPaymentThreshold` parameter was not properly respected