This is based on April’s IFT ZK Call. Visit the IFT ZK Meeting Notes for additional resources, and the video (TO BE POSTED) of this meeting.
In 2018, the Electric Coin Company released released the Sapling update for Zcash. Sapling brought a change in zk-SNARKs; Groth16 replaced the optimized version of Pinocchio, BCTV14, that Sprout had used. The critical reason for this change was kept quiet for a few months. A vulnerability existed with BCTV14 that risked Zcash and other privacy currencies.
BCTV14 could be exploited by a malicious party to forge a proof that would pass verification checks. In Zcash, Komodo and Horizen this exploit would result in infinite inflation. A malicious individual could forge a counterfeit transaction to create large quantity of funds. Fortunately, this did not happen.
Timeline of the exploit discovery
Pinocchio was a popular pairing-based zk-SNARK. Nowadays, Pinocchio has been supplanted by Groth16. Like Groth16, Pinocchio uses public parameters on a per circuit basis. These public parameters are constructed in terms of secret values often referred to as trapdoors.
If any individual possesses the trapdoors, then she could forge a proof. Multiparty computation (MPC) protocols are used to ensure that these public parameters are correctly computed and no one possesses these trapdoors. A MPC ceremony allows for anyone to provide additional randomness in the generation of the trapdoors. Further, as long as one participate is honest, the trapdoors cannot be recovered. Zcash performed such a ceremony for the version of Pinocchio (BCTV14) that they used.
While preparing a presentation on Zcash’s MPC ceremony in March 2018, Ariel Gabizon discovered a critical flaw in BCTV14. A flaw that would allow a malicious user with the public parameters to generate Zec. Acting quickly, the transcript of MPC for Zcash’s public parameters were accidentally deleted. A backup was maintained in a secure location, but offline.
Over course of months, options were considered among a few Zcash employees how to mitigate the risk. Zcash could hardfork redoing the MPC ceremony or change over to Groth16. In October 2018, Groth16 replaced BCTV16 in a planned upgrade.
Once Zcash was secure, the Electric Coin Company (ECC) began communicating with Komodo and Horizen. In these communications, the ECC disclosed the existence of the exploit in BCTV14 but not the specifics of the exploit. Additionally, ECC recommended adopting Groth16 as a solution for removing the exploit.
In February 2019, ECC made the exploit in BCTV14 public.
The exploit
The infinite inflation glitch exploits a flaw that lurks within BCTV14’s public parameters.
The public parameters for BCTV14 are circuit specific. In particular, functions a(X), b(X), c(X) that represent the circuit’s wire assignments are incorporated within the public parameters. Additionally, the public parameters for BCTV14 are computed using trapdoors \alpha_A,\alpha_B,\alpha_C, \beta, \gamma, \theta, \rho_A, \rho_B \in \mathbb{Z} and group elements g_1 \in \mathbb{G}_1 and g_2 \in \mathbb{G}_2.
| \alpha_B\cdot g_1 | \beta\gamma\cdot g_1 |
|---|---|
| \{\theta^i\cdot g_1\}_{i=0}^{d} | \{\rho_A a_i(\theta)\cdot g_1\}^m_{i=0} |
| \{\alpha_A \rho_A a_i(\theta)\cdot g_1\}_{i=0}^\ell | \{\alpha_A \rho_A a_i(\theta)\cdot g_1\}_{i=\ell+1}^m |
| \{\alpha_B \rho_B b_i(\theta)\cdot g_1\}_{i=0}^m | \{ \rho_A \rho_B c_i(\theta)\cdot g_1\}^m_{i=0} |
| \{\alpha_C \rho_A \rho_B c_i(\theta)\cdot g_1\}_{i=0}^m | \{\beta(\rho_A a_i(\theta) + \rho_B b_i(\theta) + \rho_A \rho_B c_i(\theta))\cdot g_1\}_{i=0}^m |
| 1\cdot g_2 | \alpha_A\cdot g_2 |
| \alpha_C\cdot g_2 | \gamma\cdot g_2 |
| \beta \gamma\cdot g_2 | \rho_A \rho_B z(\theta)\cdot g_2 |
| \{\rho_B b_i(\theta)\cdot g_2\}_{i=0}^{m} |
In this table of public parameters, one entry is dangerous: \{\alpha_A \rho_A a_i(\theta)\cdot g_1\}_{i=0}^\ell. We will demonstrate how a proof can be forged using these elements.
To forge a proof, we use a valid proof as our basis. Specifically, we take the valid proof (\pi_A, \pi_A',\pi_B',\pi_C, \pi_C', \pi_K, \pi_H, \pi_B) \in \mathbb{G}_1^7 \times \mathbb{G}_2 for public inputs \mathbf{x} \in \mathbb{Z}_p^{\ell+1} with \mathbf{x}[0] = 1.
A Verifier checks this proof with the following identity checks:
- e(\pi'_A, g_2) \stackrel{?}{=} e(\pi_A, \alpha_A \cdot g_2),
- e(\pi_B', g_2) \stackrel{?}{=} e(\alpha_B\cdot g_1, \pi_B),
- e(\pi'_C, g_2) \stackrel{?}{=} e(\pi_C, \alpha_C \cdot g_2),
- e(\pi_K, \gamma \cdot g_2) \stackrel{?}{=} e(\mathsf{PI}(\mathbf{x}) + \pi_A + \pi_C, \beta \gamma \cdot g_2) \cdot e(\beta \gamma\cdot g_1, \pi_B), and
- e(\mathsf{PI}(\mathbf{x}) + \pi_A, \pi_B) \stackrel{?}{=} e(\pi_C, g_2) \cdot e(\pi_H, z(\theta) \rho_A \rho_B \cdot g_2)
where \mathsf{PI}(\mathbf{X}) :=\rho_A a_0(\theta) \cdot g_1 + \sum_{i=1}^\ell \mathbf{X}[i] \rho_A a_i(\theta) \cdot g_1 \in \mathbb{G}_1.
To forge a proof with different public inputs \mathbf{y} \in \mathbb{Z}^{\ell+1}, with \mathbf{y}[0]=1), we need to adjust \pi_A. \pi_A appears in identities 4 and 5 along with \mathsf{PI}(\mathbf{x}). Additionally, \pi_A is used in identity 1 with \pi_A'. We note that \pi_A \alpha_A = \pi_A'; we have omitted proof generation to focus on the exploit.
We replace \pi_A with \eta_A := \pi_A + \sum_{i=1}^\ell (\mathbf{x}[i] - \mathbf{y}[i]) \rho_A a_i(\theta) \cdot g_1, and \pi_A' with \eta_A' = \eta_A \cdot \alpha_A.
Our selection of \eta_A and \eta_A' ensures that identity 1 holds. Additionally, 4 and 5 follows from \mathsf{PI}(\mathbf{y}) + \eta_A = \mathsf{PI}(\mathbf{x}) + \pi_A.
Hence, by using a valid proof (\pi_A, \pi_A',\pi_B',\pi_C, \pi_C', \pi_K, \pi_H, \pi_B) \in \mathbb{G}_1^7 \times \mathbb{G}_2 for public inputs \mathbf{x} \in \mathbb{Z}_p^{\ell+1} we have forged the proof (\eta_A, \eta_A',\pi_B',\pi_C, \pi_C', \pi_K, \pi_H, \pi_B) \in \mathbb{G}_1^7 \times \mathbb{G}_2 for public inputs \mathbf{y} \in \mathbb{Z}^{\ell+1}. This forged proof will be accepted with probability 1!
Unused exploit?
The real question is: was this exploit known and abused? Unlikely.
The vulnerability existed within BCTV14 for about four years without being detected. The detection of the exploit required deep technical and cryptographical knowledge. This reduces the number of people who may have spotted the flaw.
ECC acted quickly to removed the MPC transcript. This prevented additional downloads of the transcript that was necessary to forge a transaction. Further, prior to the transcript’s removal, it had hardly been accessed.
ECC did not detect any abuse of the exploit.
Finally, ECC handled the exploit quietly and discreetly. Only a few within ECC knew about the exploit prior to Sapling. Once ECC had secured Zcash, their communications with Komodo and Horizen was carefully crafted to avoid compromising another project.
We note that ECC’s approach for notifying other projects was not perfect. ECC has been criticized for not contacting every affected project before publicly announcing the infinite inflation glitch. However, ECC has defended their selection of projects based on market value to limit the damage.
Takeaway lessons
What lessons should we take away from the infinite inflation glitch? How could this be prevented in the future?
The lack of full and dedicated security proof for BCTV14 gave false assurance in the soundness of the zk-SNARK. The infinite inflation glitch eluded researchers for years. But, high level of knowledge and skills for entry is not security.
Audits and reviews performed by the community as a whole serves as a crucial safeguard. While peer-review process did not catch the flaws in BCTV14, continual audits performed by engineers and researchers working to gain a deeper understanding can reveal these issues.
The public parameters that can be exploited from BCTV14 were not used in proof generation or verification. Some implementations of BCTV14 omitted these values altogether. As a consequence of this, these impementations were secure against the infinite inflation glitch. This is an interesting software engineering for storage optimizations.