As far as I understand the posting, this depends on the total minted Zerocoins. Since you can not tell with any certainty that a specific Zerocoin is already redeemed ( except if all are redeemed, more on that later), the probability that a specific Zerocoin belongs to you is 1/n, where n is the number of addresses which have ever generated Zerocoins.
However, there are some assumptions in the argument, most importantly that the number of Zerocoins is always rising. Dropping this assumption ( and mentioning that I did not double check my argument), the probability that the last redeemed Zerocoin is also the last minted is 1/min( n(t) + m(t)), where n(t) denotes the number of addresses which generated Zerocoins since some time t and m(t) is the number of not redeemed Zerocoins at t. At least from the perspective of an outside observer who does not hold any Zerocoins. In the case of an attacker with f Zerocoins the probability would be
P=1/min(n(t)+m(t)-f).
The worst case is then, that your adversary holds all Zerocoins just before you mint your Zerocoin. And a attacker with large resources can continue to mint Zerocoins until he runs out of funds, simulating a working anonymising ecosystem. Therefore you should wait until a plausible attacker runs out of funds, that is for a attacker with total funds f0 (using the above formula at the time of your minting of a coin t=0 with m(0)=f)
P0 > 1/(n(t) - (f0-m(0)).
where PO is a parameter describing your desired anonymity level. And therefore you should wait for the minting of
n(t)> 1/P0 + (f0 - m0)
Zerocoins before you redeem your originally minted one. Simple corollary, you should mint when there are many coins in existence and you should pick poor enemies.
> the probability that a specific Zerocoin belongs to you is 1/n
I think you're missing the subtlety that the parent was trying to get at. Imagine that everyone redeemed their Zerocoins exactly five minutes after minting them; it'd be trivial to match up which coin was being redeemed. Now obviously that'd be stupid, so instead let's say you choose when to redeem your Zerocoin randomly, by sampling a waiting time from some distribution p(t). This makes it harder for the attacker to recover which coin is yours, since instead of just counting backwards five minutes, they now only have a posterior probability distribution spread over a range of possible minting times (note this distribution is really just a flipped version of p(t)). But that still gives them some information. The only way for them to have a truly uniform distribution across all possible minting times is if you had used a truly uniform distribution across all waiting times, but as pointed out below, there is no such distribution! So no matter how you choose your waiting time, your attacker will get some information out of it; the probability will never be exactly 1/n.
> The worst case is then, that your adversary holds all Zerocoins just before you mint your Zerocoin. And a attacker with large resources can continue to mint Zerocoins until he runs out of funds, simulating a working anonymising ecosystem.
Given that Bitcoin's security already assumes that an attacker controls no more than 49% of the network, it seem reasonable to me to make a similar assumption for ZeroCoin. But that is a good point: Zerocoin's anonymity depends on having enough users that you can safely "hide in the crowd", and that's not necessarily something that's easy to verify from within the network (though as you point out, it can work if you have a bound on your attacker's potential funds).
I don't understand how once the zero coin's serial number is revealed in the spend transaction it can remain anonymous. Can't you then go back and test previous mint transaction to see if it was for that serial number? If you're doing it continuously, so you keep a record of which mint transactions you know have been spent it would reduce the workload.
The coin is a commitment to the serial number. Specifically the coin is g^s * h ^ r where g and h are generators of a group where the discrete log problem is hard, s is the serial number and r is some random number known only to the minter. If you only reveal the serial number and not the randomness, there is no way to know which coin it came from. In fact for any coin c there exists an r' such that c=g^s h^r'. As such, if you only know the serial number and not random r, it is equally likely to be any coin.
The serial number is never revealed. You provide a zero knowledge proof that you know a serial, and that that serial has never been spent. This proof is currently a major issue in zerocoin, because it is prohibitivly large.
However, there are some assumptions in the argument, most importantly that the number of Zerocoins is always rising. Dropping this assumption ( and mentioning that I did not double check my argument), the probability that the last redeemed Zerocoin is also the last minted is 1/min( n(t) + m(t)), where n(t) denotes the number of addresses which generated Zerocoins since some time t and m(t) is the number of not redeemed Zerocoins at t. At least from the perspective of an outside observer who does not hold any Zerocoins. In the case of an attacker with f Zerocoins the probability would be P=1/min(n(t)+m(t)-f).
The worst case is then, that your adversary holds all Zerocoins just before you mint your Zerocoin. And a attacker with large resources can continue to mint Zerocoins until he runs out of funds, simulating a working anonymising ecosystem. Therefore you should wait until a plausible attacker runs out of funds, that is for a attacker with total funds f0 (using the above formula at the time of your minting of a coin t=0 with m(0)=f) P0 > 1/(n(t) - (f0-m(0)). where PO is a parameter describing your desired anonymity level. And therefore you should wait for the minting of n(t)> 1/P0 + (f0 - m0) Zerocoins before you redeem your originally minted one. Simple corollary, you should mint when there are many coins in existence and you should pick poor enemies.