Unlike the system from [BCTV14a], which internally operates on Quadratic Arithmetic Programs (which arise from R1CSs, systems of constraints of the form <a, w> * <b, w> = <c, w>), [GM17] operates on Square Arithmetic Programs (which arise from constraints of the form (<a, w>)² = <c, w>). It turns out that an R1CS constraint can be converted into two equivalent SAP-compatible constraints at the cost of introducing an extra variable. This pull request includes an implementation of SAPs along with an R1CS→SAP reduction that follows the existing R1CS→QAP reduction but also performs this additional conversion.
It should be noted that the proof system relies on an assumption that is stronger than KEA used in most LIP SNARK works, but weaker than generic group model (used in Groth'16).
When compared to [BCTV14a] on the same input R1CS systems, [GM17] is slower but produces shorter proofs (just 2 elements in G1 and 1 in G2).
Here are the results of some benchmarking of our implementations of [BCTV14a] and [GM17] on an R1CS instance with 100 000 constraints and 1000 inputs:
This pull request implements the proof system presented in Groth and Maller's IACR-CRYPTO-2017 paper.
Unlike the system from [BCTV14a], which internally operates on Quadratic Arithmetic Programs (which arise from R1CSs, systems of constraints of the form <a, w> * <b, w> = <c, w>), [GM17] operates on Square Arithmetic Programs (which arise from constraints of the form (<a, w>)² = <c, w>). It turns out that an R1CS constraint can be converted into two equivalent SAP-compatible constraints at the cost of introducing an extra variable. This pull request includes an implementation of SAPs along with an R1CS→SAP reduction that follows the existing R1CS→QAP reduction but also performs this additional conversion.
It should be noted that the proof system relies on an assumption that is stronger than KEA used in most LIP SNARK works, but weaker than generic group model (used in Groth'16).
When compared to [BCTV14a] on the same input R1CS systems, [GM17] is slower but produces shorter proofs (just 2 elements in G1 and 1 in G2).
Here are the results of some benchmarking of our implementations of [BCTV14a] and [GM17] on an R1CS instance with 100 000 constraints and 1000 inputs:
r1cs_ppzksnark)r1cs_se_ppzksnark)