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

poly_commitment/
utils.rs
