Nova/src/circuit.rs
src/circuit.rsRaw
1//! There are two Verification Circuits. The primary and the secondary.
2//! Each of them is over a Pasta curve but
3//! only the primary executes the next step of the computation.
4//! We have two running instances. Each circuit takes as input 2 hashes: one for each
5//! of the running instances. Each of these hashes is
6//! H(params = H(shape, gens), i, z0, zi, U). Each circuit folds the last invocation of
7//! the other into the running instance
8
9use super::{
10 commitments::Commitment,
11 constants::{NUM_FE_FOR_HASH, NUM_HASH_BITS},
12 gadgets::{
13 ecc::AllocatedPoint,
14 r1cs::{AllocatedR1CSInstance, AllocatedRelaxedR1CSInstance},
15 utils::{
16 alloc_num_equals, alloc_scalar_as_base, alloc_zero, conditionally_select, le_bits_to_num,
17 },
18 },
19 r1cs::{R1CSInstance, RelaxedR1CSInstance},
20 traits::{circuit::StepCircuit, Group, ROCircuitTrait, ROConstantsCircuit},
21};
22use bellperson::{
23 gadgets::{
24 boolean::{AllocatedBit, Boolean},
25 num::AllocatedNum,
26 Assignment,
27 },
28 Circuit, ConstraintSystem, SynthesisError,
29};
30use ff::Field;
31
32#[derive(Debug, Clone)]
33pub struct NovaAugmentedCircuitParams {
34 limb_width: usize,
35 n_limbs: usize,
36 is_primary_circuit: bool, // A boolean indicating if this is the primary circuit
37}
38
39impl NovaAugmentedCircuitParams {
40 pub fn new(limb_width: usize, n_limbs: usize, is_primary_circuit: bool) -> Self {
41 Self {
42 limb_width,
43 n_limbs,
44 is_primary_circuit,
45 }
46 }
47}
48
49#[derive(Debug)]
50pub struct NovaAugmentedCircuitInputs<G: Group> {
51 params: G::Scalar, // Hash(Shape of u2, Gens for u2). Needed for computing the challenge.
52 i: G::Base,
53 z0: G::Base,
54 zi: Option<G::Base>,
55 U: Option<RelaxedR1CSInstance<G>>,
56 u: Option<R1CSInstance<G>>,
57 T: Option<Commitment<G>>,
58}
59
60impl<G> NovaAugmentedCircuitInputs<G>
61where
62 G: Group,
63{
64 /// Create new inputs/witness for the verification circuit
65 #[allow(clippy::too_many_arguments)]
66 pub fn new(
67 params: G::Scalar,
68 i: G::Base,
69 z0: G::Base,
70 zi: Option<G::Base>,
71 U: Option<RelaxedR1CSInstance<G>>,
72 u: Option<R1CSInstance<G>>,
73 T: Option<Commitment<G>>,
74 ) -> Self {
75 Self {
76 params,
77 i,
78 z0,
79 zi,
80 U,
81 u,
82 T,
83 }
84 }
85}
86
87/// The augmented circuit F' in Nova that includes a step circuit F
88/// and the circuit for the verifier in Nova's non-interactive folding scheme
89pub struct NovaAugmentedCircuit<G, SC>
90where
91 G: Group,
92 SC: StepCircuit<G::Base>,
93{
94 params: NovaAugmentedCircuitParams,
95 ro_consts: ROConstantsCircuit<G>,
96 inputs: Option<NovaAugmentedCircuitInputs<G>>,
97 step_circuit: SC, // The function that is applied for each step
98}
99
100impl<G, SC> NovaAugmentedCircuit<G, SC>
101where
102 G: Group,
103 SC: StepCircuit<G::Base>,
104{
105 /// Create a new verification circuit for the input relaxed r1cs instances
106 pub fn new(
107 params: NovaAugmentedCircuitParams,
108 inputs: Option<NovaAugmentedCircuitInputs<G>>,
109 step_circuit: SC,
110 ro_consts: ROConstantsCircuit<G>,
111 ) -> Self {
112 Self {
113 params,
114 inputs,
115 step_circuit,
116 ro_consts,
117 }
118 }
119
120 /// Allocate all witnesses and return
121 fn alloc_witness<CS: ConstraintSystem<<G as Group>::Base>>(
122 &self,
123 mut cs: CS,
124 ) -> Result<
125 (
126 AllocatedNum<G::Base>,
127 AllocatedNum<G::Base>,
128 AllocatedNum<G::Base>,
129 AllocatedNum<G::Base>,
130 AllocatedRelaxedR1CSInstance<G>,
131 AllocatedR1CSInstance<G>,
132 AllocatedPoint<G::Base>,
133 ),
134 SynthesisError,
135 > {
136 // Allocate the params
137 let params = alloc_scalar_as_base::<G, _>(
138 cs.namespace(|| "params"),
139 self.inputs.get().map_or(None, |inputs| Some(inputs.params)),
140 )?;
141
142 // Allocate i
143 let i = AllocatedNum::alloc(cs.namespace(|| "i"), || Ok(self.inputs.get()?.i))?;
144
145 // Allocate z0
146 let z_0 = AllocatedNum::alloc(cs.namespace(|| "z0"), || Ok(self.inputs.get()?.z0))?;
147
148 // Allocate zi. If inputs.zi is not provided (base case) allocate default value 0
149 let z_i = AllocatedNum::alloc(cs.namespace(|| "zi"), || {
150 Ok(self.inputs.get()?.zi.unwrap_or_else(G::Base::zero))
151 })?;
152
153 // Allocate the running instance
154 let U: AllocatedRelaxedR1CSInstance<G> = AllocatedRelaxedR1CSInstance::alloc(
155 cs.namespace(|| "Allocate U"),
156 self.inputs.get().map_or(None, |inputs| {
157 inputs.U.get().map_or(None, |U| Some(U.clone()))
158 }),
159 self.params.limb_width,
160 self.params.n_limbs,
161 )?;
162
163 // Allocate the instance to be folded in
164 let u = AllocatedR1CSInstance::alloc(
165 cs.namespace(|| "allocate instance u to fold"),
166 self.inputs.get().map_or(None, |inputs| {
167 inputs.u.get().map_or(None, |u| Some(u.clone()))
168 }),
169 )?;
170
171 // Allocate T
172 let T = AllocatedPoint::alloc(
173 cs.namespace(|| "allocate T"),
174 self.inputs.get().map_or(None, |inputs| {
175 inputs
176 .T
177 .get()
178 .map_or(None, |T| Some(T.comm.to_coordinates()))
179 }),
180 )?;
181
182 Ok((params, i, z_0, z_i, U, u, T))
183 }
184
185 /// Synthesizes base case and returns the new relaxed R1CSInstance
186 fn synthesize_base_case<CS: ConstraintSystem<<G as Group>::Base>>(
187 &self,
188 mut cs: CS,
189 u: AllocatedR1CSInstance<G>,
190 ) -> Result<AllocatedRelaxedR1CSInstance<G>, SynthesisError> {
191 let U_default: AllocatedRelaxedR1CSInstance<G> = if self.params.is_primary_circuit {
192 // The primary circuit just returns the default R1CS instance
193 AllocatedRelaxedR1CSInstance::default(
194 cs.namespace(|| "Allocate U_default"),
195 self.params.limb_width,
196 self.params.n_limbs,
197 )?
198 } else {
199 // The secondary circuit returns the incoming R1CS instance
200 AllocatedRelaxedR1CSInstance::from_r1cs_instance(
201 cs.namespace(|| "Allocate U_default"),
202 u,
203 self.params.limb_width,
204 self.params.n_limbs,
205 )?
206 };
207 Ok(U_default)
208 }
209
210 /// Synthesizes non base case and returns the new relaxed R1CSInstance
211 /// And a boolean indicating if all checks pass
212 #[allow(clippy::too_many_arguments)]
213 fn synthesize_non_base_case<CS: ConstraintSystem<<G as Group>::Base>>(
214 &self,
215 mut cs: CS,
216 params: AllocatedNum<G::Base>,
217 i: AllocatedNum<G::Base>,
218 z_0: AllocatedNum<G::Base>,
219 z_i: AllocatedNum<G::Base>,
220 U: AllocatedRelaxedR1CSInstance<G>,
221 u: AllocatedR1CSInstance<G>,
222 T: AllocatedPoint<G::Base>,
223 ) -> Result<(AllocatedRelaxedR1CSInstance<G>, AllocatedBit), SynthesisError> {
224 // Check that u.x[0] = Hash(params, U, i, z0, zi)
225 let mut ro = G::ROCircuit::new(self.ro_consts.clone(), NUM_FE_FOR_HASH);
226 ro.absorb(params.clone());
227 ro.absorb(i);
228 ro.absorb(z_0);
229 ro.absorb(z_i);
230 U.absorb_in_ro(cs.namespace(|| "absorb U"), &mut ro)?;
231
232 let hash_bits = ro.squeeze(cs.namespace(|| "Input hash"), NUM_HASH_BITS)?;
233 let hash = le_bits_to_num(cs.namespace(|| "bits to hash"), hash_bits)?;
234 let check_pass = alloc_num_equals(
235 cs.namespace(|| "check consistency of u.X[0] with H(params, U, i, z0, zi)"),
236 &u.X0,
237 &hash,
238 )?;
239
240 // Run NIFS Verifier
241 let U_fold = U.fold_with_r1cs(
242 cs.namespace(|| "compute fold of U and u"),
243 params,
244 u,
245 T,
246 self.ro_consts.clone(),
247 self.params.limb_width,
248 self.params.n_limbs,
249 )?;
250
251 Ok((U_fold, check_pass))
252 }
253}
254
255impl<G, SC> Circuit<<G as Group>::Base> for NovaAugmentedCircuit<G, SC>
256where
257 G: Group,
258 SC: StepCircuit<G::Base>,
259{
260 fn synthesize<CS: ConstraintSystem<<G as Group>::Base>>(
261 self,
262 cs: &mut CS,
263 ) -> Result<(), SynthesisError> {
264 // Allocate all witnesses
265 let (params, i, z_0, z_i, U, u, T) =
266 self.alloc_witness(cs.namespace(|| "allocate the circuit witness"))?;
267
268 // Compute variable indicating if this is the base case
269 let zero = alloc_zero(cs.namespace(|| "zero"))?;
270 let is_base_case = alloc_num_equals(cs.namespace(|| "Check if base case"), &i.clone(), &zero)?;
271
272 // Synthesize the circuit for the base case and get the new running instance
273 let Unew_base = self.synthesize_base_case(cs.namespace(|| "base case"), u.clone())?;
274
275 // Synthesize the circuit for the non-base case and get the new running
276 // instance along with a boolean indicating if all checks have passed
277 let (Unew_non_base, check_non_base_pass) = self.synthesize_non_base_case(
278 cs.namespace(|| "synthesize non base case"),
279 params.clone(),
280 i.clone(),
281 z_0.clone(),
282 z_i.clone(),
283 U,
284 u.clone(),
285 T,
286 )?;
287
288 // Either check_non_base_pass=true or we are in the base case
289 let should_be_false = AllocatedBit::nor(
290 cs.namespace(|| "check_non_base_pass nor base_case"),
291 &check_non_base_pass,
292 &is_base_case,
293 )?;
294 cs.enforce(
295 || "check_non_base_pass nor base_case = false",
296 |lc| lc + should_be_false.get_variable(),
297 |lc| lc + CS::one(),
298 |lc| lc,
299 );
300
301 // Compute the U_new
302 let Unew = Unew_base.conditionally_select(
303 cs.namespace(|| "compute U_new"),
304 Unew_non_base,
305 &Boolean::from(is_base_case.clone()),
306 )?;
307
308 // Compute i + 1
309 let i_new = AllocatedNum::alloc(cs.namespace(|| "i + 1"), || {
310 Ok(*i.get_value().get()? + G::Base::one())
311 })?;
312 cs.enforce(
313 || "check i + 1",
314 |lc| lc,
315 |lc| lc,
316 |lc| lc + i_new.get_variable() - CS::one() - i.get_variable(),
317 );
318
319 // Compute z_{i+1}
320 let z_input = conditionally_select(
321 cs.namespace(|| "select input to F"),
322 &z_0,
323 &z_i,
324 &Boolean::from(is_base_case),
325 )?;
326
327 let z_next = self
328 .step_circuit
329 .synthesize(&mut cs.namespace(|| "F"), z_input)?;
330
331 // Compute the new hash H(params, Unew, i+1, z0, z_{i+1})
332 let mut ro = G::ROCircuit::new(self.ro_consts, NUM_FE_FOR_HASH);
333 ro.absorb(params);
334 ro.absorb(i_new.clone());
335 ro.absorb(z_0);
336 ro.absorb(z_next);
337 Unew.absorb_in_ro(cs.namespace(|| "absorb U_new"), &mut ro)?;
338 let hash_bits = ro.squeeze(cs.namespace(|| "output hash bits"), NUM_HASH_BITS)?;
339 let hash = le_bits_to_num(cs.namespace(|| "convert hash to num"), hash_bits)?;
340
341 // Outputs the computed hash and u.X[1] that corresponds to the hash of the other circuit
342 u.X1
343 .inputize(cs.namespace(|| "Output unmodified hash of the other circuit"))?;
344 hash.inputize(cs.namespace(|| "output new hash of this circuit"))?;
345
346 Ok(())
347 }
348}
349
350#[cfg(test)]
351mod tests {
352 use super::*;
353 use crate::bellperson::{shape_cs::ShapeCS, solver::SatisfyingAssignment};
354 type G1 = pasta_curves::pallas::Point;
355 type G2 = pasta_curves::vesta::Point;
356 use crate::constants::{BN_LIMB_WIDTH, BN_N_LIMBS};
357 use crate::{
358 bellperson::r1cs::{NovaShape, NovaWitness},
359 poseidon::PoseidonConstantsCircuit,
360 traits::{circuit::TrivialTestCircuit, ROConstantsTrait},
361 };
362
363 #[test]
364 fn test_recursive_circuit() {
365 // In the following we use 1 to refer to the primary, and 2 to refer to the secondary circuit
366 let params1 = NovaAugmentedCircuitParams::new(BN_LIMB_WIDTH, BN_N_LIMBS, true);
367 let params2 = NovaAugmentedCircuitParams::new(BN_LIMB_WIDTH, BN_N_LIMBS, false);
368 let ro_consts1: ROConstantsCircuit<G2> = PoseidonConstantsCircuit::new();
369 let ro_consts2: ROConstantsCircuit<G1> = PoseidonConstantsCircuit::new();
370
371 // Initialize the shape and gens for the primary
372 let circuit1: NovaAugmentedCircuit<G2, TrivialTestCircuit<<G2 as Group>::Base>> =
373 NovaAugmentedCircuit::new(
374 params1.clone(),
375 None,
376 TrivialTestCircuit::default(),
377 ro_consts1.clone(),
378 );
379 let mut cs: ShapeCS<G1> = ShapeCS::new();
380 let _ = circuit1.synthesize(&mut cs);
381 let (shape1, gens1) = (cs.r1cs_shape(), cs.r1cs_gens());
382 assert_eq!(cs.num_constraints(), 19739);
383
384 // Initialize the shape and gens for the secondary
385 let circuit2: NovaAugmentedCircuit<G1, TrivialTestCircuit<<G1 as Group>::Base>> =
386 NovaAugmentedCircuit::new(
387 params2.clone(),
388 None,
389 TrivialTestCircuit::default(),
390 ro_consts2.clone(),
391 );
392 let mut cs: ShapeCS<G2> = ShapeCS::new();
393 let _ = circuit2.synthesize(&mut cs);
394 let (shape2, gens2) = (cs.r1cs_shape(), cs.r1cs_gens());
395 assert_eq!(cs.num_constraints(), 20271);
396
397 // Execute the base case for the primary
398 let zero1 = <<G2 as Group>::Base as Field>::zero();
399 let mut cs1: SatisfyingAssignment<G1> = SatisfyingAssignment::new();
400 let inputs1: NovaAugmentedCircuitInputs<G2> =
401 NovaAugmentedCircuitInputs::new(shape2.get_digest(), zero1, zero1, None, None, None, None);
402 let circuit1: NovaAugmentedCircuit<G2, TrivialTestCircuit<<G2 as Group>::Base>> =
403 NovaAugmentedCircuit::new(
404 params1,
405 Some(inputs1),
406 TrivialTestCircuit::default(),
407 ro_consts1,
408 );
409 let _ = circuit1.synthesize(&mut cs1);
410 let (inst1, witness1) = cs1.r1cs_instance_and_witness(&shape1, &gens1).unwrap();
411 // Make sure that this is satisfiable
412 assert!(shape1.is_sat(&gens1, &inst1, &witness1).is_ok());
413
414 // Execute the base case for the secondary
415 let zero2 = <<G1 as Group>::Base as Field>::zero();
416 let mut cs2: SatisfyingAssignment<G2> = SatisfyingAssignment::new();
417 let inputs2: NovaAugmentedCircuitInputs<G1> = NovaAugmentedCircuitInputs::new(
418 shape1.get_digest(),
419 zero2,
420 zero2,
421 None,
422 None,
423 Some(inst1),
424 None,
425 );
426 let circuit: NovaAugmentedCircuit<G1, TrivialTestCircuit<<G1 as Group>::Base>> =
427 NovaAugmentedCircuit::new(
428 params2,
429 Some(inputs2),
430 TrivialTestCircuit::default(),
431 ro_consts2,
432 );
433 let _ = circuit.synthesize(&mut cs2);
434 let (inst2, witness2) = cs2.r1cs_instance_and_witness(&shape2, &gens2).unwrap();
435 // Make sure that it is satisfiable
436 assert!(shape2.is_sat(&gens2, &inst2, &witness2).is_ok());
437 }
438}