Synchronize with Sake
MODIFY
WalletWasabi/WabiSabi/Client/AmountDecomposer.cs
WalletWasabi/WabiSabi/Client/AmountDecomposer.cs
@@ -2,33 +2,153 @@ using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using NBitcoin;
-using WalletWasabi.WabiSabi.Models.Decomposition;
+namespace WalletWasabi.WabiSabi.Client
+{
/// <summary>
/// Pull requests to this file must be up to date with this simulation to ensure correctness: https://github.com/nopara73/Sake
/// </summary>
-namespace WalletWasabi.WabiSabi.Client
-{
public class AmountDecomposer
{
+ /// <param name="feeRate">Bitcoin network fee rate the coinjoin is targeting.</param>
+ /// <param name="minAllowedOutputAmount"></param>
+ /// <param name="outputSize">Size of an output.</param>
+ /// <param name="availableVsize">Available virtual size for outputs.</param>
public AmountDecomposer(FeeRate feeRate, Money minAllowedOutputAmount, int outputSize, int availableVsize)
{
- OutputSize = outputSize;
FeeRate = feeRate;
+ OutputSize = outputSize;
AvailableVsize = availableVsize;
- MinimumAmountPlusFee = minAllowedOutputAmount + OutputFee;
- StandardDenominationsPlusFee = StandardDenomination.Values
- .Select(x => x + OutputFee)
- .OrderByDescending(x => x)
- .ToImmutableArray();
+
+ MinAllowedOutputAmountPlusFee = minAllowedOutputAmount + OutputFee;
+
+ // Create many standard denominations.
+ DenominationsPlusFees = CreateDenominationsPlusFees();
}
public FeeRate FeeRate { get; }
public int AvailableVsize { get; }
- public Money MinimumAmountPlusFee { get; }
+ public Money MinAllowedOutputAmountPlusFee { get; }
public Money OutputFee => FeeRate.GetFee(OutputSize);
public int OutputSize { get; }
- private ImmutableArray<Money> StandardDenominationsPlusFee { get; }
+ public IOrderedEnumerable<ulong> DenominationsPlusFees { get; }
+
+ private IOrderedEnumerable<ulong> CreateDenominationsPlusFees()
+ {
+ ulong maxSatoshis = ProtocolConstants.MaxAmountPerAlice;
+ ulong minSatoshis = MinAllowedOutputAmountPlusFee;
+ var denominations = new HashSet<ulong>();
+
+ // Powers of 2
+ for (int i = 0; i < int.MaxValue; i++)
+ {
+ var denom = (ulong)Math.Pow(2, i) + OutputFee;
+
+ if (denom < minSatoshis)
+ {
+ continue;
+ }
+
+ if (denom > maxSatoshis)
+ {
+ break;
+ }
+
+ denominations.Add(denom);
+ }
+
+ // Powers of 3
+ for (int i = 0; i < int.MaxValue; i++)
+ {
+ var denom = (ulong)Math.Pow(3, i) + OutputFee;
+
+ if (denom < minSatoshis)
+ {
+ continue;
+ }
+
+ if (denom > maxSatoshis)
+ {
+ break;
+ }
+
+ denominations.Add(denom);
+ }
+
+ // Powers of 3 * 2
+ for (int i = 0; i < int.MaxValue; i++)
+ {
+ var denom = (ulong)Math.Pow(3, i) * 2 + OutputFee;
+
+ if (denom < minSatoshis)
+ {
+ continue;
+ }
+
+ if (denom > maxSatoshis)
+ {
+ break;
+ }
+
+ denominations.Add(denom);
+ }
+
+ // Powers of 10 (1-2-5 series)
+ for (int i = 0; i < int.MaxValue; i++)
+ {
+ var denom = (ulong)Math.Pow(10, i) + OutputFee;
+
+ if (denom < minSatoshis)
+ {
+ continue;
+ }
+
+ if (denom > maxSatoshis)
+ {
+ break;
+ }
+
+ denominations.Add(denom);
+ }
+
+ // Powers of 10 * 2 (1-2-5 series)
+ for (int i = 0; i < int.MaxValue; i++)
+ {
+ var denom = (ulong)Math.Pow(10, i) * 2 + OutputFee;
+
+ if (denom < minSatoshis)
+ {
+ continue;
+ }
+
+ if (denom > maxSatoshis)
+ {
+ break;
+ }
+
+ denominations.Add(denom);
+ }
+
+ // Powers of 10 * 5 (1-2-5 series)
+ for (int i = 0; i < int.MaxValue; i++)
+ {
+ var denom = (ulong)Math.Pow(10, i) * 5 + OutputFee;
+
+ if (denom < minSatoshis)
+ {
+ continue;
+ }
+
+ if (denom > maxSatoshis)
+ {
+ break;
+ }
+
+ denominations.Add(denom);
+ }
+
+ return denominations.OrderByDescending(x => x);
+ }
public IEnumerable<Money> Decompose(IEnumerable<Coin> myInputCoins, IEnumerable<Coin> allInputCoins)
{
@@ -51,7 +171,7 @@ namespace WalletWasabi.WabiSabi.Client
{
while (denom <= remaining)
{
- if (remaining < MinimumAmountPlusFee || remainingVsize < 2 * OutputSize)
+ if (remaining < MinAllowedOutputAmountPlusFee || remainingVsize < 2 * OutputSize)
{
end = true;
break;
@@ -68,7 +188,7 @@ namespace WalletWasabi.WabiSabi.Client
}
}
- if (remaining >= MinimumAmountPlusFee)
+ if (remaining >= MinAllowedOutputAmountPlusFee)
{
naiveSet.Add(remaining - OutputFee);
}
@@ -86,8 +206,13 @@ namespace WalletWasabi.WabiSabi.Client
do
{
var denomPlusFees = denoms.Where(x => x <= remaining && x >= (remaining / 3)).ToList();
+ if (denomPlusFees.Any())
+ {
+ break;
+ }
+
var denomPlusFee = denomPlusFees.RandomElement();
- if (denomPlusFee is null || remaining < MinimumAmountPlusFee || remainingVsize < 2 * OutputSize)
+ if (remaining < MinAllowedOutputAmountPlusFee || remainingVsize < 2 * OutputSize)
{
break;
}
@@ -103,7 +228,7 @@ namespace WalletWasabi.WabiSabi.Client
if (currSet.Count <= naiveSet.Count || currSet.Count <= 3)
{
- if (remaining >= MinimumAmountPlusFee)
+ if (remaining >= MinAllowedOutputAmountPlusFee)
{
currSet.Add(remaining - OutputFee);
}
@@ -132,7 +257,7 @@ namespace WalletWasabi.WabiSabi.Client
{
throw new InvalidOperationException("The decomposer is creating money. Aborting.");
}
- if (totalOutputAmount + MinimumAmountPlusFee < totalInput)
+ if (totalOutputAmount + MinAllowedOutputAmountPlusFee < totalInput)
{
throw new InvalidOperationException("The decomposer is losing money. Aborting.");
}
@@ -145,12 +270,12 @@ namespace WalletWasabi.WabiSabi.Client
return finalCandidate;
}
- private Dictionary<Money, long> GetDenominationFrequency(IEnumerable<Coin> allInputCoins)
+ private Dictionary<ulong, long> GetDenominationFrequency(IEnumerable<Coin> allInputCoins)
{
var secondLargestInput = allInputCoins.OrderByDescending(x => x.Amount).Skip(1).FirstOrDefault();
- IEnumerable<Money> demonsForBreakDown = StandardDenominationsPlusFee.Where(x => secondLargestInput is null || x <= secondLargestInput.EffectiveValue(FeeRate));
+ IEnumerable<ulong> demonsForBreakDown = DenominationsPlusFees.Where(x => secondLargestInput is null || x <= (ulong)secondLargestInput.EffectiveValue(FeeRate).Satoshi);
- Dictionary<Money, long> denomProbabilities = new();
+ Dictionary<ulong, long> denomProbabilities = new();
foreach (var input in allInputCoins)
{
@@ -166,13 +291,13 @@ namespace WalletWasabi.WabiSabi.Client
return denomProbabilities;
}
- private IEnumerable<Money> BreakDown(Coin coin, IEnumerable<Money> denominations)
+ private IEnumerable<ulong> BreakDown(Coin coin, IEnumerable<ulong> denominations)
{
var remaining = coin.EffectiveValue(FeeRate);
foreach (var denomPlusFee in denominations)
{
- if (denomPlusFee < MinimumAmountPlusFee || remaining < MinimumAmountPlusFee)
+ if (denomPlusFee < MinAllowedOutputAmountPlusFee || remaining < MinAllowedOutputAmountPlusFee)
{
break;
}
@@ -184,7 +309,7 @@ namespace WalletWasabi.WabiSabi.Client
}
}
- if (remaining >= MinimumAmountPlusFee)
+ if (remaining >= MinAllowedOutputAmountPlusFee)
{
yield return remaining;
}

DELETE
WalletWasabi/WabiSabi/Models/Decomposition/StandardDenomination.cs
-using NBitcoin;
-using System.Collections.Generic;
-using System.Collections.Immutable;
-using System.Linq;
-
-namespace WalletWasabi.WabiSabi.Models.Decomposition
-{
- public static class StandardDenomination
- {
- public static readonly ImmutableArray<Money> Values = Generate().ToImmutableArray();
-
- private static IEnumerable<long> Multiple(IEnumerable<long> coefficients, IEnumerable<long> values) =>
- values
- .SelectMany(c => coefficients, (v, c) => c * v)
- .TakeWhile(x => x <= ProtocolConstants.MaxAmountPerAlice);
-
- private static IEnumerable<long> PowersOf(int b) =>
- Enumerable
- .Range(0, int.MaxValue)
- .Select(x => (long)Math.Pow(b, x))
- .TakeWhile(x => x <= ProtocolConstants.MaxAmountPerAlice);
-
- private static IEnumerable<Money> Generate()
- {
- var ternary = Multiple(new long[] { 1, 2 }, PowersOf(3));
- var preferredValueSeries = Multiple(new long[] { 1, 2, 5 }, PowersOf(10));
-
- return PowersOf(2)
- .Union(ternary)
- .Union(preferredValueSeries)
- .OrderBy(v => v)
- .Select(Money.Satoshis);
- }
- }
-}

Synchronize with Sake