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 hash: AllocatedNum<G::Base>, // hash of (params, running_instance, i, z0, zi)
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(hash);
229 u.absorb_in_ro(&mut ro);
230 ro.absorb(T.x.clone());
231 ro.absorb(T.y.clone());
232 ro.absorb(T.is_infinity.clone());
233 let r_bits = ro.get_challenge(cs.namespace(|| "r bits"))?;
234 let r = le_bits_to_num(cs.namespace(|| "r"), r_bits.clone())?;
235
236 // W_fold = self.W + r * u.W
237 let rW = u.W.scalar_mul(cs.namespace(|| "r * u.W"), r_bits.clone())?;
238 let W_fold = self.W.add(cs.namespace(|| "self.W + r * u.W"), &rW)?;
239
240 // E_fold = self.E + r * T
241 let rT = T.scalar_mul(cs.namespace(|| "r * T"), r_bits)?;
242 let E_fold = self.E.add(cs.namespace(|| "self.E + r * T"), &rT)?;
243
244 // u_fold = u_r + r
245 let u_fold = AllocatedNum::alloc(cs.namespace(|| "u_fold"), || {
246 Ok(*self.u.get_value().get()? + r.get_value().get()?)
247 })?;
248 cs.enforce(
249 || "Check u_fold",
250 |lc| lc,
251 |lc| lc,
252 |lc| lc + u_fold.get_variable() - self.u.get_variable() - r.get_variable(),
253 );
254
255 // Fold the IO:
256 // Analyze r into limbs
257 let r_bn = BigNat::from_num(
258 cs.namespace(|| "allocate r_bn"),
259 Num::from(r.clone()),
260 limb_width,
261 n_limbs,
262 )?;
263
264 // Allocate the order of the non-native field as a constant
265 let m_bn = alloc_bignat_constant(
266 cs.namespace(|| "alloc m"),
267 &G::get_order(),
268 limb_width,
269 n_limbs,
270 )?;
271
272 // Analyze X0 to bignat
273 let X0_bn = BigNat::from_num(
274 cs.namespace(|| "allocate X0_bn"),
275 Num::from(u.X0.clone()),
276 limb_width,
277 n_limbs,
278 )?;
279
280 // Fold self.X[0] + r * X[0]
281 let (_, r_0) = X0_bn.mult_mod(cs.namespace(|| "r*X[0]"), &r_bn, &m_bn)?;
282 // add X_r[0]
283 let r_new_0 = self.X0.add::<CS>(&r_0)?;
284 // Now reduce
285 let X0_fold = r_new_0.red_mod(cs.namespace(|| "reduce folded X[0]"), &m_bn)?;
286
287 // Analyze X1 to bignat
288 let X1_bn = BigNat::from_num(
289 cs.namespace(|| "allocate X1_bn"),
290 Num::from(u.X1.clone()),
291 limb_width,
292 n_limbs,
293 )?;
294
295 // Fold self.X[1] + r * X[1]
296 let (_, r_1) = X1_bn.mult_mod(cs.namespace(|| "r*X[1]"), &r_bn, &m_bn)?;
297 // add X_r[1]
298 let r_new_1 = self.X1.add::<CS>(&r_1)?;
299 // Now reduce
300 let X1_fold = r_new_1.red_mod(cs.namespace(|| "reduce folded X[1]"), &m_bn)?;
301
302 Ok(Self {
303 W: W_fold,
304 E: E_fold,
305 u: u_fold,
306 X0: X0_fold,
307 X1: X1_fold,
308 })
309 }
310
311 /// If the condition is true then returns this otherwise it returns the other
312 pub fn conditionally_select<CS: ConstraintSystem<<G as Group>::Base>>(
313 &self,
314 mut cs: CS,
315 other: AllocatedRelaxedR1CSInstance<G>,
316 condition: &Boolean,
317 ) -> Result<AllocatedRelaxedR1CSInstance<G>, SynthesisError> {
318 let W = AllocatedPoint::conditionally_select(
319 cs.namespace(|| "W = cond ? self.W : other.W"),
320 &self.W,
321 &other.W,
322 condition,
323 )?;
324
325 let E = AllocatedPoint::conditionally_select(
326 cs.namespace(|| "E = cond ? self.E : other.E"),
327 &self.E,
328 &other.E,
329 condition,
330 )?;
331
332 let u = conditionally_select(
333 cs.namespace(|| "u = cond ? self.u : other.u"),
334 &self.u,
335 &other.u,
336 condition,
337 )?;
338
339 let X0 = conditionally_select_bignat(
340 cs.namespace(|| "X[0] = cond ? self.X[0] : other.X[0]"),
341 &self.X0,
342 &other.X0,
343 condition,
344 )?;
345
346 let X1 = conditionally_select_bignat(
347 cs.namespace(|| "X[1] = cond ? self.X[1] : other.X[1]"),
348 &self.X1,
349 &other.X1,
350 condition,
351 )?;
352
353 Ok(AllocatedRelaxedR1CSInstance { W, E, u, X0, X1 })
354 }
355}