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