Refactoring of non-native field gadgets

[UlrichHaboeck75]

The current design of non-native field arithmetics treats non-native field gadgets and their multiplication results separately. This causes code duplication, as the arithmetic operations on multiplication results (as well as reduction to normal form) is identical to that of normal non-native gadgets. I therefore propose to

• unify NonNativeFieldGadget and NonNativeFieldMultResultGadget: A unification of these gadgets by a sinlge non-native field gadgets which allows up to the double number of limbs (than that of the modulus) clarifies the architecture of non-native arithmetics, and moreover allows the extend the greedy pre-reduction strategy to multiplication results.

Currently, the parameters are chosen by find_parameters() as the minimum number of constraints for a multiplication and post-reduction of two non-native gadgets, assuming SURFEIT=10. I doubt that this approach is optimal, as the optimum depends on the specific arithmetic "network" to be simulated. For this reason I propose a

• different treatment of parameters: Let us introduce separate NonNativeFieldParameters to allow a manual specification, and let us run find_parameters() over the real constraint counts provided by ConstraintSystem. As reference circuit one can use again multiplication with post-reduction, or a custom circuit provided by the user.

A further improvement on the code structure would be to

• implement big integer gadgets: The key principle of simulating non-native field arithmetics is its translation of mod p identities to big integer equalities. In particular, the core piece is the grouped normalization procedure group_and_check_equality() , which checks the equality of big integers with oversized limbs. As big integer gadgets might be useful in application circuits anyway, I propose to implement the simulation of non-reduced big integer arithmetics, and build the non-native field arithmetics on top of it.

[DDT92]

I would propose also to keep track of the value bounds of the gadgets, instead of length bounds and number of additions. The struct NonNativeFieldGadget should have two components:

• limbs, which we already have;
• limbs_max, which is a vector of ConstraintF, keeping track of the maximum possible value of limbs[i] for each i.

In my opinion, these would the advantages of doing it:

• A bit less constraints due to more precise estimates;
• Code more elegant and readable: the operations that you do on the component "limbs" of the gadget are the same (excluding enforcing constraints) that we do on the component "limbs_max";
• Code less error-prone: working with surfeit and number of additions is very tricky. For example if often happens that we underestimate or overestimate the number of constraints needed for allocating a specific variable.

I do not see particular disadvantages, apart from the fact that it would be a rather radical change, requiring time which would be subtracted to other tasks.

[UlrichHaboeck75]

@DDT92 as discussed offline, I fully agree.