A statement from Least Authority
Zooko Wilcox-O’Hearn writing:
About us
At Least Authority, our mission is to bring verifiable end-to-end security to everyone. As a part of this mission, we have been collaborating with the scientists behind zk-SNARKS, libsnark, and Zcash. These are some of the most promising new advances in cryptography, and we are exploring whether they can be used to provide more safety and freedom to all users of the Internet.
We’re not ready to post about our specific plans, but we want to address the recent news that a bug has been discovered in libsnark.
A bug in libsnark
Recently there was a bug reported by Bryan Parno from Microsoft Research. Because libsnark is used to implement the cryptography in Zcash, some people have worried that this bug could have led to a critical failure in Zcash, if Zcash had already been deployed before the bug was discovered.
We asked some of the authors of libsnark to comment about the bug.
How we work
Before turning the floor over to the libsnark scientists, I’d like to make two points myself:
First, in the long run, having independent scientists like Bryan Parno study the zk-SNARK literature and the libsnark implementation in search of flaws is the right way for a cryptographic innovation like this to get vetted and improved. It is encouraging to see this kind of scientific scrutiny happening, and we are grateful for the work he and other researchers have done.
Second, before we at Least Authority deploy new software or cryptography for our users to rely on, we perform our own internal security audits and solicit external security audits from independent experts. We have not yet performed that process for libsnark, and we would do so before deploying any libsnark-based systems to our users.
If you’re interested in our history, here are the reports from some of the security audits that we’ve performed on behalf of others, and here is a contest we organized for others to find security flaws in our flagship product.
We also notified the authors of another zk-SNARK implementation named snarklib, so that they could fix the bug as it applies to snarklib.
A statement from the libsnark team
Alessandro Chiesa, Eli Ben-Sasson, Eran Tromer, and Madars Virza writing:
Summary
- Bryan Parno identified a bug in the R1CS-to-QAP reduction in libsnark.
- Current libsnark includes a full and general fix, in commit f55afd03.
- The fix has negligible performance implications when the number of constraints is much larger than the number of inputs, as is typical in SNARK applications, including Zerocash.
- Known users of libsnark have been notified, so that they may update their code to the latest release.
More details about the bug and its fix
One of the preprocessing SNARKs in libsnark represents NP statements to be proved as rank-1 constraint systems (R1CS). Internally, a given R1CS is converted into a Quadratic Arithmetic Program (QAP), an algebraic representation of the NP statement. If the R1CS has an input of size n, the QAP includes polynomials A_0,…,A_n over a finite field F and, for the soundness of the SNARK to hold, these polynomials must be linearly independent over F. The R1CS-to-QAP reduction, which converts an R1CS into a QAP, should ensure this independence. Until recently, libsnark’s implementation of that reduction had a bug: it did not explicitly ensure this independence.
This bug does not always manifest, because a R1CS may naturally induce a QAP in which A_0,…,A_n are linearly independent. However, the linear independence should be assured generically for all possible R1CS. The straightforward fix to do so is as follows.
In the following, consider an R1CS with M constraints, N variables, and n inputs. (The n inputs correspond to variables that are fixed to known values by the NP statement; the remaining N-n variables are part of the witness, and can take on any value.) The fix is to add n+1 dummy constraints that ensure that the constructed QAP always has linearly independent A_0,…,A_n. This causes the degree of the constructed QAP to increase from M to M+n+1. (An optimization, not implemented in our code, is to only add as many additional constraints as needed to ensure that the constructed QAP satisfies the desired property; this number is at least 0 and at most n+1.)
The increase has negligible performance implications when M is much larger than n. Our experiments show that this is the case for all the applications that we considered. For both SNARKs for TinyRAM [BCTV14, USENIX Security] and Scalable Zero-Knowledge [BCTV14, CRYPTO], the increase in the number of constraints is at most 0.007%. For Zcash [BCGGMTV14, S&P], the increase is smaller: 0.00022%. More generally, we believe that M is much larger than n for most interesting applications, e.g., for constraint systems that verify cryptographic computations.
For more details, see Remark 2.5 in the extended version (revised on 9 May 2015) of Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. (Note that the paper is phrased in terms of arithmetic circuits rather than rank-1 constraint systems, so that the paper’s remark and the explanation above differ slightly.)