[ianmiers]

An indefinitely growing list of spent transactions is the least of Monero's scaling issues. Monero doesn't scale to large anonymity sets.

Monero uses CryptNote's ring signature approach, which scales linearly with the number of coins you want to mix with. Want to fully mix 1,000 coins together? You need a 30kb transaction[0]. You chunk those coins into smaller mixing sets, but then they aren't fully mixed. In anything using this approach, your anonymity set is limited by what you can transmit across the network in any given transaction or a small set of transactions. I've never seen an exact proposal for mixing tx size and I'd be very interested to see one, but if it was more than 100 coins per tx I'd be surprised.

In ZCash, transactions are constant size and are fully mixed with every other coin in the current anonymity set.

Both approaches do have the indefinitely growing list of spent tokens issue. Which in practice means you need to move coins into a new anonymity set after e.g. 2^32 serial numbers and throw away the old coins and spent serial number list[1]. So there is an inherent limit on the maximal anonymity set you get out of any anonymous ecash scheme. Zerocash hits that limit. Due to its per transaction scaling issues, CryptoNote simply can't.

As a result, in ZCash, your coin is hidden amongst all the coins in the maximal anonymity set. In Cryptonote/Monero, it's hidden amongst a far smaller fraction of that set. In Monero, you are far less anonymous. All things being equal, you want to be more anonymous.

Of course, all other things are not equal. There are merits to both Zerocash and CryptNote on a technical level, but scalability isn't where CryptNote shines.

[0] Assume one group element per signature in the ring at 32 bytes per element. The real scheme is likely worse.

[1] There more sophisticated approaches that can be used.

[NobleSir]

> In Cryptonote/Monero, it's hidden amongst a far smaller fraction of that set.

Just wanted to point out that it's not that simple - what you are referring to is more like coinjoin level of anonymity. In Monero / Cryptonote, since one-time keys are used for each transaction, when you receive coins, they are in fact hidden among the entire set (which is the same anonymity level as Zerocash). The received coins can then be used as non-signers in "many" ring sigs, and so they have been possibly spent at any time for the remainder of the blockchain - the anonymity set for when a coin is spent is therefore "all" the ring sigs it is a member of, and since they remain on the blockchain indefinitely, this can therefore grow infinitely large.

Edit: I mean, it's fine to downvote, but at least providing a comment is helpful if you disagree.

[petertodd]

That is a good point; I should have clarified I was talking about transaction scalability in general, not _anonymous_ transaction scalability.

In any case, hopefully ZK-SNARKS continue to be optimized sufficiently that there's no question about which approach is better; I know you guys have done tremendous work on achieving that goal. Thank you!

[droffel]

> which scales linearly with the number of coins you want to mix with. Want to fully mix 1,000 coins together? You need a 30kb transaction

Actually, it does not scale linearly, it scales logarithmically in the worst case.

If you create a transaction to send 1543XMR, it splits it into 4 pieces: 1000, 500, 40, and 3, respectively. Each of these transactions are put into a ring signature, where the other transactions in the ring are selected from the pool of all other transactions of the same size, since the creation of the network. I'm not sure why you think that it scales linearly on the amount of coins sent.

Edit: Unless you mean, "to achieve perfect anonymity, you need to mix your coins with every other transaction of the same size, which scales linearly with the total number of transactions performed since the start of the network", in which case, yes. It is linear. But thats serious overkill, theres no reason to have a ring size that large.

[ianmiers]

Yes, I meant perfect anonymity.

If we consider imperfect anonymity, we need to consider more than the size of the anonymity set, we need to consider how likely it is a given coin in the anonymity set is the actual one we are hiding. This is a bayesian thing that depends on that attackers prior knowledge. For many coins it may be vanishingly close to zero. Which means they don't really contribute to the anonymity set. Which means you can end up with a large looking anonymity set that is equivalent to a perfect anonymity set of say 5 coins.

How big is the anonymity set for a given CryptoNote transaction? You might think it 1) clearly is at least the size of all the coins in the tx and 2) actually it's the union of those coins anonymity sets. But what are the probabilities? I don't know. But consider a few possible issues.

If you sample the coins in the mixing set for your tx uniformly from the whole blockchain, than many of them will be very old, but the actual coin you are spending is likely new. This also applies to the sets you are taking the union of. Couple this with other issues such as long term intersection attacks, and it gets very hard to say how much anonymity you really have. Especially because we don't know what techniques the companies that are doing coin tracing have and more significantly, what third party data they are correlating with beyond just the blockchain. Perfect anonymity and very large anonymity sets is the best defense we have against this stuff.

[plasticmachine]

Unsurprisingly, there exists research by the Monero Research Lab highlighting temporal association attacks and other possibilities.

https://lab.getmonero.org/pubs/MRL-0001.pdf https://lab.getmonero.org/pubs/MRL-0004.pdf

As to your last statement: even if the supposition is that the true signer is the most recent output on the blockchain, that is nothing but an unprovable supposition, which means that Monero enables plausible deniability at the very least.

Since transactions are both unlinkable (for any two outgoing transactions it is impossible to prove they were sent to the same person) and untraceable (for each incoming transaction all possible senders are equiprobable) the anonymityset continues to grow, which makes the privacy risk cryptographically negligible.

[plasticmachine]

I don't understand your terminology. What do you mean "mix 1000 coins together", and what is the use-case there?