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},
  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, EE>
 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    _ek: &EE::ProverKey,
 70    _S: &R1CSShape<G>,
 71    _decomm: &Self::Decommitment,
 72    _comm: &Self::Commitment,
 73    _r: &(&[G::Scalar], &[G::Scalar]),
 74    _transcript: &mut G::TE,
 75  ) -> Result<Self::EvaluationArgument, NovaError> {
 76    Ok(TrivialEvaluationArgument {
 77      _p: Default::default(),
 78    })
 79  }
 80
 81  /// verifies an evaluation of R1CS matrices viewed as polynomials
 82  fn verify(
 83    _vk: &EE::VerifierKey,
 84    comm: &Self::Commitment,
 85    r: &(&[G::Scalar], &[G::Scalar]),
 86    _arg: &Self::EvaluationArgument,
 87    _transcript: &mut G::TE,
 88  ) -> Result<(G::Scalar, G::Scalar, G::Scalar), NovaError> {
 89    let (r_x, r_y) = r;
 90    let evals = SparsePolynomial::<G>::multi_evaluate(&[&comm.S.A, &comm.S.B, &comm.S.C], r_x, r_y);
 91    Ok((evals[0], evals[1], evals[2]))
 92  }
 93}
 94
 95mod product;
 96mod sparse;
 97
 98use sparse::{SparseEvaluationArgument, SparsePolynomial, SparsePolynomialCommitment};
 99
100/// A non-trivial implementation of `CompCommitmentEngineTrait` using Spartan's SPARK compiler
101pub struct SparkEngine<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> {
102  _p: PhantomData<G>,
103  _p2: PhantomData<EE>,
104}
105
106/// An implementation of Spark decommitment
107#[derive(Clone, Serialize, Deserialize)]
108#[serde(bound = "")]
109pub struct SparkDecommitment<G: Group> {
110  A: SparsePolynomial<G>,
111  B: SparsePolynomial<G>,
112  C: SparsePolynomial<G>,
113}
114
115impl<G: Group> SparkDecommitment<G> {
116  fn new(S: &R1CSShape<G>) -> Self {
117    let ell = (S.num_cons.log_2(), S.num_vars.log_2() + 1);
118    let A = SparsePolynomial::new(ell, &S.A);
119    let B = SparsePolynomial::new(ell, &S.B);
120    let C = SparsePolynomial::new(ell, &S.C);
121
122    Self { A, B, C }
123  }
124
125  fn commit(&self, ck: &CommitmentKey<G>) -> SparkCommitment<G> {
126    let comm_A = self.A.commit(ck);
127    let comm_B = self.B.commit(ck);
128    let comm_C = self.C.commit(ck);
129
130    SparkCommitment {
131      comm_A,
132      comm_B,
133      comm_C,
134    }
135  }
136}
137
138/// An implementation of Spark commitment
139#[derive(Clone, Serialize, Deserialize)]
140#[serde(bound = "")]
141pub struct SparkCommitment<G: Group> {
142  comm_A: SparsePolynomialCommitment<G>,
143  comm_B: SparsePolynomialCommitment<G>,
144  comm_C: SparsePolynomialCommitment<G>,
145}
146
147impl<G: Group> TranscriptReprTrait<G> for SparkCommitment<G> {
148  fn to_transcript_bytes(&self) -> Vec<u8> {
149    let mut bytes = self.comm_A.to_transcript_bytes();
150    bytes.extend(self.comm_B.to_transcript_bytes());
151    bytes.extend(self.comm_C.to_transcript_bytes());
152    bytes
153  }
154}
155
156/// Provides an implementation of a trivial evaluation argument
157#[derive(Clone, Serialize, Deserialize)]
158#[serde(bound = "")]
159pub struct SparkEvaluationArgument<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> {
160  arg_A: SparseEvaluationArgument<G, EE>,
161  arg_B: SparseEvaluationArgument<G, EE>,
162  arg_C: SparseEvaluationArgument<G, EE>,
163}
164
165impl<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> CompCommitmentEngineTrait<G, EE>
166  for SparkEngine<G, EE>
167{
168  type Decommitment = SparkDecommitment<G>;
169  type Commitment = SparkCommitment<G>;
170  type EvaluationArgument = SparkEvaluationArgument<G, EE>;
171
172  /// commits to R1CS matrices
173  fn commit(
174    ck: &CommitmentKey<G>,
175    S: &R1CSShape<G>,
176  ) -> Result<(Self::Commitment, Self::Decommitment), NovaError> {
177    let sparse = SparkDecommitment::new(S);
178    let comm = sparse.commit(ck);
179    Ok((comm, sparse))
180  }
181
182  /// proves an evaluation of R1CS matrices viewed as polynomials
183  fn prove(
184    ck: &CommitmentKey<G>,
185    pk_ee: &EE::ProverKey,
186    S: &R1CSShape<G>,
187    decomm: &Self::Decommitment,
188    comm: &Self::Commitment,
189    r: &(&[G::Scalar], &[G::Scalar]),
190    transcript: &mut G::TE,
191  ) -> Result<Self::EvaluationArgument, NovaError> {
192    let arg_A =
193      SparseEvaluationArgument::prove(ck, pk_ee, &decomm.A, &S.A, &comm.comm_A, r, transcript)?;
194    let arg_B =
195      SparseEvaluationArgument::prove(ck, pk_ee, &decomm.B, &S.B, &comm.comm_B, r, transcript)?;
196    let arg_C =
197      SparseEvaluationArgument::prove(ck, pk_ee, &decomm.C, &S.C, &comm.comm_C, r, transcript)?;
198
199    Ok(SparkEvaluationArgument {
200      arg_A,
201      arg_B,
202      arg_C,
203    })
204  }
205
206  /// verifies an evaluation of R1CS matrices viewed as polynomials
207  fn verify(
208    vk_ee: &EE::VerifierKey,
209    comm: &Self::Commitment,
210    r: &(&[G::Scalar], &[G::Scalar]),
211    arg: &Self::EvaluationArgument,
212    transcript: &mut G::TE,
213  ) -> Result<(G::Scalar, G::Scalar, G::Scalar), NovaError> {
214    let eval_A = arg.arg_A.verify(vk_ee, &comm.comm_A, r, transcript)?;
215    let eval_B = arg.arg_B.verify(vk_ee, &comm.comm_B, r, transcript)?;
216    let eval_C = arg.arg_C.verify(vk_ee, &comm.comm_C, r, transcript)?;
217
218    Ok((eval_A, eval_B, eval_C))
219  }
220}