ark_poly_commit/streaming_kzg/
time.rs

1//! An impementation of a time-efficient version of Kate et al's polynomial commitment,
2//! with optimization from [\[BDFG20\]](https://eprint.iacr.org/2020/081.pdf).
3use crate::streaming_kzg::{
4    linear_combination, msm, powers, vanishing_polynomial, Commitment, EvaluationProof, VerifierKey,
5};
6use ark_ec::{pairing::Pairing, scalar_mul::ScalarMul, CurveGroup};
7use ark_ff::Zero;
8use ark_poly::{univariate::DensePolynomial, DenseUVPolynomial};
9#[cfg(not(feature = "std"))]
10use ark_std::vec::Vec;
11use ark_std::{borrow::Borrow, ops::Div, ops::Mul, rand::RngCore, UniformRand};
12
13/// The SRS for the polynomial commitment scheme for a max
14///
15/// The SRS consists of the `max_degree` powers of \\(\tau\\) in \\(\GG_1\\)
16/// plus the `max_eval_degree` powers over \\(\GG_2\\),
17/// where `max_degree` is the max polynomial degree to commit to,
18/// and `max_eval_degree` is the max number of different points to open simultaneously.
19pub struct CommitterKey<E: Pairing> {
20    pub(crate) powers_of_g: Vec<E::G1Affine>,
21    pub(crate) powers_of_g2: Vec<E::G2Affine>,
22}
23
24impl<E: Pairing> From<&CommitterKey<E>> for VerifierKey<E> {
25    fn from(ck: &CommitterKey<E>) -> VerifierKey<E> {
26        let max_eval_points = ck.max_eval_points();
27        let powers_of_g2 = ck.powers_of_g2[..max_eval_points + 1].to_vec();
28        let powers_of_g = ck.powers_of_g[..max_eval_points].to_vec();
29
30        VerifierKey {
31            powers_of_g,
32            powers_of_g2,
33        }
34    }
35}
36
37impl<E: Pairing> CommitterKey<E> {
38    /// The setup algorithm for the commitment scheme.
39    ///
40    /// Given a degree bound `max_degree`,
41    /// an evaluation point bound `max_eval_points`,
42    /// and a cryptographically-secure random number generator `rng`,
43    /// construct the committer key.
44    pub fn new(max_degree: usize, max_eval_points: usize, rng: &mut impl RngCore) -> Self {
45        // Compute the consecutive powers of an element.
46        let tau = E::ScalarField::rand(rng);
47        let powers_of_tau = powers(tau, max_degree + 1);
48
49        let g = E::G1::rand(rng);
50        let powers_of_g = g.batch_mul(&powers_of_tau);
51
52        let g2 = E::G2::rand(rng).into_affine();
53        let powers_of_g2 = powers_of_tau
54            .iter()
55            .take(max_eval_points + 1)
56            .map(|t| g2.mul(t).into_affine())
57            .collect::<Vec<_>>();
58
59        CommitterKey {
60            powers_of_g,
61            powers_of_g2,
62        }
63    }
64
65    /// Return the bound on evaluation points.
66    #[inline]
67    pub fn max_eval_points(&self) -> usize {
68        self.powers_of_g2.len() - 1
69    }
70
71    /// Given a polynomial `polynomial` of degree less than `max_degree`, return a commitment to `polynomial`.
72    pub fn commit(&self, polynomial: &[E::ScalarField]) -> Commitment<E> {
73        Commitment(msm::<E>(&self.powers_of_g, polynomial))
74    }
75
76    /// Obtain a new preprocessed committer key defined by the indices `indices`.
77    pub fn index_by(&self, indices: &[usize]) -> Self {
78        let mut indexed_powers_of_g = vec![E::G1::zero(); self.powers_of_g.len()];
79        indices
80            .iter()
81            .zip(self.powers_of_g.iter())
82            .for_each(|(&i, &g)| indexed_powers_of_g[i] = indexed_powers_of_g[i] + g);
83        Self {
84            powers_of_g2: self.powers_of_g2.clone(),
85            powers_of_g: E::G1::normalize_batch(indexed_powers_of_g.as_slice()),
86        }
87    }
88
89    /// Given an iterator over `polynomials`, expressed as vectors of coefficients, return a vector of commitmetns to all of them.
90    pub fn batch_commit<J>(&self, polynomials: J) -> Vec<Commitment<E>>
91    where
92        J: IntoIterator,
93        J::Item: Borrow<Vec<E::ScalarField>>,
94    {
95        polynomials
96            .into_iter()
97            .map(|p| self.commit(p.borrow()))
98            .collect::<Vec<_>>()
99    }
100
101    /// Given a polynomial `polynomial` and an evaluation point `evaluation_point`,
102    /// return the evaluation of `polynomial in `evaluation_point`,
103    /// together with an evaluation proof.
104    pub fn open(
105        &self,
106        polynomial: &[E::ScalarField],
107        evalualtion_point: &E::ScalarField,
108    ) -> (E::ScalarField, EvaluationProof<E>) {
109        let mut quotient = Vec::new();
110
111        let mut previous = E::ScalarField::zero();
112        for &c in polynomial.iter().rev() {
113            let coefficient = c + previous * evalualtion_point;
114            quotient.insert(0, coefficient);
115            previous = coefficient;
116        }
117
118        let (&evaluation, quotient) = quotient
119            .split_first()
120            .unwrap_or((&E::ScalarField::zero(), &[]));
121        let evaluation_proof = msm::<E>(&self.powers_of_g, quotient);
122        (evaluation, EvaluationProof(evaluation_proof))
123    }
124
125    /// Evaluate a single polynomial at a set of points `eval_points`, and provide a single evaluation proof.
126    pub fn open_multi_points(
127        &self,
128        polynomial: &[E::ScalarField],
129        eval_points: &[E::ScalarField],
130    ) -> EvaluationProof<E> {
131        // Computing the vanishing polynomial over eval_points
132        let z_poly = vanishing_polynomial(eval_points);
133
134        let f_poly = DensePolynomial::from_coefficients_slice(polynomial);
135        let q_poly = f_poly.div(&z_poly);
136        EvaluationProof(self.commit(&q_poly.coeffs).0)
137    }
138
139    /// Evaluate a set of polynomials at a set of points `eval_points`, and provide a single batched evaluation proof.
140    /// `eval_chal` is the random challenge for batching evaluation proofs across different polynomials.
141    pub fn batch_open_multi_points(
142        &self,
143        polynomials: &[&Vec<E::ScalarField>],
144        eval_points: &[E::ScalarField],
145        eval_chal: &E::ScalarField,
146    ) -> EvaluationProof<E> {
147        assert!(eval_points.len() < self.powers_of_g2.len());
148        let etas = powers(*eval_chal, polynomials.len());
149        let batched_polynomial =
150            linear_combination(polynomials, &etas).unwrap_or_else(|| vec![E::ScalarField::zero()]);
151        self.open_multi_points(&batched_polynomial, eval_points)
152    }
153}
ark_poly_commit/streaming_kzg/time.rs

ark_poly_commit/streaming_kzg/
time.rs
