[bug]: incorrect lagrange evaluation when zeta is roots of unity

[alxiong]

Thanks to Shresth and CommonPrefix team for catching this bug (for an audit of the corresponding plonk verifier contract).

Currently the logic for computing lagrange evaluation is wrong when random challenge zeta is roots of unity (which results in vanishing_eval to be zero. In this case, $\mathcal{L}_1(\zeta) = 1$ if $\zeta$ is the first roots-of-unity, and zero otherwise. but our current code would simply panic due to division by zero.

    pub(crate) fn evaluate_lagrange_1_and_n(
        &self,
        zeta: &E::ScalarField,
        vanish_eval: &E::ScalarField,
    ) -> (E::ScalarField, E::ScalarField) {
        let divisor =
            E::ScalarField::from(self.domain.size() as u32) * (*zeta - E::ScalarField::one());
        let lagrange_1_eval = *vanish_eval / divisor;
        let divisor =
            E::ScalarField::from(self.domain.size() as u32) * (*zeta - self.domain.group_gen_inv);
        let lagrange_n_eval = *vanish_eval * self.domain.group_gen_inv / divisor;
        (lagrange_1_eval, lagrange_n_eval)
    }

this also affects evaluate_pi_poly() that internally uses lagrange_i_eval. We should further double check and fix prover-side code.

Note: we didn't catch this in test because:

• we didn't have property test on lagrange poly eval
• zeta is random challenge, the probability of it being one of roots of unity is negligible

Thus this issue should also aim to improve tests to guard against this bug

Note2: this is a hard-to-exploit bug (unless our FS is also broken), so current downstream relying on jellyfish shouldn't panic, but the PR that fix this bug should issue a new release and recommend all downstream to migrate over soon.

cc @mrain @chancharles92

[alxiong]

comments needed, I wanted to directly replace our usage with arkworks' API, unfortunately, they only have EvalDomain::evaluate_all_lagrange_coefficients()

~maybe I'll just mimic write a fn evaluate_lagrange_coeff_at(domain) for now, and submit a PR upstream for future arkworks to include this API directly in struct EvalDomain, okay?~

Here's my plan:

• declare a local pub(crate) trait LagrangeCoeffs with ::first(), ::last() and from_range(range) -> Vec<F>
• implement them (the last one is similar to arkwork's impl
• write test, testing ours against arkwork's evaulate_all_lagrange_coefficients()
• submit an issue on arkworks on directly adding these 3 methods on trait EvaluationDomain so later in the future, we can easily use theirs once we upgrade arkworks dep.

@mrain @chancharles92