[Question] Does R1CS support "free" multiply-by-scalar?

[cjpatton]

I've been playing around with the r1cs module. So far my understanding is that this module provides more or less the same functionality as the "arithmetic circuit" functionality from Section 5 of the paper. I gather from the paper -- or rather the referenced construction from [BCC+16] -- that multiplication by a constant is "free" in the sense that it does not count towards the constraints on the multiplication gates.

If accurate, I'm wondering how to take advantage of this using the constraint system API. Consider the following minimal (and fairly dumb) example:

/// A polynomial over the scalar field.
pub struct Poly(Vec<Scalar>);

impl Poly {
    /// We want to prove that some polynomial, `other_poly`, is equal to this polynomial. One way
    /// to do this is to have the constraint system generate a random challenge scalar, evaluate
    /// each polynomial at this point, and assert that the results are equal.
    fn gadget<CS: RandomizableConstraintSystem>(
        &self,
        cs: &mut CS,
        other_poly: Vec<Variable>,
    ) -> Result<(), R1CSError> {
        let poly = self.0.clone();
        let l = poly.len();
        assert_eq!(other_poly.len(), l);
        if l == 0 {
            return Ok(());
        }

        cs.specify_randomized_constraints(move |cs| {
            let r = cs.challenge_scalar(b"random point");
            let mut x = Scalar::one();

            // Evaluate `poly` and `other_poly` at random point `r`.
            let mut result = Scalar::zero();
            let mut other_result = LinearCombination::from(Scalar::zero());
            for i in 0..l {
                result += x * poly[i];
                let (_, _, c) = cs.multiply(x.into(), other_poly[i].into());
                other_result = other_result + c;
                x *= r;
            }

            // Expect the results to be equal.
            cs.constrain(LinearCombination::from(result) - other_result);

            println!("number of multipliers: {}", cs.multipliers_len());
            Ok(())
        })
    }

Notice that this circuit contains as many multipliers (i.e., multiplication gates) as there are coefficients in the polynomial. However since the the left wire of each multiplier is a public constant and the right wire is one of the input variables, I would expect to be able to express this particular (dumb) circuit without any multipliers, i.e., calls to cs.multiply().

I'd appreciate if someone could tell me which of the following is true:

1. The r1cs module admits free multiply-by-constant (if so, how is this expressed?)
2. The r1cs module does not support this now, but Bulletproofs do support this in principle.
3. I am misunderstanding something about Bulletproofs 😄

Thanks in advance!

[rubdos]

(I have not really looked at your code)

You can multiply Scalar by LinearCombination, just by using the * operator from Rust.

[cjpatton]

Yup, that's super obvious in retrospect. Thanks for your help!

Updated example:

impl Poly {
    /// We want to prove that some polynomial, `other_poly``, is equal to this polynomial. One way
    /// to do this is to have the constraint system generate a random challenge sclaar, evaluate
    /// each polynomial at this point, and assert that the results are equal.
    fn gadget<CS: RandomizableConstraintSystem>(
        &self,
        cs: &mut CS,
        other_poly: Vec<Variable>,
    ) -> Result<(), R1CSError> {
        let poly = self.0.clone();
        let l = poly.len();
        assert_eq!(other_poly.len(), l);
        if l == 0 {
            return Ok(());
        }

        cs.specify_randomized_constraints(move |cs| {
            let r = cs.challenge_scalar(b"random point");
            let mut x = Scalar::one();

            // Evaluate `poly` and `other_poly` at random point `r`.
            let mut result = LinearCombination::from(Scalar::zero());
            let mut other_result = LinearCombination::from(Scalar::zero());
            for i in 0..l {
                result = result + (x * poly[i]);
                other_result = other_result + (x * LinearCombination::from(other_poly[i].clone()));
                x *= r;
            }

            // Expect the results to be equal.
            cs.constrain(LinearCombination::from(result) - other_result);

            println!("number of multipliers: {}", cs.multipliers_len());
            Ok(())
        })