Select a better set of coins
ADD
WalletWasabi.Tests/UnitTests/Wallet/SmartCoinSelectorTests.cs
+using System.Linq;
+using NBitcoin;
+using WalletWasabi.Blockchain.Analysis.Clustering;
+using WalletWasabi.Blockchain.Keys;
+using WalletWasabi.Blockchain.TransactionBuilding;
+using WalletWasabi.Tests.Helpers;
+using Xunit;
+
+namespace WalletWasabi.Tests.UnitTests.Wallet;
+
+public class SmartCoinSelectorTests
+{
+ private KeyManager KeyManager { get; }
+
+ public SmartCoinSelectorTests()
+ {
+ KeyManager = KeyManager.Recover(new Mnemonic("all all all all all all all all all all all all"), "", Network.Main, KeyManager.GetAccountKeyPath(Network.Main));
+ }
+
+ [Fact]
+ public void SelectsOnlyOneCoinWhenPossible()
+ {
+ var keys = Enumerable.Range(0, 10)
+ .Select(_ => KeyManager.GenerateNewKey(new SmartLabel("Juan"), KeyState.Clean, false));
+
+ var cluster = new Cluster(keys);
+
+ var smartCoins = keys
+ .Select((key, i) => {
+ var coin =BitcoinFactory.CreateSmartCoin(key, 0.1m * (i+1));
+ coin.HdPubKey.Cluster = cluster;
+ return coin; });
+
+ var selector = new SmartCoinSelector(smartCoins);
+
+ var someCoins = smartCoins.Take(5).Select(x => x.Coin);
+ var coinsToSpend = selector.Select(someCoins, Money.Coins(0.3m));
+
+ var theOnlyOne = Assert.Single(coinsToSpend.Cast<Coin>());
+ Assert.Equal(0.3m, theOnlyOne.Amount.ToUnit(MoneyUnit.BTC));
+ }
+
+ [Fact]
+ public void PreferLessCoinsOverExactAmount()
+ {
+ var keys = Enumerable.Range(0, 5)
+ .Select(_ => KeyManager.GenerateNewKey(new SmartLabel("Juan"), KeyState.Clean, false))
+ .ToList();
+
+ var cluster = new Cluster(keys);
+
+ var smartCoins = keys
+ .Select((key, i) => {
+ var coin = BitcoinFactory.CreateSmartCoin(key, 0.1m * (i+1));
+ coin.HdPubKey.Cluster = cluster;
+ return coin; })
+ .ToList();
+ smartCoins.Add(BitcoinFactory.CreateSmartCoin(keys[0], 0.11m));
+
+ var selector = new SmartCoinSelector(smartCoins);
+
+ var someCoins = smartCoins.Select(x => x.Coin);
+ var coinsToSpend = selector.Select(someCoins, Money.Coins(0.41m));
+
+ var theOnlyOne = Assert.Single(coinsToSpend.Cast<Coin>());
+ Assert.Equal(0.5m, theOnlyOne.Amount.ToUnit(MoneyUnit.BTC));
+ }
+
+ [Fact]
+ public void PreferSameScript()
+ {
+ var keys = Enumerable.Range(0, 5)
+ .Select(_ => KeyManager.GenerateNewKey(new SmartLabel("Juan"), KeyState.Clean, false))
+ .ToList();
+
+ var cluster = new Cluster(keys);
+
+ var smartCoins = keys
+ .Select((key, i) => {
+ var coin = BitcoinFactory.CreateSmartCoin(key, 0.2m);
+ coin.HdPubKey.Cluster = cluster;
+ return coin; })
+ .ToList();
+ smartCoins.Add(BitcoinFactory.CreateSmartCoin(keys[0], 0.11m));
+
+ var selector = new SmartCoinSelector(smartCoins);
+
+ var someCoins = smartCoins.Select(x => x.Coin);
+ var coinsToSpend = selector.Select(someCoins, Money.Coins(0.31m)).Cast<Coin>().ToList();
+
+ Assert.Equal(2, coinsToSpend.Count);
+ Assert.Equal(coinsToSpend[0].ScriptPubKey, coinsToSpend[1].ScriptPubKey);
+ Assert.Equal(0.31m, coinsToSpend.Sum(x => x.Amount.ToUnit(MoneyUnit.BTC)));
+ }
+}
\ No newline at end of file

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/SmartCoinSelector.cs
WalletWasabi/Blockchain/TransactionBuilding/SmartCoinSelector.cs
@@ -4,6 +4,7 @@ using System.Collections.Generic;
using WalletWasabi.Exceptions;
using WalletWasabi.Blockchain.Analysis.Clustering;
using WalletWasabi.Blockchain.TransactionOutputs;
+using System.Collections.Immutable;
namespace WalletWasabi.Blockchain.TransactionBuilding;
@@ -44,14 +45,13 @@ public class SmartCoinSelector : ICoinSelector
// This operation is doing super advanced grouping on the coin clusters and adding properties to each of them.
var sayajinCoinClusters = coinClusters
.Select(coins => (Coins: coins, Privacy: 1.0m / (1 + coins.Sum(x => x.HdPubKey.Cluster.Labels.Count()))))
- .Select(group => new
- {
- 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.HdPubKey.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)
- });
+ .Select(group => (
+ 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.HdPubKey.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)
+ ));
// Find the best coin cluster that we are going to use.
IEnumerable<SmartCoin> bestCoinCluster = sayajinCoinClusters
@@ -65,21 +65,20 @@ public class SmartCoinSelector : ICoinSelector
var coinsInBestClusterByScript = bestCoinCluster
.GroupBy(c => c.ScriptPubKey)
- .Select(group => new { Coins = group });
-
- var coinsToSpend = new List<SmartCoin>();
+ .Select(group => (ScriptPubKey: group.Key, Coins: group.ToList()))
+ .ToImmutableList();
- foreach (IGrouping<Script, SmartCoin> coinsGroup in coinsInBestClusterByScript
- .Select(group => group.Coins))
- {
- coinsToSpend.AddRange(coinsGroup);
+ var coinsGroup = coinsInBestClusterByScript.Count < 10
+ ? coinsInBestClusterByScript.CombinationsWithoutRepetition(1, 5).Select(x => x.ToImmutableList())
+ : coinsInBestClusterByScript.Select(x => ImmutableList.Create(x))
+ .Concat(coinsInBestClusterByScript.Scan(ImmutableList<(Script ScriptPubKey, List<SmartCoin> Coins)>.Empty, (acc, coinGroup) => acc.Add(coinGroup)));
- if (coinsToSpend.Sum(x => x.Amount) >= targetMoney)
- {
- break;
- }
- }
+ var candidates = coinsGroup
+ .Select(x => x.SelectMany(y => y.Coins))
+ .Select(x => (Coins: x, Total: x.Sum(y => y.Amount)))
+ .Where(x => x.Total >= targetMoney) // filter combinations below target
+ .OrderBy(x => x.Coins.Count());
- return coinsToSpend.Select(c => c.Coin);
+ return candidates.First().Coins.Select(x => x.Coin);
}
}

Select a better set of coins