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