poly_commitment/utils.rs
1use crate::{
2 commitment::{b_poly_coefficients, CommitmentCurve},
3 ipa::SRS,
4 PolynomialsToCombine,
5};
6use alloc::{vec, vec::Vec};
7use ark_ec::{CurveGroup, VariableBaseMSM};
8use ark_ff::{batch_inversion, FftField, Field, One, PrimeField, UniformRand, Zero};
9use ark_poly::{univariate::DensePolynomial, DenseUVPolynomial, EvaluationDomain, Evaluations};
10use o1_utils::ExtendedDensePolynomial;
11#[cfg(feature = "parallel")]
12use rayon::prelude::*;
13
14/// Represent a polynomial either with its coefficients or its evaluations.
15///
16/// See [`DensePolynomialOrEvaluations::DensePolynomial`] and
17/// [`DensePolynomialOrEvaluations::Evaluations`] for the two variants.
18pub enum DensePolynomialOrEvaluations<'a, F: FftField, D: EvaluationDomain<F>> {
19 /// Polynomial represented by its coefficients
20 DensePolynomial(&'a DensePolynomial<F>),
21 /// Polynomial represented by its evaluations over a domain D
22 Evaluations(&'a Evaluations<F, D>, D),
23}
24
25/// A formal sum of the form
26/// `s_0 * p_0 + ... s_n * p_n`
27/// where each `s_i` is a scalar and each `p_i` is a polynomial.
28/// The parameter `P` is expected to be the coefficients of the polynomial
29/// `p_i`, even though we could treat it as the evaluations.
30///
31/// This hypothesis is important if `to_dense_polynomial` is called.
32#[derive(Default)]
33struct ScaledChunkedPolynomial<F, P>(Vec<(F, P)>);
34
35impl<F, P> ScaledChunkedPolynomial<F, P> {
36 fn add_poly(&mut self, scale: F, p: P) {
37 self.0.push((scale, p));
38 }
39}
40
41impl<F: Field> ScaledChunkedPolynomial<F, &[F]> {
42 /// Compute the resulting scaled polynomial.
43 /// Example:
44 /// Given the two polynomials `1 + 2X` and `3 + 4X`, and the scaling
45 /// factors `2` and `3`, the result is the polynomial `11 + 16X`.
46 /// ```text
47 /// 2 * [1, 2] + 3 * [3, 4] = [2, 4] + [9, 12] = [11, 16]
48 /// ```
49 fn to_dense_polynomial(&self) -> DensePolynomial<F> {
50 // Note: using a reference to avoid reallocation of the result.
51 let mut res = DensePolynomial::<F>::zero();
52
53 let scaled: Vec<_> = o1_utils::cfg_iter!(self.0)
54 .map(|(scale, segment)| {
55 let scale = *scale;
56 // We simply scale each coefficients.
57 // It is simply because DensePolynomial doesn't have a method
58 // `scale`.
59 let v = o1_utils::cfg_iter!(segment).map(|x| scale * *x).collect();
60 DensePolynomial::from_coefficients_vec(v)
61 })
62 .collect();
63
64 for p in scaled {
65 res += &p;
66 }
67
68 res
69 }
70}
71
72/// Combine the polynomials using a scalar (`polyscale`).
73///
74/// Creates a single unified polynomial to open. This function also accepts
75/// polynomials in evaluations form. In this case it applies an IFFT, and,
76/// if necessary, applies chunking to it (ie. split it in multiple
77/// polynomials of degree less than the SRS size).
78///
79/// # Panics
80///
81/// Panics if the evaluation polynomials have inconsistent domain sizes.
82///
83/// Parameters:
84/// - `plnms`: vector of polynomials, either in evaluations or coefficients form, together with
85/// a set of scalars representing their blinders.
86/// - `polyscale`: scalar to combine the polynomials, which will be scaled based on the number of
87/// polynomials to combine.
88///
89/// Output:
90/// - `combined_poly`: combined polynomial. The order of the output follows the order of `plnms`.
91/// - `combined_comm`: combined scalars representing the blinder commitment.
92///
93/// Example:
94/// Given the three polynomials `p1(X)`, and `p3(X)` in coefficients
95/// forms, p2(X) in evaluation form,
96/// and the scaling factor `polyscale`, the result will be the polynomial:
97///
98/// ```text
99/// p1(X) + polyscale * i_fft(chunks(p2))(X) + polyscale^2 p3(X)
100/// ```
101///
102/// Additional complexity is added to handle chunks.
103pub fn combine_polys<G: CommitmentCurve, D: EvaluationDomain<G::ScalarField>>(
104 plnms: PolynomialsToCombine<G, D>,
105 polyscale: G::ScalarField,
106 srs_length: usize,
107) -> (DensePolynomial<G::ScalarField>, G::ScalarField) {
108 // Initialising the output for the combined coefficients forms
109 let mut plnm_coefficients =
110 ScaledChunkedPolynomial::<G::ScalarField, &[G::ScalarField]>::default();
111 // Initialising the output for the combined evaluations forms
112 let mut plnm_evals_part = {
113 // For now just check that all the evaluation polynomials are the same
114 // degree so that we can do just a single FFT.
115 // If/when we change this, we can add more complicated code to handle
116 // different degrees.
117 let degree = plnms
118 .iter()
119 .fold(None, |acc, (p, _)| match p {
120 DensePolynomialOrEvaluations::DensePolynomial(_) => acc,
121 DensePolynomialOrEvaluations::Evaluations(_, d) => {
122 if let Some(n) = acc {
123 assert_eq!(n, d.size());
124 }
125 Some(d.size())
126 }
127 })
128 .unwrap_or(0);
129 vec![G::ScalarField::zero(); degree]
130 };
131
132 // Will contain ∑ comm_chunk * polyscale^i
133 let mut combined_comm = G::ScalarField::zero();
134
135 // Will contain polyscale^i
136 let mut polyscale_to_i = G::ScalarField::one();
137
138 // Iterating over polynomials in the batch.
139 // Note that the chunks in the commitment `p_i_comm` are given as `PolyComm<G::ScalarField>`. They are
140 // evaluations.
141 // We do modify two different structures depending on the form of the
142 // polynomial we are currently processing: `plnm` and `plnm_evals_part`.
143 // We do need to treat both forms separately.
144 for (p_i, p_i_comm) in plnms {
145 match p_i {
146 // Here we scale the polynomial in evaluations forms
147 // Note that based on the check above, sub_domain.size() always give
148 // the same value
149 DensePolynomialOrEvaluations::Evaluations(evals_i, sub_domain) => {
150 let stride = evals_i.evals.len() / sub_domain.size();
151 let evals = &evals_i.evals;
152 o1_utils::cfg_iter_mut!(plnm_evals_part)
153 .enumerate()
154 .for_each(|(i, x)| {
155 *x += polyscale_to_i * evals[i * stride];
156 });
157 for comm_chunk in p_i_comm {
158 combined_comm += &(*comm_chunk * polyscale_to_i);
159 polyscale_to_i *= &polyscale;
160 }
161 }
162
163 // Here we scale the polynomial in coefficient forms
164 DensePolynomialOrEvaluations::DensePolynomial(p_i) => {
165 let mut offset = 0;
166 // iterating over chunks of the polynomial
167 for comm_chunk in p_i_comm {
168 let segment = &p_i.coeffs[core::cmp::min(offset, p_i.coeffs.len())
169 ..core::cmp::min(offset + srs_length, p_i.coeffs.len())];
170 plnm_coefficients.add_poly(polyscale_to_i, segment);
171
172 combined_comm += &(*comm_chunk * polyscale_to_i);
173 polyscale_to_i *= &polyscale;
174 offset += srs_length;
175 }
176 }
177 }
178 }
179
180 // Now, we will combine both evaluations and coefficients forms
181
182 // plnm will be our final combined polynomial. We first treat the
183 // polynomials in coefficients forms, which is simply scaling the
184 // coefficients and add them.
185 let mut combined_plnm = plnm_coefficients.to_dense_polynomial();
186
187 if !plnm_evals_part.is_empty() {
188 // n is the number of evaluations, which is a multiple of the
189 // domain size.
190 // We treat now each chunk.
191 let n = plnm_evals_part.len();
192 let max_poly_size = srs_length;
193 let num_chunks = n.div_ceil(max_poly_size);
194 // Interpolation on the whole domain, i.e. it can be d2, d4, etc.
195 combined_plnm += &Evaluations::from_vec_and_domain(plnm_evals_part, D::new(n).unwrap())
196 .interpolate()
197 .to_chunked_polynomial(num_chunks, max_poly_size)
198 .linearize(polyscale);
199 }
200
201 (combined_plnm, combined_comm)
202}
203
204/// Check a batch of dlog accumulator commitments.
205///
206/// # Panics
207///
208/// Panics if `comms` is non-empty and `chals.len()` is not a
209/// multiple of `comms.len()`.
210// TODO: Not compatible with variable rounds
211#[cfg(feature = "std")]
212pub fn batch_dlog_accumulator_check<G: CommitmentCurve>(
213 urs: &SRS<G>,
214 comms: &[G],
215 chals: &[G::ScalarField],
216) -> bool {
217 let k = comms.len();
218
219 if k == 0 {
220 assert_eq!(chals.len(), 0);
221 return true;
222 }
223
224 let rounds = chals.len() / k;
225 assert_eq!(chals.len() % rounds, 0);
226
227 let rs = {
228 let r = G::ScalarField::rand(&mut rand::rngs::OsRng);
229 let mut rs = vec![G::ScalarField::one(); k];
230 for i in 1..k {
231 rs[i] = r * rs[i - 1];
232 }
233 rs
234 };
235
236 let mut points = urs.g.clone();
237 let n = points.len();
238 points.extend(comms);
239
240 let mut scalars = vec![G::ScalarField::zero(); n];
241 scalars.extend(&rs[..]);
242
243 let chal_invs = {
244 let mut cs = chals.to_vec();
245 batch_inversion(&mut cs);
246 cs
247 };
248
249 let termss: Vec<_> = chals
250 .par_iter()
251 .zip(chal_invs)
252 .chunks(rounds)
253 .zip(rs)
254 .map(|(chunk, r)| {
255 let chals: Vec<_> = chunk.iter().map(|(c, _)| **c).collect();
256 let mut s = b_poly_coefficients(&chals);
257 for c in &mut s {
258 *c *= &r;
259 }
260 s
261 })
262 .collect();
263
264 for terms in termss {
265 assert_eq!(terms.len(), n);
266 for i in 0..n {
267 scalars[i] -= &terms[i];
268 }
269 }
270
271 let scalars: Vec<_> = scalars.iter().map(|x| x.into_bigint()).collect();
272 G::Group::msm_bigint(&points, &scalars) == G::Group::zero()
273}
274
275/// Generate a batch of dlog accumulator commitments.
276///
277/// # Panics
278///
279/// Panics if `num_comms` is non-zero and `chals.len()` is not a
280/// multiple of the derived round count.
281#[cfg(feature = "std")]
282pub fn batch_dlog_accumulator_generate<G: CommitmentCurve>(
283 urs: &SRS<G>,
284 num_comms: usize,
285 chals: &[G::ScalarField],
286) -> Vec<G> {
287 let k = num_comms;
288
289 if k == 0 {
290 assert_eq!(chals.len(), 0);
291 return vec![];
292 }
293
294 let rounds = chals.len() / k;
295 assert_eq!(chals.len() % rounds, 0);
296
297 let comms: Vec<_> = chals
298 .par_iter()
299 .chunks(rounds)
300 .map(|chals| {
301 let chals: Vec<G::ScalarField> = chals.into_iter().copied().collect();
302 let scalars: Vec<_> = b_poly_coefficients(&chals)
303 .into_iter()
304 .map(ark_ff::PrimeField::into_bigint)
305 .collect();
306 let points: Vec<_> = urs.g.clone();
307 G::Group::msm_bigint(&points, &scalars).into_affine()
308 })
309 .collect();
310
311 comms
312}