use ff::PrimeField;
use bellpepper_core::{ConstraintSystem, LinearCombination, SynthesisError};
use super::boolean::{AllocatedBit, Boolean};
use super::multieq::MultiEq;
#[derive(Clone)]
pub struct UInt32 {
bits: Vec<Boolean>,
value: Option<u32>,
}
impl UInt32 {
pub fn constant(value: u32) -> Self {
let mut bits = Vec::with_capacity(32);
let mut tmp = value;
for _ in 0..32 {
if tmp & 1 == 1 {
bits.push(Boolean::constant(true))
} else {
bits.push(Boolean::constant(false))
}
tmp >>= 1;
}
UInt32 {
bits,
value: Some(value),
}
}
pub fn alloc<Scalar, CS>(mut cs: CS, value: Option<u32>) -> Result<Self, SynthesisError>
where
Scalar: PrimeField,
CS: ConstraintSystem<Scalar>,
{
let values = match value {
Some(mut val) => {
let mut v = Vec::with_capacity(32);
for _ in 0..32 {
v.push(Some(val & 1 == 1));
val >>= 1;
}
v
}
None => vec![None; 32],
};
let bits = values
.into_iter()
.enumerate()
.map(|(i, v)| {
Ok(Boolean::from(AllocatedBit::alloc(
cs.namespace(|| format!("allocated bit {}", i)),
v,
)?))
})
.collect::<Result<Vec<_>, SynthesisError>>()?;
Ok(UInt32 { bits, value })
}
pub fn into_bits_be(self) -> Vec<Boolean> {
let mut ret = self.bits;
ret.reverse();
ret
}
pub fn from_bits_be(bits: &[Boolean]) -> Self {
assert_eq!(bits.len(), 32);
let mut value = Some(0u32);
for b in bits {
if let Some(v) = value.as_mut() {
*v <<= 1;
}
match b.get_value() {
Some(true) => {
if let Some(v) = value.as_mut() {
*v |= 1;
}
}
Some(false) => {}
None => {
value = None;
}
}
}
UInt32 {
value,
bits: bits.iter().rev().cloned().collect(),
}
}
pub fn into_bits(self) -> Vec<Boolean> {
self.bits
}
pub fn from_bits(bits: &[Boolean]) -> Self {
assert_eq!(bits.len(), 32);
let new_bits = bits.to_vec();
let mut value = Some(0u32);
for b in new_bits.iter().rev() {
if let Some(v) = value.as_mut() {
*v <<= 1;
}
match *b {
Boolean::Constant(b) => {
if b {
if let Some(v) = value.as_mut() {
*v |= 1;
}
}
}
Boolean::Is(ref b) => match b.get_value() {
Some(true) => {
if let Some(v) = value.as_mut() {
*v |= 1;
}
}
Some(false) => {}
None => value = None,
},
Boolean::Not(ref b) => match b.get_value() {
Some(false) => {
if let Some(v) = value.as_mut() {
*v |= 1;
}
}
Some(true) => {}
None => value = None,
},
}
}
UInt32 {
value,
bits: new_bits,
}
}
pub fn rotr(&self, by: usize) -> Self {
let by = by % 32;
let new_bits = self
.bits
.iter()
.skip(by)
.chain(self.bits.iter())
.take(32)
.cloned()
.collect();
UInt32 {
bits: new_bits,
value: self.value.map(|v| v.rotate_right(by as u32)),
}
}
pub fn shr(&self, by: usize) -> Self {
let by = by % 32;
let fill = Boolean::constant(false);
let new_bits = self
.bits
.iter() .skip(by) .chain(Some(&fill).into_iter().cycle()) .take(32) .cloned()
.collect();
UInt32 {
bits: new_bits,
value: self.value.map(|v| v >> by as u32),
}
}
fn triop<Scalar, CS, F, U>(
mut cs: CS,
a: &Self,
b: &Self,
c: &Self,
tri_fn: F,
circuit_fn: U,
) -> Result<Self, SynthesisError>
where
Scalar: PrimeField,
CS: ConstraintSystem<Scalar>,
F: Fn(u32, u32, u32) -> u32,
U: Fn(&mut CS, usize, &Boolean, &Boolean, &Boolean) -> Result<Boolean, SynthesisError>,
{
let new_value = match (a.value, b.value, c.value) {
(Some(a), Some(b), Some(c)) => Some(tri_fn(a, b, c)),
_ => None,
};
let bits = a
.bits
.iter()
.zip(b.bits.iter())
.zip(c.bits.iter())
.enumerate()
.map(|(i, ((a, b), c))| circuit_fn(&mut cs, i, a, b, c))
.collect::<Result<_, _>>()?;
Ok(UInt32 {
bits,
value: new_value,
})
}
pub fn sha256_maj<Scalar, CS>(
cs: CS,
a: &Self,
b: &Self,
c: &Self,
) -> Result<Self, SynthesisError>
where
Scalar: PrimeField,
CS: ConstraintSystem<Scalar>,
{
Self::triop(
cs,
a,
b,
c,
|a, b, c| (a & b) ^ (a & c) ^ (b & c),
|cs, i, a, b, c| Boolean::sha256_maj(cs.namespace(|| format!("maj {}", i)), a, b, c),
)
}
pub fn sha256_ch<Scalar, CS>(
cs: CS,
a: &Self,
b: &Self,
c: &Self,
) -> Result<Self, SynthesisError>
where
Scalar: PrimeField,
CS: ConstraintSystem<Scalar>,
{
Self::triop(
cs,
a,
b,
c,
|a, b, c| (a & b) ^ ((!a) & c),
|cs, i, a, b, c| Boolean::sha256_ch(cs.namespace(|| format!("ch {}", i)), a, b, c),
)
}
pub fn xor<Scalar, CS>(&self, mut cs: CS, other: &Self) -> Result<Self, SynthesisError>
where
Scalar: PrimeField,
CS: ConstraintSystem<Scalar>,
{
let new_value = match (self.value, other.value) {
(Some(a), Some(b)) => Some(a ^ b),
_ => None,
};
let bits = self
.bits
.iter()
.zip(other.bits.iter())
.enumerate()
.map(|(i, (a, b))| Boolean::xor(cs.namespace(|| format!("xor of bit {}", i)), a, b))
.collect::<Result<_, _>>()?;
Ok(UInt32 {
bits,
value: new_value,
})
}
#[allow(clippy::unnecessary_unwrap)]
pub fn addmany<Scalar, CS, M>(mut cs: M, operands: &[Self]) -> Result<Self, SynthesisError>
where
Scalar: PrimeField,
CS: ConstraintSystem<Scalar>,
M: ConstraintSystem<Scalar, Root = MultiEq<Scalar, CS>>,
{
assert!(Scalar::NUM_BITS >= 64);
assert!(operands.len() >= 2); assert!(operands.len() <= 10);
let mut max_value = (operands.len() as u64) * (u64::from(u32::max_value()));
let mut result_value = Some(0u64);
let mut lc = LinearCombination::zero();
let mut all_constants = true;
for op in operands {
match op.value {
Some(val) => {
if let Some(v) = result_value.as_mut() {
*v += u64::from(val);
}
}
None => {
result_value = None;
}
}
let mut coeff = Scalar::ONE;
for bit in &op.bits {
lc = lc + &bit.lc(CS::one(), coeff);
all_constants &= bit.is_constant();
coeff = coeff.double();
}
}
let modular_value = result_value.map(|v| v as u32);
if all_constants && modular_value.is_some() {
return Ok(UInt32::constant(modular_value.unwrap()));
}
let mut result_bits = vec![];
let mut result_lc = LinearCombination::zero();
let mut coeff = Scalar::ONE;
let mut i = 0;
while max_value != 0 {
let b = AllocatedBit::alloc(
cs.namespace(|| format!("result bit {}", i)),
result_value.map(|v| (v >> i) & 1 == 1),
)?;
result_lc = result_lc + (coeff, b.get_variable());
result_bits.push(b.into());
max_value >>= 1;
i += 1;
coeff = coeff.double();
}
cs.get_root().enforce_equal(i, &lc, &result_lc);
result_bits.truncate(32);
Ok(UInt32 {
bits: result_bits,
value: modular_value,
})
}
}
#[cfg(test)]
mod test {
use super::UInt32;
use crate::gadgets::boolean::Boolean;
use crate::gadgets::multieq::MultiEq;
use bellpepper_core::test_cs::*;
use bellpepper_core::ConstraintSystem;
use blstrs::Scalar as Fr;
use ff::Field;
use rand_core::{RngCore, SeedableRng};
use rand_xorshift::XorShiftRng;
#[test]
fn test_uint32_from_bits_be() {
let mut rng = XorShiftRng::from_seed([
0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06,
0xbc, 0xe5,
]);
for _ in 0..1000 {
let v = (0..32)
.map(|_| Boolean::constant(rng.next_u32() % 2 != 0))
.collect::<Vec<_>>();
let b = UInt32::from_bits_be(&v);
for (i, bit) in b.bits.iter().enumerate() {
match *bit {
Boolean::Constant(bit) => {
assert!(bit == ((b.value.unwrap() >> i) & 1 == 1));
}
_ => unreachable!(),
}
}
let expected_to_be_same = b.into_bits_be();
for x in v.iter().zip(expected_to_be_same.iter()) {
match x {
(&Boolean::Constant(true), &Boolean::Constant(true)) => {}
(&Boolean::Constant(false), &Boolean::Constant(false)) => {}
_ => unreachable!(),
}
}
}
}
#[test]
fn test_uint32_from_bits() {
let mut rng = XorShiftRng::from_seed([
0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06,
0xbc, 0xe5,
]);
for _ in 0..1000 {
let v = (0..32)
.map(|_| Boolean::constant(rng.next_u32() % 2 != 0))
.collect::<Vec<_>>();
let b = UInt32::from_bits(&v);
for (i, bit) in b.bits.iter().enumerate() {
match *bit {
Boolean::Constant(bit) => {
assert!(bit == ((b.value.unwrap() >> i) & 1 == 1));
}
_ => unreachable!(),
}
}
let expected_to_be_same = b.into_bits();
for x in v.iter().zip(expected_to_be_same.iter()) {
match x {
(&Boolean::Constant(true), &Boolean::Constant(true)) => {}
(&Boolean::Constant(false), &Boolean::Constant(false)) => {}
_ => unreachable!(),
}
}
}
}
#[test]
fn test_uint32_xor() {
let mut rng = XorShiftRng::from_seed([
0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06,
0xbc, 0xe5,
]);
for _ in 0..1000 {
let mut cs = TestConstraintSystem::<Fr>::new();
let a = rng.next_u32();
let b = rng.next_u32();
let c = rng.next_u32();
let mut expected = a ^ b ^ c;
let a_bit = UInt32::alloc(cs.namespace(|| "a_bit"), Some(a)).unwrap();
let b_bit = UInt32::constant(b);
let c_bit = UInt32::alloc(cs.namespace(|| "c_bit"), Some(c)).unwrap();
let r = a_bit.xor(cs.namespace(|| "first xor"), &b_bit).unwrap();
let r = r.xor(cs.namespace(|| "second xor"), &c_bit).unwrap();
assert!(cs.is_satisfied());
assert!(r.value == Some(expected));
for b in r.bits.iter() {
match *b {
Boolean::Is(ref b) => {
assert_eq!(b.get_value().unwrap(), expected & 1 == 1);
}
Boolean::Not(ref b) => {
assert_ne!(b.get_value().unwrap(), expected & 1 == 1);
}
Boolean::Constant(b) => {
assert_eq!(b, expected & 1 == 1);
}
}
expected >>= 1;
}
}
}
#[test]
fn test_uint32_addmany_constants() {
let mut rng = XorShiftRng::from_seed([
0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06,
0xbc, 0xe5,
]);
for _ in 0..1000 {
let mut cs = TestConstraintSystem::<Fr>::new();
let a = rng.next_u32();
let b = rng.next_u32();
let c = rng.next_u32();
let a_bit = UInt32::constant(a);
let b_bit = UInt32::constant(b);
let c_bit = UInt32::constant(c);
let mut expected = a.wrapping_add(b).wrapping_add(c);
let r = {
let mut cs = MultiEq::new(&mut cs);
let r =
UInt32::addmany(cs.namespace(|| "addition"), &[a_bit, b_bit, c_bit]).unwrap();
r
};
assert!(r.value == Some(expected));
for b in r.bits.iter() {
match *b {
Boolean::Is(_) => panic!(),
Boolean::Not(_) => panic!(),
Boolean::Constant(b) => {
assert!(b == (expected & 1 == 1));
}
}
expected >>= 1;
}
}
}
#[test]
#[allow(clippy::many_single_char_names)]
fn test_uint32_addmany() {
let mut rng = XorShiftRng::from_seed([
0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06,
0xbc, 0xe5,
]);
for _ in 0..1000 {
let mut cs = TestConstraintSystem::<Fr>::new();
let a = rng.next_u32();
let b = rng.next_u32();
let c = rng.next_u32();
let d = rng.next_u32();
let mut expected = (a ^ b).wrapping_add(c).wrapping_add(d);
let a_bit = UInt32::alloc(cs.namespace(|| "a_bit"), Some(a)).unwrap();
let b_bit = UInt32::constant(b);
let c_bit = UInt32::constant(c);
let d_bit = UInt32::alloc(cs.namespace(|| "d_bit"), Some(d)).unwrap();
let r = a_bit.xor(cs.namespace(|| "xor"), &b_bit).unwrap();
let r = {
let mut cs = MultiEq::new(&mut cs);
UInt32::addmany(cs.namespace(|| "addition"), &[r, c_bit, d_bit]).unwrap()
};
assert!(cs.is_satisfied());
assert!(r.value == Some(expected));
for b in r.bits.iter() {
match *b {
Boolean::Is(ref b) => {
assert_eq!(b.get_value().unwrap(), expected & 1 == 1);
}
Boolean::Not(ref b) => {
assert_ne!(b.get_value().unwrap(), expected & 1 == 1);
}
Boolean::Constant(_) => unreachable!(),
}
expected >>= 1;
}
if cs.get("addition/result bit 0/boolean").is_zero().into() {
cs.set("addition/result bit 0/boolean", Field::ONE);
} else {
cs.set("addition/result bit 0/boolean", Field::ZERO);
}
assert!(!cs.is_satisfied());
}
}
#[test]
fn test_uint32_rotr() {
let mut rng = XorShiftRng::from_seed([
0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06,
0xbc, 0xe5,
]);
let mut num = rng.next_u32();
let a = UInt32::constant(num);
for i in 0..32 {
let b = a.rotr(i);
assert_eq!(a.bits.len(), b.bits.len());
assert!(b.value.unwrap() == num);
let mut tmp = num;
for b in &b.bits {
match *b {
Boolean::Constant(b) => {
assert_eq!(b, tmp & 1 == 1);
}
_ => unreachable!(),
}
tmp >>= 1;
}
num = num.rotate_right(1);
}
}
#[test]
fn test_uint32_shr() {
let mut rng = XorShiftRng::from_seed([
0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06,
0xbc, 0xe5,
]);
for _ in 0..50 {
for i in 0..60 {
let num = rng.next_u32();
let a = UInt32::constant(num).shr(i);
let b = UInt32::constant(num.wrapping_shr(i as u32));
assert_eq!(a.value.unwrap(), num.wrapping_shr(i as u32));
assert_eq!(a.bits.len(), b.bits.len());
for (a, b) in a.bits.iter().zip(b.bits.iter()) {
assert_eq!(a.get_value().unwrap(), b.get_value().unwrap());
}
}
}
}
#[test]
fn test_uint32_sha256_maj() {
let mut rng = XorShiftRng::from_seed([
0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06,
0xbc, 0xe5,
]);
for _ in 0..1000 {
let mut cs = TestConstraintSystem::<Fr>::new();
let a = rng.next_u32();
let b = rng.next_u32();
let c = rng.next_u32();
let mut expected = (a & b) ^ (a & c) ^ (b & c);
let a_bit = UInt32::alloc(cs.namespace(|| "a_bit"), Some(a)).unwrap();
let b_bit = UInt32::constant(b);
let c_bit = UInt32::alloc(cs.namespace(|| "c_bit"), Some(c)).unwrap();
let r = UInt32::sha256_maj(&mut cs, &a_bit, &b_bit, &c_bit).unwrap();
assert!(cs.is_satisfied());
assert!(r.value == Some(expected));
for b in r.bits.iter() {
match *b {
Boolean::Is(ref b) => {
assert_eq!(b.get_value().unwrap(), expected & 1 == 1);
}
Boolean::Not(ref b) => {
assert_ne!(b.get_value().unwrap(), expected & 1 == 1);
}
Boolean::Constant(b) => {
assert_eq!(b, expected & 1 == 1);
}
}
expected >>= 1;
}
}
}
#[test]
fn test_uint32_sha256_ch() {
let mut rng = XorShiftRng::from_seed([
0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06,
0xbc, 0xe5,
]);
for _ in 0..1000 {
let mut cs = TestConstraintSystem::<Fr>::new();
let a = rng.next_u32();
let b = rng.next_u32();
let c = rng.next_u32();
let mut expected = (a & b) ^ ((!a) & c);
let a_bit = UInt32::alloc(cs.namespace(|| "a_bit"), Some(a)).unwrap();
let b_bit = UInt32::constant(b);
let c_bit = UInt32::alloc(cs.namespace(|| "c_bit"), Some(c)).unwrap();
let r = UInt32::sha256_ch(&mut cs, &a_bit, &b_bit, &c_bit).unwrap();
assert!(cs.is_satisfied());
assert!(r.value == Some(expected));
for b in r.bits.iter() {
match *b {
Boolean::Is(ref b) => {
assert_eq!(b.get_value().unwrap(), expected & 1 == 1);
}
Boolean::Not(ref b) => {
assert_ne!(b.get_value().unwrap(), expected & 1 == 1);
}
Boolean::Constant(b) => {
assert_eq!(b, expected & 1 == 1);
}
}
expected >>= 1;
}
}
}
}