Cyclone MSM panic

[jonathanpwang]

I tried to use the msm bench cargo bench --bench msm but switching best_multiexp for best_multiexp_independent_points but there is a panic.

Benchmarking code here: https://github.com/privacy-scaling-explorations/halo2curves/compare/main...axiom-crypto:halo2curves:bench/cyclone?expand=1

Is there some hidden assumptions on the coeffs/bases allowed to be used here?

[davidnevadoc]

Looks like it is panicking in the batch_add https://github.com/privacy-scaling-explorations/halo2curves/blob/8af4f1ebab640405c799e65d9873847a4acf04f8/src/msm.rs#L88

Any ideas on what the issue is? @kilic @mratsim

[mratsim]

Didn't check but from the name

best_multiexp for best_multiexp_independent_points

and seeing that it's batch inversion that fails, I assume it's batch inversion that assumes no point has itself or its inverse in the same batch.

_edit: see my review comment https://github.com/privacy-scaling-explorations/halo2curves/pull/130#discussion_r1471274568_

[jonathanpwang]

So this means best_multiexp_independent_points cannot be used in place of best_multiexp, for example in halo2?

[mratsim]

Good question. In Constantine I made sure to handle all edge cases so I didn't have to worry about this.

In Barretenberg they do make the distinction: https://github.com/AztecProtocol/barretenberg/blob/31ec608/cpp/src/barretenberg/ecc/scalar_multiplication/scalar_multiplication.cpp#L310-L441.

[AlekseiVambol]

The implementation of fn batch_add is not entirely correct. The EC addition formulas implementation is not complete: the special cases (point doubling and adding the inverse point) were not taken into account. Thus, for certain inputs, fn best_multiexp_independent_points panics. To create the test showing the problem, replace the lines 533-542 of fn run_msm_cross with the following code:

        let p = C::Curve::random(OsRng);
        let points = (0..1 << max_k).map(|_| p).collect::<Vec<_>>();
        let mut affine_points = vec![C::identity(); 1 << max_k];
        C::Curve::batch_normalize(&points[..], &mut affine_points[..]);
        let points = affine_points;

        let s = C::Scalar::random(OsRng);
        let scalars = (0..1 << max_k).map(|_| s).collect::<Vec<_>>();