1use super::dense_mlpoly::EqPolynomial;
  2use super::errors::ProofVerifyError;
  3use super::r1csinstance::{
  4  R1CSCommitment, R1CSCommitmentGens, R1CSDecommitment, R1CSEvalProof, R1CSInstance,
  5  R1CSInstanceEvals,
  6};
  7use super::r1csproof::{R1CSGens, R1CSProof};
  8use super::scalar::Scalar;
  9use super::timer::Timer;
 10use super::transcript::{AppendToTranscript, ProofTranscript};
 11use merlin::Transcript;
 12use rand::rngs::OsRng;
 13use serde::{Deserialize, Serialize};
 14
 15pub struct SpartanGens {
 16  gens_r1cs_sat: R1CSGens,
 17  gens_r1cs_eval: R1CSCommitmentGens,
 18}
 19
 20impl SpartanGens {
 21  pub fn new(gens_r1cs_sat: R1CSGens, gens_r1cs_eval: R1CSCommitmentGens) -> SpartanGens {
 22    SpartanGens {
 23      gens_r1cs_sat,
 24      gens_r1cs_eval,
 25    }
 26  }
 27}
 28
 29#[derive(Serialize, Deserialize, Debug)]
 30pub struct SpartanProof {
 31  r1cs_sat_proof: R1CSProof,
 32  inst_evals: R1CSInstanceEvals,
 33  r1cs_eval_proof: R1CSEvalProof,
 34}
 35
 36impl SpartanProof {
 37  fn protocol_name() -> &'static [u8] {
 38    b"Spartan proof"
 39  }
 40
 41  /// A public computation to create a commitment to an R1CS instance
 42  pub fn encode(
 43    inst: &R1CSInstance,
 44    gens: &R1CSCommitmentGens,
 45  ) -> (R1CSCommitment, R1CSDecommitment) {
 46    inst.commit(gens)
 47  }
 48
 49  /// A method to produce a proof of the satisfiability of an R1CS instance
 50  pub fn prove(
 51    inst: &R1CSInstance,
 52    decomm: &R1CSDecommitment,
 53    vars: Vec<Scalar>,
 54    input: &Vec<Scalar>,
 55    gens: &SpartanGens,
 56    transcript: &mut Transcript,
 57  ) -> SpartanProof {
 58    // we create a Transcript object seeded with a random Scalar
 59    // to aid the prover produce its randomness
 60    let mut random_tape = {
 61      let mut csprng: OsRng = OsRng;
 62      let mut tape = Transcript::new(b"SpartanProof");
 63      tape.append_scalar(b"init_randomness", &Scalar::random(&mut csprng));
 64      tape
 65    };
 66
 67    transcript.append_protocol_name(SpartanProof::protocol_name());
 68    let (r1cs_sat_proof, rx, ry) = {
 69      let (proof, rx, ry) = R1CSProof::prove(
 70        inst,
 71        vars,
 72        input,
 73        &gens.gens_r1cs_sat,
 74        transcript,
 75        &mut random_tape,
 76      );
 77      let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
 78      Timer::print(&format!("len_r1cs_sat_proof {:?}", proof_encoded.len()));
 79
 80      (proof, rx, ry)
 81    };
 82
 83    // We send evaluations of A, B, C at r = (rx, ry) as claims
 84    // to enable the verifier complete the first sum-check
 85    let timer_eval = Timer::new("eval_sparse_polys");
 86    let inst_evals = {
 87      let eval_table_rx = EqPolynomial::new(rx.clone()).evals();
 88      let eval_table_ry = EqPolynomial::new(ry.clone()).evals();
 89      inst.evaluate_with_tables(&eval_table_rx, &eval_table_ry)
 90    };
 91    inst_evals.append_to_transcript(b"r1cs_inst_evals", transcript);
 92    timer_eval.stop();
 93
 94    let r1cs_eval_proof = {
 95      let proof = R1CSEvalProof::prove(
 96        decomm,
 97        &rx,
 98        &ry,
 99        &inst_evals,
100        &gens.gens_r1cs_eval,
101        transcript,
102        &mut random_tape,
103      );
104
105      let proof_encoded: Vec<u8> = bincode::serialize(&proof).unwrap();
106      Timer::print(&format!("len_r1cs_eval_proof {:?}", proof_encoded.len()));
107      proof
108    };
109
110    SpartanProof {
111      r1cs_sat_proof,
112      inst_evals,
113      r1cs_eval_proof,
114    }
115  }
116
117  /// A method to verify the proof of the satisfiability of an R1CS instance
118  pub fn verify(
119    &self,
120    comm: &R1CSCommitment,
121    input: &Vec<Scalar>,
122    transcript: &mut Transcript,
123    gens: &SpartanGens,
124  ) -> Result<(), ProofVerifyError> {
125    transcript.append_protocol_name(SpartanProof::protocol_name());
126
127    let timer_sat_proof = Timer::new("verify_sat_proof");
128    assert_eq!(input.len(), comm.get_num_inputs());
129    let (rx, ry) = self
130      .r1cs_sat_proof
131      .verify(
132        comm.get_num_vars(),
133        comm.get_num_cons(),
134        input,
135        &self.inst_evals,
136        transcript,
137        &gens.gens_r1cs_sat,
138      )
139      .unwrap();
140    timer_sat_proof.stop();
141
142    let timer_eval_proof = Timer::new("verify_eval_proof");
143    self
144      .inst_evals
145      .append_to_transcript(b"r1cs_inst_evals", transcript);
146    assert!(self
147      .r1cs_eval_proof
148      .verify(
149        comm,
150        &rx,
151        &ry,
152        &self.inst_evals,
153        &gens.gens_r1cs_eval,
154        transcript
155      )
156      .is_ok());
157    timer_eval_proof.stop();
158    Ok(())
159  }
160}
161
162#[cfg(test)]
163mod tests {
164  use super::*;
165
166  #[test]
167  pub fn check_spartan_proof() {
168    let num_vars = 256;
169    let num_cons = num_vars;
170    let num_inputs = 10;
171    let (inst, vars, input) = R1CSInstance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
172
173    let r1cs_size = inst.size();
174    let gens_r1cs_eval = R1CSCommitmentGens::new(&r1cs_size, b"gens_r1cs_eval");
175
176    // create a commitment to R1CSInstance
177    let (comm, decomm) = SpartanProof::encode(&inst, &gens_r1cs_eval);
178
179    let gens_r1cs_sat = R1CSGens::new(num_cons, num_vars, b"gens_r1cs_sat");
180    let gens = SpartanGens::new(gens_r1cs_sat, gens_r1cs_eval);
181
182    let mut prover_transcript = Transcript::new(b"example");
183    let proof = SpartanProof::prove(&inst, &decomm, vars, &input, &gens, &mut prover_transcript);
184
185    let mut verifier_transcript = Transcript::new(b"example");
186    assert!(proof
187      .verify(&comm, &input, &mut verifier_transcript, &gens)
188      .is_ok());
189  }
190}