Zcash Counterfeiting Vulnerability Successfully Remediated

Document Outline:

Summary

Eleven months ago we discovered a counterfeiting vulnerability in the cryptography underlying some kinds of zero-knowledge proofs. This post provides details on the vulnerability, how we fixed it and the steps taken to protect Zcash users.

The counterfeiting vulnerability was fixed by the Sapling network upgrade that activated on October 28th, 2018. The vulnerability was specific to counterfeiting and did not affect user privacy in any way. Prior to its remediation, an attacker could have created fake Zcash without being detected. The counterfeiting vulnerability has been fully remediated in Zcash and no action is required by Zcash users.

The counterfeiting vulnerability was discovered by a cryptographer employed by the Zerocoin Electric Coin Company (aka The Zcash Company) on March 1st, 2018. It was not reported publicly at the time in order to protect against it being exploited prior to its remediation, and to provide information and remediated code to other projects that were also vulnerable. We employed stringent operational security measures to keep its existence a secret, even from our own engineers.

We believe that no one else was aware of the vulnerability and that no counterfeiting occurred in Zcash for the following reasons:

  • Discovery of the vulnerability would have required a high level of technical and cryptographic sophistication that very few people possess.
  • The vulnerability had existed for years but was undiscovered by numerous expert cryptographers, scientists, third-party auditors, and third-party engineering teams who initiated new projects based upon the Zcash code.
  • The Zcash Company has seen no evidence that counterfeiting has occurred as might be discovered by monitoring the the total amount of Zcash held in Sprout addresses (i.e., the Sprout shielded pool). As long as the value in the shielded pools are greater than zero, no counterfeiting has been detected. Bitfly’s Zcha.in displays these values on the network statistics page, and Zcash nodes report them in the output of the getblockchaininfo command.
  • Upon discovering the vulnerability, the Zcash Company took extraordinary measures to minimize the possibility of exploitation. The specifics of our steps taken are documented in the detail below.
  • The Zcash Company studied the blockchain for evidence of exploitation: An attack might leave a specific kind of footprint. We found no such footprint.

Although we believe that no counterfeiting occurred, we are monitoring pool totals and will act in accordance with our published defense against counterfeiting in an effort to preserve the monetary supply.

Zcash makes use of the most sophisticated and novel cryptography available on a public blockchain. Pushing cryptographic boundaries is inherently risky and user safety is of highest importance for the Zcash Company. We believe that the steps we have taken to mitigate the issue while working to ensure the safety of Zcash users has been successful. More information on the specific events that transpired from the initial discovery of the counterfeiting vulnerability through this disclosure will be covered in a future post.

Key Points:

  • A counterfeiting vulnerability was discovered in Zcash by a Zcash Company cryptographer.
  • The counterfeiting vulnerability has been fully remediated in Zcash and no action is required by Zcash users.
  • The successful remediation for Sprout addresses was introduced by the Zcash Company in the Zcash Sapling upgrade that occurred on the 28th of October, 2018.
  • The vulnerability was specific to counterfeiting and its exploitation would not have impacted privacy.
  • Zcash has not been susceptible to this attack since the Sapling activation.
  • We have found no evidence that the vulnerability was discovered by anyone else or that counterfeiting occurred.
  • The Zcash Company used best practices in operational security to keep this information private, and responsible disclosure to share it with two affected projects.

Background

On March 1, 2018, Ariel Gabizon, a cryptographer employed by the Zcash Company at the time, discovered a subtle cryptographic flaw in the [BCTV14] paper that describes the zk-SNARK construction used in the original launch of Zcash. The flaw allows an attacker to create counterfeit shielded value in any system that depends on parameters which are generated as described by the paper.

This vulnerability is so subtle that it evaded years of analysis by expert cryptographers focused on zero-knowledge proving systems and zk-SNARKs. In an analysis [Parno15] in 2015, Bryan Parno from Microsoft Research discovered a different mistake in the paper. However, the vulnerability we discovered appears to have evaded his analysis. The vulnerability also appears in the subversion zero-knowledge SNARK scheme of [Fuchsbauer17], where an adaptation of [BCTV14] inherits the flaw. The vulnerability also appears in the ADSNARK construction described in [BBFR14]. Finally, the vulnerability evaded the Zcash Company’s own cryptography team, which includes experts in the field that had identified several flaws in other parts of the system.

Importantly, the [BCTV14] construction did not have a dedicated security proof, as noted in [Parno15], and relied mainly on the [PGHR13] security proof and the similarity between the two schemes. The Zcash Company team did attempt to write a security proof in [BGG17], but it did not uncover this vulnerability. Zcash has since upgraded to a new proving system [Groth16] which has multiple independent proofs and significantly better analysis.

After finding the vulnerability, Ariel immediately contacted another cryptographer at the Zcash Company, Sean Bowe. After Sean confirmed the existence of the vulnerability, Zooko Wilcox (CEO of the Zcash Company) and Nathan Wilcox (CTO of the Zcash Company) were briefed. Through careful coordination, the counterfeiting vulnerability was mitigated in the Zcash network without any known further disclosure outside this group of four people.

With the activation of Sapling, Sprout transactions were moved onto the new [Groth16] proving system, fixing the issue on the Zcash network as described below.

To exploit the counterfeiting vulnerability, an attacker would have needed to possess information found in the large MPC protocol transcript that was made available shortly after the launch of Zcash. This transcript had not been widely downloaded and was removed from public availability immediately upon discovery of the vulnerability to make it more difficult to exploit. The Zcash Company adopted and maintained a cover story that the transcript was missing due to accidental deletion. The transcript was later reconstructed from DVDs collected from the participants of the original ceremony and posted following the Sapling activation.  

We have been monitoring the total of funds in the Sprout pool against time and have not found any indication that any counterfeiting activity has taken place.

Counterfeiting Vulnerability Details

The [BCTV14] parameter setup algorithm, as described by the paper, mistakenly produces extra elements that violate the soundness of the proving system. The construction described by [BCTV14] Appendix B is a variant of the [PGHR13] zk-SNARK scheme with modifications to improve performance and adapt the scheme for the asymmetric pairing setting. This scheme was used in the original launch of Zcash and has been independently implemented by several other projects.

Ariel Gabizon, a cryptographer employed by the Zcash Company at the time of discovery, uncovered a soundness vulnerability. The key generation procedure of [BCTV14], in step 3, produces various elements that are the result of evaluating polynomials related to the statement being proven. Some of these elements are unused by the prover and were included by mistake; but their presence allows a cheating prover to circumvent a consistency check, and thereby transform the proof of one statement into a valid-looking proof of a different statement. This breaks the soundness of the proving system.

The [BGG17] multi-party computation (MPC) protocol that produced Sprout parameters for the [BCTV14] construction follows the paper’s setup procedure, including the computation of the extra elements. These are not included in the actual parameters distributed to Zcash nodes since they are omitted from the parameter file format used by the proving routine implementation of [BCTV14] in the libsnark library (used by Sprout). However, these elements do appear in the MPC ceremony transcript. Consequently, anyone with access to the ceremony transcript would have been able to create false proofs.

What is affected?

While Zcash is no longer affected, any project that depends on the MPC ceremony used by the original Sprout system that was distributed in the initial launch of Zcash is vulnerable. This original Sprout system for shielded funds is comprised of the original Sprout circuit, the [BCTV14] proving system using libsnark, and the parameters generated by an MPC ceremony [BGG17]. It was used by the 1.x series of Zcash software (which also carried the “Sprout” name).

The algorithm described in [BCTV14], before the update corresponding to this disclosure, is vulnerable (though its libsnark implementation, when used with its built-in parameter generation is not). The vulnerability was included in some independent implementations of [BCTV14], such as [snarkjs], even though they do not require an MPC. Similar flaws can be found in the [BBFR14] and [Fuchsbauer17] zk-SNARK schemes.

We do not have an exhaustive list of all systems affected by this vulnerability, and we encourage all users, developers and maintainers of systems using [BCTV14] to take the time to triage this issue and check if they are affected.

Resources:

Original Sprout circuit implementation

Original Sprout zk-SNARK parameters: proving key and verifying key.

Sprout proving and verifying routines

[BCTV14]

libsnark proving system and its Zcash fork

What is not affected?

The newer Sprout-on-Groth16 system used by Zcash mainnet for Sprout addresses ever since the Sapling activation (block 419200 at 28 Oct 2018) is not affected by the counterfeiting vulnerability. It uses a new Sprout circuit, that runs on the Groth16 proving system, with new parameters, and operates on the BLS12-381 curve implemented in the Bellman library. The newer Sapling system for shielded funds, activated at the same time and using a new address format, is not vulnerable either.

The vulnerability is not present in the algorithms of [PGHR13] (which underlies [BCTV14]), nor in [BCGTV13], which used similar techniques. It is also not present in other zk-SNARKs constructions, such as [GM17] or [BG18], or in zero-knowledge proof systems that do not rely on a structured reference string. It is not present in libsnark when used with its built-in parameter generator.

Resources:

New Sprout-on-Groth16 circuit implementation

New Sprout-on-Groth16 zk-SNARK parameters

New Sprout-on-Groth16 proving and verifying routines

Groth16 proving system

Third Party Disclosure

An analysis of the market cap of affected projects revealed that we could reach more than a two thirds majority of affected capital with only two disclosures: Horizen, with whom we already had a reciprocal vulnerability disclosure agreement, and Komodo who we worked with to form a disclosure agreement in order to disclose this issue to them privately.

We established a ninety-day maximum public disclosure timeline with both parties, and provided the conditions required for a workable solution.

Further disclosure would have significantly increased the risk of exploitation of the majority of capital for much smaller gains in terms of coverage of users and capital. To protect the shielded pools of these and other projects, exact details of the cause of the vulnerability were redacted from the private disclosures. It appears that both Horizen and Komodo have taken appropriate actions per our recommendation. We recommend that third parties including affected projects, wallets, and exchanges, carefully consider how best to work through the upgrades needed to fix this issue.

Timeline of Events

01 March 2018

Ariel Gabizon, a cryptographer working for the Zcash Company, discovered the flaw while attending the Financial Cryptography 2018 conference, where he had been invited to present [BGG17] to the Bitcoin’18 workshop. Sean Bowe, a cryptographer at the Zcash Company, and Zooko Wilcox, the CEO of the Zcash Company, were also attending the conference.

The issue was discovered by Ariel the night before his presentation, and he contacted Sean to confirm. Sean met Ariel in person and the two contacted Zooko immediately. Zooko then met Sean and Ariel in person to determine a response strategy. It was quickly determined that the transcript (which would allow an adversary to create false proofs) should be deleted from where it had been publicly made available by the company, since it appeared unlikely that many had downloaded it until that point. Zooko contacted Nathan Wilcox, the CTO of the Zcash Company, to ask him to delete the transcript.

02 March 2018 – 27 October 2018

Nathan deleted the transcript under a coinciding operational security cover story.

Sean had an additional backup of the transcript, which was later transferred into the dual possession of Sean and Zooko (Sean kept an encryption key, while Zooko deposited the USB in a safe deposit box) until it was later decided to destroy the backup entirely.

Two mitigation strategies were proposed. Ariel proposed a mitigation which involved an emergency hardfork that required users to switch to new zk-SNARK parameters that did not suffer from the vulnerability, by re-randomizing or replacing the existing parameters in a subsequent ceremony. Sean proposed that the mitigation be covertly included in the Sapling network upgrade by switching to the Groth16 proving system and parameters constructed in the upcoming Sapling ceremony. The team agreed to adopt Sean’s recommendation.

Covert mitigations were developed and deployed without further known disclosures beyond these four individuals.

28 October 2018

The Sapling network upgrade activated successfully on the Zcash mainnet, removing the counterfeiting vulnerability.

01 November 2018

The director of product security at the Zcash Company, Benjamin Winston, was briefed on the vulnerability and worked with the existing team to prepare disclosure packages for other affected projects.

09 November 2018

Josh Swihart, vice president of marketing and business development at the Zcash Company was briefed on the vulnerability in order to coordinate and prepare communications for two possible scenarios: full disclosure (this and related communications), or a leak by the parties to which information was initially released prior to the full disclosure date.

13 November 2018

The Zcash Company disclosed the impact and fix path of this issue to Horizen’s (previously known as ZenCash) security team ([email protected]) and Komodo ([email protected]) using PGP encrypted email.

The Zcash Company did not disclose the specifics of the vulnerability, only its existence and our recommendation to upgrade their proving system to Groth16. We also did not tell them who else was notified. The complete message and disclosure sent to both Horizen and Komodo is copied below.

Three hours later, Zencash responded to say that they had decrypted our message and that they were looking into the issue.

16 November 2018

Komodo responded to say that they’d received the notification. Later communication made it clear that they were working on a fix.

18 November 2018

Sean reconstructed the transcript from the DVDs collected from the participants of the original ceremony. Sean posted the reconstituted transcript.

10 December 2018

Zcash Company team members (Benjamin, Josh, Zooko) met with the Horizen team by video conference. The Horizen team members present were Alberto Garofollo, Dean Steinbeck, Maurizio Binello, Rob Viglione, Rosario Pabst. In the meeting we discussed the timeline for full disclosure. The Horizen team asked to be given the details of the full disclosure prior to posting. We did not agree to provide them these details.

20 December 2018

Zooko notified and briefed David Campbell, COO of the Zcash Company.

05 January 2019

Zooko notified and briefed Zcash founding scientists Eli-Ben Sasson, Eran Tromer, Madars Virza and Matthew Green. These founding scientists, along with Alessandro Chiesa, were the original authors of [BCTV14] and [BGG17].

08 January 2019

Zooko notified and briefed Zcash founding scientist Alessandro Chiesa.

25 January 2019

Benjamin and Josh briefed John O’Brien, partner at Strange Brew Strategies, who serves as the Zcash Company PR firm, in preparation for supporting press inquiries.

29 January 2019

Sean and Ariel briefed Zcash company cryptographers Daira Hopwood and Jack Grigg.

Benjamin filed for a CVE number for this issue, and received CVE-2019-7167 from mitre.org.

31 January 2019

Benjamin and Josh met with Steve Lee from Komodo to coordinate the public release of information.

01 February 2019

Benjamin and Josh briefed Zcash team members Brad Miller, Elise Hamdon and Paige Peterson for readiness and assistance in preparation for public disclosure. Andy Murray, Zcash Company CFO, was briefed by David Campbell.

04 February 2019   

Jack Gavigan, head of product and regulatory relations was briefed.

The Zcash Foundation and its board members were briefed.

All employees and contractors working full time at the Zcash Company were briefed on a joint conference call.

Community member and forum moderator mineZcash (pseudonym) was briefed.

Sprout ceremony participants Derek Hinch of the NCC Group and John Dobbertin (pseudonym) were briefed.

CVE-2019-7167 details were updated.

05 February 2019

The Zcash Company public disclosure through the blog post, social media channels and direct contacts with other 3rd parties.

CVE-2019-7167 released with the text as shown in this post.

List of References

[BCTV14] https://eprint.iacr.org/2013/879

[PGHR13] https://eprint.iacr.org/2013/279

[BGG17] https://eprint.iacr.org/2017/602

[Parno15] https://eprint.iacr.org/2015/437

[snarkjs] https://github.com/iden3/snarkjs

[Groth16] https://eprint.iacr.org/2016/260

Papers inheriting the soundness vulnerability from [BCTV14]:

[BBFR14] https://eprint.iacr.org/2014/617