1//! This module provides an implementation of a commitment engine
  2use crate::{
  3  errors::NovaError,
  4  traits::{
  5    commitment::{CommitmentEngineTrait, CommitmentTrait},
  6    AbsorbInROTrait, CompressedGroup, Group, ROTrait, TranscriptReprTrait,
  7  },
  8};
  9use core::{
 10  fmt::Debug,
 11  marker::PhantomData,
 12  ops::{Add, AddAssign, Mul, MulAssign},
 13};
 14use ff::Field;
 15use rayon::prelude::*;
 16use serde::{Deserialize, Serialize};
 17
 18/// A type that holds commitment generators
 19#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
 20pub struct CommitmentKey<G: Group> {
 21  ck: Vec<G::PreprocessedGroupElement>,
 22  _p: PhantomData<G>,
 23}
 24
 25/// A type that holds a commitment
 26#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
 27#[serde(bound = "")]
 28pub struct Commitment<G: Group> {
 29  pub(crate) comm: G,
 30}
 31
 32/// A type that holds a compressed commitment
 33#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
 34#[serde(bound = "")]
 35pub struct CompressedCommitment<G: Group> {
 36  comm: G::CompressedGroupElement,
 37}
 38
 39impl<G: Group> CommitmentTrait<G> for Commitment<G> {
 40  type CompressedCommitment = CompressedCommitment<G>;
 41
 42  fn compress(&self) -> Self::CompressedCommitment {
 43    CompressedCommitment {
 44      comm: self.comm.compress(),
 45    }
 46  }
 47
 48  fn to_coordinates(&self) -> (G::Base, G::Base, bool) {
 49    self.comm.to_coordinates()
 50  }
 51
 52  fn decompress(c: &Self::CompressedCommitment) -> Result<Self, NovaError> {
 53    let comm = c.comm.decompress();
 54    if comm.is_none() {
 55      return Err(NovaError::DecompressionError);
 56    }
 57    Ok(Commitment {
 58      comm: comm.unwrap(),
 59    })
 60  }
 61}
 62
 63impl<G: Group> Default for Commitment<G> {
 64  fn default() -> Self {
 65    Commitment { comm: G::zero() }
 66  }
 67}
 68
 69impl<G: Group> TranscriptReprTrait<G> for Commitment<G> {
 70  fn to_transcript_bytes(&self) -> Vec<u8> {
 71    let (x, y, is_infinity) = self.comm.to_coordinates();
 72    let is_infinity_byte = (!is_infinity).into();
 73    [
 74      x.to_transcript_bytes(),
 75      y.to_transcript_bytes(),
 76      [is_infinity_byte].to_vec(),
 77    ]
 78    .concat()
 79  }
 80}
 81
 82impl<G: Group> AbsorbInROTrait<G> for Commitment<G> {
 83  fn absorb_in_ro(&self, ro: &mut G::RO) {
 84    let (x, y, is_infinity) = self.comm.to_coordinates();
 85    ro.absorb(x);
 86    ro.absorb(y);
 87    ro.absorb(if is_infinity {
 88      G::Base::ONE
 89    } else {
 90      G::Base::ZERO
 91    });
 92  }
 93}
 94
 95impl<G: Group> TranscriptReprTrait<G> for CompressedCommitment<G> {
 96  fn to_transcript_bytes(&self) -> Vec<u8> {
 97    self.comm.to_transcript_bytes()
 98  }
 99}
100
101impl<G: Group> MulAssign<G::Scalar> for Commitment<G> {
102  fn mul_assign(&mut self, scalar: G::Scalar) {
103    let result = (self as &Commitment<G>).comm * scalar;
104    *self = Commitment { comm: result };
105  }
106}
107
108impl<'a, 'b, G: Group> Mul<&'b G::Scalar> for &'a Commitment<G> {
109  type Output = Commitment<G>;
110  fn mul(self, scalar: &'b G::Scalar) -> Commitment<G> {
111    Commitment {
112      comm: self.comm * scalar,
113    }
114  }
115}
116
117impl<G: Group> Mul<G::Scalar> for Commitment<G> {
118  type Output = Commitment<G>;
119
120  fn mul(self, scalar: G::Scalar) -> Commitment<G> {
121    Commitment {
122      comm: self.comm * scalar,
123    }
124  }
125}
126
127impl<'b, G: Group> AddAssign<&'b Commitment<G>> for Commitment<G> {
128  fn add_assign(&mut self, other: &'b Commitment<G>) {
129    let result = (self as &Commitment<G>).comm + other.comm;
130    *self = Commitment { comm: result };
131  }
132}
133
134impl<'a, 'b, G: Group> Add<&'b Commitment<G>> for &'a Commitment<G> {
135  type Output = Commitment<G>;
136  fn add(self, other: &'b Commitment<G>) -> Commitment<G> {
137    Commitment {
138      comm: self.comm + other.comm,
139    }
140  }
141}
142
143macro_rules! define_add_variants {
144  (G = $g:path, LHS = $lhs:ty, RHS = $rhs:ty, Output = $out:ty) => {
145    impl<'b, G: $g> Add<&'b $rhs> for $lhs {
146      type Output = $out;
147      fn add(self, rhs: &'b $rhs) -> $out {
148        &self + rhs
149      }
150    }
151
152    impl<'a, G: $g> Add<$rhs> for &'a $lhs {
153      type Output = $out;
154      fn add(self, rhs: $rhs) -> $out {
155        self + &rhs
156      }
157    }
158
159    impl<G: $g> Add<$rhs> for $lhs {
160      type Output = $out;
161      fn add(self, rhs: $rhs) -> $out {
162        &self + &rhs
163      }
164    }
165  };
166}
167
168macro_rules! define_add_assign_variants {
169  (G = $g:path, LHS = $lhs:ty, RHS = $rhs:ty) => {
170    impl<G: $g> AddAssign<$rhs> for $lhs {
171      fn add_assign(&mut self, rhs: $rhs) {
172        *self += &rhs;
173      }
174    }
175  };
176}
177
178define_add_assign_variants!(G = Group, LHS = Commitment<G>, RHS = Commitment<G>);
179define_add_variants!(G = Group, LHS = Commitment<G>, RHS = Commitment<G>, Output = Commitment<G>);
180
181/// Provides a commitment engine
182#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
183pub struct CommitmentEngine<G: Group> {
184  _p: PhantomData<G>,
185}
186
187impl<G: Group> CommitmentEngineTrait<G> for CommitmentEngine<G> {
188  type CommitmentKey = CommitmentKey<G>;
189  type Commitment = Commitment<G>;
190
191  fn setup(label: &'static [u8], n: usize) -> Self::CommitmentKey {
192    Self::CommitmentKey {
193      ck: G::from_label(label, n.next_power_of_two()),
194      _p: Default::default(),
195    }
196  }
197
198  fn commit(ck: &Self::CommitmentKey, v: &[G::Scalar]) -> Self::Commitment {
199    assert!(ck.ck.len() >= v.len());
200    Commitment {
201      comm: G::vartime_multiscalar_mul(v, &ck.ck[..v.len()]),
202    }
203  }
204}
205
206/// A trait listing properties of a commitment key that can be managed in a divide-and-conquer fashion
207pub trait CommitmentKeyExtTrait<G: Group> {
208  /// Holds the type of the commitment engine
209  type CE: CommitmentEngineTrait<G>;
210
211  /// Splits the commitment key into two pieces at a specified point
212  fn split_at(&self, n: usize) -> (Self, Self)
213  where
214    Self: Sized;
215
216  /// Combines two commitment keys into one
217  fn combine(&self, other: &Self) -> Self;
218
219  /// Folds the two commitment keys into one using the provided weights
220  fn fold(&self, w1: &G::Scalar, w2: &G::Scalar) -> Self;
221
222  /// Scales the commitment key using the provided scalar
223  fn scale(&self, r: &G::Scalar) -> Self;
224
225  /// Reinterprets commitments as commitment keys
226  fn reinterpret_commitments_as_ck(
227    c: &[<<<Self as CommitmentKeyExtTrait<G>>::CE as CommitmentEngineTrait<G>>::Commitment as CommitmentTrait<G>>::CompressedCommitment],
228  ) -> Result<Self, NovaError>
229  where
230    Self: Sized;
231}
232
233impl<G: Group> CommitmentKeyExtTrait<G> for CommitmentKey<G> {
234  type CE = CommitmentEngine<G>;
235
236  fn split_at(&self, n: usize) -> (CommitmentKey<G>, CommitmentKey<G>) {
237    (
238      CommitmentKey {
239        ck: self.ck[0..n].to_vec(),
240        _p: Default::default(),
241      },
242      CommitmentKey {
243        ck: self.ck[n..].to_vec(),
244        _p: Default::default(),
245      },
246    )
247  }
248
249  fn combine(&self, other: &CommitmentKey<G>) -> CommitmentKey<G> {
250    let ck = {
251      let mut c = self.ck.clone();
252      c.extend(other.ck.clone());
253      c
254    };
255    CommitmentKey {
256      ck,
257      _p: Default::default(),
258    }
259  }
260
261  // combines the left and right halves of `self` using `w1` and `w2` as the weights
262  fn fold(&self, w1: &G::Scalar, w2: &G::Scalar) -> CommitmentKey<G> {
263    let w = vec![*w1, *w2];
264    let (L, R) = self.split_at(self.ck.len() / 2);
265
266    let ck = (0..self.ck.len() / 2)
267      .into_par_iter()
268      .map(|i| {
269        let bases = [L.ck[i].clone(), R.ck[i].clone()].to_vec();
270        G::vartime_multiscalar_mul(&w, &bases).preprocessed()
271      })
272      .collect();
273
274    CommitmentKey {
275      ck,
276      _p: Default::default(),
277    }
278  }
279
280  /// Scales each element in `self` by `r`
281  fn scale(&self, r: &G::Scalar) -> Self {
282    let ck_scaled = self
283      .ck
284      .clone()
285      .into_par_iter()
286      .map(|g| G::vartime_multiscalar_mul(&[*r], &[g]).preprocessed())
287      .collect();
288
289    CommitmentKey {
290      ck: ck_scaled,
291      _p: Default::default(),
292    }
293  }
294
295  /// reinterprets a vector of commitments as a set of generators
296  fn reinterpret_commitments_as_ck(c: &[CompressedCommitment<G>]) -> Result<Self, NovaError> {
297    let d = (0..c.len())
298      .into_par_iter()
299      .map(|i| Commitment::<G>::decompress(&c[i]))
300      .collect::<Result<Vec<Commitment<G>>, NovaError>>()?;
301    let ck = (0..d.len())
302      .into_par_iter()
303      .map(|i| d[i].comm.preprocessed())
304      .collect();
305    Ok(CommitmentKey {
306      ck,
307      _p: Default::default(),
308    })
309  }
310}