Lib.rs

› Cryptography
#finite-fields #elliptic #field #elliptic-curve #arkworks #prime-field #specialized

nightly no-std ark-ff-optimized

Optimized field implementations that outperform the generic field implementations in arkworks

by Andrew Milson

2 releases

0.4.1 May 16, 2023
0.4.0 Feb 9, 2023

#2039 in Cryptography

Download history 9/week @ 2024-06-17 18/week @ 2024-06-24 26/week @ 2024-07-01 4/week @ 2024-07-08 55/week @ 2024-07-15 15/week @ 2024-07-22 16/week @ 2024-07-29 10/week @ 2024-08-05 10/week @ 2024-08-12 4/week @ 2024-08-19 36/week @ 2024-08-26 13/week @ 2024-09-02 18/week @ 2024-09-09 22/week @ 2024-09-16 42/week @ 2024-09-23 16/week @ 2024-09-30

100 downloads per month
Used in 2 crates

MIT license

45KB
1K SLoC

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

Dependencies

~2.7–3.5MB
~72K SLoC