arkworks-rs / snark

Interfaces for Relations and SNARKs for these relations
https://www.arkworks.rs
Apache License 2.0
776 stars 209 forks source link

Do not check whether inverse exists in `FpGadget::inverse` #251

Closed weikengchen closed 4 years ago

weikengchen commented 4 years ago

Currently, FpGadget::inverse would complain when the inverse does not exist.

#[inline]
fn inverse<CS: ConstraintSystem<F>>(&self, mut cs: CS) -> Result<Self, SynthesisError> {
    let inverse = Self::alloc(cs.ns(|| "inverse"), || {
       let result = self.value.get()?;
       let inv = result.inverse().expect("Inverse doesn't exist!");
       Ok(inv)
    })?;

    let one = CS::one();
    cs.enforce(
        || "inv_constraint",
        |lc| &self.variable + lc,
        |lc| &inverse.variable + lc,
        |lc| lc + one,
    );
    Ok(inverse)
}

This, however, creates significant challenges during the indexing phase, in which all inputs and witnesses are fake, and many of them could be zero.

For example, in Zexe there is a NIZK verifier that checks the proof in the constraint system, which does some inverse operations. To make the indexing works, Zexe has to generate a proof for a blank circuit.

A similar challenge exists for other recursive proof systems, in which a real proof or a carefully crafted fake proof is needed.


Proposed solution:

Consider this line:

let inv = result.inverse().expect("Inverse doesn't exist!");

What if we set inv to zero when the inverse does not exist? This can be done with a unwrap_or(...).

Setting it to zero would not cause a soundness issue since the constraint would be unsatisfied, which would not affect the indexing phase.

Pratyush commented 4 years ago

Fixed in master (which uses the new API)