saffron/
utils.rs

1use crate::encoding::{decode_into, encoding_size};
2use ark_ec::{AffineRepr, CurveGroup, VariableBaseMSM};
3use ark_ff::PrimeField;
4use ark_poly::{
5    univariate::DensePolynomial, EvaluationDomain, Evaluations, Radix2EvaluationDomain as R2D,
6};
7use o1_utils::field_helpers::pows;
8use std::marker::PhantomData;
9use thiserror::Error;
10use tracing::instrument;
11
12pub(crate) fn evals_to_polynomial<F: PrimeField>(
13    evals: Vec<F>,
14    domain: R2D<F>,
15) -> DensePolynomial<F> {
16    Evaluations::from_vec_and_domain(evals, domain).interpolate_by_ref()
17}
18
19#[derive(Clone, Debug)]
20/// Represents the bytes a user query
21pub struct QueryBytes {
22    pub start: usize,
23    pub len: usize,
24}
25
26#[derive(Copy, Clone, PartialEq, PartialOrd, Eq, Ord, Debug)]
27/// We store the data in a vector of vector of field element
28/// The inner vector represent polynomials
29struct FieldElt {
30    /// the index of the polynomial the data point is attached too
31    poly_index: usize,
32    /// the index of the root of unity the data point is attached too
33    eval_index: usize,
34    domain_size: usize,
35    n_polys: usize,
36}
37/// Represents a query in term of Field element
38#[derive(Debug)]
39pub struct QueryField<F> {
40    start: FieldElt,
41    /// how many bytes we need to trim from the first chunk
42    /// we get from the first field element we decode
43    leftover_start: usize,
44    end: FieldElt,
45    /// how many bytes we need to trim from the last chunk
46    /// we get from the last field element we decode
47    leftover_end: usize,
48    tag: PhantomData<F>,
49}
50
51impl<F: PrimeField> QueryField<F> {
52    #[instrument(skip_all, level = "debug")]
53    pub fn apply(self, data: &[Vec<F>]) -> Vec<u8> {
54        let mut buffer = vec![0u8; encoding_size::<F>()];
55        let mut answer = Vec::new();
56        self.start
57            .into_iter()
58            .take_while(|x| x <= &self.end)
59            .for_each(|x| {
60                let value = data[x.poly_index][x.eval_index];
61                decode_into(&mut buffer, value);
62                answer.extend_from_slice(&buffer);
63            });
64
65        answer[(self.leftover_start)..(answer.len() - self.leftover_end)].to_vec()
66    }
67}
68
69impl Iterator for FieldElt {
70    type Item = FieldElt;
71    fn next(&mut self) -> Option<Self::Item> {
72        let current = *self;
73
74        if (self.eval_index + 1) < self.domain_size {
75            self.eval_index += 1;
76        } else if (self.poly_index + 1) < self.n_polys {
77            self.poly_index += 1;
78            self.eval_index = 0;
79        } else {
80            return None;
81        }
82
83        Some(current)
84    }
85}
86
87#[derive(Debug, Error, Clone, PartialEq)]
88pub enum QueryError {
89    #[error("Query out of bounds: poly_index {poly_index} eval_index {eval_index} n_polys {n_polys} domain_size {domain_size}")]
90    QueryOutOfBounds {
91        poly_index: usize,
92        eval_index: usize,
93        n_polys: usize,
94        domain_size: usize,
95    },
96}
97
98impl QueryBytes {
99    pub fn into_query_field<F: PrimeField>(
100        &self,
101        domain_size: usize,
102        n_polys: usize,
103    ) -> Result<QueryField<F>, QueryError> {
104        let n = encoding_size::<F>();
105        let start = {
106            let start_field_nb = self.start / n;
107            FieldElt {
108                poly_index: start_field_nb / domain_size,
109                eval_index: start_field_nb % domain_size,
110                domain_size,
111                n_polys,
112            }
113        };
114        let byte_end = self.start + self.len;
115        let end = {
116            let end_field_nb = byte_end / n;
117            FieldElt {
118                poly_index: end_field_nb / domain_size,
119                eval_index: end_field_nb % domain_size,
120                domain_size,
121                n_polys,
122            }
123        };
124
125        if start.poly_index >= n_polys || end.poly_index >= n_polys {
126            return Err(QueryError::QueryOutOfBounds {
127                poly_index: end.poly_index,
128                eval_index: end.eval_index,
129                n_polys,
130                domain_size,
131            });
132        };
133
134        let leftover_start = self.start % n;
135        let leftover_end = n - byte_end % n;
136
137        Ok(QueryField {
138            start,
139            leftover_start,
140            end,
141            leftover_end,
142            tag: std::marker::PhantomData,
143        })
144    }
145}
146
147#[cfg(test)]
148pub mod test_utils {
149    use proptest::prelude::*;
150
151    #[derive(Debug, Clone)]
152    pub struct UserData(pub Vec<u8>);
153
154    impl UserData {
155        pub fn len(&self) -> usize {
156            self.0.len()
157        }
158
159        pub fn is_empty(&self) -> bool {
160            self.0.is_empty()
161        }
162    }
163
164    #[derive(Clone, Debug)]
165    pub enum DataSize {
166        Small,
167        Medium,
168        Large,
169    }
170
171    impl DataSize {
172        const KB: usize = 1_000;
173        const MB: usize = 1_000_000;
174
175        fn size_range_bytes(&self) -> (usize, usize) {
176            match self {
177                // Small: 1KB - 1MB
178                Self::Small => (Self::KB, Self::MB),
179                // Medium: 1MB - 10MB
180                Self::Medium => (Self::MB, 10 * Self::MB),
181                // Large: 10MB - 100MB
182                Self::Large => (10 * Self::MB, 100 * Self::MB),
183            }
184        }
185    }
186
187    impl Arbitrary for DataSize {
188        type Parameters = ();
189        type Strategy = BoxedStrategy<Self>;
190
191        fn arbitrary_with(_: ()) -> Self::Strategy {
192            prop_oneof![
193                6 => Just(DataSize::Small), // 60% chance
194                3 => Just(DataSize::Medium),
195                1 => Just(DataSize::Large)
196            ]
197            .boxed()
198        }
199    }
200
201    impl Default for DataSize {
202        fn default() -> Self {
203            Self::Small
204        }
205    }
206
207    impl Arbitrary for UserData {
208        type Parameters = DataSize;
209        type Strategy = BoxedStrategy<Self>;
210
211        fn arbitrary() -> Self::Strategy {
212            DataSize::arbitrary()
213                .prop_flat_map(|size| {
214                    let (min, max) = size.size_range_bytes();
215                    prop::collection::vec(any::<u8>(), min..max)
216                })
217                .prop_map(UserData)
218                .boxed()
219        }
220
221        fn arbitrary_with(size: Self::Parameters) -> Self::Strategy {
222            let (min, max) = size.size_range_bytes();
223            prop::collection::vec(any::<u8>(), min..max)
224                .prop_map(UserData)
225                .boxed()
226        }
227    }
228}
229
230// returns the minimum number of polynomials required to encode the data
231pub fn min_encoding_chunks<F: PrimeField, D: EvaluationDomain<F>>(domain: &D, xs: &[u8]) -> usize {
232    let m = encoding_size::<F>();
233    let n = xs.len();
234    let num_field_elems = (n + m - 1) / m;
235    (num_field_elems + domain.size() - 1) / domain.size()
236}
237
238pub fn chunk_size_in_bytes<F: PrimeField, D: EvaluationDomain<F>>(domain: &D) -> usize {
239    let m = encoding_size::<F>();
240    domain.size() * m
241}
242
243/// For commitments C_i and randomness r, returns ∑ r^i C_i.
244pub fn aggregate_commitments<G: AffineRepr>(randomness: G::ScalarField, commitments: &[G]) -> G {
245    // powers_of_randomness = [1, r, r², r³, …]
246    let powers_of_randomness = pows(commitments.len(), randomness);
247    let aggregated_commitment =
248    // Using unwrap() is safe here, as err is returned when commitments and powers have different lengths,
249    // and powers are built with commitment.len().
250        G::Group::msm(commitments, powers_of_randomness.as_slice()).unwrap().into_affine();
251    aggregated_commitment
252}
253
254#[cfg(test)]
255mod tests {
256    use super::*;
257    use crate::encoding::encode_for_domain;
258    use ark_poly::Radix2EvaluationDomain;
259    use mina_curves::pasta::Fp;
260    use once_cell::sync::Lazy;
261    use proptest::prelude::*;
262    use test_utils::{DataSize, UserData};
263    use tracing::debug;
264
265    static DOMAIN: Lazy<Radix2EvaluationDomain<Fp>> = Lazy::new(|| {
266        const SRS_SIZE: usize = 1 << 16;
267        Radix2EvaluationDomain::new(SRS_SIZE).unwrap()
268    });
269
270    // The number of field elements required to encode the data, including the padding
271    fn padded_field_length(xs: &[u8]) -> usize {
272        let n = min_encoding_chunks(&*DOMAIN, xs);
273        n * DOMAIN.size()
274    }
275
276    proptest! {
277        #![proptest_config(ProptestConfig::with_cases(20))]
278        #[test]
279        fn test_padded_byte_length(UserData(xs) in UserData::arbitrary()
280    )
281          { let chunked = encode_for_domain::<Fp>(DOMAIN.size(), &xs);
282            let n = chunked.into_iter().flatten().count();
283            prop_assert_eq!(n, padded_field_length(&xs));
284          }
285        }
286
287    proptest! {
288        #![proptest_config(ProptestConfig::with_cases(20))]
289        #[test]
290        fn test_query(
291            (UserData(xs), queries) in UserData::arbitrary()
292                .prop_flat_map(|xs| {
293                    let n = xs.len();
294                    let query_strategy = (0..(n - 1)).prop_flat_map(move |start| {
295                        ((start + 1)..n).prop_map(move |end| QueryBytes { start, len: end - start})
296                    });
297                    let queries_strategy = prop::collection::vec(query_strategy, 10);
298                    (Just(xs), queries_strategy)
299                })
300        ) {
301            let chunked = encode_for_domain(DOMAIN.size(), &xs);
302            for query in queries {
303                let expected = &xs[query.start..(query.start+query.len)];
304                let field_query: QueryField<Fp> = query.into_query_field(DOMAIN.size(), chunked.len()).unwrap();
305                let got_answer = field_query.apply(&chunked);
306                prop_assert_eq!(expected, got_answer);
307            }
308        }
309    }
310
311    proptest! {
312        #![proptest_config(ProptestConfig::with_cases(20))]
313        #[test]
314        fn test_for_invalid_query_length(
315            (UserData(xs), mut query) in UserData::arbitrary()
316                .prop_flat_map(|UserData(xs)| {
317                    let padded_len = {
318                        let m = Fp::MODULUS_BIT_SIZE as usize / 8;
319                        padded_field_length(&xs) * m
320                    };
321                    let query_strategy = (0..xs.len()).prop_map(move |start| {
322                        // this is the last valid end point
323                        let end = padded_len - 1;
324                        QueryBytes { start, len: end - start }
325                    });
326                    (Just(UserData(xs)), query_strategy)
327                })
328        ) {
329            debug!("check that first query is valid");
330            let chunked = encode_for_domain::<Fp>(DOMAIN.size(), &xs);
331            let n_polys = chunked.len();
332            let query_field = query.into_query_field::<Fp>(DOMAIN.size(), n_polys);
333            prop_assert!(query_field.is_ok());
334            debug!("check that extending query length by 1 is invalid");
335            query.len += 1;
336            let query_field = query.into_query_field::<Fp>(DOMAIN.size(), n_polys);
337            prop_assert!(query_field.is_err());
338
339        }
340    }
341
342    proptest! {
343        #![proptest_config(ProptestConfig::with_cases(20))]
344        #[test]
345        fn test_nil_query(
346            (UserData(xs), query) in UserData::arbitrary_with(DataSize::Small)
347                .prop_flat_map(|xs| {
348                    let padded_len = {
349                        let m = Fp::MODULUS_BIT_SIZE as usize / 8;
350                        padded_field_length(&xs.0) * m
351                    };
352                    let query_strategy = (0..padded_len).prop_map(move |start| {
353                        QueryBytes { start, len: 0 }
354                    });
355                    (Just(xs), query_strategy)
356                })
357        ) {
358            let chunked = encode_for_domain(DOMAIN.size(), &xs);
359            let n_polys = chunked.len();
360            let field_query: QueryField<Fp> = query.into_query_field(DOMAIN.size(), n_polys).unwrap();
361            let got_answer = field_query.apply(&chunked);
362            prop_assert!(got_answer.is_empty());
363            }
364
365    }
366}
saffron/utils.rs

saffron/
utils.rs
