Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Cyclone MSM panic #153

Closed
jonathanpwang opened this issue Apr 24, 2024 · 5 comments · Fixed by #169
Closed

Cyclone MSM panic #153

jonathanpwang opened this issue Apr 24, 2024 · 5 comments · Fixed by #169
Assignees

Comments

@jonathanpwang
Copy link
Contributor

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?

@kilic kilic self-assigned this Apr 24, 2024
@davidnevadoc
Copy link
Contributor

Looks like it is panicking in the batch_add

acc = acc.invert().unwrap();

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

@mratsim
Copy link
Contributor

mratsim commented Apr 29, 2024

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 #130 (comment)

@jonathanpwang
Copy link
Contributor Author

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

@mratsim
Copy link
Contributor

mratsim commented Apr 30, 2024

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
Copy link
Contributor

AlekseiVambol commented Jun 27, 2024

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<_>>();

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants