Rank-1 constraint systems as used in Groth16 and other similar LIP-based SNARKs enjoy "free" addition gates of arbitrary arity. That is, the cost of MSMs in these SNARKs does not scale with the density of the R1CS matrices.
This is not the case for SNARKs like Marlin and Fractal. In these SNARKs, MSM cost scales with matrix density. One way to reduce density is to "outline" commonly used linear combinations: instead of substituting a LC into the constraints that uses it, one instead creates a new variable from the LC, and uses this variable in those constraints. This optimization is beneficial as long as the number of variables does not grow too large. This issue tracks ideas and progress on implementing an algorithm for performing this optimization.
Pratyush
commented
3 years ago
Rank-1 constraint systems as used in Groth16 and other similar LIP-based SNARKs enjoy "free" addition gates of arbitrary arity. That is, the cost of MSMs in these SNARKs does not scale with the density of the R1CS matrices.
This is not the case for SNARKs like Marlin and Fractal. In these SNARKs, MSM cost scales with matrix density. One way to reduce density is to "outline" commonly used linear combinations: instead of substituting a LC into the constraints that uses it, one instead creates a new variable from the LC, and uses this variable in those constraints. This optimization is beneficial as long as the number of variables does not grow too large. This issue tracks ideas and progress on implementing an algorithm for performing this optimization.