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