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, ToBigInt};
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        Self::to_biguint(self).to_bigint().unwrap()
113    }
114
115    /// Create a new field element from this field elements bits
116    fn bits_to_field(&self, start: usize, end: usize) -> Result<F>;
117
118    /// Field size in bytes
119    fn size_in_bytes() -> usize
120    where
121        F: PrimeField,
122    {
123        (F::MODULUS_BIT_SIZE / 8) as usize + (F::MODULUS_BIT_SIZE % 8 != 0) as usize
124    }
125
126    /// Get the modulus as `BigUint`
127    fn modulus_biguint() -> BigUint
128    where
129        F: PrimeField,
130    {
131        BigUint::from_bytes_le(&F::MODULUS.to_bytes_le())
132    }
133}
134
135impl<F: Field> FieldHelpers<F> for F {
136    fn from_bytes(bytes: &[u8]) -> Result<F> {
137        F::deserialize_uncompressed(&mut &*bytes).map_err(|_| FieldHelpersError::DeserializeBytes)
138    }
139
140    fn from_hex(hex: &str) -> Result<F> {
141        let bytes: Vec<u8> = hex::decode(hex).map_err(|_| FieldHelpersError::DecodeHex)?;
142        F::deserialize_uncompressed(&mut &bytes[..])
143            .map_err(|_| FieldHelpersError::DeserializeBytes)
144    }
145
146    /// Creates a field element from bits (little endian)
147    fn from_bits(bits: &[bool]) -> Result<F> {
148        let bytes = bits
149            .iter()
150            .enumerate()
151            .fold(F::zero().to_bytes(), |mut bytes, (i, bit)| {
152                bytes[i / 8] |= (*bit as u8) << (i % 8);
153                bytes
154            });
155
156        F::deserialize_uncompressed(&mut &bytes[..])
157            .map_err(|_| FieldHelpersError::DeserializeBytes)
158    }
159
160    fn to_bytes(&self) -> Vec<u8> {
161        let mut bytes: Vec<u8> = vec![];
162        self.serialize_uncompressed(&mut bytes)
163            .expect("Failed to serialize field");
164
165        bytes
166    }
167
168    fn to_hex(&self) -> String {
169        hex::encode(self.to_bytes())
170    }
171
172    /// Converts a field element into bit representation (little endian)
173    fn to_bits(&self) -> Vec<bool> {
174        self.to_bytes().iter().fold(vec![], |mut bits, byte| {
175            let mut byte = *byte;
176            for _ in 0..8 {
177                bits.push(byte & 0x01 == 0x01);
178                byte >>= 1;
179            }
180            bits
181        })
182    }
183
184    fn bits_to_field(&self, start: usize, end: usize) -> Result<F> {
185        F::from_bits(&self.to_bits()[start..end]).map_err(|_| FieldHelpersError::DeserializeBits)
186    }
187}
188
189/// Field element wrapper for [BigUint]
190pub trait BigUintFieldHelpers {
191    /// Convert BigUint into PrimeField element
192    fn to_field<F: PrimeField>(self) -> Result<F>;
193}
194
195impl BigUintFieldHelpers for BigUint {
196    fn to_field<F: PrimeField>(self) -> Result<F> {
197        F::from_biguint(&self)
198    }
199}
200
201/// Converts an [i32] into a [Field]
202pub fn i32_to_field<F: From<u64> + Neg<Output = F>>(i: i32) -> F {
203    if i >= 0 {
204        F::from(i as u64)
205    } else {
206        -F::from(-i as u64)
207    }
208}
209
210/// `pows(d, x)` returns a vector containing the first `d` powers of the
211/// field element `x` (from `1` to `x^(d-1)`).
212pub fn pows<F: Field>(d: usize, x: F) -> Vec<F> {
213    let mut acc = F::one();
214    let mut res = Vec::with_capacity(d);
215    for _ in 1..=d {
216        res.push(acc);
217        acc *= x;
218    }
219    res
220}
221
222/// Returns the product of all the field elements belonging to an iterator.
223pub fn product<F: Field>(xs: impl Iterator<Item = F>) -> F {
224    let mut res = F::one();
225    for x in xs {
226        res *= &x;
227    }
228    res
229}
230
231/// COmpute the inner product of two slices of field elements.
232pub fn inner_prod<F: Field>(xs: &[F], ys: &[F]) -> F {
233    let mut res = F::zero();
234    for (&x, y) in xs.iter().zip(ys) {
235        res += &(x * y);
236    }
237    res
238}
o1_utils/field_helpers.rs

o1_utils/
field_helpers.rs
