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.

Sign up for GitHub

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

Jump to bottom

The current GLV implementation may not be correct #802

Open
weikengchen opened this issue Mar 7, 2024 · 3 comments
Open

The current GLV implementation may not be correct #802

weikengchen opened this issue Mar 7, 2024 · 3 comments

Comments

@weikengchen
Copy link
Member

weikengchen commented Mar 7, 2024 •
edited
Loading

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.
@weikengchen
Copy link
Member Author

I think we just need to implement this overdue code:

f293ae8#diff-d8344ecc09cd2bfaca236326b07295b62d2834de6561c999546f683ca49488e3R31

// could be nice to check if k1 and k2 are indeed small.

@weikengchen
Copy link
Member Author

Let me submit a PR for test-template first to see how the issue can be handled.

@weikengchen
Copy link
Member Author

Can confirm that BN254 failed the test:

---- curves::tests::g1_glv::test_scalar_decomposition stdout ----
thread 'curves::tests::g1_glv::test_scalar_decomposition' panicked at /home/ubuntu/Rustrover/algebra/test-templates/src/glv.rs:35:9:
k2 has 187 bits
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

---- curves::tests::g2_glv::test_scalar_decomposition stdout ----
thread 'curves::tests::g2_glv::test_scalar_decomposition' panicked at /home/ubuntu/Rustrover/algebra/test-templates/src/glv.rs:35:9:
k2 has 187 bits

@weikengchen weikengchen mentioned this issue Mar 8, 2024
Merged
6 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@weikengchen