Nova/src/gadgets/r1cs.rs
src/gadgets/r1cs.rsRaw
1//! This module implements various gadgets necessary for folding R1CS types.
2use super::nonnative::{
3 bignat::BigNat,
4 util::{f_to_nat, Num},
5};
6use crate::{
7 constants::{NUM_CHALLENGE_BITS, NUM_FE_FOR_RO},
8 gadgets::{
9 ecc::AllocatedPoint,
10 utils::{
11 alloc_bignat_constant, alloc_one, alloc_scalar_as_base, conditionally_select,
12 conditionally_select_bignat, le_bits_to_num,
13 },
14 },
15 r1cs::{R1CSInstance, RelaxedR1CSInstance},
16 traits::{Group, ROCircuitTrait, ROConstantsCircuit},
17};
18use bellperson::{
19 gadgets::{boolean::Boolean, num::AllocatedNum, Assignment},
20 ConstraintSystem, SynthesisError,
21};
22use ff::Field;
23
24/// An Allocated R1CS Instance
25#[derive(Clone)]
26pub struct AllocatedR1CSInstance<G>
27where
28 G: Group,
29{
30 pub(crate) W: AllocatedPoint<G>,
31 pub(crate) X0: AllocatedNum<G::Base>,
32 pub(crate) X1: AllocatedNum<G::Base>,
33}
34
35impl<G> AllocatedR1CSInstance<G>
36where
37 G: Group,
38{
39 /// Takes the r1cs instance and creates a new allocated r1cs instance
40 pub fn alloc<CS: ConstraintSystem<<G as Group>::Base>>(
41 mut cs: CS,
42 u: Option<R1CSInstance<G>>,
43 ) -> Result<Self, SynthesisError> {
44 // Check that the incoming instance has exactly 2 io
45 let W = AllocatedPoint::alloc(
46 cs.namespace(|| "allocate W"),
47 u.get()
48 .map_or(None, |u| Some(u.comm_W.comm.to_coordinates())),
49 )?;
50
51 let X0 = alloc_scalar_as_base::<G, _>(
52 cs.namespace(|| "allocate X[0]"),
53 u.get().map_or(None, |u| Some(u.X[0])),
54 )?;
55 let X1 = alloc_scalar_as_base::<G, _>(
56 cs.namespace(|| "allocate X[1]"),
57 u.get().map_or(None, |u| Some(u.X[1])),
58 )?;
59
60 Ok(AllocatedR1CSInstance { W, X0, X1 })
61 }
62
63 /// Absorb the provided instance in the RO
64 pub fn absorb_in_ro(&self, ro: &mut G::ROCircuit) {
65 ro.absorb(self.W.x.clone());
66 ro.absorb(self.W.y.clone());
67 ro.absorb(self.W.is_infinity.clone());
68 ro.absorb(self.X0.clone());
69 ro.absorb(self.X1.clone());
70 }
71}
72
73/// An Allocated Relaxed R1CS Instance
74pub struct AllocatedRelaxedR1CSInstance<G>
75where
76 G: Group,
77{
78 pub(crate) W: AllocatedPoint<G>,
79 pub(crate) E: AllocatedPoint<G>,
80 pub(crate) u: AllocatedNum<G::Base>,
81 pub(crate) X0: BigNat<G::Base>,
82 pub(crate) X1: BigNat<G::Base>,
83}
84
85impl<G> AllocatedRelaxedR1CSInstance<G>
86where
87 G: Group,
88{
89 /// Allocates the given RelaxedR1CSInstance as a witness of the circuit
90 pub fn alloc<CS: ConstraintSystem<<G as Group>::Base>>(
91 mut cs: CS,
92 inst: Option<RelaxedR1CSInstance<G>>,
93 limb_width: usize,
94 n_limbs: usize,
95 ) -> Result<Self, SynthesisError> {
96 let W = AllocatedPoint::alloc(
97 cs.namespace(|| "allocate W"),
98 inst
99 .get()
100 .map_or(None, |inst| Some(inst.comm_W.comm.to_coordinates())),
101 )?;
102
103 let E = AllocatedPoint::alloc(
104 cs.namespace(|| "allocate E"),
105 inst
106 .get()
107 .map_or(None, |inst| Some(inst.comm_E.comm.to_coordinates())),
108 )?;
109
110 // u << |G::Base| despite the fact that u is a scalar.
111 // So we parse all of its bytes as a G::Base element
112 let u = alloc_scalar_as_base::<G, _>(
113 cs.namespace(|| "allocate u"),
114 inst.get().map_or(None, |inst| Some(inst.u)),
115 )?;
116
117 // Allocate X0 and X1. If the input instance is None, then allocate default values 0.
118 let X0 = BigNat::alloc_from_nat(
119 cs.namespace(|| "allocate X[0]"),
120 || {
121 Ok(f_to_nat(
122 &inst.clone().map_or(G::Scalar::zero(), |inst| inst.X[0]),
123 ))
124 },
125 limb_width,
126 n_limbs,
127 )?;
128
129 let X1 = BigNat::alloc_from_nat(
130 cs.namespace(|| "allocate X[1]"),
131 || {
132 Ok(f_to_nat(
133 &inst.clone().map_or(G::Scalar::zero(), |inst| inst.X[1]),
134 ))
135 },
136 limb_width,
137 n_limbs,
138 )?;
139
140 Ok(AllocatedRelaxedR1CSInstance { W, E, u, X0, X1 })
141 }
142
143 /// Allocates the hardcoded default RelaxedR1CSInstance in the circuit.
144 /// W = E = 0, u = 1, X0 = X1 = 0
145 pub fn default<CS: ConstraintSystem<<G as Group>::Base>>(
146 mut cs: CS,
147 limb_width: usize,
148 n_limbs: usize,
149 ) -> Result<Self, SynthesisError> {
150 let W = AllocatedPoint::default(cs.namespace(|| "allocate W"))?;
151 let E = W.clone();
152
153 let u = W.x.clone(); // In the default case, W.x = u = 0
154
155 let X0 = BigNat::alloc_from_nat(
156 cs.namespace(|| "allocate x_default[0]"),
157 || Ok(f_to_nat(&G::Scalar::zero())),
158 limb_width,
159 n_limbs,
160 )?;
161
162 let X1 = BigNat::alloc_from_nat(
163 cs.namespace(|| "allocate x_default[1]"),
164 || Ok(f_to_nat(&G::Scalar::zero())),
165 limb_width,
166 n_limbs,
167 )?;
168
169 Ok(AllocatedRelaxedR1CSInstance { W, E, u, X0, X1 })
170 }
171
172 /// Allocates the R1CS Instance as a RelaxedR1CSInstance in the circuit.
173 /// E = 0, u = 1
174 pub fn from_r1cs_instance<CS: ConstraintSystem<<G as Group>::Base>>(
175 mut cs: CS,
176 inst: AllocatedR1CSInstance<G>,
177 limb_width: usize,
178 n_limbs: usize,
179 ) -> Result<Self, SynthesisError> {
180 let E = AllocatedPoint::default(cs.namespace(|| "allocate W"))?;
181
182 let u = alloc_one(cs.namespace(|| "one"))?;
183
184 let X0 = BigNat::from_num(
185 cs.namespace(|| "allocate X0 from relaxed r1cs"),
186 Num::from(inst.X0.clone()),
187 limb_width,
188 n_limbs,
189 )?;
190
191 let X1 = BigNat::from_num(
192 cs.namespace(|| "allocate X1 from relaxed r1cs"),
193 Num::from(inst.X1.clone()),
194 limb_width,
195 n_limbs,
196 )?;
197
198 Ok(AllocatedRelaxedR1CSInstance {
199 W: inst.W,
200 E,
201 u,
202 X0,
203 X1,
204 })
205 }
206
207 /// Absorb the provided instance in the RO
208 pub fn absorb_in_ro<CS: ConstraintSystem<<G as Group>::Base>>(
209 &self,
210 mut cs: CS,
211 ro: &mut G::ROCircuit,
212 ) -> Result<(), SynthesisError> {
213 ro.absorb(self.W.x.clone());
214 ro.absorb(self.W.y.clone());
215 ro.absorb(self.W.is_infinity.clone());
216 ro.absorb(self.E.x.clone());
217 ro.absorb(self.E.y.clone());
218 ro.absorb(self.E.is_infinity.clone());
219 ro.absorb(self.u.clone());
220
221 // Analyze X0 as limbs
222 let X0_bn = self
223 .X0
224 .as_limbs::<CS>()
225 .iter()
226 .enumerate()
227 .map(|(i, limb)| {
228 limb.as_allocated_num(cs.namespace(|| format!("convert limb {} of X_r[0] to num", i)))
229 })
230 .collect::<Result<Vec<AllocatedNum<G::Base>>, _>>()?;
231
232 // absorb each of the limbs of X[0]
233 for limb in X0_bn.into_iter() {
234 ro.absorb(limb);
235 }
236
237 // Analyze X1 as limbs
238 let X1_bn = self
239 .X1
240 .as_limbs::<CS>()
241 .iter()
242 .enumerate()
243 .map(|(i, limb)| {
244 limb.as_allocated_num(cs.namespace(|| format!("convert limb {} of X_r[1] to num", i)))
245 })
246 .collect::<Result<Vec<AllocatedNum<G::Base>>, _>>()?;
247
248 // absorb each of the limbs of X[1]
249 for limb in X1_bn.into_iter() {
250 ro.absorb(limb);
251 }
252
253 Ok(())
254 }
255
256 /// Folds self with a relaxed r1cs instance and returns the result
257 #[allow(clippy::too_many_arguments)]
258 pub fn fold_with_r1cs<CS: ConstraintSystem<<G as Group>::Base>>(
259 &self,
260 mut cs: CS,
261 params: AllocatedNum<G::Base>, // hash of R1CSShape of F'
262 u: AllocatedR1CSInstance<G>,
263 T: AllocatedPoint<G>,
264 ro_consts: ROConstantsCircuit<G>,
265 limb_width: usize,
266 n_limbs: usize,
267 ) -> Result<AllocatedRelaxedR1CSInstance<G>, SynthesisError> {
268 // Compute r:
269 let mut ro = G::ROCircuit::new(ro_consts, NUM_FE_FOR_RO);
270 ro.absorb(params);
271 self.absorb_in_ro(cs.namespace(|| "absorb running instance"), &mut ro)?;
272 u.absorb_in_ro(&mut ro);
273 ro.absorb(T.x.clone());
274 ro.absorb(T.y.clone());
275 ro.absorb(T.is_infinity.clone());
276 let r_bits = ro.squeeze(cs.namespace(|| "r bits"), NUM_CHALLENGE_BITS)?;
277 let r = le_bits_to_num(cs.namespace(|| "r"), r_bits.clone())?;
278
279 // W_fold = self.W + r * u.W
280 let rW = u.W.scalar_mul(cs.namespace(|| "r * u.W"), r_bits.clone())?;
281 let W_fold = self.W.add(cs.namespace(|| "self.W + r * u.W"), &rW)?;
282
283 // E_fold = self.E + r * T
284 let rT = T.scalar_mul(cs.namespace(|| "r * T"), r_bits)?;
285 let E_fold = self.E.add(cs.namespace(|| "self.E + r * T"), &rT)?;
286
287 // u_fold = u_r + r
288 let u_fold = AllocatedNum::alloc(cs.namespace(|| "u_fold"), || {
289 Ok(*self.u.get_value().get()? + r.get_value().get()?)
290 })?;
291 cs.enforce(
292 || "Check u_fold",
293 |lc| lc,
294 |lc| lc,
295 |lc| lc + u_fold.get_variable() - self.u.get_variable() - r.get_variable(),
296 );
297
298 // Fold the IO:
299 // Analyze r into limbs
300 let r_bn = BigNat::from_num(
301 cs.namespace(|| "allocate r_bn"),
302 Num::from(r.clone()),
303 limb_width,
304 n_limbs,
305 )?;
306
307 // Allocate the order of the non-native field as a constant
308 let m_bn = alloc_bignat_constant(
309 cs.namespace(|| "alloc m"),
310 &G::get_curve_params().2,
311 limb_width,
312 n_limbs,
313 )?;
314
315 // Analyze X0 to bignat
316 let X0_bn = BigNat::from_num(
317 cs.namespace(|| "allocate X0_bn"),
318 Num::from(u.X0.clone()),
319 limb_width,
320 n_limbs,
321 )?;
322
323 // Fold self.X[0] + r * X[0]
324 let (_, r_0) = X0_bn.mult_mod(cs.namespace(|| "r*X[0]"), &r_bn, &m_bn)?;
325 // add X_r[0]
326 let r_new_0 = self.X0.add::<CS>(&r_0)?;
327 // Now reduce
328 let X0_fold = r_new_0.red_mod(cs.namespace(|| "reduce folded X[0]"), &m_bn)?;
329
330 // Analyze X1 to bignat
331 let X1_bn = BigNat::from_num(
332 cs.namespace(|| "allocate X1_bn"),
333 Num::from(u.X1.clone()),
334 limb_width,
335 n_limbs,
336 )?;
337
338 // Fold self.X[1] + r * X[1]
339 let (_, r_1) = X1_bn.mult_mod(cs.namespace(|| "r*X[1]"), &r_bn, &m_bn)?;
340 // add X_r[1]
341 let r_new_1 = self.X1.add::<CS>(&r_1)?;
342 // Now reduce
343 let X1_fold = r_new_1.red_mod(cs.namespace(|| "reduce folded X[1]"), &m_bn)?;
344
345 Ok(Self {
346 W: W_fold,
347 E: E_fold,
348 u: u_fold,
349 X0: X0_fold,
350 X1: X1_fold,
351 })
352 }
353
354 /// If the condition is true then returns this otherwise it returns the other
355 pub fn conditionally_select<CS: ConstraintSystem<<G as Group>::Base>>(
356 &self,
357 mut cs: CS,
358 other: AllocatedRelaxedR1CSInstance<G>,
359 condition: &Boolean,
360 ) -> Result<AllocatedRelaxedR1CSInstance<G>, SynthesisError> {
361 let W = AllocatedPoint::conditionally_select(
362 cs.namespace(|| "W = cond ? self.W : other.W"),
363 &self.W,
364 &other.W,
365 condition,
366 )?;
367
368 let E = AllocatedPoint::conditionally_select(
369 cs.namespace(|| "E = cond ? self.E : other.E"),
370 &self.E,
371 &other.E,
372 condition,
373 )?;
374
375 let u = conditionally_select(
376 cs.namespace(|| "u = cond ? self.u : other.u"),
377 &self.u,
378 &other.u,
379 condition,
380 )?;
381
382 let X0 = conditionally_select_bignat(
383 cs.namespace(|| "X[0] = cond ? self.X[0] : other.X[0]"),
384 &self.X0,
385 &other.X0,
386 condition,
387 )?;
388
389 let X1 = conditionally_select_bignat(
390 cs.namespace(|| "X[1] = cond ? self.X[1] : other.X[1]"),
391 &self.X1,
392 &other.X1,
393 condition,
394 )?;
395
396 Ok(AllocatedRelaxedR1CSInstance { W, E, u, X0, X1 })
397 }
398}