plonky2-ecdsa/src/gadgets/nonnative.rs
src/gadgets/nonnative.rsRaw
1use alloc::vec;
2use alloc::vec::Vec;
3use core::marker::PhantomData;
4
5use num::{BigUint, Integer, One, Zero};
6use plonky2::field::extension::Extendable;
7use plonky2::field::types::{Field, PrimeField};
8use plonky2::hash::hash_types::RichField;
9use plonky2::iop::generator::{GeneratedValues, SimpleGenerator};
10use plonky2::iop::target::{BoolTarget, Target};
11use plonky2::iop::witness::{PartitionWitness, WitnessWrite};
12use plonky2::plonk::circuit_builder::CircuitBuilder;
13use plonky2::util::ceil_div_usize;
14use plonky2_u32::gadgets::arithmetic_u32::{CircuitBuilderU32, U32Target};
15use plonky2_u32::gadgets::range_check::range_check_u32_circuit;
16use plonky2_u32::witness::GeneratedValuesU32;
17
18use crate::gadgets::biguint::{
19 BigUintTarget, CircuitBuilderBiguint, GeneratedValuesBigUint, WitnessBigUint,
20};
21
22#[derive(Clone, Debug)]
23pub struct NonNativeTarget<FF: Field> {
24 pub(crate) value: BigUintTarget,
25 pub(crate) _phantom: PhantomData<FF>,
26}
27
28pub trait CircuitBuilderNonNative<F: RichField + Extendable<D>, const D: usize> {
29 fn num_nonnative_limbs<FF: Field>() -> usize {
30 ceil_div_usize(FF::BITS, 32)
31 }
32
33 fn biguint_to_nonnative<FF: Field>(&mut self, x: &BigUintTarget) -> NonNativeTarget<FF>;
34
35 fn nonnative_to_canonical_biguint<FF: Field>(
36 &mut self,
37 x: &NonNativeTarget<FF>,
38 ) -> BigUintTarget;
39
40 fn constant_nonnative<FF: PrimeField>(&mut self, x: FF) -> NonNativeTarget<FF>;
41
42 fn zero_nonnative<FF: PrimeField>(&mut self) -> NonNativeTarget<FF>;
43
44 // Assert that two NonNativeTarget's, both assumed to be in reduced form, are equal.
45 fn connect_nonnative<FF: Field>(
46 &mut self,
47 lhs: &NonNativeTarget<FF>,
48 rhs: &NonNativeTarget<FF>,
49 );
50
51 fn add_virtual_nonnative_target<FF: Field>(&mut self) -> NonNativeTarget<FF>;
52
53 fn add_virtual_nonnative_target_sized<FF: Field>(
54 &mut self,
55 num_limbs: usize,
56 ) -> NonNativeTarget<FF>;
57
58 fn add_nonnative<FF: PrimeField>(
59 &mut self,
60 a: &NonNativeTarget<FF>,
61 b: &NonNativeTarget<FF>,
62 ) -> NonNativeTarget<FF>;
63
64 fn mul_nonnative_by_bool<FF: Field>(
65 &mut self,
66 a: &NonNativeTarget<FF>,
67 b: BoolTarget,
68 ) -> NonNativeTarget<FF>;
69
70 fn if_nonnative<FF: PrimeField>(
71 &mut self,
72 b: BoolTarget,
73 x: &NonNativeTarget<FF>,
74 y: &NonNativeTarget<FF>,
75 ) -> NonNativeTarget<FF>;
76
77 fn add_many_nonnative<FF: PrimeField>(
78 &mut self,
79 to_add: &[NonNativeTarget<FF>],
80 ) -> NonNativeTarget<FF>;
81
82 // Subtract two `NonNativeTarget`s.
83 fn sub_nonnative<FF: PrimeField>(
84 &mut self,
85 a: &NonNativeTarget<FF>,
86 b: &NonNativeTarget<FF>,
87 ) -> NonNativeTarget<FF>;
88
89 fn mul_nonnative<FF: PrimeField>(
90 &mut self,
91 a: &NonNativeTarget<FF>,
92 b: &NonNativeTarget<FF>,
93 ) -> NonNativeTarget<FF>;
94
95 fn mul_many_nonnative<FF: PrimeField>(
96 &mut self,
97 to_mul: &[NonNativeTarget<FF>],
98 ) -> NonNativeTarget<FF>;
99
100 fn neg_nonnative<FF: PrimeField>(&mut self, x: &NonNativeTarget<FF>) -> NonNativeTarget<FF>;
101
102 fn inv_nonnative<FF: PrimeField>(&mut self, x: &NonNativeTarget<FF>) -> NonNativeTarget<FF>;
103
104 /// Returns `x % |FF|` as a `NonNativeTarget`.
105 fn reduce<FF: Field>(&mut self, x: &BigUintTarget) -> NonNativeTarget<FF>;
106
107 fn reduce_nonnative<FF: Field>(&mut self, x: &NonNativeTarget<FF>) -> NonNativeTarget<FF>;
108
109 fn bool_to_nonnative<FF: Field>(&mut self, b: &BoolTarget) -> NonNativeTarget<FF>;
110
111 // Split a nonnative field element to bits.
112 fn split_nonnative_to_bits<FF: Field>(&mut self, x: &NonNativeTarget<FF>) -> Vec<BoolTarget>;
113
114 fn nonnative_conditional_neg<FF: PrimeField>(
115 &mut self,
116 x: &NonNativeTarget<FF>,
117 b: BoolTarget,
118 ) -> NonNativeTarget<FF>;
119}
120
121impl<F: RichField + Extendable<D>, const D: usize> CircuitBuilderNonNative<F, D>
122 for CircuitBuilder<F, D>
123{
124 fn num_nonnative_limbs<FF: Field>() -> usize {
125 ceil_div_usize(FF::BITS, 32)
126 }
127
128 fn biguint_to_nonnative<FF: Field>(&mut self, x: &BigUintTarget) -> NonNativeTarget<FF> {
129 NonNativeTarget {
130 value: x.clone(),
131 _phantom: PhantomData,
132 }
133 }
134
135 fn nonnative_to_canonical_biguint<FF: Field>(
136 &mut self,
137 x: &NonNativeTarget<FF>,
138 ) -> BigUintTarget {
139 x.value.clone()
140 }
141
142 fn constant_nonnative<FF: PrimeField>(&mut self, x: FF) -> NonNativeTarget<FF> {
143 let x_biguint = self.constant_biguint(&x.to_canonical_biguint());
144 self.biguint_to_nonnative(&x_biguint)
145 }
146
147 fn zero_nonnative<FF: PrimeField>(&mut self) -> NonNativeTarget<FF> {
148 self.constant_nonnative(FF::ZERO)
149 }
150
151 // Assert that two NonNativeTarget's, both assumed to be in reduced form, are equal.
152 fn connect_nonnative<FF: Field>(
153 &mut self,
154 lhs: &NonNativeTarget<FF>,
155 rhs: &NonNativeTarget<FF>,
156 ) {
157 self.connect_biguint(&lhs.value, &rhs.value);
158 }
159
160 fn add_virtual_nonnative_target<FF: Field>(&mut self) -> NonNativeTarget<FF> {
161 let num_limbs = Self::num_nonnative_limbs::<FF>();
162 let value = self.add_virtual_biguint_target(num_limbs);
163
164 NonNativeTarget {
165 value,
166 _phantom: PhantomData,
167 }
168 }
169
170 fn add_virtual_nonnative_target_sized<FF: Field>(
171 &mut self,
172 num_limbs: usize,
173 ) -> NonNativeTarget<FF> {
174 let value = self.add_virtual_biguint_target(num_limbs);
175
176 NonNativeTarget {
177 value,
178 _phantom: PhantomData,
179 }
180 }
181
182 fn add_nonnative<FF: PrimeField>(
183 &mut self,
184 a: &NonNativeTarget<FF>,
185 b: &NonNativeTarget<FF>,
186 ) -> NonNativeTarget<FF> {
187 let sum = self.add_virtual_nonnative_target::<FF>();
188 let overflow = self.add_virtual_bool_target_unsafe();
189
190 self.add_simple_generator(NonNativeAdditionGenerator::<F, D, FF> {
191 a: a.clone(),
192 b: b.clone(),
193 sum: sum.clone(),
194 overflow,
195 _phantom: PhantomData,
196 });
197
198 let sum_expected = self.add_biguint(&a.value, &b.value);
199
200 let modulus = self.constant_biguint(&FF::order());
201 let mod_times_overflow = self.mul_biguint_by_bool(&modulus, overflow);
202 let sum_actual = self.add_biguint(&sum.value, &mod_times_overflow);
203 self.connect_biguint(&sum_expected, &sum_actual);
204
205 // Range-check result.
206 // TODO: can potentially leave unreduced until necessary (e.g. when connecting values).
207 let cmp = self.cmp_biguint(&sum.value, &modulus);
208 let one = self.one();
209 self.connect(cmp.target, one);
210
211 sum
212 }
213
214 fn mul_nonnative_by_bool<FF: Field>(
215 &mut self,
216 a: &NonNativeTarget<FF>,
217 b: BoolTarget,
218 ) -> NonNativeTarget<FF> {
219 NonNativeTarget {
220 value: self.mul_biguint_by_bool(&a.value, b),
221 _phantom: PhantomData,
222 }
223 }
224
225 fn if_nonnative<FF: PrimeField>(
226 &mut self,
227 b: BoolTarget,
228 x: &NonNativeTarget<FF>,
229 y: &NonNativeTarget<FF>,
230 ) -> NonNativeTarget<FF> {
231 let not_b = self.not(b);
232 let maybe_x = self.mul_nonnative_by_bool(x, b);
233 let maybe_y = self.mul_nonnative_by_bool(y, not_b);
234 self.add_nonnative(&maybe_x, &maybe_y)
235 }
236
237 fn add_many_nonnative<FF: PrimeField>(
238 &mut self,
239 to_add: &[NonNativeTarget<FF>],
240 ) -> NonNativeTarget<FF> {
241 if to_add.len() == 1 {
242 return to_add[0].clone();
243 }
244
245 let sum = self.add_virtual_nonnative_target::<FF>();
246 let overflow = self.add_virtual_u32_target();
247 let summands = to_add.to_vec();
248
249 self.add_simple_generator(NonNativeMultipleAddsGenerator::<F, D, FF> {
250 summands: summands.clone(),
251 sum: sum.clone(),
252 overflow,
253 _phantom: PhantomData,
254 });
255
256 range_check_u32_circuit(self, sum.value.limbs.clone());
257 range_check_u32_circuit(self, vec![overflow]);
258
259 let sum_expected = summands
260 .iter()
261 .fold(self.zero_biguint(), |a, b| self.add_biguint(&a, &b.value));
262
263 let modulus = self.constant_biguint(&FF::order());
264 let overflow_biguint = BigUintTarget {
265 limbs: vec![overflow],
266 };
267 let mod_times_overflow = self.mul_biguint(&modulus, &overflow_biguint);
268 let sum_actual = self.add_biguint(&sum.value, &mod_times_overflow);
269 self.connect_biguint(&sum_expected, &sum_actual);
270
271 // Range-check result.
272 // TODO: can potentially leave unreduced until necessary (e.g. when connecting values).
273 let cmp = self.cmp_biguint(&sum.value, &modulus);
274 let one = self.one();
275 self.connect(cmp.target, one);
276
277 sum
278 }
279
280 // Subtract two `NonNativeTarget`s.
281 fn sub_nonnative<FF: PrimeField>(
282 &mut self,
283 a: &NonNativeTarget<FF>,
284 b: &NonNativeTarget<FF>,
285 ) -> NonNativeTarget<FF> {
286 let diff = self.add_virtual_nonnative_target::<FF>();
287 let overflow = self.add_virtual_bool_target_unsafe();
288
289 self.add_simple_generator(NonNativeSubtractionGenerator::<F, D, FF> {
290 a: a.clone(),
291 b: b.clone(),
292 diff: diff.clone(),
293 overflow,
294 _phantom: PhantomData,
295 });
296
297 range_check_u32_circuit(self, diff.value.limbs.clone());
298 self.assert_bool(overflow);
299
300 let diff_plus_b = self.add_biguint(&diff.value, &b.value);
301 let modulus = self.constant_biguint(&FF::order());
302 let mod_times_overflow = self.mul_biguint_by_bool(&modulus, overflow);
303 let diff_plus_b_reduced = self.sub_biguint(&diff_plus_b, &mod_times_overflow);
304 self.connect_biguint(&a.value, &diff_plus_b_reduced);
305
306 diff
307 }
308
309 fn mul_nonnative<FF: PrimeField>(
310 &mut self,
311 a: &NonNativeTarget<FF>,
312 b: &NonNativeTarget<FF>,
313 ) -> NonNativeTarget<FF> {
314 let prod = self.add_virtual_nonnative_target::<FF>();
315 let modulus = self.constant_biguint(&FF::order());
316 let overflow = self.add_virtual_biguint_target(
317 a.value.num_limbs() + b.value.num_limbs() - modulus.num_limbs(),
318 );
319
320 self.add_simple_generator(NonNativeMultiplicationGenerator::<F, D, FF> {
321 a: a.clone(),
322 b: b.clone(),
323 prod: prod.clone(),
324 overflow: overflow.clone(),
325 _phantom: PhantomData,
326 });
327
328 range_check_u32_circuit(self, prod.value.limbs.clone());
329 range_check_u32_circuit(self, overflow.limbs.clone());
330
331 let prod_expected = self.mul_biguint(&a.value, &b.value);
332
333 let mod_times_overflow = self.mul_biguint(&modulus, &overflow);
334 let prod_actual = self.add_biguint(&prod.value, &mod_times_overflow);
335 self.connect_biguint(&prod_expected, &prod_actual);
336
337 prod
338 }
339
340 fn mul_many_nonnative<FF: PrimeField>(
341 &mut self,
342 to_mul: &[NonNativeTarget<FF>],
343 ) -> NonNativeTarget<FF> {
344 if to_mul.len() == 1 {
345 return to_mul[0].clone();
346 }
347
348 let mut accumulator = self.mul_nonnative(&to_mul[0], &to_mul[1]);
349 for t in to_mul.iter().skip(2) {
350 accumulator = self.mul_nonnative(&accumulator, t);
351 }
352 accumulator
353 }
354
355 fn neg_nonnative<FF: PrimeField>(&mut self, x: &NonNativeTarget<FF>) -> NonNativeTarget<FF> {
356 let zero_target = self.constant_biguint(&BigUint::zero());
357 let zero_ff = self.biguint_to_nonnative(&zero_target);
358
359 self.sub_nonnative(&zero_ff, x)
360 }
361
362 fn inv_nonnative<FF: PrimeField>(&mut self, x: &NonNativeTarget<FF>) -> NonNativeTarget<FF> {
363 let num_limbs = x.value.num_limbs();
364 let inv_biguint = self.add_virtual_biguint_target(num_limbs);
365 let div = self.add_virtual_biguint_target(num_limbs);
366
367 self.add_simple_generator(NonNativeInverseGenerator::<F, D, FF> {
368 x: x.clone(),
369 inv: inv_biguint.clone(),
370 div: div.clone(),
371 _phantom: PhantomData,
372 });
373
374 let product = self.mul_biguint(&x.value, &inv_biguint);
375
376 let modulus = self.constant_biguint(&FF::order());
377 let mod_times_div = self.mul_biguint(&modulus, &div);
378 let one = self.constant_biguint(&BigUint::one());
379 let expected_product = self.add_biguint(&mod_times_div, &one);
380 self.connect_biguint(&product, &expected_product);
381
382 NonNativeTarget::<FF> {
383 value: inv_biguint,
384 _phantom: PhantomData,
385 }
386 }
387
388 /// Returns `x % |FF|` as a `NonNativeTarget`.
389 fn reduce<FF: Field>(&mut self, x: &BigUintTarget) -> NonNativeTarget<FF> {
390 let modulus = FF::order();
391 let order_target = self.constant_biguint(&modulus);
392 let value = self.rem_biguint(x, &order_target);
393
394 NonNativeTarget {
395 value,
396 _phantom: PhantomData,
397 }
398 }
399
400 fn reduce_nonnative<FF: Field>(&mut self, x: &NonNativeTarget<FF>) -> NonNativeTarget<FF> {
401 let x_biguint = self.nonnative_to_canonical_biguint(x);
402 self.reduce(&x_biguint)
403 }
404
405 fn bool_to_nonnative<FF: Field>(&mut self, b: &BoolTarget) -> NonNativeTarget<FF> {
406 let limbs = vec![U32Target(b.target)];
407 let value = BigUintTarget { limbs };
408
409 NonNativeTarget {
410 value,
411 _phantom: PhantomData,
412 }
413 }
414
415 // Split a nonnative field element to bits.
416 fn split_nonnative_to_bits<FF: Field>(&mut self, x: &NonNativeTarget<FF>) -> Vec<BoolTarget> {
417 let num_limbs = x.value.num_limbs();
418 let mut result = Vec::with_capacity(num_limbs * 32);
419
420 for i in 0..num_limbs {
421 let limb = x.value.get_limb(i);
422 let bit_targets = self.split_le_base::<2>(limb.0, 32);
423 let mut bits: Vec<_> = bit_targets
424 .iter()
425 .map(|&t| BoolTarget::new_unsafe(t))
426 .collect();
427
428 result.append(&mut bits);
429 }
430
431 result
432 }
433
434 fn nonnative_conditional_neg<FF: PrimeField>(
435 &mut self,
436 x: &NonNativeTarget<FF>,
437 b: BoolTarget,
438 ) -> NonNativeTarget<FF> {
439 let not_b = self.not(b);
440 let neg = self.neg_nonnative(x);
441 let x_if_true = self.mul_nonnative_by_bool(&neg, b);
442 let x_if_false = self.mul_nonnative_by_bool(x, not_b);
443
444 self.add_nonnative(&x_if_true, &x_if_false)
445 }
446}
447
448#[derive(Debug)]
449struct NonNativeAdditionGenerator<F: RichField + Extendable<D>, const D: usize, FF: PrimeField> {
450 a: NonNativeTarget<FF>,
451 b: NonNativeTarget<FF>,
452 sum: NonNativeTarget<FF>,
453 overflow: BoolTarget,
454 _phantom: PhantomData<F>,
455}
456
457impl<F: RichField + Extendable<D>, const D: usize, FF: PrimeField> SimpleGenerator<F>
458 for NonNativeAdditionGenerator<F, D, FF>
459{
460 fn dependencies(&self) -> Vec<Target> {
461 self.a
462 .value
463 .limbs
464 .iter()
465 .cloned()
466 .chain(self.b.value.limbs.clone())
467 .map(|l| l.0)
468 .collect()
469 }
470
471 fn run_once(&self, witness: &PartitionWitness<F>, out_buffer: &mut GeneratedValues<F>) {
472 let a = FF::from_noncanonical_biguint(witness.get_biguint_target(self.a.value.clone()));
473 let b = FF::from_noncanonical_biguint(witness.get_biguint_target(self.b.value.clone()));
474 let a_biguint = a.to_canonical_biguint();
475 let b_biguint = b.to_canonical_biguint();
476 let sum_biguint = a_biguint + b_biguint;
477 let modulus = FF::order();
478 let (overflow, sum_reduced) = if sum_biguint > modulus {
479 (true, sum_biguint - modulus)
480 } else {
481 (false, sum_biguint)
482 };
483
484 out_buffer.set_biguint_target(&self.sum.value, &sum_reduced);
485 out_buffer.set_bool_target(self.overflow, overflow);
486 }
487}
488
489#[derive(Debug)]
490struct NonNativeMultipleAddsGenerator<F: RichField + Extendable<D>, const D: usize, FF: PrimeField>
491{
492 summands: Vec<NonNativeTarget<FF>>,
493 sum: NonNativeTarget<FF>,
494 overflow: U32Target,
495 _phantom: PhantomData<F>,
496}
497
498impl<F: RichField + Extendable<D>, const D: usize, FF: PrimeField> SimpleGenerator<F>
499 for NonNativeMultipleAddsGenerator<F, D, FF>
500{
501 fn dependencies(&self) -> Vec<Target> {
502 self.summands
503 .iter()
504 .flat_map(|summand| summand.value.limbs.iter().map(|limb| limb.0))
505 .collect()
506 }
507
508 fn run_once(&self, witness: &PartitionWitness<F>, out_buffer: &mut GeneratedValues<F>) {
509 let summands: Vec<_> = self
510 .summands
511 .iter()
512 .map(|summand| {
513 FF::from_noncanonical_biguint(witness.get_biguint_target(summand.value.clone()))
514 })
515 .collect();
516 let summand_biguints: Vec<_> = summands
517 .iter()
518 .map(|summand| summand.to_canonical_biguint())
519 .collect();
520
521 let sum_biguint = summand_biguints
522 .iter()
523 .fold(BigUint::zero(), |a, b| a + b.clone());
524
525 let modulus = FF::order();
526 let (overflow_biguint, sum_reduced) = sum_biguint.div_rem(&modulus);
527 let overflow = overflow_biguint.to_u64_digits()[0] as u32;
528
529 out_buffer.set_biguint_target(&self.sum.value, &sum_reduced);
530 out_buffer.set_u32_target(self.overflow, overflow);
531 }
532}
533
534#[derive(Debug)]
535struct NonNativeSubtractionGenerator<F: RichField + Extendable<D>, const D: usize, FF: Field> {
536 a: NonNativeTarget<FF>,
537 b: NonNativeTarget<FF>,
538 diff: NonNativeTarget<FF>,
539 overflow: BoolTarget,
540 _phantom: PhantomData<F>,
541}
542
543impl<F: RichField + Extendable<D>, const D: usize, FF: PrimeField> SimpleGenerator<F>
544 for NonNativeSubtractionGenerator<F, D, FF>
545{
546 fn dependencies(&self) -> Vec<Target> {
547 self.a
548 .value
549 .limbs
550 .iter()
551 .cloned()
552 .chain(self.b.value.limbs.clone())
553 .map(|l| l.0)
554 .collect()
555 }
556
557 fn run_once(&self, witness: &PartitionWitness<F>, out_buffer: &mut GeneratedValues<F>) {
558 let a = FF::from_noncanonical_biguint(witness.get_biguint_target(self.a.value.clone()));
559 let b = FF::from_noncanonical_biguint(witness.get_biguint_target(self.b.value.clone()));
560 let a_biguint = a.to_canonical_biguint();
561 let b_biguint = b.to_canonical_biguint();
562
563 let modulus = FF::order();
564 let (diff_biguint, overflow) = if a_biguint >= b_biguint {
565 (a_biguint - b_biguint, false)
566 } else {
567 (modulus + a_biguint - b_biguint, true)
568 };
569
570 out_buffer.set_biguint_target(&self.diff.value, &diff_biguint);
571 out_buffer.set_bool_target(self.overflow, overflow);
572 }
573}
574
575#[derive(Debug)]
576struct NonNativeMultiplicationGenerator<F: RichField + Extendable<D>, const D: usize, FF: Field> {
577 a: NonNativeTarget<FF>,
578 b: NonNativeTarget<FF>,
579 prod: NonNativeTarget<FF>,
580 overflow: BigUintTarget,
581 _phantom: PhantomData<F>,
582}
583
584impl<F: RichField + Extendable<D>, const D: usize, FF: PrimeField> SimpleGenerator<F>
585 for NonNativeMultiplicationGenerator<F, D, FF>
586{
587 fn dependencies(&self) -> Vec<Target> {
588 self.a
589 .value
590 .limbs
591 .iter()
592 .cloned()
593 .chain(self.b.value.limbs.clone())
594 .map(|l| l.0)
595 .collect()
596 }
597
598 fn run_once(&self, witness: &PartitionWitness<F>, out_buffer: &mut GeneratedValues<F>) {
599 let a = FF::from_noncanonical_biguint(witness.get_biguint_target(self.a.value.clone()));
600 let b = FF::from_noncanonical_biguint(witness.get_biguint_target(self.b.value.clone()));
601 let a_biguint = a.to_canonical_biguint();
602 let b_biguint = b.to_canonical_biguint();
603
604 let prod_biguint = a_biguint * b_biguint;
605
606 let modulus = FF::order();
607 let (overflow_biguint, prod_reduced) = prod_biguint.div_rem(&modulus);
608
609 out_buffer.set_biguint_target(&self.prod.value, &prod_reduced);
610 out_buffer.set_biguint_target(&self.overflow, &overflow_biguint);
611 }
612}
613
614#[derive(Debug)]
615struct NonNativeInverseGenerator<F: RichField + Extendable<D>, const D: usize, FF: PrimeField> {
616 x: NonNativeTarget<FF>,
617 inv: BigUintTarget,
618 div: BigUintTarget,
619 _phantom: PhantomData<F>,
620}
621
622impl<F: RichField + Extendable<D>, const D: usize, FF: PrimeField> SimpleGenerator<F>
623 for NonNativeInverseGenerator<F, D, FF>
624{
625 fn dependencies(&self) -> Vec<Target> {
626 self.x.value.limbs.iter().map(|&l| l.0).collect()
627 }
628
629 fn run_once(&self, witness: &PartitionWitness<F>, out_buffer: &mut GeneratedValues<F>) {
630 let x = FF::from_noncanonical_biguint(witness.get_biguint_target(self.x.value.clone()));
631 let inv = x.inverse();
632
633 let x_biguint = x.to_canonical_biguint();
634 let inv_biguint = inv.to_canonical_biguint();
635 let prod = x_biguint * &inv_biguint;
636 let modulus = FF::order();
637 let (div, _rem) = prod.div_rem(&modulus);
638
639 out_buffer.set_biguint_target(&self.div, &div);
640 out_buffer.set_biguint_target(&self.inv, &inv_biguint);
641 }
642}
643
644#[cfg(test)]
645mod tests {
646 use anyhow::Result;
647 use plonky2::field::secp256k1_base::Secp256K1Base;
648 use plonky2::field::types::{Field, PrimeField, Sample};
649 use plonky2::iop::witness::PartialWitness;
650 use plonky2::plonk::circuit_builder::CircuitBuilder;
651 use plonky2::plonk::circuit_data::CircuitConfig;
652 use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};
653
654 use crate::gadgets::nonnative::CircuitBuilderNonNative;
655
656 #[test]
657 fn test_nonnative_add() -> Result<()> {
658 type FF = Secp256K1Base;
659 const D: usize = 2;
660 type C = PoseidonGoldilocksConfig;
661 type F = <C as GenericConfig<D>>::F;
662
663 let x_ff = FF::rand();
664 let y_ff = FF::rand();
665 let sum_ff = x_ff + y_ff;
666
667 let config = CircuitConfig::standard_ecc_config();
668 let pw = PartialWitness::new();
669 let mut builder = CircuitBuilder::<F, D>::new(config);
670
671 let x = builder.constant_nonnative(x_ff);
672 let y = builder.constant_nonnative(y_ff);
673 let sum = builder.add_nonnative(&x, &y);
674
675 let sum_expected = builder.constant_nonnative(sum_ff);
676 builder.connect_nonnative(&sum, &sum_expected);
677
678 let data = builder.build::<C>();
679 let proof = data.prove(pw).unwrap();
680 data.verify(proof)
681 }
682
683 #[test]
684 fn test_nonnative_many_adds() -> Result<()> {
685 type FF = Secp256K1Base;
686 const D: usize = 2;
687 type C = PoseidonGoldilocksConfig;
688 type F = <C as GenericConfig<D>>::F;
689
690 let a_ff = FF::rand();
691 let b_ff = FF::rand();
692 let c_ff = FF::rand();
693 let d_ff = FF::rand();
694 let e_ff = FF::rand();
695 let f_ff = FF::rand();
696 let g_ff = FF::rand();
697 let h_ff = FF::rand();
698 let sum_ff = a_ff + b_ff + c_ff + d_ff + e_ff + f_ff + g_ff + h_ff;
699
700 let config = CircuitConfig::standard_ecc_config();
701 let pw = PartialWitness::new();
702 let mut builder = CircuitBuilder::<F, D>::new(config);
703
704 let a = builder.constant_nonnative(a_ff);
705 let b = builder.constant_nonnative(b_ff);
706 let c = builder.constant_nonnative(c_ff);
707 let d = builder.constant_nonnative(d_ff);
708 let e = builder.constant_nonnative(e_ff);
709 let f = builder.constant_nonnative(f_ff);
710 let g = builder.constant_nonnative(g_ff);
711 let h = builder.constant_nonnative(h_ff);
712 let all = [a, b, c, d, e, f, g, h];
713 let sum = builder.add_many_nonnative(&all);
714
715 let sum_expected = builder.constant_nonnative(sum_ff);
716 builder.connect_nonnative(&sum, &sum_expected);
717
718 let data = builder.build::<C>();
719 let proof = data.prove(pw).unwrap();
720 data.verify(proof)
721 }
722
723 #[test]
724 fn test_nonnative_sub() -> Result<()> {
725 type FF = Secp256K1Base;
726 const D: usize = 2;
727 type C = PoseidonGoldilocksConfig;
728 type F = <C as GenericConfig<D>>::F;
729
730 let x_ff = FF::rand();
731 let mut y_ff = FF::rand();
732 while y_ff.to_canonical_biguint() > x_ff.to_canonical_biguint() {
733 y_ff = FF::rand();
734 }
735 let diff_ff = x_ff - y_ff;
736
737 let config = CircuitConfig::standard_ecc_config();
738 let pw = PartialWitness::new();
739 let mut builder = CircuitBuilder::<F, D>::new(config);
740
741 let x = builder.constant_nonnative(x_ff);
742 let y = builder.constant_nonnative(y_ff);
743 let diff = builder.sub_nonnative(&x, &y);
744
745 let diff_expected = builder.constant_nonnative(diff_ff);
746 builder.connect_nonnative(&diff, &diff_expected);
747
748 let data = builder.build::<C>();
749 let proof = data.prove(pw).unwrap();
750 data.verify(proof)
751 }
752
753 #[test]
754 fn test_nonnative_mul() -> Result<()> {
755 type FF = Secp256K1Base;
756 const D: usize = 2;
757 type C = PoseidonGoldilocksConfig;
758 type F = <C as GenericConfig<D>>::F;
759 let x_ff = FF::rand();
760 let y_ff = FF::rand();
761 let product_ff = x_ff * y_ff;
762
763 let config = CircuitConfig::standard_ecc_config();
764 let pw = PartialWitness::new();
765 let mut builder = CircuitBuilder::<F, D>::new(config);
766
767 let x = builder.constant_nonnative(x_ff);
768 let y = builder.constant_nonnative(y_ff);
769 let product = builder.mul_nonnative(&x, &y);
770
771 let product_expected = builder.constant_nonnative(product_ff);
772 builder.connect_nonnative(&product, &product_expected);
773
774 let data = builder.build::<C>();
775 let proof = data.prove(pw).unwrap();
776 data.verify(proof)
777 }
778
779 #[test]
780 fn test_nonnative_neg() -> Result<()> {
781 type FF = Secp256K1Base;
782 const D: usize = 2;
783 type C = PoseidonGoldilocksConfig;
784 type F = <C as GenericConfig<D>>::F;
785 let x_ff = FF::rand();
786 let neg_x_ff = -x_ff;
787
788 let config = CircuitConfig::standard_ecc_config();
789 let pw = PartialWitness::new();
790 let mut builder = CircuitBuilder::<F, D>::new(config);
791
792 let x = builder.constant_nonnative(x_ff);
793 let neg_x = builder.neg_nonnative(&x);
794
795 let neg_x_expected = builder.constant_nonnative(neg_x_ff);
796 builder.connect_nonnative(&neg_x, &neg_x_expected);
797
798 let data = builder.build::<C>();
799 let proof = data.prove(pw).unwrap();
800 data.verify(proof)
801 }
802
803 #[test]
804 fn test_nonnative_inv() -> Result<()> {
805 type FF = Secp256K1Base;
806 const D: usize = 2;
807 type C = PoseidonGoldilocksConfig;
808 type F = <C as GenericConfig<D>>::F;
809 let x_ff = FF::rand();
810 let inv_x_ff = x_ff.inverse();
811
812 let config = CircuitConfig::standard_ecc_config();
813 let pw = PartialWitness::new();
814 let mut builder = CircuitBuilder::<F, D>::new(config);
815
816 let x = builder.constant_nonnative(x_ff);
817 let inv_x = builder.inv_nonnative(&x);
818
819 let inv_x_expected = builder.constant_nonnative(inv_x_ff);
820 builder.connect_nonnative(&inv_x, &inv_x_expected);
821
822 let data = builder.build::<C>();
823 let proof = data.prove(pw).unwrap();
824 data.verify(proof)
825 }
826}