Zerocoin: making Bitcoin anonymous
blog.cryptographyengineering.com
blog.cryptographyengineering.com
At the very least, the authors have made the formulation so unclear that you could start to suspect the authors were deliberately trying to obfuscate it. They define a function ZKSoK(c, w, r), and it would make sense not to use c, w, and r to mean anything else in the short definition of the construction. However, the authors chose to also use c for the hash used to make it non-interactive, and r_i for a series of random numbers. Using the same variable name for two different things makes it hard to work out what they mean, but as far as I can tell, the c that is the function parameter is public knowledge, w can be computed from public information, and ZKSoK does actually depend on the r that is the function parameter, and the validation of the proof does not actually check that S is correct (c is computed as c <- g^S * h^r mod p, but it is useless if you can spend a zerocoin using any arbitrary S that doesn't actually correspond to any real c) as it claims.
In the 15 page version, they claim that the proof of the soundness of the ZKSoK proof can be found in "the full version of this paper" - perhaps that text makes things clearer, but they don't seem to provide a reference to it.
40KB anything is not going anywhere near the blockchain soon; this is going to be a no-go for the dev team and miners.
There are also a bunch of ancillary questions, like can these zero knowledge proofs (presumably non-interactive ones) be combined up with the rest of the blockchain to be turing-complete? Also a no-go.
Anyway, this is cool. Given current Bitcoin decision making processes, I would expect it would need a solid year of great adoption in some sort of side-car process before it had a shot at main blockchain integration, and even then, it would have to get drilled down to 1 or 2k of data max.
Currently almost all transactions scripts just do public-key verification.
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?
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.
Bitcoin is still largely unregulated, and this allow for all sorts of innovation, yet the media is already scaremongering around because it is "anonymous" and used for laundering and drug dealing.
If Zerocoin attracts true media attention, then you will get a political firestorm of people claiming that someone is making Bitcoin even worse for nefarious purposes. And of course, the paper mention of drug deal does not help with that.
In this context of Zerocoin, they released a technology research paper. It should be treated as such. Not a company PR dept.
There can be multiple denominations of ZeroCoins, but it's in everyone's interest for the set of denominations to be small, otherwise you lose anonymity.
If that is the case, participating in the Zerocoin network itself would be a crime. I don't think this is going to go anywhere. And if it does, then hope that the Secret Service doesn't catch you even touching this stuff...
Since BTC is expected to be regulated like a currency
[1] http://fincen.gov/statutes_regs/guidance/html/FIN-2013-G001....
Would they not try to claim that using Zerocoin is, in effect, making you an independent exchange? Or are you only an exchanger when going from Bitcoin to USD?
An exchanger is a person engaged as a business in the exchange of virtual currency for real currency, funds, or other virtual currency.
There is this clause, but it only refers to businesses.
Might be difficult, there's no market there. One Zerocoin is one Bitcoin in value by definition. It's not an exchange to convert dollars into cents, so it would be hard to argue this.
If you participate in the Zerocoin network, you can therefore issue Zerocoins (in exchange of bitcoins), and redeem Zerocoins for bitcoins.
Since withdrawing money from an ATM is not money laundering, it works.
What makes it anonymous is that anyone can now start a 'bitcoin account' with purely unconnected zerocoins without any AML paperwork to go through just like a real life equivalent of dumping stacks of cash at your no questions asked numbered bank account service.
Its like any other law, except the Secret Service is especially hard on money launderers.
> For the more paranoid, there are services called 'laundries' that take in bitcoins from a whole bunch of users, mix them up and shuffle them back out. In theory this makes it hard to track your money. Unfortunately, laundries suffer from a few problems. First, they only work well if lots of people are using them, and today's laundries have relatively low volume. More importantly, you're entirely dependent on the honesty and goodwill of the laundry itself. A dishonest (or hacked) laundry can steal your coins, or even trace its inputs and outputs -- which could completely undermine your privacy.
Those services always reminded me of David Chaum's Mix Networks: http://en.wikipedia.org/wiki/Mix_network)
I disagree.
If the zero coins were not the same difficulty to create then you could just create zero coins and trade them for bit coins anytime you wanted.
This seems like a huge flaw in the system.
Minting takes place within the block chain, unlike Dollar exchanges on MtGox, which are not directly visible as such in the block chain.
I am not buying that they are impossible to forge. Especially if they are computationally easy to create.