Discussed at length in section 3.1 onwards in MRL4: https://lab.getmonero.org/pubs/MRL-0004.pdf
Question on mixin selection
Hello,
I wonder something about the process through which "other inputs" are selected to be mixed with the "true input" when making a transaction.
How are these inputs selected? Is it purely random? (except for amounts, obviously)
Because if that's the case, there's a problem there. Actual usage is not random: the age of the outputs change the likelihood of it being used. Newer outputs tend to be used more frequently. You can check that in Bitcoin and probably on other coins.
So, if Monero selects the mixin inputs randomly, an observer could see which of the inputs seem to be more likely to be the true one by checking which of them is closer to the "real usage function" than to a random distribution. Of course, that would require math knowledge that I - and most people - don't have. But once you write a program that does it, you can publish data about all transactions in the chain and everybody can use this data.
Fixing that is probably not an easy task. It would require first of all to know which is the "real distribution", and in Monero you cannot, by desing, know that for sure. Using Bitcoin or any other coin as reference might not be accurate as their usage might not correspond to Monero's usage. And finally, this distribution is not static: it will change in time.
I think the only way to come out with such "real distribution" is by, well... attacking Monero users' privacy... It would be necessary to build up the data that an attacker would build up, in order to know which are the inputs that don't seem to follow a random age distribution in Monero's chain. Once the discrepancy found, the random selection gets replaced with a selection that would destroy such discrepancy and make every input as likely to be the true one. But obviously, this function would need to evolve, so it would have to constantly re-read the chain and check again for discrepancies.
I cannot even imagine the level of math required to do such a thing.
"Newer outputs tend to be used more frequently"
This was changed to a triangular distribution with more recent outputs assumed to be more likely as you suggested
https://github.com/monero-project/bitmonero/commit/f2e8348be0c91c903e68ef582cee687c52411722
According to wikipedia the triangular distribution "is based on a knowledge of the minimum and maximum and an "inspired guess" as to the modal value. For these reasons, the triangle distribution has been called a "lack of knowledge" distribution"
Perhaps in the future we'll come up with a method to do even better, but for now it seems to be the best possible with the available information.