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