8 ms·
Zerocoin: making Bitcoin anonymous
- ezyang 14y agoHere 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 14y agoU[0,∞]
- ezyang 14y agoExpected wait time: infinity!
- krcz 14y agoNot really, it's silly to talk about expected value here. There's just no such distribution.
- anologwintermut 14y agoIf 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 14y agoCan I play as many times as I want?
- jerf 14y agoNo 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 14y agoAcknowledged. 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 14y agoCould 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 14y agoUsing 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 14y agoThe probability of any finite interval P(a, b) = 0
- jerf 14y agoThe 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 14y agoSounds 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 14y agoPick someone else's and repeat it?
- ezyang 14y agoThis 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 14y agoThis 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 14y agoAs 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 14y 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).
- joelrunyon 14y agoLink to the article (not the comments section) - http://blog.cryptographyengineering.com/2013/04/zerocoin-making-bitcoin-anonymous.html http://blog.cryptographyengineering.com/2013/04/zerocoin-mak...
- dragontamer 14y agoSince 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...
- mdelias 14y agoSince BTC is expected to be regulated like a currency Citation? The recent FinCEN statement [1] does not support your claim. [1] http://fincen.gov/statutes_regs/guidance/html/FIN-2013-G001.html http://fincen.gov/statutes_regs/guidance/html/FIN-2013-G001....
- johndevor 14y agoHowever, 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.
- IanCal 14y ago"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.
- dragontamer 14y agoI'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.
- speeder 14y agoI 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.
- johndevor 14y agoI 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.
- dmix 14y agoCryptography 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.
- corin_ 14y agoAgree 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.
- olivier1664 14y ago"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.
- tptacek 14y agoProjects like this are the one hard-to-deny good thing about Bitcoin: it's a very cool toy to play with.
- jasonlingx 14y agoCan't we just open a mtgox account, deposit and then withdraw?
- gojomo 14y agoMtGox 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.
- jevinskie 14y agoCorrect. 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!
- gizmo686 14y agoMathematically 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.
- deleted 14y ago[deleted]
- pjscott 14y agoThe article addresses this: > 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.
- emin_gun_sirer 14y agoTechnically, 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.
- deepblueocean 14y agoWhy? 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.
- emin_gun_sirer 14y agoBecause each coin transaction entails a 40KB zero knowledge proof. So a Satoshi will require 40*10^8 KB transferred for a 1BTC transaction.
- tlrobinson 14y agoAs 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.
- felipelalli 14y agoI did not like it.
- vessenes 14y agoI 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.
- brianberns 14y agoI know what Turing-complete means, but can you explain how the blockchain could become Turing-complete, and why that would be a bad thing?
- limmeau 14y agoIt would be inconvenient if the validity of a blockchain became undecidable, or even just NP-hard.
- jlgreco 14y agoI'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.
- nanofortnight 14y agoThe transaction verification language[1] is not turing complete, and only provides one bit of information (accept/reject transaction). Currently almost all transactions scripts just do public-key verification. [1]: https://en.bitcoin.it/wiki/Script https://en.bitcoin.it/wiki/Script
- anologwintermut 14y ago
- drakaal 14y agoIn 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. This seems like a huge flaw in the system.
- gizmo686 14y agoNo, 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.
- w-ll 14y agoWhat stops me from 'minting' zerocoins by selling them to myself? exchanged with gold? what?
- limmeau 14y agoWhen 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.
- w-ll 14y agoBut 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?
- DannoHung 14y agoThe only reason that you need anonymous financial transactions is because you believe that money is free speech. I disagree.
- cheez 14y agoAbsolutely not. I don't want my future employees knowing how much money I spend down at the strip club, for example.
- DannoHung 14y agoI'd like to see you tip a stripper with bitcoins.
- cheez 14y agoMaybe only a matter of time.
- jondtaylor 14y agoBusiness idea right here!
- rb2k_ 14y agoAnother option would be to just use an existing mixing service: https://en.bitcoin.it/wiki/Mixing_service https://en.bitcoin.it/wiki/Mixing_service Those services always reminded me of David Chaum's Mix Networks: http://en.wikipedia.org/wiki/Mix_network http://en.wikipedia.org/wiki/Mix_network)
- TazeTSchnitzel 14y agoThey're the same as the "laundering" services the article mentions.
- deleted 14y ago[deleted]
- stephan83 14y agoTotal coincidence: I registered zeroco.in last week. I was planning to use it for a lightweight bitcoin client I'm developing. What should I do?
- A1kmm 14y agohttp://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf, which is the fundamental piece of new cryptography which enables it to work, doesn't make any sense to me. 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.