Perf: optimize EC arithmetic

[yelhousni]

Description

A collection of small ideas to optimize the elliptic curve arithmetic in emulated and 2-chains packages (BLS12 and BLS24). Comments in the code explain the tricks.

Type of change

• New feature (non-breaking change which adds functionality)

How has this been tested?

Same tests for the existing methods.

How has this been benchmarked?

1- Emulated case: SNARK curve: BN254

• Emulated curve: e.g. secp256k1:
  ScalarMul: 385,458 scs vs. 656,839 scs
  JointScalarMul: 451,908 scs vs. 680,740 scs

• Emulated curve: e.g. BW6-761:
  ScalarMul: 1,367,064 scs vs. 2,291,619 scs
  JointScalarMul: 1,589,533 scs vs. 2,355,964 scs

2- Native case: e.g. BLS12-377/BW6-761 chain
varScalarMul G1 3,851 scs vs. 3,858 scs
JointScalarMul G1 6,191 scs vs. 6,705 scs
varScalarMul G2 9,956 scs vs. 12,579 scs

3- Some circuits of interest:

• PLONK verifier (BW6-761 in BN254) goes from 50,750,530 scs to 33,860,282 scs.
• ECRECOVER (secp256k1 in BN254) goes from 688,362 scs to 459,082 scs.

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]

I think we should add the checks that the scalar decompositions s0 and |s0| correspond to each other corresponding to the returned bit.
And have a look if we should also need to choose between different inputs which we add-sub in beginning/end of the loop. Imo we still have a chance to hit the incomplete case, but I might be wrong.
But otherwise, looks good! I think the performance improvements are significant.

Made the changes. You can review now. One thing I'm still not 100% sure about is the 0/1 (bigints) in the hint. Maybe we should assert that they are booleans in-circuit? or just revert to subtracting the subscalars and their absolute values instead.

Seems good, I think the conditional select between G and phi2(G) is good.

I'll check a bit if I can optimize a bit the consistency check between s1, s3, s5. Currently it involves multiplication s1*s1 == s5*s5, but imo we could avoid multiplications by trying to check (-1)^(1-s3)*s5 - s1 == 0. And I think I'll also see if it makes sense to output the sign bits in a separate hint as when we use non-native hint calling, then we also range check all limbs of the bit which is wasteful. If we would output the sign bits directly from a hint, then can only do AssertIsBoolean on native API.

[ivokub]

Hmm - but do we need to return both s1 and t1=|s1| from the hint? Shouldn't it be sufficient if we return |s1| and sign bit and then in-circuit would compute s1 = Select(signbit, t1, Neg(t1))? I think this could reduce the number of constraints a little.

[ivokub]

It looks like alternative approach works -- we have instead two hint functions where one returns non-native subscalars and the other one bits. When we call Select for the native bits, then they are range checked to be 0-1. This allows to avoid a few multiplications and range checks.

But I guess before merging this PR it would be better to create a new one which introduces the variants to emulated.Field.NewHint and emulated.UnwrapHint which allow native outputs.

But still, the test TestJointScalarMul6 occasionally fails now, but it is not consistent. I also tried commit bc1c711 and even there it still occasionally fails.

So I guess adding conditionally G or phi^2(G) doesn't work? Inside division hint we get ModInverse(k*p, p) which is undefined.

[ivokub]

Looking at the implementation now -- wouldn't it work better if the second point would be random? We could even compute it deterministically from a hash and make R and [2**b] R part of the curve parameters?

[yelhousni]

It looks like alternative approach works -- we have instead two hint functions where one returns non-native subscalars and the other one bits. When we call Select for the native bits, then they are range checked to be 0-1. This allows to avoid a few multiplications and range checks.

But I guess before merging this PR it would be better to create a new one which introduces the variants to emulated.Field.NewHint and emulated.UnwrapHint which allow native outputs.

But still, the test TestJointScalarMul6 occasionally fails now, but it is not consistent. I also tried commit bc1c711 and even there it still occasionally fails.

So I guess adding conditionally G or phi^2(G) doesn't work? Inside division hint we get ModInverse(k*p, p) which is undefined.

I think G and phi^2(G) still work fine but they need to be inverted the Select logic. Pushed the fix which seems to solce the TestJointScalarMul6 failing test.

[yelhousni]

Looking at the implementation now -- wouldn't it work better if the second point would be random? We could even compute it deterministically from a hash and make R and [2**b] R part of the curve parameters?

randomly as in at each call of JointScalarMul we sample a random point R and compute [2**b]R? That would work in the sense that it's unfeasible for an attacker to come up with two input points P and Q such that P+Q = phi(R). But if the random point is part of the curve parameters I don't think it's different from having the base point G. If R is publicly available one can still craft the failing input points P and Q.

[ivokub]

I separated the hint calling with native outputs in a separate PR (#1080). That PR also adds non-native hint calling with native inputs and implements tests. This means that we could revert the commit cdedeca from this PR as it would be merged in from #1080. But that means that #1080 needs to be merged first and then merged into PR.

Otherwise, your changes look good. I think the comments now are very nice, they make quite an understandable implementation.

[ivokub]

LGTM!

[ivokub]

Looking at the implementation now -- wouldn't it work better if the second point would be random? We could even compute it deterministically from a hash and make R and [2**b] R part of the curve parameters?

randomly as in at each call of JointScalarMul we sample a random point R and compute [2**b]R? That would work in the sense that it's unfeasible for an attacker to come up with two input points P and Q such that P+Q = phi(R). But if the random point is part of the curve parameters I don't think it's different from having the base point G. If R is publicly available one can still craft the failing input points P and Q.

I see. In this case I do agree it is better to stay with G and phi2(G) as we already have them.

[ivokub]

Seemed that master applied well. I would say good to merge from my side!