Ark-ff Small Field Support

[z-tech]

Description

Arkworks Prime fields are instantiated using procedural macros (e.g. #[derive(MontConfig)]) that rely on the num_bigint::BigInt library. The flexibility of this approach allows for arbitrary-length prime moduli and good performance, but is slower than system native arithmetic for small moduli (as demonstrated in benchmark evaluations).

To capture this optimization, in the linked PR we introduce a new procedural macro, SmallFp, which targets primes < 128 bits. It generates field arithmetic using the smallest appropriate integer primitive (u8, u16, u32, u64, u128).

Please see slides for more information: https://andrewzitek.xyz/images/small_fp_slides.pdf

#TL;DR

The primary motivation of this PR is to create a generic path toward vectorized/ SIMD instruction optimizations for finite fields in Arkworks.

In the process, we pick up a non-trivial performance boost in serial.

• We introduce SmallFp, a procedural macro for instantiating prime fields with modulus < 2^127
• In the place of BigInt, this macro uses native integer types (u8, u16, u32, u64, u128)
• For a summary of results and benchmarking please see section "results" in slides
• There a no breaking changes in this effort

This work was done in collaboration with @benbencik