Add new fast decomposer
MODIFY
WalletWasabi/Extensions/LinqExtensions.cs
WalletWasabi/Extensions/LinqExtensions.cs
@@ -215,4 +215,14 @@ public static class LinqExtensions
public static bool IsSuperSetOf<T>(this IEnumerable<T> me, IEnumerable<T> other) =>
other.All(x => me.Contains(x));
+
+ public static ulong Sum(this IEnumerable<ulong> me)
+ {
+ ulong inputSum = 0;
+ foreach (var item in me)
+ {
+ inputSum += item;
+ }
+ return inputSum;
+ }
}

MODIFY
WalletWasabi/WabiSabi/Client/AmountDecomposer.cs
WalletWasabi/WabiSabi/Client/AmountDecomposer.cs
@@ -154,12 +154,29 @@ public class AmountDecomposer
var histogram = GetDenominationFrequencies(othersInputCoinEffectiveValues.Concat(myInputCoinEffectiveValues));
// Filter out and order denominations those have occurred in the frequency table at least twice.
- var denoms = histogram
+ var preFilteredDenoms = histogram
.Where(x => x.Value > 1)
.OrderByDescending(x => x.Key)
.Select(x => x.Key)
.ToArray();
+ // Filter out denominations very close to each other.
+ // Heavy filtering on the top, little to no filtering on the bottom,
+ // because in smaller denom levels larger users are expected to participate,
+ // but on larger denom levels there's little chance of finding each other.
+ var increment = 0.5 / preFilteredDenoms.Length;
+ List<ulong> denoms = new();
+ var currentLength = preFilteredDenoms.Length;
+ foreach (var denom in preFilteredDenoms)
+ {
+ var filterSeverity = 1 + currentLength * increment;
+ if (!denoms.Any() || denom <= (denoms.Last() / filterSeverity))
+ {
+ denoms.Add(denom);
+ }
+ currentLength--;
+ }
+
var myInputs = myInputCoinEffectiveValues.ToArray();
var myInputSum = myInputs.Sum();
var remaining = myInputSum;
@@ -174,7 +191,7 @@ public class AmountDecomposer
// Create the most naive decomposition for starter.
List<Money> naiveSet = new();
bool end = false;
- foreach (var denomPlusFee in denoms.Where(x => x <= remaining))
+ foreach (var denomPlusFee in preFilteredDenoms.Where(x => x <= remaining))
{
var denomUsage = 0;
while (denomPlusFee <= remaining)
@@ -233,69 +250,23 @@ public class AmountDecomposer
(naiveSet, loss + (ulong)naiveSet.Count * OutputFee)); // The cost is the remaining + output cost.
// Create many decompositions for optimization.
- var before = DateTimeOffset.UtcNow;
- do
- {
- var currSet = new List<Money>();
- remaining = myInputs.Sum();
- remainingVsize = AvailableVsize;
- do
- {
- var denomPlusFees = denoms.Where(x => x <= remaining && x >= (remaining / 3)).ToList();
- if (!denomPlusFees.Any())
- {
- break;
- }
-
- var denomPlusFee = denomPlusFees.RandomElement();
- if (remaining < MinAllowedOutputAmountPlusFee || remainingVsize < 2 * OutputSize)
- {
- break;
- }
-
- if (denomPlusFee <= remaining)
- {
- currSet.Add(denomPlusFee);
- remaining -= denomPlusFee;
- remainingVsize -= OutputSize;
- }
- }
- while (currSet.Count <= naiveSet.Count || currSet.Count <= 3);
-
- // If currSet.Count <= 3 then we still generate sets to add ambiguity.
- if (currSet.Count <= naiveSet.Count || currSet.Count <= 3)
+ Decomposer.StdDenoms = denoms.Where(x => x <= myInputSum).Select(x => (long)x).ToArray();
+ foreach (var (sum, count, decomp) in Decomposer.Decompose((long)myInputSum, (long)Math.Max(loss, 0.5 * (ulong)MinAllowedOutputAmountPlusFee), Math.Min(8, Math.Max(5, naiveSet.Count))))
{
- loss = 0;
- if (remaining >= MinAllowedOutputAmountPlusFee)
- {
- currSet.Add(remaining);
- }
- else
- {
- loss = remaining;
- }
-
- // When not even the minimum denom is reached.
- if (currSet.Count == 0)
- {
- currSet.Add(remaining);
- loss = 0;
- }
+ var currentSet = Decomposer.ToRealValuesArray(
+ decomp,
+ count,
+ Decomposer.StdDenoms).Select(Money.Satoshis).ToList();
hash = new();
- foreach (var item in currSet.OrderBy(x => x))
+ foreach (var item in currentSet.OrderBy(x => x))
{
hash.Add(item);
}
-
- setCandidates.TryAdd(
- hash.ToHashCode(),
- (currSet, loss + (ulong)currSet.Count * OutputFee));
- }
+ setCandidates.TryAdd(hash.ToHashCode(), (currentSet, myInputSum - (ulong)currentSet.Sum() + (ulong)count * OutputFee)); // The cost is the remaining + output cost.
}
- while ((DateTimeOffset.UtcNow - before).TotalMilliseconds <= 500);
- var denomHashSet = denoms.ToHashSet();
+ var denomHashSet = preFilteredDenoms.ToHashSet();
var finalCandidates = setCandidates.Select(x => x.Value).ToList();
finalCandidates.Shuffle();

ADD
WalletWasabi/WabiSabi/Client/Decomposer.cs
+using System.Collections.Generic;
+using System.Linq;
+
+namespace WalletWasabi.WabiSabi.Client;
+
+/// <summary>
+/// https://github.com/lontivero/DecompositionsPlayground/blob/master/Notebook.ipynb
+/// </summary>
+public static class Decomposer
+{
+ public static long[] StdDenoms;
+
+ public static IEnumerable<(long Sum, int Count, ulong Decomposition)> Decompose(long target, long tolerance, int maxCount)
+ {
+ if (maxCount is <= 1 or > 8)
+ {
+ throw new ArgumentOutOfRangeException(nameof(maxCount), "The maximum decomposition lenght cannot be greater than 8 or smaller than 1.");
+ }
+ if (target <= 0)
+ {
+ throw new ArgumentException("Only possitive numbers can be decomposed.", nameof(target));
+ }
+
+ var denoms = StdDenoms.SkipWhile(x => x > target).ToArray();
+
+ if (denoms.Length > 255)
+ {
+ throw new ArgumentException("Too many denominations. Maximum number is 256.", nameof(target));
+ }
+ return denoms.SelectMany(_ => InternalCombinations(target, tolerance: tolerance, maxCount, denoms)).Take(10_000).ToList();
+ }
+
+ private static IEnumerable<(long Sum, int Count, ulong Decomposition)> InternalCombinations(long target, long tolerance, int maxLength, long[] denoms)
+ {
+ IEnumerable<(long Sum, int Count, ulong Decomposition)> Combinations(
+ int currentDenominationIdx,
+ ulong accumulator,
+ long sum,
+ int k)
+ {
+ accumulator = (accumulator << 8) | ((ulong)currentDenominationIdx & 0xff);
+ var currentDenomination = denoms[currentDenominationIdx];
+ sum += currentDenomination;
+ var remaining = target - sum;
+ if (k == 0 || remaining < tolerance)
+ {
+ return new[] { (sum, maxLength - k, accumulator) };
+ }
+
+ currentDenominationIdx = Search(remaining, denoms, currentDenominationIdx);
+
+ return Enumerable.Range(0, denoms.Length - currentDenominationIdx)
+ .TakeWhile(i => k * denoms[currentDenominationIdx + i] >= remaining - tolerance)
+ .SelectMany((_, i) =>
+ Combinations(currentDenominationIdx + i, accumulator, sum, k - 1)
+ .TakeUntil(x => x.Sum == target));
+ }
+
+ return denoms.SelectMany((_, i) => Combinations(i, 0ul, 0, maxLength - 1)).Take(5_000).ToList();
+ }
+
+ private static int Search(long value, long[] denoms, int offset)
+ {
+ var startingIndex = Array.BinarySearch(denoms, offset, denoms.Length - offset, value, ReverseComparer.Default);
+ return startingIndex < 0 ? ~startingIndex : startingIndex;
+ }
+
+ public static IEnumerable<long> ToRealValuesArray(ulong decomposition, int count, long[] denoms)
+ {
+ var list = new long[count];
+ for (var i = 0; i < count; i++)
+ {
+ var index = (decomposition >> (i * 8)) & 0xff;
+ list[count - i - 1] = denoms[index];
+ }
+ return list;
+ }
+}
+
+public static class LinqEx
+{
+ public static IEnumerable<T> TakeUntil<T>(this IEnumerable<T> list, Func<T, bool> predicate)
+ {
+ foreach (T el in list)
+ {
+ yield return el;
+ if (predicate(el))
+ {
+ yield break;
+ }
+ }
+ }
+}
+
+public class ReverseComparer : IComparer<long>
+{
+ public static readonly ReverseComparer Default = new();
+ public int Compare(long x, long y)
+ {
+ // Compare y and x in reverse order.
+ return y.CompareTo(x);
+ }
+}
\ No newline at end of file

Add new fast decomposer