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)..
Someone was kind enough to ping me in private to come back here. Otherwise I wouldn't have seen this. I am not reading this thread normally.
What I was getting at is the ordering that transactions appear in the block chain. I provided some examples where combinatorial analysis has whittled done the anonymity set such that you have transaction in which all the inputs to a ring have been included in enough rings (taking into account all other inputs to those rings) that it is known that all those inputs have been spent, but it is not known which input is the spender to each of the said rings.
From there are ways to isolate which input is the spender.
1) If the last use of one the inputs is in a ring includes only other inputs that already reached their saturation (or any smaller set say just two of inputs that didn't reach saturation), then we know that said input is the spender (or know the spender is one of the smaller set of unsaturated inputs). Here is an example in chronological order:
Ring 1:
I0, I1, I2
Ring 2:
I0, I1, I3
Ring 3:
I0, I2, I3
Ring 4:
I1, I2, I3
Ring 5:
I2, I3, I4 ------> I4 is surely the spender
2) The second case I wrote was indeed difficult to parse because it was incorrect. I believe I was thinking about how to insure the overlapping in #1 doesn't occur and afaics that requires deciding which outputs must be mixed with which outputs before any ring with those outputs has been created. I apparently conflated those thoughts when trying to contemplate the explanation of a case where combinatorial analysis unmasks the anonymity such as #1 above.
The worst thing that can happen to me is that I'm "disappeared", but that's why the core team is seven strong:)
What if you "disappeared" and because of that the other 6 "retire" or "lose interest" and turn over control to "Gavinmike".
Much better the code was done and locked in stone. But I know that is very difficult to achieve at this experimentation stage.
Sufficed to say your "cooperation" would not go so far as to backdoor anything or use libs you otherwise would not have, correct?
That's why it's OPEN SOURCE.
Sometimes even that isn't enough:
https://www.schneier.com/blog/archives/2006/01/countering_trus.html