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