Refactor and take input costs into account
MODIFY
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
@@ -13,6 +13,22 @@ public class BranchAndBoundTests
{
private static Random Random { get; } = new();
+ [Fact]
+ public void InvalidInputs()
+ {
+ List<long> inputValues = new() { };
+ ArgumentException argumentException = Assert.Throws<ArgumentException>(() => new BranchAndBound(inputValues));
+ Assert.Equal("List is empty.", argumentException.Message);
+
+ inputValues = new() { -1, 1, 1 };
+ argumentException = Assert.Throws<ArgumentException>(() => new BranchAndBound(inputValues));
+ Assert.Equal("Only strictly positive values are supported.", argumentException.Message);
+
+ inputValues = new() { 1, 2, 3, 1 };
+ argumentException = Assert.Throws<ArgumentException>(() => new BranchAndBound(inputValues));
+ Assert.Equal("Input values must be sorted in descending order.", argumentException.Message);
+ }
+
[Fact]
public void ExactMatch_RandomizedTest()
{
@@ -61,7 +77,8 @@ public class BranchAndBoundTests
}
/// <summary>
- /// Tests that sum of input values must be larger or equal to the target otherwise we end up searching all options in vain.
+ /// Tests that sum of input values must be larger or equal to the target otherwise
+ /// we end up searching all options in vain.
/// </summary>
[Fact]
public void ExactMatch_TargetIsBiggerThanBalance()
@@ -96,20 +113,63 @@ public class BranchAndBoundTests
Assert.Null(selectedCoins);
}
- /// <summary>Tests that best found solution is found when exact solution does not exist.</summary>
+ /// <summary>Tests that a best found selection is found when an exact solution does not exist.</summary>
+ [Fact]
+ public void CheapestSelection_NoInputCosts()
+ {
+ List<long> inputValues = new() { 11, 7, 5, 3, 2 }; // Sum is 28.
+ long[] inputCosts = new long[] { 0, 0, 0, 0, 0 }; // No input costs. Idealized.
+ long target = 27; // Target that we cannot get as a sum of input values.
+
+ BranchAndBound algorithm = new(inputValues);
+ CheapestSelectionStrategy strategy = new(target, inputCosts);
+ bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
+
+ Assert.False(wasSuccessful);
+ Assert.Null(selectedCoins);
+ Assert.Equal(new long[] { 11, 7, 5, 3, 2 }, strategy.GetBestSelectionFound());
+ }
+
[Fact]
- public void BestSum_NoExactSolution()
+ public void CheapestSelection_ExactMatchIsAlsoCheapest()
{
- List<long> inputValues = new() { 2, 3, 5, 7, 11 }; // Sum is 28.
+ List<long> inputValues = new() { 35, 17, 10, 5, 3, 2 };
+
+ // Make the second input very expensive to spend so that it is not selected (not likely in reality).
+ long[] inputCosts = new long[] { 1, 5, 1, 1, 1, 1 };
+
+ long target = 27;
+
+ BranchAndBound algorithm = new(inputValues);
+ CheapestSelectionStrategy strategy = new(target, inputCosts);
+ bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
+
+ Assert.False(wasSuccessful);
+ Assert.Null(selectedCoins);
+
+ Assert.Equal(new long[] { 17, 10 }, strategy.GetBestSelectionFound());
+ }
+
+ [Fact]
+ public void CheapestSelection_ExactMatchIsExpensive()
+ {
+ List<long> inputValues = new() { 35, 17, 10, 5, 3, 2 };
+
+ // Make the second input very expensive to spend so that it is not selected (not likely in reality).
+ long[] inputCosts = new long[] { 1, 1000, 1, 1, 1, 1 };
+
long target = 27; // Target that we cannot get as a sum of input values.
BranchAndBound algorithm = new(inputValues);
- BestSumStrategy strategy = new(target);
+ CheapestSelectionStrategy strategy = new(target, inputCosts);
bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
Assert.False(wasSuccessful);
Assert.Null(selectedCoins);
- Assert.Equal(new long[] { 11, 7, 5, 3, 2 }, strategy.GetBestSumFound());
+
+ // Selection (17, 10) is actually more expensive: 17 + 10 + 1000 + 1 = 1018.
+ // Whereas (35) costs us 35 + 1 = 36.
+ Assert.Equal(new long[] { 35 }, strategy.GetBestSelectionFound());
}
private List<long> GenerateListOfRandomValues(int count = 1000)
@@ -121,6 +181,8 @@ public class BranchAndBoundTests
values.Add(Random.Next(1000, 99999999));
}
+ values = values.OrderByDescending(x => x).ToList();
+
return values;
}
}

DELETE
WalletWasabi/Blockchain/TransactionBuilding/BnB/BestSumStrategy.cs
-using System.Linq;
-
-namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
-
-/// <summary>
-/// Strategy that stores the best sum of values found along the way and prunes
-/// search space where we would find worse solutions that we already have.
-/// </summary>
-public class BestSumStrategy : ISearchStrategy
-{
- private long _bestTargetSoFar = long.MaxValue;
- private long[]? _bestSolutionSoFar;
-
- public BestSumStrategy(long target)
- {
- Target = target;
- }
-
- /// <inheritdoc/>
- public long Target { get; }
-
- /// <summary>Gives lowest found value selection whose sum is larger than or equal to <see cref="Target"/>.</summary>
- public long[]? GetBestSumFound() => _bestSolutionSoFar?.Where(x => x > 0).ToArray();
-
- /// <inheritdoc/>
- public EvaluationResult Evaluate(long[] solution, int depth, long effValue)
- {
- if (effValue > _bestTargetSoFar)
- {
- // Our solution is already better than what we might get here.
- return EvaluationResult.SkipBranch;
- }
- else if (effValue >= Target)
- {
- if (_bestTargetSoFar > effValue)
- {
- _bestTargetSoFar = effValue;
- _bestSolutionSoFar = solution[0..depth];
- }
-
- if (effValue > Target)
- {
- // Excessive funds, cut the branch!
- return EvaluationResult.SkipBranch;
- }
- else
- {
- // Match found!
- return EvaluationResult.Match;
- }
- }
- else if (depth == solution.Length)
- {
- // Leaf reached, no match
- return EvaluationResult.SkipBranch;
- }
-
- return EvaluationResult.Continue;
- }
-}

ADD
WalletWasabi/Blockchain/TransactionBuilding/BnB/CheapestSelectionStrategy.cs
+using System.Linq;
+
+namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
+
+/// <summary>
+/// Strategy that searches search-space and caches every found selection that minimizes
+/// waste of user's fund by looking for a selection that minimizes inputs' spending costs
+/// and extra cost of paying more than specified target.
+/// </summary>
+public class CheapestSelectionStrategy : ISearchStrategy
+{
+ private long _currentInputCosts = 0;
+ private long _bestTargetSoFar = long.MaxValue;
+ private long[]? _bestSelectionSoFar;
+
+ /// <param name="target">Value in satoshis.</param>
+ /// <param name="inputSpendingCosts">Costs of spending coins in satoshis.</param>
+ public CheapestSelectionStrategy(long target, long[] inputSpendingCosts)
+ {
+ Target = target;
+ InputCosts = inputSpendingCosts;
+ }
+
+ /// <inheritdoc/>
+ public long Target { get; }
+ public long[] InputCosts { get; }
+
+ /// <summary>Gives lowest found value selection whose sum is larger than or equal to <see cref="Target"/>.</summary>
+ public long[]? GetBestSelectionFound() => _bestSelectionSoFar?.Where(x => x > 0).ToArray();
+
+ /// <inheritdoc/>
+ public long UpdateSum(NextAction action, long[] selection, int depth, long oldSum)
+ {
+ if (action == NextAction.IncludeFirstThenOmit || action == NextAction.Include)
+ {
+ _currentInputCosts += InputCosts[depth];
+ return oldSum + selection[depth];
+ }
+
+ _currentInputCosts -= InputCosts[depth];
+ return oldSum - selection[depth];
+ }
+
+ /// <inheritdoc/>
+ public EvaluationResult Evaluate(long[] selection, int depth, long sum)
+ {
+ long totalSum = sum + _currentInputCosts;
+
+ if (totalSum > _bestTargetSoFar)
+ {
+ // Our solution is already better than what we might get here.
+ return EvaluationResult.SkipBranch;
+ }
+ else if (sum >= Target)
+ {
+ if (_bestTargetSoFar > totalSum)
+ {
+ _bestTargetSoFar = totalSum;
+ _bestSelectionSoFar = selection[0..depth];
+ }
+
+ // Even if a match occurred we cannot be sure that there isn't
+ // a better selection thanks to input costs.
+ return EvaluationResult.SkipBranch;
+ }
+ else if (depth == selection.Length)
+ {
+ // Leaf reached, no match
+ return EvaluationResult.SkipBranch;
+ }
+
+ return EvaluationResult.Continue;
+ }
+}

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
@@ -12,7 +12,7 @@ public class BranchAndBound
{
private readonly Random _random = new();
- /// <param name="values">All values must be strictly positive.</param>
+ /// <param name="values">All values must be strictly positive and in descending order.</param>
public BranchAndBound(List<long> values)
{
if (values.Count == 0)
@@ -27,6 +27,11 @@ public class BranchAndBound
Count = values.Count;
SortedValues = values.OrderByDescending(x => x).ToArray();
+
+ if (!values.SequenceEqual(SortedValues))
+ {
+ throw new ArgumentException("Input values must be sorted in descending order.");
+ }
}
/// <remarks>Input values sorted in descending order.</remarks>

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelector.cs
WalletWasabi/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelector.cs
@@ -28,15 +28,18 @@ public static class ChangelessTransactionCoinSelector
// Keys are effective values of smart coins in satoshis.
IOrderedEnumerable<SmartCoin> sortedCoins = availableCoins.OrderByDescending(x => x.EffectiveValue(feeRate).Satoshi);
+ // How much it costs to spend each coin.
+ long[] inputCosts = sortedCoins.Select(x => x.Amount.Satoshi - x.EffectiveValue(feeRate).Satoshi).ToArray();
+
Dictionary<SmartCoin, long> inputs = new(sortedCoins.ToDictionary(x => x, x => x.EffectiveValue(feeRate).Satoshi));
// Pass smart coins' effective values in descending order.
BranchAndBound branchAndBound = new(inputs.Values.ToList());
- BestSumStrategy strategy = new(target);
+ CheapestSelectionStrategy strategy = new(target, inputCosts);
_ = branchAndBound.TryGetMatch(strategy, out List<long>? solution, cancellationToken);
- if (solution is null && strategy.GetBestSumFound() is long[] bestSolution)
+ if (solution is null && strategy.GetBestSelectionFound() is long[] bestSolution)
{
solution = bestSolution.ToList();
}

Refactor and take input costs into account