Extend R1CS allocate API with evalution

[jimpo]

I've been playing around with some R1CS gadgets and have noticed that allocate is rather difficult to use. It accepts an assignment function, however, computing the assignments from other variables is not easy. I have found that I need to pass around all variable assignments with the variables in my gadget and compute new assignments in parallel. If instead, allocate exposed access to evaluate LinearCombinations of other variables, this would be must simpler.

I propose modifying allocate in ConstraintSystem to have the following signature:

fn allocate<F>(&mut self, assign_fn: F) -> Result<(Variable, Variable, Variable), R1CSError>
    where
        F: FnOnce(&dyn Fn(&LinearCombination) -> Scalar)
            -> Result<(Scalar, Scalar, Scalar), R1CSError>;

Then the Prover will call assign_fn with a closure that evaluates the given LinearCombination:

let (l, r, o) = {
    // The explicit type hint seems to be necessary to compile.
    let eval: &dyn for<'c> Fn(&'c LinearCombination) -> Scalar =
        &(|lc| self.eval(lc));
    assign_fn(eval)?
};

With this modification, multiply in ProverCS and VerifierCS could be implemented mostly using allocate (with the extra constraints).

Thoughts? Or is there another recommended pattern for using allocate?

[oleganza]

In the ZkVM we use Option<ScalarWitness> as an assignment because it preserves the integer for the rangeproof, but also allows raw scalars for other kinds of assignments. If R1CS provides API for scalar assignments (that is, exposes eval this way or another), that would not be enough for our purposes: the underlying integer type would be erased.

pub enum ScalarWitness {
    /// `ScalarKind::Integer` represents a signed integer with 64-bit absolute value (think "i65")
    Integer(SignedInteger),
    /// `ScalarKind::Scalar` represents a scalar modulo group order.
    Scalar(Scalar),
}

There are two solutions:

1. Let the user keep their own assignments as we do today. We can simplify API in other ways to make overall usage nicer. E.g. instead of providing a closure to .allocate, we can simply provide Option<Scalar>, so that closure could be effectively shifted to user's witness.map(|w| w.to_scalar()). See also #206.
2. Make all LinearCombinations generic over S: Into<Scalar>, so the user can query their own witness type. I don't think that would work out into a clean and nice API.

[cathieyun]

See https://github.com/dalek-cryptography/bulletproofs/pull/256 (merged), where Oleg implemented approach #1, providing Option<Scalar> instead of a closure. Want to give the new API a try and see if that is easier to use? You can also see the Cloak code that uses this updated API to see it in use: https://github.com/interstellar/slingshot/pull/211