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 if U.b_vec.len() != W.a_vec.len() {
194 return Err(NovaError::InvalidInputLength);
195 }
196
197 // absorb the instance in the transcript
198 transcript.absorb(b"U", U);
199
200 // sample a random base for commiting to the inner product
201 let r = transcript.squeeze(b"r")?;
202 let ck_c = ck_c.scale(&r);
203
204 // a closure that executes a step of the recursive inner product argument
205 let prove_inner = |a_vec: &[G::Scalar],
206 b_vec: &[G::Scalar],
207 ck: &CommitmentKey<G>,
208 transcript: &mut G::TE|
209 -> Result<
210 (
211 CompressedCommitment<G>,
212 CompressedCommitment<G>,
213 Vec<G::Scalar>,
214 Vec<G::Scalar>,
215 CommitmentKey<G>,
216 ),
217 NovaError,
218 > {
219 let n = a_vec.len();
220 let (ck_L, ck_R) = ck.split_at(n / 2);
221
222 let c_L = inner_product(&a_vec[0..n / 2], &b_vec[n / 2..n]);
223 let c_R = inner_product(&a_vec[n / 2..n], &b_vec[0..n / 2]);
224
225 let L = CE::<G>::commit(
226 &ck_R.combine(&ck_c),
227 &a_vec[0..n / 2]
228 .iter()
229 .chain(iter::once(&c_L))
230 .copied()
231 .collect::<Vec<G::Scalar>>(),
232 )
233 .compress();
234 let R = CE::<G>::commit(
235 &ck_L.combine(&ck_c),
236 &a_vec[n / 2..n]
237 .iter()
238 .chain(iter::once(&c_R))
239 .copied()
240 .collect::<Vec<G::Scalar>>(),
241 )
242 .compress();
243
244 transcript.absorb(b"L", &L);
245 transcript.absorb(b"R", &R);
246
247 let r = transcript.squeeze(b"r")?;
248 let r_inverse = r.invert().unwrap();
249
250 // fold the left half and the right half
251 let a_vec_folded = a_vec[0..n / 2]
252 .par_iter()
253 .zip(a_vec[n / 2..n].par_iter())
254 .map(|(a_L, a_R)| *a_L * r + r_inverse * *a_R)
255 .collect::<Vec<G::Scalar>>();
256
257 let b_vec_folded = b_vec[0..n / 2]
258 .par_iter()
259 .zip(b_vec[n / 2..n].par_iter())
260 .map(|(b_L, b_R)| *b_L * r_inverse + r * *b_R)
261 .collect::<Vec<G::Scalar>>();
262
263 let ck_folded = ck.fold(&r_inverse, &r);
264
265 Ok((L, R, a_vec_folded, b_vec_folded, ck_folded))
266 };
267
268 // two vectors to hold the logarithmic number of group elements
269 let mut L_vec: Vec<CompressedCommitment<G>> = Vec::new();
270 let mut R_vec: Vec<CompressedCommitment<G>> = Vec::new();
271
272 // we create mutable copies of vectors and generators
273 let mut a_vec = W.a_vec.to_vec();
274 let mut b_vec = U.b_vec.to_vec();
275 let mut ck = ck.clone();
276 for _i in 0..(U.b_vec.len() as f64).log2() as usize {
277 let (L, R, a_vec_folded, b_vec_folded, ck_folded) =
278 prove_inner(&a_vec, &b_vec, &ck, transcript)?;
279 L_vec.push(L);
280 R_vec.push(R);
281
282 a_vec = a_vec_folded;
283 b_vec = b_vec_folded;
284 ck = ck_folded;
285 }
286
287 Ok(InnerProductArgument {
288 L_vec,
289 R_vec,
290 a_hat: a_vec[0],
291 _p: Default::default(),
292 })
293 }
294
295 fn verify(
296 &self,
297 ck: &CommitmentKey<G>,
298 ck_c: &CommitmentKey<G>,
299 n: usize,
300 U: &InnerProductInstance<G>,
301 transcript: &mut G::TE,
302 ) -> Result<(), NovaError> {
303 transcript.dom_sep(Self::protocol_name());
304 if U.b_vec.len() != n
305 || n != (1 << self.L_vec.len())
306 || self.L_vec.len() != self.R_vec.len()
307 || self.L_vec.len() >= 32
308 {
309 return Err(NovaError::InvalidInputLength);
310 }
311
312 // absorb the instance in the transcript
313 transcript.absorb(b"U", U);
314
315 // sample a random base for commiting to the inner product
316 let r = transcript.squeeze(b"r")?;
317 let ck_c = ck_c.scale(&r);
318
319 let P = U.comm_a_vec + CE::<G>::commit(&ck_c, &[U.c]);
320
321 let batch_invert = |v: &[G::Scalar]| -> Result<Vec<G::Scalar>, NovaError> {
322 let mut products = vec![G::Scalar::zero(); v.len()];
323 let mut acc = G::Scalar::one();
324
325 for i in 0..v.len() {
326 products[i] = acc;
327 acc *= v[i];
328 }
329
330 // we can compute an inversion only if acc is non-zero
331 if acc == G::Scalar::zero() {
332 return Err(NovaError::InvalidInputLength);
333 }
334
335 // compute the inverse once for all entries
336 acc = acc.invert().unwrap();
337
338 let mut inv = vec![G::Scalar::zero(); v.len()];
339 for i in 0..v.len() {
340 let tmp = acc * v[v.len() - 1 - i];
341 inv[v.len() - 1 - i] = products[v.len() - 1 - i] * acc;
342 acc = tmp;
343 }
344
345 Ok(inv)
346 };
347
348 // compute a vector of public coins using self.L_vec and self.R_vec
349 let r = (0..self.L_vec.len())
350 .map(|i| {
351 transcript.absorb(b"L", &self.L_vec[i]);
352 transcript.absorb(b"R", &self.R_vec[i]);
353 transcript.squeeze(b"r")
354 })
355 .collect::<Result<Vec<G::Scalar>, NovaError>>()?;
356
357 // precompute scalars necessary for verification
358 let r_square: Vec<G::Scalar> = (0..self.L_vec.len())
359 .into_par_iter()
360 .map(|i| r[i] * r[i])
361 .collect();
362 let r_inverse = batch_invert(&r)?;
363 let r_inverse_square: Vec<G::Scalar> = (0..self.L_vec.len())
364 .into_par_iter()
365 .map(|i| r_inverse[i] * r_inverse[i])
366 .collect();
367
368 // compute the vector with the tensor structure
369 let s = {
370 let mut s = vec![G::Scalar::zero(); n];
371 s[0] = {
372 let mut v = G::Scalar::one();
373 for r_inverse_i in &r_inverse {
374 v *= r_inverse_i;
375 }
376 v
377 };
378 for i in 1..n {
379 let pos_in_r = (31 - (i as u32).leading_zeros()) as usize;
380 s[i] = s[i - (1 << pos_in_r)] * r_square[(self.L_vec.len() - 1) - pos_in_r];
381 }
382 s
383 };
384
385 let ck_hat = {
386 let c = CE::<G>::commit(ck, &s).compress();
387 CommitmentKey::<G>::reinterpret_commitments_as_ck(&[c])?
388 };
389
390 let b_hat = inner_product(&U.b_vec, &s);
391
392 let P_hat = {
393 let ck_folded = {
394 let ck_L = CommitmentKey::<G>::reinterpret_commitments_as_ck(&self.L_vec)?;
395 let ck_R = CommitmentKey::<G>::reinterpret_commitments_as_ck(&self.R_vec)?;
396 let ck_P = CommitmentKey::<G>::reinterpret_commitments_as_ck(&[P.compress()])?;
397 ck_L.combine(&ck_R).combine(&ck_P)
398 };
399
400 CE::<G>::commit(
401 &ck_folded,
402 &r_square
403 .iter()
404 .chain(r_inverse_square.iter())
405 .chain(iter::once(&G::Scalar::one()))
406 .copied()
407 .collect::<Vec<G::Scalar>>(),
408 )
409 };
410
411 if P_hat == CE::<G>::commit(&ck_hat.combine(&ck_c), &[self.a_hat, self.a_hat * b_hat]) {
412 Ok(())
413 } else {
414 Err(NovaError::InvalidIPA)
415 }
416 }
417}