nova_snark/spartan/
direct.rs

1//! This module provides interfaces to directly prove a step circuit by using Spartan SNARK.
2//! In particular, it supports any SNARK that implements `RelaxedR1CSSNARK` trait
3//! (e.g., with the SNARKs implemented in ppsnark.rs or snark.rs).
4use crate::traits::evm_serde::EvmCompatSerde;
5use crate::{
6  errors::NovaError,
7  frontend::{
8    num::AllocatedNum,
9    r1cs::{NovaShape, NovaWitness},
10    shape_cs::ShapeCS,
11    solver::SatisfyingAssignment,
12    Circuit, ConstraintSystem, SynthesisError,
13  },
14  r1cs::{R1CSShape, RelaxedR1CSInstance, RelaxedR1CSWitness},
15  traits::{
16    circuit::StepCircuit,
17    commitment::CommitmentEngineTrait,
18    snark::{DigestHelperTrait, RelaxedR1CSSNARKTrait},
19    Engine,
20  },
21  Commitment, CommitmentKey, DerandKey,
22};
23use core::marker::PhantomData;
24use ff::Field;
25use serde::{Deserialize, Serialize};
26use serde_with::serde_as;
27
28/// A direct circuit that can be synthesized
29pub struct DirectCircuit<E: Engine, SC: StepCircuit<E::Scalar>> {
30  z_i: Option<Vec<E::Scalar>>, // inputs to the circuit
31  sc: SC,                      // step circuit to be executed
32}
33
34impl<E: Engine, SC: StepCircuit<E::Scalar>> DirectCircuit<E, SC> {
35  /// Create a new direct circuit from a step circuit and optional inputs
36  pub fn new(z_i: Option<Vec<E::Scalar>>, sc: SC) -> Self {
37    Self { z_i, sc }
38  }
39}
40
41impl<E: Engine, SC: StepCircuit<E::Scalar>> Circuit<E::Scalar> for DirectCircuit<E, SC> {
42  fn synthesize<CS: ConstraintSystem<E::Scalar>>(self, cs: &mut CS) -> Result<(), SynthesisError> {
43    // obtain the arity information
44    let arity = self.sc.arity();
45
46    // Allocate zi. If inputs.zi is not provided, allocate default value 0
47    let zero = vec![E::Scalar::ZERO; arity];
48    let z_i = (0..arity)
49      .map(|i| {
50        AllocatedNum::alloc(cs.namespace(|| format!("zi_{i}")), || {
51          Ok(self.z_i.as_ref().unwrap_or(&zero)[i])
52        })
53      })
54      .collect::<Result<Vec<AllocatedNum<E::Scalar>>, _>>()?;
55
56    let z_i_plus_one = self.sc.synthesize(&mut cs.namespace(|| "F"), &z_i)?;
57
58    // inputize both z_i and z_i_plus_one
59    for (j, input) in z_i.iter().enumerate().take(arity) {
60      let _ = input.inputize(cs.namespace(|| format!("input {j}")));
61    }
62    for (j, output) in z_i_plus_one.iter().enumerate().take(arity) {
63      let _ = output.inputize(cs.namespace(|| format!("output {j}")));
64    }
65
66    Ok(())
67  }
68}
69
70/// A type that holds the prover key
71#[derive(Clone, Serialize, Deserialize)]
72#[serde(bound = "")]
73pub struct ProverKey<E, S>
74where
75  E: Engine,
76  S: RelaxedR1CSSNARKTrait<E>,
77{
78  S: R1CSShape<E>,
79  ck: CommitmentKey<E>,
80  pk: S::ProverKey,
81}
82
83/// A type that holds the verifier key
84#[derive(Clone, Serialize, Deserialize)]
85#[serde(bound = "")]
86pub struct VerifierKey<E, S>
87where
88  E: Engine,
89  S: RelaxedR1CSSNARKTrait<E>,
90{
91  dk: DerandKey<E>,
92  vk: S::VerifierKey,
93}
94
95impl<E: Engine, S: RelaxedR1CSSNARKTrait<E>> VerifierKey<E, S> {
96  /// Returns the digest of the verifier's key
97  pub fn digest(&self) -> E::Scalar {
98    self.vk.digest()
99  }
100}
101
102/// A direct SNARK proving a step circuit
103#[serde_as]
104#[derive(Clone, Serialize, Deserialize)]
105#[serde(bound = "")]
106pub struct DirectSNARK<E, S, C>
107where
108  E: Engine,
109  S: RelaxedR1CSSNARKTrait<E>,
110  C: StepCircuit<E::Scalar>,
111{
112  comm_W: Commitment<E>, // commitment to the witness
113  #[serde_as(as = "EvmCompatSerde")]
114  blind_r_W: E::Scalar,
115  snark: S, // snark proving the witness is satisfying
116  _p: PhantomData<C>,
117}
118
119impl<E: Engine, S: RelaxedR1CSSNARKTrait<E>, C: StepCircuit<E::Scalar>> DirectSNARK<E, S, C> {
120  /// Produces prover and verifier keys for the direct SNARK
121  pub fn setup(sc: C) -> Result<(ProverKey<E, S>, VerifierKey<E, S>), NovaError> {
122    // construct a circuit that can be synthesized
123    let circuit: DirectCircuit<E, C> = DirectCircuit { z_i: None, sc };
124
125    let mut cs: ShapeCS<E> = ShapeCS::new();
126    let _ = circuit.synthesize(&mut cs);
127
128    let shape = cs.r1cs_shape()?;
129    let ck = R1CSShape::commitment_key(&[&shape], &[&*S::ck_floor()])?;
130
131    let (pk, vk) = S::setup(&ck, &shape)?;
132
133    let dk = E::CE::derand_key(&ck);
134
135    let pk = ProverKey { S: shape, ck, pk };
136
137    let vk = VerifierKey { dk, vk };
138
139    Ok((pk, vk))
140  }
141
142  /// Produces a proof of satisfiability of the provided circuit
143  pub fn prove(pk: &ProverKey<E, S>, sc: C, z_i: &[E::Scalar]) -> Result<Self, NovaError> {
144    let mut cs = SatisfyingAssignment::<E>::new();
145
146    let circuit: DirectCircuit<E, C> = DirectCircuit {
147      z_i: Some(z_i.to_vec()),
148      sc,
149    };
150
151    let _ = circuit.synthesize(&mut cs);
152    let (u, w) = cs
153      .r1cs_instance_and_witness(&pk.S, &pk.ck)
154      .map_err(|_e| NovaError::UnSat {
155        reason: "Unable to generate a satisfying witness".to_string(),
156      })?;
157
158    // convert the instance and witness to relaxed form
159    let (u_relaxed, w_relaxed) = (
160      RelaxedR1CSInstance::from_r1cs_instance_unchecked(&u.comm_W, &u.X),
161      RelaxedR1CSWitness::from_r1cs_witness(&pk.S, &w),
162    );
163
164    // derandomize/unblind commitments
165    let (derandom_w_relaxed, blind_W, blind_E) = w_relaxed.derandomize();
166    let derandom_u_relaxed = u_relaxed.derandomize(&E::CE::derand_key(&pk.ck), &blind_W, &blind_E);
167
168    // prove the instance using Spartan
169    let snark = S::prove(
170      &pk.ck,
171      &pk.pk,
172      &pk.S,
173      &derandom_u_relaxed,
174      &derandom_w_relaxed,
175    )?;
176
177    Ok(DirectSNARK {
178      comm_W: u.comm_W,
179      blind_r_W: w_relaxed.r_W,
180      snark,
181      _p: PhantomData,
182    })
183  }
184
185  /// Verifies a proof of satisfiability
186  pub fn verify(&self, vk: &VerifierKey<E, S>, io: &[E::Scalar]) -> Result<(), NovaError> {
187    // derandomize/unblind commitments
188    let comm_W = E::CE::derandomize(&vk.dk, &self.comm_W, &self.blind_r_W);
189
190    // construct an instance using the provided commitment to the witness and z_i and z_{i+1}
191    let u_relaxed = RelaxedR1CSInstance::from_r1cs_instance_unchecked(&comm_W, io);
192
193    // verify the snark using the constructed instance
194    self.snark.verify(&vk.vk, &u_relaxed)?;
195
196    Ok(())
197  }
198}
199
200#[cfg(test)]
201mod tests {
202  use super::*;
203  use crate::{
204    frontend::{num::AllocatedNum, ConstraintSystem, SynthesisError},
205    provider::{Bn256EngineKZG, PallasEngine, Secp256k1Engine},
206  };
207  use core::marker::PhantomData;
208  use ff::PrimeField;
209
210  #[derive(Clone, Debug, Default)]
211  struct CubicCircuit<F: PrimeField> {
212    _p: PhantomData<F>,
213  }
214
215  impl<F: PrimeField> StepCircuit<F> for CubicCircuit<F> {
216    fn arity(&self) -> usize {
217      1
218    }
219
220    fn synthesize<CS: ConstraintSystem<F>>(
221      &self,
222      cs: &mut CS,
223      z: &[AllocatedNum<F>],
224    ) -> Result<Vec<AllocatedNum<F>>, SynthesisError> {
225      // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
226      let x = &z[0];
227      let x_sq = x.square(cs.namespace(|| "x_sq"))?;
228      let x_cu = x_sq.mul(cs.namespace(|| "x_cu"), x)?;
229      let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
230        Ok(x_cu.get_value().unwrap() + x.get_value().unwrap() + F::from(5u64))
231      })?;
232
233      cs.enforce(
234        || "y = x^3 + x + 5",
235        |lc| {
236          lc + x_cu.get_variable()
237            + x.get_variable()
238            + CS::one()
239            + CS::one()
240            + CS::one()
241            + CS::one()
242            + CS::one()
243        },
244        |lc| lc + CS::one(),
245        |lc| lc + y.get_variable(),
246      );
247
248      Ok(vec![y])
249    }
250  }
251
252  impl<F: PrimeField> CubicCircuit<F> {
253    fn output(&self, z: &[F]) -> Vec<F> {
254      vec![z[0] * z[0] * z[0] + z[0] + F::from(5u64)]
255    }
256  }
257
258  #[test]
259  fn test_direct_snark() {
260    type E = PallasEngine;
261    type EE = crate::provider::ipa_pc::EvaluationEngine<E>;
262    type S = crate::spartan::snark::RelaxedR1CSSNARK<E, EE>;
263    test_direct_snark_with::<E, S>();
264
265    type Spp = crate::spartan::ppsnark::RelaxedR1CSSNARK<E, EE>;
266    test_direct_snark_with::<E, Spp>();
267
268    type E2 = Bn256EngineKZG;
269    type EE2 = crate::provider::hyperkzg::EvaluationEngine<E2>;
270    type S2 = crate::spartan::snark::RelaxedR1CSSNARK<E2, EE2>;
271    test_direct_snark_with::<E2, S2>();
272
273    type S2pp = crate::spartan::ppsnark::RelaxedR1CSSNARK<E2, EE2>;
274    test_direct_snark_with::<E2, S2pp>();
275
276    type E3 = Secp256k1Engine;
277    type EE3 = crate::provider::ipa_pc::EvaluationEngine<E3>;
278    type S3 = crate::spartan::snark::RelaxedR1CSSNARK<E3, EE3>;
279    test_direct_snark_with::<E3, S3>();
280
281    type S3pp = crate::spartan::ppsnark::RelaxedR1CSSNARK<E3, EE3>;
282    test_direct_snark_with::<E3, S3pp>();
283  }
284
285  fn test_direct_snark_with<E: Engine, S: RelaxedR1CSSNARKTrait<E>>() {
286    let circuit = CubicCircuit::default();
287
288    // produce keys
289    let (pk, vk) =
290      DirectSNARK::<E, S, CubicCircuit<<E as Engine>::Scalar>>::setup(circuit.clone()).unwrap();
291
292    let num_steps = 3;
293
294    // setup inputs
295    let z0 = vec![<E as Engine>::Scalar::ZERO];
296    let mut z_i = z0;
297
298    for _i in 0..num_steps {
299      // produce a SNARK
300      let res = DirectSNARK::prove(&pk, circuit.clone(), &z_i);
301      assert!(res.is_ok());
302
303      let z_i_plus_one = circuit.output(&z_i);
304
305      let snark = res.unwrap();
306
307      // verify the SNARK
308      let io = z_i
309        .clone()
310        .into_iter()
311        .chain(z_i_plus_one.clone())
312        .collect::<Vec<_>>();
313      let res = snark.verify(&vk, &io);
314      assert!(res.is_ok());
315
316      // set input to the next step
317      z_i.clone_from(&z_i_plus_one);
318    }
319
320    // sanity: check the claimed output with a direct computation of the same
321    assert_eq!(z_i, vec![<E as Engine>::Scalar::from(2460515u64)]);
322  }
323}
nova_snark/spartan/direct.rs

nova_snark/spartan/
direct.rs
