Optimising algorithms for constraint systems

Where constraints are in the format of:

(A * B) - C == 0

or

(A * B) == C

The number of constraints increases the proving time, but the complexity of the constraint also increases proving time, and the complexity of the B parameter increases proving time more than then A or C parameters.

Each of the parameters, A, B and C are linear combinations, which are the additive sum of a constant coefficient and a variable. The values of both coefficients and variables exist within a Galois field of around 254 bits. An example of a linear combination is:

10*X + 3892*Y + 8292*Z

Where the constant coefficients are:

• 10
• 3892
• 8292

And the variables are:

• X
• Y
• Z

The constants are essentially hard-coded and cannot be modified from proof to proof, but the variables can be assigned any users input for each proof. If you wanted to add X, Y and Z together you'd use the coefficient 1 for each:

1*X + 1*Y + 1*Z == X+Y+Z

Using -1 as the coefficient negates that item, e.g.

1*X + -1*Y + -1*Z == X-Y-Z

Where each coefficient*variable is a "Term" in the linear combination, and there can be any number of terms in each of the linear combinations for A, B and C. Increasing the number of terms increases the complexity, and thus increases the proving time.

Questions / TODO:

• How does the complexity of the A, B and C parameters affect proving time
• Where the terms are binary, that is faster than when they operate over the full-range of GF(p)
• Terms in B are more complex to compute than an equivalent number in A and C
• What are the ratios?
• How can this guide optimisation strategies?

---