Add ChangelessTransactionCoinSelector and fix a few bugs.
MODIFY
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
@@ -109,7 +109,7 @@ public class BranchAndBoundTests
Assert.False(wasSuccessful);
Assert.Null(selectedCoins);
- Assert.Equal(new long[] { 11, 7, 5, 3 }, strategy.GetBestSolution());
+ Assert.Equal(new long[] { 11, 7, 5, 3, 2 }, strategy.GetBestSolution());
}
private List<long> GenerateListOfRandomValues(int count = 1000)

ADD
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelectorTests.cs
+using NBitcoin;
+using System.Collections.Generic;
+using System.Linq;
+using WalletWasabi.Blockchain.Analysis.Clustering;
+using WalletWasabi.Blockchain.Keys;
+using WalletWasabi.Blockchain.TransactionBuilding;
+using WalletWasabi.Blockchain.TransactionOutputs;
+using WalletWasabi.Blockchain.Transactions;
+using WalletWasabi.Models;
+using WalletWasabi.Tests.Helpers;
+using Xunit;
+
+namespace WalletWasabi.Tests.UnitTests.Blockchain.TransactionBuilding;
+
+/// <summary>
+/// Tests for <see cref="ChangelessTransactionCoinSelector"/> class.
+/// </summary>
+public class ChangelessTransactionCoinSelectorTests
+{
+ [Fact]
+ public void FindBestSolution()
+ {
+ using Key key = new();
+
+ List<SmartCoin> coins = GenerateDummySmartCoins(key, 6_025, 6_561, 8_192, 13_122, 50_000, 100_000, 196_939, 524_288);
+ long target = 150_000;
+
+ bool found = ChangelessTransactionCoinSelector.TryGetCoins(coins, new FeeRate(satoshiPerByte: 4), target, out List<SmartCoin>? selectedCoins);
+ Assert.True(found);
+
+ long[] solution = selectedCoins!.Select(x => x.Amount.Satoshi).ToArray();
+ Assert.Equal(new long[] { 100_000, 50_000, 6_025 }, solution);
+ Assert.Equal(6025, solution.Sum() - target); // ~4% more for the privacy.
+ }
+
+ private List<SmartCoin> GenerateDummySmartCoins(Key key, params long[] values)
+ {
+ Network network = Network.Main;
+ Transaction tx = Transaction.Create(network);
+ tx.Inputs.Add(TxIn.CreateCoinbase(200));
+
+ foreach (long satoshis in values)
+ {
+ tx.Outputs.Add(Money.Satoshis(satoshis), BitcoinFactory.CreateBitcoinAddress(network, key));
+ }
+
+ SmartTransaction stx = new(tx, Height.Mempool);
+ List<SmartCoin> result = new(capacity: values.Length);
+
+ for (uint i = 0; i < values.Length; i++)
+ {
+ HdPubKey hdPubKey = new(key.PubKey, new KeyPath($"m/84h/0h/0h/1/{i}"), SmartLabel.Empty, KeyState.Clean);
+ result.Add(new SmartCoin(stx, i, hdPubKey));
+ }
+
+ return result;
+ }
+}

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/PruneByBestStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/PruneByBestStrategy.cs
+using System.Linq;
+
namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
/// <summary>
@@ -17,7 +19,7 @@ public class PruneByBestStrategy : ISearchStrategy
/// <inheritdoc/>
public long Target { get; }
- public long[]? GetBestSolution() => _bestSolutionSoFar;
+ public long[]? GetBestSolution() => _bestSolutionSoFar?.Where(x => x > 0).ToArray();
/// <inheritdoc/>
public EvaluationResult Evaluate(long[] solution, int depth, long effValue)
@@ -32,7 +34,7 @@ public class PruneByBestStrategy : ISearchStrategy
if (_bestTargetSoFar > effValue)
{
_bestTargetSoFar = effValue;
- _bestSolutionSoFar = solution[0..depth];
+ _bestSolutionSoFar = solution[0..(depth + 1)];
}
if (effValue > Target)

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
@@ -171,7 +171,7 @@ public class BranchAndBound
return _randomFn() ? NextAction.IncludeFirstThenOmit : NextAction.OmitFirstThenInclude;
}
- private NextAction GetNextStep(NextAction action)
+ private static NextAction GetNextStep(NextAction action)
{
return action switch
{

ADD
WalletWasabi/Blockchain/TransactionBuilding/ChangelessTransactionCoinSelector.cs
+using NBitcoin;
+using System.Collections.Generic;
+using System.Diagnostics.CodeAnalysis;
+using System.Linq;
+using System.Threading;
+using WalletWasabi.Blockchain.TransactionBuilding.BnB;
+using WalletWasabi.Blockchain.TransactionOutputs;
+
+namespace WalletWasabi.Blockchain.TransactionBuilding;
+
+public static class ChangelessTransactionCoinSelector
+{
+ public static bool TryGetCoins(List<SmartCoin> availableCoins, FeeRate feeRate, long target, [NotNullWhen(true)] out List<SmartCoin>? selectedCoins, CancellationToken cancellationToken = default)
+ {
+ selectedCoins = null;
+ // Keys are effective values of smart coins in satoshis.
+ var sortedCoins = availableCoins.OrderByDescending(x => x.EffectiveValue(feeRate).Satoshi);
+
+ Dictionary<SmartCoin, long> inputs = new(sortedCoins.ToDictionary(x => x, x => x.EffectiveValue(feeRate).Satoshi));
+
+ // Pass smart coins' effective values in ascending order.
+ BranchAndBound branchAndBound = new(inputs.Values.ToList());
+ PruneByBestStrategy strategy = new(target);
+
+ _ = branchAndBound.TryGetMatch(strategy, out List<long>? solution, cancellationToken);
+
+ if (solution is null && strategy.GetBestSolution() is long[] bestSolution)
+ {
+ solution = bestSolution.ToList();
+ }
+
+ if (solution is not null)
+ {
+ selectedCoins = new();
+ int i = 0;
+
+ foreach ((SmartCoin smartCoin, long effectiveSatoshis) in inputs)
+ {
+ if (effectiveSatoshis == solution[i])
+ {
+ i++;
+ selectedCoins.Add(smartCoin);
+ if (i == solution.Count)
+ {
+ break;
+ }
+ }
+ }
+
+ return true;
+ }
+
+ return false;
+ }
+}

Add ChangelessTransactionCoinSelector and fix a few bugs.