Skip to content

Fix: GLV exponentiation in GT with large exponents#451

Merged
yelhousni merged 7 commits intomasterfrom
fix/glv
Oct 2, 2023
Merged

Fix: GLV exponentiation in GT with large exponents#451
yelhousni merged 7 commits intomasterfrom
fix/glv

Conversation

@ThomasPiellard
Copy link
Copy Markdown
Contributor

@ThomasPiellard ThomasPiellard commented Sep 29, 2023

Description

  • ExpGLV on 𝔽_{q}* /(𝔽_{q}*)ʳ uses max(len(s1), len(s2)) in the main loop (as in G1 and G2)
  • mulWindowed failed for negative exponents ( [-s]G returned [s]G), the PR also fixes this.

Type of change

  • Bug fix (non-breaking change which fixes an issue)

How has this been tested?

  • Added a test that was previously failing with a big exponent for ExpGLV
  • Added a test to check the property [-s]G=-[s]G

Checklist:

  • I have performed a self-review of my code
  • I have added tests that prove my fix is effective or that my feature works
  • New and existing unit tests pass locally with my changes

@yelhousni yelhousni added type: bug Something isn't working type: cleanup Suggestion to clean up the code labels Sep 29, 2023
@yelhousni yelhousni added this to the v0.10.0 milestone Sep 29, 2023
@github-actions
Copy link
Copy Markdown

Summary

✅ Passed: 5883
❌ Failed: 0
🚧 Skipped: 5

🚧 Skipped

  • TestReference (github.com/consensys/gnark-crypto/ecc/bn254/fr/sis)
  • TestLimbDecomposition (github.com/consensys/gnark-crypto/ecc/bn254/fr/sis)
  • TestAppend (github.com/consensys/gnark-crypto/ecc/bn254/fr/tensor-commitment)
  • TestAppendSis (github.com/consensys/gnark-crypto/ecc/bn254/fr/tensor-commitment)
  • TestCommitmentSis (github.com/consensys/gnark-crypto/ecc/bn254/fr/tensor-commitment)

@github-actions
Copy link
Copy Markdown

Summary

✅ Passed: 5883
❌ Failed: 0
🚧 Skipped: 5

🚧 Skipped

  • TestReference (github.com/consensys/gnark-crypto/ecc/bn254/fr/sis)
  • TestLimbDecomposition (github.com/consensys/gnark-crypto/ecc/bn254/fr/sis)
  • TestAppend (github.com/consensys/gnark-crypto/ecc/bn254/fr/tensor-commitment)
  • TestAppendSis (github.com/consensys/gnark-crypto/ecc/bn254/fr/tensor-commitment)
  • TestCommitmentSis (github.com/consensys/gnark-crypto/ecc/bn254/fr/tensor-commitment)

Copy link
Copy Markdown
Collaborator

@yelhousni yelhousni left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

All looks good 👍
The last two commits just fix few typos and some cosmetics:

  • merges the new (exp, expGLV) with the old (exp, expGLV and CyclotomicExp) test;
  • uses genA variable to switch GenE12() for GenE24() or GenE6() when needed;
  • uses {{ toUpper .Name}} for curves' names instead of BN254 in the new test;
  • manually apply the fix (and test) to BLS24-* and BW6-* as the towers are not auto-generated there.

@yelhousni yelhousni changed the title Fix/glv Fix: GLV exponentiation in GT with large exponents Sep 29, 2023
@yelhousni yelhousni merged commit ec6be1a into master Oct 2, 2023
@yelhousni yelhousni deleted the fix/glv branch October 2, 2023 14:11

res.Set(&g1Infinity)
ops[0].Set(a)
e := s
Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@yelhousni @ThomasPiellard this snippet is weird? didn't review this PR but to me this code is useless.
What does this code do; assign a *big.Int, overwrites it with an object from a pool, and Neg(s) into e, the object of the pool before discarding it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

type: bug Something isn't working type: cleanup Suggestion to clean up the code

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants