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