Consensys
fix: use emulated arithmetic for GLV decomp
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
- [x] 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:
- [x] I have performed a self-review of my code
- [x] I have commented my code, particularly in hard-to-understand areas
- [x] I have made corresponding changes to the documentation
- [x] I have added tests that prove my fix is effective or that my feature works
- [x] I did not modify files generated from templates
- [x]
golangci-lintdoes not output errors locally - [x] New and existing unit tests pass locally with my changes
- [x] Any dependent changes have been merged and published in downstream modules
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.
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
Oh got it! You are right. BLS12-377 doesn't have an overflow because it's not the same equation.