Estimating anonymity set size?

Question

Is there any way to at least estimate what kind of anonymity set a user would have after churning Monero X times assuming the anonymity set of each individual transaction is the ringsize (i.e. there are no major flaws that would give an attacker any ideas about which inputs are decoys)?

The adversary I'm thinking about in this case would be someone looking at a future transaction (say, a cash out to an exchange to convert Monero to fiat) and attempting to correlate that transaction to the earlier transaction where the same user converted fiat/another cryptocoin to Monero at an exchange. So basically an E-A-E attack.

Intuitively, it would seem like if you waited a reasonable amount of time between transactions the anonymity set would be ringsize^(number of churns), as each transaction has (ringsize) inputs and by the time you started your next churn each decoy has likely been used at least once giving another (ringsize) decoys for each decoy you used, and by the time you churn again each of those decoys has likely been used again giving another (ringsize) decoys per decoy etc, but the anonymity set in that case grows well beyond the total number of transactions on the entire blockchain with just a few churns so that can't be right.

Answer 1

Any given output in a ring has a 1/11 chance it is the true spend, whether you see that output in one ring or N different tx rings.

One of the problems with churning is it can easily have the opposite and undesired effect - reducing ones anonymity set. This can either be through timing analysis and / or linked outputs (e.g. seeing a tx with 3 specific outputs being spent and those 3 input rings each having one of the original 3 outputs).

For example, if an exchange sends you 3 outputs in a transaction (your withdrawal) and you then merge all those outputs (via a churn) to a subsequent single tx, the chance of it being you spending becomes significantly higher: 1 tx, 3 input rings with each ring containing 1 of the original 3 withdrawal outputs; it's an almost certainty it's you.

If on the other hand you hadn't performed this churn, you defer the decision making to the wallet to make its best effort in avoiding creating this kind of association. Which brings us to one of the specific cases of churning that can help. If you don't have enough other spare outputs to fund the new transaction, then performing careful churns (utilizing sweep_single) comes into play, as you can perform individual churns on those 3 outputs. Which brings us to the interesting part of your question: timing.

Performing 3 sweep_single transactions to churn those outputs in quick succession, isn't going to help much. Imagine all 3 in different transactions but in the same block - bingo, you're not greatly improved. What you really want to do is space them out to a degree that they could have naturally been selected as decoys in other transactions.

There's no comprehensive research yet (at least that I've come across) to give an indication of the best timing to use, though this topic does come up from time-to-time in MRL discussions, often in relation to the output selection algorithm, to improve default wallet behavior. One thing we can say for certain is that spreading out these single output churns over hours, days or even weeks is going to be better that in the same transaction or block.