1use std::cmp::max;
  2
  3use crate::errors::ProofVerifyError;
  4use crate::r1csproof::R1CSVerifierProof;
  5use crate::{
  6  poseidon_transcript::PoseidonTranscript,
  7  r1csproof::{R1CSGens, R1CSProof},
  8  transcript::Transcript,
  9  InputsAssignment, Instance, VarsAssignment,
 10};
 11use ark_crypto_primitives::sponge::poseidon::PoseidonConfig;
 12use ark_crypto_primitives::sponge::Absorb;
 13use ark_ec::pairing::Pairing;
 14
 15use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
 16
 17#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
 18
 19// TestudoNizk is suitable for uniform circuits where the
 20// evaluation of R1CS matrices A, B and C is cheap and can
 21// be done by the verifier. For more complex circuits this
 22// operation has to be offloaded to the prover.
 23pub struct TestudoNizk<E: Pairing> {
 24  pub r1cs_verifier_proof: R1CSVerifierProof<E>,
 25  pub r: (Vec<E::ScalarField>, Vec<E::ScalarField>),
 26}
 27
 28pub struct TestudoNizkGens<E: Pairing> {
 29  gens_r1cs_sat: R1CSGens<E>,
 30}
 31
 32impl<E: Pairing> TestudoNizkGens<E> {
 33  /// Performs the setup required  by the polynomial commitment PST and Groth16
 34  pub fn setup(
 35    num_cons: usize,
 36    num_vars: usize,
 37    num_inputs: usize,
 38    poseidon: PoseidonConfig<E::ScalarField>,
 39  ) -> Self {
 40    // ensure num_vars is a power of 2
 41    let num_vars_padded = {
 42      let mut num_vars_padded = max(num_vars, num_inputs + 1);
 43      if num_vars_padded != num_vars_padded.next_power_of_two() {
 44        num_vars_padded = num_vars_padded.next_power_of_two();
 45      }
 46      num_vars_padded
 47    };
 48
 49    let num_cons_padded = {
 50      let mut num_cons_padded = num_cons;
 51
 52      // ensure that num_cons_padded is at least 2
 53      if num_cons_padded == 0 || num_cons_padded == 1 {
 54        num_cons_padded = 2;
 55      }
 56
 57      // ensure that num_cons_padded is a power of 2
 58      if num_cons.next_power_of_two() != num_cons {
 59        num_cons_padded = num_cons.next_power_of_two();
 60      }
 61      num_cons_padded
 62    };
 63
 64    let gens_r1cs_sat = R1CSGens::setup(
 65      b"gens_r1cs_sat",
 66      num_cons_padded,
 67      num_vars_padded,
 68      num_inputs,
 69      poseidon,
 70    );
 71    TestudoNizkGens { gens_r1cs_sat }
 72  }
 73}
 74
 75impl<E: Pairing> TestudoNizk<E>
 76where
 77  E::ScalarField: Absorb,
 78{
 79  // Returns a proof that the R1CS instance is satisfiable
 80  pub fn prove(
 81    inst: &Instance<E::ScalarField>,
 82    vars: VarsAssignment<E::ScalarField>,
 83    inputs: &InputsAssignment<E::ScalarField>,
 84    gens: &TestudoNizkGens<E>,
 85    transcript: &mut PoseidonTranscript<E::ScalarField>,
 86    poseidon: PoseidonConfig<E::ScalarField>,
 87  ) -> Result<TestudoNizk<E>, ProofVerifyError> {
 88    transcript.append_bytes(b"", &inst.digest);
 89
 90    let c: E::ScalarField = transcript.challenge_scalar(b"");
 91    transcript.new_from_state(&c);
 92
 93    // we might need to pad variables
 94    let padded_vars = {
 95      let num_padded_vars = inst.inst.get_num_vars();
 96      let num_vars = vars.assignment.len();
 97      if num_padded_vars > num_vars {
 98        vars.pad(num_padded_vars)
 99      } else {
100        vars
101      }
102    };
103
104    let (r1cs_sat_proof, rx, ry) = R1CSProof::prove(
105      &inst.inst,
106      padded_vars.assignment,
107      &inputs.assignment,
108      &gens.gens_r1cs_sat,
109      transcript,
110    );
111
112    let inst_evals = inst.inst.evaluate(&rx, &ry);
113
114    transcript.new_from_state(&c);
115    let r1cs_verifier_proof = r1cs_sat_proof
116      .prove_verifier(
117        inst.inst.get_num_vars(),
118        inst.inst.get_num_cons(),
119        &inputs.assignment,
120        &inst_evals,
121        transcript,
122        &gens.gens_r1cs_sat,
123        poseidon,
124      )
125      .unwrap();
126    Ok(TestudoNizk {
127      r1cs_verifier_proof,
128      r: (rx, ry),
129    })
130  }
131
132  // Verifies the satisfiability proof for the R1CS instance. In NIZK mode, the
133  // verifier evaluates matrices A, B and C themselves, which is a linear
134  // operation and hence this is not a SNARK.
135  // However, for highly structured circuits this operation is fast.
136  pub fn verify(
137    &self,
138    gens: &TestudoNizkGens<E>,
139    inst: &Instance<E::ScalarField>,
140    input: &InputsAssignment<E::ScalarField>,
141    transcript: &mut PoseidonTranscript<E::ScalarField>,
142    _poseidon: PoseidonConfig<E::ScalarField>,
143  ) -> Result<bool, ProofVerifyError> {
144    transcript.append_bytes(b"", &inst.digest);
145    let (claimed_rx, claimed_ry) = &self.r;
146    let inst_evals = inst.inst.evaluate(claimed_rx, claimed_ry);
147
148    let sat_verified = self.r1cs_verifier_proof.verify(
149      (claimed_rx.clone(), claimed_ry.clone()),
150      &input.assignment,
151      &inst_evals,
152      transcript,
153      &gens.gens_r1cs_sat,
154    )?;
155    assert!(sat_verified == true);
156    Ok(sat_verified)
157  }
158}
159
160#[cfg(test)]
161mod tests {
162  use crate::{
163    parameters::poseidon_params,
164    poseidon_transcript::PoseidonTranscript,
165    testudo_nizk::{TestudoNizk, TestudoNizkGens},
166    Instance,
167  };
168
169  #[test]
170  pub fn check_testudo_nizk() {
171    let num_vars = 256;
172    let num_cons = num_vars;
173    let num_inputs = 10;
174
175    type E = ark_bls12_377::Bls12_377;
176
177    // produce public generators
178    let gens = TestudoNizkGens::<E>::setup(num_cons, num_vars, num_inputs, poseidon_params());
179
180    // produce a synthetic R1CSInstance
181    let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);
182
183    let params = poseidon_params();
184
185    // produce a proof
186    let mut prover_transcript = PoseidonTranscript::new(&params);
187    let proof =
188      TestudoNizk::prove(&inst, vars, &inputs, &gens, &mut prover_transcript, params).unwrap();
189
190    // verify the proof
191    let mut verifier_transcript = PoseidonTranscript::new(&poseidon_params());
192    assert!(proof
193      .verify(
194        &gens,
195        &inst,
196        &inputs,
197        &mut verifier_transcript,
198        poseidon_params()
199      )
200      .is_ok());
201  }
202}