Improve anonymity scoring
MODIFY
WalletWasabi.Tests/Common.cs
WalletWasabi.Tests/Common.cs
@@ -5,6 +5,7 @@ using System.IO;
using System.Linq;
using System.Net;
using System.Runtime.CompilerServices;
+using WalletWasabi.Blockchain.Analysis;
using WalletWasabi.Blockchain.Analysis.Clustering;
using WalletWasabi.Blockchain.Keys;
using WalletWasabi.Blockchain.TransactionOutputs;
@@ -32,20 +33,75 @@ namespace WalletWasabi.Tests
public static string DataDir => EnvironmentHelpers.GetDataDir(Path.Combine("WalletWasabi", "Tests"));
- public static SmartTransaction RandomSmartTransaction()
+ public static BlockchainAnalyzer RandomBlockchainAnalyzer(int privacyLevelThreshold = 100, Money? dustThreshold = null)
{
+ dustThreshold ??= Money.Satoshis(1);
+ return new BlockchainAnalyzer(privacyLevelThreshold, dustThreshold);
+ }
+
+ public static SmartTransaction RandomSmartTransaction(int othersInputCount = 1, int othersOutputCount = 1, int ownInputCount = 0, int ownOutputCount = 0)
+ {
+ var km = RandomKeyManager().Item2;
var tx = Transaction.Create(Network.Main);
- tx.Outputs.Add(Money.Coins(1), new Key());
+ var walletInputs = new HashSet<SmartCoin>(ownInputCount);
+ var walletOutputs = new HashSet<SmartCoin>(ownOutputCount);
+
+ for (int i = 0; i < othersInputCount; i++)
+ {
+ var sc = RandomSmartCoin(RandomHdPubKey(km), 1m);
+ tx.Inputs.Add(sc.OutPoint);
+ }
+ for (int i = 0; i < ownInputCount; i++)
+ {
+ var sc = RandomSmartCoin(RandomHdPubKey(km), 1m);
+ tx.Inputs.Add(sc.OutPoint);
+ walletInputs.Add(sc);
+ }
+
+ for (int i = 0; i < othersOutputCount; i++)
+ {
+ var sc = RandomSmartCoin(RandomHdPubKey(km), 1.00001m);
+ tx.Outputs.Add(sc.TxOut);
+ }
+ for (int i = 0; i < ownOutputCount; i++)
+ {
+ var sc = RandomSmartCoin(RandomHdPubKey(km), 1.00001m);
+ tx.Outputs.Add(sc.TxOut);
+ walletOutputs.Add(sc);
+ }
+
var stx = new SmartTransaction(tx, Height.Mempool);
+
+ foreach (var sc in walletInputs)
+ {
+ stx.WalletInputs.Add(sc);
+ }
+
+ foreach (var sc in walletOutputs)
+ {
+ stx.WalletOutputs.Add(sc);
+ }
+
return stx;
}
- public static SmartCoin RandomSmartCoin(HdPubKey pubKey, decimal amount, bool confirmed = true, int anonymitySet = 1)
+ public static HdPubKey RandomHdPubKey(KeyManager km)
+ {
+ return km.GenerateNewKey(SmartLabel.Empty, KeyState.Clean, isInternal: false);
+ }
+
+ public static SmartCoin RandomSmartCoin(HdPubKey pubKey, decimal amountBtc, bool confirmed = true, int anonymitySet = 1)
+ => RandomSmartCoin(pubKey, Money.Coins(amountBtc), confirmed, anonymitySet);
+
+ public static int RandomInt(int minInclusive, int maxInclusive)
+ => new Random().Next(minInclusive, maxInclusive + 1);
+
+ public static SmartCoin RandomSmartCoin(HdPubKey pubKey, Money amount, bool confirmed = true, int anonymitySet = 1)
{
- var height = confirmed ? new Height(new Random().Next(0, 200)) : Height.Mempool;
+ var height = confirmed ? new Height(RandomInt(0, 200)) : Height.Mempool;
pubKey.SetKeyState(KeyState.Used);
var tx = Transaction.Create(Network.Main);
- tx.Outputs.Add(new TxOut(Money.Coins(amount), pubKey.P2wpkhScript));
+ tx.Outputs.Add(new TxOut(amount, pubKey.P2wpkhScript));
var stx = new SmartTransaction(tx, height);
pubKey.AnonymitySet = anonymitySet;
return new SmartCoin(stx, 0, pubKey);

ADD
WalletWasabi.Tests/UnitTests/BlockchainAnalysis/CoinJoinAnonscoreTests.cs
+using System;
+using System.Collections.Generic;
+using System.Text;
+
+namespace WalletWasabi.Tests.UnitTests.BlockchainAnalysis
+{
+ public class CoinJoinAnonscoreTests
+ {
+ }
+}

ADD
WalletWasabi.Tests/UnitTests/BlockchainAnalysis/NormalSpendAnonScoreTests.cs
+using NBitcoin;
+using System;
+using System.Collections.Generic;
+using System.Text;
+using WalletWasabi.Blockchain.Analysis;
+using Xunit;
+
+namespace WalletWasabi.Tests.UnitTests.BlockchainAnalysis
+{
+ /// <summary>
+ /// In these tests all the inputs of a transaction are controlled by the user.
+ /// </summary>
+ public class NormalSpendAnonScoreTests
+ {
+ [Fact]
+ public void OneOwnInOneOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(0, 1, 1, 0);
+ var coin = Assert.Single(tx.WalletInputs);
+ var key = coin.HdPubKey;
+ key.AnonymitySet = 3;
+
+ analyser.Analyze(tx);
+
+ // Since we sent this money to someone we should assume that someone learnt our input,
+ // so its anonset should become 1.
+ Assert.Empty(tx.WalletOutputs);
+ Assert.Equal(1, coin.HdPubKey.AnonymitySet);
+ }
+
+ [Fact]
+ public void ManyOwnInOneOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(0, 1, 3, 0);
+
+ foreach (var coin in tx.WalletInputs)
+ {
+ coin.HdPubKey.AnonymitySet = 3;
+ }
+
+ analyser.Analyze(tx);
+
+ // Since we sent this money to someone we should assume that someone learnt our inputs,
+ // so its anonset should become 1.
+ Assert.Empty(tx.WalletOutputs);
+ Assert.All(tx.WalletInputs, x => Assert.Equal(1, x.HdPubKey.AnonymitySet));
+ }
+
+ [Fact]
+ public void OneOwnInManyOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(0, 3, 1, 0);
+ var coin = Assert.Single(tx.WalletInputs);
+ var key = coin.HdPubKey;
+ key.AnonymitySet = 3;
+
+ analyser.Analyze(tx);
+
+ // Since we sent this money to someone we should assume that someone learnt our input,
+ // so its anonset should become 1.
+ Assert.Empty(tx.WalletOutputs);
+ Assert.Equal(1, coin.HdPubKey.AnonymitySet);
+ }
+
+ [Fact]
+ public void OneOwnInOneOutOneOwnOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(0, 1, 1, 1);
+
+ foreach (var coin in tx.WalletInputs)
+ {
+ coin.HdPubKey.AnonymitySet = 3;
+ }
+
+ analyser.Analyze(tx);
+
+ // Since we sent this money to someone we should assume that someone learnt both our input and output,
+ // so its anonset should become 1.
+ var output = Assert.Single(tx.WalletOutputs);
+ Assert.Equal(1, output.HdPubKey.AnonymitySet);
+ Assert.All(tx.WalletInputs, x => Assert.Equal(1, x.HdPubKey.AnonymitySet));
+ }
+
+ [Fact]
+ public void OneOwnInManyOutManyOwnOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(0, 3, 1, 3);
+
+ foreach (var coin in tx.WalletInputs)
+ {
+ coin.HdPubKey.AnonymitySet = 3;
+ }
+
+ analyser.Analyze(tx);
+
+ // Since we sent this money to someone we should assume that someone learnt both our input and output,
+ // so its anonset should become 1.
+ Assert.All(tx.WalletOutputs, x => Assert.Equal(1, x.HdPubKey.AnonymitySet));
+ Assert.All(tx.WalletInputs, x => Assert.Equal(1, x.HdPubKey.AnonymitySet));
+ }
+
+ [Fact]
+ public void ManyOwnInOneOutOneOwnOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(0, 1, 3, 1);
+
+ foreach (var coin in tx.WalletInputs)
+ {
+ coin.HdPubKey.AnonymitySet = 3;
+ }
+
+ analyser.Analyze(tx);
+
+ // Since we sent this money to someone we should assume that someone learnt both our inputs and output,
+ // so its anonset should become 1.
+ Assert.All(tx.WalletOutputs, x => Assert.Equal(1, x.HdPubKey.AnonymitySet));
+ Assert.All(tx.WalletInputs, x => Assert.Equal(1, x.HdPubKey.AnonymitySet));
+ }
+
+ [Fact]
+ public void ManyOwnInManyOutManyOwnOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(0, 3, 3, 3);
+
+ foreach (var coin in tx.WalletInputs)
+ {
+ coin.HdPubKey.AnonymitySet = 3;
+ }
+
+ analyser.Analyze(tx);
+
+ // Since we sent this money to someone we should assume that someone learnt both our inputs and outputs,
+ // so its anonset should become 1.
+ Assert.All(tx.WalletOutputs, x => Assert.Equal(1, x.HdPubKey.AnonymitySet));
+ Assert.All(tx.WalletInputs, x => Assert.Equal(1, x.HdPubKey.AnonymitySet));
+ }
+ }
+}

ADD
WalletWasabi.Tests/UnitTests/BlockchainAnalysis/SelfSpendAnonScoreTests.cs
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using Xunit;
+
+namespace WalletWasabi.Tests.UnitTests.BlockchainAnalysis
+{
+ /// <summary>
+ /// In these tests all the inputs and outputs of a transaction are controlled by the user.
+ /// </summary>
+ public class SelfSpendAnonScoreTests
+ {
+ [Fact]
+ public void OneOwnInOneOwnOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(0, 0, 1, 1);
+ var coin = Assert.Single(tx.WalletInputs);
+ var key = coin.HdPubKey;
+ key.AnonymitySet = 3;
+
+ analyser.Analyze(tx);
+
+ // Anonset of the input shall be retained.
+ // Although the tx has more than one interpretation
+ // blockchain anal usually just assumes it's a self spend.
+ Assert.All(tx.WalletOutputs, x => Assert.Equal(3, x.HdPubKey.AnonymitySet));
+ Assert.All(tx.WalletInputs, x => Assert.Equal(3, x.HdPubKey.AnonymitySet));
+ }
+
+ [Fact]
+ public void OneOwnInManyOwnOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(0, 0, 1, 3);
+ var coin = Assert.Single(tx.WalletInputs);
+ var key = coin.HdPubKey;
+ key.AnonymitySet = 3;
+
+ analyser.Analyze(tx);
+
+ // Anonset of the input shall be retained.
+ // Although the tx has many interpretations we shall not guess which one
+ // a blockchain analyzer would go with, therefore outputs shall not gain anonsets
+ // as we're conservatively estimating.
+ Assert.All(tx.WalletOutputs, x => Assert.Equal(3, x.HdPubKey.AnonymitySet));
+ Assert.All(tx.WalletInputs, x => Assert.Equal(3, x.HdPubKey.AnonymitySet));
+ }
+
+ [Fact]
+ public void ManyOwnInOneOwnOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(0, 0, 3, 1);
+ var smallestAnonset = 3;
+
+ tx.WalletInputs.First().HdPubKey.AnonymitySet = smallestAnonset;
+ foreach (var coin in tx.WalletInputs.Skip(1))
+ {
+ coin.HdPubKey.AnonymitySet = 100;
+ }
+
+ analyser.Analyze(tx);
+
+ // Anonset of the input shall be worsened because of input merging.
+ Assert.All(tx.WalletOutputs, x => Assert.True(x.HdPubKey.AnonymitySet < smallestAnonset));
+ Assert.All(tx.WalletInputs, x => Assert.True(x.HdPubKey.AnonymitySet < smallestAnonset));
+ }
+
+ [Fact]
+ public void ManyOwnInManyOwnOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(0, 0, 3, 3);
+ var smallestAnonset = 3;
+
+ tx.WalletInputs.First().HdPubKey.AnonymitySet = smallestAnonset;
+ foreach (var coin in tx.WalletInputs.Skip(1))
+ {
+ coin.HdPubKey.AnonymitySet = 100;
+ }
+
+ analyser.Analyze(tx);
+
+ // Anonset of the input shall be worsened because of input merging.
+ // Although the tx has many interpretations we shall not guess which one
+ // a blockchain analyzer would go with, therefore outputs shall not gain anonsets
+ // as we're conservatively estimating.
+ Assert.All(tx.WalletOutputs, x => Assert.True(x.HdPubKey.AnonymitySet < smallestAnonset));
+ Assert.All(tx.WalletInputs, x => Assert.True(x.HdPubKey.AnonymitySet < smallestAnonset));
+ }
+ }
+}

ADD
WalletWasabi.Tests/UnitTests/BlockchainAnalysis/WalletIrrelevantAnonScoreTests.cs
+using System;
+using System.Collections.Generic;
+using System.Text;
+using Xunit;
+
+namespace WalletWasabi.Tests.UnitTests.BlockchainAnalysis
+{
+ /// <summary>
+ /// In these tests no inputs, nor outputs in a transaction are controlled by the user.
+ /// </summary>
+ public class WalletIrrelevantAnonScoreTests
+ {
+ [Fact]
+ public void OneInOneOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(1, 1, 0, 0);
+
+ analyser.Analyze(tx);
+
+ Assert.Empty(tx.WalletInputs);
+ Assert.Empty(tx.WalletOutputs);
+ }
+
+ [Fact]
+ public void ManyInManyOut()
+ {
+ var analyser = Common.RandomBlockchainAnalyzer();
+ var tx = Common.RandomSmartTransaction(3, 3, 0, 0);
+
+ analyser.Analyze(tx);
+
+ Assert.Empty(tx.WalletInputs);
+ Assert.Empty(tx.WalletOutputs);
+ }
+ }
+}

MODIFY
WalletWasabi/Blockchain/Analysis/BlockchainAnalyzer.cs
WalletWasabi/Blockchain/Analysis/BlockchainAnalyzer.cs
@@ -3,6 +3,7 @@ using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
+using WalletWasabi.Blockchain.Keys;
using WalletWasabi.Blockchain.Transactions;
namespace WalletWasabi.Blockchain.Analysis
@@ -23,34 +24,78 @@ namespace WalletWasabi.Blockchain.Analysis
/// </summary>
public void Analyze(SmartTransaction tx)
{
- // Dust attack could ruin the analysis, so it's better not to incorporate this.
- // For example if someone would dust a mixed coin of ours, its anon score would end up being 1,
- // even though the duster does not know who it sent the money.
- // FTR at the time of writing this comment the transaction processor doesn't even let dust to come this far,
- // but it's better to be prepared for future changes if it's not too computationally expensive.
- foreach (var newCoin in tx.WalletOutputs.Where(x => x.Amount > DustThreshold))
+ var inputCount = tx.Transaction.Inputs.Count;
+ var outputCount = tx.Transaction.Outputs.Count;
+
+ var ownInputCount = tx.WalletInputs.Count;
+ var ownOutputCount = tx.WalletOutputs.Count;
+
+ var othersInputCount = inputCount - ownInputCount;
+ var othersOutputCount = outputCount - ownOutputCount;
+
+ // If self spend then retain anonset:
+ if (inputCount == ownInputCount && outputCount == ownOutputCount)
+ {
+ var anonset = Intersect(tx.WalletInputs.Select(x => x.HdPubKey.AnonymitySet), 1);
+ foreach (var key in tx.WalletInputs.Concat(tx.WalletOutputs).Select(x => x.HdPubKey))
+ {
+ key.AnonymitySet = anonset;
+ }
+ }
+ // If all our inputs are ours and there's more than one output that isn't,
+ // then we can assume that the persons the money was sent to learnt our inputs.
+ // AND if there're outputs that go to someone else,
+ // then we can assume that the people learnt our change outputs,
+ // or at the very least assume that all the changes in the tx is ours.
+ // For example even if the assumed change output is a payment to someone, a blockchain analyzer
+ // probably would just assume it's ours and go on with its life.
+ else if (inputCount == ownInputCount && othersOutputCount > 0)
+ {
+ foreach (var key in tx.WalletInputs.Concat(tx.WalletOutputs).Select(x => x.HdPubKey))
+ {
+ key.AnonymitySet = 1;
+ }
+ }
+ else
+ {
+ foreach (var newCoin in tx.WalletOutputs)
{
- // Calculate anonymity sets.
// Get the anonymity set of i-th output in the transaction.
var anonset = tx.Transaction.GetAnonymitySet(newCoin.Index);
+ // Let's assume the blockchain analyser also participates in the transaction.
+ anonset = Math.Max(1, anonset - 1);
+
// If we provided inputs to the transaction.
- if (tx.WalletInputs.Any())
+ if (ownInputCount > 0)
{
- // Take the input that we provided with the smallest anonset.
+ var privacyBonus = Intersect(tx.WalletInputs.Select(x => x.HdPubKey.AnonymitySet), (double)ownInputCount / inputCount);
+
+ // If the privacy bonus is <=1 then we are not inheriting any privacy from the inputs.
+ var normalizedBonus = privacyBonus - 1;
+
// And add that to the base anonset from the tx.
- // Our smallest anonset input is the relevant here, because this way the common input ownership heuristic is considered.
- // Take minus 1, because we do not want to count own into the anonset, so...
- // If the anonset of our UTXO would be 1, and the smallest anonset of our inputs would be 1, too, then we don't make...
- // The new UTXO's anonset 2, but only 1.
- anonset += tx.WalletInputs.Select(x => x.HdPubKey).Min(x => x.AnonymitySet) - 1;
+ anonset += normalizedBonus;
}
- newCoin.HdPubKey.AnonymitySet = Math.Min(anonset, newCoin.HdPubKey.AnonymitySet);
+ HdPubKey hdPubKey = newCoin.HdPubKey;
- // Set clusters.
+ hdPubKey.AnonymitySet = hdPubKey.AnonymitySet == HdPubKey.DefaultHighAnonymitySet
+ ? anonset
+ : Intersect(new[] { anonset, hdPubKey.AnonymitySet }, 1);
+ }
+ }
+
+ AnalyzeClusters(tx);
+ }
+
+ private void AnalyzeClusters(SmartTransaction tx)
+ {
+ foreach (var newCoin in tx.WalletOutputs)
+ {
if (newCoin.HdPubKey.AnonymitySet < PrivacyLevelThreshold)
{
+ // Set clusters.
foreach (var spentCoin in tx.WalletInputs)
{
newCoin.HdPubKey.Cluster.Merge(spentCoin.HdPubKey.Cluster);
@@ -58,5 +103,26 @@ namespace WalletWasabi.Blockchain.Analysis
}
}
}
+
+ /// <param name="coefficient">If larger than 1, then penalty is larger, if smaller than 1 then penalty is smaller.</param>
+ private int Intersect(IEnumerable<int> anonsets, double coefficient)
+ {
+ // Sanity check.
+ if (!anonsets.Any())
+ {
+ return 1;
+ }
+
+ // Our smallest anonset is the relevant here, because anonsets cannot grow by intersection punishments.
+ var smallestAnon = anonsets.Min();
+ // Punish intersection exponentially.
+ // If there is only a single anonset then the exponent should be zero to divide by 1 thus retain the input coin anonset.
+ var intersectPenalty = Math.Pow(2, anonsets.Count() - 1);
+ var intersectionAnonset = smallestAnon / Math.Max(1, intersectPenalty * coefficient);
+
+ // Sanity check.
+ var normalizedIntersectionAnonset = Math.Max(1d, intersectionAnonset);
+ return (int)normalizedIntersectionAnonset;
+ }
}
}

MODIFY
WalletWasabi/Blockchain/Keys/HdPubKey.cs
WalletWasabi/Blockchain/Keys/HdPubKey.cs
@@ -14,8 +14,10 @@ namespace WalletWasabi.Blockchain.Keys
[JsonObject(MemberSerialization.OptIn)]
public class HdPubKey : NotifyPropertyChangedBase, IEquatable<HdPubKey>
{
+ public const int DefaultHighAnonymitySet = int.MaxValue;
+
+ private int _anonymitySet = DefaultHighAnonymitySet;
private Cluster _cluster;
- private int _anonymitySet = int.MaxValue;
public HdPubKey(PubKey pubKey, KeyPath fullKeyPath, SmartLabel label, KeyState keyState)
{

Improve anonymity scoring