Find Best Strategy to Decide When Reducing After Multiplying Non-native Field Elements

[nicholas-mainardi]

The refactoring of NonNativeFieldGadget mentioned in issue #152 should allow to perform more than one multiplication before reducing the result back to a non-native field element. Nonetheless, some preliminary benchmarks suggested that the greedy strategy of performing as many multiplications as possible without reducing the result is not always the one which minimizes the number of constraints. Indeed, the preliminary benchmarks showed that the convenience of performing multiple multiplications without reducing varies with the non-native field (e.g, secp256 or ed25519) and with the surfeit of the operands. Furthermore, the benchmarks showed that batching multiple muls without reducing is advantageous over the strategy of reducing after each multiplication only for a limited number of multiplications, as after a certain number of multiplications the final reduce becomes too much costlier.

Since these benchmarks suggested that the greedy strategy is not the best one, we need to think about optimal strategies that would allow to decide after how many multiplications a reduce should be performed. When tackling this issue, we may start from these 2 ideas:

• The preliminary benchmarks suggest that the final reduce after several muls becomes too much costly when the surfeit of the product overcomes certain thresholds; thus, we may perform more experiments to try identifying these thresholds, which can then be employed to decide when reducing a product
• It should possible to compare, before each multiplication (e.g., in pre_mul_reduce), the cost of reducing the result of the multiplication with and without reducing the input operands before the multiplication: the decision on reducing the input operands can be taken depending on the outcome of such comparison. The idea is that if the final reduce will become too costly after the multiplication, then the comparison should suggest that it is better to reduce one or both the input operands before performing the multiplication, and this should guarantee that we avoid a too much costly reduction. This strategy is based on the assumption that if reduction becomes costlier after n multiplications, then it will be costlier for m > n multiplications, and thus it makes sense to reduce operands before performing the n-th multiplication.