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