Improve transaction privacy (use cluster info)
MODIFY
WalletWasabi.Tests/UnitTests/Transactions/TransactionFactoryTests.cs
WalletWasabi.Tests/UnitTests/Transactions/TransactionFactoryTests.cs
@@ -130,11 +130,11 @@ namespace WalletWasabi.Tests.UnitTests.Transactions
Assert.True(result.Signed);
Assert.True(result.SpendsUnconfirmed);
- Assert.Equal(4, result.SpentCoins.Count());
- Assert.Equal(Money.Coins(0.15m), result.SpentCoins.Select(x => x.Amount).Sum());
+ Assert.Equal(3, result.SpentCoins.Count());
+ Assert.Equal(Money.Coins(0.14m), result.SpentCoins.Select(x => x.Amount).Sum());
var changeCoin = Assert.Single(result.InnerWalletOutputs);
- Assert.Equal("Daniel, Maria, Pablo, Sophie", changeCoin.Label.ToString());
+ Assert.Equal("Daniel, Maria, Sophie", changeCoin.Label.ToString());
var tx = result.Transaction.Transaction;
// it must select the unconfirm coin even when the anonymity set is lower
@@ -142,6 +142,90 @@ namespace WalletWasabi.Tests.UnitTests.Transactions
Assert.Equal(2, tx.Outputs.Count());
}
+ [Fact]
+ public void SelectSameClusterCoins()
+ {
+ var (password, keyManager) = DefaultKeyManager();
+
+ keyManager.AssertCleanKeysIndexed();
+
+ Func<HdPubKey> newKey = ()=> keyManager.GenerateNewKey(new SmartLabel(""), KeyState.Used, true, false);
+ var scoins = new[] {
+ Coin("Pablo", newKey(), 0.9m),
+ Coin("Daniel", newKey(), 0.9m),
+ Coin("Adolf", newKey(), 0.9m),
+ Coin("Maria", newKey(), 0.9m),
+ Coin("Ding", newKey(), 0.9m),
+ Coin("Joseph", newKey(), 0.9m),
+ Coin("Eve", newKey(), 0.9m),
+ Coin("Julio", newKey(), 0.9m),
+ Coin("Donald, Jean, Lee, Onur", newKey(), 0.9m),
+ Coin("Satoshi",newKey(), 0.9m)
+ };
+ var coinsByLabel = scoins.ToDictionary(x=>x.Label.ToString());
+
+ // cluster 1 is known by 7 people: Pablo, Daniel, Adolf, Maria, Ding, Joseph and Eve
+ var coinsCluster1 = new[]{scoins[0], scoins[1], scoins[2], scoins[3], scoins[4], scoins[5], scoins[6]};
+ var cluster1 = new Cluster(coinsCluster1);
+ foreach(var coin in coinsCluster1)
+ {
+ coin.Clusters = cluster1;
+ }
+
+ // cluster 2 is known by 6 people: Julio, Lee, Jean, Donald, Onur and Satoshi
+ var coinsCluster2 = new[]{scoins[7], scoins[8], scoins[9]};
+ var cluster2 = new Cluster(coinsCluster2);
+ foreach(var coin in coinsCluster2)
+ {
+ coin.Clusters = cluster2;
+ }
+
+ var coinsView = new CoinsView(scoins.ToArray());
+ var transactionFactory = new TransactionFactory(Network.Main, keyManager, coinsView, password);
+
+ // Two 0.9btc coins are enough
+ var payment = new PaymentIntent(new Key().ScriptPubKey, Money.Coins(1.75m), label: new SmartLabel("Sophie"));
+ var feeRate = new FeeRate(2m);
+ var result = transactionFactory.BuildTransaction(payment, feeRate);
+
+ Assert.Equal(2, result.SpentCoins.Count());
+ Assert.All(result.SpentCoins, c=> Assert.Equal(c.Clusters, cluster2));
+ Assert.Contains(coinsByLabel["Julio"], result.SpentCoins);
+ Assert.Contains(coinsByLabel["Donald, Jean, Lee, Onur"], result.SpentCoins);
+
+ // Three 0.9btc coins are enough
+ payment = new PaymentIntent(new Key().ScriptPubKey, Money.Coins(1.85m), label: new SmartLabel("Sophie"));
+ feeRate = new FeeRate(2m);
+ result = transactionFactory.BuildTransaction(payment, feeRate);
+
+ Assert.Equal(3, result.SpentCoins.Count());
+ Assert.All(result.SpentCoins, c=> Assert.Equal(c.Clusters, cluster2));
+ Assert.Contains(coinsByLabel["Julio"], result.SpentCoins);
+ Assert.Contains(coinsByLabel["Donald, Jean, Lee, Onur"], result.SpentCoins);
+ Assert.Contains(coinsByLabel["Satoshi"], result.SpentCoins);
+
+ // Four 0.9btc coins are enough but this time the more private cluster is NOT enough
+ // That's why it has to use the coins in the cluster number 1
+ payment = new PaymentIntent(new Key().ScriptPubKey, Money.Coins(3.5m), label: new SmartLabel("Sophie"));
+ feeRate = new FeeRate(2m);
+ result = transactionFactory.BuildTransaction(payment, feeRate);
+
+ Assert.Equal(4, result.SpentCoins.Count());
+ Assert.All(result.SpentCoins, c=> Assert.Equal(c.Clusters, cluster1));
+ Assert.Contains(coinsByLabel["Pablo"], result.SpentCoins);
+ Assert.Contains(coinsByLabel["Daniel"], result.SpentCoins);
+ Assert.Contains(coinsByLabel["Adolf"], result.SpentCoins);
+ Assert.Contains(coinsByLabel["Maria"], result.SpentCoins);
+
+ // Nine 0.9btc coins are enough but there is no cluster big enough
+ // That's why it has to use the coins from both the clusters
+ payment = new PaymentIntent(new Key().ScriptPubKey, Money.Coins(7.4m), label: new SmartLabel("Sophie"));
+ feeRate = new FeeRate(2m);
+ result = transactionFactory.BuildTransaction(payment, feeRate);
+
+ Assert.Equal(9, result.SpentCoins.Count());
+ }
+
[Fact]
public void CustomChangeScript()
{
@@ -435,8 +519,15 @@ namespace WalletWasabi.Tests.UnitTests.Transactions
keyManager.AssertCleanKeysIndexed();
var keys = keyManager.GetKeys().Take(10).ToArray();
- var scoins = coins.Select(x => Coin(x.Label, keys[x.KeyIndex], x.Amount, x.Confirmed, x.AnonymitySet));
- var coinsView = new CoinsView(scoins.ToArray());
+ var scoins = coins.Select(x => Coin(x.Label, keys[x.KeyIndex], x.Amount, x.Confirmed, x.AnonymitySet)).ToArray();
+ foreach(var coin in scoins)
+ {
+ foreach(var sameLabelCoin in scoins.Where(c=>c.Label == coin.Label))
+ {
+ sameLabelCoin.Clusters = coin.Clusters;
+ }
+ }
+ var coinsView = new CoinsView(scoins);
return new TransactionFactory(Network.Main, keyManager, coinsView, password, allowUnconfirmed);
}

MODIFY
WalletWasabi/BlockchainAnalysis/Cluster.cs
WalletWasabi/BlockchainAnalysis/Cluster.cs
@@ -13,10 +13,14 @@ namespace WalletWasabi.BlockchainAnalysis
private string _labels;
public Cluster(SmartCoin coin)
+ : this( new[] { coin })
{
- Labels = "";
- Coins = new List<SmartCoin>() { coin };
- Labels = string.Join(", ", coin.Label.Labels);
+ }
+
+ public Cluster(IEnumerable<SmartCoin> coins)
+ {
+ Coins = coins.ToList();
+ Labels = string.Join(", ", KnownBy);
}
public string Labels
@@ -25,6 +29,10 @@ namespace WalletWasabi.BlockchainAnalysis
private set => RaiseAndSetIfChanged(ref _labels, value);
}
+ public int Size => Coins.Count();
+
+ public IEnumerable<string> KnownBy => Coins.SelectMany(x => x.Label.Labels).Distinct(StringComparer.OrdinalIgnoreCase);
+
public void Merge(Cluster clusters) => Merge(clusters.Coins);
public void Merge(IEnumerable<SmartCoin> coins)
@@ -40,7 +48,7 @@ namespace WalletWasabi.BlockchainAnalysis
}
if (insertPosition > 0) // at least one element was inserted
{
- Labels = string.Join(", ", Coins.SelectMany(x => x.Label.Labels).Distinct(StringComparer.OrdinalIgnoreCase));
+ Labels = string.Join(", ", KnownBy);
}
}
}

MODIFY
WalletWasabi/Extensions/LinqExtensions.cs
WalletWasabi/Extensions/LinqExtensions.cs
@@ -83,6 +83,26 @@ namespace System.Linq
return !(source is null) && source.Any();
}
+ public static IEnumerable<IEnumerable<T>> CombinationsWithoutRepetition<T>(
+ this IEnumerable<T> items,
+ int ofLength)
+ {
+ return (ofLength == 1) ?
+ items.Select(item => new[] { item }) :
+ items.SelectMany((item, i) => items.Skip(i + 1)
+ .CombinationsWithoutRepetition(ofLength - 1)
+ .Select(result => new T[] { item }.Concat(result)));
+ }
+
+ public static IEnumerable<IEnumerable<T>> CombinationsWithoutRepetition<T>(
+ this IEnumerable<T> items,
+ int ofLength,
+ int upToLength)
+ {
+ return Enumerable.Range(ofLength, Math.Max(0, upToLength - ofLength + 1))
+ .SelectMany(len => items.CombinationsWithoutRepetition(ofLength: len));
+ }
+
public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> items, int count)
{
int i = 0;

MODIFY
WalletWasabi/Transactions/TransactionBuilding/SmartCoinSelector.cs
WalletWasabi/Transactions/TransactionBuilding/SmartCoinSelector.cs
@@ -7,6 +7,7 @@ using WalletWasabi.Exceptions;
using WalletWasabi.Helpers;
using WalletWasabi.Logging;
using WalletWasabi.Coins;
+using WalletWasabi.BlockchainAnalysis;
namespace WalletWasabi.Transactions.TransactionBuilding
{
@@ -29,23 +30,50 @@ namespace WalletWasabi.Transactions.TransactionBuilding
throw new InsufficientBalanceException(targetMoney, available);
}
- // Group coins by scriptPubKey in order to treat them all as one.
- var coinsByScriptPubKey = UnspentCoins
+ var clusters = UnspentCoins
+ .Select(coin => coin.Clusters)
+ .Distinct()
+ .CombinationsWithoutRepetition(ofLength: 1, upToLength: 6)
+ .Select(clusterCombination => UnspentCoins.Where(coin=> clusterCombination.Contains(coin.Clusters)))
+ .ToList();
+
+ clusters.Add(UnspentCoins);
+
+ var coinsByCluster = clusters
+ .Select(coins => (Coins: coins, Privacy: 1.0m / coins.SelectMany(x=>x.Clusters.KnownBy).Count()))
+ .Select(group => new
+ {
+ Coins = group.Coins,
+ Unconfirmed = group.Coins.Any(x => !x.Confirmed), // If group has an unconfirmed, then the whole group is unconfirmed.
+ AnonymitySet = group.Coins.Min(x => x.AnonymitySet), // The group is as anonymous as its weakest member.
+ ClusterPrivacy = group.Privacy, // The number people/entities that know the cluster.
+ Amount = group.Coins.Sum(x => x.Amount)
+ });
+
+ var coinsInBestCluster = coinsByCluster
+ .Where(group => group.Amount >= targetMoney)
+ .OrderBy(group => group.Unconfirmed)
+ .ThenByDescending(group => group.AnonymitySet) // Always try to spend/merge the largest anonset coins first.
+ .ThenByDescending(group => group.ClusterPrivacy) // Select lesser-known coins.
+ .ThenByDescending(group => group.Amount) // Then always try to spend by amount.
+ .First()
+ .Coins;
+
+ var coinsInBestClusterByScript = coinsInBestCluster
.GroupBy(c => c.ScriptPubKey)
.Select(group => new
{
Coins = group,
Unconfirmed = group.Any(x => !x.Confirmed), // If group has an unconfirmed, then the whole group is unconfirmed.
AnonymitySet = group.Min(x => x.AnonymitySet), // The group is as anonymous as its weakest member.
+ ClusterPrivacy = 1.0 / group.First().Clusters.KnownBy.Count(), // The number people/entities that know the cluster.
+ ClusterSize = group.First().Clusters.Size, // The number of coins in the cluster.
Amount = group.Sum(x => x.Amount)
});
var coinsToSpend = new List<SmartCoin>();
- foreach (IGrouping<Script, SmartCoin> coinsGroup in coinsByScriptPubKey
- .OrderBy(group => group.Unconfirmed)
- .ThenByDescending(group => group.AnonymitySet) // Always try to spend/merge the largest anonset coins first.
- .ThenByDescending(group => group.Amount) // Then always try to spend by amount.
+ foreach (IGrouping<Script, SmartCoin> coinsGroup in coinsInBestClusterByScript
.Select(group => group.Coins))
{
coinsToSpend.AddRange(coinsGroup);

Improve transaction privacy (use cluster info)