optimize selection
MODIFY
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelectorTests.cs
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelectorTests.cs
@@ -50,7 +50,7 @@ public class ChangelessTransactionCoinSelectorTests
var txOut = new TxOut(target, BitcoinFactory.CreateBitcoinAddress(Network.TestNet, key));
bool found = ChangelessTransactionCoinSelector.TryGetCoins(SuggestionType.Less, coins, new FeeRate(satoshiPerByte: 4), txOut, out IEnumerable<SmartCoin>? selectedCoins);
- //Assert.True(found);
+ Assert.True(found);
long[] solution = selectedCoins!.Select(x => x.Amount.Satoshi).ToArray();
Assert.Equal(new long[] { 50_000, 8_192, 6_561 }, solution);

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/CheapestSelectionStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/CheapestSelectionStrategy.cs
@@ -12,6 +12,7 @@ public class CheapestSelectionStrategy
private long _currentInputCosts = 0;
private long _bestTargetSoFar;
private long[]? _bestSelectionSoFar;
+ private long _remainingAmount;
/// <param name="target">Value in satoshis.</param>
/// <param name="inputCosts">Costs of spending coins in satoshis.</param>
@@ -22,6 +23,7 @@ public class CheapestSelectionStrategy
Target = target;
SuggestionType = suggestionType;
_bestTargetSoFar = suggestionType == SuggestionType.More ? long.MaxValue : long.MinValue;
+ _remainingAmount = InputValues.Sum();
}
/// <summary>Costs corresponding to <see cref="InputValues"/> values.</summary>
@@ -56,6 +58,7 @@ public class CheapestSelectionStrategy
if (selection[depth] == 0)
{
_currentInputCosts += InputCosts[depth];
+ _remainingAmount -= InputValues[depth];
}
selection[depth] = InputValues[depth];
@@ -66,6 +69,7 @@ public class CheapestSelectionStrategy
if (selection[depth] > 0)
{
_currentInputCosts -= InputCosts[depth];
+ _remainingAmount += InputValues[depth];
}
newSum = oldSum - selection[depth];
@@ -93,6 +97,11 @@ public class CheapestSelectionStrategy
// Our solution is already better than what we might get here.
return EvaluationResult.SkipBranch;
}
+ else if (sum + _remainingAmount < Target)
+ {
+ // The remaining coins cannot sum up to required target, cut the branch.
+ return EvaluationResult.SkipBranch;
+ }
else if (sum >= Target)
{
if (_bestTargetSoFar > totalCost)
@@ -127,6 +136,12 @@ public class CheapestSelectionStrategy
return EvaluationResult.SkipBranch;
}
+ if (sum + _remainingAmount < _bestTargetSoFar)
+ {
+ // The remaining coins cannot sum up to our solution, so cut the branch.
+ return EvaluationResult.SkipBranch;
+ }
+
if (_bestTargetSoFar < totalCost)
{
_bestSelectionSoFar = selection[0..depth];

optimize selection