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