nova_snark/provider/
ipa_pc.rs

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

nova_snark/provider/
ipa_pc.rs
