poly_commitment/utils.rs
1use crate::{
2 commitment::{b_poly_coefficients, CommitmentCurve},
3 ipa::SRS,
4 PolynomialsToCombine,
5};
6use ark_ec::{CurveGroup, VariableBaseMSM};
7use ark_ff::{batch_inversion, FftField, Field, One, PrimeField, UniformRand, Zero};
8use ark_poly::{univariate::DensePolynomial, DenseUVPolynomial, EvaluationDomain, Evaluations};
9use o1_utils::ExtendedDensePolynomial;
10use rayon::prelude::*;
11
12/// Represent a polynomial either with its coefficients or its evaluations.
13///
14/// See [`DensePolynomialOrEvaluations::DensePolynomial`] and
15/// [`DensePolynomialOrEvaluations::Evaluations`] for the two variants.
16pub enum DensePolynomialOrEvaluations<'a, F: FftField, D: EvaluationDomain<F>> {
17 /// Polynomial represented by its coefficients
18 DensePolynomial(&'a DensePolynomial<F>),
19 /// Polynomial represented by its evaluations over a domain D
20 Evaluations(&'a Evaluations<F, D>, D),
21}
22
23/// A formal sum of the form
24/// `s_0 * p_0 + ... s_n * p_n`
25/// where each `s_i` is a scalar and each `p_i` is a polynomial.
26/// The parameter `P` is expected to be the coefficients of the polynomial
27/// `p_i`, even though we could treat it as the evaluations.
28///
29/// This hypothesis is important if `to_dense_polynomial` is called.
30#[derive(Default)]
31struct ScaledChunkedPolynomial<F, P>(Vec<(F, P)>);
32
33impl<F, P> ScaledChunkedPolynomial<F, P> {
34 fn add_poly(&mut self, scale: F, p: P) {
35 self.0.push((scale, p));
36 }
37}
38
39impl<F: Field> ScaledChunkedPolynomial<F, &[F]> {
40 /// Compute the resulting scaled polynomial.
41 /// Example:
42 /// Given the two polynomials `1 + 2X` and `3 + 4X`, and the scaling
43 /// factors `2` and `3`, the result is the polynomial `11 + 16X`.
44 /// ```text
45 /// 2 * [1, 2] + 3 * [3, 4] = [2, 4] + [9, 12] = [11, 16]
46 /// ```
47 fn to_dense_polynomial(&self) -> DensePolynomial<F> {
48 // Note: using a reference to avoid reallocation of the result.
49 let mut res = DensePolynomial::<F>::zero();
50
51 let scaled: Vec<_> = self
52 .0
53 .par_iter()
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 = segment.par_iter().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 plnm_evals_part
153 .par_iter_mut()
154 .enumerate()
155 .for_each(|(i, x)| {
156 *x += polyscale_to_i * evals[i * stride];
157 });
158 for comm_chunk in p_i_comm {
159 combined_comm += &(*comm_chunk * polyscale_to_i);
160 polyscale_to_i *= &polyscale;
161 }
162 }
163
164 // Here we scale the polynomial in coefficient forms
165 DensePolynomialOrEvaluations::DensePolynomial(p_i) => {
166 let mut offset = 0;
167 // iterating over chunks of the polynomial
168 for comm_chunk in p_i_comm {
169 let segment = &p_i.coeffs[std::cmp::min(offset, p_i.coeffs.len())
170 ..std::cmp::min(offset + srs_length, p_i.coeffs.len())];
171 plnm_coefficients.add_poly(polyscale_to_i, segment);
172
173 combined_comm += &(*comm_chunk * polyscale_to_i);
174 polyscale_to_i *= &polyscale;
175 offset += srs_length;
176 }
177 }
178 }
179 }
180
181 // Now, we will combine both evaluations and coefficients forms
182
183 // plnm will be our final combined polynomial. We first treat the
184 // polynomials in coefficients forms, which is simply scaling the
185 // coefficients and add them.
186 let mut combined_plnm = plnm_coefficients.to_dense_polynomial();
187
188 if !plnm_evals_part.is_empty() {
189 // n is the number of evaluations, which is a multiple of the
190 // domain size.
191 // We treat now each chunk.
192 let n = plnm_evals_part.len();
193 let max_poly_size = srs_length;
194 let num_chunks = n.div_ceil(max_poly_size);
195 // Interpolation on the whole domain, i.e. it can be d2, d4, etc.
196 combined_plnm += &Evaluations::from_vec_and_domain(plnm_evals_part, D::new(n).unwrap())
197 .interpolate()
198 .to_chunked_polynomial(num_chunks, max_poly_size)
199 .linearize(polyscale);
200 }
201
202 (combined_plnm, combined_comm)
203}
204
205/// Check a batch of dlog accumulator commitments.
206///
207/// # Panics
208///
209/// Panics if `comms` is non-empty and `chals.len()` is not a
210/// multiple of `comms.len()`.
211// TODO: Not compatible with variable rounds
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.
281pub fn batch_dlog_accumulator_generate<G: CommitmentCurve>(
282 urs: &SRS<G>,
283 num_comms: usize,
284 chals: &[G::ScalarField],
285) -> Vec<G> {
286 let k = num_comms;
287
288 if k == 0 {
289 assert_eq!(chals.len(), 0);
290 return vec![];
291 }
292
293 let rounds = chals.len() / k;
294 assert_eq!(chals.len() % rounds, 0);
295
296 let comms: Vec<_> = chals
297 .par_iter()
298 .chunks(rounds)
299 .map(|chals| {
300 let chals: Vec<G::ScalarField> = chals.into_iter().copied().collect();
301 let scalars: Vec<_> = b_poly_coefficients(&chals)
302 .into_iter()
303 .map(ark_ff::PrimeField::into_bigint)
304 .collect();
305 let points: Vec<_> = urs.g.clone();
306 G::Group::msm_bigint(&points, &scalars).into_affine()
307 })
308 .collect();
309
310 comms
311}