Fix/plonk constraints blowup

[ThomasPiellard]

Summary

The current system to convert a cs to a sparseR1CS doesn't take in account duplicate constraints, factorisation, etc, and a lot of constraints coming from a QAP are converted multiple times, ending up with a blow up of the number of constraints. This PR fixes this issue.

Description

Example

This is an example of a series of Double() called on a G1Affine point, expressed as a QAP, each block corresponds to a single double, reusing the previous result.

(1*1) * (1*1 ) = 1*3
(2*2) * (1*4 ) = 3*3
(1*4) * (1*4 ) = 1*5
(1*1) * (1*4 ) = 1*6
(1*4) * (-2*1 + 1*5 ) = 1*7

(-2*1 + 1*5) * (-2*1 + 1*5 ) = 1*8
(1*9) * (-2*2 + 2*6 + -2*7 ) = 3*8
(1*9) * (1*9 ) = 1*10
(1*9) * (-2*1 + 1*5 ) = 1*11
(1*9) * (4*1 + -2*5 + 1*10 ) = 1*12

(4*1 + -2*5 + 1*10) * (4*1 + -2*5 + 1*10 ) = 1*13
(1*14) * (2*2 + -2*6 + 2*7 + 2*11 + -2*12 ) = 3*13
(1*14) * (1*14 ) = 1*15
(1*14) * (4*1 + -2*5 + 1*10 ) = 1*16
(1*14) * (-8*1 + 4*5 + -2*10 + 1*15 ) = 1*17

(-8*1 + 4*5 + -2*10 + 1*15) * (-8*1 + 4*5 + -2*10 + 1*15 ) = 1*18
(1*19) * (-2*2 + 2*6 + -2*7 + -2*11 + 2*12 + 2*16 + -2*17 ) = 3*18
(1*19) * (1*19 ) = 1*20
(1*19) * (-8*1 + 4*5 + -2*10 + 1*15 ) = 1*21
(1*19) * (16*1 + -8*5 + 4*10 + -2*15 + 1*20 ) = 1*22

We see that each block starts with a square, reusing a linear expression from the previous block. Moreover this linear expression grows, and can be factored using an already computed sub linear expression. The current system doesn't leverage that, and the longer the linear expression the greater the number of corresponding plonk constraints.

Fix

To fix it, toSparseR1CS now uses a record of sorted linear expressions encountered. Each time we encounter a linear expression to split, it is now turned into a "primitive" linear expression, which means that the linear expression becomesprimitive_linearExpression = 1/gcd(coefs) * linearExpression(the sign of the gcd changes according to the sign of the first coef to ensure non ambiguity). The primitive_linearEpression is recursively split, yielding a single term that is equal to the linear expression, but only plonk constraints are used to reach it. It is then multiplied by the original gcd to retrieve the correct value.

The split function now checks if the leftmost part of a linear expression l[:i] for i from len(l)-1 to 0 is in the record, and the rightmost part is recursively split. This strategy covers a lot of sub linear expression, however in order to work all the time, one should in fact check all the possible sub linear expressions (2 to the len(l) possiblities). But since the record stores the sorted linear expression, only very specific patterns are not caught by the fix (I can describe it if needed, briefly it happens only when added terms to a recorded linear expression are in between consecutive terms of the recorded expression after sorting it).

Results

The TestScalarMulG1 circuit took ~430k constraints due to the blow up, now it's at ~7k constraints.

Tests

The regression tests fail, however it's due to the fact that now the plonk circuits take less constraints.