Nova/src/provider/ipa_pc.rs
src/provider/ipa_pc.rsRaw
1//! This module implements `EvaluationEngine` using an IPA-based polynomial commitment scheme
2#![allow(clippy::too_many_arguments)]
3use crate::{
4 errors::NovaError,
5 provider::pedersen::CommitmentGensExtTrait,
6 spartan::polynomial::EqPolynomial,
7 traits::{
8 commitment::{CommitmentEngineTrait, CommitmentGensTrait, CommitmentTrait},
9 evaluation::EvaluationEngineTrait,
10 AppendToTranscriptTrait, ChallengeTrait, Group,
11 },
12 Commitment, CommitmentGens, CompressedCommitment, CE,
13};
14use core::{cmp::max, iter};
15use ff::Field;
16use merlin::Transcript;
17use rayon::prelude::*;
18use serde::{Deserialize, Serialize};
19use std::marker::PhantomData;
20
21/// Provides an implementation of generators for proving evaluations
22#[derive(Clone, Debug, Serialize, Deserialize)]
23#[serde(bound = "")]
24pub struct EvaluationGens<G: Group> {
25 gens_v: CommitmentGens<G>,
26 gens_s: CommitmentGens<G>,
27}
28
29/// Provides an implementation of a polynomial evaluation argument
30#[derive(Clone, Debug, Serialize, Deserialize)]
31#[serde(bound = "")]
32pub struct EvaluationArgument<G: Group> {
33 nifs: Vec<NIFSForInnerProduct<G>>,
34 ipa: InnerProductArgument<G>,
35}
36
37/// Provides an implementation of a polynomial evaluation engine using IPA
38#[derive(Clone, Debug, Serialize, Deserialize)]
39pub struct EvaluationEngine<G: Group> {
40 _p: PhantomData<G>,
41}
42
43impl<G> EvaluationEngineTrait<G> for EvaluationEngine<G>
44where
45 G: Group,
46 CommitmentGens<G>: CommitmentGensExtTrait<G, CE = G::CE>,
47{
48 type CE = G::CE;
49 type EvaluationGens = EvaluationGens<G>;
50 type EvaluationArgument = EvaluationArgument<G>;
51
52 fn setup(gens: &<Self::CE as CommitmentEngineTrait<G>>::CommitmentGens) -> Self::EvaluationGens {
53 EvaluationGens {
54 gens_v: gens.clone(),
55 gens_s: CommitmentGens::<G>::new(b"ipa", 1),
56 }
57 }
58
59 fn prove_batch(
60 gens: &Self::EvaluationGens,
61 transcript: &mut Transcript,
62 comms: &[Commitment<G>],
63 polys: &[Vec<G::Scalar>],
64 points: &[Vec<G::Scalar>],
65 evals: &[G::Scalar],
66 ) -> Result<Self::EvaluationArgument, NovaError> {
67 // sanity checks (these should never fail)
68 assert!(polys.len() >= 2);
69 assert_eq!(comms.len(), polys.len());
70 assert_eq!(comms.len(), points.len());
71 assert_eq!(comms.len(), evals.len());
72
73 let mut r_U = InnerProductInstance::new(
74 &comms[0],
75 &EqPolynomial::new(points[0].clone()).evals(),
76 &evals[0],
77 );
78 let mut r_W = InnerProductWitness::new(&polys[0]);
79 let mut nifs = Vec::new();
80
81 for i in 1..polys.len() {
82 let (n, u, w) = NIFSForInnerProduct::prove(
83 &r_U,
84 &r_W,
85 &InnerProductInstance::new(
86 &comms[i],
87 &EqPolynomial::new(points[i].clone()).evals(),
88 &evals[i],
89 ),
90 &InnerProductWitness::new(&polys[i]),
91 transcript,
92 );
93 nifs.push(n);
94 r_U = u;
95 r_W = w;
96 }
97
98 let ipa = InnerProductArgument::prove(&gens.gens_v, &gens.gens_s, &r_U, &r_W, transcript)?;
99
100 Ok(EvaluationArgument { nifs, ipa })
101 }
102
103 /// A method to verify purported evaluations of a batch of polynomials
104 fn verify_batch(
105 gens: &Self::EvaluationGens,
106 transcript: &mut Transcript,
107 comms: &[Commitment<G>],
108 points: &[Vec<G::Scalar>],
109 evals: &[G::Scalar],
110 arg: &Self::EvaluationArgument,
111 ) -> Result<(), NovaError> {
112 // sanity checks (these should never fail)
113 assert!(comms.len() >= 2);
114 assert_eq!(comms.len(), points.len());
115 assert_eq!(comms.len(), evals.len());
116
117 let mut r_U = InnerProductInstance::new(
118 &comms[0],
119 &EqPolynomial::new(points[0].clone()).evals(),
120 &evals[0],
121 );
122 let mut num_vars = points[0].len();
123 for i in 1..comms.len() {
124 let u = arg.nifs[i - 1].verify(
125 &r_U,
126 &InnerProductInstance::new(
127 &comms[i],
128 &EqPolynomial::new(points[i].clone()).evals(),
129 &evals[i],
130 ),
131 transcript,
132 );
133 r_U = u;
134 num_vars = max(num_vars, points[i].len());
135 }
136
137 arg.ipa.verify(
138 &gens.gens_v,
139 &gens.gens_s,
140 (2_usize).pow(num_vars as u32),
141 &r_U,
142 transcript,
143 )?;
144
145 Ok(())
146 }
147}
148
149fn inner_product<T>(a: &[T], b: &[T]) -> T
150where
151 T: Field + Send + Sync,
152{
153 assert_eq!(a.len(), b.len());
154 (0..a.len())
155 .into_par_iter()
156 .map(|i| a[i] * b[i])
157 .reduce(T::zero, |x, y| x + y)
158}
159
160/// An inner product instance consists of a commitment to a vector `a` and another vector `b`
161/// and the claim that c = <a, b>.
162pub struct InnerProductInstance<G: Group> {
163 comm_a_vec: Commitment<G>,
164 b_vec: Vec<G::Scalar>,
165 c: G::Scalar,
166}
167
168impl<G: Group> InnerProductInstance<G> {
169 fn new(comm_a_vec: &Commitment<G>, b_vec: &[G::Scalar], c: &G::Scalar) -> Self {
170 InnerProductInstance {
171 comm_a_vec: *comm_a_vec,
172 b_vec: b_vec.to_vec(),
173 c: *c,
174 }
175 }
176
177 fn pad(&self, n: usize) -> InnerProductInstance<G> {
178 let mut b_vec = self.b_vec.clone();
179 b_vec.resize(n, G::Scalar::zero());
180 InnerProductInstance {
181 comm_a_vec: self.comm_a_vec,
182 b_vec,
183 c: self.c,
184 }
185 }
186}
187
188struct InnerProductWitness<G: Group> {
189 a_vec: Vec<G::Scalar>,
190}
191
192impl<G: Group> InnerProductWitness<G> {
193 fn new(a_vec: &[G::Scalar]) -> Self {
194 InnerProductWitness {
195 a_vec: a_vec.to_vec(),
196 }
197 }
198
199 fn pad(&self, n: usize) -> InnerProductWitness<G> {
200 let mut a_vec = self.a_vec.clone();
201 a_vec.resize(n, G::Scalar::zero());
202 InnerProductWitness { a_vec }
203 }
204}
205
206/// A non-interactive folding scheme (NIFS) for inner product relations
207#[derive(Clone, Debug, Serialize, Deserialize)]
208pub struct NIFSForInnerProduct<G: Group> {
209 cross_term: G::Scalar,
210}
211
212impl<G: Group> NIFSForInnerProduct<G> {
213 fn protocol_name() -> &'static [u8] {
214 b"NIFSForInnerProduct"
215 }
216
217 fn prove(
218 U1: &InnerProductInstance<G>,
219 W1: &InnerProductWitness<G>,
220 U2: &InnerProductInstance<G>,
221 W2: &InnerProductWitness<G>,
222 transcript: &mut Transcript,
223 ) -> (Self, InnerProductInstance<G>, InnerProductWitness<G>) {
224 transcript.append_message(b"protocol-name", Self::protocol_name());
225
226 // pad the instances and witness so they are of the same length
227 let U1 = U1.pad(max(U1.b_vec.len(), U2.b_vec.len()));
228 let U2 = U2.pad(max(U1.b_vec.len(), U2.b_vec.len()));
229 let W1 = W1.pad(max(U1.b_vec.len(), U2.b_vec.len()));
230 let W2 = W2.pad(max(U1.b_vec.len(), U2.b_vec.len()));
231
232 // add the two commitments and two public vectors to the transcript
233 U1.comm_a_vec
234 .append_to_transcript(b"U1_comm_a_vec", transcript);
235 U1.b_vec.append_to_transcript(b"U1_b_vec", transcript);
236 U2.comm_a_vec
237 .append_to_transcript(b"U2_comm_a_vec", transcript);
238 U2.b_vec.append_to_transcript(b"U2_b_vec", transcript);
239
240 // compute the cross-term
241 let cross_term = inner_product(&W1.a_vec, &U2.b_vec) + inner_product(&W2.a_vec, &U1.b_vec);
242
243 // add the cross-term to the transcript
244 cross_term.append_to_transcript(b"cross_term", transcript);
245
246 // obtain a random challenge
247 let r = G::Scalar::challenge(b"r", transcript);
248
249 // fold the vectors and their inner product
250 let a_vec = W1
251 .a_vec
252 .par_iter()
253 .zip(W2.a_vec.par_iter())
254 .map(|(x1, x2)| *x1 + r * x2)
255 .collect::<Vec<G::Scalar>>();
256 let b_vec = U1
257 .b_vec
258 .par_iter()
259 .zip(U2.b_vec.par_iter())
260 .map(|(a1, a2)| *a1 + r * a2)
261 .collect::<Vec<G::Scalar>>();
262
263 let c = U1.c + r * r * U2.c + r * cross_term;
264 let comm_a_vec = U1.comm_a_vec + U2.comm_a_vec * r;
265
266 let W = InnerProductWitness { a_vec };
267 let U = InnerProductInstance {
268 comm_a_vec,
269 b_vec,
270 c,
271 };
272
273 (NIFSForInnerProduct { cross_term }, U, W)
274 }
275
276 fn verify(
277 &self,
278 U1: &InnerProductInstance<G>,
279 U2: &InnerProductInstance<G>,
280 transcript: &mut Transcript,
281 ) -> InnerProductInstance<G> {
282 transcript.append_message(b"protocol-name", Self::protocol_name());
283
284 // pad the instances so they are of the same length
285 let U1 = U1.pad(max(U1.b_vec.len(), U2.b_vec.len()));
286 let U2 = U2.pad(max(U1.b_vec.len(), U2.b_vec.len()));
287
288 // add the two commitments and two public vectors to the transcript
289 U1.comm_a_vec
290 .append_to_transcript(b"U1_comm_a_vec", transcript);
291 U1.b_vec.append_to_transcript(b"U1_b_vec", transcript);
292 U2.comm_a_vec
293 .append_to_transcript(b"U2_comm_a_vec", transcript);
294 U2.b_vec.append_to_transcript(b"U2_b_vec", transcript);
295
296 // add the cross-term to the transcript
297 self
298 .cross_term
299 .append_to_transcript(b"cross_term", transcript);
300
301 // obtain a random challenge
302 let r = G::Scalar::challenge(b"r", transcript);
303
304 // fold the vectors and their inner product
305 let b_vec = U1
306 .b_vec
307 .par_iter()
308 .zip(U2.b_vec.par_iter())
309 .map(|(a1, a2)| *a1 + r * a2)
310 .collect::<Vec<G::Scalar>>();
311 let c = U1.c + r * r * U2.c + r * self.cross_term;
312 let comm_a_vec = U1.comm_a_vec + U2.comm_a_vec * r;
313
314 InnerProductInstance {
315 comm_a_vec,
316 b_vec,
317 c,
318 }
319 }
320}
321
322/// An inner product argument
323#[derive(Clone, Debug, Serialize, Deserialize)]
324#[serde(bound = "")]
325struct InnerProductArgument<G: Group> {
326 L_vec: Vec<CompressedCommitment<G>>,
327 R_vec: Vec<CompressedCommitment<G>>,
328 a_hat: G::Scalar,
329 _p: PhantomData<G>,
330}
331
332impl<G> InnerProductArgument<G>
333where
334 G: Group,
335 CommitmentGens<G>: CommitmentGensExtTrait<G, CE = G::CE>,
336{
337 fn protocol_name() -> &'static [u8] {
338 b"inner product argument"
339 }
340
341 fn prove(
342 gens: &CommitmentGens<G>,
343 gens_c: &CommitmentGens<G>,
344 U: &InnerProductInstance<G>,
345 W: &InnerProductWitness<G>,
346 transcript: &mut Transcript,
347 ) -> Result<Self, NovaError> {
348 transcript.append_message(b"protocol-name", Self::protocol_name());
349
350 if U.b_vec.len() != W.a_vec.len() {
351 return Err(NovaError::InvalidInputLength);
352 }
353
354 U.comm_a_vec.append_to_transcript(b"comm_a_vec", transcript);
355 U.b_vec.append_to_transcript(b"b_vec", transcript);
356 U.c.append_to_transcript(b"c", transcript);
357
358 // sample a random base for commiting to the inner product
359 let r = G::Scalar::challenge(b"r", transcript);
360 let gens_c = gens_c.scale(&r);
361
362 // a closure that executes a step of the recursive inner product argument
363 let prove_inner = |a_vec: &[G::Scalar],
364 b_vec: &[G::Scalar],
365 gens: &CommitmentGens<G>,
366 transcript: &mut Transcript|
367 -> Result<
368 (
369 CompressedCommitment<G>,
370 CompressedCommitment<G>,
371 Vec<G::Scalar>,
372 Vec<G::Scalar>,
373 CommitmentGens<G>,
374 ),
375 NovaError,
376 > {
377 let n = a_vec.len();
378 let (gens_L, gens_R) = gens.split_at(n / 2);
379
380 let c_L = inner_product(&a_vec[0..n / 2], &b_vec[n / 2..n]);
381 let c_R = inner_product(&a_vec[n / 2..n], &b_vec[0..n / 2]);
382
383 let L = CE::<G>::commit(
384 &gens_R.combine(&gens_c),
385 &a_vec[0..n / 2]
386 .iter()
387 .chain(iter::once(&c_L))
388 .copied()
389 .collect::<Vec<G::Scalar>>(),
390 )
391 .compress();
392 let R = CE::<G>::commit(
393 &gens_L.combine(&gens_c),
394 &a_vec[n / 2..n]
395 .iter()
396 .chain(iter::once(&c_R))
397 .copied()
398 .collect::<Vec<G::Scalar>>(),
399 )
400 .compress();
401
402 L.append_to_transcript(b"L", transcript);
403 R.append_to_transcript(b"R", transcript);
404
405 let r = G::Scalar::challenge(b"challenge_r", transcript);
406 let r_inverse = r.invert().unwrap();
407
408 // fold the left half and the right half
409 let a_vec_folded = a_vec[0..n / 2]
410 .par_iter()
411 .zip(a_vec[n / 2..n].par_iter())
412 .map(|(a_L, a_R)| *a_L * r + r_inverse * *a_R)
413 .collect::<Vec<G::Scalar>>();
414
415 let b_vec_folded = b_vec[0..n / 2]
416 .par_iter()
417 .zip(b_vec[n / 2..n].par_iter())
418 .map(|(b_L, b_R)| *b_L * r_inverse + r * *b_R)
419 .collect::<Vec<G::Scalar>>();
420
421 let gens_folded = gens.fold(&r_inverse, &r);
422
423 Ok((L, R, a_vec_folded, b_vec_folded, gens_folded))
424 };
425
426 // two vectors to hold the logarithmic number of group elements
427 let mut L_vec: Vec<CompressedCommitment<G>> = Vec::new();
428 let mut R_vec: Vec<CompressedCommitment<G>> = Vec::new();
429
430 // we create mutable copies of vectors and generators
431 let mut a_vec = W.a_vec.to_vec();
432 let mut b_vec = U.b_vec.to_vec();
433 let mut gens = gens.clone();
434 for _i in 0..(U.b_vec.len() as f64).log2() as usize {
435 let (L, R, a_vec_folded, b_vec_folded, gens_folded) =
436 prove_inner(&a_vec, &b_vec, &gens, transcript)?;
437 L_vec.push(L);
438 R_vec.push(R);
439
440 a_vec = a_vec_folded;
441 b_vec = b_vec_folded;
442 gens = gens_folded;
443 }
444
445 Ok(InnerProductArgument {
446 L_vec,
447 R_vec,
448 a_hat: a_vec[0],
449 _p: Default::default(),
450 })
451 }
452
453 fn verify(
454 &self,
455 gens: &CommitmentGens<G>,
456 gens_c: &CommitmentGens<G>,
457 n: usize,
458 U: &InnerProductInstance<G>,
459 transcript: &mut Transcript,
460 ) -> Result<(), NovaError> {
461 transcript.append_message(b"protocol-name", Self::protocol_name());
462 if U.b_vec.len() != n
463 || n != (1 << self.L_vec.len())
464 || self.L_vec.len() != self.R_vec.len()
465 || self.L_vec.len() >= 32
466 {
467 return Err(NovaError::InvalidInputLength);
468 }
469
470 U.comm_a_vec.append_to_transcript(b"comm_a_vec", transcript);
471 U.b_vec.append_to_transcript(b"b_vec", transcript);
472 U.c.append_to_transcript(b"c", transcript);
473
474 // sample a random base for commiting to the inner product
475 let r = G::Scalar::challenge(b"r", transcript);
476 let gens_c = gens_c.scale(&r);
477
478 let P = U.comm_a_vec + CE::<G>::commit(&gens_c, &[U.c]);
479
480 let batch_invert = |v: &[G::Scalar]| -> Result<Vec<G::Scalar>, NovaError> {
481 let mut products = vec![G::Scalar::zero(); v.len()];
482 let mut acc = G::Scalar::one();
483
484 for i in 0..v.len() {
485 products[i] = acc;
486 acc *= v[i];
487 }
488
489 // we can compute an inversion only if acc is non-zero
490 if acc == G::Scalar::zero() {
491 return Err(NovaError::InvalidInputLength);
492 }
493
494 // compute the inverse once for all entries
495 acc = acc.invert().unwrap();
496
497 let mut inv = vec![G::Scalar::zero(); v.len()];
498 for i in 0..v.len() {
499 let tmp = acc * v[v.len() - 1 - i];
500 inv[v.len() - 1 - i] = products[v.len() - 1 - i] * acc;
501 acc = tmp;
502 }
503
504 Ok(inv)
505 };
506
507 // compute a vector of public coins using self.L_vec and self.R_vec
508 let r = (0..self.L_vec.len())
509 .map(|i| {
510 self.L_vec[i].append_to_transcript(b"L", transcript);
511 self.R_vec[i].append_to_transcript(b"R", transcript);
512 G::Scalar::challenge(b"challenge_r", transcript)
513 })
514 .collect::<Vec<G::Scalar>>();
515
516 // precompute scalars necessary for verification
517 let r_square: Vec<G::Scalar> = (0..self.L_vec.len())
518 .into_par_iter()
519 .map(|i| r[i] * r[i])
520 .collect();
521 let r_inverse = batch_invert(&r)?;
522 let r_inverse_square: Vec<G::Scalar> = (0..self.L_vec.len())
523 .into_par_iter()
524 .map(|i| r_inverse[i] * r_inverse[i])
525 .collect();
526
527 // compute the vector with the tensor structure
528 let s = {
529 let mut s = vec![G::Scalar::zero(); n];
530 s[0] = {
531 let mut v = G::Scalar::one();
532 for r_inverse_i in &r_inverse {
533 v *= r_inverse_i;
534 }
535 v
536 };
537 for i in 1..n {
538 let pos_in_r = (31 - (i as u32).leading_zeros()) as usize;
539 s[i] = s[i - (1 << pos_in_r)] * r_square[(self.L_vec.len() - 1) - pos_in_r];
540 }
541 s
542 };
543
544 let gens_hat = {
545 let c = CE::<G>::commit(gens, &s).compress();
546 CommitmentGens::<G>::reinterpret_commitments_as_gens(&[c])?
547 };
548
549 let b_hat = inner_product(&U.b_vec, &s);
550
551 let P_hat = {
552 let gens_folded = {
553 let gens_L = CommitmentGens::<G>::reinterpret_commitments_as_gens(&self.L_vec)?;
554 let gens_R = CommitmentGens::<G>::reinterpret_commitments_as_gens(&self.R_vec)?;
555 let gens_P = CommitmentGens::<G>::reinterpret_commitments_as_gens(&[P.compress()])?;
556 gens_L.combine(&gens_R).combine(&gens_P)
557 };
558
559 CE::<G>::commit(
560 &gens_folded,
561 &r_square
562 .iter()
563 .chain(r_inverse_square.iter())
564 .chain(iter::once(&G::Scalar::one()))
565 .copied()
566 .collect::<Vec<G::Scalar>>(),
567 )
568 };
569
570 if P_hat
571 == CE::<G>::commit(
572 &gens_hat.combine(&gens_c),
573 &[self.a_hat, self.a_hat * b_hat],
574 )
575 {
576 Ok(())
577 } else {
578 Err(NovaError::InvalidIPA)
579 }
580 }
581}