Btw I made a summary of the zerocoin paper here.
http://www.mail-archive.com/cryptography@randombit.net/msg04117.htmlNot sure it helps understand it or not, but there you go.
About ZKP of set-membership the first thing to understand is the RSA accumulator of Benaloh.
http://www.cs.stevens.edu/~mdemare/pubs/owa.pdfIts like a commutative hash function but using RSA. With discrete log (or EC discrete log) if i give you A = xG (G is base point x some random number) I can prove I know the discrete log by showing you x and G is fixed. But if you are allowed to use any generator H then you can start with A divide it by some random number x and call the result H. Now you can prove xH = A but that doesnt prove anything as anyone can do that if they can prove the discrete log to some random base its an x-th root not a discrete log, which is easy . How you "divide" A by x is multiply by x^-1 mod n (n is the order of the curve a public known value for a EC parameter set). And you can compute x^-1 mod n easily with euclidean algorithm (normal modular math, no EC).
However the analogous division is not possible with RSA, in RSA computing x-th roots is also hard (as well as discrete log). eg If I give you A you cant compute A^(x^-1) because x^-1 has to be mod phi(n) = (p-1)*(q-1), and in the case of RSA phi(n) is secret and in the case of an accumulator p, q, phi(n) are supposed to be deleted after setup so no-one knows them. So if I can show you H and x and H^x = A that proves you I had an influence in producing A.
each step is done by the user after receiving the previous accum set. Users can go in any order as exponentiation is commutative.
G and n is published, p, q deleted
step0: accum set = {G}
user1: private x1, accum set = {G,A"=G^x1}
user2: private x2, accum set = {G^x2,G^x1,A'=G^x1^x2}
user3: private x3, accum set = {G^x2^x3,G^x1^x3,G^x1^x2,A=G^x1^x1^x3}
The accum set is broadcast by each user and each user raises every element except the last to his private exponent xi, and appends the last element raised to his private exponent xi.
You notice that the base of each user is missing the exponent of his respective xi, user1 base is missing x1 (first item in set), user 2 is missing x2 (second item in set), user 3 is missing x3 (third item in set). Consequently a user can raise his private base call it Bi for user i, to power xi and get A the global accumulator Bi^xi = A. Because discrete log and x-th roots are hard in RSA he cant do that unless he was involved in this process.
That involves a lot of sending of sets. If alternatively each user broadcasts his xi, everyone can compute his own Bi and the final A, however now anyone can compute any Bi and all xi are public. Its a lot more communication efficient however. To combat the fact that xi are public, xi has to be chosen eg as xi = H( yi ) where yi is secret. Then a user can prove that by revealing yi and having the verifier check xi = H( yi ) and Bi^xi = A.
Or as its hard to efficiently make ZKP about (symmetric) one way hash functions a discrete log "hash" function could be used eg xi = H^yi. Now the user could prove knowledge of yi without revealing yi (via a Schnorr signature see below).
So lots of people compute and pass those messages around then they can prove simply that their zerocoin is in the set until there is a final A that includes contributions from all users who produced zerocoins in this time period. And each user knows a Bi such that Bi^xi = A for the single A value so they can prove membership. The order is commutative so it doesnt matter which comes first. A is small - just 2048 bits = 256bytes no matter how any serial numbers are provable against it. Bi is also small 256bytes as well as is xi. And the user need only store Bi and xi because he can compute A from it.
So that provides a proof that you had an influence on an accumulator (some non-secret value of yours was included "hashed" into an accumulator). Its rather like a merkle tree except that you dont need to provide log n path in the three to prove, just prove you know Bi^xi = A.
So far thats not private as all Bi values are recognizable to anyone who saw them. However using an extended blind schnorr signature like proof where you can prove you must know such an xi and Bi without actually revealing them. Its ZKP because the verifier could even create a fake if he choose the challenge himself so therefore you can argue he couldnt learn anything about Bi nor xi from something he could've created yourself.
A schnorr proof of knowledge to get an idea how you could prove something similar is related to a DSA signature and relatively simple eg here.
http://en.wikipedia.org/wiki/Schnorr_signature and its the same concept as DSA, ECDSA etc - ie you can prove you know the discrete log of something, without actually revealing the discrete log!
A schnorr proof only hides xi, the zerocoin enhanced proof also hides Bi but the basic idea is the same.
The efficiency problem in zerocoin is that each run of the ZKP has a 1/2 chance of being unconvincing. So you have to run it like 128-times to get probability 1/2^128 kinds of cryptographic assurance. This repetition is called cut-and-choose. Fortunately it can be made non interactive (by fixing the challenges based on a one-way hash of the parameters), but thats still 128 x 2048-bit RSA things which is like 10s of kB. Probably they are doing a bit less than 128 cut-and-choose rounds because they say that proof size is 45kB for 2048-bit and I presume a proof includes at least 2x 2048-bit values. Actually I see they say 80x, so that comes out to 2.2 so maybe there is some auxilliary info, eg the serial number?
To prevent double spending they just keep a public list of spent zerocoin serial numbers, and you cant influence the serial number after the fact.
So I guess the other thing you can do if that is unnecessarily complicated is just say ok there's a ZKP of set membership which proves your coin is one of that set, but not which one and trust that people have figured out how to make that work.
btw Benaloh's accumulator paper is quite readable
[edit: fix error about xi vs Bi and give a small example]
[edit2: more communication efficient public xi = H^yi, secret yi or xi = H( yi ) version]
Adam
