An examination of the flaws in the Zerocoin protocol

Over its 7-year history, Zerocoin displayed a turbulent history, with several security flaws and twists.
This report covers some of the most significant ones, with a greater focus on 2019's incidents and their consequences from the perspective of different projects.

1. Overview of Zerocoin and its implementation(s)

1.1 Description of the Zerocoin protocol

The Zerocoin protocol allows transactions to be anonymized without the need to go through any trusted third-party (e.g., Bitcoin mixers). Instead, the mixing process occurs at the protocol level.

It was developed in 2013 by cryptographer Matthew D. Green and his students at the Johns Hopkins Information Security Institute.

At its core, the Zerocoin works in a similar fashion as a mixing pool, with the notable difference that users do not have to trust any third parties; the tumbler is implemented directly at the protocol level.

This system relies on two tokens: the basecoin (e.g., Bitcoin) and the zerocoin. Coins are minted by burning used ones up, and subsequently redeeming for new coins with no transaction history. Owing to this redemption/minting process, the history of basecoins cannot be traced back to their original users.

For instance, Alice wants to send Bob 1 BTC. Using the zerocoin protocol, she would mint a zerocoin, which is essentially a cryptographic proof of possession, and send the zerocoin to Bob. Meanwhile, 1 BTC is transferred to a token reserve that is not spendable. Whenever Bob wishes to spend part of his 1 BTC, he can use his zerocoin as a zero-knowledge proof.

Chart 1 - Zerocoin mechanism from the perspective of transactions

The Zerocoin protocol relies on an initial trusted set-up; i.e., it is required to trust someone to generate initial parameters and then destroy those parameters. For instance, ZCoin relied on RSA accumulators, which need the generation of two large prime numbers. Specifically, it relied on RSA-2048 parameters, generated from the RSA factoring challenge¹.

Thought to be an extension to the Bitcoin protocol, Zerocoin was not approved by Bitcoin developers for several reasons, namely bloated computation times, some controversy over the validity of the end-result, and whether the proposed changes were too radical of a deviation from the original Bitcoin whitepaper.

Instead, ZCoin was created in late 2015² (under the name "Moneta") as the first stand-alone cryptocurrency implementing the Zerocoin protocol (see next subsection).

Differences between Zerocoin and Zerocash

In late 2013, the scope of the Zerocoin protocol was extended in an upgrade called Zerocash.

Aiming to provide full privacy, Zerocash introduced efficiency improvements (i.e., smaller proof size and faster verification) and enhanced privacy (with added encryption of the amount and both sender & receiver addresses). The most widely known implementation of Zerocash is ZCash.

Despite some key advantages, several reasons explained why Zerocash did not replace Zerocoin. Among them, the most prominent³ ones are:

• The lack of auditability of its total supply: balances are hidden with the Zerocash protocol. On the other hand, the Zerocoin protocol does not hide them. However, as discussed in the next section, some attackers managed to create false proofs from the RSA accumulator without detection, i.e., spending other people’s coins.
• Less testing in its underlying cryptography (the main implementation of zkSNARKs is ZCash) and the general complexity of the cryptographic underlying the protocol, making it complex to audit the system.
• The time to generate a private transaction locally is high owing to its computationally intensive process.

As a result, the Zerocoin protocol has remained independent from Zerocash. Hence, the rest of this report focuses solely on the Zerocoin algorithm and its core implementation, defined in the library libzerocoin.

1.2 Overview of its different implementations

Table 1 - Comparison of major Zerocoin-based stand-alone implementations

Despite all these implementations relying on the Zerocoin protocol, these cryptocurrencies have many differences that are not the focal point of this report⁴, but some of their underlying designs are still discussed in this report.

1.3 Descriptions of ZCoin, PIVX, and Veil

1.3.1 ZCoin (pre-Sigma, as of early 2019)

ZCoin is a cryptocurrency, launched in September 2016, as the first stand-alone implementation of the Zerocoin protocol (as described in the previous section).

ZCoin’s core characteristics include:

• Based on Bitcoin source code.
• Proof of Work: it relies on MTP mining algorithm, a CPU-friendly ASIC-resistant algorithm.
• Hashing function: Merkle Tree Function (MTP) has replaced Lyra2z since 2018.
• Block time: 5 minutes (reduced from 10 minutes)
• Maximum block size: 2MB
• Total supply: 21 million (increased to 21.4 million after the exploit of several flaws). Mining rewards are halved ~ every four years (currently at 25 ZCoin/block).
• Zerocoin protocol: ZCoin was the first cryptocurrency implementing the protocol natively. However, since July 2019, ZCoin’s Zerocoin protocol has been deactivated and replaced by Sigma, while the need for a trusted set-up was also deprecated.

Chart 2 - Price of ZCoin in 2019 (USD)

1.3.2 PIVX

PIVX is a cryptocurrency designed to achieve “fungibility, transaction privacy, community governance, network scalability, and real-world utilization" for online purposes, which started in 2016.

Before zerocoin minting got disabled (in early 2019), PIVX relied on:

• PIVX started as a code fork of Dash (which itself comes from Litecoin’s code).
• It started in January 2016 under the name DNET and was rebranded to PIVX in January 2017.
• Zerocoin protocol: PIVX developed a custom implementation of the zerocoin protocol based on the libzerocoin, which was introduced to mainnet in late 2017.
• Proof of Stake (PoS): after its initial PoW phase (between January and August 2016 with the Quark algorithm), PIVX transitioned to Proof of Stake at block 259,201. On the PIVX network, both PIV and zPIV could be staked. Through this unique staking reward program, private staking was offered, along with “regular staking". Users also had an incentive to use zPoS as it would result in a 50% increase in expected staking rewards. Its purpose was to provide additional privacy against malicious behavior from other participants as the anonymity set remains a key element to consider⁵. Since January 5th 2020, the PoS Time Protocol v2 has been used, which also incorporated Cold Staking.

• Maximum block size: 2MB
• Block time: 60 seconds (with re-targeting at every block)
• Coin emission rate: PIVX has a cap of 6 PIV per block. All transaction fees and zPIV minting fees are burnt from the coin supply instead of being allocated for additional masternode/staking rewards.
• Total supply: by June 2060, the estimated maximum total supply will be 189,001,497 PIV. There is no cap on the supply. However, PIVX can even decrease in coin supply over time, depending on the number of transactions.

Chart 3 - Price of PIVX in 2019 (USD)

1.3.3 Veil

Veil is a cryptocurrency, created in early 2018 by James Burden (also known as 4x13), an expert in crypto-privacy who was also a lead for PIVX (see subsection 1.2).

Veil aims at providing "full-time privacy without compromising the strength of anonymity".

At its core, Veil relies on:

• Bitcoin protocol software: the 0.1.7 version of the bitcoin software is used.
• Zerocoin protocol: the libzerocoin, described in the previous subsection, is used.
• RingCT based on Particl's implementation.
• Stealth addresses: the use of one-time addresses for every transaction is implemented.

Other characteristics include:

• Block time: 60 seconds (with re-targeting at every block)
• Total supply: 300 million.
• Block size: 2MB.
• Hybrid Proof-of-Work and Proof-of-Stake consensus system:
  • Its Proof of Work (PoW) consensus relies on the ASIC-resistant X16RT hashing algorithm. Its purpose is to provide a fair distribution of new coins created.
  • Its Proof-of-Stake (PoS) system relies on staking conducted and rewarded directly in Zerocoin denominations. Its purpose is to reward Veil coin-holders.
  • In this two-fold hybrid mechanism, a target of one block (out of six) must be found by PoS participants.
• Auto-minting: Veil relies on an auto-minting feature: unless explicitly specified, "basecoin veils" are automatically converted into "zerocoin veils".

Veil also uses multi-transaction Zerocoin spends, owing to multi-block transactions. As computing resources are expensive (and the zerocoin protocol only allows up to 20 zerocoin denominations in one transaction), this multi-transaction spend feature is split across two or more blocks automatically.

Chart 4 - Price of Veil in 2019 (USD)

2. Historical flaws and incidents in Zerocoin-based cryptos

2.1 Description of historical flaws and vector attacks

2.1.1 ZCoin’s 2017's incident

In 2017, an incident occurred, a few months after ZCoin revealed that a typo in its source-code was exploited to mint 370,000 additional ZCoins⁶.

Following this 2017 incident, ZCoin teams announced that 18,171 coins were generated through this exploit. Specifically, someone was capable of generating fake spends, hence inflating the supply of ZCoin.

As an immediate fix, the team released immediately an emergency update to prevent additional zerocoin spends. As an end-result, the libzerocoin v2 was released, which led to a hardfork of ZCoin, and the reintroduction of zerocoin spends.

Conversely, other projects like SmartCash deactivated Zerocoin and subsequently decided not to re-adopt it, officially abandoning it in early 2018⁷.

2.1.2 Potential denial of spending attack (2017)

Another potentially exploitable flaw was publicly disclosed in 2017, by researchers at Friedrich-Alexander-Universität in Germany. Its attack commonly referred to as a denial-of-spending attack, which could have allowed a malicious user to destroy the money of honest users.

The attack would work as follows:

• An honest user wants to spend his zerocoin and sends the spend transaction (including the serial number) to the network.
• Meanwhile, the attacker, who needs control over his target victim’s network, now intercepts the spending message to make sure it never reaches the nodes of the network. Afterward, the attacker mints a new malicious zerocoin with the exact same serial number. By doing so, the attacker is able to spend this zerocoin by revealing the correct serial number.
• Following this initial spend by the malicious user, if the honest individual attempted to spend his zerocoin, the transaction would be rejected by the network and considered as a double-spending attempt due to the earlier malicious spend.

As a result, the malicious user would burn the zerocoin ahead of the honest user, usurping the new, “no-history" coins of the honest user.

Chart 5 - Description of a denial of spending attack

However, the rewards from this type of attack were not limited to on-chain effects.

A larger potential profit from this exploit would be to create a short panic where users would sell upon hearing about the attack on the protocol, while the attacker would be holding a short position on the asset itself (e.g., Zcoin). However, in 2017, it was relatively hard to construct a short position in ZCoin, hence making this type of attacks hard to conduct.

Furthermore, as mentioned by the ZCoin team itself, the risk of the attack failing remained high, and a malicious individual could also become a victim of its own attack⁸.

2.1.3 Implementation issues in libzerocoin affecting PIVX (2019)

On March 6th 2019, the PIVX team disclosed elements about an attack detected on the PIVX network zerocoin protocol (i.e., zPIV).

This vulnerability allowed a malicious individual to fake serials and to spend zerocoins that were not minted in the first place. Unlike the attack described in subsection 1.4, it would not result in user funds being stolen or getting lost. However, it would have an impact on inflation as the circulating supply could increase independently of the designated inflation schedule of PIVX.

Following the discovery of invalid blocks, PIVX team discovered that an implementation flaw was being gamed by malicious individuals, while the Zerocoin protocol had been precautiously deactivated (based on sporks⁹).

According to the PIVX team, two main elements led to the exploitability of this flaw:

1. In the libzerocoin library, the transaction signature check was performed only over the last 256 bits and not across the entire object, while the serial number was stored as a numeric type allowing to store data larger than 256 bits.
2. The signature of knowledge verification was done after the coin spend signature verification. It would not verify that the bitsize of the serial number was strictly inferior to 256 bits.

For a full detail along with the implementation, please visit the comprehensive explanation provided by the PIVX team, which includes on-chain analysis of the impact of this exploit. Other details are provided there.

This vulnerability did not impact ZCoin but impacted a wide variety of PIVX forks that were mostly low-cap cryptocurrencies.

2.2.4 Description of the most recent cryptographic flaw (2019)

In April 2019, ZCoin experienced an attack based on cryptographic flaws of Zerocoin’s core protocol design.

The full detail of the attack was disclosed on April 30th 2019 by ZCoin in a blog post.

Based on the disclosure provided by ZCoin, an attacker with at least one legitimately minted coin could create as many spends as he wants out of it, in any Zerocoin-based cryptocurrency. None of these fake spendings would be indistinguishable from authentic ones.

Chart 6 - Description of the attack (vs. normal zerocoin minting/spending process)

From a cryptographic perspective, it turned out possible to create one of the wrong proofs, with only one zerocoin being minted.

The next subsection discusses the impact on ZCoin, PIVX, and Veil from this recent attack.

2.2. The impact from 2019’s recent attacks

2.2.1 ZCoin

As an urgent fix, the team decided to disable zerocoin mints and prevent any zerocoin spend to be conducted. Hence, they effectively froze the funds in the accumulator until the release of Sigma.

Following the end of the window to convert the zerocoin on January 20th, the total damage from the attack was assessed: a total of 66,996 XZC was forged through this vulnerability.

Owing to a specific signature from the attack, the team was also able to blacklist some mints, hence preventing the attackers from converting some zerocoins into Sigma mints. As a result, the total damage was estimated at 54,321 XZC, according to ZCoin's recent update.

In July 2019, the team officially removed the Zerocoin protocol and replaced it by Sigma, also bypassing the need for any trusted set-up. Indeed, ZCoin had started working on deprecating the Zerocoin protocol since early 2018.

After its migration to Sigma, ZCoin introduced a feature to “remint" zerocoins, i.e., transfer zerocoins to Sigma mints.

2.2.2 PIVX

As a response to the incident described in subsection 2.1.3, the PIVX team had deactivated the privacy features from Zerocoin, through a spork. Since then, zerocoins have been used in a public mode i.e., in a similar fashion as normal UTXO transactions.

Specifically, zerocoin minting has been disabled while zerocoin spending remains enabled (with full links to the original basecoin). Furthermore, the team relies on Schnorr Signatures to ensure that zerocoins could be spent back to basecoins, without any exposure to the pre-existing vulnerability.

On January 5th 2020, PoS Time Protocol v2 was introduced with the 4.0 release (along with Cold Staking). Following this hardfork, PIVX is expected to announce its next privacy protocol very soon.

For cryptographic details, please visit this link.

2.2.3 Veil

Following the flaw discovery by ZCoin on April 17th 2019, the Veil team decided to deactivate the anonymizing feature from the Zerocoin protocol. It initially prevented the attack from being conducted on the Veil chain.

For Veil, staking rewards can only be paid in zerocoin (and not in basecoin). Hence, the initial fix did not rely on deactivating the complete reliance on the zerocoin protocol through an immediate hardfork.

This initial fix consisted of the addition of a patch to require all zerocoin spends to have a signature attached that links the spend to the mint. In other words, the zero-knowledge proof required to prevent a double spend was replaced by a single signature, leading to the removal of the anonymity feature but solved the exploit nonetheless.

Unfortunately, the attack “evolved", and the initial fix did not protect attackers from stealing funds from the accumulator. As an urgent solution, Veil's team decided to:

• Work with exchanges: withdrawals & deposits were suspended to prevent any transaction on the network, which could lead to substantial loss of funds.
• Return to a "true" state by adding back stolen balances to the zerocoin pools and ban the remaining zerocoins that had not been shuffled with RingCT.

Furthermore, the team disabled zero-knowledge proof making zerocoins behaving in a similar fashion to other (normal) UTXO transactions. However, unlike PIVX, minting and issuing zerocoins were not disabled (as staking was only possible in zerocoin), but privacy features have been non-existent since then.

In the medium and long term, the team decided to adopt several solutions:

• Adjustment of the emission schedule: this attack effectively increased the supply by 12,441,690 coins. As a response, the founder’s rewards have been reduced (by ~ 10 million veils) to offset most of this supply increase and will burn them, along with an additional 2.1 million (in excess of the general budget expenses dedicated to the development of the project).
• Accelerating its departure from the Zerocoin protocol: the team has confirmed its desire to part away from the Zerocoin protocol, following ZCoin’s example.

So far, the most prominent solution to consider has been RingCT staking in order to stake anonymously again. In addition, the team has also been working on a new protocol using Supersonic proofs.

3. Conclusion and lessons to consider

Unlike previous incidents, the latest Zerocoin flaw had a broad impact on the existing landscape of privacy coins.

ZCoin, its first implementation (and largest by marketcap), has moved away from the protocol and has successfully activated Sigma since August 2019. As the team had started working on an alternative to the Zerocoin protocol since early 2018, its transition was possible within a very short timeframe (following the incident).

PIVX deactivated privacy features from the Zerocoin protocol but has still not revealed the full scope of its plans beyond disclosing its desire to replace the use of Zerocoin entirely. Since the 2019 incidents, zerocoins have been used in a public mode, i.e., in a similar fashion as normal UTXO transactions.

Veil suffered a massive inflation shock, but its team managed to save the project through cooperation with trading venues and giving up a significant part of the founders’ allocation. As a result, its team decided that the Zerocoin protocol shall be fully replaced moving forward, and has since then been working on alternative propositions (e.g., RingCT staking).

This recent incident may mark the end of one of the most emblematic blockchain privacy solutions, hence, accelerating the transformation of the privacy coin landscape. However, Zerocoin, as a protocol, will likely continue to be improved based on various design propositions (e.g., from Equihash co-creator Dmitry Khovratovich), which could potentially solve its most recently discovered cryptographic flaws.

This report greatly contributed from discussions with members from teams working on the privacy coins mentioned in this report.

References

• Bootle, J., Cerulli, A., Chaidos, P., Ghadafi, E., Groth, J., & Petit, C. (2015, September). Short accountable ring signatures based on DDH. In European Symposium on Research in Computer Security (pp. 243-265). Springer, Cham. https://eprint.iacr.org/2015/643.pdf
• CoinTelegraph (Suberg, W.). Zerocoin Hacker Creates and Spends 370,000 tokens worth 410 BTC. https://cointelegraph.com/news/zerocoin-hacker-creates-and-spends-370000-tokens-worth-410-btc
• Damgård, I. (2002). On Σ-protocols. Lecture Notes, University of Aarhus, Department for Computer Science. https://www.cs.au.dk/~ivan/Sigma.pdf
• Dogan, T (2019). Zerocoin Protocol, Sigma Protocol and Privacy Coins. https://medium.com/hackernoon/zerocoin-protocol-sigma-protocol-and-privacy-coins-7761db50a0c2
• Groth, J., & Kohlweiss, M. (2015, April). One-out-of-many proofs: Or how to leak a secret and spend a coin. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 253-280). Springer, Berlin, Heidelberg. https://www.iacr.org/archive/eurocrypt2015/90560252/90560252.pdf
• Miers, I., Garman, C., Green, M., & Rubin, A. D. (2013). Zerocoin: Anonymous distributed e-cash from bitcoin. In 2013 IEEE Symposium on Security and Privacy (pp. 397-411). https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6547123
• PIVX. Website. https://pivx.org/ (Accessed on November 19th 2019)
• Ruffing, T., Thyagarajan, S. A., Ronge, V., & Schröder, D. Burning (2018). Burning Zerocoins for Fun and for Profit. https://eprint.iacr.org/2018/612.pdf
• Stanford University. Zero-Knowledge Proofs. https://crypto.stanford.edu/pbc/notes/crypto/zk.html (Accessed on November 19th 2019)
• Veil. Website. https://veil-project.com/ (Accessed on November 19th 2019)
• Zcoin. Website. https://zcoin.io (Accessed on November 19th 2019)
• Zcoin. Privacy-Enhancing Technology: Zerocoin Protocol. https://zcoin.io/tech/ (Accessed on November 19th 2019)
• Zcoin (Yap, R.). Zcoin's Sigma is Released (2019). https://zcoin.io/zcoins-sigma-is-released/
• Zerocash. Website. http://zerocash-project.org/ (Accessed on November 19th 2019)
• Zerocoin. Website. http://zerocoin.org/ (Accessed on November 19th 2019)