winter_math/field/
traits.rs

1// Copyright (c) Facebook, Inc. and its affiliates.
2//
3// This source code is licensed under the MIT license found in the
4// LICENSE file in the root directory of this source tree.
5
6use alloc::vec::Vec;
7use core::{
8    fmt::{Debug, Display},
9    ops::{
10        Add, AddAssign, BitAnd, Div, DivAssign, Mul, MulAssign, Neg, Shl, Shr, ShrAssign, Sub,
11        SubAssign,
12    },
13};
14
15use utils::{AsBytes, Deserializable, DeserializationError, Randomizable, Serializable};
16
17// FIELD ELEMENT
18// ================================================================================================
19/// Defines an element in a finite field.
20///
21/// This trait defines basic arithmetic operations for elements in
22/// [finite fields](https://en.wikipedia.org/wiki/Finite_field) (e.g. addition subtraction,
23/// multiplication, division) as well as several convenience functions (e.g. double, square cube).
24/// Moreover, it defines interfaces for serializing and deserializing field elements.
25///
26/// The elements could be in a prime field or an extension of a prime field. Currently, only
27/// quadratic and cubic field extensions are supported.
28pub trait FieldElement:
29    Copy
30    + Clone
31    + Debug
32    + Display
33    + Default
34    + Send
35    + Sync
36    + Eq
37    + PartialEq
38    + Sized
39    + Add<Self, Output = Self>
40    + Sub<Self, Output = Self>
41    + Mul<Self, Output = Self>
42    + Div<Self, Output = Self>
43    + AddAssign<Self>
44    + SubAssign<Self>
45    + MulAssign<Self>
46    + DivAssign<Self>
47    + Neg<Output = Self>
48    + From<u32>
49    + From<u16>
50    + From<u8>
51    + TryFrom<u64>
52    + TryFrom<u128>
53    + for<'a> TryFrom<&'a [u8]>
54    + ExtensionOf<<Self as FieldElement>::BaseField>
55    + AsBytes
56    + Randomizable
57    + Serializable
58    + Deserializable
59{
60    /// A type defining positive integers big enough to describe a field modulus for
61    /// `Self::BaseField` with no loss of precision.
62    type PositiveInteger: Debug
63        + Copy
64        + PartialEq
65        + PartialOrd
66        + ShrAssign
67        + Shl<u32, Output = Self::PositiveInteger>
68        + Shr<u32, Output = Self::PositiveInteger>
69        + BitAnd<Output = Self::PositiveInteger>
70        + From<u32>
71        + From<u64>;
72
73    /// Base field type for this finite field. For prime fields, `BaseField` should be set
74    /// to `Self`.
75    type BaseField: StarkField;
76
77    /// Extension degree of this field with respect to `Self::BaseField`. For prime fields,
78    /// extension degree should be set to 1.
79    const EXTENSION_DEGREE: usize;
80
81    /// Number of bytes needed to encode an element
82    const ELEMENT_BYTES: usize;
83
84    /// True if internal representation of the element is the same as its canonical representation.
85    const IS_CANONICAL: bool;
86
87    /// The additive identity.
88    const ZERO: Self;
89
90    /// The multiplicative identity.
91    const ONE: Self;
92
93    // ALGEBRA
94    // --------------------------------------------------------------------------------------------
95
96    /// Returns this field element added to itself.
97    #[inline]
98    #[must_use]
99    fn double(self) -> Self {
100        self + self
101    }
102
103    /// Returns this field element raised to power 2.
104    #[inline]
105    #[must_use]
106    fn square(self) -> Self {
107        self * self
108    }
109
110    /// Returns this field element raised to power 3.
111    #[inline]
112    #[must_use]
113    fn cube(self) -> Self {
114        self * self * self
115    }
116
117    /// Exponentiates this field element by `power` parameter.
118    #[must_use]
119    fn exp(self, power: Self::PositiveInteger) -> Self {
120        self.exp_vartime(power)
121    }
122
123    /// Exponentiates this field element by `power` parameter.
124    /// This function is expressly variable time, to speed-up verifier computations.
125    #[must_use]
126    fn exp_vartime(self, power: Self::PositiveInteger) -> Self {
127        let mut r = Self::ONE;
128        let mut b = self;
129        let mut p = power;
130
131        let int_zero = Self::PositiveInteger::from(0u32);
132        let int_one = Self::PositiveInteger::from(1u32);
133
134        if p == int_zero {
135            return Self::ONE;
136        } else if b == Self::ZERO {
137            return Self::ZERO;
138        }
139
140        while p > int_zero {
141            if p & int_one == int_one {
142                r *= b;
143            }
144            p >>= int_one;
145            b = b.square();
146        }
147
148        r
149    }
150
151    /// Returns a multiplicative inverse of this field element. If this element is ZERO, ZERO is
152    /// returned.
153    #[must_use]
154    fn inv(self) -> Self;
155
156    /// Returns a conjugate of this field element.
157    #[must_use]
158    fn conjugate(&self) -> Self;
159
160    // BASE ELEMENT CONVERSIONS
161    // --------------------------------------------------------------------------------------------
162
163    /// Return base filed element component of this field element at the specified index `i`.
164    ///
165    /// # Panics
166    /// Panics if the specified index is greater than or equal to `Self::EXTENSION_DEGREE`.
167    fn base_element(&self, i: usize) -> Self::BaseField;
168
169    /// Converts a slice of field elements into a slice of elements in the underlying base field.
170    ///
171    /// For base STARK fields, the input and output slices are the same. For extension fields, the
172    /// output slice will contain decompositions of each extension element into underlying base
173    /// field elements.
174    fn slice_as_base_elements(elements: &[Self]) -> &[Self::BaseField];
175
176    /// Convert a slice of base field elements into a slice of field elements.
177    ///
178    /// For base STARK fields, the input and output slices are the same. For extension fields, the
179    /// output slice will contain a composition of base field elements into extension field
180    /// elements.
181    ///
182    /// # Panics
183    /// Panics if the the length of the provided slice is not divisible by `Self::EXTENSION_DEGREE`.
184    fn slice_from_base_elements(elements: &[Self::BaseField]) -> &[Self];
185
186    // SERIALIZATION / DESERIALIZATION
187    // --------------------------------------------------------------------------------------------
188
189    /// Converts a list of elements into a list of bytes.
190    ///
191    /// The elements may be in the internal representation rather than in the canonical
192    /// representation. This conversion is intended to be zero-copy (i.e. by re-interpreting the
193    /// underlying memory).
194    fn elements_as_bytes(elements: &[Self]) -> &[u8];
195
196    /// Converts a list of bytes into a list of field elements.
197    ///
198    /// The elements are assumed to encoded in the internal representation rather than in the
199    /// canonical representation. The conversion is intended to be zero-copy (i.e. by
200    /// re-interpreting the underlying memory).
201    ///
202    /// # Errors
203    /// An error is returned if:
204    /// * Memory alignment of `bytes` does not match memory alignment of field element data.
205    /// * Length of `bytes` does not divide into whole number of elements.
206    ///
207    /// # Safety
208    /// This function is unsafe because it does not check whether underlying bytes represent valid
209    /// field elements according to their internal representation.
210    unsafe fn bytes_as_elements(bytes: &[u8]) -> Result<&[Self], DeserializationError>;
211}
212
213// STARK FIELD
214// ================================================================================================
215
216/// Defines an element in a STARK-friendly finite field.
217///
218/// A STARK-friendly field is defined as a prime field with high two-addicity. That is, the
219/// the modulus of the field should be a prime number of the form `k` * 2^`n` + 1 (a Proth prime),
220/// where `n` is relatively large (e.g., greater than 32).
221pub trait StarkField: FieldElement<BaseField = Self> {
222    // CONSTANTS
223    //----------------------------------------------------------------------------------------------
224
225    /// Prime modulus of the field. Must be of the form `k` * 2^`n` + 1 (a Proth prime).
226    /// This ensures that the field has high 2-adicity.
227    const MODULUS: Self::PositiveInteger;
228
229    /// The number of bits needed to represents `Self::MODULUS`.
230    const MODULUS_BITS: u32;
231
232    /// A multiplicative generator of the field.
233    const GENERATOR: Self;
234
235    /// Let Self::MODULUS = `k` * 2^`n` + 1; then, TWO_ADICITY is `n`.
236    const TWO_ADICITY: u32;
237
238    /// Let Self::MODULUS = `k` * 2^`n` + 1; then, TWO_ADIC_ROOT_OF_UNITY is 2^`n` root of unity
239    /// computed as Self::GENERATOR^`k`.
240    const TWO_ADIC_ROOT_OF_UNITY: Self;
241
242    // REQUIRED METHODS
243    //----------------------------------------------------------------------------------------------
244
245    /// Returns byte representation of the field modulus in little-endian byte order.
246    fn get_modulus_le_bytes() -> Vec<u8>;
247
248    /// Returns a canonical integer representation of this field element.
249    fn as_int(&self) -> Self::PositiveInteger;
250
251    // PROVIDED METHODS
252    //----------------------------------------------------------------------------------------------
253
254    /// Returns the root of unity of order 2^`n`.
255    ///
256    /// # Panics
257    /// Panics if the root of unity for the specified order does not exist in this field.
258    fn get_root_of_unity(n: u32) -> Self {
259        assert!(n != 0, "cannot get root of unity for n = 0");
260        assert!(n <= Self::TWO_ADICITY, "order cannot exceed 2^{}", Self::TWO_ADICITY);
261        let power = Self::PositiveInteger::from(1u32) << (Self::TWO_ADICITY - n);
262        Self::TWO_ADIC_ROOT_OF_UNITY.exp(power)
263    }
264
265    /// Converts a slice of bytes into a field element. Pads the slice if it is smaller than the
266    /// number of bytes needed to represent an element.
267    ///
268    /// # Panics
269    /// Panics if
270    /// - the length of `bytes` is greater than the number of bytes needed to encode an element.
271    /// - the value of the bytes is not a valid field element after padding
272    fn from_bytes_with_padding(bytes: &[u8]) -> Self {
273        assert!(bytes.len() < Self::ELEMENT_BYTES);
274
275        let mut buf = bytes.to_vec();
276        buf.resize(Self::ELEMENT_BYTES, 0);
277
278        let element = match Self::try_from(buf.as_slice()) {
279            Ok(element) => element,
280            Err(_) => panic!("element deserialization failed"),
281        };
282
283        element
284    }
285}
286
287// EXTENSIBLE FIELD
288// ================================================================================================
289
290/// Defines basic arithmetic in an extension of a [StarkField] of a given degree.
291///
292/// This trait defines how to perform multiplication and compute a Frobenius automorphisms of an
293/// element in an extension of degree N for a given [StarkField]. It as assumed that an element in
294/// degree N extension field can be represented by N field elements in the base field.
295///
296/// Implementation of this trait implicitly defines the irreducible polynomial over which the
297/// extension field is defined.
298pub trait ExtensibleField<const N: usize>: StarkField {
299    /// Returns a product of `a` and `b` in the field defined by this extension.
300    fn mul(a: [Self; N], b: [Self; N]) -> [Self; N];
301
302    /// Returns the square of `a` in the field defined by this extension.
303    fn square(a: [Self; N]) -> [Self; N] {
304        <Self as ExtensibleField<N>>::mul(a, a)
305    }
306
307    /// Returns a product of `a` and `b` in the field defined by this extension. `b` represents
308    /// an element in the base field.
309    fn mul_base(a: [Self; N], b: Self) -> [Self; N];
310
311    /// Returns Frobenius automorphisms for `x` in the field defined by this extension.
312    fn frobenius(x: [Self; N]) -> [Self; N];
313
314    /// Returns true if this extension is supported for the underlying base field.
315    fn is_supported() -> bool {
316        true
317    }
318}
319
320// EXTENSION OF
321// ================================================================================================
322
323/// Specifies that a field is an extension of another field.
324///
325/// Currently, this implies the following:
326/// - An element in the base field can be converted into an element in the extension field.
327/// - An element in the extension field can be multiplied by a base field element directly. This can
328///   be used for optimization purposes as such multiplication could be much more efficient than
329///   multiplication of two extension field elements.
330pub trait ExtensionOf<E: FieldElement>: From<E> {
331    fn mul_base(self, other: E) -> Self;
332}
333
334/// A field is always an extension of itself.
335impl<E: FieldElement> ExtensionOf<E> for E {
336    #[inline(always)]
337    fn mul_base(self, other: E) -> Self {
338        self * other
339    }
340}
341
342// TO ELEMENTS
343// ================================================================================================
344
345/// Defines how to convert a struct to a vector of field elements.
346pub trait ToElements<E: FieldElement> {
347    fn to_elements(&self) -> Vec<E>;
348}
349
350impl<E: FieldElement> ToElements<E> for () {
351    fn to_elements(&self) -> Vec<E> {
352        Vec::new()
353    }
354}
355
356impl<E: FieldElement> ToElements<E> for E {
357    fn to_elements(&self) -> Vec<E> {
358        vec![*self]
359    }
360}
winter_math/field/traits.rs

winter_math/field/
traits.rs
