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 },
10};
11use core::{
12 fmt::Debug,
13 marker::PhantomData,
14 ops::{Add, AddAssign, Mul, MulAssign},
15};
16use ff::Field;
17use merlin::Transcript;
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 for Commitment<G> {
100 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
101 transcript.append_message(label, self.comm.compress().as_bytes());
102 }
103}
104
105impl<G: Group> AbsorbInROTrait<G> for Commitment<G> {
106 fn absorb_in_ro(&self, ro: &mut G::RO) {
107 let (x, y, is_infinity) = self.comm.to_coordinates();
108 ro.absorb(x);
109 ro.absorb(y);
110 ro.absorb(if is_infinity {
111 G::Base::one()
112 } else {
113 G::Base::zero()
114 });
115 }
116}
117
118impl<C: CompressedGroup> AppendToTranscriptTrait for CompressedCommitment<C> {
119 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
120 transcript.append_message(label, self.comm.as_bytes());
121 }
122}
123
124impl<G: Group> MulAssign<G::Scalar> for Commitment<G> {
125 fn mul_assign(&mut self, scalar: G::Scalar) {
126 let result = (self as &Commitment<G>).comm * scalar;
127 *self = Commitment { comm: result };
128 }
129}
130
131impl<'a, 'b, G: Group> Mul<&'b G::Scalar> for &'a Commitment<G> {
132 type Output = Commitment<G>;
133 fn mul(self, scalar: &'b G::Scalar) -> Commitment<G> {
134 Commitment {
135 comm: self.comm * scalar,
136 }
137 }
138}
139
140impl<G: Group> Mul<G::Scalar> for Commitment<G> {
141 type Output = Commitment<G>;
142
143 fn mul(self, scalar: G::Scalar) -> Commitment<G> {
144 Commitment {
145 comm: self.comm * scalar,
146 }
147 }
148}
149
150impl<'b, G: Group> AddAssign<&'b Commitment<G>> for Commitment<G> {
151 fn add_assign(&mut self, other: &'b Commitment<G>) {
152 let result = (self as &Commitment<G>).comm + other.comm;
153 *self = Commitment { comm: result };
154 }
155}
156
157impl<'a, 'b, G: Group> Add<&'b Commitment<G>> for &'a Commitment<G> {
158 type Output = Commitment<G>;
159 fn add(self, other: &'b Commitment<G>) -> Commitment<G> {
160 Commitment {
161 comm: self.comm + other.comm,
162 }
163 }
164}
165
166macro_rules! define_add_variants {
167 (G = $g:path, LHS = $lhs:ty, RHS = $rhs:ty, Output = $out:ty) => {
168 impl<'b, G: $g> Add<&'b $rhs> for $lhs {
169 type Output = $out;
170 fn add(self, rhs: &'b $rhs) -> $out {
171 &self + rhs
172 }
173 }
174
175 impl<'a, G: $g> Add<$rhs> for &'a $lhs {
176 type Output = $out;
177 fn add(self, rhs: $rhs) -> $out {
178 self + &rhs
179 }
180 }
181
182 impl<G: $g> Add<$rhs> for $lhs {
183 type Output = $out;
184 fn add(self, rhs: $rhs) -> $out {
185 &self + &rhs
186 }
187 }
188 };
189}
190
191macro_rules! define_add_assign_variants {
192 (G = $g:path, LHS = $lhs:ty, RHS = $rhs:ty) => {
193 impl<G: $g> AddAssign<$rhs> for $lhs {
194 fn add_assign(&mut self, rhs: $rhs) {
195 *self += &rhs;
196 }
197 }
198 };
199}
200
201define_add_assign_variants!(G = Group, LHS = Commitment<G>, RHS = Commitment<G>);
202define_add_variants!(G = Group, LHS = Commitment<G>, RHS = Commitment<G>, Output = Commitment<G>);
203
204/// Provides a commitment engine
205#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
206pub struct CommitmentEngine<G: Group> {
207 _p: PhantomData<G>,
208}
209
210impl<G: Group> CommitmentEngineTrait<G> for CommitmentEngine<G> {
211 type CommitmentGens = CommitmentGens<G>;
212 type Commitment = Commitment<G>;
213 type CompressedCommitment = CompressedCommitment<G::CompressedGroupElement>;
214
215 fn commit(gens: &Self::CommitmentGens, v: &[G::Scalar]) -> Self::Commitment {
216 gens.commit(v)
217 }
218}
219
220pub(crate) trait CommitmentGensExtTrait<G: Group>: CommitmentGensTrait<G> {
221 type CE: CommitmentEngineTrait<G>;
222
223 /// Splits the commitment key into two pieces at a specified point
224 fn split_at(&self, n: usize) -> (Self, Self)
225 where
226 Self: Sized;
227
228 /// Combines two commitment keys into one
229 fn combine(&self, other: &Self) -> Self;
230
231 /// Folds the two commitment keys into one using the provided weights
232 fn fold(&self, w1: &G::Scalar, w2: &G::Scalar) -> Self;
233
234 /// Scales the commitment key using the provided scalar
235 fn scale(&self, r: &G::Scalar) -> Self;
236
237 /// Reinterprets commitments as commitment keys
238 fn reinterpret_commitments_as_gens(
239 c: &[<<Self as CommitmentGensExtTrait<G>>::CE as CommitmentEngineTrait<G>>::CompressedCommitment],
240 ) -> Result<Self, NovaError>
241 where
242 Self: Sized;
243}
244
245impl<G: Group> CommitmentGensExtTrait<G> for CommitmentGens<G> {
246 type CE = CommitmentEngine<G>;
247
248 fn split_at(&self, n: usize) -> (CommitmentGens<G>, CommitmentGens<G>) {
249 (
250 CommitmentGens {
251 gens: self.gens[0..n].to_vec(),
252 _p: Default::default(),
253 },
254 CommitmentGens {
255 gens: self.gens[n..].to_vec(),
256 _p: Default::default(),
257 },
258 )
259 }
260
261 fn combine(&self, other: &CommitmentGens<G>) -> CommitmentGens<G> {
262 let gens = {
263 let mut c = self.gens.clone();
264 c.extend(other.gens.clone());
265 c
266 };
267 CommitmentGens {
268 gens,
269 _p: Default::default(),
270 }
271 }
272
273 // combines the left and right halves of `self` using `w1` and `w2` as the weights
274 fn fold(&self, w1: &G::Scalar, w2: &G::Scalar) -> CommitmentGens<G> {
275 let w = vec![*w1, *w2];
276 let (L, R) = self.split_at(self.len() / 2);
277
278 let gens = (0..self.len() / 2)
279 .into_par_iter()
280 .map(|i| {
281 let bases = [L.gens[i].clone(), R.gens[i].clone()].to_vec();
282 G::vartime_multiscalar_mul(&w, &bases).preprocessed()
283 })
284 .collect();
285
286 CommitmentGens {
287 gens,
288 _p: Default::default(),
289 }
290 }
291
292 /// Scales each element in `self` by `r`
293 fn scale(&self, r: &G::Scalar) -> Self {
294 let gens_scaled = self
295 .gens
296 .clone()
297 .into_par_iter()
298 .map(|g| G::vartime_multiscalar_mul(&[*r], &[g]).preprocessed())
299 .collect();
300
301 CommitmentGens {
302 gens: gens_scaled,
303 _p: Default::default(),
304 }
305 }
306
307 /// reinterprets a vector of commitments as a set of generators
308 fn reinterpret_commitments_as_gens(
309 c: &[CompressedCommitment<G::CompressedGroupElement>],
310 ) -> Result<Self, NovaError> {
311 let d = (0..c.len())
312 .into_par_iter()
313 .map(|i| c[i].decompress())
314 .collect::<Result<Vec<Commitment<G>>, NovaError>>()?;
315 let gens = (0..d.len())
316 .into_par_iter()
317 .map(|i| d[i].comm.preprocessed())
318 .collect();
319 Ok(CommitmentGens {
320 gens,
321 _p: Default::default(),
322 })
323 }
324}