ark_poly_commit/marlin/marlin_pc/
data_structures.rs

1use crate::{
2    kzg10, DenseUVPolynomial, PCCommitment, PCCommitmentState, PCCommitterKey,
3    PCPreparedCommitment, PCPreparedVerifierKey, PCVerifierKey,
4};
5use ark_ec::{pairing::Pairing, AdditiveGroup};
6use ark_ff::{Field, PrimeField, ToConstraintField};
7use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
8#[cfg(not(feature = "std"))]
9use ark_std::vec::Vec;
10use ark_std::{
11    ops::{Add, AddAssign},
12    rand::RngCore,
13};
14/// `UniversalParams` are the universal parameters for the KZG10 scheme.
15pub type UniversalParams<E> = kzg10::UniversalParams<E>;
16
17/// `CommitterKey` is used to commit to and create evaluation proofs for a given
18/// polynomial.
19#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
20#[derivative(
21    Default(bound = ""),
22    Hash(bound = ""),
23    Clone(bound = ""),
24    Debug(bound = "")
25)]
26pub struct CommitterKey<E: Pairing> {
27    /// The key used to commit to polynomials.
28    pub powers: Vec<E::G1Affine>,
29
30    /// The key used to commit to shifted polynomials.
31    /// This is `None` if `self` does not support enforcing any degree bounds.
32    pub shifted_powers: Option<Vec<E::G1Affine>>,
33
34    /// The key used to commit to hiding polynomials.
35    pub powers_of_gamma_g: Vec<E::G1Affine>,
36
37    /// The degree bounds that are supported by `self`.
38    /// In ascending order from smallest to largest.
39    /// This is `None` if `self` does not support enforcing any degree bounds.
40    pub enforced_degree_bounds: Option<Vec<usize>>,
41    /// The maximum degree supported by the `UniversalParams` `self` was derived
42    /// from.
43    pub max_degree: usize,
44}
45
46impl<E: Pairing> CommitterKey<E> {
47    /// Obtain powers for the underlying KZG10 construction
48    pub fn powers<'a>(&'a self) -> kzg10::Powers<'a, E> {
49        kzg10::Powers {
50            powers_of_g: self.powers.as_slice().into(),
51            powers_of_gamma_g: self.powers_of_gamma_g.as_slice().into(),
52        }
53    }
54
55    /// Obtain powers for committing to shifted polynomials.
56    pub fn shifted_powers<'a>(
57        &'a self,
58        degree_bound: impl Into<Option<usize>>,
59    ) -> Option<kzg10::Powers<'a, E>> {
60        self.shifted_powers.as_ref().map(|shifted_powers| {
61            let powers_range = if let Some(degree_bound) = degree_bound.into() {
62                assert!(self
63                    .enforced_degree_bounds
64                    .as_ref()
65                    .unwrap()
66                    .contains(&degree_bound));
67                let max_bound = self
68                    .enforced_degree_bounds
69                    .as_ref()
70                    .unwrap()
71                    .last()
72                    .unwrap();
73                (max_bound - degree_bound)..
74            } else {
75                0..
76            };
77            let ck = kzg10::Powers {
78                powers_of_g: (&shifted_powers[powers_range]).into(),
79                powers_of_gamma_g: self.powers_of_gamma_g.as_slice().into(),
80            };
81            ck
82        })
83    }
84}
85
86impl<E: Pairing> PCCommitterKey for CommitterKey<E> {
87    fn max_degree(&self) -> usize {
88        self.max_degree
89    }
90
91    fn supported_degree(&self) -> usize {
92        self.powers.len() - 1
93    }
94}
95
96/// `VerifierKey` is used to check evaluation proofs for a given commitment.
97#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
98#[derivative(Default(bound = ""), Clone(bound = ""), Debug(bound = ""))]
99pub struct VerifierKey<E: Pairing> {
100    /// The verification key for the underlying KZG10 scheme.
101    pub vk: kzg10::VerifierKey<E>,
102    /// Information required to enforce degree bounds. Each pair
103    /// is of the form `(degree_bound, shifting_advice)`.
104    /// The vector is sorted in ascending order of `degree_bound`.
105    /// This is `None` if `self` does not support enforcing any degree bounds.
106    pub degree_bounds_and_shift_powers: Option<Vec<(usize, E::G1Affine)>>,
107    /// The maximum degree supported by the `UniversalParams` `self` was derived
108    /// from.
109    pub max_degree: usize,
110    /// The maximum degree supported by the trimmed parameters that `self` is
111    /// a part of.
112    pub supported_degree: usize,
113}
114
115impl<E: Pairing> VerifierKey<E> {
116    /// Find the appropriate shift for the degree bound.
117    pub fn get_shift_power(&self, bound: usize) -> Option<E::G1Affine> {
118        self.degree_bounds_and_shift_powers.as_ref().and_then(|v| {
119            v.binary_search_by(|(d, _)| d.cmp(&bound))
120                .ok()
121                .map(|i| v[i].1)
122        })
123    }
124}
125
126impl<E: Pairing> PCVerifierKey for VerifierKey<E> {
127    fn max_degree(&self) -> usize {
128        self.max_degree
129    }
130
131    fn supported_degree(&self) -> usize {
132        self.supported_degree
133    }
134}
135
136impl<E: Pairing> ToConstraintField<<E::TargetField as Field>::BasePrimeField> for VerifierKey<E>
137where
138    E::G1Affine: ToConstraintField<<E::TargetField as Field>::BasePrimeField>,
139    E::G2Affine: ToConstraintField<<E::TargetField as Field>::BasePrimeField>,
140{
141    fn to_field_elements(&self) -> Option<Vec<<E::TargetField as Field>::BasePrimeField>> {
142        let mut res = Vec::new();
143        res.extend_from_slice(&self.vk.to_field_elements().unwrap());
144
145        if let Some(degree_bounds_and_shift_powers) = &self.degree_bounds_and_shift_powers {
146            for (d, shift_power) in degree_bounds_and_shift_powers.iter() {
147                let d_elem: <E::TargetField as Field>::BasePrimeField = (*d as u64).into();
148
149                res.push(d_elem);
150                res.extend_from_slice(&shift_power.to_field_elements().unwrap());
151            }
152        }
153
154        Some(res)
155    }
156}
157
158/// `PreparedVerifierKey` is used to check evaluation proofs for a given commitment.
159#[derive(Derivative)]
160#[derivative(Clone(bound = ""), Debug(bound = ""))]
161pub struct PreparedVerifierKey<E: Pairing> {
162    /// The verification key for the underlying KZG10 scheme.
163    pub prepared_vk: kzg10::PreparedVerifierKey<E>,
164    /// Information required to enforce degree bounds. Each pair
165    /// is of the form `(degree_bound, shifting_advice)`.
166    /// This is `None` if `self` does not support enforcing any degree bounds.
167    pub prepared_degree_bounds_and_shift_powers: Option<Vec<(usize, Vec<E::G1Affine>)>>,
168    /// The maximum degree supported by the `UniversalParams` `self` was derived
169    /// from.
170    pub max_degree: usize,
171    /// The maximum degree supported by the trimmed parameters that `self` is
172    /// a part of.
173    pub supported_degree: usize,
174}
175
176impl<E: Pairing> PCPreparedVerifierKey<VerifierKey<E>> for PreparedVerifierKey<E> {
177    /// prepare `PreparedVerifierKey` from `VerifierKey`
178    fn prepare(vk: &VerifierKey<E>) -> Self {
179        let prepared_vk = kzg10::PreparedVerifierKey::<E>::prepare(&vk.vk);
180
181        let supported_bits = E::ScalarField::MODULUS_BIT_SIZE as usize;
182
183        let prepared_degree_bounds_and_shift_powers: Option<Vec<(usize, Vec<E::G1Affine>)>> =
184            if vk.degree_bounds_and_shift_powers.is_some() {
185                let mut res = Vec::<(usize, Vec<E::G1Affine>)>::new();
186
187                let degree_bounds_and_shift_powers =
188                    vk.degree_bounds_and_shift_powers.as_ref().unwrap();
189
190                for (d, shift_power) in degree_bounds_and_shift_powers {
191                    let mut prepared_shift_power = Vec::<E::G1Affine>::new();
192
193                    let mut cur = E::G1::from(shift_power.clone());
194                    for _ in 0..supported_bits {
195                        prepared_shift_power.push(cur.clone().into());
196                        cur.double_in_place();
197                    }
198
199                    res.push((d.clone(), prepared_shift_power));
200                }
201
202                Some(res)
203            } else {
204                None
205            };
206
207        Self {
208            prepared_vk,
209            prepared_degree_bounds_and_shift_powers,
210            max_degree: vk.max_degree,
211            supported_degree: vk.supported_degree,
212        }
213    }
214}
215
216/// Commitment to a polynomial that optionally enforces a degree bound.
217#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
218#[derivative(
219    Default(bound = ""),
220    Hash(bound = ""),
221    Clone(bound = ""),
222    Copy(bound = ""),
223    Debug(bound = ""),
224    PartialEq(bound = ""),
225    Eq(bound = "")
226)]
227pub struct Commitment<E: Pairing> {
228    /// A KZG10 commitment to the polynomial.
229    pub comm: kzg10::Commitment<E>,
230
231    /// A KZG10 commitment to the shifted polynomial.
232    /// This is `none` if the committed polynomial does not
233    /// enforce a strict degree bound.
234    pub shifted_comm: Option<kzg10::Commitment<E>>,
235}
236
237impl<E: Pairing> ToConstraintField<<E::TargetField as Field>::BasePrimeField> for Commitment<E>
238where
239    E::G1Affine: ToConstraintField<<E::TargetField as Field>::BasePrimeField>,
240{
241    fn to_field_elements(&self) -> Option<Vec<<E::TargetField as Field>::BasePrimeField>> {
242        let mut res = Vec::new();
243        res.extend_from_slice(&self.comm.to_field_elements().unwrap());
244
245        if let Some(shifted_comm) = &self.shifted_comm {
246            res.extend_from_slice(&shifted_comm.to_field_elements().unwrap());
247        }
248
249        Some(res)
250    }
251}
252
253impl<E: Pairing> PCCommitment for Commitment<E> {
254    #[inline]
255    fn empty() -> Self {
256        Self {
257            comm: kzg10::Commitment::empty(),
258            shifted_comm: Some(kzg10::Commitment::empty()),
259        }
260    }
261
262    fn has_degree_bound(&self) -> bool {
263        self.shifted_comm.is_some()
264    }
265}
266
267/// Prepared commitment to a polynomial that optionally enforces a degree bound.
268#[derive(Derivative)]
269#[derivative(
270    Hash(bound = ""),
271    Clone(bound = ""),
272    Debug(bound = ""),
273    PartialEq(bound = ""),
274    Eq(bound = "")
275)]
276pub struct PreparedCommitment<E: Pairing> {
277    pub(crate) prepared_comm: kzg10::PreparedCommitment<E>,
278    pub(crate) shifted_comm: Option<kzg10::Commitment<E>>,
279}
280
281impl<E: Pairing> PCPreparedCommitment<Commitment<E>> for PreparedCommitment<E> {
282    /// Prepare commitment to a polynomial that optionally enforces a degree bound.
283    fn prepare(comm: &Commitment<E>) -> Self {
284        let prepared_comm = kzg10::PreparedCommitment::<E>::prepare(&comm.comm);
285
286        let shifted_comm = comm.shifted_comm.clone();
287
288        Self {
289            prepared_comm,
290            shifted_comm,
291        }
292    }
293}
294
295/// `Randomness` hides the polynomial inside a commitment. It is output by `KZG10::commit`.
296#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
297#[derivative(
298    Hash(bound = ""),
299    Clone(bound = ""),
300    Debug(bound = ""),
301    PartialEq(bound = ""),
302    Eq(bound = "")
303)]
304pub struct Randomness<F: PrimeField, P: DenseUVPolynomial<F>> {
305    /// Commitment randomness for a KZG10 commitment.
306    pub rand: kzg10::Randomness<F, P>,
307    /// Commitment randomness for a KZG10 commitment to the shifted polynomial.
308    /// This is `None` if the committed polynomial does not enforce a strict
309    /// degree bound.
310    pub shifted_rand: Option<kzg10::Randomness<F, P>>,
311}
312
313impl<'a, F: PrimeField, P: DenseUVPolynomial<F>> Add<&'a Self> for Randomness<F, P> {
314    type Output = Self;
315
316    fn add(mut self, other: &'a Self) -> Self {
317        self += other;
318        self
319    }
320}
321
322impl<'a, F: PrimeField, P: DenseUVPolynomial<F>> AddAssign<&'a Self> for Randomness<F, P> {
323    #[inline]
324    fn add_assign(&mut self, other: &'a Self) {
325        self.rand += &other.rand;
326        if let Some(r1) = &mut self.shifted_rand {
327            *r1 += other
328                .shifted_rand
329                .as_ref()
330                .unwrap_or(&kzg10::Randomness::empty());
331        } else {
332            self.shifted_rand = other.shifted_rand.as_ref().map(|r| r.clone());
333        }
334    }
335}
336
337impl<'a, F: PrimeField, P: DenseUVPolynomial<F>> Add<(F, &'a Randomness<F, P>)>
338    for Randomness<F, P>
339{
340    type Output = Self;
341
342    #[inline]
343    fn add(mut self, other: (F, &'a Randomness<F, P>)) -> Self {
344        self += other;
345        self
346    }
347}
348
349impl<'a, F: PrimeField, P: DenseUVPolynomial<F>> AddAssign<(F, &'a Randomness<F, P>)>
350    for Randomness<F, P>
351{
352    #[inline]
353    fn add_assign(&mut self, (f, other): (F, &'a Randomness<F, P>)) {
354        self.rand += (f, &other.rand);
355        let empty = kzg10::Randomness::empty();
356        if let Some(r1) = &mut self.shifted_rand {
357            *r1 += (f, other.shifted_rand.as_ref().unwrap_or(&empty));
358        } else {
359            self.shifted_rand = other.shifted_rand.as_ref().map(|r| empty + (f, r));
360        }
361    }
362}
363
364impl<F: PrimeField, P: DenseUVPolynomial<F>> PCCommitmentState for Randomness<F, P> {
365    type Randomness = Self;
366    fn empty() -> Self {
367        Self {
368            rand: kzg10::Randomness::empty(),
369            shifted_rand: None,
370        }
371    }
372
373    fn rand<R: RngCore>(
374        hiding_bound: usize,
375        has_degree_bound: bool,
376        _: Option<usize>,
377        rng: &mut R,
378    ) -> Self {
379        let shifted_rand = if has_degree_bound {
380            Some(kzg10::Randomness::rand(hiding_bound, false, None, rng))
381        } else {
382            None
383        };
384        Self {
385            rand: kzg10::Randomness::rand(hiding_bound, false, None, rng),
386            shifted_rand,
387        }
388    }
389}
ark_poly_commit/marlin/marlin_pc/data_structures.rs

ark_poly_commit/marlin/marlin_pc/
data_structures.rs
