arkworks-rs / r1cs-std

R1CS constraints for bits, fields, and elliptic curves
https://www.arkworks.rs
Apache License 2.0
135 stars 59 forks source link

Examine more carefully on the bound for UInt `addmany` implementation #23

Open weikengchen opened 3 years ago

weikengchen commented 3 years ago

The current implementation of addmany has a number of bounds:

https://github.com/arkworks-rs/r1cs-std/blob/master/src/bits/uint.rs#L184

// Make some arbitrary bounds for ourselves to avoid overflows
// in the scalar field
assert!(F::Params::MODULUS_BITS >= 2 * $size);
assert!($size * operands.len() <= F::Params::MODULUS_BITS as usize);

However, these bounds seem to be too strict. This part of the code is supposed for additions. And the bounds here seem for multiplication.

Pratyush commented 3 years ago

Hmm so it should $size + operands.len()?

weikengchen commented 3 years ago

or $size + log2(operands.len() + 1)?

Pratyush commented 3 years ago

why the + 1?