/// Enforce the constraints that ensure that `value` consists of binary values and that the num
/// representation thereof is smaller than or equal to `lower_bound`.
Enforce the constraints that ensure that `value` consists of binary values and that the num
representation thereof is smaller than or equal to `lower_bound`.
Enforce the constraints that ensure that ` value ` consists of binary values and that the num representation thereof is smaller than or equal to ` lower_bound ` .
pub fn upper_bound_check_u64<Scalar: PrimeField, CS: ConstraintSystem<Scalar>>(
    mut cs: CS,
    upper_bound: u64,
    value: &[AllocatedNum<Scalar>],
) -> Result<(), SynthesisError> {
    assert_eq!(value.len(), 64);
    let mut upper_bound_bits = vec![];
    let mut first_one = None;
    for i in (0..64).rev() {
        let bit = upper_bound >> i & 1;
        if first_one != None {
            upper_bound_bits.push(bit);
        } else if bit == 1 {
            upper_bound_bits.push(bit);
            first_one = Some(63 - i);
        }
    }
    // arrays are sorted with most significant bit first and least significant bit last
    let upper_bound_bits = upper_bound_bits;
    let (leading_bits, value_bits) =
        value.split_at(first_one.expect("There should be a first '1'."));
    // set leading value bits to zero
    for (i, leading_bit) in leading_bits.iter().enumerate() {
        cs.enforce(
            || format!("Zero constrain leading bit {}", i),
            |lc| lc + leading_bit.get_variable(),
            |lc| lc + CS::one(),
            |lc| lc,
        );
    }
    // actual range check
    // --> determine Pi_i for i in range [n-1,t+1], where t is the number of trailing one's in c.
    let mut t = 0;
    for (i, &b) in upper_bound_bits.iter().rev().enumerate() {
        if b == 0 {
            t = i;
            break;
        }
    }
    let mut pis = vec![value_bits[0].clone()];
    for (i, (&c, a)) in upper_bound_bits
        .iter()
        .zip(value_bits.iter())
        .rev()
        .skip(t + 1)
        .rev()
        .skip(1)
        .enumerate()
    {
        let pi_prev = pis.last().expect("This vector is not empty.");
        let pi_new = AllocatedNum::alloc(cs.namespace(|| format!("pi_(n-{})", i + 2)), || {
            if c == 0 {
                pi_prev.get_value().get().map(|&pi| pi)
            } else {
                let mut pi_prev = *pi_prev.get_value().get()?;
                a.get_value().get().map(|a| {
                    pi_prev.mul_assign(a);
                    pi_prev
                })
            }
        })?;
        cs.enforce(
            || format!("pi_(n-{}) constraint", i + 2),
            |lc| lc + pi_prev.get_variable(),
            |lc| {
                if c == 0 {
                    lc + CS::one()
                } else {
                    lc + a.get_variable()
                }
            },
            |lc| lc + pi_new.get_variable(),
        );
        pis.push(pi_new);
    }
    // --> constrain value bits
    for (i, (&c, a)) in upper_bound_bits.iter().zip(value_bits.iter()).enumerate() {
        if c == 0 {
            cs.enforce(
                || format!("c=0 constraint for bit n-{}", i + 1),
                |lc| lc + CS::one() - pis[i - 1].get_variable() - a.get_variable(),
                |lc| lc + a.get_variable(),
                |lc| lc,
            );
        } else {
            cs.enforce(
                || format!("c=1 constraint for bit n-{}", i + 1),
                |lc| lc + a.get_variable(),
                |lc| lc + CS::one() - a.get_variable(),
                |lc| lc,
            );
        }
    }
    Ok(())
}
pub fn upper_bound_check_u64 < Scalar : PrimeField , CS : ConstraintSystem < Scalar > > ( mut cs : CS , upper_bound : u64 , value : & [ AllocatedNum < Scalar > ] , ) -> Result < ( ) , SynthesisError > { assert_eq ! ( value len ( ) 64 ) ; let mut upper_bound_bits = vec ! [ ] ; let mut first_one = None ; for i in ( 0 .. 64 ) . rev ( ) { let bit = upper_bound >> i & 1 ; if first_one != None { upper_bound_bits . push ( bit ) ; } else if bit == 1 { upper_bound_bits . push ( bit ) ; first_one = Some ( 63 - i ) ; } } // arrays are sorted with most significant bit first and least significant bit last let upper_bound_bits = upper_bound_bits ; let ( leading_bits , value_bits ) = value . split_at ( first_one . expect ( " " ) ) ; // set leading value bits to zero for ( i , leading_bit ) in leading_bits . iter ( ) . enumerate ( ) { cs . enforce ( | | format ! ( " " i ) , | lc | lc + leading_bit . get_variable ( ) , | lc | lc + CS :: one ( ) , | lc | lc , ) ; } // actual range check // --> determine Pi_i for i in range [n-1,t+1], where t is the number of trailing one's in c. let mut t = 0 ; for ( i , & b ) in upper_bound_bits . iter ( ) . rev ( ) . enumerate ( ) { if b == 0 { t = i ; break ; } } let mut pis = vec ! [ value_bits [ 0 ] clone ( ) ] ; for ( i , ( & c , a ) ) in upper_bound_bits . iter ( ) . zip ( value_bits . iter ( ) ) . rev ( ) . skip ( t + 1 ) . rev ( ) . skip ( 1 ) . enumerate ( ) { let pi_prev = pis . last ( ) . expect ( " " ) ; let pi_new = AllocatedNum :: alloc ( cs . namespace ( | | format ! ( " " i 2 ) ) , | | { if c == 0 { pi_prev . get_value ( ) . get ( ) . map ( | & pi | pi ) } else { let mut pi_prev = * pi_prev . get_value ( ) . get ( ) ? ; a . get_value ( ) . get ( ) . map ( | a | { pi_prev . mul_assign ( a ) ; pi_prev } ) } } ) ? ; cs . enforce ( | | format ! ( " " i 2 ) , | lc | lc + pi_prev . get_variable ( ) , | lc | { if c == 0 { lc + CS :: one ( ) } else { lc + a . get_variable ( ) } } , | lc | lc + pi_new . get_variable ( ) , ) ; pis . push ( pi_new ) ; } // --> constrain value bits for ( i , ( & c , a ) ) in upper_bound_bits . iter ( ) . zip ( value_bits . iter ( ) ) . enumerate ( ) { if c == 0 { cs . enforce ( | | format ! ( " " i 1 ) , | lc | lc + CS :: one ( ) - pis [ i - 1 ] . get_variable ( ) - a . get_variable ( ) , | lc | lc + a . get_variable ( ) , | lc | lc , ) ; } else { cs . enforce ( | | format ! ( " " i 1 ) , | lc | lc + a . get_variable ( ) , | lc | lc + CS :: one ( ) - a . get_variable ( ) , | lc | lc , ) ; } } Ok ( ( ) ) }
Enforce the constraints that ensure that `value` consists of binary values and that the num
representation thereof is smaller than or equal to `lower_bound`.
Enforce the constraints that ensure that ` value ` consists of binary values and that the num representation thereof is smaller than or equal to ` lower_bound ` .
cs
CS
upper_bound
u64
value
&[AllocatedNum<Scalar>]