Here is a puzzle for HNers. Suppose that I am a user who wants to anonymize some Bitcoins, and I am willing to wait expected time N before redeeming my Zerocoins. What is the correct probability distribution for me to pick my wait time from?
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.
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).
The zero knowledge proof ensures no one learns r.
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.)
On the other hand... It would be secure :) never withdraw. Anonymity through one way function/flow.
Edit: The helpful explanation linked in a comment on the question you linked is defective because it applies to all continuous probability distributions.
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.
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.)
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.
For an analysis of this and some other interesting things, see the Dirac delta (psuedo-)function: http://en.wikipedia.org/wiki/Dirac_delta_function
No, why do you think so?