-
-
Notifications
You must be signed in to change notification settings - Fork 43
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
Another G2 MSM wrong result #366
Comments
Thanks for the repro. It seems like it's once again the endomorphism acceleration that is problematic. Using constantine/constantine/math/elliptic/ec_multi_scalar_mul.nim Lines 95 to 97 in c7979b0
And removing constantine/constantine/math/elliptic/ec_multi_scalar_mul.nim Lines 406 to 437 in c7979b0
|
One thing really strange is that I tried to slice the input from 0 to 22000 or 1000 to 23000 and having too few points make the bug disappear. |
So how this bug was discovered was really strange. These are the B2 points from a Groth16 proof. The circuit is essentially doing Poseidon2 hashes. The proof always succeeded below a given circuit size and always failed above a given size, no matter what the inputs are, what the exact structure of these hashes are (linear sponge, Merkle tree, independent permutation calls), this threshold even survived changing the number of the rounds in the Poseidon permutation. However with completely different circuits, much larger circuits worked fine too... |
|
Further investigation shows that when 22528 points work while 22529 points doesn't. This is the exact value for which c, the bucket size, changes from 12 to 13. |
I found the bug: constantine/constantine/math/elliptic/ec_multi_scalar_mul.nim Lines 255 to 284 in 5308ddc
It is the This bug is hard to trigger but can be triggered reliably once understood, here is the sequence of events.
|
huh, nice detective work! |
This has been merged. Note that I did several refactorings of the internals in preparation for the first release of Constantine and support for named fields and not just named curves. Here are the important changes:
|
Wrong result for a particular G2 MSM calculation (this time
multiScalarMul_vartime
is affected).Unfortunately I don't have a small example (so far the smallest one is ~24,000 elements) and I don't have the energy or patience to try find a minimal one, so I just created a repo with all the data and code to reproduce.
Two independent implementations gives the correct result, and also constantine gives the correct result for smaller prefix vectors (I haven't done exhaustive testing here, but for example the first 10,000 elements is fine)
c7979b0
(but the bug should be present for at least a few months)The text was updated successfully, but these errors were encountered: