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