Zerocash: Decentralized Anonymous Payments from Bitcoin [pdf]

http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf

by rdl • 12 years ago

156 56 12 years ago

fhinson• 12 years ago

"The Zerocash protocol extends Bitcoin and enables users to pay one another directly, via payment transactions that reveal neither the origin, destination, or amount of the payment."

I can't see many governments being happy with a service like this.

sirdogealot9• 12 years ago

My thoughts exactly.

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.

rdl7• 12 years ago

This is, for me, the single most interesting thing in the Bitcoin/Blockchain world.

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.

sirdogealot9• 12 years ago

Blockchain technology would certainly make title searches on real property easier.

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.

rdl7• 12 years ago

There are two main systems of managing real property -- the decentralized common law system, and the land registry system. I think for each just regular signatures work -- the hard part is associating a key to each property owner, but a central timestamping service helps there.

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.

rrggrr• 12 years ago

Can someone explain how this works to a non-mathematician?

sirdogealot9• 12 years ago

That would be very difficult, and I'm sure will prove to be a major deterring factor in the early adoption of this new currency.

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

rdl7• 12 years ago

Do you want to know what the results are, or how it works?

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.

jacobwcarlson• 12 years ago

The math and crypto are fairly straight-forward, dunno why you're telling people they can't 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.

nullc10• 12 years ago

derivative instrument against that pool

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.

gizmo6864• 12 years ago

EDIT: Check out [1] for a better explanation. Specifically, page 2 has a nice description.

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/

prawn• 12 years ago

You were doing so well until "crystallographic primitive"! ;)

Is this the same thing? http://en.wikipedia.org/wiki/Primitive_cell

(Upvoted and appreciated though. The rest is a lot clearer.)

maaku• 12 years ago

Zerocash != Zerocoin

(What you describe is Zerocoin, the OP is about Zerocash)

nullc10• 12 years ago

Can someone explain how this works to a non-mathematician?

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?

rumcajz• 12 years ago

I have been thinking about fully anonymous currencies in the past, which, not a big surprise, lead me to NIZK proofs. I was stopped there by the lack of resources on the topic. Your simple explanation (the link above) was really helpful. Thanks fro writing that down!

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?

pmorici• 12 years ago

So is this something that can be added on top of Bitcoin or is it a separate coin with improvements? It isn't clear to me which it is from the abstract.

gizmo6864• 12 years ago

This is described in section 6:

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

sirdogealot9• 12 years ago

It is going to be a separate coin once released.

Their attempts to merge the original Zerocoin idea into the Bitcoin blockchain were met with contempt.

kzrdude• 12 years ago

oh. contempt from whom, and why?

rgbrgb• 12 years ago

Could anyone better versed in cryptocoinage tell me how this differs from darkcoin[1]? DRK is another cryptocurrency created for anonymous transactions.

http://www.darkcoin.io/

wmf• 12 years ago

One of them is an academic paper and the other has a website that mostly consists of "coming soon" pages. But seriously, DarkCoin appears to use CoinJoin[1] which has a smaller anonymity set than SNARKy systems.

[1] https://bitcointalk.org/index.php?topic=279249.0

aaxx1503• 12 years ago

Darkcoin has actually implemented a lot of new code. They have an advanced form of decentralized coinjoin called darksend mixed with a system of masternodes which share the block reward as a sort of proof of service. The masternodes require 1000 DRK ($6600+ as of right now) to limit network chatter and make it increasingly expensive for people to take control of a lot of masternodes. Additionally coins in masternodes are removed from circulation, allowing a sort of positive feedback loop as far as price goes.

Darkcoin V2 is also adding ring signatures mixed in with the masaternode system so I'll see how that works when it gets released.

http://www.darkcoin.io/downloads/DarkcoinWhitepaper.pdf

nullc10• 12 years ago

Darkcoin is a Bitcoin clone which was released with basically no changes at all to the system, but with CoinJoin (https://bitcointalk.org/index.php?topic=279249.0) privacy as a sales pitch.

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

nullc10• 12 years ago

It's a little disappointing to see how much ZeroCash is hyped compared to Bytecoin (https://bytecoin.org/), since the former is still vaporware while the latter is something real that you can go use right now.

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

Taek2• 12 years ago

Zerocoin was really the first of it's kind, that's where all of the hype comes from. The promise that Zerocoin offered initially was a lot stronger than anything around, and many people heard about Zerocoin long before they heard about CoinSwap or CoinJoin (and subsequently Bytecoin).

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.

nullc10• 12 years ago

Zerocoin was really the first of it's kind, that's where all of the hype comes from. The promise that Zerocoin offered initially was a lot stronger than anything around

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.

jafaku2• 12 years ago

As someone who's been working on cryptocurrencies

Do you realize you are talking to a Bitcoin core dev? lol...

javert• 12 years ago

It is an economic law that the least costly means of exhcange wins and predominates in any given niche and drives out all other means of exchange.

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

rdl7• 12 years ago

I'm confident "the community" could come up with an awesome trusted initiation procedure which was both secure and obviously secure enough to convince people for all time, based on ~$100b in the pool, that it hadn't been compromised. Probably for less than $5-10mm.

sirdogealot9• 12 years ago

Please. Give me a break.

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

nullc10• 12 years ago

Nope. You are confused. You should consider this great news because you are about to discover something quite interesting!

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

Perseids• 12 years ago

Please excuse my outburst, but this bothers me to no end:

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.

lifeisstillgood• 12 years ago

isn't there a legal issue here - in any contract there is consideration - but if consideration is anonymous who can enforce a contract?

oleganza• 12 years ago

To enforce contract you do not always need identity. Identity is needed when enforcement is through violence. But you can use economic incentives to make people prefer following the contract.

http://blog.oleganza.com/post/71410377996/real-crypto-anarch...

http://blog.oleganza.com/post/58240549599/contracts-without-...

driverdan• 12 years ago

You're making two possibly false assumptions, that the parties don't know each other outside the payment system and that they won't have incentive to fulfill their contract without knowing each other's identity.

nullz• 12 years ago

a source of some confusion: zerocoin !== zerocash

Zerocash: Decentralized Anonymous Payments from Bitcoin [pdf]

Related Stories