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