Nova/src/spartan_with_ipa_pc/ipa.rs
src/spartan_with_ipa_pc/ipa.rsRaw
1#![allow(clippy::too_many_arguments)]
2use crate::commitments::{CommitGens, CommitTrait, Commitment, CompressedCommitment};
3use crate::errors::NovaError;
4use crate::traits::{AppendToTranscriptTrait, ChallengeTrait, Group};
5use core::iter;
6use ff::Field;
7use merlin::Transcript;
8use rayon::prelude::*;
9use std::marker::PhantomData;
10
11pub fn inner_product<T>(a: &[T], b: &[T]) -> T
12where
13 T: Field + Send + Sync,
14{
15 assert_eq!(a.len(), b.len());
16 (0..a.len())
17 .into_par_iter()
18 .map(|i| a[i] * b[i])
19 .reduce(T::zero, |x, y| x + y)
20}
21
22/// An inner product instance consists of a commitment to a vector `a` and another vector `b`
23/// and the claim that c = <a, b>.
24pub struct InnerProductInstance<G: Group> {
25 comm_a_vec: Commitment<G>,
26 b_vec: Vec<G::Scalar>,
27 c: G::Scalar,
28}
29
30impl<G: Group> InnerProductInstance<G> {
31 pub fn new(comm_a_vec: &Commitment<G>, b_vec: &[G::Scalar], c: &G::Scalar) -> Self {
32 InnerProductInstance {
33 comm_a_vec: *comm_a_vec,
34 b_vec: b_vec.to_vec(),
35 c: *c,
36 }
37 }
38}
39
40pub struct InnerProductWitness<G: Group> {
41 a_vec: Vec<G::Scalar>,
42}
43
44impl<G: Group> InnerProductWitness<G> {
45 pub fn new(a_vec: &[G::Scalar]) -> Self {
46 InnerProductWitness {
47 a_vec: a_vec.to_vec(),
48 }
49 }
50}
51
52/// A non-interactive folding scheme (NIFS) for inner product relations
53pub struct NIFSForInnerProduct<G: Group> {
54 cross_term: G::Scalar,
55}
56
57impl<G: Group> NIFSForInnerProduct<G> {
58 pub fn protocol_name() -> &'static [u8] {
59 b"NIFSForInnerProduct"
60 }
61
62 pub fn prove(
63 U1: &InnerProductInstance<G>,
64 W1: &InnerProductWitness<G>,
65 U2: &InnerProductInstance<G>,
66 W2: &InnerProductWitness<G>,
67 transcript: &mut Transcript,
68 ) -> (Self, InnerProductInstance<G>, InnerProductWitness<G>) {
69 transcript.append_message(b"protocol-name", Self::protocol_name());
70
71 // add the two commitments and two public vectors to the transcript
72 U1.comm_a_vec
73 .append_to_transcript(b"U1_comm_a_vec", transcript);
74 U1.b_vec.append_to_transcript(b"U1_b_vec", transcript);
75 U2.comm_a_vec
76 .append_to_transcript(b"U2_comm_a_vec", transcript);
77 U2.b_vec.append_to_transcript(b"U2_b_vec", transcript);
78
79 // compute the cross-term
80 let cross_term = inner_product(&W1.a_vec, &U2.b_vec) + inner_product(&W2.a_vec, &U1.b_vec);
81
82 // add the cross-term to the transcript
83 cross_term.append_to_transcript(b"cross_term", transcript);
84
85 // obtain a random challenge
86 let r = G::Scalar::challenge(b"r", transcript);
87
88 // fold the vectors and their inner product
89 let a_vec = W1
90 .a_vec
91 .par_iter()
92 .zip(W2.a_vec.par_iter())
93 .map(|(x1, x2)| *x1 + r * x2)
94 .collect::<Vec<G::Scalar>>();
95 let b_vec = U1
96 .b_vec
97 .par_iter()
98 .zip(U2.b_vec.par_iter())
99 .map(|(a1, a2)| *a1 + r * a2)
100 .collect::<Vec<G::Scalar>>();
101
102 let c = U1.c + r * r * U2.c + r * cross_term;
103 let comm_a_vec = U1.comm_a_vec + U2.comm_a_vec * r;
104
105 let W = InnerProductWitness { a_vec };
106 let U = InnerProductInstance {
107 comm_a_vec,
108 b_vec,
109 c,
110 };
111
112 (NIFSForInnerProduct { cross_term }, U, W)
113 }
114
115 pub fn verify(
116 &self,
117 U1: &InnerProductInstance<G>,
118 U2: &InnerProductInstance<G>,
119 transcript: &mut Transcript,
120 ) -> InnerProductInstance<G> {
121 transcript.append_message(b"protocol-name", Self::protocol_name());
122
123 // add the two commitments and two public vectors to the transcript
124 U1.comm_a_vec
125 .append_to_transcript(b"U1_comm_a_vec", transcript);
126 U1.b_vec.append_to_transcript(b"U1_b_vec", transcript);
127 U2.comm_a_vec
128 .append_to_transcript(b"U2_comm_a_vec", transcript);
129 U2.b_vec.append_to_transcript(b"U2_b_vec", transcript);
130
131 // add the cross-term to the transcript
132 self
133 .cross_term
134 .append_to_transcript(b"cross_term", transcript);
135
136 // obtain a random challenge
137 let r = G::Scalar::challenge(b"r", transcript);
138
139 // fold the vectors and their inner product
140 let b_vec = U1
141 .b_vec
142 .par_iter()
143 .zip(U2.b_vec.par_iter())
144 .map(|(a1, a2)| *a1 + r * a2)
145 .collect::<Vec<G::Scalar>>();
146 let c = U1.c + r * r * U2.c + r * self.cross_term;
147 let comm_a_vec = U1.comm_a_vec + U2.comm_a_vec * r;
148
149 InnerProductInstance {
150 comm_a_vec,
151 b_vec,
152 c,
153 }
154 }
155}
156
157/// An inner product argument
158#[derive(Debug)]
159pub struct InnerProductArgument<G: Group> {
160 L_vec: Vec<CompressedCommitment<G::CompressedGroupElement>>,
161 R_vec: Vec<CompressedCommitment<G::CompressedGroupElement>>,
162 a_hat: G::Scalar,
163 _p: PhantomData<G>,
164}
165
166impl<G: Group> InnerProductArgument<G> {
167 fn protocol_name() -> &'static [u8] {
168 b"inner product argument"
169 }
170
171 pub fn prove(
172 gens: &CommitGens<G>,
173 gens_c: &CommitGens<G>,
174 U: &InnerProductInstance<G>,
175 W: &InnerProductWitness<G>,
176 transcript: &mut Transcript,
177 ) -> Result<Self, NovaError> {
178 transcript.append_message(b"protocol-name", Self::protocol_name());
179
180 if U.b_vec.len() != W.a_vec.len() {
181 return Err(NovaError::InvalidInputLength);
182 }
183
184 U.comm_a_vec.append_to_transcript(b"comm_a_vec", transcript);
185 U.b_vec.append_to_transcript(b"b_vec", transcript);
186 U.c.append_to_transcript(b"c", transcript);
187
188 // sample a random base for commiting to the inner product
189 let r = G::Scalar::challenge(b"r", transcript);
190 let gens_c = gens_c.scale(&r);
191
192 // a closure that executes a step of the recursive inner product argument
193 let prove_inner = |a_vec: &[G::Scalar],
194 b_vec: &[G::Scalar],
195 gens: &CommitGens<G>,
196 transcript: &mut Transcript|
197 -> Result<
198 (
199 CompressedCommitment<G::CompressedGroupElement>,
200 CompressedCommitment<G::CompressedGroupElement>,
201 Vec<G::Scalar>,
202 Vec<G::Scalar>,
203 CommitGens<G>,
204 ),
205 NovaError,
206 > {
207 let n = a_vec.len();
208 let (gens_L, gens_R) = gens.split_at(n / 2);
209
210 let c_L = inner_product(&a_vec[0..n / 2], &b_vec[n / 2..n]);
211 let c_R = inner_product(&a_vec[n / 2..n], &b_vec[0..n / 2]);
212
213 let L = a_vec[0..n / 2]
214 .iter()
215 .chain(iter::once(&c_L))
216 .copied()
217 .collect::<Vec<G::Scalar>>()
218 .commit(&gens_R.combine(&gens_c))
219 .compress();
220 let R = a_vec[n / 2..n]
221 .iter()
222 .chain(iter::once(&c_R))
223 .copied()
224 .collect::<Vec<G::Scalar>>()
225 .commit(&gens_L.combine(&gens_c))
226 .compress();
227
228 L.append_to_transcript(b"L", transcript);
229 R.append_to_transcript(b"R", transcript);
230
231 let r = G::Scalar::challenge(b"challenge_r", transcript);
232 let r_inverse = r.invert().unwrap();
233
234 // fold the left half and the right half
235 let a_vec_folded = a_vec[0..n / 2]
236 .par_iter()
237 .zip(a_vec[n / 2..n].par_iter())
238 .map(|(a_L, a_R)| *a_L * r + r_inverse * *a_R)
239 .collect::<Vec<G::Scalar>>();
240
241 let b_vec_folded = b_vec[0..n / 2]
242 .par_iter()
243 .zip(b_vec[n / 2..n].par_iter())
244 .map(|(b_L, b_R)| *b_L * r_inverse + r * *b_R)
245 .collect::<Vec<G::Scalar>>();
246
247 let gens_folded = gens.fold(&r_inverse, &r);
248
249 Ok((L, R, a_vec_folded, b_vec_folded, gens_folded))
250 };
251
252 // two vectors to hold the logarithmic number of group elements
253 let mut L_vec: Vec<CompressedCommitment<G::CompressedGroupElement>> = Vec::new();
254 let mut R_vec: Vec<CompressedCommitment<G::CompressedGroupElement>> = Vec::new();
255
256 // we create mutable copies of vectors and generators
257 let mut a_vec = W.a_vec.to_vec();
258 let mut b_vec = U.b_vec.to_vec();
259 let mut gens = gens.clone();
260 for _i in 0..(U.b_vec.len() as f64).log2() as usize {
261 let (L, R, a_vec_folded, b_vec_folded, gens_folded) =
262 prove_inner(&a_vec, &b_vec, &gens, transcript)?;
263 L_vec.push(L);
264 R_vec.push(R);
265
266 a_vec = a_vec_folded;
267 b_vec = b_vec_folded;
268 gens = gens_folded;
269 }
270
271 Ok(InnerProductArgument {
272 L_vec,
273 R_vec,
274 a_hat: a_vec[0],
275 _p: Default::default(),
276 })
277 }
278
279 pub fn verify(
280 &self,
281 gens: &CommitGens<G>,
282 gens_c: &CommitGens<G>,
283 n: usize,
284 U: &InnerProductInstance<G>,
285 transcript: &mut Transcript,
286 ) -> Result<(), NovaError> {
287 transcript.append_message(b"protocol-name", Self::protocol_name());
288 if U.b_vec.len() != n
289 || n != (1 << self.L_vec.len())
290 || self.L_vec.len() != self.R_vec.len()
291 || self.L_vec.len() >= 32
292 {
293 return Err(NovaError::InvalidInputLength);
294 }
295
296 U.comm_a_vec.append_to_transcript(b"comm_a_vec", transcript);
297 U.b_vec.append_to_transcript(b"b_vec", transcript);
298 U.c.append_to_transcript(b"c", transcript);
299
300 // sample a random base for commiting to the inner product
301 let r = G::Scalar::challenge(b"r", transcript);
302 let gens_c = gens_c.scale(&r);
303
304 let P = U.comm_a_vec + [U.c].commit(&gens_c);
305
306 let batch_invert = |v: &[G::Scalar]| -> Result<Vec<G::Scalar>, NovaError> {
307 let mut products = vec![G::Scalar::zero(); v.len()];
308 let mut acc = G::Scalar::one();
309
310 for i in 0..v.len() {
311 products[i] = acc;
312 acc *= v[i];
313 }
314
315 // we can compute an inversion only if acc is non-zero
316 if acc == G::Scalar::zero() {
317 return Err(NovaError::InvalidInputLength);
318 }
319
320 // compute the inverse once for all entries
321 acc = acc.invert().unwrap();
322
323 let mut inv = vec![G::Scalar::zero(); v.len()];
324 for i in 0..v.len() {
325 let tmp = acc * v[v.len() - 1 - i];
326 inv[v.len() - 1 - i] = products[v.len() - 1 - i] * acc;
327 acc = tmp;
328 }
329
330 Ok(inv)
331 };
332
333 // compute a vector of public coins using self.L_vec and self.R_vec
334 let r = (0..self.L_vec.len())
335 .map(|i| {
336 self.L_vec[i].append_to_transcript(b"L", transcript);
337 self.R_vec[i].append_to_transcript(b"R", transcript);
338 G::Scalar::challenge(b"challenge_r", transcript)
339 })
340 .collect::<Vec<G::Scalar>>();
341
342 // precompute scalars necessary for verification
343 let r_square: Vec<G::Scalar> = (0..self.L_vec.len())
344 .into_par_iter()
345 .map(|i| r[i] * r[i])
346 .collect();
347 let r_inverse = batch_invert(&r)?;
348 let r_inverse_square: Vec<G::Scalar> = (0..self.L_vec.len())
349 .into_par_iter()
350 .map(|i| r_inverse[i] * r_inverse[i])
351 .collect();
352
353 // compute the vector with the tensor structure
354 let s = {
355 let mut s = vec![G::Scalar::zero(); n];
356 s[0] = {
357 let mut v = G::Scalar::one();
358 for r_inverse_i in &r_inverse {
359 v *= r_inverse_i;
360 }
361 v
362 };
363 for i in 1..n {
364 let pos_in_r = (31 - (i as u32).leading_zeros()) as usize;
365 s[i] = s[i - (1 << pos_in_r)] * r_square[(self.L_vec.len() - 1) - pos_in_r];
366 }
367 s
368 };
369
370 let gens_hat = {
371 let c = s.commit(gens).compress();
372 CommitGens::reinterpret_commitments_as_gens(&[c])?
373 };
374
375 let b_hat = inner_product(&U.b_vec, &s);
376
377 let P_hat = {
378 let gens_folded = {
379 let gens_L = CommitGens::reinterpret_commitments_as_gens(&self.L_vec)?;
380 let gens_R = CommitGens::reinterpret_commitments_as_gens(&self.R_vec)?;
381 let gens_P = CommitGens::reinterpret_commitments_as_gens(&[P.compress()])?;
382 gens_L.combine(&gens_R).combine(&gens_P)
383 };
384 r_square
385 .iter()
386 .chain(r_inverse_square.iter())
387 .chain(iter::once(&G::Scalar::one()))
388 .copied()
389 .collect::<Vec<G::Scalar>>()
390 .commit(&gens_folded)
391 };
392
393 if P_hat == [self.a_hat, self.a_hat * b_hat].commit(&gens_hat.combine(&gens_c)) {
394 Ok(())
395 } else {
396 Err(NovaError::InvalidIPA)
397 }
398 }
399}