Add alternative decompositions
ADD
WalletWasabi.Tests/UnitTests/WabiSabi/Client/AmountDecomposerTests.cs
+using System.Collections.Generic;
+using System.Linq;
+using NBitcoin;
+using WalletWasabi.Helpers;
+using WalletWasabi.Tests.Helpers;
+using WalletWasabi.WabiSabi;
+using WalletWasabi.WabiSabi.Client;
+using Xunit;
+
+namespace WalletWasabi.Tests.UnitTests.WabiSabi.Client
+{
+ public class AmountDecomposerTests
+ {
+ private static readonly Random Random = new (1234567);
+
+ [Theory]
+ [InlineData(0, 0, 8)]
+ [InlineData(0, 0, 1)]
+ [InlineData(0, 0, 2)]
+ [InlineData(0, 0, 3)]
+ [InlineData(0, 1_000, 1)]
+ [InlineData(0, 100_000, 2)]
+ [InlineData(0, 1_000_000, 3)]
+ [InlineData(0, 10_000_000, 8)]
+ [InlineData(20, 0, 1)]
+ [InlineData(100, 0, 2)]
+ [InlineData(500, 0, 3)]
+ [InlineData(5000, 0, 8)]
+ public void DecompositionsTest(decimal feeRateDecimal, long minOutputAmout, int maxAvailableOutputs)
+ {
+ var availableVsize = maxAvailableOutputs * Constants.P2WPKHOutputSizeInBytes;
+ var feeRate = new FeeRate(feeRateDecimal);
+ var feePerOutput = feeRate.GetFee(Constants.P2WPKHOutputSizeInBytes);
+ var registeredCoins = GenerateRandomCoins().Take(3).ToList();
+ var theirCoins = GenerateRandomCoins().Take(30).ToList();
+ var totalEffectiveValue = registeredCoins.Sum(x => x.EffectiveValue(feeRate));
+
+ var amountDecomposer = new AmountDecomposer(feeRate, minOutputAmout, Constants.P2WPKHOutputSizeInBytes, availableVsize);
+ var outputValues = amountDecomposer.Decompose(registeredCoins, theirCoins);
+
+ var totalEffectiveCost = outputValues.Count() * feePerOutput;
+ Assert.InRange(outputValues.Count(), 1, maxAvailableOutputs);
+ Assert.Equal(totalEffectiveValue - totalEffectiveCost, outputValues.Sum());
+ Assert.All(outputValues, v => Assert.InRange(v.Satoshi, minOutputAmout, totalEffectiveValue));
+ }
+
+ [Fact]
+ public void MinimumPrivacyTest()
+ {
+ var feeRate = new FeeRate(25.0m);
+ var feePerOutput = feeRate.GetFee(Constants.P2WPKHOutputSizeInBytes);
+ var amountDecomposer = new AmountDecomposer(feeRate, 0L, Constants.P2WPKHOutputSizeInBytes, 255);
+
+ var numberOfInputsPerUser = new[]{ 1, 2, 3, 7 };
+ var usersCoins = numberOfInputsPerUser.Select(n => GenerateRandomCoins().Take(n).ToArray()).ToArray();
+ var theirCoins = usersCoins.SelectMany(x => x);
+ var usersDecompositions = usersCoins.Select(coins => amountDecomposer.Decompose(coins, theirCoins)).ToArray();
+
+ Assert.All(usersDecompositions, d => Assert.Equal(8, d.Count()));
+ }
+
+ private static IEnumerable<Coin> GenerateRandomCoins()
+ {
+ using var key = new Key();
+ var script = key.GetScriptPubKey(ScriptPubKeyType.Segwit);
+ while (true)
+ {
+ var amount = Random.NextInt64(100_000, ProtocolConstants.MaxAmountPerAlice);
+ yield return CreateCoin(script, amount);
+ }
+ }
+
+ private static Coin CreateCoin(Script scriptPubKey, long amount)
+ {
+ var prevOut = BitcoinFactory.CreateOutPoint();
+ var txOut = new TxOut(Money.Satoshis(amount), scriptPubKey);
+ return new Coin(prevOut, txOut);
+ }
+ }
+}

MODIFY
WalletWasabi/WabiSabi/Client/AmountDecomposer.cs
WalletWasabi/WabiSabi/Client/AmountDecomposer.cs
@@ -31,18 +31,17 @@ namespace WalletWasabi.WabiSabi.Client
{
var histogram = GetDenominationFrequency(allInputCoins);
- var inputs = myInputCoins.Select(x => x.EffectiveValue(FeeRate));
- var remaining = inputs.Sum();
-
var denoms = histogram
.Where(x => x.Value > 1)
.OrderByDescending(x => x.Key)
.Select(x => x.Key)
.ToArray();
- List<Money> outputAmounts = new();
+ var inputs = myInputCoins.Select(x => x.EffectiveValue(FeeRate));
+ var remaining = inputs.Sum();
var remainingVsize = AvailableVsize;
+ List<Money> outputAmounts = new();
bool end = false;
foreach (var denom in denoms.Where(x => x <= remaining))
{
@@ -70,7 +69,46 @@ namespace WalletWasabi.WabiSabi.Client
outputAmounts.Add(remaining - OutputFee);
}
- return outputAmounts;
+ var bestSet = outputAmounts;
+ for (int i = 0; i < 10_000; i++)
+ {
+ remaining = inputs.Sum();
+ var currSet = new List<Money>();
+ do
+ {
+ var selectableDenomPlusFees = denoms.Where(x => x <= remaining).ToList();
+ var denomPlusFees = selectableDenomPlusFees.Skip(selectableDenomPlusFees.Count / 3).ToList();
+ var denom = denomPlusFees.RandomElement();
+ if (denom is null || remaining < MinimumAmountPlusFee )
+ {
+ break;
+ }
+
+ if (denom <= remaining)
+ {
+ currSet.Add(denom - OutputFee);
+ remaining -= denom;
+ }
+ }
+ while (currSet.Count < bestSet.Count);
+
+ if (currSet.Count >= bestSet.Count)
+ {
+ continue;
+ }
+
+ if (remaining >= MinimumAmountPlusFee)
+ {
+ currSet.Add(remaining - OutputFee);
+ }
+
+ if (currSet.Count < bestSet.Count)
+ {
+ bestSet = currSet;
+ }
+ }
+
+ return bestSet;
}
private Dictionary<Money, long> GetDenominationFrequency(IEnumerable<Coin> allInputCoins)
@@ -82,11 +120,11 @@ namespace WalletWasabi.WabiSabi.Client
foreach (var input in allInputCoins)
{
- foreach (var denom in BreakDown(input, demonsForBreakDown))
+ foreach (var denom in BreakDown(input.Amount, demonsForBreakDown))
{
if (!denomProbabilities.TryAdd(denom, 1))
{
- denomProbabilities[denom] += 1;
+ denomProbabilities[denom]++;
}
}
}
@@ -94,9 +132,9 @@ namespace WalletWasabi.WabiSabi.Client
return denomProbabilities;
}
- private IEnumerable<Money> BreakDown(Coin coin, IEnumerable<Money> denominations)
+ private IEnumerable<Money> BreakDown(long amount, IEnumerable<Money> denominations)
{
- var remaining = coin.EffectiveValue(FeeRate);
+ var remaining = amount;
foreach (var denomPlusFee in denominations)
{

Add alternative decompositions