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.
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.
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.
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
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).
Probably, that's the first result I got when googling "crystallographic primitive", my comment problem makes more sense reading it as "cryptographic primitive" :).
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).
Good catch. I haven't thoroughly read the OP, but from the little bit I have read, it looks like they refer to the currency of Zerocash as zerocoins (the uppercase on Zerocash and lowercase on Zerocoin come from the paper), and the OP seems to be by the same authors.
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/
> 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.
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.
Use N distinct ZK proof systems in parallel. This requires having multiple distinct systems which are sufficiently efficient. Getting one is currently hard enough, but in the long run it might be a good way to achieve adequate security.
