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 || Ok(f_to_nat(&inst.map_or(G::Scalar::ZERO, |inst| inst.X[0]))),
108 limb_width,
109 n_limbs,
110 )?;
111
112 let X1 = BigNat::alloc_from_nat(
113 cs.namespace(|| "allocate X[1]"),
114 || Ok(f_to_nat(&inst.map_or(G::Scalar::ZERO, |inst| inst.X[1]))),
115 limb_width,
116 n_limbs,
117 )?;
118
119 Ok(AllocatedRelaxedR1CSInstance { W, E, u, X0, X1 })
120 }
121
122 /// Allocates the hardcoded default RelaxedR1CSInstance in the circuit.
123 /// W = E = 0, u = 1, X0 = X1 = 0
124 pub fn default<CS: ConstraintSystem<<G as Group>::Base>>(
125 mut cs: CS,
126 limb_width: usize,
127 n_limbs: usize,
128 ) -> Result<Self, SynthesisError> {
129 let W = AllocatedPoint::default(cs.namespace(|| "allocate W"))?;
130 let E = W.clone();
131
132 let u = W.x.clone(); // In the default case, W.x = u = 0
133
134 let X0 = BigNat::alloc_from_nat(
135 cs.namespace(|| "allocate x_default[0]"),
136 || Ok(f_to_nat(&G::Scalar::ZERO)),
137 limb_width,
138 n_limbs,
139 )?;
140
141 let X1 = BigNat::alloc_from_nat(
142 cs.namespace(|| "allocate x_default[1]"),
143 || Ok(f_to_nat(&G::Scalar::ZERO)),
144 limb_width,
145 n_limbs,
146 )?;
147
148 Ok(AllocatedRelaxedR1CSInstance { W, E, u, X0, X1 })
149 }
150
151 /// Allocates the R1CS Instance as a RelaxedR1CSInstance in the circuit.
152 /// E = 0, u = 1
153 pub fn from_r1cs_instance<CS: ConstraintSystem<<G as Group>::Base>>(
154 mut cs: CS,
155 inst: AllocatedR1CSInstance<G>,
156 limb_width: usize,
157 n_limbs: usize,
158 ) -> Result<Self, SynthesisError> {
159 let E = AllocatedPoint::default(cs.namespace(|| "allocate W"))?;
160
161 let u = alloc_one(cs.namespace(|| "one"))?;
162
163 let X0 = BigNat::from_num(
164 cs.namespace(|| "allocate X0 from relaxed r1cs"),
165 &Num::from(inst.X0),
166 limb_width,
167 n_limbs,
168 )?;
169
170 let X1 = BigNat::from_num(
171 cs.namespace(|| "allocate X1 from relaxed r1cs"),
172 &Num::from(inst.X1),
173 limb_width,
174 n_limbs,
175 )?;
176
177 Ok(AllocatedRelaxedR1CSInstance {
178 W: inst.W,
179 E,
180 u,
181 X0,
182 X1,
183 })
184 }
185
186 /// Absorb the provided instance in the RO
187 pub fn absorb_in_ro<CS: ConstraintSystem<<G as Group>::Base>>(
188 &self,
189 mut cs: CS,
190 ro: &mut G::ROCircuit,
191 ) -> Result<(), SynthesisError> {
192 ro.absorb(self.W.x.clone());
193 ro.absorb(self.W.y.clone());
194 ro.absorb(self.W.is_infinity.clone());
195 ro.absorb(self.E.x.clone());
196 ro.absorb(self.E.y.clone());
197 ro.absorb(self.E.is_infinity.clone());
198 ro.absorb(self.u.clone());
199
200 // Analyze X0 as limbs
201 let X0_bn = self
202 .X0
203 .as_limbs()
204 .iter()
205 .enumerate()
206 .map(|(i, limb)| {
207 limb.as_allocated_num(cs.namespace(|| format!("convert limb {i} of X_r[0] to num")))
208 })
209 .collect::<Result<Vec<AllocatedNum<G::Base>>, _>>()?;
210
211 // absorb each of the limbs of X[0]
212 for limb in X0_bn.into_iter() {
213 ro.absorb(limb);
214 }
215
216 // Analyze X1 as limbs
217 let X1_bn = self
218 .X1
219 .as_limbs()
220 .iter()
221 .enumerate()
222 .map(|(i, limb)| {
223 limb.as_allocated_num(cs.namespace(|| format!("convert limb {i} of X_r[1] to num")))
224 })
225 .collect::<Result<Vec<AllocatedNum<G::Base>>, _>>()?;
226
227 // absorb each of the limbs of X[1]
228 for limb in X1_bn.into_iter() {
229 ro.absorb(limb);
230 }
231
232 Ok(())
233 }
234
235 /// Folds self with a relaxed r1cs instance and returns the result
236 #[allow(clippy::too_many_arguments)]
237 pub fn fold_with_r1cs<CS: ConstraintSystem<<G as Group>::Base>>(
238 &self,
239 mut cs: CS,
240 params: AllocatedNum<G::Base>, // hash of R1CSShape of F'
241 u: &AllocatedR1CSInstance<G>,
242 T: &AllocatedPoint<G>,
243 ro_consts: ROConstantsCircuit<G>,
244 limb_width: usize,
245 n_limbs: usize,
246 ) -> Result<AllocatedRelaxedR1CSInstance<G>, SynthesisError> {
247 // Compute r:
248 let mut ro = G::ROCircuit::new(ro_consts, NUM_FE_FOR_RO);
249 ro.absorb(params);
250 self.absorb_in_ro(cs.namespace(|| "absorb running instance"), &mut ro)?;
251 u.absorb_in_ro(&mut ro);
252 ro.absorb(T.x.clone());
253 ro.absorb(T.y.clone());
254 ro.absorb(T.is_infinity.clone());
255 let r_bits = ro.squeeze(cs.namespace(|| "r bits"), NUM_CHALLENGE_BITS)?;
256 let r = le_bits_to_num(cs.namespace(|| "r"), &r_bits)?;
257
258 // W_fold = self.W + r * u.W
259 let rW = u.W.scalar_mul(cs.namespace(|| "r * u.W"), &r_bits)?;
260 let W_fold = self.W.add(cs.namespace(|| "self.W + r * u.W"), &rW)?;
261
262 // E_fold = self.E + r * T
263 let rT = T.scalar_mul(cs.namespace(|| "r * T"), &r_bits)?;
264 let E_fold = self.E.add(cs.namespace(|| "self.E + r * T"), &rT)?;
265
266 // u_fold = u_r + r
267 let u_fold = AllocatedNum::alloc(cs.namespace(|| "u_fold"), || {
268 Ok(*self.u.get_value().get()? + r.get_value().get()?)
269 })?;
270 cs.enforce(
271 || "Check u_fold",
272 |lc| lc,
273 |lc| lc,
274 |lc| lc + u_fold.get_variable() - self.u.get_variable() - r.get_variable(),
275 );
276
277 // Fold the IO:
278 // Analyze r into limbs
279 let r_bn = BigNat::from_num(
280 cs.namespace(|| "allocate r_bn"),
281 &Num::from(r),
282 limb_width,
283 n_limbs,
284 )?;
285
286 // Allocate the order of the non-native field as a constant
287 let m_bn = alloc_bignat_constant(
288 cs.namespace(|| "alloc m"),
289 &G::get_curve_params().2,
290 limb_width,
291 n_limbs,
292 )?;
293
294 // Analyze X0 to bignat
295 let X0_bn = BigNat::from_num(
296 cs.namespace(|| "allocate X0_bn"),
297 &Num::from(u.X0.clone()),
298 limb_width,
299 n_limbs,
300 )?;
301
302 // Fold self.X[0] + r * X[0]
303 let (_, r_0) = X0_bn.mult_mod(cs.namespace(|| "r*X[0]"), &r_bn, &m_bn)?;
304 // add X_r[0]
305 let r_new_0 = self.X0.add(&r_0)?;
306 // Now reduce
307 let X0_fold = r_new_0.red_mod(cs.namespace(|| "reduce folded X[0]"), &m_bn)?;
308
309 // Analyze X1 to bignat
310 let X1_bn = BigNat::from_num(
311 cs.namespace(|| "allocate X1_bn"),
312 &Num::from(u.X1.clone()),
313 limb_width,
314 n_limbs,
315 )?;
316
317 // Fold self.X[1] + r * X[1]
318 let (_, r_1) = X1_bn.mult_mod(cs.namespace(|| "r*X[1]"), &r_bn, &m_bn)?;
319 // add X_r[1]
320 let r_new_1 = self.X1.add(&r_1)?;
321 // Now reduce
322 let X1_fold = r_new_1.red_mod(cs.namespace(|| "reduce folded X[1]"), &m_bn)?;
323
324 Ok(Self {
325 W: W_fold,
326 E: E_fold,
327 u: u_fold,
328 X0: X0_fold,
329 X1: X1_fold,
330 })
331 }
332
333 /// If the condition is true then returns this otherwise it returns the other
334 pub fn conditionally_select<CS: ConstraintSystem<<G as Group>::Base>>(
335 &self,
336 mut cs: CS,
337 other: &AllocatedRelaxedR1CSInstance<G>,
338 condition: &Boolean,
339 ) -> Result<AllocatedRelaxedR1CSInstance<G>, SynthesisError> {
340 let W = AllocatedPoint::conditionally_select(
341 cs.namespace(|| "W = cond ? self.W : other.W"),
342 &self.W,
343 &other.W,
344 condition,
345 )?;
346
347 let E = AllocatedPoint::conditionally_select(
348 cs.namespace(|| "E = cond ? self.E : other.E"),
349 &self.E,
350 &other.E,
351 condition,
352 )?;
353
354 let u = conditionally_select(
355 cs.namespace(|| "u = cond ? self.u : other.u"),
356 &self.u,
357 &other.u,
358 condition,
359 )?;
360
361 let X0 = conditionally_select_bignat(
362 cs.namespace(|| "X[0] = cond ? self.X[0] : other.X[0]"),
363 &self.X0,
364 &other.X0,
365 condition,
366 )?;
367
368 let X1 = conditionally_select_bignat(
369 cs.namespace(|| "X[1] = cond ? self.X[1] : other.X[1]"),
370 &self.X1,
371 &other.X1,
372 condition,
373 )?;
374
375 Ok(AllocatedRelaxedR1CSInstance { W, E, u, X0, X1 })
376 }
377}