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, CommitmentKeyTrait, CommitmentTrait},
9 evaluation::EvaluationEngineTrait,
10 AppendToTranscriptTrait, ChallengeTrait, Group, TranscriptEngineTrait,
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: CommitmentKey::<G>::new(b"ipa", 1),
63 };
64
65 let vk = VerifierKey {
66 ck_v: ck.clone(),
67 ck_s: CommitmentKey::<G>::new(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
142struct InnerProductWitness<G: Group> {
143 a_vec: Vec<G::Scalar>,
144}
145
146impl<G: Group> InnerProductWitness<G> {
147 fn new(a_vec: &[G::Scalar]) -> Self {
148 InnerProductWitness {
149 a_vec: a_vec.to_vec(),
150 }
151 }
152}
153
154/// An inner product argument
155#[derive(Clone, Debug, Serialize, Deserialize)]
156#[serde(bound = "")]
157struct InnerProductArgument<G: Group> {
158 L_vec: Vec<CompressedCommitment<G>>,
159 R_vec: Vec<CompressedCommitment<G>>,
160 a_hat: G::Scalar,
161 _p: PhantomData<G>,
162}
163
164impl<G> InnerProductArgument<G>
165where
166 G: Group,
167 CommitmentKey<G>: CommitmentKeyExtTrait<G, CE = G::CE>,
168{
169 fn protocol_name() -> &'static [u8] {
170 b"inner product argument"
171 }
172
173 fn prove(
174 ck: &CommitmentKey<G>,
175 ck_c: &CommitmentKey<G>,
176 U: &InnerProductInstance<G>,
177 W: &InnerProductWitness<G>,
178 transcript: &mut G::TE,
179 ) -> Result<Self, NovaError> {
180 transcript.absorb_bytes(b"protocol-name", Self::protocol_name());
181
182 if U.b_vec.len() != W.a_vec.len() {
183 return Err(NovaError::InvalidInputLength);
184 }
185
186 U.comm_a_vec.append_to_transcript(b"comm_a_vec", transcript);
187 <G::Scalar as AppendToTranscriptTrait<G>>::append_to_transcript(&U.c, b"c", transcript);
188
189 // sample a random base for commiting to the inner product
190 let r = G::Scalar::challenge(b"r", transcript)?;
191 let ck_c = ck_c.scale(&r);
192
193 // a closure that executes a step of the recursive inner product argument
194 let prove_inner = |a_vec: &[G::Scalar],
195 b_vec: &[G::Scalar],
196 ck: &CommitmentKey<G>,
197 transcript: &mut G::TE|
198 -> Result<
199 (
200 CompressedCommitment<G>,
201 CompressedCommitment<G>,
202 Vec<G::Scalar>,
203 Vec<G::Scalar>,
204 CommitmentKey<G>,
205 ),
206 NovaError,
207 > {
208 let n = a_vec.len();
209 let (ck_L, ck_R) = ck.split_at(n / 2);
210
211 let c_L = inner_product(&a_vec[0..n / 2], &b_vec[n / 2..n]);
212 let c_R = inner_product(&a_vec[n / 2..n], &b_vec[0..n / 2]);
213
214 let L = CE::<G>::commit(
215 &ck_R.combine(&ck_c),
216 &a_vec[0..n / 2]
217 .iter()
218 .chain(iter::once(&c_L))
219 .copied()
220 .collect::<Vec<G::Scalar>>(),
221 )
222 .compress();
223 let R = CE::<G>::commit(
224 &ck_L.combine(&ck_c),
225 &a_vec[n / 2..n]
226 .iter()
227 .chain(iter::once(&c_R))
228 .copied()
229 .collect::<Vec<G::Scalar>>(),
230 )
231 .compress();
232
233 L.append_to_transcript(b"L", transcript);
234 R.append_to_transcript(b"R", transcript);
235
236 let r = G::Scalar::challenge(b"challenge_r", transcript)?;
237 let r_inverse = r.invert().unwrap();
238
239 // fold the left half and the right half
240 let a_vec_folded = a_vec[0..n / 2]
241 .par_iter()
242 .zip(a_vec[n / 2..n].par_iter())
243 .map(|(a_L, a_R)| *a_L * r + r_inverse * *a_R)
244 .collect::<Vec<G::Scalar>>();
245
246 let b_vec_folded = b_vec[0..n / 2]
247 .par_iter()
248 .zip(b_vec[n / 2..n].par_iter())
249 .map(|(b_L, b_R)| *b_L * r_inverse + r * *b_R)
250 .collect::<Vec<G::Scalar>>();
251
252 let ck_folded = ck.fold(&r_inverse, &r);
253
254 Ok((L, R, a_vec_folded, b_vec_folded, ck_folded))
255 };
256
257 // two vectors to hold the logarithmic number of group elements
258 let mut L_vec: Vec<CompressedCommitment<G>> = Vec::new();
259 let mut R_vec: Vec<CompressedCommitment<G>> = Vec::new();
260
261 // we create mutable copies of vectors and generators
262 let mut a_vec = W.a_vec.to_vec();
263 let mut b_vec = U.b_vec.to_vec();
264 let mut ck = ck.clone();
265 for _i in 0..(U.b_vec.len() as f64).log2() as usize {
266 let (L, R, a_vec_folded, b_vec_folded, ck_folded) =
267 prove_inner(&a_vec, &b_vec, &ck, transcript)?;
268 L_vec.push(L);
269 R_vec.push(R);
270
271 a_vec = a_vec_folded;
272 b_vec = b_vec_folded;
273 ck = ck_folded;
274 }
275
276 Ok(InnerProductArgument {
277 L_vec,
278 R_vec,
279 a_hat: a_vec[0],
280 _p: Default::default(),
281 })
282 }
283
284 fn verify(
285 &self,
286 ck: &CommitmentKey<G>,
287 ck_c: &CommitmentKey<G>,
288 n: usize,
289 U: &InnerProductInstance<G>,
290 transcript: &mut G::TE,
291 ) -> Result<(), NovaError> {
292 transcript.absorb_bytes(b"protocol-name", Self::protocol_name());
293 if U.b_vec.len() != n
294 || n != (1 << self.L_vec.len())
295 || self.L_vec.len() != self.R_vec.len()
296 || self.L_vec.len() >= 32
297 {
298 return Err(NovaError::InvalidInputLength);
299 }
300
301 U.comm_a_vec.append_to_transcript(b"comm_a_vec", transcript);
302 <G::Scalar as AppendToTranscriptTrait<G>>::append_to_transcript(&U.c, b"c", transcript);
303
304 // sample a random base for commiting to the inner product
305 let r = G::Scalar::challenge(b"r", transcript)?;
306 let ck_c = ck_c.scale(&r);
307
308 let P = U.comm_a_vec + CE::<G>::commit(&ck_c, &[U.c]);
309
310 let batch_invert = |v: &[G::Scalar]| -> Result<Vec<G::Scalar>, NovaError> {
311 let mut products = vec![G::Scalar::zero(); v.len()];
312 let mut acc = G::Scalar::one();
313
314 for i in 0..v.len() {
315 products[i] = acc;
316 acc *= v[i];
317 }
318
319 // we can compute an inversion only if acc is non-zero
320 if acc == G::Scalar::zero() {
321 return Err(NovaError::InvalidInputLength);
322 }
323
324 // compute the inverse once for all entries
325 acc = acc.invert().unwrap();
326
327 let mut inv = vec![G::Scalar::zero(); v.len()];
328 for i in 0..v.len() {
329 let tmp = acc * v[v.len() - 1 - i];
330 inv[v.len() - 1 - i] = products[v.len() - 1 - i] * acc;
331 acc = tmp;
332 }
333
334 Ok(inv)
335 };
336
337 // compute a vector of public coins using self.L_vec and self.R_vec
338 let r = (0..self.L_vec.len())
339 .map(|i| {
340 self.L_vec[i].append_to_transcript(b"L", transcript);
341 self.R_vec[i].append_to_transcript(b"R", transcript);
342 G::Scalar::challenge(b"challenge_r", transcript)
343 })
344 .collect::<Result<Vec<G::Scalar>, NovaError>>()?;
345
346 // precompute scalars necessary for verification
347 let r_square: Vec<G::Scalar> = (0..self.L_vec.len())
348 .into_par_iter()
349 .map(|i| r[i] * r[i])
350 .collect();
351 let r_inverse = batch_invert(&r)?;
352 let r_inverse_square: Vec<G::Scalar> = (0..self.L_vec.len())
353 .into_par_iter()
354 .map(|i| r_inverse[i] * r_inverse[i])
355 .collect();
356
357 // compute the vector with the tensor structure
358 let s = {
359 let mut s = vec![G::Scalar::zero(); n];
360 s[0] = {
361 let mut v = G::Scalar::one();
362 for r_inverse_i in &r_inverse {
363 v *= r_inverse_i;
364 }
365 v
366 };
367 for i in 1..n {
368 let pos_in_r = (31 - (i as u32).leading_zeros()) as usize;
369 s[i] = s[i - (1 << pos_in_r)] * r_square[(self.L_vec.len() - 1) - pos_in_r];
370 }
371 s
372 };
373
374 let ck_hat = {
375 let c = CE::<G>::commit(ck, &s).compress();
376 CommitmentKey::<G>::reinterpret_commitments_as_ck(&[c])?
377 };
378
379 let b_hat = inner_product(&U.b_vec, &s);
380
381 let P_hat = {
382 let ck_folded = {
383 let ck_L = CommitmentKey::<G>::reinterpret_commitments_as_ck(&self.L_vec)?;
384 let ck_R = CommitmentKey::<G>::reinterpret_commitments_as_ck(&self.R_vec)?;
385 let ck_P = CommitmentKey::<G>::reinterpret_commitments_as_ck(&[P.compress()])?;
386 ck_L.combine(&ck_R).combine(&ck_P)
387 };
388
389 CE::<G>::commit(
390 &ck_folded,
391 &r_square
392 .iter()
393 .chain(r_inverse_square.iter())
394 .chain(iter::once(&G::Scalar::one()))
395 .copied()
396 .collect::<Vec<G::Scalar>>(),
397 )
398 };
399
400 if P_hat == CE::<G>::commit(&ck_hat.combine(&ck_c), &[self.a_hat, self.a_hat * b_hat]) {
401 Ok(())
402 } else {
403 Err(NovaError::InvalidIPA)
404 }
405 }
406}