1use crate::{
9 constants::GATE_WIDTH,
10 gadgets::utils::next_multiple,
11 Circuit,
12 CircuitError::{self, ParameterError},
13 PlonkCircuit, Variable,
14};
15use ark_ff::PrimeField;
16use ark_std::{format, string::ToString, vec, vec::Vec};
17use num_bigint::BigUint;
18
19macro_rules! to_big_int {
20 ($x:expr) => {
21 ($x).into_bigint().into()
22 };
23}
24
25#[derive(Debug, Clone, Eq, PartialEq, Default, Copy)]
26pub struct FpElem<F: PrimeField> {
34 p: (F, F),
35 m: usize,
36 two_power_m: F,
37}
38
39impl<F> FpElem<F>
40where
41 F: PrimeField,
42{
43 pub fn new(p: &F, m: usize, two_power_m: Option<F>) -> Result<Self, CircuitError> {
46 if m > F::MODULUS_BIT_SIZE as usize / 2 {
47 return Err(ParameterError(format!(
48 "field split parameter ({}) larger than half of the field size ({}) in bits",
49 m,
50 F::MODULUS_BIT_SIZE / 2
51 )));
52 }
53 let two_power_m = match two_power_m {
54 Some(p) => p,
55 None => F::from(2u8).pow([m as u64]),
56 };
57 let (p1, p0) = div_rem(p, &two_power_m);
58 Ok(Self {
59 p: (p0, p1),
60 m,
61 two_power_m,
62 })
63 }
64
65 pub fn field_elem(&self) -> F {
67 self.p.0 + self.two_power_m * self.p.1
68 }
69
70 pub fn components(&self) -> (F, F) {
72 self.p
73 }
74
75 pub fn param_m(&self) -> usize {
77 self.m
78 }
79
80 pub fn two_power_m(&self) -> F {
82 self.two_power_m
83 }
84}
85
86#[derive(Debug, Clone, Eq, PartialEq, Default, Copy)]
87pub struct FpElemVar<F: PrimeField> {
92 vars: (Variable, Variable),
93 m: usize,
94 two_power_m: F,
95}
96
97impl<F: PrimeField> FpElemVar<F> {
98 pub fn new_unchecked(
104 cs: &mut PlonkCircuit<F>,
105 var: Variable,
106 m: usize,
107 two_power_m: Option<F>,
108 ) -> Result<Self, CircuitError> {
109 let fp_elem = FpElem::new(&cs.witness(var)?, m, two_power_m)?;
110 let var0 = cs.create_variable(fp_elem.p.0)?;
111 let var1 = cs.create_variable(fp_elem.p.1)?;
112 cs.lc_gate(
113 &[var0, var1, cs.zero(), cs.zero(), var],
114 &[F::one(), fp_elem.two_power_m, F::zero(), F::zero()],
115 )?;
116
117 Ok(Self {
118 vars: (var0, var1),
119 m,
120 two_power_m: fp_elem.two_power_m,
121 })
122 }
123
124 pub fn convert_to_var(&self, cs: &mut PlonkCircuit<F>) -> Result<Variable, CircuitError> {
127 cs.lc(
128 &[self.vars.0, self.vars.1, cs.zero(), cs.zero()],
129 &[F::one(), self.two_power_m, F::zero(), F::zero()],
130 )
131 }
132
133 pub fn new_from_field_element(
137 cs: &mut PlonkCircuit<F>,
138 f: &F,
139 m: usize,
140 two_power_m: Option<F>,
141 ) -> Result<Self, CircuitError> {
142 let fp_elem = FpElem::new(f, m, two_power_m)?;
143 Self::new_from_fp_elem(cs, &fp_elem, m, two_power_m)
144 }
145
146 pub fn new_from_fp_elem(
150 cs: &mut PlonkCircuit<F>,
151 fp_elem: &FpElem<F>,
152 m: usize,
153 two_power_m: Option<F>,
154 ) -> Result<Self, CircuitError> {
155 let var0 = cs.create_variable(fp_elem.p.0)?;
156 let var1 = cs.create_variable(fp_elem.p.1)?;
157
158 cs.range_gate_with_lookup(var0, m)?;
159 cs.range_gate_with_lookup(var1, m)?;
160
161 Ok(Self {
162 vars: (var0, var1),
163 m,
164 two_power_m: match two_power_m {
165 Some(p) => p,
166 None => F::from(2u8).pow([m as u64]),
167 },
168 })
169 }
170
171 pub fn witness_fp_elem(&self, cs: &PlonkCircuit<F>) -> Result<FpElem<F>, CircuitError> {
173 Ok(FpElem {
174 p: (cs.witness(self.vars.0)?, cs.witness(self.vars.1)?),
175 m: self.m,
176 two_power_m: self.two_power_m,
177 })
178 }
179
180 pub fn witness(&self, cs: &PlonkCircuit<F>) -> Result<F, CircuitError> {
182 Ok(cs.witness(self.vars.0)? + cs.witness(self.vars.1)? * self.two_power_m)
183 }
184
185 pub fn components(&self) -> (Variable, Variable) {
187 self.vars
188 }
189
190 pub fn param_m(&self) -> usize {
192 self.m
193 }
194
195 pub fn two_power_m(&self) -> F {
197 self.two_power_m
198 }
199
200 pub fn zero(cs: &PlonkCircuit<F>, m: usize, two_power_m: Option<F>) -> Self {
202 FpElemVar {
203 vars: (cs.zero(), cs.zero()),
204 m,
205 two_power_m: match two_power_m {
206 Some(p) => p,
207 None => F::from(2u8).pow([m as u64]),
208 },
209 }
210 }
211
212 pub fn one(cs: &PlonkCircuit<F>, m: usize, two_power_m: Option<F>) -> Self {
214 FpElemVar {
215 vars: (cs.one(), cs.zero()),
216 m,
217 two_power_m: match two_power_m {
218 Some(p) => p,
219 None => F::from(2u8).pow([m as u64]),
220 },
221 }
222 }
223
224 pub fn enforce_equal(
226 &self,
227 circuit: &mut PlonkCircuit<F>,
228 other: &Self,
229 ) -> Result<(), CircuitError> {
230 if self.m != other.m || self.two_power_m != other.two_power_m {
231 return Err(CircuitError::ParameterError(
232 "m or two_power_m do not match".to_string(),
233 ));
234 }
235 circuit.enforce_equal(self.components().0, other.components().0)?;
236 circuit.enforce_equal(self.components().1, other.components().1)
237 }
238}
239
240impl<F: PrimeField> PlonkCircuit<F> {
241 fn mod_add_internal(
249 &mut self,
250 vars: &[Variable],
251 p: F,
252 l_p: usize,
253 ) -> Result<Variable, CircuitError> {
254 let range_bit_len = self.range_bit_len()?;
255 let range_size = self.range_size()?;
256 let mut sum_x = F::zero();
257 for &var in vars.iter() {
258 sum_x += self.witness(var)?;
259 }
260 let (z, y) = div_rem(&sum_x, &p);
262 let z_range = F::from(range_size as u32);
263 if z >= z_range {
264 return Err(ParameterError(format!(
265 "z = {z} is out of range, the sum of variable values = {sum_x} might be too large for modulus = {p}",
266 )));
267 }
268
269 let z_var = self.create_variable(z)?;
271 self.range_gate_with_lookup(z_var, range_bit_len)?;
273 let y_var = self.create_variable(y)?;
274 self.range_gate_with_lookup(y_var, range_bit_len * l_p)?;
276
277 let mut padded = vec![z_var];
279 padded.extend(vars);
280 let rate = GATE_WIDTH - 1; let padded_len = next_multiple(padded.len() - 1, rate)? + 1;
282 padded.resize(padded_len, self.zero());
283
284 let coeffs = [F::one(), F::one(), F::one(), F::one()];
285 let mut accum = padded[padded_len - 1];
286 for i in 1..padded_len / rate {
287 accum = self.lc(
288 &[
289 accum,
290 padded[padded_len - 1 - rate * i + 2],
291 padded[padded_len - 1 - rate * i + 1],
292 padded[padded_len - 1 - rate * i],
293 ],
294 &coeffs,
295 )?;
296 }
297 let coeffs = [F::one(), F::one(), F::one(), p.neg()];
299 let wires = [accum, padded[2], padded[1], padded[0], y_var];
300 self.lc_gate(&wires, &coeffs)?;
301
302 Ok(y_var)
303 }
304
305 pub fn mod_add(
308 &mut self,
309 x: &FpElemVar<F>,
310 y: &FpElemVar<F>,
311 p: &FpElem<F>,
312 ) -> Result<FpElemVar<F>, CircuitError> {
313 let range_bit_len = self.range_bit_len()?;
314 self.check_var_bound(x.vars.0)?;
315 self.check_var_bound(x.vars.1)?;
316 self.check_var_bound(y.vars.0)?;
317 self.check_var_bound(y.vars.1)?;
318
319 if x.m != p.m || y.m != p.m {
320 return Err(ParameterError(format!(
321 "field elements splitting parameters do not match: x.m = {}, y.m = {}, p.m = {}",
322 x.m, y.m, p.m
323 )));
324 }
325 if x.two_power_m != p.two_power_m || y.two_power_m != p.two_power_m {
326 return Err(ParameterError(format!(
327 "field elements splitting parameters do not match: x.2^m = {}, y.2^m = {}, p.2^m = {}",
328 x.two_power_m, y.two_power_m, p.two_power_m
329 ))
330 );
331 }
332 if p.m % range_bit_len != 0 {
333 return Err(ParameterError(format!(
334 "splitting parameter m = {} is not a multiple of range_bit_len",
335 p.m
336 )));
337 }
338
339 let x_var = x.convert_to_var(self)?;
340 let y_var = y.convert_to_var(self)?;
341
342 let num_range_blocks = self.num_range_blocks()?;
343 let res = self.mod_add_internal(&[x_var, y_var], p.field_elem(), num_range_blocks)?;
344
345 FpElemVar::new_unchecked(self, res, x.m, Some(p.two_power_m))
346 }
347
348 pub fn mod_add_constant(
356 &mut self,
357 x: &FpElemVar<F>,
358 y: &FpElem<F>,
359 p: &FpElem<F>,
360 ) -> Result<FpElemVar<F>, CircuitError> {
361 let range_bit_len = self.range_bit_len()?;
362 let range_size = self.range_size()?;
363 self.check_var_bound(x.vars.0)?;
364 self.check_var_bound(x.vars.1)?;
365
366 if x.m != p.m || y.m != p.m {
367 return Err(ParameterError(format!(
368 "field elements splitting parameters do not match: x.m = {}, y.m = {}, p.m = {}",
369 x.m, y.m, p.m
370 )));
371 }
372 if x.two_power_m != p.two_power_m || y.two_power_m != p.two_power_m {
373 return Err(ParameterError(format!(
374 "field elements splitting parameters do not match: x.2^m = {}, y.2^m = {}, p.2^m = {}",
375 x.two_power_m, y.two_power_m, p.two_power_m
376 ))
377 );
378 }
379 if p.m % range_bit_len != 0 {
380 return Err(ParameterError(format!(
381 "splitting parameter m = {} is not a multiple of range_bit_len",
382 p.m
383 )));
384 }
385 let x_var = x.convert_to_var(self)?;
389 let y_f = y.field_elem();
390 let p_f = p.field_elem();
391
392 let sum = self.witness(x_var)? + y_f;
394 let (divisor, remainder) = div_rem(&sum, &p_f);
395
396 let divisor_range = F::from(range_size as u32);
397 if divisor >= divisor_range {
398 return Err(ParameterError(format!(
399 "divisor = {divisor} is out of range, the sum of variable values = {sum} might be too large for modulus = {p_f}",
400 ))
401 );
402 }
403
404 let divisor_var = self.create_variable(divisor)?;
418 self.range_gate_with_lookup(divisor_var, range_bit_len)?;
420
421 let remainder_var = self.create_variable(remainder)?;
423 let num_range_blocks = self.num_range_blocks()?;
424 self.range_gate_with_lookup(remainder_var, range_bit_len * num_range_blocks)?;
425
426 let wires = [x_var, remainder_var, divisor_var, self.zero(), self.zero()];
428 let q_lc = [F::one(), -F::one(), -p_f, F::zero()];
429 let q_mul = [F::zero(), F::zero()];
430 let q_o = F::zero();
431 let q_c = y_f;
432
433 self.quad_poly_gate(&wires, &q_lc, &q_mul, q_o, q_c)?;
434
435 FpElemVar::new_unchecked(self, remainder_var, x.m, Some(p.two_power_m))
436 }
437
438 pub fn mod_add_vec(
441 &mut self,
442 x: &[FpElemVar<F>],
443 p: &FpElem<F>,
444 ) -> Result<FpElemVar<F>, CircuitError> {
445 let range_bit_len = self.range_bit_len()?;
446 for e in x {
447 if e.m != p.m {
448 return Err(ParameterError(format!(
449 "field elements splitting parameters do not match: x.m = {}, p.m = {}",
450 e.m, p.m
451 )));
452 }
453
454 if e.two_power_m != p.two_power_m {
455 return Err(ParameterError(format!(
456 "field elements splitting parameters do not match: x.2^m = {}, p.2^m = {}",
457 e.two_power_m, p.two_power_m
458 )));
459 }
460 }
461
462 if p.m % range_bit_len != 0 {
463 return Err(ParameterError(format!(
464 "splitting parameter m = {} is not a multiple of range_bit_len",
465 p.m
466 )));
467 }
468
469 let x_vars: Vec<Variable> = x
470 .iter()
471 .map(|y| y.convert_to_var(self))
472 .collect::<Result<Vec<Variable>, _>>()?;
473
474 let num_range_blocks = self.num_range_blocks()?;
475 let res = self.mod_add_internal(x_vars.as_ref(), p.field_elem(), num_range_blocks)?;
476
477 FpElemVar::new_unchecked(self, res, p.m, Some(p.two_power_m))
478 }
479
480 #[allow(clippy::many_single_char_names)]
483 pub fn mod_mul(
484 &mut self,
485 x: &FpElemVar<F>,
486 y: &FpElemVar<F>,
487 p: &FpElem<F>,
488 ) -> Result<FpElemVar<F>, CircuitError> {
489 let range_bit_len = self.range_bit_len()?;
490 if x.m != p.m || y.m != p.m {
491 return Err(ParameterError(format!(
492 "field elements splitting parameters do not match: x.m = {}, y.m = {}, p.m = {}",
493 x.m, y.m, p.m
494 )));
495 }
496 if x.two_power_m != p.two_power_m || y.two_power_m != p.two_power_m {
497 return Err(ParameterError(format!(
498 "field elements splitting parameters do not match: x.2^m = {}, y.2^m = {}, p.2^m = {}",
499 x.two_power_m, y.two_power_m, p.two_power_m
500 )));
501 }
502 if p.m % range_bit_len != 0 {
503 return Err(ParameterError(format!(
504 "splitting parameter m = {} is not a multiple of range_bit_len",
505 p.m
506 )));
507 }
508
509 let two_power_m_int: BigUint = to_big_int!(p.two_power_m);
513 let x0_int: BigUint = to_big_int!(self.witness(x.vars.0)?);
514 let x1_int: BigUint = to_big_int!(self.witness(x.vars.1)?);
515 let y0_int: BigUint = to_big_int!(self.witness(y.vars.0)?);
516 let y1_int: BigUint = to_big_int!(self.witness(y.vars.1)?);
517 let p0_int: BigUint = to_big_int!(p.p.0);
518 let p1_int: BigUint = to_big_int!(p.p.1);
519 let x_int = &x0_int + &two_power_m_int * &x1_int;
520 let y_int = &y0_int + &two_power_m_int * &y1_int;
521 let p_int = &p0_int + &two_power_m_int * &p1_int;
522
523 let xy_int = &x_int * &y_int;
525 let w_int = &xy_int / &p_int;
526 let z_int = &xy_int - (&w_int * &p_int);
527 let w = FpElem::new(&F::from(w_int), p.m, Some(p.two_power_m))?;
528 let w0_int: BigUint = to_big_int!(w.p.0);
529 let w1_int: BigUint = to_big_int!(w.p.1);
530 let z = FpElem::new(&F::from(z_int), p.m, Some(p.two_power_m))?;
531 let z0_int = to_big_int!(z.p.0);
532 let z1_int = to_big_int!(z.p.1);
533
534 let x0y0_int = &x0_int * &y0_int;
551 let z0_plus_p0w0_int = &z0_int + &p0_int * &w0_int;
552 let c0_int = if z0_plus_p0w0_int >= x0y0_int {
553 let carry0_int = (&z0_plus_p0w0_int - &x0y0_int) / &two_power_m_int;
554 &two_power_m_int + carry0_int
555 } else {
556 let carry0_int = (&x0y0_int - z0_plus_p0w0_int) / &two_power_m_int;
557 &two_power_m_int - carry0_int
558 };
559
560 let a_int = &x0_int * &y1_int + &x1_int * &y0_int + &two_power_m_int;
564 let b_int = &z1_int + &p0_int * &w1_int + &p1_int * &w0_int + &c0_int;
565 let c1_int = if b_int >= a_int {
566 let carry1_int = (b_int - a_int) / &two_power_m_int;
567 &two_power_m_int + &two_power_m_int + carry1_int
568 } else {
569 let carry1_int = (a_int - b_int) / &two_power_m_int;
570 &two_power_m_int + &two_power_m_int - carry1_int
571 };
572
573 let w0_var = self.create_variable(F::from(w0_int))?;
585 let w1_var = self.create_variable(F::from(w1_int))?;
586 let z0_var = self.create_variable(F::from(z0_int))?;
587 let z1_var = self.create_variable(F::from(z1_int))?;
588 let c0_var = self.create_variable(F::from(c0_int))?;
589 let c1_var = self.create_variable(F::from(c1_int))?;
590 self.range_gate_with_lookup(w0_var, p.m)?;
591 self.range_gate_with_lookup(w1_var, p.m)?;
592 self.range_gate_with_lookup(z0_var, p.m)?;
593 self.range_gate_with_lookup(z1_var, p.m)?;
594 self.range_gate_with_lookup(c0_var, p.m + range_bit_len)?;
595 self.range_gate_with_lookup(c1_var, p.m + range_bit_len)?;
596
597 let wires = [x.vars.0, y.vars.0, w0_var, c0_var, z0_var];
604 let q_lin = [F::zero(), F::zero(), -p.p.0, p.two_power_m];
605 let q_mul = [F::one(), F::zero()];
606 let q_o = F::one();
607 let q_c = -p.two_power_m.square();
608 self.quad_poly_gate(&wires, &q_lin, &q_mul, q_o, q_c)?;
609
610 let wires_in = [x.vars.0, y.vars.1, x.vars.1, y.vars.0];
621 let q_mul = [F::one(), F::one()];
622 let t1_var = self.mul_add(&wires_in, &q_mul)?;
623
624 let wires_in = [w1_var, w0_var, self.zero(), self.zero()];
626 let q_lc = [p.p.0, p.p.1, F::zero(), F::zero()];
627 let t2_var = self.lc(&wires_in, &q_lc)?;
628
629 let wires = [t1_var, t2_var, c0_var, c1_var, z1_var];
635 let q_lin = [F::one(), -F::one(), -F::one(), p.two_power_m];
636 let q_mul = [F::zero(), F::zero()];
637 let q_o = F::one();
638 let q_c = p.two_power_m - p.two_power_m.square().double();
639 self.quad_poly_gate(&wires, &q_lin, &q_mul, q_o, q_c)?;
640
641 let wires = [x.vars.1, y.vars.1, w1_var, self.zero(), c1_var];
646 let q_lin = [F::zero(), F::zero(), -p.p.1, F::zero()];
647 let q_mul = [F::one(), F::zero()];
648 let q_o = F::one();
649 let q_c = p.two_power_m.double();
650 self.quad_poly_gate(&wires, &q_lin, &q_mul, q_o, q_c)?;
651
652 Ok(FpElemVar {
653 vars: (z0_var, z1_var),
654 m: p.m,
655 two_power_m: p.two_power_m,
656 })
657 }
658
659 #[allow(clippy::many_single_char_names)]
667 pub fn mod_mul_constant(
668 &mut self,
669 x: &FpElemVar<F>,
670 y: &FpElem<F>,
671 p: &FpElem<F>,
672 ) -> Result<FpElemVar<F>, CircuitError> {
673 let range_bit_len = self.range_bit_len()?;
674 if x.m != p.m || y.m != p.m {
675 return Err(ParameterError(format!(
676 "field elements splitting parameters do not match: x.m = {}, y.m = {}, p.m = {}",
677 x.m, y.m, p.m
678 )));
679 }
680 if x.two_power_m != p.two_power_m || y.two_power_m != p.two_power_m {
681 return Err(ParameterError(format!(
682 "field elements splitting parameters do not match: x.2^m = {}, y.2^m = {}, p.2^m = {}",
683 x.two_power_m, y.two_power_m, p.two_power_m
684 )));
685 }
686 if p.m % range_bit_len != 0 {
687 return Err(ParameterError(format!(
688 "splitting parameter m = {} is not a multiple of range_bit_len",
689 p.m
690 )));
691 }
692
693 let two_power_m_int: BigUint = to_big_int!(p.two_power_m);
697 let x0_int: BigUint = to_big_int!(self.witness(x.vars.0)?);
698 let x1_int: BigUint = to_big_int!(self.witness(x.vars.1)?);
699 let y0_int: BigUint = to_big_int!(y.p.0);
700 let y1_int: BigUint = to_big_int!(y.p.1);
701 let p0_int: BigUint = to_big_int!(p.p.0);
702 let p1_int: BigUint = to_big_int!(p.p.1);
703 let x_int = &x0_int + &two_power_m_int * &x1_int;
704 let y_int = &y0_int + &two_power_m_int * &y1_int;
705 let p_int = &p0_int + &two_power_m_int * &p1_int;
706
707 let xy_int = &x_int * &y_int;
709 let w_int = &xy_int / &p_int;
710 let z_int = &xy_int - (&w_int * &p_int);
711 let w = FpElem::new(&F::from(w_int), p.m, Some(p.two_power_m))?;
712 let w0_int: BigUint = to_big_int!(w.p.0);
713 let w1_int: BigUint = to_big_int!(w.p.1);
714 let z = FpElem::new(&F::from(z_int), p.m, Some(p.two_power_m))?;
715 let z0_int = to_big_int!(z.p.0);
716 let z1_int = to_big_int!(z.p.1);
717
718 let x0y0_int = &x0_int * &y0_int;
735 let z0_plus_p0w0_int = &z0_int + &p0_int * &w0_int;
736 let c0_int = if z0_plus_p0w0_int >= x0y0_int {
737 let carry0_int = (&z0_plus_p0w0_int - &x0y0_int) / &two_power_m_int;
738 &two_power_m_int + carry0_int
739 } else {
740 let carry0_int = (&x0y0_int - z0_plus_p0w0_int) / &two_power_m_int;
741 &two_power_m_int - carry0_int
742 };
743
744 let a_int = &x0_int * &y1_int + &x1_int * &y0_int + &two_power_m_int;
748 let b_int = &z1_int + &p0_int * &w1_int + &p1_int * &w0_int + &c0_int;
749 let c1_int = if b_int >= a_int {
750 let carry1_int = (b_int - a_int) / &two_power_m_int;
751 &two_power_m_int + &two_power_m_int + carry1_int
752 } else {
753 let carry1_int = (a_int - b_int) / &two_power_m_int;
754 &two_power_m_int + &two_power_m_int - carry1_int
755 };
756
757 let w0_var = self.create_variable(F::from(w0_int))?;
769 let w1_var = self.create_variable(F::from(w1_int))?;
770 let z0_var = self.create_variable(F::from(z0_int))?;
771 let z1_var = self.create_variable(F::from(z1_int))?;
772 let c0_var = self.create_variable(F::from(c0_int))?;
773 let c1_var = self.create_variable(F::from(c1_int))?;
774 self.range_gate_with_lookup(w0_var, p.m)?;
775 self.range_gate_with_lookup(w1_var, p.m)?;
776 self.range_gate_with_lookup(z0_var, p.m)?;
777 self.range_gate_with_lookup(z1_var, p.m)?;
778 self.range_gate_with_lookup(c0_var, p.m + range_bit_len)?;
779 self.range_gate_with_lookup(c1_var, p.m + range_bit_len)?;
780
781 let wires = [x.vars.0, w0_var, c0_var, z0_var, self.zero()];
789 let q_lin = [y.p.0, -p.p.0, p.two_power_m, -F::one()];
790 let q_mul = [F::zero(), F::zero()];
791 let q_o = F::zero();
792 let q_c = -p.two_power_m.square();
793 self.quad_poly_gate(&wires, &q_lin, &q_mul, q_o, q_c)?;
794
795 let wires_in = [x.vars.0, x.vars.1, w1_var, w0_var];
806 let coeffs = [y.p.1, y.p.0, -p.p.0, -p.p.1];
807 let t1_var = self.lc(&wires_in, &coeffs)?;
808
809 let wires = [t1_var, z1_var, c0_var, c1_var, self.zero()];
815 let q_lin = [F::one(), -F::one(), -F::one(), p.two_power_m];
816 let q_mul = [F::zero(), F::zero()];
817 let q_o = F::zero();
818 let q_c = p.two_power_m - p.two_power_m.square().double();
819 self.quad_poly_gate(&wires, &q_lin, &q_mul, q_o, q_c)?;
820
821 let wires = [x.vars.1, w1_var, c1_var, self.zero(), self.zero()];
826 let q_lin = [y.p.1, -p.p.1, -F::one(), F::zero()];
827 let q_mul = [F::zero(), F::zero()];
828 let q_o = F::zero();
829 let q_c = p.two_power_m.double();
830 self.quad_poly_gate(&wires, &q_lin, &q_mul, q_o, q_c)?;
831
832 Ok(FpElemVar {
833 vars: (z0_var, z1_var),
834 m: p.m,
835 two_power_m: p.two_power_m,
836 })
837 }
838
839 pub fn mod_negate(&mut self, x: &FpElemVar<F>, p: &F) -> Result<FpElemVar<F>, CircuitError> {
842 let range_bit_len = self.range_bit_len()?;
843 if x.m % range_bit_len != 0 {
844 return Err(ParameterError(format!(
845 "splitting parameter m = {} is not a multiple of range_bit_len",
846 x.m
847 )));
848 }
849 let two_power_m_int: BigUint = to_big_int!(x.two_power_m);
851 let x0_int: BigUint = to_big_int!(self.witness(x.vars.0)?);
852 let x1_int: BigUint = to_big_int!(self.witness(x.vars.1)?);
853 let p_int: BigUint = to_big_int!(p);
854 let x_int = &x0_int + &two_power_m_int * &x1_int;
855 if x_int >= p_int {
856 return Err(CircuitError::FieldAlgebraError(
857 "non native field overflow".to_string(),
858 ));
859 }
860 let x_negate = F::from(p_int - x_int);
861
862 let x_var = x.convert_to_var(self)?;
864 let x_neg_var = self.create_variable(x_negate)?;
865
866 let wires = [x_var, x_neg_var, self.one(), self.zero(), self.zero()];
867 let coeffs = [F::one(), F::one(), -*p, F::zero()];
868
869 self.lc_gate(&wires, &coeffs)?;
870
871 FpElemVar::new_unchecked(self, x_neg_var, x.m, Some(x.two_power_m))
872 }
873}
874
875#[inline]
876fn int_div<F: PrimeField>(a: &F, b: &F) -> F {
878 let c_big_int: BigUint = a.into_bigint().into() / b.into_bigint().into();
879 F::from(c_big_int)
880}
881
882#[inline]
883fn div_rem<F: PrimeField>(a: &F, b: &F) -> (F, F) {
885 let div = int_div(a, b);
886 let rem = *a - *b * div;
887 (div, rem)
888}
889
890#[cfg(test)]
891mod test {
892 use super::*;
893 use crate::gadgets::test_utils::test_variable_independence_for_circuit;
894 use ark_bls12_377::{Fq as Fq377, Fr as Fr377};
895 use ark_ed_on_bls12_377::{Fq as FqEd377, Fr as FrEd377};
896 use ark_ed_on_bls12_381::Fq as FqEd381;
897 use ark_ed_on_bn254::{Fq as FqEd254, Fr as FrEd254};
898 use ark_ff::BigInteger;
899 use ark_std::rand::Rng;
900 use jf_utils::{field_switching, test_rng};
901
902 const RANGE_BIT_LEN_FOR_TEST: usize = 16;
903 const RANGE_SIZE_FOR_TEST: usize = 65536;
904
905 #[test]
906 fn test_fp_elem() -> Result<(), CircuitError> {
907 test_fp_elem_helper::<FqEd254>()?;
908 test_fp_elem_helper::<FqEd377>()?;
909 test_fp_elem_helper::<FqEd381>()?;
910 test_fp_elem_helper::<Fq377>()
911 }
912 fn test_fp_elem_helper<F: PrimeField>() -> Result<(), CircuitError> {
914 let mut rng = test_rng();
915 let p = int_div(&F::rand(&mut rng), &F::from(4u8));
916
917 let m = F::MODULUS_BIT_SIZE as usize / 2;
919 let two_power_m = F::from(2u8).pow([m as u64]);
920 let fp_elem = FpElem::new(&p, m, Some(two_power_m))?;
921 assert!(fp_elem.p.0 < two_power_m, "p0 larger than 2^m");
922 assert!(fp_elem.p.1 < two_power_m, "p1 larger than 2^m");
923 let q = fp_elem.field_elem();
924 assert_eq!(p, q, "FpElem conversion failure");
925
926 let fp_elem = FpElem::new(&p, 0, Some(two_power_m))?;
928 let q = fp_elem.field_elem();
929 assert_eq!(p, q, "FpElem conversion failure when m = 0");
930
931 let m = F::MODULUS_BIT_SIZE as usize / 2 + 1;
933 assert!(FpElem::new(&p, m, Some(two_power_m)).is_err());
934
935 Ok(())
936 }
937
938 #[test]
939 fn test_fp_elem_var() -> Result<(), CircuitError> {
940 test_fp_elem_var_helper::<FqEd254>()?;
941 test_fp_elem_var_helper::<FqEd377>()?;
942 test_fp_elem_var_helper::<FqEd381>()?;
943 test_fp_elem_var_helper::<Fq377>()
944 }
945 fn test_fp_elem_var_helper<F: PrimeField>() -> Result<(), CircuitError> {
947 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
948 let m = F::MODULUS_BIT_SIZE as usize / 2;
949 let mut rng = test_rng();
950
951 let p = F::rand(&mut rng);
953 let p_var = circuit.create_variable(p)?;
954 let fp_elem_var = FpElemVar::new_unchecked(&mut circuit, p_var, m, None)?;
955 let q_var = fp_elem_var.convert_to_var(&mut circuit)?;
956 circuit.enforce_equal(p_var, q_var)?;
957 assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
958
959 *circuit.witness_mut(p_var) = F::zero();
961 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
962
963 let p1 = F::rand(&mut rng);
965 let p2 = F::rand(&mut rng);
966 let circuit_1 = build_fp_elem_var_circuit(p1, m, fp_elem_var.two_power_m)?;
967 let circuit_2 = build_fp_elem_var_circuit(p2, m, fp_elem_var.two_power_m)?;
968 test_variable_independence_for_circuit::<F>(circuit_1, circuit_2)?;
969
970 Ok(())
971 }
972 fn build_fp_elem_var_circuit<F: PrimeField>(
973 p: F,
974 m: usize,
975 two_power_m: F,
976 ) -> Result<PlonkCircuit<F>, CircuitError> {
977 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(2);
978 let p_var = circuit.create_variable(p)?;
979 let fp_elem_var = FpElemVar::new_unchecked(&mut circuit, p_var, m, Some(two_power_m))?;
980 let _ = fp_elem_var.convert_to_var(&mut circuit)?;
981 circuit.finalize_for_arithmetization()?;
982 Ok(circuit)
983 }
984
985 #[test]
990 fn test_mod_add_internal() -> Result<(), CircuitError> {
991 test_mod_add_internal_helper::<FqEd254>()?;
992 test_mod_add_internal_helper::<FqEd377>()?;
993 test_mod_add_internal_helper::<FqEd381>()?;
994 test_mod_add_internal_helper::<Fq377>()
995 }
996 fn test_mod_add_internal_helper<F: PrimeField>() -> Result<(), CircuitError> {
997 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
998
999 let p = F::from(17u8);
1003 let vars: Vec<Variable> = (1..=10)
1004 .map(|i| circuit.create_variable(F::from(i as u8)))
1005 .collect::<Result<Vec<_>, CircuitError>>()?;
1006 let y_var = circuit.mod_add_internal(&vars, p, 1)?;
1007 assert_eq!(circuit.witness(y_var)?, F::from(4u8));
1008 assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1009
1010 let p = F::from(RANGE_SIZE_FOR_TEST as u32).pow([10u64]);
1012 let mut rng = test_rng();
1013 let vars: Vec<Variable> = (0..12)
1014 .map(|_| {
1015 circuit.create_variable(
1016 int_div(&p, &F::from(2u8)) + F::from(rng.gen_range(0..u64::MAX)),
1017 )
1018 })
1019 .collect::<Result<Vec<_>, CircuitError>>()?;
1020 let y_var = circuit.mod_add_internal(&vars, p, 10)?;
1021 let mut expected_y = F::zero();
1023 for &var in vars.iter() {
1024 expected_y += circuit.witness(var)?;
1025 }
1026 expected_y -= F::from(6u8) * p;
1027 assert_eq!(circuit.witness(y_var)?, expected_y);
1028 assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1029
1030 *circuit.witness_mut(y_var) = F::zero();
1034 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1035 *circuit.witness_mut(y_var) = p + F::one();
1036 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1037
1038 *circuit.witness_mut(y_var) = expected_y;
1039 let range_size = F::from(RANGE_SIZE_FOR_TEST as u32);
1041 let bad_x_var = circuit.create_variable(range_size * p)?;
1042 assert!(circuit
1043 .mod_add_internal(&[bad_x_var, bad_x_var], p, 10)
1044 .is_err());
1045
1046 let elems1: Vec<F> = (0..3)
1048 .map(|_| int_div(&p, &F::from(3u8)) + F::from(rng.gen_range(0..u64::MAX)))
1049 .collect();
1050 let elems2: Vec<F> = (0..3)
1051 .map(|_| int_div(&p, &F::from(3u8)) + F::from(rng.gen_range(0..u64::MAX)))
1052 .collect();
1053 let circuit_1 = build_mod_add_internal_circuit(&elems1, p, 10)?;
1054 let circuit_2 = build_mod_add_internal_circuit(&elems2, p, 10)?;
1055 test_variable_independence_for_circuit::<F>(circuit_1, circuit_2)?;
1056
1057 Ok(())
1058 }
1059 fn build_mod_add_internal_circuit<F: PrimeField>(
1060 elems: &[F],
1061 p: F,
1062 l_p: usize,
1063 ) -> Result<PlonkCircuit<F>, CircuitError> {
1064 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(3);
1065 let vars: Vec<Variable> = elems
1066 .iter()
1067 .map(|&elem| circuit.create_variable(elem))
1068 .collect::<Result<Vec<_>, CircuitError>>()?;
1069 circuit.mod_add_internal(&vars, p, l_p)?;
1070 circuit.finalize_for_arithmetization()?;
1071 Ok(circuit)
1072 }
1073
1074 #[test]
1078 fn test_mod_mul() -> Result<(), CircuitError> {
1079 test_mod_mul_helper::<FqEd254>()?;
1080 test_mod_mul_helper::<FqEd377>()?;
1081 test_mod_mul_helper::<FqEd381>()?;
1082 test_mod_mul_helper::<Fq377>()
1083 }
1084 fn test_mod_mul_helper<F: PrimeField>() -> Result<(), CircuitError> {
1085 let p = F::from(RANGE_SIZE_FOR_TEST as u32).pow([10u64]);
1086 let m = 80;
1087 let p_split = FpElem::new(&p, m, None)?;
1088 let mut rng = test_rng();
1089 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
1090
1091 for _ in 0..10 {
1092 let x_var = circuit.create_variable(p - F::from(rng.gen_range(1..u128::MAX)))?;
1093 let x_split_vars =
1094 FpElemVar::new_unchecked(&mut circuit, x_var, m, Some(p_split.two_power_m))?;
1095 let y_var = circuit.create_variable(p - F::from(rng.gen_range(1..u128::MAX)))?;
1096 let y_split_vars =
1097 FpElemVar::new_unchecked(&mut circuit, y_var, m, Some(p_split.two_power_m))?;
1098 let z_split_vars = circuit.mod_mul(&x_split_vars, &y_split_vars, &p_split)?;
1099 assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1100
1101 *circuit.witness_mut(z_split_vars.vars.1) += F::one();
1103 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1104 *circuit.witness_mut(z_split_vars.vars.1) -= F::one();
1105 *circuit.witness_mut(z_split_vars.vars.1) += p_split.two_power_m;
1106 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1108 *circuit.witness_mut(z_split_vars.vars.1) -= p_split.two_power_m;
1109
1110 let z_var = z_split_vars.convert_to_var(&mut circuit)?;
1111 check_mod_mul(
1112 circuit.witness(z_var)?,
1113 circuit.witness(x_var)?,
1114 circuit.witness(y_var)?,
1115 &p,
1116 );
1117 }
1118
1119 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
1122 let zero_var = circuit.zero();
1124 let x_split_vars =
1125 FpElemVar::new_unchecked(&mut circuit, zero_var, m + 1, Some(p_split.two_power_m))?;
1126 let y_split_vars =
1127 FpElemVar::new_unchecked(&mut circuit, zero_var, m, Some(p_split.two_power_m))?;
1128 assert!(circuit
1129 .mod_mul(&x_split_vars, &y_split_vars, &p_split)
1130 .is_err());
1131 let p_split_bad = FpElem::new(&p, m + 1, Some(p_split.two_power_m))?;
1133 let x_split_vars =
1134 FpElemVar::new_unchecked(&mut circuit, zero_var, m + 1, Some(p_split.two_power_m))?;
1135 let y_split_vars =
1136 FpElemVar::new_unchecked(&mut circuit, zero_var, m + 1, Some(p_split.two_power_m))?;
1137 assert!(circuit
1138 .mod_mul(&x_split_vars, &y_split_vars, &p_split_bad)
1139 .is_err());
1140
1141 let p_split_bad = FpElem::new(&p, m, Some(p_split.two_power_m + F::one()))?;
1143 let x_split_vars =
1144 FpElemVar::new_unchecked(&mut circuit, zero_var, m, Some(p_split.two_power_m))?;
1145 let y_split_vars =
1146 FpElemVar::new_unchecked(&mut circuit, zero_var, m, Some(p_split.two_power_m))?;
1147 assert!(circuit
1148 .mod_mul(&x_split_vars, &y_split_vars, &p_split_bad)
1149 .is_err());
1150
1151 let x1 = p - F::from(rng.gen_range(1..u128::MAX));
1153 let y1 = p - F::from(rng.gen_range(1..u128::MAX));
1154 let x2 = p - F::from(rng.gen_range(1..u128::MAX));
1155 let y2 = p - F::from(rng.gen_range(1..u128::MAX));
1156 let circuit_1 = build_mod_mul_circuit(&x1, &y1, &p_split)?;
1157 let circuit_2 = build_mod_mul_circuit(&x2, &y2, &p_split)?;
1158 test_variable_independence_for_circuit::<F>(circuit_1, circuit_2)?;
1159
1160 Ok(())
1161 }
1162 fn check_mod_mul<F: PrimeField>(z: F, x: F, y: F, p: &F) {
1163 let x_int: BigUint = to_big_int!(x);
1164 let y_int: BigUint = to_big_int!(y);
1165 let p_int: BigUint = to_big_int!(p);
1166 let xy_int = &x_int * &y_int;
1167 let w_int = &xy_int / &p_int;
1168 let z_int = &xy_int - (&w_int * &p_int);
1169 let expected_z = F::from(z_int);
1170 assert_eq!(z, expected_z);
1171 }
1172 fn build_mod_mul_circuit<F: PrimeField>(
1173 x: &F,
1174 y: &F,
1175 p: &FpElem<F>,
1176 ) -> Result<PlonkCircuit<F>, CircuitError> {
1177 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(5);
1178 let x_var = circuit.create_variable(*x)?;
1179 let x_split_vars = FpElemVar::new_unchecked(&mut circuit, x_var, p.m, Some(p.two_power_m))?;
1180 let y_var = circuit.create_variable(*y)?;
1181 let y_split_vars = FpElemVar::new_unchecked(&mut circuit, y_var, p.m, Some(p.two_power_m))?;
1182 circuit.mod_mul(&x_split_vars, &y_split_vars, p)?;
1183 circuit.finalize_for_arithmetization()?;
1184 Ok(circuit)
1185 }
1186
1187 #[test]
1191 fn test_mod_mul_constant() -> Result<(), CircuitError> {
1192 test_mod_mul_constant_helper::<FqEd254>()?;
1193 test_mod_mul_constant_helper::<FqEd377>()?;
1194 test_mod_mul_constant_helper::<FqEd381>()?;
1195 test_mod_mul_constant_helper::<Fq377>()
1196 }
1197 fn test_mod_mul_constant_helper<F: PrimeField>() -> Result<(), CircuitError> {
1198 let p = F::from(RANGE_SIZE_FOR_TEST as u32).pow([10u64]);
1199 let m = 80;
1200 let p_split = FpElem::new(&p, m, None)?;
1201 let mut rng = test_rng();
1202 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
1203
1204 for _ in 0..10 {
1205 let x_var = circuit.create_variable(p - F::from(rng.gen_range(1..u128::MAX)))?;
1206 let x_split_vars =
1207 FpElemVar::new_unchecked(&mut circuit, x_var, m, Some(p_split.two_power_m))?;
1208 let y = p - F::from(rng.gen_range(1..u128::MAX));
1209 let y_split = FpElem::new(&y, m, Some(p_split.two_power_m))?;
1210 let z_split_vars = circuit.mod_mul_constant(&x_split_vars, &y_split, &p_split)?;
1211 assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1212
1213 *circuit.witness_mut(z_split_vars.vars.1) += F::one();
1215 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1216 *circuit.witness_mut(z_split_vars.vars.1) -= F::one();
1217 *circuit.witness_mut(z_split_vars.vars.1) += p_split.two_power_m;
1218 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1220 *circuit.witness_mut(z_split_vars.vars.1) -= p_split.two_power_m;
1221
1222 let z_var = z_split_vars.convert_to_var(&mut circuit)?;
1223 check_mod_mul(circuit.witness(z_var)?, circuit.witness(x_var)?, y, &p);
1224 }
1225
1226 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
1229 let zero_var = circuit.zero();
1231 let x_split_vars =
1232 FpElemVar::new_unchecked(&mut circuit, zero_var, m + 1, Some(p_split.two_power_m))?;
1233 let y = p - F::from(rng.gen_range(1..u128::MAX));
1234 let y_split = FpElem::new(&y, m, Some(p_split.two_power_m))?;
1235 assert!(circuit
1236 .mod_mul_constant(&x_split_vars, &y_split, &p_split)
1237 .is_err());
1238 let p_split_bad = FpElem::new(&p, m + 1, Some(p_split.two_power_m))?;
1240 let x_split_vars =
1241 FpElemVar::new_unchecked(&mut circuit, zero_var, m + 1, Some(p_split.two_power_m))?;
1242 let y = p - F::from(rng.gen_range(1..u128::MAX));
1243 let y_split = FpElem::new(&y, m + 1, Some(p_split.two_power_m))?;
1244 assert!(circuit
1245 .mod_mul_constant(&x_split_vars, &y_split, &p_split_bad)
1246 .is_err());
1247
1248 let p_split_bad = FpElem::new(&p, m, Some(p_split.two_power_m + F::one()))?;
1250 let x_split_vars =
1251 FpElemVar::new_unchecked(&mut circuit, zero_var, m, Some(p_split.two_power_m))?;
1252 let y = p - F::from(rng.gen_range(1..u128::MAX));
1253 let y_split = FpElem::new(&y, m, Some(p_split.two_power_m))?;
1254 assert!(circuit
1255 .mod_mul_constant(&x_split_vars, &y_split, &p_split_bad)
1256 .is_err());
1257
1258 let x1 = p - F::from(rng.gen_range(1..u128::MAX));
1260 let y1 = p - F::from(rng.gen_range(1..u128::MAX));
1261 let x2 = p - F::from(rng.gen_range(1..u128::MAX));
1262 let y2 = p - F::from(rng.gen_range(1..u128::MAX));
1263 let circuit_1 = build_mod_mul_constant_circuit(&x1, &y1, &p_split)?;
1264 let circuit_2 = build_mod_mul_constant_circuit(&x2, &y2, &p_split)?;
1265 test_variable_independence_for_circuit::<F>(circuit_1, circuit_2)?;
1266
1267 Ok(())
1268 }
1269 fn build_mod_mul_constant_circuit<F: PrimeField>(
1270 x: &F,
1271 y: &F,
1272 p: &FpElem<F>,
1273 ) -> Result<PlonkCircuit<F>, CircuitError> {
1274 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(5);
1275 let x_var = circuit.create_variable(*x)?;
1276 let x_split_vars = FpElemVar::new_unchecked(&mut circuit, x_var, p.m, Some(p.two_power_m))?;
1277 let y_split = FpElem::new(y, p.m, Some(p.two_power_m))?;
1278 circuit.mod_mul_constant(&x_split_vars, &y_split, p)?;
1279 circuit.finalize_for_arithmetization()?;
1280 Ok(circuit)
1281 }
1282
1283 #[test]
1287 fn test_mod_add() -> Result<(), CircuitError> {
1288 test_mod_add_helper::<FqEd254>()?;
1289 test_mod_add_helper::<FqEd377>()?;
1290 test_mod_add_helper::<FqEd381>()?;
1291 test_mod_add_helper::<Fq377>()
1292 }
1293 fn test_mod_add_helper<F: PrimeField>() -> Result<(), CircuitError> {
1294 let p = F::from(RANGE_SIZE_FOR_TEST as u32).pow([10u64]);
1295 let m = 80;
1296 let p_split = FpElem::new(&p, m, None)?;
1297 let mut rng = test_rng();
1298 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
1299
1300 for _ in 0..10 {
1301 let x_var = circuit.create_variable(p - F::from(rng.gen_range(1..u128::MAX)))?;
1302 let x_split_vars =
1303 FpElemVar::new_unchecked(&mut circuit, x_var, m, Some(p_split.two_power_m))?;
1304 let y_var = circuit.create_variable(p - F::from(rng.gen_range(1..u128::MAX)))?;
1305 let y_split_vars =
1306 FpElemVar::new_unchecked(&mut circuit, y_var, m, Some(p_split.two_power_m))?;
1307 let z_split_vars = circuit.mod_add(&x_split_vars, &y_split_vars, &p_split)?;
1308 assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1309
1310 *circuit.witness_mut(z_split_vars.vars.1) += F::one();
1312 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1313 *circuit.witness_mut(z_split_vars.vars.1) -= F::one();
1314 *circuit.witness_mut(z_split_vars.vars.1) += p_split.two_power_m;
1315 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1317 *circuit.witness_mut(z_split_vars.vars.1) -= p_split.two_power_m;
1318
1319 let z_var = z_split_vars.convert_to_var(&mut circuit)?;
1320 check_mod_add(
1321 circuit.witness(z_var)?,
1322 circuit.witness(x_var)?,
1323 circuit.witness(y_var)?,
1324 &p,
1325 );
1326 }
1327
1328 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
1331 let zero_var = circuit.zero();
1333 let x_split_vars =
1334 FpElemVar::new_unchecked(&mut circuit, zero_var, m + 1, Some(p_split.two_power_m))?;
1335 let y_split_vars =
1336 FpElemVar::new_unchecked(&mut circuit, zero_var, m, Some(p_split.two_power_m))?;
1337 assert!(circuit
1338 .mod_add(&x_split_vars, &y_split_vars, &p_split)
1339 .is_err());
1340 let p_split_bad = FpElem::new(&p, m + 1, Some(p_split.two_power_m))?;
1342 let x_split_vars =
1343 FpElemVar::new_unchecked(&mut circuit, zero_var, m + 1, Some(p_split.two_power_m))?;
1344 let y_split_vars =
1345 FpElemVar::new_unchecked(&mut circuit, zero_var, m + 1, Some(p_split.two_power_m))?;
1346 assert!(circuit
1347 .mod_add(&x_split_vars, &y_split_vars, &p_split_bad)
1348 .is_err());
1349 let p_split_bad = FpElem::new(&p, m, Some(p_split.two_power_m + F::one()))?;
1351 let x_split_vars =
1352 FpElemVar::new_unchecked(&mut circuit, zero_var, m, Some(p_split.two_power_m))?;
1353 let y_split_vars =
1354 FpElemVar::new_unchecked(&mut circuit, zero_var, m, Some(p_split.two_power_m))?;
1355 assert!(circuit
1356 .mod_add(&x_split_vars, &y_split_vars, &p_split_bad)
1357 .is_err());
1358
1359 let x1 = p - F::from(rng.gen_range(1..u128::MAX));
1361 let y1 = p - F::from(rng.gen_range(1..u128::MAX));
1362 let x2 = p - F::from(rng.gen_range(1..u128::MAX));
1363 let y2 = p - F::from(rng.gen_range(1..u128::MAX));
1364 let circuit_1 = build_mod_add_circuit(&x1, &y1, &p_split)?;
1365 let circuit_2 = build_mod_add_circuit(&x2, &y2, &p_split)?;
1366 test_variable_independence_for_circuit::<F>(circuit_1, circuit_2)?;
1367
1368 Ok(())
1369 }
1370 fn check_mod_add<F: PrimeField>(z: F, x: F, y: F, p: &F) {
1371 let x_int: BigUint = to_big_int!(x);
1372 let y_int: BigUint = to_big_int!(y);
1373 let p_int: BigUint = to_big_int!(p);
1374 let xy_int = &x_int + &y_int;
1375 let w_int = &xy_int / &p_int;
1376 let z_int = &xy_int - (&w_int * &p_int);
1377 let expected_z = F::from(z_int);
1378 assert_eq!(z, expected_z);
1379 }
1380 fn build_mod_add_circuit<F: PrimeField>(
1381 x: &F,
1382 y: &F,
1383 p: &FpElem<F>,
1384 ) -> Result<PlonkCircuit<F>, CircuitError> {
1385 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(5);
1386 let x_var = circuit.create_variable(*x)?;
1387 let x_split_vars = FpElemVar::new_unchecked(&mut circuit, x_var, p.m, Some(p.two_power_m))?;
1388 let y_var = circuit.create_variable(*y)?;
1389 let y_split_vars = FpElemVar::new_unchecked(&mut circuit, y_var, p.m, Some(p.two_power_m))?;
1390 circuit.mod_add(&x_split_vars, &y_split_vars, p)?;
1391 circuit.finalize_for_arithmetization()?;
1392 Ok(circuit)
1393 }
1394
1395 #[test]
1399 fn test_mod_add_constant() -> Result<(), CircuitError> {
1400 test_mod_add_constant_helper::<FqEd254>()?;
1401 test_mod_add_constant_helper::<FqEd377>()?;
1402 test_mod_add_constant_helper::<FqEd381>()?;
1403 test_mod_add_constant_helper::<Fq377>()
1404 }
1405 fn test_mod_add_constant_helper<F: PrimeField>() -> Result<(), CircuitError> {
1406 let p = F::from(RANGE_SIZE_FOR_TEST as u32).pow([10u64]);
1407 let m = 80;
1408 let p_split = FpElem::new(&p, m, None)?;
1409 let mut rng = test_rng();
1410 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
1411
1412 {
1414 let x = p - F::one();
1415 let y = F::from(2u8);
1416
1417 let x_var = circuit.create_variable(x)?;
1418 let x_split_vars =
1419 FpElemVar::new_unchecked(&mut circuit, x_var, m, Some(p_split.two_power_m))?;
1420 let y_split = FpElem::new(&y, m, Some(p_split.two_power_m))?;
1421
1422 let z_split_vars = circuit.mod_add_constant(&x_split_vars, &y_split, &p_split)?;
1423 assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1424
1425 *circuit.witness_mut(z_split_vars.vars.1) += F::one();
1427 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1428 *circuit.witness_mut(z_split_vars.vars.1) -= F::one();
1429 *circuit.witness_mut(z_split_vars.vars.1) += p_split.two_power_m;
1430 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1432 *circuit.witness_mut(z_split_vars.vars.1) -= p_split.two_power_m;
1433
1434 let z_var = z_split_vars.convert_to_var(&mut circuit)?;
1435
1436 check_mod_add_constant(circuit.witness(z_var)?, circuit.witness(x_var)?, y, &p);
1437 }
1438
1439 for _ in 0..10 {
1441 let x_var = circuit.create_variable(p - F::from(rng.gen_range(1..u128::MAX)))?;
1442 let x_split_vars =
1443 FpElemVar::new_unchecked(&mut circuit, x_var, m, Some(p_split.two_power_m))?;
1444 let y = p - F::from(rng.gen_range(1..u128::MAX));
1445 let y_split = FpElem::new(&y, m, Some(p_split.two_power_m))?;
1446
1447 let z_split_vars = circuit.mod_add_constant(&x_split_vars, &y_split, &p_split)?;
1448 assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1449
1450 *circuit.witness_mut(z_split_vars.vars.1) += F::one();
1452 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1453 *circuit.witness_mut(z_split_vars.vars.1) -= F::one();
1454 *circuit.witness_mut(z_split_vars.vars.1) += p_split.two_power_m;
1455 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1457 *circuit.witness_mut(z_split_vars.vars.1) -= p_split.two_power_m;
1458
1459 let z_var = z_split_vars.convert_to_var(&mut circuit)?;
1460 check_mod_add_constant(circuit.witness(z_var)?, circuit.witness(x_var)?, y, &p);
1461 }
1462
1463 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
1466 let zero_var = circuit.zero();
1468 let x_split_vars =
1469 FpElemVar::new_unchecked(&mut circuit, zero_var, m + 1, Some(p_split.two_power_m))?;
1470 let y_split = FpElem::new(
1471 &(p - F::from(rng.gen_range(1..u128::MAX))),
1472 m,
1473 Some(p_split.two_power_m),
1474 )?;
1475
1476 assert!(circuit
1477 .mod_add_constant(&x_split_vars, &y_split, &p_split)
1478 .is_err());
1479 let p_split_bad = FpElem::new(&p, m + 1, Some(p_split.two_power_m))?;
1481 let x_split_vars =
1482 FpElemVar::new_unchecked(&mut circuit, zero_var, m + 1, Some(p_split.two_power_m))?;
1483 let y_split = FpElem::new(
1484 &(p - F::from(rng.gen_range(1..u128::MAX))),
1485 m + 1,
1486 Some(p_split.two_power_m),
1487 )?;
1488 assert!(circuit
1489 .mod_add_constant(&x_split_vars, &y_split, &p_split_bad)
1490 .is_err());
1491 let p_split_bad = FpElem::new(&p, m, Some(p_split.two_power_m + F::one()))?;
1493 let x_split_vars =
1494 FpElemVar::new_unchecked(&mut circuit, zero_var, m, Some(p_split.two_power_m))?;
1495 let y_split = FpElem::new(
1496 &(p - F::from(rng.gen_range(1..u128::MAX))),
1497 m,
1498 Some(p_split.two_power_m),
1499 )?;
1500 assert!(circuit
1501 .mod_add_constant(&x_split_vars, &y_split, &p_split_bad)
1502 .is_err());
1503
1504 let x1 = p - F::from(rng.gen_range(1..u128::MAX));
1506 let y1 = p - F::from(rng.gen_range(1..u128::MAX));
1507 let x2 = p - F::from(rng.gen_range(1..u128::MAX));
1508 let y2 = p - F::from(rng.gen_range(1..u128::MAX));
1509 let circuit_1 = build_mod_add_constant_circuit(&x1, &y1, &p_split)?;
1510 let circuit_2 = build_mod_add_constant_circuit(&x2, &y2, &p_split)?;
1511 test_variable_independence_for_circuit::<F>(circuit_1, circuit_2)?;
1512
1513 Ok(())
1514 }
1515 fn check_mod_add_constant<F: PrimeField>(z: F, x: F, y: F, p: &F) {
1516 let x_int: BigUint = to_big_int!(x);
1517 let y_int: BigUint = to_big_int!(y);
1518 let p_int: BigUint = to_big_int!(p);
1519 let xy_int = &x_int + &y_int;
1520 let w_int = &xy_int / &p_int;
1521 let z_int = &xy_int - (&w_int * &p_int);
1522 let expected_z = F::from(z_int);
1523 assert_eq!(z, expected_z);
1524 }
1525 fn build_mod_add_constant_circuit<F: PrimeField>(
1526 x: &F,
1527 y: &F,
1528 p: &FpElem<F>,
1529 ) -> Result<PlonkCircuit<F>, CircuitError> {
1530 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(5);
1531 let x_var = circuit.create_variable(*x)?;
1532 let x_split_vars = FpElemVar::new_unchecked(&mut circuit, x_var, p.m, Some(p.two_power_m))?;
1533 let y_split = FpElem::new(y, p.m, Some(p.two_power_m))?;
1534 circuit.mod_add_constant(&x_split_vars, &y_split, p)?;
1535 circuit.finalize_for_arithmetization()?;
1536 Ok(circuit)
1537 }
1538
1539 #[test]
1543 fn test_mod_negation() -> Result<(), CircuitError> {
1544 test_mod_negation_helper::<FqEd254, FrEd254>(126, 9)?;
1545 test_mod_negation_helper::<FqEd377, FrEd377>(126, 9)?;
1546 test_mod_negation_helper::<Fq377, Fr377>(128, 16)
1547
1548 }
1551 fn test_mod_negation_helper<F: PrimeField, T: PrimeField>(
1552 m: usize,
1553 range_bit_len: usize,
1554 ) -> Result<(), CircuitError> {
1555 let p = F::from_le_bytes_mod_order(T::MODULUS.to_bytes_le().as_ref());
1556 let p_split = FpElem::new(&p, m, None)?;
1557 let mut rng = test_rng();
1558 let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(range_bit_len);
1559
1560 for _ in 0..10 {
1561 let x = T::rand(&mut rng);
1562 let x_var = circuit.create_variable(field_switching(&x))?;
1563 let x_split_vars =
1564 FpElemVar::new_unchecked(&mut circuit, x_var, m, Some(p_split.two_power_m))?;
1565
1566 let y_split_vars = circuit.mod_negate(&x_split_vars, &p)?;
1567
1568 assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
1569
1570 *circuit.witness_mut(y_split_vars.vars.1) += F::one();
1572 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1573 *circuit.witness_mut(y_split_vars.vars.1) -= F::one();
1574 *circuit.witness_mut(y_split_vars.vars.1) += p_split.two_power_m;
1575
1576 assert!(circuit.check_circuit_satisfiability(&[]).is_err());
1578 *circuit.witness_mut(y_split_vars.vars.1) -= p_split.two_power_m;
1579
1580 let y_var = y_split_vars.convert_to_var(&mut circuit)?;
1581 let y = circuit.witness(y_var)?;
1582 assert_eq!(T::zero(), x + field_switching::<_, T>(&y))
1583 }
1584
1585 Ok(())
1586 }
1587}