Zerocash: Decentralized Anonymous Payments from Bitcoin [pdf]
zerocash-project.org
zerocash-project.org
While the CRS ZK-SNARK stuff used for ZeroCash is very exciting technology, the cryptographic assumptions are very new and kinda sketchy. The fact that there is a trusted initialization is unfortunate, especially since compromise of the initialization results in unbounded and undetectable inflation (well I suppose you can detect it once a single altruist ends up with more coins than ought to exist!). ... though it has implications which go far beyond transaction anonymity.
The Bytecoin approach is based on much simpler cryptography— a schnorr ring signature in the curve25519 group. The anonymity it provides is theoretically more limited— sort of like a CoinJoin where even ofline people or even already spent coins can be joined with you—, but because it doesn't required gigabytes of signing keys or tens of seconds of computation to sign it might be more anonymous in practice just due to being easier to use. (Oh yea, and did I mention, it's already in use so at the moment it's infinitely more private! :) )
So far all of these anonymous systems have a number of interesting limitations in common. For example, none of them support any kind of pruning so a verifying node has state that grows forever— as compared to Bitcoin where if you're just verifying new blocks (as opposed to helping initialize new peers) you can forget the old state... e.g. right now a Bitcoin full verifier technically only needs about 300MBytes of storage. So this privacy stuff comes at a rather extreme cost. I've suggested some ways to improve this (basically expiring old coins), but they reduce the anonymity set and have some usability tradeoffs.
In any case, it's certantly better to see things like ZeroCash and Bytecoin being worked on... I'm really skeptical about the wisdom of splitting up the crypto-currency adoption network effect just to introduce some new transaction features. But certantly doing it with substantive new features is way better than just-another-worthless-clone. ... especially when there is running code and not merely a whitepaper. :)
>I'm really skeptical about the wisdom of splitting up the crypto-currency adoption network effect just to introduce some new transaction features.
As someone who's been working on cryptocurrencies, I think that most of the Internet of Tomorrow is going to be driven by a set of cryptocurrencies that all do different things, following some of the primary principals of Unix. Storage and computation, for example, are services that I think will eventually find homes in cryptocurrency. Already you see things like MaidSAFE and Ethereum attacking these problems. But you also have problems that need to be solved like DNS routing, public random numbers, time synchronization where the modern solution involves centralized services.
Right now, there's not much that allows cryptocurrencies to communicate, but that's quickly changing and should move forward much more in the next 5 years. Merge mining, colored coins, and decentralized inter-currency exchanges are just the beginning.
There are a lot of problems that cryptocurrency has the potential to solve, and I think it's foolish to hope that a single cryptocurrency that will effectively solve all of them. But I also don't think that having 12 or 200 different cryptocurrencies means that any individual currency needs to be made weaker. Merge-mining is a good start, but I think that inter-currency cooperation and protection will continue to get better.
Can you really say that Zerocoin was the first of its kind when it still doesn't actually exist? There is a crypto library that implements the blind accumulator but thats it. Not a usable system. Bytecoin and CoinJoins are things you can use today.
The anonymity offered by systems that exist is inherently better than that offered by ones that don't exist, I think. :) The Bytecoin anonymity is better than Zerocoin's too, even ignoring the whole existence part.
(FWIW, I (and others) were posting about CoinJoin a long time before Zerocoin was a twinkle in anyone's eye. But the suddenly popularity of Zerocoin made me realize that I needed to attach a compact and snazzy _name_ to the idea if I wanted people to pick it up and run with it. Doing so appears to have been a pretty massive success. ... I worry a lot about people paying too much intention on someday-ware and as a result not going out and building things that we can use sooner than someday.)
> As someone who's been working on cryptocurrencies, I think that most of the Internet of Tomorrow is going to be driven by a set of cryptocurrencies that all do different things, following some of the primary principals of Unix
Well, what do I know. ::shrugs::
To me "driven by a set of cryptocurrencies that all do different things" doesn't sound like unix it sounds like saying that "in the future computer communications will be enabled by orthogonal networks that each do different things".
I think currencies just like communications networks benefit from Metcalf's law... So it seems silly to me to artificially divide up the world into separate currencies just to get different transaction features. It's technically unnecessary. There is, I think, an argument for dividing things up for different economic approaches— e.g. freicoin's inflationary currency— but for transactional purposes, it just isn't necessary. You can have one cryptocurrency being used on many different transaction networks (including decentralized ones). And I think that if in the future these things continue to be used at all, we'll find ways to not create artificial friction where it can be avoided.
Well, if you consider ntp to be one network, and the dns system to be a separate network, and the CA system to be a separate network, that statement seems to hold pretty well to today's internet. I'm not sure if you were disagreeing with my statement.
>So it seems silly to me to artificially divide up the world into separate currencies just to get different transaction features.
Just as you can have one cryptocurrency being used on many transaction networks, you can have one transaction network that uses many cryptocurrencies. Just like the ntp/dns analogy, just because Bitcoin and Ethereum are separate systems doesn't mean that I can't actively use each for what it's most useful for. Each can still benefit from the users of the other.
Do you realize you are talking to a Bitcoin core dev? lol...
"Least costly" here does factor in convenience.
You can have a case where there is no clear winner---e.g. one type of exchange is harder to use, BUT more private.
So in summary, there is likely to be one predominant cryptocurrency, and at best maybe one or two others that offer nice things (e.g. more privacy) but at an additional cost.
If one cryptocurrency can offer all commonly-wanted useful features, it will strictly dominate all the others and drive them out.
That said, there are many, many potential uses for _blockchain technology_, such as storage and computation.
Bytecoin is literally a direct copy of the Bitcoin code. Minus their recent change to the unproven (non peer-reviewed) curve25519 algorithm. It's basicaly a scrypt altcoin with an even lesser-tested algorithm at it's base.
Zerocash/Zerocoin is far from that reality.
Bytecoin has done literally nothing besidres change the hashing algorithm, Zerocash is an entirely new beast altogether.
See here for proof of calling out curve225519 vs scrypt http://www.google.com/trends/explore#q=curve25519%2C%20scryp... (when scrypt isn't even really an improvement upon bitcoin).
Bytecoin is a ground up rewrite (for better or worse) blockchain cryptocurrency which uses a pretty boring schnorr-like ring signature in an _very_ clever way to achieve strong privacy. The ring signature its using has been peer reviewed, though the partial uncloaking technique they use to prevent double spending is a novel application.
(And come on, I'm not usually one to lean on authority— but you ought to believe /me/ when I say it's not copying Bitcoin and that it's doing something very useful and interesting for cryptographic privacy)
The privacy achieved by Bytecoin is better than any existing-in-production privacy tools (e.g. CoinJoin) and also as good as or better than every theoretical system I've heard proposed except for Zerocash. Relative to ZeroCash, Bytecoin exists today and has simpler cryptographic assumptions, better performance for signers, and no requirement for trusted initialization. Because it doesn't mask values its anonymity set is potentially smaller, though the implementation does some clever denomination tricks to reduce the harm of value transparency.
The reason I included a hyperlink instead of just speaking comparatively was so that you wouldn't have to suffer from any confusion on the matter. :)
Kinda sad that with all the worthless clonecoin and whitepapercoin pumping people are missing the few bits of real innovation that are getting created, enh? Don't you agree, sir_doge_alot? :P
> See here for proof of calling out curve225519 vs scrypt http://www.google.com/trends/explore#q=curve25519%2C%20scryp.... (when scrypt isn't even really an improvement upon bitcoin).
I have no idea why you're comparing an elliptic curve group with a crappy proof of work algorithm, so here is a bunny with a pancake on its head: http://www.upsidedownguild.com/wp-content/uploads/2013/12/pa...
I was assuming the entire time that "bytecoin" was referring to the group that literally copied the bitcoin sourcecode entirely, and left it at that.
What is "the new bytecoin" then that you are supposedly referring to?
It seems very naive of the "new bytecoin team" to adopt a name that has been associated with fraudulant activity in the past.
I still rest behind my case.
I have not invested a single penny in bytecoin and probably never will.
Do they have professional cryptographers working on and vouching for their source code like zerocash? Please, inform me.
I beg of you to tell me the next great crypto currency to invest in. But for now, I am investing most of my diversification fund into zerocoin.
> See here for proof of calling out curve225519 vs scrypt http://www.google.com/trends/explore#q=curve25519%2C%20scryp.... (when scrypt isn't even really an improvement upon bitcoin).
Comparing cryptographic primitives by a Google publicity count is completely nonsensical. They offer disjunct applications: curve25519 is a mathematical group for protocols like Diffie-Hellman etc. while scrypt is a guaranteed to be slow hash function.
> unproven (non peer-reviewed) curve25519 algorithm
curve25519 was published by the renowned cryptographer Dan Bernstein in "Lecture Notes in Computer Science" ( http://link.springer.com/chapter/10.1007/11745853_14 ) and according to Google Scholar it has 114 citations. On its Wikipedia page you could have found out that it extensively used by Apple in iOS: https://www.apple.com/iphone/business/docs/iOS_Security_Feb1... . It's probably going to be one of the major groups used for ECDH (elliptic curve Diffie-Hellman - the stuff you need for fast perfect forward secrecy) in TLS 1.3 and some even argue to ditch all the NIST curves in its favor.
I'd appreciate if you would do a minimum amount of research before you dismiss widely accepted cryptographic primitives just because you haven't heard of them before.
I love the idea of Cryptocurrencies in general (and got interested in computers, cryptography, security, and cypherpunks around the same time in ~1992), but without something which makes every transaction unlinkable, and thus preserves fungibility of the currency, I find things like Bitcoin a step back from Chaumian blinded tokens. There's the potential for coin validation in regular bitcoin, and once there's technical potential, it can become mandated. Once that happens, even if it starts for something "nice" like preventing large thefts, it can turn into censorship.
With zerocash, I could see blockchain-based anonymous systems coexisting for low-throughput, high-persistence systems mainly going to blockchain tech, and high-throughput, non-inherent-decentralized systems doing their own Chaumian blinded token currencies. And "currencies" not just being used for human payments, but lots of forms of resource allocation.
Right now I have to physically drive to a land records office, pay the people behind the desk to look through some old photocopied records; which they can't even fully guarantee the accuracy of.
Most of the automated systems for land title seem to be the civil law approach, and for that a central registrar doesn't really map well to the blockchain. There's also no real anonymity -- at best, pseudonymity for keys, but the hard part is binding keys to legal owners.
Can you imagine what might happen if the land of the U.S. federal reserve building was somehow transferred to a random individual?
I used to get "free money" in my bank account all the time. Some banker would make an error, depositing a check from a member of a separate branch into my account with the same account number. The mistake was usually noticed during an audit and the money would magically be removed from my account.
Reversible transactions do have their place, I suppose.
Where it gets really interesting is with things like cars (and eventually cellphones and other similarly priced goods); putting effectively activation locks and DRM into the equipment. IFF you could trust the whole system, it would make theft much less of a concern, which is great.
It could make phone theft a lot harder depending on the hardness of the DRM.
Darkcoin V2 is also adding ring signatures mixed in with the masaternode system so I'll see how that works when it gets released.
It's certantly not the first time that I've posted about something technical where some altcoin then popped up with it as a sales feature on its whitepaper without even bothering to implement it. :-/
The funny thing is that CoinJoin's primary advantage is the network support for it is already part of Bitcoin since day one. Maybe it's not /completely/ pointless to launch a new cryptocurrency around CoinJoin simply because a commitment from a lot of users to use it might increase the anonymity set... but as far as I can it's nearly completely pointless (esp since in Bitcoin some ordinary transactions look like CJs).
If you're going to do something incompatible at the protocol much better can be done— as shown in practice by Bytecoin, or in theory in ZeroCash and ZeroCoin. ... even there isn't not a requirement to start up a whole new currency for it, but at least not pointless. CoinJoin isn't the be all end all of transaction privacy, but at least you don't have to switch currencies or convince people to deploy improvements to Bitcoin in order to make use of it. :)
Their old "zerocoin" project website had a neat infographic depicting it's simplified usage: http://zerocoin.org/media/images/zerocoin_blockchain.png
Although I haven't fully read the zerocash whitepaper yet to know if they're still headed in the same direction, I believe that they are.
There is also the Q&A page on the new zerocash-project.org website: http://zerocash-project.org/q_and_a
The results are essentially that a central party can pool together an arbitrary number of bitcoins, then issue a derivative instrument against that pool. Those derivative instruments can be constantly recreated, so they're not maintaining any history or linkability. Once you receive one, you can also redeem it, destroying it, and claim an equivalent value of bitcoin, which is removed from the pool.
Except there is no "central party", except at the initiation of the system; you can build it so the central party creates parameters but doesn't save anything, so he's just a normal participant after that, and can disappear. So it's almost as decentralized as Bitcoin/Satoshi.
How it works is a bit more complex; it involves zero knowledge proofs about the derivative instruments. This is sufficiently advanced crypto that it will be a burden to anyone trying to understand it.
I'm curious about implementation, though. Most derivatives have a cost of carry built-in and this doesn't. It also doesn't work unless you convert your bitcoin immediately; the blockchain doesn't forget.
Would you mind explaining the q-power knoweldge of exponent assumption and how someone verifying the recursively constructed proof can be confident that the prover actually knows a _specific_ satisfaction of the circuit themselves given that the proof is much smaller possible state of different inputs? :P
There isn't anything in ZeroCash that I would describe as a derivative instrument.
The super-simplified explanation I would give is that it lets you encrypt the content of your transactions and prove just enough properties about the encrypted data so that the network can tell that the the transactions as valid without actually revealing any of the private specifics.
Its been a while since I read about it, so the method may have changed (or I may be misremembering), but here is my understanding:
Every zerocoin has a secret key associated with it (that only the creator of said zerocoin knows). Using a cryptographic primitive called a zero knowledge proof, it is possible for someone to prove that they know the secret without revealing the secret itself.
There is another cryptographic primitive called an accumulator, which represents the set of all zerocoins that have been created. It is possible to prove that you know the secret of some zerocoin within this set, without revealing which zerocoin it is. It is further possible to prove that the zerocoin you know is different from all of the other zerocoins which have been claimed in this manner.
To 'transfer' a zerocoin from party A to B, party B generates a new zerocoin, and sends the (public) details to A, keeping the secret to itself. Party A then uses the above mechanism to show that it has an unspent zerocoin, and spends that coin to insert B's coin into the accumulator. Simmilarly, A could spend a normal bitcoin to do so (or do anything else that would convince the network that A has the right to insert a zerocoin into the accumulator).
[1] http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf
EDIT 2: s/crystallographic/cryptographic/
Is this the same thing? http://en.wikipedia.org/wiki/Primitive_cell
(Upvoted and appreciated though. The rest is a lot clearer.)
Unfortunately, primitive cells seem mathy enough to be plausibly to cryptography for that to be a confusing mistake (especially given the existence of lattice based cryptography).
(What you describe is Zerocoin, the OP is about Zerocash)
Can anyone comment on how simmilar/different Zerocash is from the original Zerocoin? Did they just improve the underlying crypto, or is there a more high level change involved?
Zerocoin basically implemented a decenteralized 'mix' via a blind accumulator. Zerocash uses zero knoweldge proofs of execution for general computation so that basically all properties of a coin can be completely blinded.
In ZeroCoin, coins— all of equal denomination— go into a bag (one bag per denomination), and coins come out of the bag and you can't tell which was which (except, of course it can't come out until after it's gone in.). In Zerocash its more like everything is completely encrypted, even the values, the network knows that its all valid due to zero knoweldge proofs, but only the transaction participants know any of the details of the transactions at all.
In some ways Zerocash is really the some of the most pedestrian applications of the ZK-SNARK technology, ... prepare to have your mind blown and go read some at http://www.scipr-lab.org/
Sure if you're willing to let me blackbox away the worst of the complexity.
First: There exists a special execution environment where you can run a program with some inputs known to the public and other inputs that are secret and only known to you. As a result of the properties of this execution environment the output of the program comes along with a compact (constant size, regardless of the program!) proof which you can show to people which will convince them that the output really was the correct output of running that specific program with those public inputs and some secret inputs and they learn nothing about the secret inputs.
If you're willing to accept that much, the rest is simple. If not— well the math to make those proofs efficient is really N levels deep of really gnarly abstract algebra and cryptographic assumptions. I've never seen a strong explanation which is adequate for an ordinary mathematician (as opposed to one who is expert in the relevant subfields), much less Joe-HNer. If even the idea that someone can prove the validity of execution in zero knowledge seems incredible to you, before we start talking about small proofs, then maybe I can help there: I came up with a toy (not proven secure) example system for this that doesn't require more math than accepting one way functions function, and some simple statistical reasoning to follow: https://people.xiph.org/~greg/simple_verifyable_execution.tx... (I created this not as something for people to use, but because if I want people to start engineering systems that makes use of this technology I must first remove it from the realm of unbelievable magic. :))
In any case, given that we've got this magical proof producing execution environment the rest follows naturally:
To make a transaction paying to an anonymous address, I take the recipient's one time public key, a random nonce, and the value of the amount that I'm paying and hash them: OUT = H(pubkey|value|nonce). You can think of this as an 'encrypted' coin. I then have a program that checks that OUT really is the hash of the recipient's pubkey and some nonce (known only to me) and the value that its supposed to be. I run the program (which just runs the hash and an equivalence test) in the magic ZK execution environment and it gives me a proof. I stick OUT and the proof in my transaction. By virtue of the proof the network is convinced that OUT is a valid blinded coin with the correct value, even though it can't tell what the nonce/pubkey was and so it can't check for itself by repeating the computation. After accepting my transaction the network appends OUT to a merkle hash tree over all previously created anonymous outputs. I tell the recipient the nonce and value, and he can see that the newly created coin has been added to the network's collection of coins.
Later, when the recipient wants to spend that coin, he goes and extracts the log2() sized tree fragment (all the hashes along the path from the root to the coin) which can be used that coin is in the network's current hashtree. He has a program that verifies that takes this fragment and verifies that it's valid, his pubkey, and the nonce it also takes a new anonymous output (like my first program, a new pubkey nonce and value), and verifies that the values add up. He runs this program in the ZK proof environment with the pubkey that its spending and the new output as public inputs, and the hash tree fragment as a secret input... and gets a proof.
He sticks the proof in a transaction along with the new output, and signs it with the public key he just revealed. The network can now be convinced that he's spending a coin that exists (though it doesn't know which), and that it's creating a new coin (which it will add to the list) with a permissible value (though it doesn't know the value). The network then remembers the public key used, and never permits another transaction that uses the same pubkey— this prevents him from spending the same coin over and over again. No one observing can tell which coin was spent, because although they can now see the pubkey they still don't know the nonce and so they can't go testing against all the previously created coins.
Of course, to make a real system out of this you need several different programs that you can run in the ZK environment: A program to create a new anonymous coin from non-anonymous sources with known values (e.g. to let you mine coins anonymously), a program to take two anonymous coins and produce one new anonymous coin of the sum value (perhaps leaking a little value for fees), and a program to take one anonymous coin and split it into two anonymous coins. (Perhaps you might want some other variation— though in the ZKP system used for ZeroCash each distinct circuit, since they do not use a universal circuit for efficiency reasons, requires the provers to have hundreds of megs of of 'prover key' created by the trusted initialization process, so its helpful to avoid having too many different programs)
The security of all this depends on the integrity of the ZKP system. If its compromised, no privacy is lost, the succinct proofs aren't even big enough to leak the secret data... but someone who has compromised the proof system could create false proofs, spending coins that never existed.
Hopefully this makes it a bit more accessible?
That being said, the biggest problem of the system seems to be that if it is compromised, someone can make ludicrious amount of money (2^64 units or such) out of nothing. Which has, in turn, potential to drive the price of the currency towards zero. Even worse, you don't know, at any given point, whether the system was already compromised or not. Thus, no emergency measures (such as the one made when bitcoin chain was forked) can be applied.
Any ideas how to fight the problem?
I can't see many governments being happy with a service like this.
Matthew Green has carefully worded his presentation of this project in the past.
He has always claimed that such an implementation could be possible. Not that it was inherent to the coin itself.
Let's hope that he gets it running sooner, rather than later. Before somebody has a chance to change his mind.
"Zerocash can be deployed atop any ledger (even one maintained by a central bank). Here, we briefly detail integration with the Bitcoin protocol."
"Zerocash breaks compatibility with the Bitcoin network. While Zerocash could be integrated into Bitcoin (the actual currency and its supporting software) via a “flag day” where a super-majority of Bitcoin miners simultaneously adopt the new software, we neither expect nor advise such integration in the near future and suggest using Zerocash in a separate altcoin."
"Integrating Zerocash into Bitcoin consists of adding a new transaction type, Zerocash transactions, and modifying the protocol and software to invoke Zerocash’s DAP interface to create and verify these transactions. There are at least two possible approaches to this integration. The first approach replaces all bitcoins with zerocoins, making all transactions anonymous at the cost of losing any additional Bitcoin functionality provided by, e.g., the Bitcoin scripting language (see Section 6.1). The second approach maintains this functionality, adding a parallel Zerocash currency, zerocoin, which can be converted to and from bitcoin at a one-to-one rate "
Their attempts to merge the original Zerocoin idea into the Bitcoin blockchain were met with contempt.
Zerocoin used one-way accumulators and discrete log based ZKPs, which are fairly approachable to anyone who has taken an undergraduate course in cryptography. Zerocash, however, uses Ben-Sasson's highly efficient zk-SNARK construct [0], the details of which are probably fully understood by a handful of people in the world. There's a reason the people who geek out over this kind of thing (#bitcoin-wizards) call it 'Moon math'.
ZeroCash improves the performance from the network's perspective greatly (at the expense of client performance), so it might be easier to make work. It also greatly improves the anonymity by hiding the values, at the same time it makes the trusted initialization worse. Mixed bag.
That said— I don't know about 'contempt', here was my response: https://bitcointalk.org/index.php?topic=175156.msg1826596#ms... and I don't recall anyone else with pull in these things being more negative than I was.
("My initial read of their paper was interesting, but it was two to three orders of magnitude more resource intensive than would be required to make it actually viable ... On the plus side— approaches can only get better")
I do hope that cryptographic privacy improvements are themselves not too controversial to deploy. Bitcoin as it is, is basically a privacy disaster which is only mitigated by the fact that Bitcoin is a niche thing that no one is forced to use. If you felt compelled to use Bitcoin in your daily personal and business life the current state of privacy there would cause a lot of harm. I cringe a bit at people trying to promote Bitcoin to 'authorities' with the "it's not private" argument, I think that stems from a misunderstanding of what authorities should want (e.g. they shouldn't want people to be made vulnerable through a loss of privacy), and a lack of knoweldge into how to discuss that privacy isn't incompatible with the public interest (quite the opposite), and that trying to deny privacy seldom reduces privacy for criminals (since they can buy their way to privacy) but mostly for innocent individuals... but I guess we'll see how things pan out.
Right now the proposed privacy technology has to little maturity and too many tradeoffs to consider it in Bitcoin, but when that isn't the case I hope we can adopt them, but even without doing so the privacy techniques that can already be used in Bitcoin and cannot be stopped (like CoinJoins and CoinSwaps) can help a lot if they become more widely used.
http://blog.oleganza.com/post/71410377996/real-crypto-anarch...
http://blog.oleganza.com/post/58240549599/contracts-without-...