search

arkworks-rs / algebra

Libraries for finite field, elliptic curve, and polynomial arithmetic
https://arkworks.rs
Apache License 2.0
636 stars 248 forks source link

The current GLV implementation may not be correct #802

Open weikengchen opened 8 months ago

weikengchen commented 8 months ago

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 commented 8 months ago

I think we just need to implement this overdue code:

https://github.com/arkworks-rs/algebra/commit/f293ae886403d737811d4dbde821ed63d2509317#diff-d8344ecc09cd2bfaca236326b07295b62d2834de6561c999546f683ca49488e3R31

// could be nice to check if k1 and k2 are indeed small.
weikengchen commented 8 months ago

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

weikengchen commented 8 months ago

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