ark_poly_commit/streaming_kzg/
space.rs

1//! Space-efficient implementation of the polynomial commitment of Kate et al.
2use crate::{
3    streaming_kzg::{
4        time::CommitterKey, vanishing_polynomial, Commitment, EvaluationProof,
5        FoldedPolynomialTree, VerifierKey,
6    },
7    utils::ceil_div,
8};
9use ark_ec::{
10    pairing::Pairing,
11    scalar_mul::variable_base::{ChunkedPippenger, HashMapPippenger, VariableBaseMSM},
12    CurveGroup,
13};
14use ark_ff::{PrimeField, Zero};
15use ark_poly::Polynomial;
16#[cfg(not(feature = "std"))]
17use ark_std::vec::Vec;
18use ark_std::{
19    borrow::Borrow,
20    collections::VecDeque,
21    iterable::{Iterable, Reverse},
22};
23
24const LENGTH_MISMATCH_MSG: &str = "Expecting at least one element in the committer key.";
25
26/// The streaming SRS for the polynomial commitment scheme consists of a stream of consecutive powers of g.
27/// It also implements functions for `setup`, `commit` and `open`.
28#[derive(Clone)]
29pub struct CommitterKeyStream<E, SG>
30where
31    E: Pairing,
32    SG: Iterable,
33    SG::Item: Borrow<E::G1Affine>,
34{
35    /// Stream of G1 elements.
36    pub powers_of_g: SG,
37    /// Two G2 elements needed for the committer.
38    pub powers_of_g2: Vec<E::G2Affine>,
39}
40
41impl<E, SG> CommitterKeyStream<E, SG>
42where
43    E: Pairing,
44    SG: Iterable,
45    SG::Item: Borrow<E::G1Affine>,
46{
47    /// Turn a streaming SRS into a normal SRS.
48    pub fn as_committer_key(&self, max_degree: usize) -> CommitterKey<E> {
49        let offset = self.powers_of_g.len() - max_degree;
50        let mut powers_of_g = self
51            .powers_of_g
52            .iter()
53            .skip(offset)
54            .map(|x| *x.borrow())
55            .collect::<Vec<_>>();
56        powers_of_g.reverse();
57        let powers_of_g2 = self.powers_of_g2.clone().to_vec();
58        CommitterKey {
59            powers_of_g,
60            powers_of_g2,
61        }
62    }
63
64    /// Evaluate a single polynomial at the point `alpha`, and provide an evaluation proof along with the evaluation.
65    pub fn open<SF>(
66        &self,
67        polynomial: &SF,
68        alpha: &E::ScalarField,
69        max_msm_buffer: usize,
70    ) -> (E::ScalarField, EvaluationProof<E>)
71    where
72        SF: Iterable,
73        SF::Item: Borrow<E::ScalarField>,
74    {
75        let mut quotient: ChunkedPippenger<E::G1> = ChunkedPippenger::new(max_msm_buffer);
76
77        let bases_init = self.powers_of_g.iter();
78        let scalars = polynomial.iter();
79
80        // align the streams and remove one degree
81        // TODO: change `skip` to `advance_by` once rust-lang/rust#7774 is fixed.
82        // See <https://github.com/rust-lang/rust/issues/77404>
83        let bases = bases_init.skip(self.powers_of_g.len() - polynomial.len());
84
85        let mut previous = E::ScalarField::zero();
86        for (scalar, base) in scalars.zip(bases) {
87            quotient.add(base, previous.into_bigint());
88            let coefficient = previous * alpha + scalar.borrow();
89            previous = coefficient;
90        }
91
92        let evaluation = previous;
93        let evaluation_proof = quotient.finalize().into_affine();
94        (evaluation, EvaluationProof(evaluation_proof))
95    }
96
97    /// Evaluate a single polynomial at a set of points `points`, and provide an evaluation proof along with evaluations.
98    pub fn open_multi_points<SF>(
99        &self,
100        polynomial: &SF,
101        points: &[E::ScalarField],
102        max_msm_buffer: usize,
103    ) -> (Vec<E::ScalarField>, EvaluationProof<E>)
104    where
105        SF: Iterable,
106        SF::Item: Borrow<E::ScalarField>,
107    {
108        let zeros = vanishing_polynomial(points);
109        let mut quotient: ChunkedPippenger<E::G1> = ChunkedPippenger::new(max_msm_buffer);
110        let bases_init = self.powers_of_g.iter();
111        // TODO: change `skip` to `advance_by` once rust-lang/rust#7774 is fixed.
112        // See <https://github.com/rust-lang/rust/issues/77404>
113        let mut bases = bases_init.skip(self.powers_of_g.len() - polynomial.len() + zeros.degree());
114
115        let mut state = VecDeque::<E::ScalarField>::with_capacity(points.len());
116
117        let mut polynomial_iterator = polynomial.iter();
118
119        (0..points.len()).for_each(|_| {
120            state.push_back(*polynomial_iterator.next().unwrap().borrow());
121        });
122
123        for coefficient in polynomial_iterator {
124            let coefficient = coefficient.borrow();
125            let quotient_coefficient = state.pop_front().unwrap();
126            state.push_back(*coefficient);
127            (0..points.len()).for_each(|i| {
128                state[i] -= zeros.coeffs[zeros.degree() - i - 1] * quotient_coefficient;
129            });
130            let base = bases.next().unwrap();
131            quotient.add(base, quotient_coefficient.into_bigint());
132        }
133        let remainder = state.make_contiguous().to_vec();
134        let commitment = EvaluationProof(quotient.finalize().into_affine());
135        (remainder, commitment)
136    }
137
138    /// The commitment procedures, that takes as input a committer key and the streaming coefficients of polynomial, and produces the desired commitment.
139    pub fn commit<SF: ?Sized>(&self, polynomial: &SF) -> Commitment<E>
140    where
141        SF: Iterable,
142        SF::Item: Borrow<E::ScalarField>,
143    {
144        assert!(self.powers_of_g.len() >= polynomial.len());
145
146        Commitment(
147            <E::G1 as VariableBaseMSM>::msm_chunks(&self.powers_of_g, polynomial).into_affine(),
148        )
149    }
150
151    /// The batch commitment procedures, that takes as input a committer key and the streaming coefficients of a list of polynomials, and produces the desired commitments.
152    pub fn batch_commit<'a, F>(
153        &self,
154        polynomials: &[&'a dyn Iterable<Item = F, Iter = &mut dyn Iterator<Item = F>>],
155    ) -> Vec<Commitment<E>>
156    where
157        F: Borrow<E::ScalarField>,
158    {
159        polynomials.iter().map(|&p| self.commit(p)).collect()
160    }
161
162    /// The commitment procedures for our tensor check protocol.
163    /// The algorithm takes advantage of the tree structure of folding polynomials in our protocol. Please refer to our paper for more details.
164    /// The function takes as input a committer key and the tree structure of all the folding polynomials, and produces the desired commitment for each polynomial.
165    pub fn commit_folding<SF>(
166        &self,
167        polynomials: &FoldedPolynomialTree<E::ScalarField, SF>,
168        max_msm_buffer: usize,
169    ) -> Vec<Commitment<E>>
170    where
171        SF: Iterable,
172        SF::Item: Borrow<E::ScalarField>,
173    {
174        let n = polynomials.depth();
175        let mut pippengers: Vec<ChunkedPippenger<E::G1>> = Vec::new();
176        let mut folded_bases = Vec::new();
177        for i in 1..n + 1 {
178            let pippenger: ChunkedPippenger<<E as Pairing>::G1> =
179                ChunkedPippenger::with_size(max_msm_buffer / n);
180            let bases_init = self.powers_of_g.iter();
181
182            let delta = self.powers_of_g.len() - ceil_div(polynomials.len(), 1 << i);
183            // TODO: change `skip` to `advance_by` once rust-lang/rust#7774 is fixed.
184            // See <https://github.com/rust-lang/rust/issues/77404>
185            let bases = bases_init.skip(delta);
186            folded_bases.push(bases);
187            pippengers.push(pippenger);
188        }
189
190        for (i, coefficient) in polynomials.iter() {
191            let base = folded_bases[i - 1].next().unwrap();
192            pippengers[i - 1].add(base.borrow(), coefficient.into_bigint());
193        }
194
195        pippengers
196            .into_iter()
197            .map(|p| Commitment(p.finalize().into_affine()))
198            .collect::<Vec<_>>()
199    }
200
201    /// The commitment procedures for our tensor check protocol.
202    /// The algorithm takes advantage of the tree structure of folding polynomials in our protocol. Please refer to our paper for more details.
203    /// The function evaluates all the folding polynomials at a set of evaluation points `points` and produces a single batched evaluation proof.
204    /// `eta` is the random challenge for batching folding polynomials.
205    pub fn open_folding<'a, SF>(
206        &self,
207        polynomials: FoldedPolynomialTree<'a, E::ScalarField, SF>,
208        points: &[E::ScalarField],
209        etas: &[E::ScalarField],
210        max_msm_buffer: usize,
211    ) -> (Vec<Vec<E::ScalarField>>, EvaluationProof<E>)
212    where
213        SG: Iterable,
214        SF: Iterable,
215        E: Pairing,
216        SG::Item: Borrow<E::G1Affine>,
217        SF::Item: Borrow<E::ScalarField> + Copy,
218    {
219        let n = polynomials.depth();
220        let mut pippenger = HashMapPippenger::<E::G1>::new(max_msm_buffer);
221        let mut folded_bases = Vec::new();
222        let zeros = vanishing_polynomial(points);
223        let mut remainders = vec![VecDeque::new(); n];
224
225        for i in 1..n + 1 {
226            let bases_init = self.powers_of_g.iter();
227            let delta = self.powers_of_g.len() - ceil_div(polynomials.len(), 1 << i);
228            // TODO: change `skip` to `advance_by` once rust-lang/rust#7774 is fixed.
229            // See <https://github.com/rust-lang/rust/issues/77404>
230            let bases = bases_init.skip(delta);
231
232            (0..points.len()).for_each(|_| {
233                remainders[i - 1].push_back(E::ScalarField::zero());
234            });
235
236            folded_bases.push(bases);
237        }
238
239        for (i, coefficient) in polynomials.iter() {
240            if i == 0 {
241                continue;
242            } // XXX. skip the 0th elements automatically
243
244            let base = folded_bases[i - 1].next().unwrap();
245            let quotient_coefficient = remainders[i - 1].pop_front().unwrap();
246            remainders[i - 1].push_back(coefficient);
247            (0..points.len()).for_each(|j| {
248                remainders[i - 1][j] -= zeros.coeffs[zeros.degree() - j - 1] * quotient_coefficient;
249            });
250
251            let scalar = etas[i - 1] * quotient_coefficient;
252            pippenger.add(base, scalar);
253        }
254
255        let evaluation_proof = pippenger.finalize().into_affine();
256        let remainders = remainders
257            .iter_mut()
258            .map(|x| x.make_contiguous().to_vec())
259            .collect::<Vec<_>>();
260
261        (remainders, EvaluationProof(evaluation_proof))
262    }
263}
264
265impl<'a, E: Pairing> From<&'a CommitterKey<E>>
266    for CommitterKeyStream<E, Reverse<&'a [E::G1Affine]>>
267{
268    fn from(ck: &'a CommitterKey<E>) -> Self {
269        CommitterKeyStream {
270            powers_of_g: Reverse(ck.powers_of_g.as_slice()),
271            powers_of_g2: ck.powers_of_g2.clone(),
272        }
273    }
274}
275
276impl<E, SG> From<&CommitterKeyStream<E, SG>> for VerifierKey<E>
277where
278    E: Pairing,
279    SG: Iterable,
280    SG::Item: Borrow<E::G1Affine>,
281{
282    fn from(ck: &CommitterKeyStream<E, SG>) -> Self {
283        let powers_of_g2 = ck.powers_of_g2.to_vec();
284        // take the first element from the stream
285        let g = *ck
286            .powers_of_g
287            .iter()
288            .last()
289            .expect(LENGTH_MISMATCH_MSG)
290            .borrow();
291        Self {
292            powers_of_g2,
293            powers_of_g: vec![g],
294        }
295    }
296}
ark_poly_commit/streaming_kzg/space.rs

ark_poly_commit/streaming_kzg/
space.rs
