search

arkworks-rs / snark

Interfaces for Relations and SNARKs for these relations
https://www.arkworks.rs
Apache License 2.0
776 stars 209 forks source link

Add constant folding to FpGadget<F> #226

Closed ValarDragon closed 4 years ago

ValarDragon commented 4 years ago

This PR adds constant folding to FpGadget. The only place where constant folding needs special casing is from within .mul(). (Square reduces to a call to mul) Constant folding for this is achieved by checking if either argument to mul is a constant, and if so doing mul_by_constant.

Currently this checks if its a constant by a newly implemented method on linear combination. While not shown in the tests (as micro-counting number of constraints isn't really well supported), I have confirmed in a separate circuit that this does lower the number of constraints when alloc_constant is used.

Pratyush commented 4 years ago

Great, thanks! Do you think it makes sense to extend this also to the extension field and curve gadgets? (Doesn't have to be in this PR)

Alternatively, as a longer term goal, I want to integrate duplicate detection into the ConstraintSystem interface directly, so that all gadgets would benefit from this.

ValarDragon commented 4 years ago

Yeah this could totally be extended to extension fields / curve gadgets!

The general optimization would be if you have a constraint that looks like (Linear combination) * (constant) = (Variable) you just replace variable everywhere with the scaled L.C.. (This conflicts with the optimization for removing high arity constraints, but the latter optimization should probably be a global optimization rather than something done while building constraints)