o1_utils/
field_helpers.rs

1//! Useful helper methods to extend [`ark_ff::Field`].
2
3use alloc::{string::String, vec, vec::Vec};
4use ark_ff::{BigInteger, Field, PrimeField};
5use core::ops::Neg;
6use num_bigint::{BigInt, BigUint, Sign};
7use thiserror::Error;
8
9#[cfg(feature = "std")]
10use num_bigint::RandBigInt;
11#[cfg(feature = "std")]
12use rand::rngs::StdRng;
13
14/// Field helpers error
15#[allow(missing_docs)]
16#[derive(Error, Debug, Clone, PartialEq, Eq)]
17pub enum FieldHelpersError {
18    #[error("failed to deserialize field bytes")]
19    DeserializeBytes,
20    #[error("failed to deserialize field bits")]
21    DeserializeBits,
22    #[error("failed to decode hex")]
23    DecodeHex,
24    #[error("failed to convert BigUint into field element")]
25    FromBigToField,
26}
27
28/// Result alias using [`FieldHelpersError`]
29pub type Result<T> = core::result::Result<T, FieldHelpersError>;
30
31/// Helper to generate random field elements
32#[cfg(feature = "std")]
33pub trait RandomField<F> {
34    /// Generates a random field element of up to a given number of bits
35    fn gen_field_with_bits(&mut self, bits: usize) -> F;
36
37    /// Initialize a random input with a random value of given length
38    fn gen(&mut self, input: Option<F>, bits: Option<usize>) -> F;
39}
40
41#[cfg(feature = "std")]
42impl<F: PrimeField> RandomField<F> for StdRng {
43    #[allow(clippy::cast_possible_truncation)]
44    fn gen_field_with_bits(&mut self, bits: usize) -> F {
45        F::from_biguint(&self.gen_biguint_below(&BigUint::from(2u8).pow(bits as u32))).unwrap()
46    }
47
48    fn gen(&mut self, input: Option<F>, bits: Option<usize>) -> F {
49        input.unwrap_or_else(|| {
50            assert!(bits.is_some());
51            self.gen_field_with_bits(bits.unwrap())
52        })
53    }
54}
55
56/// Helper to obtain two
57pub trait Two<F> {
58    /// Value two
59    fn two() -> F;
60
61    /// Power of two
62    fn two_pow(pow: u64) -> F;
63}
64
65impl<F: Field> Two<F> for F {
66    fn two() -> F {
67        F::from(2u8)
68    }
69
70    fn two_pow(pow: u64) -> F {
71        F::two().pow([pow])
72    }
73}
74
75/// Field element helpers
76///   Unless otherwise stated everything is in little-endian byte order.
77pub trait FieldHelpers<F> {
78    /// Deserialize from bytes
79    ///
80    /// # Errors
81    ///
82    /// Returns error if deserialization fails.
83    fn from_bytes(bytes: &[u8]) -> Result<F>;
84
85    /// Deserialize from little-endian hex
86    ///
87    /// # Errors
88    ///
89    /// Returns error if hex decoding or deserialization fails.
90    fn from_hex(hex: &str) -> Result<F>;
91
92    /// Deserialize from bits
93    ///
94    /// # Errors
95    ///
96    /// Returns error if deserialization fails.
97    fn from_bits(bits: &[bool]) -> Result<F>;
98
99    /// Deserialize from `BigUint`
100    ///
101    /// # Errors
102    ///
103    /// Returns error if conversion fails.
104    fn from_biguint(big: &BigUint) -> Result<F>
105    where
106        F: PrimeField,
107    {
108        Ok(F::from(big.clone()))
109    }
110
111    /// Serialize to bytes
112    fn to_bytes(&self) -> Vec<u8>;
113
114    /// Serialize to hex
115    fn to_hex(&self) -> String;
116
117    /// Serialize to bits
118    fn to_bits(&self) -> Vec<bool>;
119
120    /// Serialize field element to a `BigUint`
121    fn to_biguint(&self) -> BigUint
122    where
123        F: PrimeField,
124    {
125        BigUint::from_bytes_le(&self.to_bytes())
126    }
127
128    /// Serialize field element f to a (positive) [`BigInt`] directly.
129    fn to_bigint_positive(&self) -> BigInt
130    where
131        F: PrimeField,
132    {
133        use ark_ff::Zero;
134        let big_int = Self::to_biguint(self);
135
136        if big_int.is_zero() {
137            BigInt::zero()
138        } else {
139            BigInt::new(Sign::Plus, big_int.to_u32_digits())
140        }
141    }
142
143    /// Create a new field element from this field elements bits
144    ///
145    /// # Errors
146    ///
147    /// Returns error if deserialization fails.
148    fn bits_to_field(&self, start: usize, end: usize) -> Result<F>;
149
150    /// Field size in bytes
151    #[must_use]
152    #[allow(clippy::cast_possible_truncation)]
153    fn size_in_bytes() -> usize
154    where
155        F: PrimeField,
156    {
157        (F::MODULUS_BIT_SIZE / 8) as usize + usize::from(F::MODULUS_BIT_SIZE % 8 != 0)
158    }
159
160    /// Get the modulus as `BigUint`
161    fn modulus_biguint() -> BigUint
162    where
163        F: PrimeField,
164    {
165        BigUint::from_bytes_le(&F::MODULUS.to_bytes_le())
166    }
167}
168
169impl<F: Field> FieldHelpers<F> for F {
170    fn from_bytes(bytes: &[u8]) -> Result<F> {
171        F::deserialize_uncompressed(&mut &*bytes).map_err(|_| FieldHelpersError::DeserializeBytes)
172    }
173
174    fn from_hex(hex: &str) -> Result<F> {
175        let bytes: Vec<u8> = hex::decode(hex).map_err(|_| FieldHelpersError::DecodeHex)?;
176        F::deserialize_uncompressed(&mut &bytes[..])
177            .map_err(|_| FieldHelpersError::DeserializeBytes)
178    }
179
180    /// Creates a field element from bits (little endian)
181    fn from_bits(bits: &[bool]) -> Result<F> {
182        let bytes = bits
183            .iter()
184            .enumerate()
185            .fold(F::zero().to_bytes(), |mut bytes, (i, bit)| {
186                bytes[i / 8] |= u8::from(*bit) << (i % 8);
187                bytes
188            });
189
190        F::deserialize_uncompressed(&mut &bytes[..])
191            .map_err(|_| FieldHelpersError::DeserializeBytes)
192    }
193
194    fn to_bytes(&self) -> Vec<u8> {
195        let mut bytes: Vec<u8> = vec![];
196        self.serialize_uncompressed(&mut bytes)
197            .expect("Failed to serialize field");
198
199        bytes
200    }
201
202    fn to_hex(&self) -> String {
203        hex::encode(self.to_bytes())
204    }
205
206    /// Converts a field element into bit representation (little endian)
207    fn to_bits(&self) -> Vec<bool> {
208        self.to_bytes().iter().fold(vec![], |mut bits, byte| {
209            let mut byte = *byte;
210            for _ in 0..8 {
211                bits.push(byte & 0x01 == 0x01);
212                byte >>= 1;
213            }
214            bits
215        })
216    }
217
218    fn bits_to_field(&self, start: usize, end: usize) -> Result<F> {
219        F::from_bits(&self.to_bits()[start..end]).map_err(|_| FieldHelpersError::DeserializeBits)
220    }
221}
222
223/// Field element wrapper for [`BigUint`]
224pub trait BigUintFieldHelpers {
225    /// Convert `BigUint` into `PrimeField` element
226    ///
227    /// # Errors
228    ///
229    /// Returns error if conversion fails.
230    fn to_field<F: PrimeField>(self) -> Result<F>;
231}
232
233impl BigUintFieldHelpers for BigUint {
234    fn to_field<F: PrimeField>(self) -> Result<F> {
235        F::from_biguint(&self)
236    }
237}
238
239/// Converts an [`i32`] into a [`Field`]
240#[must_use]
241#[allow(clippy::cast_sign_loss)]
242pub fn i32_to_field<F: From<u64> + Neg<Output = F>>(i: i32) -> F {
243    if i >= 0 {
244        F::from(i as u64)
245    } else {
246        -F::from(-i as u64)
247    }
248}
249
250/// `pows(d, x)` returns a vector containing the first `d` powers of the
251/// field element `x` (from `1` to `x^(d-1)`).
252#[must_use]
253pub fn pows<F: Field>(d: usize, x: F) -> Vec<F> {
254    let mut acc = F::one();
255    let mut res = Vec::with_capacity(d);
256    for _ in 1..=d {
257        res.push(acc);
258        acc *= x;
259    }
260    res
261}
262
263/// Returns the product of all the field elements belonging to an iterator.
264pub fn product<F: Field>(xs: impl Iterator<Item = F>) -> F {
265    let mut res = F::one();
266    for x in xs {
267        res *= &x;
268    }
269    res
270}
271
272/// Compute the inner product of two slices of field elements.
273pub fn inner_prod<F: Field>(xs: &[F], ys: &[F]) -> F {
274    let mut res = F::zero();
275    for (&x, y) in xs.iter().zip(ys) {
276        res += &(x * y);
277    }
278    res
279}
o1_utils/field_helpers.rs

o1_utils/
field_helpers.rs
