BnB: Track included coins number
MODIFY
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
@@ -71,7 +71,7 @@ public class BranchAndBoundTests
// Selection (35) costs us 35 + 1 = 36.
// Selection (17, 10) is actually more expensive: (17 + 10) + (10 + 1) = 38, but
- // we use that selection sa 27 is exactly the amount a payee expects.
+ // we use that selection as 27 is exactly the amount a payee expects.
long[] actualSelection = strategy.GetBestSelectionFound()!;
Assert.NotNull(actualSelection);
@@ -91,8 +91,7 @@ public class BranchAndBoundTests
{
using CancellationTokenSource cts = new(TimeSpan.FromSeconds(30));
- List<long> inputValues = new();
- inputValues.Add(1_000_000);
+ List<long> inputValues = new() { 1_000_000 };
for (int i = 0; i < 1000; i++)
{
@@ -120,8 +119,7 @@ public class BranchAndBoundTests
{
using CancellationTokenSource cts = new(TimeSpan.FromSeconds(30));
- List<long> inputValues = new();
- inputValues.Add(999_999);
+ List<long> inputValues = new() { 999_999 };
for (int i = 0; i < 1000; i++)
{

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/CoinSelection.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/CoinSelection.cs
@@ -12,6 +12,7 @@ public class CoinSelection
{
PaymentAmount = sum;
TotalCosts = sumWithCosts;
+ IncludedCoinsCount = 0;
}
/// <summary>Value in satoshi that the receiver will receive.</summary>
@@ -21,16 +22,24 @@ public class CoinSelection
/// <remarks><see cref="TotalCosts"/> is always greater than <see cref="PaymentAmount"/>.</remarks>
public long TotalCosts { get; private set; }
+ /// <summary>Number of non-zero values in <see cref="Selection"/>.</summary>
+ /// <remarks>This is an optimization to avoid computing this value again and again.</remarks>
+ public int IncludedCoinsCount { get; private set; }
+
/// <remarks>Array items containing zeros mean that the coin is not part of the coin selection.</remarks>
public long[]? Selection { get; private set; }
- public void Update(long paymentAmount, long totalCosts, long[] selection)
+ /// <summary>Sets a new coin selection with its properties.</summary>
+ /// <remarks>Old selection is forgotten.</remarks>
+ public void Update(long paymentAmount, long totalCosts, int includedCoinsCount, long[] selection)
{
PaymentAmount = paymentAmount;
TotalCosts = totalCosts;
+ IncludedCoinsCount = includedCoinsCount;
Selection = selection;
}
+ /// <summary>Gets an array with non-zero values in satoshis.</summary>
public long[]? GetSolutionArray()
{
return Selection?.Where(x => x > 0).ToArray();

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/LessSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/LessSelectionStrategy.cs
@@ -41,7 +41,7 @@ public class LessSelectionStrategy : SelectionStrategy
if (sum > BestSelection.PaymentAmount || (sum == BestSelection.PaymentAmount && totalCost < BestSelection.TotalCosts))
{
- BestSelection.Update(sum, totalCost, selection[0..depth]);
+ BestSelection.Update(sum, totalCost, IncludedCoinsCount, selection[0..depth]);
}
if (depth == selection.Length)

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/MoreSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/MoreSelectionStrategy.cs
@@ -35,7 +35,7 @@ public class MoreSelectionStrategy : SelectionStrategy
{
if (sum < BestSelection.PaymentAmount || (sum == BestSelection.PaymentAmount && totalCost < BestSelection.TotalCosts))
{
- BestSelection.Update(sum, totalCost, selection[0..depth]);
+ BestSelection.Update(sum, totalCost, IncludedCoinsCount, selection[0..depth]);
}
// Even if a match occurred we cannot be sure that there isn't

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/SelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/SelectionStrategy.cs
@@ -8,6 +8,7 @@ public abstract class SelectionStrategy
/// <param name="target">Value in satoshis.</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>
+ /// <param name="bestSelection">Best selection so far.</param>
public SelectionStrategy(long target, long[] inputValues, long[] inputCosts, CoinSelection bestSelection)
{
InputCosts = inputCosts;
@@ -34,6 +35,10 @@ public abstract class SelectionStrategy
/// <summary>Input values sorted in descending orders.</summary>
public long[] InputValues { get; }
+ /// <summary>Number of coins included in current selection.</summary>
+ /// <remarks>Range of values is <c>0</c> to <see cref="InputValues"/> size.</remarks>
+ protected int IncludedCoinsCount { get; set; } = 0;
+
/// <summary>Holds best coin selection found so far with some metadata to improve performance.</summary>
protected CoinSelection BestSelection { get; }
@@ -66,6 +71,7 @@ public abstract class SelectionStrategy
CurrentInputCosts += InputCosts[depth];
}
+ IncludedCoinsCount++;
selection[depth] = InputValues[depth];
newSum = oldSum + selection[depth];
}
@@ -73,6 +79,7 @@ public abstract class SelectionStrategy
{
if (selection[depth] > 0)
{
+ IncludedCoinsCount--;
CurrentInputCosts -= InputCosts[depth];
}

BnB: Track included coins number