Edge case on MSM function

[iquerejeta]

We have found an edge case for the MSM function. It always fails at this point.

We believe this is a serious bug as it could make a verifier crash for a given input.

The size of the MSM is ~2**13. The following is a minimal working example:

#[cfg(test)]
mod foo_tests {
    use std::{fs::File, io::BufReader, path::Path};

    use crate::{
        bls12381::{Fr, G1Affine},
        msm::msm_best,
    };

    #[test]
    fn fail_msm() {
        let file = File::open(Path::new("./scalars.bin")).unwrap();
        let reader = BufReader::new(file);
        let scalars: Vec<Fr> = bincode::deserialize_from(reader).unwrap();

        let file = File::open(Path::new("./points.bin")).unwrap();
        let reader = BufReader::new(file);
        let points: Vec<G1Affine> = bincode::deserialize_from(reader).unwrap();

        msm_best(&scalars, &points);
    }
}

and you need the std and serde features, cargo test fail_msm --features std --features derive_serde. I've attached the files that contain the failing test vectors.

We haven't been able to identify what is the causing issue of this failure.

points.txt
scalars.txt

[guorong009]

Thanks for report! @iquerejeta

One question, have you tried same test in the gnark-crypto library? (somewhere like here)
Some sources (paper, here) says that the algorithm is also implemented in gnark-crypto library. (Consensys/gnark-crypto#261)

cc @ed255 @kilic

[iquerejeta]

Ey @guorong009 , I did not have a look at gnark-crypto. In the meantime we are using a different library for BLS12-381.