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