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