Skip to content

fix: use emulated arithmetic for GLV decomp #1167

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
Merged
ivokub merged 2 commits into from
Jul 18, 2024
Merged

fix: use emulated arithmetic for GLV decomp #1167

ivokub merged 2 commits into from
Jul 18, 2024

Conversation

@ivokub
Copy link
Collaborator

@ivokub ivokub commented Jun 12, 2024 •
edited
Loading

Description

We use GLV for scalar multiplication in 2-chains (BLS12-377 and BLS24-315). For the decomposition of scalar to be valid we have to check that s1 + λ s2 = s where s is the initial scalar and s1, s2 are the decomposed values (width length 127 bits).

For BLS12-377 we can perform this check using native arithmetic as we constrain s1, s2, λ to all be 127 bits and we never overflow the outer curve scalar field (width 377 bits).

However, for BLS24-315 we have λ with 256 bits and in this case the check s1 + λ s2 = s may overflow the native field. We compensate for it by giving additional output from the hint which cancels out the overflowed value, but this gives the malicious prover some advantage for finding invalid inputs.

Safer approach would be to perform the arithmetic using non-native arithmetic, which this PR introduces.

Type of change

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

How has this been tested?

Existing tests work.

How has this been benchmarked?

  • PLONK in PLONK before 454514 now 468122
  • scalar multiplication in PLONK before 3588 now 4927 (VarScalarMul)
  • scalar multiplication in R1CS before 1412 now 1721 (VarScalarMul)
  • scalarmul edge cases (complete arithm) in R1CS before 2532 now 3079
  • scalarmul edge cases (complete arithm) in PLONK before 6546 now 8959
  • base mul R1CS before 1028 now 1337
  • base mul PLONK before 2818 now 4157
  • joint scalar mul in R1CS before 5100 now 5647
  • joint scalar mul in PLONK before 12239 now 14651
  • joint scalar mul edge cases in R1CS before 7628 now 8926
  • joint scalar mul edge cases in PLONK before 19687 now 25293

No impact on pairing/ML/FE.

Checklist:

  • I have performed a self-review of my code
  • I have commented my code, particularly in hard-to-understand areas
  • I have made corresponding changes to the documentation
  • I have added tests that prove my fix is effective or that my feature works
  • I did not modify files generated from templates
  • golangci-lint does not output errors locally
  • New and existing unit tests pass locally with my changes
  • Any dependent changes have been merged and published in downstream modules

@ivokub ivokub added the type: bug Something isn't working label Jun 12, 2024
@ivokub ivokub self-assigned this Jun 12, 2024
@ivokub ivokub marked this pull request as ready for review June 13, 2024 08:59
@randomsleep
Copy link

randomsleep commented Jun 14, 2024

For BLS12-377 we can perform this check using native arithmetic as we constrain s1, s2, λ to all be 127 bits and we never overflow the outer curve scalar field (width 377 bits).

The code is actually checking s1 + λ * s2 == s + cc.fr * sd[2]. Although the left side may not overflow, the right side may overflow. I think we also need to apply that to BLS12-377.

@ivokub
Copy link
Collaborator Author

ivokub commented Jun 14, 2024

For BLS12-377 we can perform this check using native arithmetic as we constrain s1, s2, λ to all be 127 bits and we never overflow the outer curve scalar field (width 377 bits).

The code is actually checking s1 + λ * s2 == s + cc.fr * sd[2]. Although the left side may not overflow, the right side may overflow. I think we also need to apply that to BLS12-377.

But for bls12-377 we don't - for example see bls24-315 https://github.com/Consensys/gnark/blob/master/std/algebra/native/sw_bls24315/g1.go#L202-L204 and the corresponding in bls12-377 https://github.com/Consensys/gnark/blob/master/std/algebra/native/sw_bls12377/g1.go#L230-L233

@randomsleep
Copy link

randomsleep commented Jun 14, 2024 •
edited
Loading

Oh got it! You are right. BLS12-377 doesn't have an overflow because it's not the same equation.

@yelhousni yelhousni self-requested a review July 18, 2024 16:23
yelhousni
yelhousni approved these changes Jul 18, 2024
View reviewed changes
Copy link
Contributor

@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.

LGTM

@ivokub ivokub merged commit 4cc13fd into master Jul 18, 2024
@ivokub ivokub deleted the fix/nonantive-bls24315-glvdecomp branch July 18, 2024 16:31
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@yelhousni yelhousni yelhousni approved these changes

Assignees

@ivokub ivokub

Labels

type: bug Something isn't working

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@ivokub @randomsleep @yelhousni