[Breakthrough] Occasional Anonymity Loss

[nopara73]

The past days I have been investigating a user's anonymity loss and I think I have finally arrived to a theory that explains it. I examined a number of testnet and mainnet wallets and this case is present about 0.1% of the times. It happens much more often for whales or plebwhales.

Take a transaction when the user comes with these coins:

Amount	Anonymity
100	1
3	1000
2	1000
1	1000

The rest of the users come with many coins between 100 and 3 and many under 3.

Let's say we create an output 105 and other smaller ones.

In this case this output of ours receives an anonymity of 1 and let's say the rest of our outputs receives high anonymities.

The total anonymity loss here is roughly (100 + 3000 + 2000 + 1000) - (105 + a little bit) ~ 6000.

And unfortunately the anonymity loss here is completely justified!

So, this means we have to fix the whale UX,

• which brings us back to the early, later abandoned implementation of whalerounds: getting larger people to wait longer for each other
• also we can probably improve coin selection by (1) getting whales to select less inputs or (2) select inputs smarter, incorporating the insight here.
• also we can probably improve amount decomposition by getting whales to create more outputs

Also note this issue is aggravated by ideas those aim to increase input counts like @MaxHillebrand's here: #10681 or @turbolay's here: #10678 (comment)

[MaxHillebrand]

That's a good catch, sounds about right.

[turbolay]

You rediscovered #10096 and #8938; this is exactly the issue explained and tried to be mitigated by implementing these points: (1) getting whales to select less inputs or (2) select inputs smarter, incorporating the insight here.. You can also see that my comment on #10096 explains that another mitigation is to reduce non standard change at all costs, which is kinda similar to the last thing you mentionned: also we can probably improve amount decomposition by getting whales to create more outputs

And by the way, your example would be much worse the other way around:

Amount	Anonymity
100	1000
3	1000
2	1
1	1000

Like this, the user is losing much more global % AnonScore, and this has an impact both:

• Direct: Global AnonScore will exceptionally decrease directly
• Long lasting: In the following round, this input will tremendously affect the WeightedAverage, hence the AnonScore gains of the other outputs.

[nopara73]

@turbolay it seems you're conflating what our anonymity calculation says about privacy loss and the actual privacy loss is and thus you're bringing in many issues needlessly like #10096 or your example:

And by the way, your example would be much worse the other way around

It's not actually bad for privacy, only for our anonymity calculation thinks so, and by the way it is the fix: #10699

However what's going on in this very issue is bad for privacy, not only our anonymity calculations say so.

[nopara73]

@turbolay Could you elaborate/copy paste the relevant text on this one here?

You can also see that my comment on #10096 explains that another mitigation is to reduce non standard change at all costs, which is kinda similar to the last thing you mentionned: also we can probably improve amount decomposition by getting whales to create more outputs

[turbolay]

@turbolay Could you elaborate/copy paste the relevant text on this one here?

Sure!
This Anonymity Loss is affecting exclusively (or almost exclusively) the big non standard output. If we reduce it, we will lose anonymity on a smaller amount. Hence, the user will be able to spend privately a bigger percentage of its wallet faster, but also the subsequent AnonymityScore will go up faster during remixes because the WeightedAverage will be less affected.

Creating more outputs for whales as you suggested is a good and effective way to reduce this change
One other approach (not mutually exclusive) is that instead of choosing the denomination that has the less cost (this line), we should prefer denominations with less change, especially if this change is suspected to be one of biggest output in the round. Obviously cost should still be acceptable (maybe proportionate to the amount).

Let me also drop here an observation that I made on Slack and that I think relevant here: https://tumblebit.slack.com/archives/CFBJX6MN0/p1682306405947139

Backup of the Slack comment:

I think that this Coinjoin is a really good example of why sometimes we have bad consolidation, at least with the naive decomposer (Lucas’ decomposer is a black box for me): https://mempool.space/tx/2f74c5a88ce9279a68ba11305e425087648858f6d5315aa475298587e71b977a
The whale had 5 inputs of 20/21 BTC, 100 BTC total. Another whale had 2 inputs of 20 BTC. Then no other inputs where big.
Most bad things will basically happen on this line:
if (!denoms.Any() || denom.Amount.Satoshi <= (long)(denoms.Last().Amount.Satoshi / filterSeverity))
The first denom below 20 BTC will be added, 20 BTC itself because of the !denoms.Any() . Then, every denominations below will be filtered out because we’re heavy filtering at the big amounts, until reaching the denoms with other participants, much much lower in that case, ‎1.34217728 BTC
We will then reach this line: var maxDenomUsage = Random.Next(2, 8);
But in fact, we’re already f*cked:
If we get a big number on this random, we will have a nice decomposition without consolidation, but we will gain almost no AnonScore , because we will have a high rate of these outputs with 20BTC denom, and the AnonScore gained is divided by this rate.
If we get a low number on this random, let’s say 3 as the whale got in my example, well 40 BTC will be mixed using these denoms, but then what about the 60 BTC remaining? remember that the next denom is 1.34217728 BTC…. well it won’t be possible to “consume” the remaining BTCs with such low denominations available -> we will create big change, potentially losing tons of AS if we mixed with a 1 AS input.

[nopara73]

Status Update

This issue is nearly resolved at this point, although there's still an unexplored territory for improvements. Let me explain: there are 3 paths one can take to improve upon this:

1. anonymity calculation - ☑
2. amount decomposition - almost ☑, we just have to put the painting on the wall: the last PR is now waiting for the final sanity test of @adamPetho and @turbolay: Increase max out from 8 to 10 #10813
3. input selection (including whale rounds and stuff) - ☐

[nopara73]

Status Update

• ☑anonymity calculation related improvements
• ☑amount decomposition related improvements
• ☐ input selection related improvements

[molnard]

What is missing to finish this?

[nopara73]

It's fixed, I only want to put the cherry on top of the cake: whale rounds. It will take some time before I get there.

[molnard]

Are you getting back to this?

[nopara73]

I am working on this.

[Pule08]

@nopara73 do you have news about this issue? Thank you!

[nopara73]

I am working on this.

[nopara73]

Only remaining thing here is: #11676