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)]
32pub struct QueryBytes {
34 pub start: usize,
35 pub len: usize,
36}
37
38#[derive(Copy, Clone, PartialEq, PartialOrd, Eq, Ord, Debug)]
39struct FieldElt {
42 poly_index: usize,
44 eval_index: usize,
46 domain_size: usize,
47 n_polys: usize,
48}
49#[derive(Debug)]
51pub struct QueryField<F> {
52 start: FieldElt,
53 leftover_start: usize,
56 end: FieldElt,
57 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 Self::Small => (Self::KB, Self::MB),
191 Self::Medium => (Self::MB, 10 * Self::MB),
193 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), 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
242pub 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
255pub fn aggregate_commitments<G: AffineRepr>(randomness: G::ScalarField, commitments: &[G]) -> G {
257 let powers_of_randomness = pows(commitments.len(), randomness);
259 let aggregated_commitment =
260 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 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 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}