Zerocoin was initially proposed to be an extension that would add true cryptographic anonymity to the Bitcoin protocol. Zerocoin provides anonymity by the introduction of a separate zerocoin cryptocurrency that is stored in the block chain along side the base currency. Originally proposed for use with the Bitcoin cryptocurrency, the original developers (Miers et al. 2013) have abandoned this concept. Zerocoin is now being implemented in Anoncoin, where it will be setup in a trustless manner using RSA UFOs. Unlike other coin mixing services, the Anoncoin implementation of Zerocoin will not rely at all on trusted third parties.
Bitcoin transactions are all stored, by design, in a public ledger (the block chain) that is accessible to everyone. These transactions provide privacy through pseudonymity, in that while each transaction is associated with the public address of the sender and receiver, the real-life names of the owners of these addresses are at no time made known to the network. To increase privacy, each person could create as many public addresses as they like, making it difficult to link transactions to the same person. If additional privacy were required, it is possible to launder coins through a trusted third party, where the input coins are mixed in a large pool and output to a new address .
Regardless of the best precautions, it is possible in certain cases to link a set of public addresses to a specific individual. For example, by data mining the block chain or by the analysis of spending habits, it is possible to link sets of addresses. By utilizing information external to the block chain, such as public addresses posted on a web site or the postal address used with an internet purchase, the possibility exists that every single transaction of a given person could be determined. If all your transactions could be deanonymized, this would be analogous to publishing the full contents of your bank account on line for all to see.
Zerocoins are purchased with the base currency in fixed denominations by a zerocoin mint transaction. Later, these zerocoins can be redeemed for the base currency to a different address by a zerocoin spend transaction. Through the use of cryptographic accumulators and commitment schemes with zero-knowledge proofs, it is not possible to link the address that was used to mint the original zerocoin to the address used to redeem the zerocoin.
The zerocoin  extension acts like a money laundering pool, temporarily pooling coins together in exchange for a temporary currency called zerocoins that can be redeemed at a later date. While the laundering pool is an established concept already utilized by several currency laundering services, Zerocoin would have implemented this at the protocol level, eliminatating any reliance on trusted third parties. It anonymizes the exchanges to and from the pool using cryptographic principles, and records the transactions within the crytptocurrency's existing block chain. Unlike many existing laundering pools, where your coins are mixed with a small number of other coins, the zerocoin laundering pool is composed of all existing zerocoins.
The anonymity afforded by Zerocoin is the result of cryptographic operations involved with separate zerocoin mint and spend transactions. To mint a zerocoin, a person generates a random serial number S, and encrypts (that is commits) this into a coin c by use of second random number r. The coin c is added to a cryptographic accumulator by miners, and at the same time, the amount of anoncoin equal in value to the denomination of the zerocoin is added to a zerocoin escrow pool.
To redeem the zerocoin into the base currency (preferably to a new public address) the owner of the coin needs to prove two things by way of a non-interactive zero-knowledge proof. (A zero-knowledge proof is a method by which one party can prove to another that a given statement is true, without conveying any additional information apart from the fact that the statement is indeed true.) The first is that they know a coin c that belongs to the set of all other minted zerocoins (c1, c2, ..., cn), without revealing which coin it is. The second is that the person knows a number r, that along with the serial number S corresponds to a zerocoin c, without revealing the value of r or c. The proof and serial number S are posted as a zerocoin spend transaction, where miners verify the proof and that the serial number S has not been spent previously. After verification, the transaction is posted to the blockchain, and the amount of anoncoin equal to the zerocoin denomination is transferred from the zerocoin escrow pool.
Anonymity in the above transaction is assured because the original minted coin c is not linked to the serial number S used to redeem the coin. In order to link the coin c to the serial number S, one would have to know the number r used to encrypt the coin, but this is not revealed by the proof. The above procedure also ensures that zerocoins can not be redeemed more than once. By posting the serial number S of the redeemed coin to the block chain, the network would easily detect if the same number were to be used at a later time.
Recognizing that Zerocoin was unlikely to be implemented Bitcoin, the authors of the Zerocoin paper (Miers et al. 2013) expressed hope that other cryptocurrencies would incorporate zerocoin anonymity features. At the present time, Anoncoin is the only cryptocurrency that is actively pursuing this goal.
Zerocoin in practice
Zerocoin mint transactions will be only slightly larger than normal transactions, corresponding to about 128 bytes per minted coin. Zerocoin spend transactions will have a small part added to the ANC blockchain, and then about 125 KB corresponding to the zerocoin proof that will be stored in an external database. Once sufficient time has passed, the old verified proofs, which serve litte purpose, will be periodically deleted. Using 8 cores on a 2.4GHz Core i7, Zerocoin spend transactions would take about 3 seconds to generate, and about 0.5 s to verify.
There will be 24 possible zerocoin denominations, ordered by factors of 10 from 10-8 and 5 10-8, to 103 and 5 103. The minimum zerocoin denomination corresponds to 1 satoshi. The Zerocoin client will show the number of coins accumulated for each denomination, as well as the mint/spend volume over the last 100 blocks, allowing users to decide how anonymous their zerocoin transaction will be.
One criticism of the original Zerocoin protocol is the added computation time required by the process, which would need to have been performed primarily by miners. If the proofs were posted to the block chain, this would also dramatically increase the size of the block chain. Nevertheless, as stated by the original authors, the proofs could be stored outside of the blockchain , and this is the approach that the Anoncoin implementation will use.
To counter criticisms that the anonymity offered by zerocoin would facilitate illegal activity, it has been suggested that a backdoor, or other features, could be added to the zerocoin protocol to allow police to track money laundering . Anoncoin would never add such a backdoor, and this would be easily verified as Anoncoin is entirely open source.
Since a zerocoin would have the same denomination as the base currency used to mint the zerocoin, anonymity would be compromised if no other zerocoins (or few zerocoins) with the same denomination are currently minted but unspent. The solution to this problem used by Anoncoin is to allow for only 24 separate zerocoin denominations.
For the accumulator, Zerocoin requires generating a number N that is composed of two large prime numbers P and Q. If these factors were known, it would be possible to forge zerocoin proofs. However, even if these factors were to become known, the anonymity of minted zerocoins would still be assured. These prime numbers could be generated by the use of third parties, but the system would then depend entirely upon the honesty and trust of these parties. The approach that Anoncoin will use is to generate RSA unfactorable objects (RSA UFOs) that are composed of two prime numbers, and which can be generated in a trustless manner using the approach of Sander (1999). Such a setup, while possible with Zerocoin, is not possible with the new Zerocash protocol of Ben-Sasson et al. (2014).
- Anonymity of cryptocurrencies
- Cryptographic accumulator
- How anonymous are you
- RSA UFO
- Zero-knowledge proof
- Official Zerocoin website: http://zerocoin.org
Miers, I., C. Garman, M. Green, A. D. Rubin (2013). Zerocoin: Anonymous Distributed E-Cash from Bitcoin, 2013 IEEE Symposium on Security and Privacy, IEEE Computer Society Conference Publishing Services, pp. 397-411, doi:10.1109/SP.2013.34.
Sander, T. (1999). Efficient Accumulators without Trapdoor Extended Abstract. In: Information and Communication Security, V. Varadharajan and Y. Mu (editors), Second International Conference, ICICS’99, pages 252-262.
Ben-Sasson, E., A. Chiesa, C. Garman, M. Green, Ian Miers, E. Tromer, M. Virz (2014). Zerocash: Decentralized Anonymous Payments from Bitcoin (extended version), Proceedings of the 2014 IEEE Symposium on Security and Privacy, 56 pp.