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 fn split_at(&self, n: usize) -> (CommitmentGens<G>, CommitmentGens<G>) {
65 (
66 CommitmentGens {
67 gens: self.gens[0..n].to_vec(),
68 _p: Default::default(),
69 },
70 CommitmentGens {
71 gens: self.gens[n..].to_vec(),
72 _p: Default::default(),
73 },
74 )
75 }
76
77 fn combine(&self, other: &CommitmentGens<G>) -> CommitmentGens<G> {
78 let gens = {
79 let mut c = self.gens.clone();
80 c.extend(other.gens.clone());
81 c
82 };
83 CommitmentGens {
84 gens,
85 _p: Default::default(),
86 }
87 }
88
89 // combines the left and right halves of `self` using `w1` and `w2` as the weights
90 fn fold(&self, w1: &G::Scalar, w2: &G::Scalar) -> CommitmentGens<G> {
91 let w = vec![*w1, *w2];
92 let (L, R) = self.split_at(self.len() / 2);
93
94 let gens = (0..self.len() / 2)
95 .into_par_iter()
96 .map(|i| {
97 let gens = CommitmentGens::<G> {
98 gens: [L.gens[i].clone(), R.gens[i].clone()].to_vec(),
99 _p: Default::default(),
100 };
101 gens.commit(&w).comm.preprocessed()
102 })
103 .collect();
104
105 CommitmentGens {
106 gens,
107 _p: Default::default(),
108 }
109 }
110
111 /// Scales each element in `self` by `r`
112 fn scale(&self, r: &G::Scalar) -> Self {
113 let gens_scaled = self
114 .gens
115 .clone()
116 .into_par_iter()
117 .map(|g| {
118 let gens = CommitmentGens::<G> {
119 gens: vec![g],
120 _p: Default::default(),
121 };
122 gens.commit(&[*r]).comm.preprocessed()
123 })
124 .collect();
125
126 CommitmentGens {
127 gens: gens_scaled,
128 _p: Default::default(),
129 }
130 }
131
132 /// reinterprets a vector of commitments as a set of generators
133 fn reinterpret_commitments_as_gens(
134 c: &[CompressedCommitment<G::CompressedGroupElement>],
135 ) -> Result<Self, NovaError> {
136 let d = (0..c.len())
137 .into_par_iter()
138 .map(|i| c[i].decompress())
139 .collect::<Result<Vec<Commitment<G>>, NovaError>>()?;
140 let gens = (0..d.len())
141 .into_par_iter()
142 .map(|i| d[i].comm.preprocessed())
143 .collect();
144 Ok(CommitmentGens {
145 gens,
146 _p: Default::default(),
147 })
148 }
149}
150
151impl<G: Group> CommitmentTrait<G> for Commitment<G> {
152 type CompressedCommitment = CompressedCommitment<G::CompressedGroupElement>;
153
154 fn compress(&self) -> CompressedCommitment<G::CompressedGroupElement> {
155 CompressedCommitment {
156 comm: self.comm.compress(),
157 }
158 }
159
160 fn to_coordinates(&self) -> (G::Base, G::Base, bool) {
161 self.comm.to_coordinates()
162 }
163}
164
165impl<G: Group> Default for Commitment<G> {
166 fn default() -> Self {
167 Commitment { comm: G::zero() }
168 }
169}
170
171impl<C: CompressedGroup> CompressedCommitmentTrait<C> for CompressedCommitment<C> {
172 type Commitment = Commitment<C::GroupElement>;
173
174 fn decompress(&self) -> Result<Self::Commitment, NovaError> {
175 let comm = self.comm.decompress();
176 if comm.is_none() {
177 return Err(NovaError::DecompressionError);
178 }
179 Ok(Commitment {
180 comm: comm.unwrap(),
181 })
182 }
183}
184
185impl<G: Group> AppendToTranscriptTrait for Commitment<G> {
186 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
187 transcript.append_message(label, self.comm.compress().as_bytes());
188 }
189}
190
191impl<G: Group> AbsorbInROTrait<G> for Commitment<G> {
192 fn absorb_in_ro(&self, ro: &mut G::RO) {
193 let (x, y, is_infinity) = self.comm.to_coordinates();
194 ro.absorb(x);
195 ro.absorb(y);
196 ro.absorb(if is_infinity {
197 G::Base::one()
198 } else {
199 G::Base::zero()
200 });
201 }
202}
203
204impl<C: CompressedGroup> AppendToTranscriptTrait for CompressedCommitment<C> {
205 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
206 transcript.append_message(label, self.comm.as_bytes());
207 }
208}
209
210impl<G: Group> MulAssign<G::Scalar> for Commitment<G> {
211 fn mul_assign(&mut self, scalar: G::Scalar) {
212 let result = (self as &Commitment<G>).comm * scalar;
213 *self = Commitment { comm: result };
214 }
215}
216
217impl<'a, 'b, G: Group> Mul<&'b G::Scalar> for &'a Commitment<G> {
218 type Output = Commitment<G>;
219 fn mul(self, scalar: &'b G::Scalar) -> Commitment<G> {
220 Commitment {
221 comm: self.comm * scalar,
222 }
223 }
224}
225
226impl<G: Group> Mul<G::Scalar> for Commitment<G> {
227 type Output = Commitment<G>;
228
229 fn mul(self, scalar: G::Scalar) -> Commitment<G> {
230 Commitment {
231 comm: self.comm * scalar,
232 }
233 }
234}
235
236impl<'b, G: Group> AddAssign<&'b Commitment<G>> for Commitment<G> {
237 fn add_assign(&mut self, other: &'b Commitment<G>) {
238 let result = (self as &Commitment<G>).comm + other.comm;
239 *self = Commitment { comm: result };
240 }
241}
242
243impl<'a, 'b, G: Group> Add<&'b Commitment<G>> for &'a Commitment<G> {
244 type Output = Commitment<G>;
245 fn add(self, other: &'b Commitment<G>) -> Commitment<G> {
246 Commitment {
247 comm: self.comm + other.comm,
248 }
249 }
250}
251
252macro_rules! define_add_variants {
253 (G = $g:path, LHS = $lhs:ty, RHS = $rhs:ty, Output = $out:ty) => {
254 impl<'b, G: $g> Add<&'b $rhs> for $lhs {
255 type Output = $out;
256 fn add(self, rhs: &'b $rhs) -> $out {
257 &self + rhs
258 }
259 }
260
261 impl<'a, G: $g> Add<$rhs> for &'a $lhs {
262 type Output = $out;
263 fn add(self, rhs: $rhs) -> $out {
264 self + &rhs
265 }
266 }
267
268 impl<G: $g> Add<$rhs> for $lhs {
269 type Output = $out;
270 fn add(self, rhs: $rhs) -> $out {
271 &self + &rhs
272 }
273 }
274 };
275}
276
277macro_rules! define_add_assign_variants {
278 (G = $g:path, LHS = $lhs:ty, RHS = $rhs:ty) => {
279 impl<G: $g> AddAssign<$rhs> for $lhs {
280 fn add_assign(&mut self, rhs: $rhs) {
281 *self += &rhs;
282 }
283 }
284 };
285}
286
287define_add_assign_variants!(G = Group, LHS = Commitment<G>, RHS = Commitment<G>);
288define_add_variants!(G = Group, LHS = Commitment<G>, RHS = Commitment<G>, Output = Commitment<G>);
289
290/// Provides a commitment engine
291#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
292pub struct CommitmentEngine<G: Group> {
293 _p: PhantomData<G>,
294}
295
296impl<G: Group> CommitmentEngineTrait<G> for CommitmentEngine<G> {
297 type CommitmentGens = CommitmentGens<G>;
298 type Commitment = Commitment<G>;
299 type CompressedCommitment = CompressedCommitment<G::CompressedGroupElement>;
300
301 fn commit(gens: &Self::CommitmentGens, v: &[G::Scalar]) -> Self::Commitment {
302 gens.commit(v)
303 }
304}