perf: check for duplicate constraints during building CS

[ivokub]

0 and 2 are essentially the same in http://play.gnark.io/?id=sdvlixeejg

[gbotrel]

for R1CS builder;

newR1C could do an optimistic check with a hashcode of the linear expressions against a hash map to see if we already have recorded a similar constraint.

But, we must know:

1. The new "internalVariable" is it in L, R or O ?
2. Is it reference previously in other constraints?

If answer to 2 is yes, then we probably need to maintain a sort of "alias" list, and do a post compile phase where we merge all variables that are "aliases" (technically interchangeable when they appear in constraints).

[ivokub]

There is also a bit newer issue #243, which considers when two constraints can be merged in plonk (for example, can merge addition and multiplication). It seems that this issue should also cover the case of duplicate constraints in plonk.

In order to ensure that the behavior is uniform over all API operations, we should first ensure that all constraint insertions are performed through a single method (system.addConstraint). There are a some cases where the constraints are added directly (e.g. https://github.com/ConsenSys/gnark/blob/develop/frontend/cs/r1cs/api.go#L417, but need to verify the whole codebase) which could possibly pass the initial filtering step.

In order to hash the linear expression, we need to have some kind of fast set hash. I'd have to check, but maybe something like FNV+XOR would be good enough? But, when hashing, we need to have a fixed value for the new internal variable added in the constraint as otherwise the set hashes of the same constraints (modulo the new internal variable) differ due to the difference in new internal variable ID. But for the hashing purposes, we can replace the ID of the new internal variable with a fixed one.

Regarding 2. - it seems a bit difficult problem. We do not want to have a full n-m mapping (between all constraints and all internal variables) as it may grow rather large. Maybe a kind of "transaction" for the internal variable (the phase where it can be recorded in new constraints as a "new" variable), such that we can eagerly perform the merging after every transaction closes.