ark-r1cs-std/src/bits/uint.rs
src/bits/uint.rsRaw
1macro_rules! make_uint {
2 ($name:ident, $size:expr, $native:ident, $mod_name:ident, $r1cs_doc_name:expr, $native_doc_name:expr, $num_bits_doc:expr) => {
3 #[doc = "This module contains the "]
4 #[doc = $r1cs_doc_name]
5 #[doc = "type, which is the R1CS equivalent of the "]
6 #[doc = $native_doc_name]
7 #[doc = " type."]
8 pub mod $mod_name {
9 use ark_ff::{Field, One, PrimeField, Zero};
10 use core::borrow::Borrow;
11 use core::convert::TryFrom;
12 use num_bigint::BigUint;
13 use num_traits::cast::ToPrimitive;
14
15 use ark_relations::r1cs::{
16 ConstraintSystemRef, LinearCombination, Namespace, SynthesisError, Variable,
17 };
18
19 use crate::{
20 boolean::{AllocatedBool, Boolean},
21 prelude::*,
22 Assignment, Vec,
23 };
24
25 #[doc = "This struct represent an unsigned"]
26 #[doc = $num_bits_doc]
27 #[doc = " bit integer as a sequence of "]
28 #[doc = $num_bits_doc]
29 #[doc = " `Boolean`s. \n"]
30 #[doc = "This is the R1CS equivalent of the native "]
31 #[doc = $native_doc_name]
32 #[doc = " unsigned integer type."]
33 #[derive(Clone, Debug)]
34 pub struct $name<F: Field> {
35 // Least significant bit first
36 bits: [Boolean<F>; $size],
37 value: Option<$native>,
38 }
39
40 impl<F: Field> R1CSVar<F> for $name<F> {
41 type Value = $native;
42
43 fn cs(&self) -> ConstraintSystemRef<F> {
44 self.bits.as_ref().cs()
45 }
46
47 fn value(&self) -> Result<Self::Value, SynthesisError> {
48 let mut value = None;
49 for (i, bit) in self.bits.iter().enumerate() {
50 let b = $native::from(bit.value()?);
51 value = match value {
52 Some(value) => Some(value + (b << i)),
53 None => Some(b << i),
54 };
55 }
56 debug_assert_eq!(self.value, value);
57 value.get()
58 }
59 }
60
61 impl<F: Field> $name<F> {
62 #[doc = "Construct a constant "]
63 #[doc = $r1cs_doc_name]
64 #[doc = " from the native "]
65 #[doc = $native_doc_name]
66 #[doc = " type."]
67 pub fn constant(value: $native) -> Self {
68 let mut bits = [Boolean::FALSE; $size];
69
70 let mut tmp = value;
71 for i in 0..$size {
72 bits[i] = Boolean::constant((tmp & 1) == 1);
73 tmp >>= 1;
74 }
75
76 $name {
77 bits,
78 value: Some(value),
79 }
80 }
81
82 /// Turns `self` into the underlying little-endian bits.
83 pub fn to_bits_le(&self) -> Vec<Boolean<F>> {
84 self.bits.to_vec()
85 }
86
87 /// Construct `Self` from a slice of `Boolean`s.
88 ///
89 /// # Panics
90 ///
91 #[doc = "This method panics if `bits.len() != "]
92 #[doc = $num_bits_doc]
93 #[doc = "`."]
94 pub fn from_bits_le(bits: &[Boolean<F>]) -> Self {
95 assert_eq!(bits.len(), $size);
96
97 let bits = <&[Boolean<F>; $size]>::try_from(bits).unwrap().clone();
98
99 let mut value = Some(0);
100 for b in bits.iter().rev() {
101 value.as_mut().map(|v| *v <<= 1);
102
103 match *b {
104 Boolean::Constant(b) => {
105 value.as_mut().map(|v| *v |= $native::from(b));
106 },
107 Boolean::Is(ref b) => match b.value() {
108 Ok(b) => {
109 value.as_mut().map(|v| *v |= $native::from(b));
110 },
111 Err(_) => value = None,
112 },
113 Boolean::Not(ref b) => match b.value() {
114 Ok(b) => {
115 value.as_mut().map(|v| *v |= $native::from(!b));
116 },
117 Err(_) => value = None,
118 },
119 }
120 }
121
122 Self { value, bits }
123 }
124
125 /// Rotates `self` to the right by `by` steps, wrapping around.
126 #[tracing::instrument(target = "r1cs", skip(self))]
127 pub fn rotr(&self, by: usize) -> Self {
128 let mut result = self.clone();
129 let by = by % $size;
130
131 let new_bits = self.bits.iter().skip(by).chain(&self.bits).take($size);
132
133 for (res, new) in result.bits.iter_mut().zip(new_bits) {
134 *res = new.clone();
135 }
136
137 result.value = self
138 .value
139 .map(|v| v.rotate_right(u32::try_from(by).unwrap()));
140 result
141 }
142
143 /// Outputs `self ^ other`.
144 ///
145 /// If at least one of `self` and `other` are constants, then this method
146 /// *does not* create any constraints or variables.
147 #[tracing::instrument(target = "r1cs", skip(self, other))]
148 pub fn xor(&self, other: &Self) -> Result<Self, SynthesisError> {
149 let mut result = self.clone();
150 result.value = match (self.value, other.value) {
151 (Some(a), Some(b)) => Some(a ^ b),
152 _ => None,
153 };
154
155 let new_bits = self.bits.iter().zip(&other.bits).map(|(a, b)| a.xor(b));
156
157 for (res, new) in result.bits.iter_mut().zip(new_bits) {
158 *res = new?;
159 }
160
161 Ok(result)
162 }
163
164 /// Perform modular addition of `operands`.
165 ///
166 /// The user must ensure that overflow does not occur.
167 #[tracing::instrument(target = "r1cs", skip(operands))]
168 pub fn addmany(operands: &[Self]) -> Result<Self, SynthesisError>
169 where
170 F: PrimeField,
171 {
172 // Make some arbitrary bounds for ourselves to avoid overflows
173 // in the scalar field
174 assert!(F::MODULUS_BIT_SIZE >= 2 * $size);
175
176 // Support up to 128
177 assert!($size <= 128);
178
179 assert!(operands.len() >= 1);
180 assert!($size * operands.len() <= F::MODULUS_BIT_SIZE as usize);
181
182 if operands.len() == 1 {
183 return Ok(operands[0].clone());
184 }
185
186 // Compute the maximum value of the sum so we allocate enough bits for
187 // the result
188 let mut max_value =
189 BigUint::from($native::max_value()) * BigUint::from(operands.len());
190
191 // Keep track of the resulting value
192 let mut result_value = Some(BigUint::zero());
193
194 // This is a linear combination that we will enforce to be "zero"
195 let mut lc = LinearCombination::zero();
196
197 let mut all_constants = true;
198
199 // Iterate over the operands
200 for op in operands {
201 // Accumulate the value
202 match op.value {
203 Some(val) => {
204 result_value.as_mut().map(|v| *v += BigUint::from(val));
205 },
206
207 None => {
208 // If any of our operands have unknown value, we won't
209 // know the value of the result
210 result_value = None;
211 },
212 }
213
214 // Iterate over each bit_gadget of the operand and add the operand to
215 // the linear combination
216 let mut coeff = F::one();
217 for bit in &op.bits {
218 match *bit {
219 Boolean::Is(ref bit) => {
220 all_constants = false;
221
222 // Add coeff * bit_gadget
223 lc += (coeff, bit.variable());
224 },
225 Boolean::Not(ref bit) => {
226 all_constants = false;
227
228 // Add coeff * (1 - bit_gadget) = coeff * ONE - coeff * bit_gadget
229 lc = lc + (coeff, Variable::One) - (coeff, bit.variable());
230 },
231 Boolean::Constant(bit) => {
232 if bit {
233 lc += (coeff, Variable::One);
234 }
235 },
236 }
237
238 coeff.double_in_place();
239 }
240 }
241
242 // The value of the actual result is modulo 2^$size
243 let modular_value = result_value.clone().map(|v| {
244 let modulus = BigUint::from(1u64) << ($size as u32);
245 (v % modulus).to_u128().unwrap() as $native
246 });
247
248 if all_constants && modular_value.is_some() {
249 // We can just return a constant, rather than
250 // unpacking the result into allocated bits.
251
252 return Ok($name::constant(modular_value.unwrap()));
253 }
254 let cs = operands.cs();
255
256 // Storage area for the resulting bits
257 let mut result_bits = vec![];
258
259 // Allocate each bit_gadget of the result
260 let mut coeff = F::one();
261 let mut i = 0;
262 while max_value != BigUint::zero() {
263 // Allocate the bit_gadget
264 let b = AllocatedBool::new_witness(cs.clone(), || {
265 result_value
266 .clone()
267 .map(|v| (v >> i) & BigUint::one() == BigUint::one())
268 .get()
269 })?;
270
271 // Subtract this bit_gadget from the linear combination to ensure the sums
272 // balance out
273 lc = lc - (coeff, b.variable());
274
275 result_bits.push(b.into());
276
277 max_value >>= 1;
278 i += 1;
279 coeff.double_in_place();
280 }
281
282 // Enforce that the linear combination equals zero
283 cs.enforce_constraint(lc!(), lc!(), lc)?;
284
285 // Discard carry bits that we don't care about
286 result_bits.truncate($size);
287 let bits = TryFrom::try_from(result_bits).unwrap();
288
289 Ok($name {
290 bits,
291 value: modular_value,
292 })
293 }
294 }
295
296 impl<ConstraintF: Field> ToBytesGadget<ConstraintF> for $name<ConstraintF> {
297 #[tracing::instrument(target = "r1cs", skip(self))]
298 fn to_bytes(&self) -> Result<Vec<UInt8<ConstraintF>>, SynthesisError> {
299 Ok(self
300 .to_bits_le()
301 .chunks(8)
302 .map(UInt8::from_bits_le)
303 .collect())
304 }
305 }
306
307 impl<ConstraintF: Field> EqGadget<ConstraintF> for $name<ConstraintF> {
308 #[tracing::instrument(target = "r1cs", skip(self))]
309 fn is_eq(&self, other: &Self) -> Result<Boolean<ConstraintF>, SynthesisError> {
310 self.bits.as_ref().is_eq(&other.bits)
311 }
312
313 #[tracing::instrument(target = "r1cs", skip(self))]
314 fn conditional_enforce_equal(
315 &self,
316 other: &Self,
317 condition: &Boolean<ConstraintF>,
318 ) -> Result<(), SynthesisError> {
319 self.bits.conditional_enforce_equal(&other.bits, condition)
320 }
321
322 #[tracing::instrument(target = "r1cs", skip(self))]
323 fn conditional_enforce_not_equal(
324 &self,
325 other: &Self,
326 condition: &Boolean<ConstraintF>,
327 ) -> Result<(), SynthesisError> {
328 self.bits
329 .conditional_enforce_not_equal(&other.bits, condition)
330 }
331 }
332
333 impl<ConstraintF: Field> CondSelectGadget<ConstraintF> for $name<ConstraintF> {
334 #[tracing::instrument(target = "r1cs", skip(cond, true_value, false_value))]
335 fn conditionally_select(
336 cond: &Boolean<ConstraintF>,
337 true_value: &Self,
338 false_value: &Self,
339 ) -> Result<Self, SynthesisError> {
340 let selected_bits = true_value
341 .bits
342 .iter()
343 .zip(&false_value.bits)
344 .map(|(t, f)| cond.select(t, f));
345 let mut bits = [Boolean::FALSE; $size];
346 for (result, new) in bits.iter_mut().zip(selected_bits) {
347 *result = new?;
348 }
349
350 let value = cond.value().ok().and_then(|cond| {
351 if cond {
352 true_value.value().ok()
353 } else {
354 false_value.value().ok()
355 }
356 });
357 Ok(Self { bits, value })
358 }
359 }
360
361 impl<ConstraintF: Field> AllocVar<$native, ConstraintF> for $name<ConstraintF> {
362 fn new_variable<T: Borrow<$native>>(
363 cs: impl Into<Namespace<ConstraintF>>,
364 f: impl FnOnce() -> Result<T, SynthesisError>,
365 mode: AllocationMode,
366 ) -> Result<Self, SynthesisError> {
367 let ns = cs.into();
368 let cs = ns.cs();
369 let value = f().map(|f| *f.borrow()).ok();
370
371 let mut values = [None; $size];
372 if let Some(val) = value {
373 values
374 .iter_mut()
375 .enumerate()
376 .for_each(|(i, v)| *v = Some((val >> i) & 1 == 1));
377 }
378
379 let mut bits = [Boolean::FALSE; $size];
380 for (b, v) in bits.iter_mut().zip(&values) {
381 *b = Boolean::new_variable(cs.clone(), || v.get(), mode)?;
382 }
383 Ok(Self { bits, value })
384 }
385 }
386
387 #[cfg(test)]
388 mod test {
389 use super::$name;
390 use crate::{bits::boolean::Boolean, prelude::*, Vec};
391 use ark_relations::r1cs::{ConstraintSystem, SynthesisError};
392 use ark_std::rand::Rng;
393 use ark_test_curves::mnt4_753::Fr;
394
395 #[test]
396 fn test_from_bits() -> Result<(), SynthesisError> {
397 let mut rng = ark_std::test_rng();
398
399 for _ in 0..1000 {
400 let v = (0..$size)
401 .map(|_| Boolean::constant(rng.gen()))
402 .collect::<Vec<Boolean<Fr>>>();
403
404 let b = $name::from_bits_le(&v);
405
406 for (i, bit) in b.bits.iter().enumerate() {
407 match bit {
408 &Boolean::Constant(bit) => {
409 assert_eq!(bit, ((b.value()? >> i) & 1 == 1));
410 },
411 _ => unreachable!(),
412 }
413 }
414
415 let expected_to_be_same = b.to_bits_le();
416
417 for x in v.iter().zip(expected_to_be_same.iter()) {
418 match x {
419 (&Boolean::Constant(true), &Boolean::Constant(true)) => {},
420 (&Boolean::Constant(false), &Boolean::Constant(false)) => {},
421 _ => unreachable!(),
422 }
423 }
424 }
425 Ok(())
426 }
427
428 #[test]
429 fn test_xor() -> Result<(), SynthesisError> {
430 use Boolean::*;
431 let mut rng = ark_std::test_rng();
432
433 for _ in 0..1000 {
434 let cs = ConstraintSystem::<Fr>::new_ref();
435
436 let a: $native = rng.gen();
437 let b: $native = rng.gen();
438 let c: $native = rng.gen();
439
440 let mut expected = a ^ b ^ c;
441
442 let a_bit = $name::new_witness(cs.clone(), || Ok(a))?;
443 let b_bit = $name::constant(b);
444 let c_bit = $name::new_witness(cs.clone(), || Ok(c))?;
445
446 let r = a_bit.xor(&b_bit).unwrap();
447 let r = r.xor(&c_bit).unwrap();
448
449 assert!(cs.is_satisfied().unwrap());
450
451 assert!(r.value == Some(expected));
452
453 for b in r.bits.iter() {
454 match b {
455 Is(b) => assert_eq!(b.value()?, (expected & 1 == 1)),
456 Not(b) => assert_eq!(!b.value()?, (expected & 1 == 1)),
457 Constant(b) => assert_eq!(*b, (expected & 1 == 1)),
458 }
459
460 expected >>= 1;
461 }
462 }
463 Ok(())
464 }
465
466 #[test]
467 fn test_addmany_constants() -> Result<(), SynthesisError> {
468 let mut rng = ark_std::test_rng();
469
470 for _ in 0..1000 {
471 let cs = ConstraintSystem::<Fr>::new_ref();
472
473 let a: $native = rng.gen();
474 let b: $native = rng.gen();
475 let c: $native = rng.gen();
476
477 let a_bit = $name::new_constant(cs.clone(), a)?;
478 let b_bit = $name::new_constant(cs.clone(), b)?;
479 let c_bit = $name::new_constant(cs.clone(), c)?;
480
481 let mut expected = a.wrapping_add(b).wrapping_add(c);
482
483 let r = $name::addmany(&[a_bit, b_bit, c_bit]).unwrap();
484
485 assert!(r.value == Some(expected));
486
487 for b in r.bits.iter() {
488 match b {
489 Boolean::Is(_) => unreachable!(),
490 Boolean::Not(_) => unreachable!(),
491 Boolean::Constant(b) => assert_eq!(*b, (expected & 1 == 1)),
492 }
493
494 expected >>= 1;
495 }
496 }
497 Ok(())
498 }
499
500 #[test]
501 fn test_addmany() -> Result<(), SynthesisError> {
502 let mut rng = ark_std::test_rng();
503
504 for _ in 0..1000 {
505 let cs = ConstraintSystem::<Fr>::new_ref();
506
507 let a: $native = rng.gen();
508 let b: $native = rng.gen();
509 let c: $native = rng.gen();
510 let d: $native = rng.gen();
511
512 let mut expected = (a ^ b).wrapping_add(c).wrapping_add(d);
513
514 let a_bit = $name::new_witness(ark_relations::ns!(cs, "a_bit"), || Ok(a))?;
515 let b_bit = $name::constant(b);
516 let c_bit = $name::constant(c);
517 let d_bit = $name::new_witness(ark_relations::ns!(cs, "d_bit"), || Ok(d))?;
518
519 let r = a_bit.xor(&b_bit).unwrap();
520 let r = $name::addmany(&[r, c_bit, d_bit]).unwrap();
521
522 assert!(cs.is_satisfied().unwrap());
523 assert!(r.value == Some(expected));
524
525 for b in r.bits.iter() {
526 match b {
527 Boolean::Is(b) => assert_eq!(b.value()?, (expected & 1 == 1)),
528 Boolean::Not(b) => assert_eq!(!b.value()?, (expected & 1 == 1)),
529 Boolean::Constant(_) => unreachable!(),
530 }
531
532 expected >>= 1;
533 }
534 }
535 Ok(())
536 }
537
538 #[test]
539 fn test_rotr() -> Result<(), SynthesisError> {
540 let mut rng = ark_std::test_rng();
541
542 let mut num = rng.gen();
543
544 let a: $name<Fr> = $name::constant(num);
545
546 for i in 0..$size {
547 let b = a.rotr(i);
548
549 assert!(b.value.unwrap() == num);
550
551 let mut tmp = num;
552 for b in &b.bits {
553 match b {
554 Boolean::Constant(b) => assert_eq!(*b, tmp & 1 == 1),
555 _ => unreachable!(),
556 }
557
558 tmp >>= 1;
559 }
560
561 num = num.rotate_right(1);
562 }
563 Ok(())
564 }
565 }
566 }
567 };
568}