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