argumentcomputer / bellpepper-gadgets

A library of gadgets compatible with bellpepper and bellperson (contact: @huitseeker)
Apache License 2.0
17 stars 13 forks source link

Adding SHA1 gadget #6

Closed avras closed 1 year ago

avras commented 1 year ago

Closing this PR as there is a simpler way to implement the OR gate.

@porcuquine pointed me to the following OR gadget in the Lurk codebase which uses De Morgan's law to implement OR using NOT and AND.

// Use DeMorgan to constrain or.
pub(crate) fn or<CS: ConstraintSystem<F>, F: PrimeField>(
    mut cs: CS,
    a: &Boolean,
    b: &Boolean,
) -> Result<Boolean, SynthesisError> {
    Ok(Boolean::not(&Boolean::and(
        cs.namespace(|| "not and (not a) (not b)"),
        &Boolean::not(a),
        &Boolean::not(b),
    )?))
}

Using this implementation of OR reduced the number of constraints in a SHA1 compression function from 16706 to 15426. See commit here.

The reason more constraints were required in the current PR is that an AllocatedBit was being allocated in the or_not_allocated_bits, nand_allocated_bits, and or_allocated_bits functions. This allocation was to get around the fact that the fields of AllocatedBit are private, preventing a direct creation of the struct as follows. Such creation occurs in the boolean module of bellpepper-core.

Ok(AllocatedBit {
    variable: result_var,
    value: result_value,
})

I will be deleting the sha1 branch. Those interested in what was in the commit can find it in this branch in my fork of bellpepper-gadgets.