Panic when evaluating s(X, Y) with x = 0 or y = 0

[ConstanceBeguier]

Crate

ragu_circuits

Severity

Repo commit

c9649de

Description

If x = 0 or y = 0, many linear constraint terms vanish, meaning the corresponding constraints are no longer enforced in the aggregated polynomial check. This can weaken soundness by allowing invalid witnesses to pass verification.

Since these values are expected to be non-zero verifier challenges, evaluating the polynomial at zero should be explicitly disallowed.

Code

File name: ragu_circuits/src/sx.rs

pub fn eval<F: Field, C: Circuit<F>, R: Rank>(
    circuit: &C,
    x: F,
    key: F,
) -> Result<unstructured::Polynomial<F, R>> {
    if x == F::ZERO {
        // The polynomial is zero if x is zero.
        return Ok(Polynomial::new());
    }

    let multiplication_constraints = 0;
    let linear_constraints = 0;
    let x_inv = x.invert().expect("x is not zero");
    let xn = x.pow_vartime([R::n() as u64]);
    let xn2 = xn.square();
    let current_u_x = xn2 * x_inv;
    let current_v_x = xn2;
    let xn4 = xn2.square();
    let current_w_x = xn4 * x_inv;

    let mut collector = Collector::<F, R> {
        result: unstructured::Polynomial::new(),
        multiplication_constraints,
        linear_constraints,
        x,
        x_inv,
        current_u_x,
        current_v_x,
        current_w_x,
        one: current_w_x,
        available_b: None,
        _marker: core::marker::PhantomData,
    };
    let (key_wire, _, one) = collector.mul(|| unreachable!())?;

    // Enforce linear constraint key_wire = key to randomize non-trivial
    // evaluations of this circuit polynomial.
    collector.enforce_zero(|lc| {
        lc.add(&key_wire)
            .add_term(&one, Coeff::NegativeArbitrary(key))
    })?;

    let mut outputs = vec![];
    let (io, _) = circuit.witness(&mut collector, Empty)?;
    io.write(&mut collector, &mut outputs)?;
    for output in outputs {
        collector.enforce_zero(|lc| lc.add(output.wire()))?;
    }
    collector.enforce_zero(|lc| lc.add(&one))?;

    collector.result[0..collector.linear_constraints].reverse();
    assert_eq!(collector.result[0], collector.one);

    Ok(collector.result)
}

Recommendations

Return an error or panic when x == 0 or y == 0, and document that verifier challenges must be sampled from F \ {0}.

pub fn eval<F: Field, C: Circuit<F>, R: Rank>(
    circuit: &C,
    x: F,
    key: F,
) -> Result<unstructured::Polynomial<F, R>> {
    // In the ZKP setting, x is a verifier challenge and must be non-zero.
    // If x == 0, linear constraints encoded in s(X, Y) may vanish,
    // weakening soundness of the aggregated check.
    assert_ne!(x, F::ZERO, "challenge x must be non-zero");

    let multiplication_constraints = 0;
    let linear_constraints = 0;
    let x_inv = x.invert().expect("x is not zero");
    let xn = x.pow_vartime([R::n() as u64]);
    let xn2 = xn.square();
    let current_u_x = xn2 * x_inv;
    let current_v_x = xn2;
    let xn4 = xn2.square();
    let current_w_x = xn4 * x_inv;

    ...
}

Also affected

The same change should be applied to:

• the eval function in ragu_circuits/src/s/sxy.rs
• the eval function in ragu_circuits/src/s/sy.rs
• the StageObject::sxy function in ragu_circuits/src/staging/object.rs
• the StageObject::sx function in ragu_circuits/src/staging/object.rs
• the StageObject::sy function in ragu_circuits/src/staging/object.rs

[AntoineRondelet]

I'm not sure that panicking inside of these functions is the right fix. These functions are sound from what I can see. I think the appropriate fix is to panic higher up in the library when the challenges and evaluation points are generated - not here, inside of this function.

Doing smthg like this:

let x = derive_challenge(&transcript); // or whatever
assert!(x != F::ZERO, "challenge must be nonzero");

sounds more appropriate than panicking inside of this function here imo.
In fact, such assert on the derivation of the evaluation point properly qualifies invariants that need to uphold on challenges -> they need to be random (RO assumption) and non-zero. The eval logic above should just do it's job of correctly evaluating the polynomials and should not be aware of the the requirements on the evaluation points imho.

It should be the responsibility of the caller to properly derive eval points (e.g. FS is frequently poorly implemented because people forget to pass the WHOLE transcript to the hash function which can be exploited). This should truly be the responsibility of the caller to derive these points adequately.

[AntoineRondelet]

imo to properly tackle these edge cases in the code base I think the 2 best things would be:

1/ Better name parameters to they properly characterise what they represent (e.g. see #48 and #52)
2/ Use dedicated types where needed (e.g. define wrappers around F to define "specific types of field elements" that have specific derivation requirements and need to satisfy invariants -> we could imagine having a MeshKey type, a Challenge type etc that would replace F in the relevant functions -> these types would take care of enforcing invariants and the function signatures would be enriched with type information that clarify the intent.)

My 2 cents: If the intent of a function is to evaluate a polynomial on a given field element, it should just do so - without panicking for reasons outside of its scope.