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.

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

Refactor: final exponentiation in pairings #375

Merged
merged 6 commits into from
Apr 11, 2023
Merged

Conversation

yelhousni
Copy link
Collaborator

@yelhousni yelhousni commented Apr 7, 2023

@feltroidprime was porting the Karabina optimisations in our final exp to Garaga and encountered a problem with: https://github.com/ConsenSys/gnark-crypto/blob/f93a56c714c4e6266429cac111a004e9eec7daa0/ecc/bls12-381/internal/fptower/e12.go#L227
When computing e(P,Q) * e(-P,Q) the decompression fails (in the corresponding Garaga code) at: https://github.com/ConsenSys/gnark-crypto/blob/f93a56c714c4e6266429cac111a004e9eec7daa0/ecc/bls12-381/internal/fptower/e12.go#L258
This is because g2 and g3 are both zero in that test case. In gnark-crypto this test does not fail because the case g2==g3==0 is handled "implicitly". Since we take the convention of 1/0 = 0 the returned value in this case is 1, which is what is expected as per the proof of Theorem 3.1 of Karabina's paper.

This is said, in this PR I make a suggestion to:

  • "Explicitly" handle the g2==g3==0 case, and
  • Return 1 when the result of the easy part is 1 — which is what happens in similar cases to e(P,Q) * e(-P,Q). This saves the hard part computation since 1^d==1.

@yelhousni yelhousni added cleanup Suggestion to clean up the code perf labels Apr 7, 2023
@yelhousni yelhousni added this to the v0.10.0 milestone Apr 7, 2023
@yelhousni yelhousni requested a review from gbotrel April 7, 2023 12:44
@yelhousni yelhousni self-assigned this Apr 7, 2023
@yelhousni yelhousni merged commit e700949 into develop Apr 11, 2023
@yelhousni yelhousni deleted the refactor/FinalExp branch April 11, 2023 15:21
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
cleanup Suggestion to clean up the code perf
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants