Expand description
§Optimized arkworks field implementations
Specialized field implementations that outperform the generic, Montgomery arithmetic, field implementations provided in arkworks. Currently only one field has been added. Please contribute an implementation! PRs are welcomed!
§Prime field p=18446744069414584321
use ark_ff_optimized::fp64::Fp;An amazing prime with modulus p=2^64−2^32+1. This field has some nice properties (1) Multiplying two 32-bit values does not overflow the field modulus and (2) Checking whether four 16-bit values form a valid field element can be done efficiently. This field is used in Polygon Miden and Polygon Zero. Implementation was sourced from EcGFp5: a Specialized Elliptic Curve and Facebook’s Winterfell repo.
Benchmark | Generic | Specialized (this repo) |
|---|---|---|
Sum of products of size 2 | 18.04 ns | 7.34 ns (🚀 2.46x faster) |
Inverse | 556.74 ns | 283.87 ns (🚀 1.96x faster) |
Legendre for QR | 1.12 us | 596.15 ns (🚀 1.88x faster) |
Naive sum of products of size 2 | 15.41 ns | 8.68 ns (🚀 1.78x faster) |
Deserialize Compressed | 8.82 ns | 4.99 ns (🚀 1.77x faster) |
Deserialize Compressed Unchecked | 8.80 ns | 4.97 ns (🚀 1.77x faster) |
Deserialize Uncompressed | 8.86 ns | 5.16 ns (🚀 1.72x faster) |
Deserialize Uncompressed Unchecked | 8.81 ns | 5.15 ns (🚀 1.71x faster) |
Square Root for QR | 4.43 us | 2.77 us (🚀 1.60x faster) |
Multiplication | 6.15 ns | 4.03 ns (🚀 1.53x faster) |
From BigInt | 5.32 ns | 4.30 ns (✅ 1.24x faster) |
Serialize Uncompressed | 4.72 ns | 3.95 ns (✅ 1.20x faster) |
Into BigInt | 4.72 ns | 3.92 ns (✅ 1.20x faster) |
Serialize Compressed | 4.72 ns | 3.96 ns (✅ 1.19x faster) |
Square | 5.60 ns | 4.88 ns (✅ 1.15x faster) |
Subtraction | 4.09 ns | 3.77 ns (✅ 1.09x faster) |
Addition | 4.11 ns | 3.79 ns (✅ 1.08x faster) |
Negation | 4.21 ns | 3.90 ns (✅ 1.08x faster) |
Double | 4.13 ns | 4.32 ns (❌ 1.04x slower) |
Benchmarked on an M1 Max. Markdown generated with criterion-table. More detailed benchmark info is here
Modules§
- fp31
- An implementation of a 31-bit Mersenne prime (no 2^k roots of unity for k>1)
field with modulus
2^31 - 1. Mersenne primes have a fast reductions to to their binary representation. - fp64
- An implementation of a 64-bit STARK-friendly prime field with modulus
2^64 - 2^32 + 1. The implementation follows https://eprint.iacr.org/2022/274.pdf and the code for the majority of functions was taken and adapted from https://github.com/novifinancial/winterfell