Redundancy in three_bit_cond_neg_lookup for FpVar

[weikengchen]

Summary of Bug

In Aleo, when Howard implemented the Bowe-Hopwood Pedersen circuit, he discovered a weird phenomenon:

• BHP compressed gadget takes 2525 constraints to hash 97 bytes (all are not constants)
• BHP compressed gadget takes 2524 constraints to hash 98 bytes (when the first byte is a constant, and the rest is not)

It is surprising that, the second case, which actually does slightly more work, reduces the constraint count by 1.

(Note: this is over a slightly different version, snarkVM. I have the feeling that the tradeoff in arkworks-rs may be slightly different. The two may be the same.)

This is because, when we are doing three_bit_cond_neg_lookup when b[0] or b[1] is not a constant, but b[2] is a constant, we have one unnecessary constraint that is related to b[2].

        // enforce y * (1 - 2 * b_2) == res
        b.cs().enforce_constraint(
            y_lc.clone(),
            b[2].lc() * F::from(2u64).neg() + (F::one(), Variable::One),
            lc!() + result.variable,
        )?;

However, this call to enforce a constraint can be avoided if, when b[2] is a constant, the code is written differently, as in this case, result is a simple linear combination of y.

What happens is that, because 97 * 8 % 3 = 2, adding a free byte at the beginning takes advantage of this dummy, so one constraint down. Indeed, it should not be the case.

Version

master

Steps to Reproduce

It may be slightly complicated. But one can look at the three_bit_cond_neg_lookup implementation for FpVar, notice that if b[0] or b[1] is not a constant, but b[2] is a constant, it goes to the implementation of AllocatedFp, in which case the above constraint, which can be avoided sometimes, is never omitted.