Tech note/MRL bulletin on linkability, dead outputs, and churn in Monero

[b-g-goodell]

Linkability in Monero is one of the older topics at MRL. It has been studied before (see here, here and here); recent set-theoretic results (see here) and the start of some graph-theoretic results (see here, in progress) have added to our body of knowledge.

We would like a technical note or an MRL bulletin compiling these results in a convenient location. MRL is aware of at least one paper in preparation by outside researchers studying this problem, with results including, in part, the difficulty of finding a complete list of all "provably spent" outputs (previously called blackballed outputs, we now refer to these as dead outputs) as belonging to a class harder than NP (see here).

[b-g-goodell]

Note: finding a complete list of all dead outputs is not necessary for a malicious party to reduce the untraceability of Monero, which is good for the attacker because it's sharp-P to do so. A partial list of dead outputs, perhaps generated by the attacker, can lead to those outputs being used as mix-ins for ring signatures, and so a partial solution is sufficient for an attacker to reduce untraceability. However, partial solutions are insufficient for an attacker to totally gain the upper hand (see chain reaction paper MRL-0001).

[b-g-goodell]

Note: applying graph theoretic methods with weighted edges, weighted according to output age, and seeking matching on a weighted bipartite graph can present a formalization of the temporal linkability problem brought up here.

Matching results/solutions to this problem, however, do not admit an easy way of testing false negatives. Heuristic approaches like this lead to a sensitivity v. specificity problem that makes assessing the goodness of the solution a PITA; although the majority of true negatives will be caught, it's difficult to assess how many negatives are true negatives and how many are false negatives, leading to the possibility that the vast majority of negatives are false.

In a law-enforcement context or a medical context, this means accusing innocent people or diagnosing healthy people, respectively, and is sufficiently problematic that these heuristics may be totally useless.

[b-g-goodell]

Note: it is thought that churning outputs by sending them to yourself multiple times should be sufficient to ensure traceability. This must be addressed formally; churning without regard to your temporal statistics (wait time between churns) can give away this behavior.

By picking a wait time for a churn that is drawn from the same temporal distribution as your wallet software when it selects mix-ins, this ensures that the mix-in/dummy ring members have the same distribution of ages as the "true" signer and totally eliminates the temporal linkability issue from monerolink.

Note also: if multiple wallets use unique temporal distributions for selecting mix-ins, or if devices use a compromised PRNG, then an observer may be able to statistically glean some non-zero amount of information about either the wallet software or the device used to construct a churn. Hence, there is a non-zero amount of linkability gained by an attacker in these scenarios. Unfortunately, there is not too much we can do about unique wallet software showing up or compromised PRNG on devices.

[b-g-goodell]

This may be sufficiently broad to warrant more than one note: one for dead outputs and one for churn

[SamsungGalaxyPlayer]

@b-g-goodell I recommend two notes. Good to know you've settled on the name "dead" outputs.

[SamsungGalaxyPlayer]

I wrote up a basic set of churn tool requirements here. We of course still need the research notes explaining the protections provided by churning and their limitations: https://github.com/wownero/wownero/issues/146#issuecomment-450674903