How does Zerocoin work?
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.