ark_poly_commit/
data_structures.rs

1use crate::Polynomial;
2use ark_ff::{Field, PrimeField, ToConstraintField};
3use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
4use ark_std::{
5    borrow::Borrow,
6    marker::PhantomData,
7    ops::{AddAssign, MulAssign, SubAssign},
8    rand::RngCore,
9};
10#[cfg(not(feature = "std"))]
11use ark_std::{string::String, vec::Vec};
12
13/// Labels a `LabeledPolynomial` or a `LabeledCommitment`.
14pub type PolynomialLabel = String;
15
16/// Defines the minimal interface for public params for any polynomial
17/// commitment scheme.
18pub trait PCUniversalParams:
19    Clone + core::fmt::Debug + CanonicalSerialize + CanonicalDeserialize
20{
21    /// Outputs the maximum degree supported by the committer key.
22    fn max_degree(&self) -> usize;
23}
24
25/// Defines the minimal interface of committer keys for any polynomial
26/// commitment scheme.
27pub trait PCCommitterKey:
28    Clone + core::fmt::Debug + CanonicalSerialize + CanonicalDeserialize
29{
30    /// Outputs the maximum degree supported by the universal parameters
31    /// `Self` was derived from.
32    fn max_degree(&self) -> usize;
33
34    /// Outputs the maximum degree supported by the committer key.
35    fn supported_degree(&self) -> usize;
36}
37
38/// Defines the minimal interface of verifier keys for any polynomial
39/// commitment scheme.
40pub trait PCVerifierKey:
41    Clone + core::fmt::Debug + CanonicalSerialize + CanonicalDeserialize
42{
43    /// Outputs the maximum degree supported by the universal parameters
44    /// `Self` was derived from.
45    fn max_degree(&self) -> usize;
46
47    /// Outputs the maximum degree supported by the verifier key.
48    fn supported_degree(&self) -> usize;
49}
50
51/// Defines the minimal interface of prepared verifier keys for any polynomial
52/// commitment scheme.
53pub trait PCPreparedVerifierKey<Unprepared: PCVerifierKey> {
54    /// prepare
55    fn prepare(vk: &Unprepared) -> Self;
56}
57
58/// Defines the minimal interface of commitments for any polynomial
59/// commitment scheme.
60pub trait PCCommitment: Clone + CanonicalSerialize + CanonicalDeserialize {
61    /// Outputs a non-hiding commitment to the zero polynomial.
62    fn empty() -> Self;
63
64    /// Does this commitment have a degree bound?
65    fn has_degree_bound(&self) -> bool;
66}
67
68/// Defines the minimal interface of prepared commitments for any polynomial
69/// commitment scheme.
70pub trait PCPreparedCommitment<UNPREPARED: PCCommitment>: Clone {
71    /// prepare
72    fn prepare(comm: &UNPREPARED) -> Self;
73}
74
75/// Defines the minimal interface of commitment state for any polynomial
76/// commitment scheme. It might be randomness etc.
77pub trait PCCommitmentState: Clone + CanonicalSerialize + CanonicalDeserialize {
78    /// This is the type of `Randomness` that the `rand` method returns
79    type Randomness: Clone + CanonicalSerialize + CanonicalDeserialize;
80
81    /// Outputs empty randomness that does not hide the commitment.
82    fn empty() -> Self;
83
84    /// Samples randomness for commitments;
85    /// `num_queries` specifies the number of queries that the commitment will be opened at.
86    /// `has_degree_bound` indicates that the corresponding commitment has an enforced
87    /// `num_vars` specifies the number of variables for multivariate commitment.
88    /// strict degree bound.
89    fn rand<R: RngCore>(
90        num_queries: usize,
91        has_degree_bound: bool,
92        num_vars: Option<usize>,
93        rng: &mut R,
94    ) -> Self::Randomness;
95}
96/// A proof of satisfaction of linear combinations.
97#[derive(Clone, CanonicalSerialize, CanonicalDeserialize)]
98pub struct BatchLCProof<F: PrimeField, T: Clone + CanonicalSerialize + CanonicalDeserialize> {
99    /// Evaluation proof.
100    pub proof: T,
101    /// Evaluations required to verify the proof.
102    pub evals: Option<Vec<F>>,
103}
104
105/// A polynomial along with information about its degree bound (if any), and the
106/// maximum number of queries that will be made to it. This latter number determines
107/// the amount of protection that will be provided to a commitment for this polynomial.
108#[derive(Debug, Clone, CanonicalSerialize, CanonicalDeserialize)]
109pub struct LabeledPolynomial<F: Field, P: Polynomial<F>> {
110    label: PolynomialLabel,
111    polynomial: P,
112    degree_bound: Option<usize>,
113    hiding_bound: Option<usize>,
114    _field: PhantomData<F>,
115}
116
117impl<'a, F: Field, P: Polynomial<F>> core::ops::Deref for LabeledPolynomial<F, P> {
118    type Target = P;
119
120    fn deref(&self) -> &Self::Target {
121        &self.polynomial
122    }
123}
124
125impl<'a, F: Field, P: Polynomial<F>> LabeledPolynomial<F, P> {
126    /// Construct a new labeled polynomial.
127    pub fn new(
128        label: PolynomialLabel,
129        polynomial: P,
130        degree_bound: Option<usize>,
131        hiding_bound: Option<usize>,
132    ) -> Self {
133        Self {
134            label,
135            polynomial: polynomial,
136            degree_bound,
137            hiding_bound,
138            _field: PhantomData,
139        }
140    }
141
142    /// Return the label for `self`.
143    pub fn label(&self) -> &String {
144        &self.label
145    }
146
147    /// Retrieve an immutable reference to the polynomial contained in `self`.
148    pub fn polynomial(&self) -> &P {
149        &self.polynomial
150    }
151    /// Retrieve a mutable reference to the polynomial contained in `self`
152    pub fn polynomial_mut(&mut self) -> &mut P {
153        &mut self.polynomial
154    }
155
156    /// Evaluate the polynomial in `self`.
157    pub fn evaluate(&self, point: &P::Point) -> F {
158        self.polynomial.evaluate(point)
159    }
160
161    /// Retrieve the degree of the polynomial in `self`.
162    pub fn degree(&self) -> usize {
163        self.polynomial.degree()
164    }
165
166    /// Retrieve the degree bound in `self`.
167    pub fn degree_bound(&self) -> Option<usize> {
168        self.degree_bound
169    }
170
171    /// Retrieve whether the polynomial in `self` should be hidden.
172    pub fn is_hiding(&self) -> bool {
173        self.hiding_bound.is_some()
174    }
175
176    /// Retrieve the hiding bound for the polynomial in `self`.
177    pub fn hiding_bound(&self) -> Option<usize> {
178        self.hiding_bound
179    }
180}
181
182/// A commitment along with information about its degree bound (if any).
183#[derive(Clone)]
184pub struct LabeledCommitment<C: PCCommitment> {
185    label: PolynomialLabel,
186    commitment: C,
187    degree_bound: Option<usize>,
188}
189
190impl<F: Field, C: PCCommitment + ToConstraintField<F>> ToConstraintField<F>
191    for LabeledCommitment<C>
192{
193    fn to_field_elements(&self) -> Option<Vec<F>> {
194        self.commitment.to_field_elements()
195    }
196}
197
198impl<C: PCCommitment> LabeledCommitment<C> {
199    /// Instantiate a new polynomial_context.
200    pub fn new(label: PolynomialLabel, commitment: C, degree_bound: Option<usize>) -> Self {
201        Self {
202            label,
203            commitment,
204            degree_bound,
205        }
206    }
207
208    /// Return the label for `self`.
209    pub fn label(&self) -> &String {
210        &self.label
211    }
212
213    /// Retrieve the commitment from `self`.
214    pub fn commitment(&self) -> &C {
215        &self.commitment
216    }
217
218    /// Retrieve the degree bound in `self`.
219    pub fn degree_bound(&self) -> Option<usize> {
220        self.degree_bound
221    }
222}
223
224/// A term in a linear combination.
225#[derive(Hash, Ord, PartialOrd, Clone, Eq, PartialEq, Debug)]
226pub enum LCTerm {
227    /// The constant term representing `one`.
228    One,
229    /// Label for a polynomial.
230    PolyLabel(String),
231}
232
233impl LCTerm {
234    /// Returns `true` if `self == LCTerm::One`
235    #[inline]
236    pub fn is_one(&self) -> bool {
237        if let LCTerm::One = self {
238            true
239        } else {
240            false
241        }
242    }
243}
244
245impl From<PolynomialLabel> for LCTerm {
246    fn from(other: PolynomialLabel) -> Self {
247        Self::PolyLabel(other)
248    }
249}
250
251impl<'a> From<&'a str> for LCTerm {
252    fn from(other: &str) -> Self {
253        Self::PolyLabel(other.into())
254    }
255}
256
257impl core::convert::TryInto<PolynomialLabel> for LCTerm {
258    type Error = ();
259    fn try_into(self) -> Result<PolynomialLabel, ()> {
260        match self {
261            Self::One => Err(()),
262            Self::PolyLabel(l) => Ok(l),
263        }
264    }
265}
266
267impl<'a> core::convert::TryInto<&'a PolynomialLabel> for &'a LCTerm {
268    type Error = ();
269
270    fn try_into(self) -> Result<&'a PolynomialLabel, ()> {
271        match self {
272            LCTerm::One => Err(()),
273            LCTerm::PolyLabel(l) => Ok(l),
274        }
275    }
276}
277
278impl<B: Borrow<String>> PartialEq<B> for LCTerm {
279    fn eq(&self, other: &B) -> bool {
280        match self {
281            Self::One => false,
282            Self::PolyLabel(l) => l == other.borrow(),
283        }
284    }
285}
286
287/// A labeled linear combinations of polynomials.
288#[derive(Clone, Debug)]
289pub struct LinearCombination<F> {
290    /// The label.
291    pub label: String,
292    /// The linear combination of `(coeff, poly_label)` pairs.
293    pub terms: Vec<(F, LCTerm)>,
294}
295
296impl<F: Field> LinearCombination<F> {
297    /// Construct an empty labeled linear combination.
298    pub fn empty(label: impl Into<String>) -> Self {
299        Self {
300            label: label.into(),
301            terms: Vec::new(),
302        }
303    }
304
305    /// Construct a new labeled linear combination.
306    /// with the terms specified in `term`.
307    pub fn new(label: impl Into<String>, terms: Vec<(F, impl Into<LCTerm>)>) -> Self {
308        let terms = terms.into_iter().map(|(c, t)| (c, t.into())).collect();
309        Self {
310            label: label.into(),
311            terms: terms,
312        }
313    }
314
315    /// Returns the label of the linear combination.
316    pub fn label(&self) -> &String {
317        &self.label
318    }
319
320    /// Returns `true` if the linear combination has no terms.
321    pub fn is_empty(&self) -> bool {
322        self.terms.is_empty()
323    }
324
325    /// Add a term to the linear combination.
326    pub fn push(&mut self, term: (F, LCTerm)) -> &mut Self {
327        self.terms.push(term);
328        self
329    }
330}
331
332impl<'a, F: Field> AddAssign<(F, &'a LinearCombination<F>)> for LinearCombination<F> {
333    fn add_assign(&mut self, (coeff, other): (F, &'a LinearCombination<F>)) {
334        self.terms
335            .extend(other.terms.iter().map(|(c, t)| (coeff * c, t.clone())));
336    }
337}
338
339impl<'a, F: Field> SubAssign<(F, &'a LinearCombination<F>)> for LinearCombination<F> {
340    fn sub_assign(&mut self, (coeff, other): (F, &'a LinearCombination<F>)) {
341        self.terms
342            .extend(other.terms.iter().map(|(c, t)| (-coeff * c, t.clone())));
343    }
344}
345
346impl<'a, F: Field> AddAssign<&'a LinearCombination<F>> for LinearCombination<F> {
347    fn add_assign(&mut self, other: &'a LinearCombination<F>) {
348        self.terms.extend(other.terms.iter().cloned());
349    }
350}
351
352impl<'a, F: Field> SubAssign<&'a LinearCombination<F>> for LinearCombination<F> {
353    fn sub_assign(&mut self, other: &'a LinearCombination<F>) {
354        self.terms
355            .extend(other.terms.iter().map(|(c, t)| (-*c, t.clone())));
356    }
357}
358
359impl<F: Field> AddAssign<F> for LinearCombination<F> {
360    fn add_assign(&mut self, coeff: F) {
361        self.terms.push((coeff, LCTerm::One));
362    }
363}
364
365impl<F: Field> SubAssign<F> for LinearCombination<F> {
366    fn sub_assign(&mut self, coeff: F) {
367        self.terms.push((-coeff, LCTerm::One));
368    }
369}
370
371impl<F: Field> MulAssign<F> for LinearCombination<F> {
372    fn mul_assign(&mut self, coeff: F) {
373        self.terms.iter_mut().for_each(|(c, _)| *c *= coeff);
374    }
375}
376
377impl<F: Field> core::ops::Deref for LinearCombination<F> {
378    type Target = [(F, LCTerm)];
379
380    fn deref(&self) -> &Self::Target {
381        &self.terms
382    }
383}
ark_poly_commit/data_structures.rs

ark_poly_commit/
data_structures.rs
