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