This would depend on the distribution of times at which other people are minting and redeeming Zerocoins ... but under reasonable assumptions, you'd probably want to go with something like the exponential(1/N) distribution, since that's the maximum entropy distribution on [0,∞] having mean N (http://en.wikipedia.org/wiki/Maximum_entropy_probability_dis...). This has the somewhat surprising property that the most likely time for you to redeem a Zerocoin is immediately after minting it!

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 zero knowledge proof ensures no one learns r.

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.

Sounds like a job for security through obscurity. I.e. any distribution you want that is unique for you and you never tell anyone about.

U[0,∞]

No such thing: http://math.stackexchange.com/questions/14777/why-isnt-there...

Get far enough into Reflection on Relativity and the author makes some interesting observations based on this tidbit: http://www.mathpages.com/rr/rrtoc.htm (But it is quite a ways in there.)

Could you point out the problem with such a distribution? It isn't immediately obvious that I cannot satisfy both axioms.

Edit: The helpful explanation linked in a comment on the question you linked is defective because it applies to all continuous probability distributions.

The key is the restriction that in the uniform distribution the probability density must be the same at all points, and if it covers infinity, it can be neither 0 nor anything greater than 0 if it's going to sum to 1. It's perfectly legal to have a probability distribution across all the reals. In fact most if not all of the well-known ones are; the Gaussian/normal distribution is defined on all reals, for instance. But it varies, and the integration from negative infinity to positive infinity sums to 1.

In fact everything that we refer to as "normal" distributions in the real world technically aren't, as the finite nature of the universe means the probability of the extremes is simply zero (give or take being totally wrong about the nature of the universe in which case all bets are off anyhow) rather than very, very small, and in many cases there's a sharp cutoff at 0, or some other arbitrary boundary, which a true normal distribution doesn't have. But it's often still the best mathematical approximation, with negligible error. (... until it isn't.... caveat emptor.)

Why isn't the answer P = { Inf -> 1, otherwise 0 } ?

Axiom 1: P(E) elem N => P(E) >= 0, for all E

Trivially satisfied

Axiom 2: P(Omega) = 1

Satisfied: Omega = N { Inf } elem N

Axiom 3: Sigma additivity. Trivially satisfied since it either includes { Inf } or it doesn't, making the outcome 0 or 1.

Where is the problem ?

I think it's pretty clear that this is the only possible solution, because since N is not closed, there is no way to keep a uniform density other than 0.

This does not seem like it's a very useful solution, but it does seem to satisfy the axioms.

In addition to anonymoushn's correct point, I would also observe that even if we do treat infinity as a specific real number, the integration of a function zero at everywhere except one specific point from -inf to +inf is still 0. And further if we are treating it as a real number, you've now violated the uniformity constraint; P(0) != P(inf), therefore it is no longer a uniform distribution, the thing you are putatively building.

For an analysis of this and some other interesting things, see the Dirac delta (psuedo-)function: http://en.wikipedia.org/wiki/Dirac_delta_function

Infinity isn't a positive real :(

In most definitions I've seen of it, it is. In fact, it's a natural number.

Using uniform distribution definition from Wikipedia ("all intervals of the same length on the distribution's support are equally probable") we get P(X \in [0,1)) = P(X \in [1, 2)) = P(X \in [2, 3)) = ...

By countable additivity P(\Omega) = P(X \in [0, \infty)) = P(X \in [0, 1)) + P(\X \in [1, 2)) + ... = P(X \in [0, 1)) + P(X \in [0, 1)) + ...

And this evaluates to 0 if P(X \in [0, 1)) = 0 and to \infty if P(\X \in [0, 1)) > 0.

>Edit: The helpful explanation linked in a comment on the question you linked is defective because it applies to all continuous probability distributions.

No, why do you think so?

It contains the sentence "For any distribution, the sum of probabilities always equals 1" without the caveat that the sum is of a countable number of probabilities. It applies to every continuous distribution using the same argument, but with "the sum across all naturals" replaced with "the sum across the appropriate universe."

"the sum across the appropriate universe" for Reals is an integral. An integral can go from -Infinite to Infinite and still equal 1. This is the reason, for instance, why Zeno's Paradox of movement doesn't really forbid all movement.

This comment is more or less irrelevant. The third axiom of probability is about sums of countably many terms: http://en.wikipedia.org/wiki/Axioms_of_probability#Third_axi...

The probability of any finite interval P(a, b) = 0

Acknowledged. Mostly a facetious comment, as any known distribution could be found (over infinite time) and you'd only become pseudononymous (which is exactly what the original comment wouldn't like!)

On the other hand... It would be secure :) never withdraw. Anonymity through one way function/flow.

Expected wait time: infinity!

If you believe that then I have a lottery ticket to sell you. http://en.wikipedia.org/wiki/St._Petersburg_paradox

Can I play as many times as I want?

Not really, it's silly to talk about expected value here. There's just no such distribution.

Pick someone else's and repeat it?

This would not work; suppose someone was using the point distribution "wait one hour and then withdraw", then it would be trivial to deanonymize Zerocoins.