1//! This module implements `CompCommitmentEngineTrait` using Spartan's SPARK compiler
  2//! We also provide a trivial implementation that has the verifier evaluate the sparse polynomials
  3use crate::{
  4  errors::NovaError,
  5  r1cs::R1CSShape,
  6  spartan::{math::Math, CompCommitmentEngineTrait, PolyEvalInstance, PolyEvalWitness},
  7  traits::{evaluation::EvaluationEngineTrait, Group, TranscriptReprTrait},
  8  CommitmentKey,
  9};
 10use core::marker::PhantomData;
 11use serde::{Deserialize, Serialize};
 12
 13/// A trivial implementation of `ComputationCommitmentEngineTrait`
 14pub struct TrivialCompComputationEngine<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> {
 15  _p: PhantomData<G>,
 16  _p2: PhantomData<EE>,
 17}
 18
 19/// Provides an implementation of a trivial commitment
 20#[derive(Clone, Debug, Serialize, Deserialize)]
 21#[serde(bound = "")]
 22pub struct TrivialCommitment<G: Group> {
 23  S: R1CSShape<G>,
 24}
 25
 26/// Provides an implementation of a trivial decommitment
 27#[derive(Clone, Debug, Serialize, Deserialize)]
 28#[serde(bound = "")]
 29pub struct TrivialDecommitment<G: Group> {
 30  _p: PhantomData<G>,
 31}
 32
 33/// Provides an implementation of a trivial evaluation argument
 34#[derive(Clone, Debug, Serialize, Deserialize)]
 35#[serde(bound = "")]
 36pub struct TrivialEvaluationArgument<G: Group> {
 37  _p: PhantomData<G>,
 38}
 39
 40impl<G: Group> TranscriptReprTrait<G> for TrivialCommitment<G> {
 41  fn to_transcript_bytes(&self) -> Vec<u8> {
 42    self.S.to_transcript_bytes()
 43  }
 44}
 45
 46impl<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> CompCommitmentEngineTrait<G>
 47  for TrivialCompComputationEngine<G, EE>
 48{
 49  type Decommitment = TrivialDecommitment<G>;
 50  type Commitment = TrivialCommitment<G>;
 51  type EvaluationArgument = TrivialEvaluationArgument<G>;
 52
 53  /// commits to R1CS matrices
 54  fn commit(
 55    _ck: &CommitmentKey<G>,
 56    S: &R1CSShape<G>,
 57  ) -> Result<(Self::Commitment, Self::Decommitment), NovaError> {
 58    Ok((
 59      TrivialCommitment { S: S.clone() },
 60      TrivialDecommitment {
 61        _p: Default::default(),
 62      },
 63    ))
 64  }
 65
 66  /// proves an evaluation of R1CS matrices viewed as polynomials
 67  fn prove(
 68    _ck: &CommitmentKey<G>,
 69    _S: &R1CSShape<G>,
 70    _decomm: &Self::Decommitment,
 71    _comm: &Self::Commitment,
 72    _r: &(&[G::Scalar], &[G::Scalar]),
 73    _transcript: &mut G::TE,
 74  ) -> Result<
 75    (
 76      Self::EvaluationArgument,
 77      Vec<(PolyEvalWitness<G>, PolyEvalInstance<G>)>,
 78    ),
 79    NovaError,
 80  > {
 81    Ok((
 82      TrivialEvaluationArgument {
 83        _p: Default::default(),
 84      },
 85      Vec::new(),
 86    ))
 87  }
 88
 89  /// verifies an evaluation of R1CS matrices viewed as polynomials
 90  fn verify(
 91    comm: &Self::Commitment,
 92    r: &(&[G::Scalar], &[G::Scalar]),
 93    _arg: &Self::EvaluationArgument,
 94    _transcript: &mut G::TE,
 95  ) -> Result<(G::Scalar, G::Scalar, G::Scalar, Vec<PolyEvalInstance<G>>), NovaError> {
 96    let (r_x, r_y) = r;
 97    let evals = SparsePolynomial::<G>::multi_evaluate(&[&comm.S.A, &comm.S.B, &comm.S.C], r_x, r_y);
 98    Ok((evals[0], evals[1], evals[2], Vec::new()))
 99  }
100}
101
102mod product;
103mod sparse;
104
105use sparse::{SparseEvaluationArgument, SparsePolynomial, SparsePolynomialCommitment};
106
107/// A non-trivial implementation of `CompCommitmentEngineTrait` using Spartan's SPARK compiler
108pub struct SparkEngine<G: Group> {
109  _p: PhantomData<G>,
110}
111
112/// An implementation of Spark decommitment
113#[derive(Clone, Serialize, Deserialize)]
114#[serde(bound = "")]
115pub struct SparkDecommitment<G: Group> {
116  A: SparsePolynomial<G>,
117  B: SparsePolynomial<G>,
118  C: SparsePolynomial<G>,
119}
120
121impl<G: Group> SparkDecommitment<G> {
122  fn new(S: &R1CSShape<G>) -> Self {
123    let ell = (S.num_cons.log_2(), S.num_vars.log_2() + 1);
124    let A = SparsePolynomial::new(ell, &S.A);
125    let B = SparsePolynomial::new(ell, &S.B);
126    let C = SparsePolynomial::new(ell, &S.C);
127
128    Self { A, B, C }
129  }
130
131  fn commit(&self, ck: &CommitmentKey<G>) -> SparkCommitment<G> {
132    let comm_A = self.A.commit(ck);
133    let comm_B = self.B.commit(ck);
134    let comm_C = self.C.commit(ck);
135
136    SparkCommitment {
137      comm_A,
138      comm_B,
139      comm_C,
140    }
141  }
142}
143
144/// An implementation of Spark commitment
145#[derive(Clone, Serialize, Deserialize)]
146#[serde(bound = "")]
147pub struct SparkCommitment<G: Group> {
148  comm_A: SparsePolynomialCommitment<G>,
149  comm_B: SparsePolynomialCommitment<G>,
150  comm_C: SparsePolynomialCommitment<G>,
151}
152
153impl<G: Group> TranscriptReprTrait<G> for SparkCommitment<G> {
154  fn to_transcript_bytes(&self) -> Vec<u8> {
155    let mut bytes = self.comm_A.to_transcript_bytes();
156    bytes.extend(self.comm_B.to_transcript_bytes());
157    bytes.extend(self.comm_C.to_transcript_bytes());
158    bytes
159  }
160}
161
162/// Provides an implementation of a trivial evaluation argument
163#[derive(Clone, Serialize, Deserialize)]
164#[serde(bound = "")]
165pub struct SparkEvaluationArgument<G: Group> {
166  arg_A: SparseEvaluationArgument<G>,
167  arg_B: SparseEvaluationArgument<G>,
168  arg_C: SparseEvaluationArgument<G>,
169}
170
171impl<G: Group> CompCommitmentEngineTrait<G> for SparkEngine<G> {
172  type Decommitment = SparkDecommitment<G>;
173  type Commitment = SparkCommitment<G>;
174  type EvaluationArgument = SparkEvaluationArgument<G>;
175
176  /// commits to R1CS matrices
177  fn commit(
178    ck: &CommitmentKey<G>,
179    S: &R1CSShape<G>,
180  ) -> Result<(Self::Commitment, Self::Decommitment), NovaError> {
181    let sparse = SparkDecommitment::new(S);
182    let comm = sparse.commit(ck);
183    Ok((comm, sparse))
184  }
185
186  /// proves an evaluation of R1CS matrices viewed as polynomials
187  fn prove(
188    ck: &CommitmentKey<G>,
189    S: &R1CSShape<G>,
190    decomm: &Self::Decommitment,
191    comm: &Self::Commitment,
192    r: &(&[G::Scalar], &[G::Scalar]),
193    transcript: &mut G::TE,
194  ) -> Result<
195    (
196      Self::EvaluationArgument,
197      Vec<(PolyEvalWitness<G>, PolyEvalInstance<G>)>,
198    ),
199    NovaError,
200  > {
201    let (arg_A, u_w_vec_A) =
202      SparseEvaluationArgument::prove(ck, &decomm.A, &S.A, &comm.comm_A, r, transcript)?;
203    let (arg_B, u_w_vec_B) =
204      SparseEvaluationArgument::prove(ck, &decomm.B, &S.B, &comm.comm_B, r, transcript)?;
205    let (arg_C, u_w_vec_C) =
206      SparseEvaluationArgument::prove(ck, &decomm.C, &S.C, &comm.comm_C, r, transcript)?;
207
208    let u_w_vec = {
209      let mut u_w_vec = u_w_vec_A;
210      u_w_vec.extend(u_w_vec_B);
211      u_w_vec.extend(u_w_vec_C);
212      u_w_vec
213    };
214
215    Ok((
216      SparkEvaluationArgument {
217        arg_A,
218        arg_B,
219        arg_C,
220      },
221      u_w_vec,
222    ))
223  }
224
225  /// verifies an evaluation of R1CS matrices viewed as polynomials
226  fn verify(
227    comm: &Self::Commitment,
228    r: &(&[G::Scalar], &[G::Scalar]),
229    arg: &Self::EvaluationArgument,
230    transcript: &mut G::TE,
231  ) -> Result<(G::Scalar, G::Scalar, G::Scalar, Vec<PolyEvalInstance<G>>), NovaError> {
232    let (eval_A, u_vec_A) = arg.arg_A.verify(&comm.comm_A, r, transcript)?;
233    let (eval_B, u_vec_B) = arg.arg_B.verify(&comm.comm_B, r, transcript)?;
234    let (eval_C, u_vec_C) = arg.arg_C.verify(&comm.comm_C, r, transcript)?;
235
236    let u_vec = {
237      let mut u_vec = u_vec_A;
238      u_vec.extend(u_vec_B);
239      u_vec.extend(u_vec_C);
240      u_vec
241    };
242
243    Ok((eval_A, eval_B, eval_C, u_vec))
244  }
245}