Nova/src/spartan/direct.rs
src/spartan/direct.rsRaw
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::{
5 bellperson::{
6 r1cs::{NovaShape, NovaWitness},
7 shape_cs::ShapeCS,
8 solver::SatisfyingAssignment,
9 },
10 errors::NovaError,
11 r1cs::{R1CSShape, RelaxedR1CSInstance, RelaxedR1CSWitness},
12 traits::{circuit::StepCircuit, snark::RelaxedR1CSSNARKTrait, Group},
13 Commitment, CommitmentKey,
14};
15use bellperson::{gadgets::num::AllocatedNum, Circuit, ConstraintSystem, SynthesisError};
16use core::marker::PhantomData;
17use ff::Field;
18use serde::{Deserialize, Serialize};
19
20struct DirectCircuit<G: Group, SC: StepCircuit<G::Scalar>> {
21 z_i: Option<Vec<G::Scalar>>, // inputs to the circuit
22 sc: SC, // step circuit to be executed
23}
24
25impl<G: Group, SC: StepCircuit<G::Scalar>> Circuit<G::Scalar> for DirectCircuit<G, SC> {
26 fn synthesize<CS: ConstraintSystem<G::Scalar>>(self, cs: &mut CS) -> Result<(), SynthesisError> {
27 // obtain the arity information
28 let arity = self.sc.arity();
29
30 // Allocate zi. If inputs.zi is not provided, allocate default value 0
31 let zero = vec![G::Scalar::ZERO; arity];
32 let z_i = (0..arity)
33 .map(|i| {
34 AllocatedNum::alloc(cs.namespace(|| format!("zi_{i}")), || {
35 Ok(self.z_i.as_ref().unwrap_or(&zero)[i])
36 })
37 })
38 .collect::<Result<Vec<AllocatedNum<G::Scalar>>, _>>()?;
39
40 let z_i_plus_one = self.sc.synthesize(&mut cs.namespace(|| "F"), &z_i)?;
41
42 // inputize both z_i and z_i_plus_one
43 for (j, input) in z_i.iter().enumerate().take(arity) {
44 let _ = input.inputize(cs.namespace(|| format!("input {j}")));
45 }
46 for (j, output) in z_i_plus_one.iter().enumerate().take(arity) {
47 let _ = output.inputize(cs.namespace(|| format!("output {j}")));
48 }
49
50 Ok(())
51 }
52}
53
54/// A type that holds the prover key
55#[derive(Clone, Serialize, Deserialize)]
56#[serde(bound = "")]
57pub struct ProverKey<G, S>
58where
59 G: Group,
60 S: RelaxedR1CSSNARKTrait<G>,
61{
62 S: R1CSShape<G>,
63 ck: CommitmentKey<G>,
64 pk: S::ProverKey,
65}
66
67/// A type that holds the verifier key
68#[derive(Clone, Serialize, Deserialize)]
69#[serde(bound = "")]
70pub struct VerifierKey<G, S>
71where
72 G: Group,
73 S: RelaxedR1CSSNARKTrait<G>,
74{
75 vk: S::VerifierKey,
76}
77
78/// A direct SNARK proving a step circuit
79#[derive(Clone, Serialize, Deserialize)]
80#[serde(bound = "")]
81pub struct DirectSNARK<G, S, C>
82where
83 G: Group,
84 S: RelaxedR1CSSNARKTrait<G>,
85 C: StepCircuit<G::Scalar>,
86{
87 comm_W: Commitment<G>, // commitment to the witness
88 snark: S, // snark proving the witness is satisfying
89 _p: PhantomData<C>,
90}
91
92impl<G: Group, S: RelaxedR1CSSNARKTrait<G>, C: StepCircuit<G::Scalar>> DirectSNARK<G, S, C> {
93 /// Produces prover and verifier keys for the direct SNARK
94 pub fn setup(sc: C) -> Result<(ProverKey<G, S>, VerifierKey<G, S>), NovaError> {
95 // construct a circuit that can be synthesized
96 let circuit: DirectCircuit<G, C> = DirectCircuit { z_i: None, sc };
97
98 let mut cs: ShapeCS<G> = ShapeCS::new();
99 let _ = circuit.synthesize(&mut cs);
100 let (shape, ck) = cs.r1cs_shape();
101
102 let (pk, vk) = S::setup(&ck, &shape)?;
103
104 let pk = ProverKey { S: shape, ck, pk };
105
106 let vk = VerifierKey { vk };
107
108 Ok((pk, vk))
109 }
110
111 /// Produces a proof of satisfiability of the provided circuit
112 pub fn prove(pk: &ProverKey<G, S>, sc: C, z_i: &[G::Scalar]) -> Result<Self, NovaError> {
113 let mut cs: SatisfyingAssignment<G> = SatisfyingAssignment::new();
114
115 let circuit: DirectCircuit<G, C> = DirectCircuit {
116 z_i: Some(z_i.to_vec()),
117 sc,
118 };
119
120 let _ = circuit.synthesize(&mut cs);
121 let (u, w) = cs
122 .r1cs_instance_and_witness(&pk.S, &pk.ck)
123 .map_err(|_e| NovaError::UnSat)?;
124
125 // convert the instance and witness to relaxed form
126 let (u_relaxed, w_relaxed) = (
127 RelaxedR1CSInstance::from_r1cs_instance_unchecked(&u.comm_W, &u.X),
128 RelaxedR1CSWitness::from_r1cs_witness(&pk.S, &w),
129 );
130
131 // prove the instance using Spartan
132 let snark = S::prove(&pk.ck, &pk.pk, &u_relaxed, &w_relaxed)?;
133
134 Ok(DirectSNARK {
135 comm_W: u.comm_W,
136 snark,
137 _p: Default::default(),
138 })
139 }
140
141 /// Verifies a proof of satisfiability
142 pub fn verify(&self, vk: &VerifierKey<G, S>, io: &[G::Scalar]) -> Result<(), NovaError> {
143 // construct an instance using the provided commitment to the witness and z_i and z_{i+1}
144 let u_relaxed = RelaxedR1CSInstance::from_r1cs_instance_unchecked(&self.comm_W, io);
145
146 // verify the snark using the constructed instance
147 self.snark.verify(&vk.vk, &u_relaxed)?;
148
149 Ok(())
150 }
151}
152
153#[cfg(test)]
154mod tests {
155 use super::*;
156 use crate::provider::bn256_grumpkin::bn256;
157 use ::bellperson::{gadgets::num::AllocatedNum, ConstraintSystem, SynthesisError};
158 use core::marker::PhantomData;
159 use ff::PrimeField;
160
161 #[derive(Clone, Debug, Default)]
162 struct CubicCircuit<F: PrimeField> {
163 _p: PhantomData<F>,
164 }
165
166 impl<F> StepCircuit<F> for CubicCircuit<F>
167 where
168 F: PrimeField,
169 {
170 fn arity(&self) -> usize {
171 1
172 }
173
174 fn synthesize<CS: ConstraintSystem<F>>(
175 &self,
176 cs: &mut CS,
177 z: &[AllocatedNum<F>],
178 ) -> Result<Vec<AllocatedNum<F>>, SynthesisError> {
179 // Consider a cubic equation: `x^3 + x + 5 = y`, where `x` and `y` are respectively the input and output.
180 let x = &z[0];
181 let x_sq = x.square(cs.namespace(|| "x_sq"))?;
182 let x_cu = x_sq.mul(cs.namespace(|| "x_cu"), x)?;
183 let y = AllocatedNum::alloc(cs.namespace(|| "y"), || {
184 Ok(x_cu.get_value().unwrap() + x.get_value().unwrap() + F::from(5u64))
185 })?;
186
187 cs.enforce(
188 || "y = x^3 + x + 5",
189 |lc| {
190 lc + x_cu.get_variable()
191 + x.get_variable()
192 + CS::one()
193 + CS::one()
194 + CS::one()
195 + CS::one()
196 + CS::one()
197 },
198 |lc| lc + CS::one(),
199 |lc| lc + y.get_variable(),
200 );
201
202 Ok(vec![y])
203 }
204
205 fn output(&self, z: &[F]) -> Vec<F> {
206 vec![z[0] * z[0] * z[0] + z[0] + F::from(5u64)]
207 }
208 }
209
210 #[test]
211 fn test_direct_snark() {
212 type G = pasta_curves::pallas::Point;
213 type EE = crate::provider::ipa_pc::EvaluationEngine<G>;
214 type S = crate::spartan::snark::RelaxedR1CSSNARK<G, EE>;
215 type Spp = crate::spartan::ppsnark::RelaxedR1CSSNARK<G, EE>;
216 test_direct_snark_with::<G, S>();
217 test_direct_snark_with::<G, Spp>();
218
219 type G2 = bn256::Point;
220 type EE2 = crate::provider::ipa_pc::EvaluationEngine<G2>;
221 type S2 = crate::spartan::snark::RelaxedR1CSSNARK<G2, EE2>;
222 type S2pp = crate::spartan::ppsnark::RelaxedR1CSSNARK<G2, EE2>;
223 test_direct_snark_with::<G2, S2>();
224 test_direct_snark_with::<G2, S2pp>();
225 }
226
227 fn test_direct_snark_with<G: Group, S: RelaxedR1CSSNARKTrait<G>>() {
228 let circuit = CubicCircuit::default();
229
230 // produce keys
231 let (pk, vk) =
232 DirectSNARK::<G, S, CubicCircuit<<G as Group>::Scalar>>::setup(circuit.clone()).unwrap();
233
234 let num_steps = 3;
235
236 // setup inputs
237 let z0 = vec![<G as Group>::Scalar::ZERO];
238 let mut z_i = z0;
239
240 for _i in 0..num_steps {
241 // produce a SNARK
242 let res = DirectSNARK::prove(&pk, circuit.clone(), &z_i);
243 assert!(res.is_ok());
244
245 let z_i_plus_one = circuit.output(&z_i);
246
247 let snark = res.unwrap();
248
249 // verify the SNARK
250 let io = z_i
251 .clone()
252 .into_iter()
253 .chain(z_i_plus_one.clone().into_iter())
254 .collect::<Vec<_>>();
255 let res = snark.verify(&vk, &io);
256 assert!(res.is_ok());
257
258 // set input to the next step
259 z_i = z_i_plus_one.clone();
260 }
261
262 // sanity: check the claimed output with a direct computation of the same
263 assert_eq!(z_i, vec![<G as Group>::Scalar::from(2460515u64)]);
264 }
265}