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