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