Fix test & fix bugs
MODIFY
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
@@ -115,7 +115,7 @@ public class BranchAndBoundTests
Assert.Equal(new long[] { 1_000_000 }, actualSelection);
}
- [Fact(Skip = "If the first coin is not selected the test fails to finish. TODO.")]
+ [Fact]
public void LessSelection_RemainingAmountOptimization()
{
using CancellationTokenSource cts = new(TimeSpan.FromSeconds(30));
@@ -142,6 +142,25 @@ public class BranchAndBoundTests
Assert.NotNull(actualSelection);
}
+ [Fact]
+ public void LesserSelection_CoinSumIsLowerThanTarget()
+ {
+ using CancellationTokenSource cts = new(TimeSpan.FromSeconds(30));
+
+ long[] inputValues = new long[] { 5, 4, 3, 2, 1 };
+ long[] inputCosts = new long[] { 1, 1, 1, 1, 1 };
+
+ long target = 16;
+
+ BranchAndBound algorithm = new();
+ LessSelectionStrategy strategy = new(target, inputValues, inputCosts);
+ _ = algorithm.TryGetMatch(strategy, out _, cts.Token);
+
+ long[] actualSelection = strategy.GetBestSelectionFound()!;
+ Assert.NotNull(actualSelection);
+ Assert.Equal(new long[] { 5, 4, 3, 2, 1 }, actualSelection);
+ }
+
[Fact]
public void LesserSelection_NoInputCosts()
{

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/LessSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/LessSelectionStrategy.cs
@@ -7,12 +7,20 @@ namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
/// </summary>
public class LessSelectionStrategy : SelectionStrategy
{
+ /// <summary>Payments are capped to be at most 25% lower than the original target.</summary>
+ public const double MinPaymentThreshold = 0.75;
+
/// <inheritdoc/>
public LessSelectionStrategy(long target, long[] inputValues, long[] inputCosts)
: base(target, inputValues, inputCosts, new CoinSelection(long.MinValue, long.MinValue))
{
+ MinimumTarget = (long)(target * MinPaymentThreshold);
}
+ /// <summary>Minimum acceptable target (inclusive).</summary>
+ /// <seealso cref="SelectionStrategy.Target"/>
+ public long MinimumTarget { get; }
+
public override EvaluationResult Evaluate(long[] selection, int depth, long sum)
{
long totalCost = sum + CurrentInputCosts;
@@ -23,9 +31,11 @@ public class LessSelectionStrategy : SelectionStrategy
return EvaluationResult.SkipBranch;
}
- if (sum + RemainingAmounts[depth - 1] < BestSelection.PaymentAmount)
+ long maximumSum = sum + RemainingAmounts[depth - 1];
+
+ if (maximumSum < BestSelection.PaymentAmount || maximumSum < MinimumTarget)
{
- // The remaining coins cannot sum up to our best solution, cut the branch.
+ // The remaining coins cannot sum up to our best solution, or it is less than minimum acceptable target value.
return EvaluationResult.SkipBranch;
}

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/MoreSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/MoreSelectionStrategy.cs
@@ -7,17 +7,25 @@ namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
/// </summary>
public class MoreSelectionStrategy : SelectionStrategy
{
+ /// <summary>Payments are capped to be at most 25% higher than the original target.</summary>
+ public const double MaxExtraPayment = 1.25;
+
/// <inheritdoc/>
public MoreSelectionStrategy(long target, long[] inputValues, long[] inputCosts)
: base(target, inputValues, inputCosts, new CoinSelection(long.MaxValue, long.MaxValue))
{
+ MaximumTarget = (long)(target * MaxExtraPayment);
}
+ /// <summary>Maximum acceptable target (inclusive).</summary>
+ /// <seealso cref="SelectionStrategy.Target"/>
+ public long MaximumTarget { get; }
+
public override EvaluationResult Evaluate(long[] selection, int depth, long sum)
{
long totalCost = sum + CurrentInputCosts;
- if (sum > BestSelection.PaymentAmount)
+ if (sum > BestSelection.PaymentAmount || sum > MaximumTarget)
{
// Our solution is already better than what we might get here.
return EvaluationResult.SkipBranch;

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
-using NBitcoin;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
-using System.Linq;
using System.Threading;
using WalletWasabi.Blockchain.TransactionBuilding.BnB;
@@ -22,11 +20,6 @@ public class BranchAndBound
{
selectedValues = null;
- if (searchStrategy.InputValues.Sum() < searchStrategy.Target)
- {
- return false;
- }
-
if (TryFindSolution(searchStrategy, out long[]? solution, cancellationToken))
{
selectedValues = new List<long>();

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelector.cs
WalletWasabi/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelector.cs
@@ -13,12 +13,6 @@ namespace WalletWasabi.Blockchain.TransactionBuilding;
public static class ChangelessTransactionCoinSelector
{
- /// <summary>Payments are capped to be at most 25% higher than the original target.</summary>
- public const double MaxExtraPayment = 1.25;
-
- /// <summary>Payments are capped to be at most 25% lower than the original target.</summary>
- public const double MinPaymentThreshold = 0.75;
-
public static async IAsyncEnumerable<IEnumerable<SmartCoin>> GetAllStrategyResultsAsync(
IEnumerable<SmartCoin> availableCoins,
FeeRate feeRate,
@@ -96,12 +90,6 @@ public static class ChangelessTransactionCoinSelector
if (solution is not null)
{
- // Sanity check: do not return solution that is much higher or much lower than the target.
- if (solution.Sum() > target * MaxExtraPayment || solution.Sum() < target * MinPaymentThreshold)
- {
- return false;
- }
-
List<SmartCoin> resultCoins = new();
int i = 0;

Fix test & fix bugs