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