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