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