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::{CommitmentEngineTrait, CommitmentGensTrait, CommitmentTrait},
6 AbsorbInROTrait, AppendToTranscriptTrait, CompressedGroup, Group, ROTrait,
7 TranscriptEngineTrait,
8 },
9};
10use core::{
11 fmt::Debug,
12 marker::PhantomData,
13 ops::{Add, AddAssign, Mul, MulAssign},
14};
15use ff::{Field, PrimeField};
16use rayon::prelude::*;
17use serde::{Deserialize, Serialize};
18
19/// A type that holds commitment generators
20#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
21pub struct CommitmentGens<G: Group> {
22 gens: Vec<G::PreprocessedGroupElement>,
23 _p: PhantomData<G>,
24}
25
26/// A type that holds a commitment
27#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
28#[serde(bound = "")]
29pub struct Commitment<G: Group> {
30 pub(crate) comm: G,
31}
32
33/// A type that holds a compressed commitment
34#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
35#[serde(bound = "")]
36pub struct CompressedCommitment<G: Group> {
37 comm: G::CompressedGroupElement,
38}
39
40impl<G: Group> CommitmentGensTrait<G> for CommitmentGens<G> {
41 type Commitment = Commitment<G>;
42
43 fn new(label: &'static [u8], n: usize) -> Self {
44 CommitmentGens {
45 gens: G::from_label(label, n.next_power_of_two()),
46 _p: Default::default(),
47 }
48 }
49
50 fn len(&self) -> usize {
51 self.gens.len()
52 }
53
54 fn commit(&self, v: &[G::Scalar]) -> Self::Commitment {
55 assert!(self.gens.len() >= v.len());
56 Commitment {
57 comm: G::vartime_multiscalar_mul(v, &self.gens[..v.len()]),
58 }
59 }
60}
61
62impl<G: Group> CommitmentTrait<G> for Commitment<G> {
63 type CompressedCommitment = CompressedCommitment<G>;
64
65 fn compress(&self) -> Self::CompressedCommitment {
66 CompressedCommitment {
67 comm: self.comm.compress(),
68 }
69 }
70
71 fn to_coordinates(&self) -> (G::Base, G::Base, bool) {
72 self.comm.to_coordinates()
73 }
74
75 fn decompress(c: &Self::CompressedCommitment) -> Result<Self, NovaError> {
76 let comm = c.comm.decompress();
77 if comm.is_none() {
78 return Err(NovaError::DecompressionError);
79 }
80 Ok(Commitment {
81 comm: comm.unwrap(),
82 })
83 }
84}
85
86impl<G: Group> Default for Commitment<G> {
87 fn default() -> Self {
88 Commitment { comm: G::zero() }
89 }
90}
91
92impl<G: Group> AppendToTranscriptTrait<G> for Commitment<G> {
93 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut G::TE) {
94 let (x, y, is_infinity) = self.comm.to_coordinates();
95 let is_infinity_byte = if is_infinity { 0u8 } else { 1u8 };
96 let bytes = [
97 x.to_repr().as_ref(),
98 y.to_repr().as_ref(),
99 &[is_infinity_byte],
100 ]
101 .concat();
102 transcript.absorb_bytes(label, &bytes);
103 }
104}
105
106impl<G: Group> AbsorbInROTrait<G> for Commitment<G> {
107 fn absorb_in_ro(&self, ro: &mut G::RO) {
108 let (x, y, is_infinity) = self.comm.to_coordinates();
109 ro.absorb(x);
110 ro.absorb(y);
111 ro.absorb(if is_infinity {
112 G::Base::one()
113 } else {
114 G::Base::zero()
115 });
116 }
117}
118
119impl<G: Group> AppendToTranscriptTrait<G> for CompressedCommitment<G> {
120 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut G::TE) {
121 transcript.absorb_bytes(label, &self.comm.as_bytes());
122 }
123}
124
125impl<G: Group> MulAssign<G::Scalar> for Commitment<G> {
126 fn mul_assign(&mut self, scalar: G::Scalar) {
127 let result = (self as &Commitment<G>).comm * scalar;
128 *self = Commitment { comm: result };
129 }
130}
131
132impl<'a, 'b, G: Group> Mul<&'b G::Scalar> for &'a Commitment<G> {
133 type Output = Commitment<G>;
134 fn mul(self, scalar: &'b G::Scalar) -> Commitment<G> {
135 Commitment {
136 comm: self.comm * scalar,
137 }
138 }
139}
140
141impl<G: Group> Mul<G::Scalar> for Commitment<G> {
142 type Output = Commitment<G>;
143
144 fn mul(self, scalar: G::Scalar) -> Commitment<G> {
145 Commitment {
146 comm: self.comm * scalar,
147 }
148 }
149}
150
151impl<'b, G: Group> AddAssign<&'b Commitment<G>> for Commitment<G> {
152 fn add_assign(&mut self, other: &'b Commitment<G>) {
153 let result = (self as &Commitment<G>).comm + other.comm;
154 *self = Commitment { comm: result };
155 }
156}
157
158impl<'a, 'b, G: Group> Add<&'b Commitment<G>> for &'a Commitment<G> {
159 type Output = Commitment<G>;
160 fn add(self, other: &'b Commitment<G>) -> Commitment<G> {
161 Commitment {
162 comm: self.comm + other.comm,
163 }
164 }
165}
166
167macro_rules! define_add_variants {
168 (G = $g:path, LHS = $lhs:ty, RHS = $rhs:ty, Output = $out:ty) => {
169 impl<'b, G: $g> Add<&'b $rhs> for $lhs {
170 type Output = $out;
171 fn add(self, rhs: &'b $rhs) -> $out {
172 &self + rhs
173 }
174 }
175
176 impl<'a, G: $g> Add<$rhs> for &'a $lhs {
177 type Output = $out;
178 fn add(self, rhs: $rhs) -> $out {
179 self + &rhs
180 }
181 }
182
183 impl<G: $g> Add<$rhs> for $lhs {
184 type Output = $out;
185 fn add(self, rhs: $rhs) -> $out {
186 &self + &rhs
187 }
188 }
189 };
190}
191
192macro_rules! define_add_assign_variants {
193 (G = $g:path, LHS = $lhs:ty, RHS = $rhs:ty) => {
194 impl<G: $g> AddAssign<$rhs> for $lhs {
195 fn add_assign(&mut self, rhs: $rhs) {
196 *self += &rhs;
197 }
198 }
199 };
200}
201
202define_add_assign_variants!(G = Group, LHS = Commitment<G>, RHS = Commitment<G>);
203define_add_variants!(G = Group, LHS = Commitment<G>, RHS = Commitment<G>, Output = Commitment<G>);
204
205/// Provides a commitment engine
206#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
207pub struct CommitmentEngine<G: Group> {
208 _p: PhantomData<G>,
209}
210
211impl<G: Group> CommitmentEngineTrait<G> for CommitmentEngine<G> {
212 type CommitmentGens = CommitmentGens<G>;
213 type Commitment = Commitment<G>;
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>>::Commitment as CommitmentTrait<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(c: &[CompressedCommitment<G>]) -> Result<Self, NovaError> {
309 let d = (0..c.len())
310 .into_par_iter()
311 .map(|i| Commitment::<G>::decompress(&c[i]))
312 .collect::<Result<Vec<Commitment<G>>, NovaError>>()?;
313 let gens = (0..d.len())
314 .into_par_iter()
315 .map(|i| d[i].comm.preprocessed())
316 .collect();
317 Ok(CommitmentGens {
318 gens,
319 _p: Default::default(),
320 })
321 }
322}