Can someone help me understand the cluster intersection attack?

[Antti Kaikkonen]

Quote from the blockski paper: "The intuition behind the attack is that outputs mixed in different transactions are often spent together. Thus, when these coins are spent together, we trace each one back to a (potentially large) set of possible address clusters and examine the intersection of these sets. This will likely result in a unique cluster. We conclude that the mixed outputs are linked to the wallet represented by this cluster."

But I don't understand the assumption that if the if the intersection matches an unique address cluster then that would mean that it's the sender. Below is a counter example that I tried to make using only 1 round of mixing:

Based on my understanding of the cluster intersection attack it would select A2 as the source address because it is reachable from both privatesend inputs. Why aren't A1 and A3 also valid candidates?

 

[stan.distortion]

Quote from the blockski paper: "The intuition behind the attack is that outputs mixed in different transactions are often spent together. Thus, when these coins are spent together, we trace each one back to a (potentially large) set of possible address clusters and examine the intersection of these sets. This will likely result in a unique cluster. We conclude that the mixed outputs are linked to the wallet represented by this cluster."

But I don't understand the assumption that if the if the intersection matches an unique address cluster then that would mean that it's the sender. Below is a counter example that I tried to make using only 1 round of mixing:View attachment 4893
Based on my understanding of the cluster intersection attack it would select A2 as the source address because it is reachable from both privatesend inputs. Why aren't A1 and A3 also valid candidates?

That attack is only possible in theory, in reality it would be extremely rare, less than one in a million. The only way they could get it to work was on their own private network with PrivateSend settings no sensible user would ever use, it's great folks are testing out PrivateSend and trying to find vulnerabilities but this one's very much a fringe possibility and only reproducible in laboratory conditions.

 

[Antti Kaikkonen]

That attack is only possible in theory, in reality it would be extremely rare, less than one in a million. The only way they could get it to work was on their own private network with PrivateSend settings no sensible user would ever use, it's great folks are testing out PrivateSend and trying to find vulnerabilities but this one's very much a fringe possibility and only reproducible in laboratory conditions.

Quote form the paper: "
Experimental setup. To perform this attack, we used shapeshift.io (an online service for conversion between cryptocurrencies) to convert Bitcoin into Dash, which we withdrew into a single address. We used the default Dash wallet to mix 0.55 Dash using the default parameters, namely 2 rounds of mixing. We obtained 55 separate mixed outputs, each 0.01 Dash. Next, we re-implemented the PrivateSend algorithm from the Dash wallet code on top of BlockSci. Given a desired spend amount, the algorithm selects a set of mixed inputs from the wallet that sum to this amount. It is shown in Algorithm 1 in the appendix. This allowed us to simulate our own PrivateSend transactions instead of actually making them."

Based on my understanding of the above they did real mixing with other users in the blockchain but only simulated the input selection part for the final step of spending the mixed outputs. This is also supported by the fact that the algorithm in the appendix is called "SelectPSInputs". Assuming that they implemented the input selection algorithm correctly then the results would be the same with real privatesend transactions.

Average number of inputs in a privatesend transaction after block 600000 is about 43. They simulated the attack for number of inputs ranging from 2 to 55. I think their setup is reasonable but I just don't understand why the intersection attack would work.

 

[stan.distortion]

Iirc they only used 1 round of PrivateSend, something no user that actually cared about their privacy would do.

 

[Antti Kaikkonen]

Iirc they only used 1 round of PrivateSend, something no user that actually cared about their privacy would do.

They used 2 rounds which is the default number in the dash wallet and probably a significant amount of dash users use. However I don't know if they tracked only 2 rounds because an outside blockchain observer couldn't know the number of rounds used.

 

[stan.distortion]

They used 2 rounds which is the default number in the dash wallet and probably a significant amount of dash users use. However I don't know if they tracked only 2 rounds because an outside blockchain observer couldn't know the number of rounds used.

My bad there, I thought it was just one round. No, they'd just see it as part of a long chain of PrivateSend transactions. I could've sworn @UdjinM6 wrote a good post on it but I can't find it, digging back through it looks like one of the issues was no mixing between transactions but I'm fairly sure there where a few more issues with their method of testing that would be unlikely in the real world.

 

[Antti Kaikkonen]

Actually I'm not so much interested in how likely it would work but more interested in understanding why it works.

For example: would it select A2 as the only possible source address like I understood it. If it would then what's the reasoning to exclude for example the combination of A1 and A3?

 

[stan.distortion]

I'm guessing because they're re-combined but it doesn't make a whole lot of sense to me, I'd have thought the only way that could work is if the entire amount was used, ie. 0.55 in, 0.55 out and I can't see how that would work through multiple rounds. Their denominations seem weird too, 0.55 shouldn't result in 55 of 0.01, at least some of it should have been denominations of 0.1