> Ring signatures actually are zero-knowledge proofs. I think, technically, they're something like witness indistinguishable (non-interactive) zero-knowledge proofs of membership?


There exist zero-knowledge implementations of ring signatures. Not every implementation of ring signatures are zero-knowledge. AFAIK anyway. If you have a link, I'd read it.


> I don't hugely understand what you meant by > any system built without zero-knowledge protocols is leaking info, but I guess you're concerned about metadata? This is actually a topic I've wanted to do a big collection of info on for a while:
What is even revealing about Monero transactions at this point? Timing analysis?


For one thing, yeah, timing. It may seem like a trivial issue, but if you can pin a transaction down to within +/- 2 minutes with its block height, you have *quite* a bit of knowledge of that transaction. It makes the knacccattack (churning) particularly effective: not only can an exchange determine the purchasing habits of its customers, it can determine what time of night they prefer to buy their hentai pillows with monero. Fact of the matter is unless a protocol is provably zero knowledge (either perfectly zero knowledge or statistically zero knowledge) then a non-trivial amount of information is made available *by definition* (otherwise you could have proven your protocol was zk in the first place).


You or I may not be clever enough to figure out how to piece that information together, but someone might be clever enough, or an advanced machine learning algorithm crawling the Monero blockchain may be clever enough in a few years.


> 'Intersection sets' (where a given sender and recipient appear together more often than expected) are an often cited issue with 'mixing' schemes, but actually don't affect monero (as address/public key reuse is impossss) so you can emphasize that somewhere.


Intersection sets are interesting. So are techniques for solving nonograms and sudoku. I fear the day that Grobner bases can be brought to bear against a blockchain.




>Are the attacks outlined in AM's monerolink inherent to passive mixing schemes? Is the distribution that transactions get picked from fixed now?


I don't know yet, but that paper is on the top of my todo. AFAIK the distribution is still triangular, but "fixed" implies there is something wrong with our current method. FWIW, there is a game-theoretic thing happening, where if an eavesdropper assumes that transactions follow some "true" distribution, a malicious user could use that assumption to convince the eavesdropper that another ring member was responsible for a transaction, by selecting an innocent and unaware ring member that is an outlier with respect to the assumed distribution. Any statistical method relies very strongly on things like the central limit theorem, which completely ignore human behavior and game theory.


So, if you decide you want to write some wallet software that selects a distribution optimally, somehow, then an eavesdropper can inspect that method, and come up with a statistical rule for determining the "true" spender in a ring... but then some malicious user can turn around and start throwing false positives and negatives on purpose for fun.


> Are these sort of 'what people do in the future can directly influence the anonymity that I, following the protocol exactly, can get' problems inherent in passive mixing protocols?


Replace "passive mixing protocol" with "probabilistic mixing protocol with revocable anonymity" and the answer, I think, is yes, due to revocable anonymity. And without revocable anonymity I believe double-spend detection is a different animal (if even possible).


Keep in mind, though, Cryptonote/monero isn't really a mixing protocol, passive or otherwise, because there is a probabilistic aspect to it, which is why I got semantic above. In a mixing protocol (say an old school vanilla bitcoin tumbler, not a shapeshift) you are playing a big pea-and-cup game, but an observer can watch every move very carefully and know factually, after a sufficiently long (even if an infeasibly long) period of time of computation, where each little pea ended up. As a consequence, there isn't really anonymity in a mixing protocol (subject to the constraint of using reasonable computers to search a reasonably sized set of combinatorial possibilities). So your question is kind of self-defeating unless you allow the mixing to only be discernible up to probability. In Monero, an observer might be able to minimize their uncertainty about ownership of some transactions, but they can't pin every transaction down with zero uncertainty. The best they can do is put a probability distribution on ownership.




>How do we define them? How do we minimise the damage? How do we parametrise the leakage?


Good question.


>Quantum proofing: what do you actually want to do here? This might be trivial from both a stealth address and pedersen commitment PoV; less so from a ring signature perspective. But that would be a really cool research avenue (is it possible??? Do you have any quantum crypto friends??? I would super work on this :D).


Secretly I want Monero to be the first quantum-proof cyptocurrency. Publicly, I have sincere doubts if PQC will ever be lightweight enough to build a decentralized blockchain that is remotely reasonably sized. All my crypto friends, quantum or otherwise, with a few exceptions, work at NSA or have zero interest in currency, unfortunately.


> You can easily make addresses much shorter.


Do tell.


> There are ways that you won't even have to communicate a new 'public viewing key' alongside every transaction. This reduces address size even more! (but only works for parties who have transacted with one another before


I will look into this.


> Sublinear ring signatures! A lot of these (actually, all that I can find!?) depend on a CRS (I've been told off for this, but i'm using CRS here to mean common reference string. This is the reason for ZCash's trusted setup -- pretty much there are some very_necessary_parameters that can only be constructed with knowledge of very_dangerous_information). There's a result that NIZKs are impossible in the standard model, so choices are the above, or use the random oracle model (as monero does now!)


That is mostly my understanding also, and trusted setups need to be avoided in Monero, which is why I'm looking deeply into ring sigs, their history, their variations.


> block size is proportional to key size and key size is proportional to privacy. What does this mean? Do you mean signature size is proportional to ring size? Or do you mean security is proportional to key size? If it's the former, absolutely - sublinear ring signatures !! If it's the latter, I don't recommend making the system less secure as a way to reduce bloat!!!!


1) Block size is proportional to key size: I mean if you double the size of keys, you will double the average block size.


2) Key size is proportional to privacy: To encrypt any amount of information with perfect secrecy requires a key with the same "size" as that information. I mean this quite literally and abstractly: the more information you wish to encrypt, the larger the keys necessary to keep that information perfectly secret. I'm not saying we should reduce security to improve bloat, I am merely recognizing the trade-off between the two.