Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Zerocoin: making Bitcoin anonymous

blog.cryptographyengineering.com

Post reply on HN
Print view View original

71–80 of 86 posts

Re: Zerocoin: making Bitcoin anonymous

#71

Post by judofyr »

drakaal wrote: post #54
gizmo686 wrote: post #49

Earlier quoted context omitted.

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…

So you counterfeit the Zero Coin and trade them for Bit Coins and the system breaks. I am not buying that they are impossible to forge. Especially if they are computationally easy to create.

On what basis are you claiming that they are not impossible to forge? You can check the crypto yourself:

http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf

Re: Zerocoin: making Bitcoin anonymous

#73

Post by A1kmm »

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 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.

Re: Zerocoin: making Bitcoin anonymous

#74

Post by gizmo686 »

Flenser wrote: post #70
davmre wrote: post #53

Earlier quoted context omitted.

> 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…

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 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.

Re: Zerocoin: making Bitcoin anonymous

#75

Post by gizmo686 »

w-ll wrote: post #68
limmeau wrote: post #59

Earlier quoted context omitted.

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?

You are paying the bitcoin to whowever redeams the zerocoin. Until someone redeems the zerocoin, no one has the bitcoin that was used to mint it.

Re: Zerocoin: making Bitcoin anonymous

#76

Post by jerf »

waps wrote: post #42
jerf wrote: post #25

Earlier quoted context omitted.

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.…

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, t…

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.

For an analysis of this and some other interesting things, see the Dirac delta (psuedo-)function: http://en.wikipedia.org/wiki/Dirac_delta_function

Re: Zerocoin: making Bitcoin anonymous

#77

Post by tlrobinson »

emin_gun_sirer wrote: post #33

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.

Re: Zerocoin: making Bitcoin anonymous

#78

Post by drakaal »

judofyr wrote: post #71
drakaal wrote: post #54

Earlier quoted context omitted.

So you counterfeit the Zero Coin and trade them for Bit Coins and the system breaks. I am not buying that they are impossible to forge. Especially if they are computationally easy to create.

On what basis are you claiming that they are not impossible to forge? You can check the crypto yourself: http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf

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.

Re: Zerocoin: making Bitcoin anonymous

#79

Post by anologwintermut »

vessenes wrote: post #45

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…

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.

Re: Zerocoin: making Bitcoin anonymous

#80

Post by anologwintermut »

Flenser wrote: post #70
davmre wrote: post #53

Earlier quoted context omitted.

> 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…

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 zero knowledge proof ensures no one learns r.

Post reply on HN