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