arkworks-rs/snark

ToBitsGadget for FpVar has non-constant output length

Closed this issue · 0 comments

FpVar's ToBitsGadget may produce a shorter output when the variable is a constant (i.e., FpVar::Constant(c)).
Because it would remove the trailing zeros.

See the code here:
https://github.com/scipr-lab/zexe/blob/master/r1cs-std/src/fields/fp/mod.rs#L875

This is problematic because:

  1. It differs from BigInteger's to_bits, which we use in the native world and does not trim trailing zeros.
  2. Non-constant length bit sequence is hard to handle and is error-prone in the constraint world.
  3. Differs from an AllocatedFp's to_bits of the same value.

The following changes seem to work: changing to_non_unique_bits_le of FpVar to

    #[tracing::instrument(target = "r1cs")]
    fn to_non_unique_bits_le(&self) -> Result<Vec<Boolean<F>>, SynthesisError> {
        use algebra::BitIteratorLE;
        match self {
            Self::Constant(c) => Ok(BitIteratorLE::new(&c.into_repr())
                .take((F::Params::MODULUS_BITS) as usize)
                .map(Boolean::constant)
                .collect::<Vec<_>>()),
            Self::Var(v) => v.to_non_unique_bits_le(),
        }
    }

which replaces "without_trailing_zeros" with the normal BitIteratorLE and only takes the same number of bits as the prime modulus's.


Will submit a PR to arkworks once it is stable. Or it would also be good if arkworks library absorbs this change soon.