-
Notifications
You must be signed in to change notification settings - Fork 240
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
The current GLV implementation may not be correct #802
Comments
I think we just need to implement this overdue code: f293ae8#diff-d8344ecc09cd2bfaca236326b07295b62d2834de6561c999546f683ca49488e3R31
|
Let me submit a PR for test-template first to see how the issue can be handled. |
Can confirm that BN254 failed the test: ---- curves::tests::g1_glv::test_scalar_decomposition stdout ---- ---- curves::tests::g2_glv::test_scalar_decomposition stdout ---- |
I tested on BN254 with Fr = 14226294082152339227274917010873249985458047913852393750281719691125978796426, the algorithm decomposes it into two numbers, one is 128 bits, but the other one is 191 bits. The computation result is correct, but this is clearly suboptimal.
It appears that the issue is due to the wrong sign of beta_2. Flipping its sign fixes the issue for BN254.
I find the tricky part is here.
https://github.com/arkworks-rs/algebra/blob/master/curves/bn254/src/curves/g1.rs#L60
https://github.com/arkworks-rs/algebra/blob/master/ec/src/scalar_mul/glv.rs#L40
A little bit uncertain how the GLV basis shall be presented.
Another issue is that the original GLV algorithm requires "rounded division" rather than simple division that the codebase currently uses. This would affect the result of one of the inequality in the GLV paper, where the rounded division (implying that the gap is smaller than "1/2") does have an impact on the decomposition quality.
Needs input from @simonmasson, @Pratyush, and @mmagician.
In addition, I think it helps to strength the GLV test by checking if the decomposition result is as expected.
The text was updated successfully, but these errors were encountered: