A statement from the libsnark team
Alessandro Chiesa, Eli Ben-Sasson, Eran Tromer, and Madars Virza writing:
- 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 Zerocash [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.)