Mixing Transactions with all inputs from the same transaction

[Antti-Kaikkonen]

There are many mixing transactions in the blockchain where all of the inputs come from the same mixing transaction.

Here are 4 examples:
https://dashradar.com/explorer/tx/6cdc89ae72f50816b3e6a74ac405b6ad025271db8be0b73f47aec7331b1916f2 (all inputs from 4a5fbb78122ab96e599aae1e73c5679808c0c924454eb8ebadab864553fff567)

https://dashradar.com/explorer/tx/b5c348c793c5e86ba4662c5b593acf07ec913126bc8b3f65415cfabfbada4931 (all inputs from 265b453958069bf9c572f23012499387bea651398f56d8bec048637c25641bdb)

https://dashradar.com/explorer/tx/761d70a5e66963d9c0c5871bd5f10da8bca1cd91ba3bcbecaf529dd6a5a5eb3c (all inputs from a3e2f72a5d81de7afbf124285ed75e1405caa57f111d65c6cc70ace09751b7a7)

https://dashradar.com/explorer/tx/4a5fbb78122ab96e599aae1e73c5679808c0c924454eb8ebadab864553fff567 (all inputs from 209101da7a14f8aa3791bfc1a55809c0c3b42122c38f4384db918b2a91af6f64)

I think that this kind of mixing transactions do not increase anonymity and could compromise your privacy if too many of your mixing rounds are this kind of transactions.

[Antti-Kaikkonen]

This bar chart shows the daily percentage of mixing transactions where are inputs are from the same transaction:

This bar chart shows the daily average branching factor of mixing transactions (number of different transaction ids in the inputs):

What is important here is that immediately after November 8th 2017 the percentage of mixing transactions where all inputs are from the same transaction has increased significantly. The average branching factor has also decreased significantly. This data suggests that the PrivateSend "improvements" released in 0.12.2 on November 8th has actually caused mixing to become significantly less efficient (less privacy achieved per mixing round). To fix this issue I recommend using this approach as suggested by @paulied.

[Antti-Kaikkonen]

One possible solution to still get some PrivateSend balance sufficiently fast would be to randomly choose denominated inputs with a probability proportional to the number of rounds mixed.

For example we could use 1+nRounds*0.5 to weight the inputs. This would give a weight of 1.0 for a 0-round input and a weight of 4.5 for a 7-round input. This means that an input with 7 rounds would be chosen 4.5 times more likely than an input with 0 rounds.

If a user has hundreds of inputs then that should probably be taken into account. For example we could only select among the ~100 inputs with most completed mixing rounds.

[PastaPastaPasta]

Very interesting @Antti-Kaikkonen. You seem to be on the right track with your idea directly above. That should allow the user to get some balance fairly quickly. Albiet, there is likely some data leakage there, it is likely better than the current system

[akijuh]

Good info Antti.
Ping to @UdjinM6 and @codablock

[UdjinM6]

Good job analysing the data @Antti-Kaikkonen 👍

But will the average branching factor even matter after #2075 is activated? I don't see how increasing this factor would help to improve privacy tbh (besides from creating some additional impact on memory consumption for blockchain analysis tools).

[PastaPastaPasta]

@UdjinM6, I'm not sure if it would leak enough to result in an attack vector, however there defenitely is data leakage when the most mixed inputs get mixed again. If you can predict which input will be mixed at each step, which I think is the current state, it would allow for some level of grouping which could result in deanonymizing rounds.

[Antti-Kaikkonen]

If the branching factor was always 1 then there would be exactly the same number of create denominations transactions reachable from a PrivateSend transaction as the PS transaction has inputs. When the branching factor is higher then there should at least on average be more create denominations transactions reachable from a PS transaction.

Tbh I didn't really understand the issue in #2075. I only understood the example diagram provided by @InhumanPerfection explaining a potential issue with the pull request.

[Antti-Kaikkonen]

Here is the daily average number of create denominations transactions reachable from a PrivateSend input transaction within 2-3 rounds of mixing. The x-axis date represents the date when the PrivateSend input transaction was included in a block.

As you can see the number dropped significantly after November 8th indicating that the average anonymity set is smaller.

As @paulied pointed out, this doesn't necessarily result in an attack vector where the privacy of a PrivateSend transaction can be completely broken. However, this should certainly make statistical analysis a lot more effective meaning that there is less privacy.

Edit: I realized that there is probably an error in the above graph. Trying to fix..
Edit2: Fixed.

[UdjinM6]

pls see #2261

[UdjinM6]

Mixing part has changed a lot and initial issue should not be relevant anymore but I would be very interested to see some analysis for v13 once it's deployed widely (i.e. after dip3 activation) @Antti-Kaikkonen . Closing this one, feel free to open new issue if you find something... interesting ;) in the way new PS works.