o1_utils/
field_helpers.rs

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

o1_utils/
field_helpers.rs
