Because I am not up-to-speed on communicating with the Monero devs (on Github or other back channels), and because my efficiency is my utmost priority and given posting in this forum is the most efficient way for me to communicate my thoughts to all that follow me, I will post this somewhat out-of-band comment here in hopes of getting a response from smooth (or if need be tacotime or fluffypony).
I do not have time to read various Monero research papers and otherwise dig to see if the following concern is already addressed.
I am concerned about a hole in the anonymity of Cryptonote ring signatures. I had sort of described this issue to smooth (who apparently relayed it to all) when I was contemplating ways that BCX might unmask the anonymity of users. I do not recall if I made this specific weakness explicit as follows.
If the actual input to a transaction (in Monero terminology this is the output of the prior transaction) is not also an input to another transaction's ring signature (and when all the other inputs to the ring are spent) or if it is also the input to a subsequent ring in which all the other inputs were outputs created after the said transaction was created, then the anonymity of the said transaction is entirely unmasked.
Combinatorial trees can be searched as well, thus even if only some of the other inputs were outputs created after the said input was created, this could cascade into unmasking the anonymity or at least reducing the anonymity set. And note the anonymity set also vulnerable to further reduction by out-of-band attacks such as IP de-obfuscation, rubber hoses, stolen private keys, hacked users, etc.
There are some tweaks that need to be made to insure the above is unlikely. Hopefully Monero is enforcing some restrictions already on which outputs can be used in ring inputs? If not, they need to get on it pronto.
P.S. for those who thought I wasn't sincerely attempting to help Monero during the BCX incident, I hope the above satisfies you. I think before I had an agreement with the Monero devs (via smooth) not to write publicly all the details of the above weakness in order to give them time to address it. I think they've had sufficient time and I want to make sure this is addressed.
TPTB_need_war, I'm a little confused by your comments here, :
"If the actual input to a transaction (in Monero terminology this is the output of the prior transaction) is not also an input to another transaction's ring signature (and when all the other inputs to the ring are spent) or if it is also the input to a subsequent ring in which all the other inputs were outputs created after the said transaction was created, then the anonymity of the said transaction is entirely unmasked."
[
could you explain how an input to a transaction is not also an input to another transactions ring signature when other inputs to the ring are spent? Specifically, how do you know the other inputs are spent, if they are also in ring signatures? (Ofc all other inputs could be sent with 0-mixin, but fluffyponyza has mentioned that this is in MRL004, and will be modified in a upcoming fork (for example mymonero forces min-mixin 3).
Also in your second sentence (sorry it's a little hard to parse), "[if actual input to a transaction]
is also the input to a subsequent ring in which all other inputs were outputs created after the said transaction was created
," how do you know in the subsequent (or initial ring) that said input is not being grabbed ad-hoc from another user as a decoy input for both the initial and subsequent ring without knowing which inputs have actually been spent?
could you please help me out by perhaps giving an example of how either of these would work (disregarding the 0-mixin case which has been addressed by fluffypony / mrl-004)
(unless you have some way of telling whether outputs have been spent, thus proving the proofs of Fujisaki/Suzuki https://eprint.iacr.org/2006/389.pdf incorrect, what you suggest seems impossible to me). Ok - I see there is an error in this logic.. in FS, they don't have any additional data about the ring itself (like inputs / outputs) so perhaps with some graph analysis with this might be possible.. -I don't think it would be a difficult fix if this was possible however, you just need to compute the graph of the people you are mixing with and make sure there are no loops.. (if the graph gets too big, pick a new ring)..
