ark_poly_commit/marlin/
mod.rs

1use crate::{
2    kzg10, BTreeMap, BTreeSet, BatchLCProof, Debug, Error, Evaluations, LabeledCommitment,
3    LabeledPolynomial, LinearCombination, PCCommitmentState, Polynomial, PolynomialCommitment,
4    QuerySet, RngCore, CHALLENGE_SIZE,
5};
6use ark_crypto_primitives::sponge::CryptographicSponge;
7use ark_ec::{pairing::Pairing, AffineRepr, CurveGroup};
8use ark_ff::{One, Zero};
9use ark_std::{convert::TryInto, hash::Hash, ops::AddAssign, ops::Mul};
10#[cfg(not(feature = "std"))]
11use ark_std::{
12    string::{String, ToString},
13    vec::Vec,
14};
15
16/// Polynomial commitment scheme from [[KZG10]][kzg] that enforces
17/// strict degree bounds and (optionally) enables hiding commitments by
18/// following the approach outlined in [[CHMMVW20, "Marlin"]][marlin].
19///
20/// [kzg]: http://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf
21/// [marlin]: https://eprint.iacr.org/2019/1047
22pub mod marlin_pc;
23
24/// Multivariate polynomial commitment based on the construction in
25/// [[PST13]][pst] with batching and (optional) hiding property inspired
26/// by the univariate scheme in [[CHMMVW20, "Marlin"]][marlin]
27///
28/// [pst]: https://eprint.iacr.org/2011/587.pdf
29/// [marlin]: https://eprint.iacr.org/2019/1047
30pub mod marlin_pst13_pc;
31
32/// Common functionalities between `marlin_pc` and `marlin_pst13_pc`
33struct Marlin<E, P, PC>
34where
35    E: Pairing,
36    P: Polynomial<E::ScalarField>,
37    PC: PolynomialCommitment<E::ScalarField, P>,
38{
39    _engine: core::marker::PhantomData<E>,
40    _poly: core::marker::PhantomData<P>,
41    _pc: core::marker::PhantomData<PC>,
42}
43
44impl<E, P, PC> Marlin<E, P, PC>
45where
46    E: Pairing,
47    P: Polynomial<E::ScalarField>,
48    PC: PolynomialCommitment<E::ScalarField, P>,
49{
50    /// MSM for `commitments` and `coeffs`
51    fn combine_commitments<'a>(
52        coeffs_and_comms: impl IntoIterator<Item = (E::ScalarField, &'a marlin_pc::Commitment<E>)>,
53    ) -> (E::G1, Option<E::G1>) {
54        let mut combined_comm = E::G1::zero();
55        let mut combined_shifted_comm = None;
56        for (coeff, comm) in coeffs_and_comms {
57            if coeff.is_one() {
58                combined_comm.add_assign(&comm.comm.0);
59            } else {
60                combined_comm += &comm.comm.0.mul(coeff);
61            }
62
63            if let Some(shifted_comm) = &comm.shifted_comm {
64                let cur = shifted_comm.0.mul(coeff);
65                combined_shifted_comm = Some(combined_shifted_comm.map_or(cur, |c| c + cur));
66            }
67        }
68        (combined_comm, combined_shifted_comm)
69    }
70
71    /// Normalize a list of commitments
72    fn normalize_commitments<'a>(
73        commitments: Vec<(E::G1, Option<E::G1>)>,
74    ) -> Vec<marlin_pc::Commitment<E>> {
75        let mut comms = Vec::with_capacity(commitments.len());
76        let mut s_comms = Vec::with_capacity(commitments.len());
77        let mut s_flags = Vec::with_capacity(commitments.len());
78        for (comm, s_comm) in commitments {
79            comms.push(comm);
80            if let Some(c) = s_comm {
81                s_comms.push(c);
82                s_flags.push(true);
83            } else {
84                s_comms.push(E::G1::zero());
85                s_flags.push(false);
86            }
87        }
88        let comms = E::G1::normalize_batch(&comms);
89        let s_comms = E::G1::normalize_batch(&mut s_comms);
90        comms
91            .into_iter()
92            .zip(s_comms)
93            .zip(s_flags)
94            .map(|((c, s_c), flag)| {
95                let shifted_comm = if flag {
96                    Some(kzg10::Commitment(s_c))
97                } else {
98                    None
99                };
100                marlin_pc::Commitment {
101                    comm: kzg10::Commitment(c),
102                    shifted_comm,
103                }
104            })
105            .collect()
106    }
107
108    /// Accumulate `commitments` and `values` according to the challenges produces by `challenge_gen`.
109    fn accumulate_commitments_and_values<'a>(
110        commitments: impl IntoIterator<Item = &'a LabeledCommitment<marlin_pc::Commitment<E>>>,
111        values: impl IntoIterator<Item = E::ScalarField>,
112        sponge: &mut impl CryptographicSponge,
113        vk: Option<&marlin_pc::VerifierKey<E>>,
114    ) -> Result<(E::G1, E::ScalarField), Error> {
115        let acc_time = start_timer!(|| "Accumulating commitments and values");
116        let mut combined_comm = E::G1::zero();
117        let mut combined_value = E::ScalarField::zero();
118        for (labeled_commitment, value) in commitments.into_iter().zip(values) {
119            let degree_bound = labeled_commitment.degree_bound();
120            let commitment = labeled_commitment.commitment();
121            assert_eq!(degree_bound.is_some(), commitment.shifted_comm.is_some());
122
123            let challenge_i = sponge.squeeze_field_elements_with_sizes(&[CHALLENGE_SIZE])[0];
124
125            combined_comm += &commitment.comm.0.mul(challenge_i);
126            combined_value += &(value * &challenge_i);
127
128            if let Some(degree_bound) = degree_bound {
129                let challenge_i_1: E::ScalarField =
130                    sponge.squeeze_field_elements_with_sizes(&[CHALLENGE_SIZE])[0];
131
132                let shifted_comm = commitment.shifted_comm.as_ref().unwrap().0.into_group();
133
134                let shift_power = vk
135                    .unwrap()
136                    .get_shift_power(degree_bound)
137                    .ok_or(Error::UnsupportedDegreeBound(degree_bound))?;
138
139                let mut adjusted_comm = shifted_comm - &shift_power.mul(value);
140
141                adjusted_comm *= challenge_i_1;
142                combined_comm += &adjusted_comm;
143            }
144        }
145
146        end_timer!(acc_time);
147        Ok((combined_comm, combined_value))
148    }
149
150    /// Combine and normalize a set of commitments
151    fn combine_and_normalize<'a, D: Clone + Ord + Sync>(
152        commitments: impl IntoIterator<Item = &'a LabeledCommitment<marlin_pc::Commitment<E>>>,
153        query_set: &QuerySet<D>,
154        evaluations: &Evaluations<D, E::ScalarField>,
155        sponge: &mut impl CryptographicSponge,
156        vk: Option<&marlin_pc::VerifierKey<E>>,
157    ) -> Result<(Vec<kzg10::Commitment<E>>, Vec<D>, Vec<E::ScalarField>), Error>
158    where
159        marlin_pc::Commitment<E>: 'a,
160    {
161        let commitments: BTreeMap<_, _> = commitments.into_iter().map(|c| (c.label(), c)).collect();
162        let mut query_to_labels_map = BTreeMap::new();
163
164        for (label, (point_label, point)) in query_set.iter() {
165            let labels = query_to_labels_map
166                .entry(point_label)
167                .or_insert((point, BTreeSet::new()));
168            labels.1.insert(label);
169        }
170
171        let mut combined_comms = Vec::new();
172        let mut combined_queries = Vec::new();
173        let mut combined_evals = Vec::new();
174        for (_, (point, labels)) in query_to_labels_map.into_iter() {
175            let lc_time =
176                start_timer!(|| format!("Randomly combining {} commitments", labels.len()));
177            let mut comms_to_combine: Vec<&'_ LabeledCommitment<_>> = Vec::new();
178            let mut values_to_combine = Vec::new();
179            for label in labels.into_iter() {
180                let commitment = commitments.get(label).ok_or(Error::MissingPolynomial {
181                    label: label.to_string(),
182                })?;
183                let degree_bound = commitment.degree_bound();
184                assert_eq!(
185                    degree_bound.is_some(),
186                    commitment.commitment().shifted_comm.is_some()
187                );
188
189                let v_i = evaluations.get(&(label.clone(), point.clone())).ok_or(
190                    Error::MissingEvaluation {
191                        label: label.to_string(),
192                    },
193                )?;
194
195                comms_to_combine.push(commitment);
196                values_to_combine.push(*v_i);
197            }
198
199            let (c, v) = Self::accumulate_commitments_and_values(
200                comms_to_combine,
201                values_to_combine,
202                sponge,
203                vk,
204            )?;
205            end_timer!(lc_time);
206
207            combined_comms.push(c);
208            combined_queries.push(point.clone());
209            combined_evals.push(v);
210        }
211        let norm_time = start_timer!(|| "Normalizing combined commitments");
212        let combined_comms_affine = E::G1::normalize_batch(&combined_comms);
213        let combined_comms = combined_comms_affine
214            .into_iter()
215            .map(|c| kzg10::Commitment(c.into()))
216            .collect::<Vec<_>>();
217        end_timer!(norm_time);
218        Ok((combined_comms, combined_queries, combined_evals))
219    }
220
221    /// On input a list of polynomials, linear combinations of those polynomials,
222    /// and a query set, `open_combination` outputs a proof of evaluation of
223    /// the combinations at the points in the query set.
224    fn open_combinations<'a, D>(
225        ck: &PC::CommitterKey,
226        lc_s: impl IntoIterator<Item = &'a LinearCombination<E::ScalarField>>,
227        polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<E::ScalarField, P>>,
228        commitments: impl IntoIterator<Item = &'a LabeledCommitment<PC::Commitment>>,
229        query_set: &QuerySet<D>,
230        sponge: &mut impl CryptographicSponge,
231        states: impl IntoIterator<Item = &'a PC::CommitmentState>,
232        rng: Option<&mut dyn RngCore>,
233    ) -> Result<BatchLCProof<E::ScalarField, PC::BatchProof>, Error>
234    where
235        P: 'a + Polynomial<E::ScalarField, Point = D>,
236        D: Debug + Clone + Hash + Ord + Sync,
237        PC: PolynomialCommitment<
238            E::ScalarField,
239            P,
240            Commitment = marlin_pc::Commitment<E>,
241            Error = Error,
242        >,
243        PC::CommitmentState: 'a + AddAssign<(E::ScalarField, &'a PC::CommitmentState)>,
244        PC::Commitment: 'a,
245    {
246        let label_map = polynomials
247            .into_iter()
248            .zip(states)
249            .zip(commitments)
250            .map(|((p, r), c)| (p.label(), (p, r, c)))
251            .collect::<BTreeMap<_, _>>();
252
253        let mut lc_polynomials = Vec::new();
254        let mut lc_states: Vec<PC::CommitmentState> = Vec::new();
255        let mut lc_commitments = Vec::new();
256        let mut lc_info = Vec::new();
257
258        for lc in lc_s {
259            let lc_label = lc.label().clone();
260            let mut poly = P::zero();
261            let mut degree_bound = None;
262            let mut hiding_bound = None;
263
264            let mut randomness = PC::CommitmentState::empty();
265            let mut coeffs_and_comms = Vec::new();
266
267            let num_polys = lc.len();
268            for (coeff, label) in lc.iter().filter(|(_, l)| !l.is_one()) {
269                let label: &String = label.try_into().expect("cannot be one!");
270                let &(cur_poly, cur_state, cur_comm) =
271                    label_map.get(label).ok_or(Error::MissingPolynomial {
272                        label: label.to_string(),
273                    })?;
274                if num_polys == 1 && cur_poly.degree_bound().is_some() {
275                    assert!(
276                        coeff.is_one(),
277                        "Coefficient must be one for degree-bounded equations"
278                    );
279                    degree_bound = cur_poly.degree_bound();
280                } else if cur_poly.degree_bound().is_some() {
281                    return Err(Error::EquationHasDegreeBounds(lc_label));
282                }
283                // Some(_) > None, always.
284                hiding_bound = core::cmp::max(hiding_bound, cur_poly.hiding_bound());
285                poly += (*coeff, cur_poly.polynomial());
286                randomness += (*coeff, cur_state);
287                coeffs_and_comms.push((*coeff, cur_comm.commitment()));
288            }
289
290            let lc_poly =
291                LabeledPolynomial::new(lc_label.clone(), poly, degree_bound, hiding_bound);
292            lc_polynomials.push(lc_poly);
293            lc_states.push(randomness);
294            lc_commitments.push(Self::combine_commitments(coeffs_and_comms));
295            lc_info.push((lc_label, degree_bound));
296        }
297
298        let comms = Self::normalize_commitments(lc_commitments);
299        let lc_commitments = lc_info
300            .into_iter()
301            .zip(comms)
302            .map(|((label, d), c)| LabeledCommitment::new(label, c, d))
303            .collect::<Vec<_>>();
304
305        let proof = PC::batch_open(
306            ck,
307            lc_polynomials.iter(),
308            lc_commitments.iter(),
309            &query_set,
310            sponge,
311            lc_states.iter(),
312            rng,
313        )?;
314
315        Ok(BatchLCProof { proof, evals: None })
316    }
317
318    fn check_combinations<'a, R, D>(
319        vk: &PC::VerifierKey,
320        lc_s: impl IntoIterator<Item = &'a LinearCombination<E::ScalarField>>,
321        commitments: impl IntoIterator<Item = &'a LabeledCommitment<PC::Commitment>>,
322        query_set: &QuerySet<P::Point>,
323        evaluations: &Evaluations<P::Point, E::ScalarField>,
324        proof: &BatchLCProof<E::ScalarField, PC::BatchProof>,
325        sponge: &mut impl CryptographicSponge,
326        rng: &mut R,
327    ) -> Result<bool, Error>
328    where
329        R: RngCore,
330        P: Polynomial<E::ScalarField, Point = D>,
331        D: Debug + Clone + Hash + Ord + Sync,
332        PC: PolynomialCommitment<
333            E::ScalarField,
334            P,
335            Commitment = marlin_pc::Commitment<E>,
336            Error = Error,
337        >,
338        PC::Commitment: 'a,
339    {
340        let BatchLCProof { proof, .. } = proof;
341        let label_comm_map = commitments
342            .into_iter()
343            .map(|c| (c.label(), c))
344            .collect::<BTreeMap<_, _>>();
345
346        let mut lc_commitments = Vec::new();
347        let mut lc_info = Vec::new();
348        let mut evaluations = evaluations.clone();
349
350        let lc_processing_time = start_timer!(|| "Combining commitments");
351        for lc in lc_s {
352            let lc_label = lc.label().clone();
353            let num_polys = lc.len();
354
355            let mut degree_bound = None;
356            let mut coeffs_and_comms = Vec::new();
357
358            for (coeff, label) in lc.iter() {
359                if label.is_one() {
360                    for (&(ref label, _), ref mut eval) in evaluations.iter_mut() {
361                        if label == &lc_label {
362                            **eval -= coeff;
363                        }
364                    }
365                } else {
366                    let label: &String = label.try_into().unwrap();
367                    let &cur_comm = label_comm_map.get(label).ok_or(Error::MissingPolynomial {
368                        label: label.to_string(),
369                    })?;
370
371                    if num_polys == 1 && cur_comm.degree_bound().is_some() {
372                        assert!(
373                            coeff.is_one(),
374                            "Coefficient must be one for degree-bounded equations"
375                        );
376                        degree_bound = cur_comm.degree_bound();
377                    } else if cur_comm.degree_bound().is_some() {
378                        return Err(Error::EquationHasDegreeBounds(lc_label));
379                    }
380                    coeffs_and_comms.push((*coeff, cur_comm.commitment()));
381                }
382            }
383            let lc_time =
384                start_timer!(|| format!("Combining {} commitments for {}", num_polys, lc_label));
385            lc_commitments.push(Self::combine_commitments(coeffs_and_comms));
386            end_timer!(lc_time);
387            lc_info.push((lc_label, degree_bound));
388        }
389        end_timer!(lc_processing_time);
390        let combined_comms_norm_time = start_timer!(|| "Normalizing commitments");
391        let comms = Self::normalize_commitments(lc_commitments);
392        let lc_commitments = lc_info
393            .into_iter()
394            .zip(comms)
395            .map(|((label, d), c)| LabeledCommitment::new(label, c, d))
396            .collect::<Vec<_>>();
397        end_timer!(combined_comms_norm_time);
398
399        PC::batch_check(
400            vk,
401            &lc_commitments,
402            &query_set,
403            &evaluations,
404            proof,
405            sponge,
406            rng,
407        )
408    }
409}
ark_poly_commit/marlin/mod.rs

ark_poly_commit/marlin/
mod.rs
