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