6 ms·

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 Zerocoin

by ezyang 13y ago

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?

lmgftp 13y ago
U[0,∞]
- ezyang 13y ago
  Expected wait time: infinity!
  - krcz 13y ago
    Not really, it's silly to talk about expected value here. There's just no such distribution.
  - anologwintermut 13y ago
    If you believe that then I have a lottery ticket to sell you. http://en.wikipedia.org/wiki/St._Petersburg_paradox http://en.wikipedia.org/wiki/St._Petersburg_paradox
    - krcz 13y ago
      Can I play as many times as I want?
- jerf 13y ago
  No such thing: http://math.stackexchange.com/questions/14777/why-isnt-there-a-uniform-probability-distribution-over-the-positive-real-number 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 http://www.mathpages.com/rr/rrtoc.htm (But it is quite a ways in there.)
  - lmgftp 13y ago
    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.
  - anonymoushn 13y ago
    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.
    - krcz 13y ago
      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.
    - lwat 13y ago
      The probability of any finite interval P(a, b) = 0
    - jerf 13y ago
      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.)
im3w1l 13y ago
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.
edmundhuber 13y ago
Pick someone else's and repeat it?
- ezyang 13y ago
  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.
davmre 13y ago
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_distribution#Positive_and_given_mean:_the_exponential_distribution 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!
yk 13y ago
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.
- davmre 13y ago
  > 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).

by ezyang 13y ago

lmgftp 13y ago

U[0,∞]

ezyang 13y ago
Expected wait time: infinity!
- krcz 13y ago
  Not really, it's silly to talk about expected value here. There's just no such distribution.
- anologwintermut 13y ago
  If you believe that then I have a lottery ticket to sell you. http://en.wikipedia.org/wiki/St._Petersburg_paradox http://en.wikipedia.org/wiki/St._Petersburg_paradox
  - krcz 13y ago
    Can I play as many times as I want?
jerf 13y ago
No such thing: http://math.stackexchange.com/questions/14777/why-isnt-there-a-uniform-probability-distribution-over-the-positive-real-number 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 http://www.mathpages.com/rr/rrtoc.htm (But it is quite a ways in there.)
- lmgftp 13y ago
  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.
- anonymoushn 13y ago
  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.
  - krcz 13y ago
    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.
  - lwat 13y ago
    The probability of any finite interval P(a, b) = 0
  - jerf 13y ago
    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.)

im3w1l 13y ago

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.

edmundhuber 13y ago

Pick someone else's and repeat it?

ezyang 13y ago
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.

davmre 13y ago

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_distribution#Positive_and_given_mean:_the_exponential_distribution 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!

yk 13y ago

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.

davmre 13y ago
> 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).