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.
I like seeing proposals like this that use Bitcoin as essentially a protocol layer (and in this case value store).
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.
I'm not sure how it would happen, but if you could get miners to perform arbitrary computation for you, as a consequence of processing zerocoin transactions, then people might decide to abuse that and generate tons of otherwise unnecessary transactions.
Non Interactive Zero knowledge proofs as used in that paper are just a set of mathematical equations and values that you check the equations hold for. They are not even close to turing complete.
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?
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 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.
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.
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)) = ...
>Edit: The helpful explanation linked in a comment on the question you linked is defective because it applies to all continuous probability distributions.
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.
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.
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.
I think that politically this is a awful time for that.
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.
Cryptography driven anonymity or subversion is not in need of PR sensitivity or timing. It is a technological progression that has been happening for decades and will continue on it's own rapid pace.
In this context of Zerocoin, they released a technology research paper. It should be treated as such. Not a company PR dept.
Agree or disagree with peoples reactions, agree or disagree with the idea that research papers should be delayed for these reasons, but don't just pretend like research, press and progress are unrelated.
I disagree. I think it is a good time to do this because it is still largely unregulated and not well understood. The media is already reporting this currency as being "crypto" or "anonymous" -- so Zerocoin is really nothing new to the media. They largely don't know the difference between pseudo-anonymity and the real thing.
"the paper mention of drug deal does not help with that".
I agree, a youporn transaction will be a good marketing example: legal but ashaming. A donation to an opposition party in a dictatorship country is also a good example.
Technically, this is very cool work. But one thing the paper overlooks is divisibility. How does one make change with zerocoin? It appears that the trapdoors allow only a whole coin to be spent, with no recourse for spending a partial coin. Needless to say, non-divisibility will make a practical deployment difficult.
As I understand it you basically deposit and withdrawal BTC in the ZeroCoin ether (much like a mixer service) using standard denominations, then you make you actual arbitrary denominated transactions with your new Bitcoins.
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.
Why? Why not simply set a minimum quantum for transactions in Zerocoin, like the penny or the satoshi? Or why not redeem the Zerocoin for a Bitcoin, which is divisible and which would be free of (traceable) history.
Since BTC is expected to be regulated like a currency, wouldn't participating in Zerocoin be basically money laundering?
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...
Money laundering only applies when the money is obtained illegally in the first place. Also, Zerocoin doesn't have a network to itself, it functions within the existing bitcoin block chain.
Bitcoin explicitly allows for creating alternate ways of defining who can spend a coin, this is simply one such alternate way.
Think of bitcoin as the bank account, and zerocoin as ATM withdrawals of cash. It's a leaky metaphor, but it fits.
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.
However, an administrator or exchanger is an MSB under FinCEN's regulations
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.
I'm more interested in: "An administrator is a person engaged as a business in issuing (putting into circulation) a virtual currency, and who has the authority to redeem (to withdraw from circulation) such virtual currency."
If you participate in the Zerocoin network, you can therefore issue Zerocoins (in exchange of bitcoins), and redeem Zerocoins for bitcoins.
"Would they not try to claim that using Zerocoin is, in effect, making you an independent exchange?"
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 live in America, you are subject to American law, regardless of the technicalities of the technologies you employ. You are expected to follow the law and the spirit of the law.
MtGox knows who you are, and is not a secret underground operation thumbing its nose at The Man. Over the long run, you should consider them as transparent as any major, bailed-out bank.
Correct. Zerocoin is a way to make it mathematically difficult (read: likely infeasible in practice) to de-anonymize instead of trusting a central party. Cool stuff!
Mathematically difficult does not mean infeasible in practice. Not even mathematically impossible means infeasible in practice. Having a solid theory is a good start, but a minor oversight in the implemantation could doom the system.
> 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.
In order for this scheme to work ZeroCoins would have to have the same computational creation requirements as a bit coin. This would mean that there would always be fewer zero coins than bit coins and those coins would have to be mined.
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.
No, ZeroCoins are computationally easy to create. The concept is that you easily create a zerocoin, and then 'buy' it using bitcoins. When you buy the zerocoin, you create a bitcoin transaction, so you have to spend the corrosponding amount of bitcoins. When you want to redeem a zerocoin, you have to prove that you bought one.
In this way, zerocoins are a lot like gold notes. They are cheap to create, but have value becuase they can be exchanged with gold/bitcoins, which have value and are hard to create. Unlike goldnotes however, zerocoins should be impossible to forge.
Things which are computationally easy to create are possible to brute force. Bit Coin only works because it is computationally hard to create them. At some point (50 years from now) Bit coins will not be as impossible to compute as they are now, but the exponential increase in difficulty to compute new ones will limit the likelihood that the advances in technology will catch the computational requirement.
It doesn't matter that the Zero Coin is computationally easy to create, because the Zero Coin doesn't have any value until it's embedded in a Mint transaction in the block chain. Mint transactions will only be accepted by the network if an equivalent value in Bitcoin is burned in the same transaction.
When you Mint a zerocoin, you spend a BTC. When you redeem a zerocoin, you receive a BTC. The collective of miners verifies that you don't get rich doing so.
But how do you know I just dont "sell it" to a btc address I already own? Or maybe I dont understand what you mean by spend BTC? Paid to who? The person "minting" coins, which is not a POW system?
The Mint transaction, which becomes part of the block chain, establishes consent that the given bitcoin address owns one BTC less and that simultaneously the given Zerocoin becomes valid.
Minting takes place within the block chain, unlike Dollar exchanges on MtGox, which are not directly visible as such in the block chain.
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.