plonky2-ecdsa/src/gadgets/biguint.rs
src/gadgets/biguint.rsRaw
1use alloc::string::String;
2use alloc::vec;
3use alloc::vec::Vec;
4use anyhow::Result;
5use core::marker::PhantomData;
6use plonky2::plonk::circuit_data::CommonCircuitData;
7use plonky2::util::serialization::{IoResult, Read, Write};
8
9use num::{BigUint, Integer, Zero};
10use plonky2::field::extension::Extendable;
11use plonky2::field::types::{PrimeField, PrimeField64};
12use plonky2::hash::hash_types::RichField;
13use plonky2::iop::generator::{GeneratedValues, SimpleGenerator};
14use plonky2::iop::target::{BoolTarget, Target};
15use plonky2::iop::witness::{PartitionWitness, Witness};
16use plonky2::plonk::circuit_builder::CircuitBuilder;
17use plonky2_u32::gadgets::arithmetic_u32::{CircuitBuilderU32, U32Target};
18use plonky2_u32::gadgets::multiple_comparison::list_le_u32_circuit;
19use plonky2_u32::witness::{GeneratedValuesU32, WitnessU32};
20
21#[derive(Clone, Debug)]
22pub struct BigUintTarget {
23 pub limbs: Vec<U32Target>,
24}
25
26impl BigUintTarget {
27 pub fn num_limbs(&self) -> usize {
28 self.limbs.len()
29 }
30
31 pub fn get_limb(&self, i: usize) -> U32Target {
32 self.limbs[i]
33 }
34
35 pub fn to_target_vec(&self) -> Vec<Target> {
36 self.limbs.iter().map(|t| t.0).collect()
37 }
38
39 pub fn from_target_vec(ts: &[Target]) -> Self {
40 Self {
41 limbs: ts.iter().map(|t| U32Target(*t)).collect(),
42 }
43 }
44}
45
46pub trait CircuitBuilderBiguint<F: RichField + Extendable<D>, const D: usize> {
47 fn constant_biguint(&mut self, value: &BigUint) -> BigUintTarget;
48
49 fn zero_biguint(&mut self) -> BigUintTarget;
50
51 fn connect_biguint(&mut self, lhs: &BigUintTarget, rhs: &BigUintTarget);
52
53 fn pad_biguints(
54 &mut self,
55 a: &BigUintTarget,
56 b: &BigUintTarget,
57 ) -> (BigUintTarget, BigUintTarget);
58
59 fn cmp_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BoolTarget;
60
61 fn add_virtual_biguint_target(&mut self, num_limbs: usize) -> BigUintTarget;
62
63 /// Add two `BigUintTarget`s.
64 fn add_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BigUintTarget;
65
66 /// Subtract two `BigUintTarget`s. We assume that the first is larger than the second.
67 fn sub_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BigUintTarget;
68
69 fn mul_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BigUintTarget;
70
71 fn mul_biguint_by_bool(&mut self, a: &BigUintTarget, b: BoolTarget) -> BigUintTarget;
72
73 /// Returns x * y + z. This is no more efficient than mul-then-add; it's purely for convenience (only need to call one CircuitBuilder function).
74 fn mul_add_biguint(
75 &mut self,
76 x: &BigUintTarget,
77 y: &BigUintTarget,
78 z: &BigUintTarget,
79 ) -> BigUintTarget;
80
81 fn div_rem_biguint(
82 &mut self,
83 a: &BigUintTarget,
84 b: &BigUintTarget,
85 ) -> (BigUintTarget, BigUintTarget);
86
87 fn div_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BigUintTarget;
88
89 fn rem_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BigUintTarget;
90}
91
92impl<F: RichField + Extendable<D>, const D: usize> CircuitBuilderBiguint<F, D>
93 for CircuitBuilder<F, D>
94{
95 fn constant_biguint(&mut self, value: &BigUint) -> BigUintTarget {
96 let limb_values = value.to_u32_digits();
97 let limbs = limb_values.iter().map(|&l| self.constant_u32(l)).collect();
98
99 BigUintTarget { limbs }
100 }
101
102 fn zero_biguint(&mut self) -> BigUintTarget {
103 self.constant_biguint(&BigUint::zero())
104 }
105
106 fn connect_biguint(&mut self, lhs: &BigUintTarget, rhs: &BigUintTarget) {
107 let min_limbs = lhs.num_limbs().min(rhs.num_limbs());
108 for i in 0..min_limbs {
109 self.connect_u32(lhs.get_limb(i), rhs.get_limb(i));
110 }
111
112 for i in min_limbs..lhs.num_limbs() {
113 self.assert_zero_u32(lhs.get_limb(i));
114 }
115 for i in min_limbs..rhs.num_limbs() {
116 self.assert_zero_u32(rhs.get_limb(i));
117 }
118 }
119
120 fn pad_biguints(
121 &mut self,
122 a: &BigUintTarget,
123 b: &BigUintTarget,
124 ) -> (BigUintTarget, BigUintTarget) {
125 if a.num_limbs() > b.num_limbs() {
126 let mut padded_b = b.clone();
127 for _ in b.num_limbs()..a.num_limbs() {
128 padded_b.limbs.push(self.zero_u32());
129 }
130
131 (a.clone(), padded_b)
132 } else {
133 let mut padded_a = a.clone();
134 for _ in a.num_limbs()..b.num_limbs() {
135 padded_a.limbs.push(self.zero_u32());
136 }
137
138 (padded_a, b.clone())
139 }
140 }
141
142 fn cmp_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BoolTarget {
143 let (a, b) = self.pad_biguints(a, b);
144
145 list_le_u32_circuit(self, a.limbs, b.limbs)
146 }
147
148 fn add_virtual_biguint_target(&mut self, num_limbs: usize) -> BigUintTarget {
149 let limbs = self.add_virtual_u32_targets(num_limbs);
150
151 BigUintTarget { limbs }
152 }
153
154 fn add_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BigUintTarget {
155 let num_limbs = a.num_limbs().max(b.num_limbs());
156
157 let mut combined_limbs = vec![];
158 let mut carry = self.zero_u32();
159 for i in 0..num_limbs {
160 let a_limb = (i < a.num_limbs())
161 .then(|| a.limbs[i])
162 .unwrap_or_else(|| self.zero_u32());
163 let b_limb = (i < b.num_limbs())
164 .then(|| b.limbs[i])
165 .unwrap_or_else(|| self.zero_u32());
166
167 let (new_limb, new_carry) = self.add_many_u32(&[carry, a_limb, b_limb]);
168 carry = new_carry;
169 combined_limbs.push(new_limb);
170 }
171 combined_limbs.push(carry);
172
173 BigUintTarget {
174 limbs: combined_limbs,
175 }
176 }
177
178 fn sub_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BigUintTarget {
179 let (a, b) = self.pad_biguints(a, b);
180 let num_limbs = a.limbs.len();
181
182 let mut result_limbs = vec![];
183
184 let mut borrow = self.zero_u32();
185 for i in 0..num_limbs {
186 let (result, new_borrow) = self.sub_u32(a.limbs[i], b.limbs[i], borrow);
187 result_limbs.push(result);
188 borrow = new_borrow;
189 }
190 // Borrow should be zero here.
191
192 BigUintTarget {
193 limbs: result_limbs,
194 }
195 }
196
197 fn mul_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BigUintTarget {
198 let total_limbs = a.limbs.len() + b.limbs.len();
199
200 let mut to_add = vec![vec![]; total_limbs];
201 for i in 0..a.limbs.len() {
202 for j in 0..b.limbs.len() {
203 let (product, carry) = self.mul_u32(a.limbs[i], b.limbs[j]);
204 to_add[i + j].push(product);
205 to_add[i + j + 1].push(carry);
206 }
207 }
208
209 let mut combined_limbs = vec![];
210 let mut carry = self.zero_u32();
211 for summands in &mut to_add {
212 let (new_result, new_carry) = self.add_u32s_with_carry(summands, carry);
213 combined_limbs.push(new_result);
214 carry = new_carry;
215 }
216 combined_limbs.push(carry);
217
218 BigUintTarget {
219 limbs: combined_limbs,
220 }
221 }
222
223 fn mul_biguint_by_bool(&mut self, a: &BigUintTarget, b: BoolTarget) -> BigUintTarget {
224 let t = b.target;
225
226 BigUintTarget {
227 limbs: a
228 .limbs
229 .iter()
230 .map(|&l| U32Target(self.mul(l.0, t)))
231 .collect(),
232 }
233 }
234
235 fn mul_add_biguint(
236 &mut self,
237 x: &BigUintTarget,
238 y: &BigUintTarget,
239 z: &BigUintTarget,
240 ) -> BigUintTarget {
241 let prod = self.mul_biguint(x, y);
242 self.add_biguint(&prod, z)
243 }
244
245 fn div_rem_biguint(
246 &mut self,
247 a: &BigUintTarget,
248 b: &BigUintTarget,
249 ) -> (BigUintTarget, BigUintTarget) {
250 let a_len = a.limbs.len();
251 let b_len = b.limbs.len();
252 let div_num_limbs = if b_len > a_len + 1 {
253 0
254 } else {
255 a_len - b_len + 1
256 };
257 let div = self.add_virtual_biguint_target(div_num_limbs);
258 let rem = self.add_virtual_biguint_target(b_len);
259
260 self.add_simple_generator(BigUintDivRemGenerator::<F, D> {
261 a: a.clone(),
262 b: b.clone(),
263 div: div.clone(),
264 rem: rem.clone(),
265 _phantom: PhantomData,
266 });
267
268 let div_b = self.mul_biguint(&div, b);
269 let div_b_plus_rem = self.add_biguint(&div_b, &rem);
270 self.connect_biguint(a, &div_b_plus_rem);
271
272 let cmp_rem_b = self.cmp_biguint(&rem, b);
273 self.assert_one(cmp_rem_b.target);
274
275 (div, rem)
276 }
277
278 fn div_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BigUintTarget {
279 let (div, _rem) = self.div_rem_biguint(a, b);
280 div
281 }
282
283 fn rem_biguint(&mut self, a: &BigUintTarget, b: &BigUintTarget) -> BigUintTarget {
284 let (_div, rem) = self.div_rem_biguint(a, b);
285 rem
286 }
287}
288
289pub trait WitnessBigUint<F: PrimeField64>: Witness<F> {
290 fn get_biguint_target(&self, target: BigUintTarget) -> BigUint;
291 fn set_biguint_target(&mut self, target: &BigUintTarget, value: &BigUint) -> Result<()>;
292}
293
294impl<T: Witness<F>, F: PrimeField64> WitnessBigUint<F> for T {
295 fn get_biguint_target(&self, target: BigUintTarget) -> BigUint {
296 target
297 .limbs
298 .into_iter()
299 .rev()
300 .fold(BigUint::zero(), |acc, limb| {
301 (acc << 32) + self.get_target(limb.0).to_canonical_biguint()
302 })
303 }
304
305 fn set_biguint_target(&mut self, target: &BigUintTarget, value: &BigUint) -> Result<()> {
306 let mut limbs = value.to_u32_digits();
307 assert!(target.num_limbs() >= limbs.len());
308 limbs.resize(target.num_limbs(), 0);
309 for i in 0..target.num_limbs() {
310 self.set_u32_target(target.limbs[i], limbs[i])?;
311 }
312
313 Ok(())
314 }
315}
316
317pub trait GeneratedValuesBigUint<F: PrimeField> {
318 fn set_biguint_target(&mut self, target: &BigUintTarget, value: &BigUint) -> Result<()>;
319}
320
321impl<F: PrimeField> GeneratedValuesBigUint<F> for GeneratedValues<F> {
322 fn set_biguint_target(&mut self, target: &BigUintTarget, value: &BigUint) -> Result<()> {
323 let mut limbs = value.to_u32_digits();
324 assert!(target.num_limbs() >= limbs.len());
325 limbs.resize(target.num_limbs(), 0);
326 for i in 0..target.num_limbs() {
327 self.set_u32_target(target.get_limb(i), limbs[i])?;
328 }
329
330 Ok(())
331 }
332}
333
334#[derive(Debug)]
335struct BigUintDivRemGenerator<F: RichField + Extendable<D>, const D: usize> {
336 a: BigUintTarget,
337 b: BigUintTarget,
338 div: BigUintTarget,
339 rem: BigUintTarget,
340 _phantom: PhantomData<F>,
341}
342
343impl<F: RichField + Extendable<D>, const D: usize> SimpleGenerator<F, D>
344 for BigUintDivRemGenerator<F, D>
345{
346 fn id(&self) -> String {
347 "BigUintDivRemGenerator".into()
348 }
349
350 fn dependencies(&self) -> Vec<Target> {
351 self.a
352 .limbs
353 .iter()
354 .chain(&self.b.limbs)
355 .map(|&l| l.0)
356 .collect()
357 }
358
359 fn run_once(
360 &self,
361 witness: &PartitionWitness<F>,
362 out_buffer: &mut GeneratedValues<F>,
363 ) -> Result<()> {
364 let a = witness.get_biguint_target(self.a.clone());
365 let b = witness.get_biguint_target(self.b.clone());
366 let (div, rem) = a.div_rem(&b);
367
368 out_buffer.set_biguint_target(&self.div, &div)?;
369 out_buffer.set_biguint_target(&self.rem, &rem)
370 }
371
372 fn serialize(&self, dst: &mut Vec<u8>, _common_data: &CommonCircuitData<F, D>) -> IoResult<()> {
373 // Serialise each biguint target's limbs.
374 dst.write_target_vec(&self.a.to_target_vec())?;
375 dst.write_target_vec(&self.b.to_target_vec())?;
376 dst.write_target_vec(&self.div.to_target_vec())?;
377 dst.write_target_vec(&self.rem.to_target_vec())
378 }
379
380 fn deserialize(
381 src: &mut plonky2::util::serialization::Buffer,
382 _common_data: &CommonCircuitData<F, D>,
383 ) -> IoResult<Self>
384 where
385 Self: Sized,
386 {
387 let a = BigUintTarget::from_target_vec(&src.read_target_vec()?);
388 let b = BigUintTarget::from_target_vec(&src.read_target_vec()?);
389 let div = BigUintTarget::from_target_vec(&src.read_target_vec()?);
390 let rem = BigUintTarget::from_target_vec(&src.read_target_vec()?);
391
392 Ok(Self {
393 a,
394 b,
395 div,
396 rem,
397 _phantom: PhantomData,
398 })
399 }
400}
401
402#[cfg(test)]
403mod tests {
404 use anyhow::Result;
405 use num::{BigUint, FromPrimitive, Integer};
406 use plonky2::iop::witness::PartialWitness;
407 use plonky2::plonk::circuit_builder::CircuitBuilder;
408 use plonky2::plonk::circuit_data::CircuitConfig;
409 use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};
410 use rand::rngs::OsRng;
411 use rand::Rng;
412
413 use crate::gadgets::biguint::{CircuitBuilderBiguint, WitnessBigUint};
414
415 #[test]
416 fn test_biguint_add() -> Result<()> {
417 const D: usize = 2;
418 type C = PoseidonGoldilocksConfig;
419 type F = <C as GenericConfig<D>>::F;
420 let mut rng = OsRng;
421
422 let x_value = BigUint::from_u128(rng.gen()).unwrap();
423 let y_value = BigUint::from_u128(rng.gen()).unwrap();
424 let expected_z_value = &x_value + &y_value;
425
426 let config = CircuitConfig::standard_recursion_config();
427 let mut pw = PartialWitness::new();
428 let mut builder = CircuitBuilder::<F, D>::new(config);
429
430 let x = builder.add_virtual_biguint_target(x_value.to_u32_digits().len());
431 let y = builder.add_virtual_biguint_target(y_value.to_u32_digits().len());
432 let z = builder.add_biguint(&x, &y);
433 let expected_z = builder.add_virtual_biguint_target(expected_z_value.to_u32_digits().len());
434 builder.connect_biguint(&z, &expected_z);
435
436 pw.set_biguint_target(&x, &x_value)?;
437 pw.set_biguint_target(&y, &y_value)?;
438 pw.set_biguint_target(&expected_z, &expected_z_value)?;
439
440 let data = builder.build::<C>();
441 let proof = data.prove(pw).unwrap();
442 data.verify(proof)
443 }
444
445 #[test]
446 fn test_biguint_sub() -> Result<()> {
447 const D: usize = 2;
448 type C = PoseidonGoldilocksConfig;
449 type F = <C as GenericConfig<D>>::F;
450 let mut rng = OsRng;
451
452 let mut x_value = BigUint::from_u128(rng.gen()).unwrap();
453 let mut y_value = BigUint::from_u128(rng.gen()).unwrap();
454 if y_value > x_value {
455 (x_value, y_value) = (y_value, x_value);
456 }
457 let expected_z_value = &x_value - &y_value;
458
459 let config = CircuitConfig::standard_recursion_config();
460 let pw = PartialWitness::new();
461 let mut builder = CircuitBuilder::<F, D>::new(config);
462
463 let x = builder.constant_biguint(&x_value);
464 let y = builder.constant_biguint(&y_value);
465 let z = builder.sub_biguint(&x, &y);
466 let expected_z = builder.constant_biguint(&expected_z_value);
467
468 builder.connect_biguint(&z, &expected_z);
469
470 let data = builder.build::<C>();
471 let proof = data.prove(pw).unwrap();
472 data.verify(proof)
473 }
474
475 #[test]
476 fn test_biguint_mul() -> Result<()> {
477 const D: usize = 2;
478 type C = PoseidonGoldilocksConfig;
479 type F = <C as GenericConfig<D>>::F;
480 let mut rng = OsRng;
481
482 let x_value = BigUint::from_u128(rng.gen()).unwrap();
483 let y_value = BigUint::from_u128(rng.gen()).unwrap();
484 let expected_z_value = &x_value * &y_value;
485
486 let config = CircuitConfig::standard_recursion_config();
487 let mut pw = PartialWitness::new();
488 let mut builder = CircuitBuilder::<F, D>::new(config);
489
490 let x = builder.add_virtual_biguint_target(x_value.to_u32_digits().len());
491 let y = builder.add_virtual_biguint_target(y_value.to_u32_digits().len());
492 let z = builder.mul_biguint(&x, &y);
493 let expected_z = builder.add_virtual_biguint_target(expected_z_value.to_u32_digits().len());
494 builder.connect_biguint(&z, &expected_z);
495
496 pw.set_biguint_target(&x, &x_value)?;
497 pw.set_biguint_target(&y, &y_value)?;
498 pw.set_biguint_target(&expected_z, &expected_z_value)?;
499
500 let data = builder.build::<C>();
501 let proof = data.prove(pw).unwrap();
502 data.verify(proof)
503 }
504
505 #[test]
506 fn test_biguint_cmp() -> Result<()> {
507 const D: usize = 2;
508 type C = PoseidonGoldilocksConfig;
509 type F = <C as GenericConfig<D>>::F;
510 let mut rng = OsRng;
511
512 let x_value = BigUint::from_u128(rng.gen()).unwrap();
513 let y_value = BigUint::from_u128(rng.gen()).unwrap();
514
515 let config = CircuitConfig::standard_recursion_config();
516 let pw = PartialWitness::new();
517 let mut builder = CircuitBuilder::<F, D>::new(config);
518
519 let x = builder.constant_biguint(&x_value);
520 let y = builder.constant_biguint(&y_value);
521 let cmp = builder.cmp_biguint(&x, &y);
522 let expected_cmp = builder.constant_bool(x_value <= y_value);
523
524 builder.connect(cmp.target, expected_cmp.target);
525
526 let data = builder.build::<C>();
527 let proof = data.prove(pw).unwrap();
528 data.verify(proof)
529 }
530
531 #[test]
532 fn test_biguint_div_rem() -> Result<()> {
533 const D: usize = 2;
534 type C = PoseidonGoldilocksConfig;
535 type F = <C as GenericConfig<D>>::F;
536 let mut rng = OsRng;
537
538 let mut x_value = BigUint::from_u128(rng.gen()).unwrap();
539 let mut y_value = BigUint::from_u128(rng.gen()).unwrap();
540 if y_value > x_value {
541 (x_value, y_value) = (y_value, x_value);
542 }
543 let (expected_div_value, expected_rem_value) = x_value.div_rem(&y_value);
544
545 let config = CircuitConfig::standard_recursion_config();
546 let pw = PartialWitness::new();
547 let mut builder = CircuitBuilder::<F, D>::new(config);
548
549 let x = builder.constant_biguint(&x_value);
550 let y = builder.constant_biguint(&y_value);
551 let (div, rem) = builder.div_rem_biguint(&x, &y);
552
553 let expected_div = builder.constant_biguint(&expected_div_value);
554 let expected_rem = builder.constant_biguint(&expected_rem_value);
555
556 builder.connect_biguint(&div, &expected_div);
557 builder.connect_biguint(&rem, &expected_rem);
558
559 let data = builder.build::<C>();
560 let proof = data.prove(pw).unwrap();
561 data.verify(proof)
562 }
563}