How does Zerocoin work?

Question

How does Zerocoin work? I got the idea that it is used to add anonymity in bitcoin. It converts bitcoin to Zerocoin and back to bitcoin. But how does this process work? I tried reading the research paper on Zerocoin, but the example provided is difficult to understand (for me).

Imagine that all users share access to a physical bulletin board. To mint a zerocoin of fixed denomination $1, a user Alice first generates a random coin serial number S, then commits to S using a secure digital commitment scheme. The resulting commitment is a coin, denoted C, which can only be opened by a random number r to reveal the serial number S. Alice pins C to the public bulletin board, along with $1 of physical currency. All users will accept C provided it is correctly structured and carries the correct sum of currency. To redeem her coin C, Alice first scans the bulletin board to obtain the set of valid commitments (C 1 , . . . , C N ) that have thus far been posted by all users in the system. She next produces a non-interactive zero-knowledge proof π for the following two statements: (1) she knows a C ∈ (C 1 , . . . , C N ) and (2) she knows a hidden value r such that the commitment C opens to S. In full view of the others, Alice, using a disguise to hide her identity, 1 posts a “spend” transaction containing (S, π). The remaining users verify the proof π and check that S has not previously appeared in any other spend transaction. If these conditions are met, the users allow Alice to collect $1 from any location on the bulletin board; otherwise they reject her transaction and prevent her from collecting the currency.

Answer 1

One of the problems (or advantages) of Bitcoin is that funds can be traced. Even if each address is used only once, it is possible to link individual transactions to each other similarly to how it is possible to track bank notes by their serial numbers (with the addition that everyone records serial numbers of all the notes they handle).

Zerocoin solves this problem by providing a new kind of transaction outputs that are not linked to inputs that spend them. Actually, outputs are linked to inputs, but the link is cryptographically obscured, so that an observer can't find which input an output is linked to. However, it is still possible to check that there is only at most one input linked to any particular output, so that double-spends are not possible.

To obscure the link, a cryptographic construction is used which is called zero-knowledge proof. Zero-knowledge proof is a way to show that something is true without revealing any useful information. For example, a digital signature is a zero-knowledge proof that shows that the signer knows the private key. There is no way, however, to learn the private key from the signature.

Proofs used in Zerocoin are more complex. Basically, when generating a Zerocoin, a user picks a random serial number and includes a special irreversible function of that number in the output. When spending, he reveals the number and provides a proof that the number corresponds to one of the outputs. Only one serial number corresponds to each of the outputs, so double-spends are prevented by checking that each serial number is used only once.

Answer 2

The process is basically as follows.

1. You generate a random serial number S and a secret r. S will be used to denote a zerocoin. Then you create a commitment C = f(S,r) s.t. without knowing both S and r it is very hard to get those back from C. Then you disclose C into the public channel.

2.To redeem the coin S you disclose S and give a proof that S corresponds to some valid commitment in a set of large number of commitments (provided by you), say {C1, C2, ..., C, ..., Cn}. As you don't explicitly mention which commitment does S correspond to, you retain your anonymity.

3. When other users verify that your proof is valid and the zerocoin S is not already spent, then only you can spend the coin. You probably understand that S needs to be revealed when spending money to prevent double spending.

Answer 3

Zerocoin is a proposed extension on Bitcoin to make it more confidential using zk-SNARKs (more detailed information on zk-SNARKs is founf here: https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/). Zerocoin only hides the origin of a payment, the destination and amounts are still public.