24 unstable releases (9 breaking)
0.10.1 | Oct 30, 2024 |
---|---|
0.9.3 | Sep 25, 2024 |
0.9.0 | May 9, 2024 |
0.8.4 | Mar 29, 2024 |
0.2.0 | Aug 24, 2021 |
#81 in Cryptography
7,548 downloads per month
Used in 50 crates
(14 directly)
315KB
5.5K
SLoC
Winter math
This crate contains modules with mathematical operations needed in STARK proof generation and verification.
Finite field
Finite field module implements arithmetic operations in STARK-friendly finite fields. The operation include:
- Basic arithmetic operations: addition, multiplication, subtraction, division, inversion.
- Drawing random and pseudo-random elements from the field.
- Computing roots of unity of a given order.
Currently, there are three implementations of finite fields:
- A 128-bit field with modulus 2128 - 45 * 240 + 1. This field was not chosen with any significant thought given to performance, and the implementation of most operations is sub-optimal as well. Proofs generated in this field can support security level of ~100 bits. If higher level of security is desired, proofs must be generated in a quadratic extension of the field.
- A 62-bit field with modulus 262 - 111 * 239 + 1. This field supports very fast modular arithmetic including branchless multiplication and addition. To achieve adequate security (i.e. ~100 bits), proofs must be generated in a quadratic extension of this field. For higher levels of security, a cubic extension field should be used.
- A 64-bit field with modulus 264 - 232 + 1. This field supports very fast modular arithmetic (comparable to the 62-bit field described above), provides a fully constant-time implementation, and has a number of other attractive properties. To achieve adequate security (i.e. ~100 bits), proofs must be generated in a quadratic extension of this field. For higher levels of security, a cubic extension field should be used.
Extension fields
Currently, the library provides a generic way to create quadratic and cubic extensions of supported STARK fields. This can be done by implementing 'ExtensibleField' trait for degrees 2 and 3.
Quadratic extension fields are defined using the following irreducible polynomials:
- For
f62
field, the polynomial is x2 - x - 1. - For
f64
field, the polynomial is x2 - x + 2. - For
f128
field, the polynomial is x2 - x - 1.
Cubic extension fields are defined using the following irreducible polynomials:
- For
f62
field, the polynomial is x3 + 2x + 2. - For
f64
field, the polynomial is x3 - x - 1. - For
f128
field, cubic extensions are not supported.
Polynomials
Polynomials module implements basic polynomial operations such as:
- Evaluation of a polynomial at a single point.
- Interpolation of a polynomial from a set of points (using Lagrange interpolation).
- Addition, multiplication, subtraction, and division of polynomials.
- Synthetic polynomial division (using Ruffini's method).
Fast Fourier transform
FFT module contains operations for computing Fast Fourier transform in a prime field (also called Number-theoretic transform). This can be used to interpolate and evaluate polynomials in O(n log n) time as long as the domain of the polynomial is a multiplicative subgroup with size which is a power of 2.
Crate features
This crate can be compiled with the following features:
std
- enabled by default and relies on the Rust standard library.concurrent
- impliesstd
and also enables multi-threaded execution for some of the crate functions.no_std
- does not rely on Rust's standard library and enables compilation to WebAssembly.
To compile with no_std
, disable default features via --no-default-features
flag.
Concurrent execution
When compiled with concurrent
feature enabled, the following operations will be executed in multiple threads:
- fft module:
evaluate_poly()
evaluate_poly_with_offset()
interpolate_poly()
interpolate_poly_with_offset()
get_twiddles()
get_inv_twiddles()
- utils module:
get_power_series()
get_power_series_with_offset()
add_in_place()
mul_acc()
batch_inversion()
The number of threads can be configured via RAYON_NUM_THREADS
environment variable, and usually defaults to the number of logical cores on the machine.
License
This project is MIT licensed.
Dependencies
~0–355KB