Switch to exhaustive groups with small B coefficient #1192

sipa commented at 9:27 PM on January 10, 2023: contributor

This has the advantage that in the future, multiplication with B can be done using secp256k1_fe_mul_int rather than the slower secp256k1_fe_mul.

sipa force-pushed on Jan 10, 2023

sipa cross-referenced this on Jan 10, 2023 from issue Add x-only ecmult_const version with x specified as n/d by sipa

in sage/gen_exhaustive_groups.sage:81 in 28cba925eb outdated

 128 | +
 129 |  print("")
 130 |  print("")
 131 |  print("/* To be put in src/group_impl.h: */")
 132 | +for f in sorted(gens.keys()):
 133 | +    # Use as generator/2 the one with lowest b, and lowest (x, y) generator (interpreted as integers).

real-or-random commented at 8:54 AM on January 11, 2023:

I guess it doesn't matter but take min(generator/2) instead of just min(generator)?

    # Use as generator/2 the one with lowest b, and lowest (x, y) generator (interpreted as non-negative integers).

sipa commented at 6:28 PM on January 11, 2023:

I guess it doesn't matter but take min(generator/2) instead of just min(generator)?

I don't understand what you're suggesting here.

real-or-random commented at 6:40 PM on January 11, 2023:

nevermind,

in sage/gen_exhaustive_groups.sage:138 in 28cba925eb outdated

 172 |  print("#    error No known generator for the specified exhaustive test group order.")
 173 |  print("#  endif")
 174 | +print("#else")
 175 | +print("static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_G;")
 176 | +output_b(7)
 177 | +print("#endif")

real-or-random commented at 9:08 AM on January 11, 2023:

print("#else")
print()
print("static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_G;")
output_b(7)
print()
print("#endif")

I think this improves readability of the output a lot. Same for the other #else/#elif branches.

in sage/gen_exhaustive_groups.sage:75 in 28cba925eb outdated

 122 | +    print("    0x%08x, 0x%08x, 0x%08x, 0x%08x,\\" % tuple((int(g[1]) >> (32 * (7 - i))) & 0xffffffff for i in range(4)))
 123 | +    print("    0x%08x, 0x%08x, 0x%08x, 0x%08x\\" % tuple((int(g[1]) >> (32 * (7 - i))) & 0xffffffff for i in range(4, 8)))
 124 | +    print(")")
 125 | +
 126 | +def output_b(b):
 127 | +    print(f"#define SECP256K1_B {int(b)}U")

real-or-random commented at 9:09 AM on January 11, 2023:

It won't matter but is there a specific reason you put the U? secp256k1_fe_mul_int takes a signed int.

sipa commented at 6:29 PM on January 11, 2023:

Heh, maybe secp256k1_fe_mul_int should be changed to take an unsigned as input...

sipa commented at 9:00 PM on January 11, 2023:

Removed the "U".

in sage/gen_exhaustive_groups.sage:79 in 28cba925eb outdated

 126 | +def output_b(b):
 127 | +    print(f"#define SECP256K1_B {int(b)}U")
 128 | +
 129 |  print("")
 130 |  print("")
 131 |  print("/* To be put in src/group_impl.h: */")

real-or-random commented at 9:10 AM on January 11, 2023:

Maybe add another line with Generated by ...

sipa commented at 9:00 PM on January 11, 2023:

I wrapped both sections in lines saying "Begin/End of section generated by sage/gen_exhaustive_groups.size.".

real-or-random commented at 9:10 AM on January 11, 2023: contributor

Great :)

This should touch also touch the exhaustive tests code touched in https://github.com/bitcoin-core/secp256k1/commit/b110c106fa9704e30f6b0c2ffa6a2697031e89a8, at least the comments.

apoelstra approved

apoelstra commented at 2:17 PM on January 11, 2023: contributor

ACK 28cba925eb8d6b434604595fad92bd9e1da54913

sipa force-pushed on Jan 11, 2023

apoelstra approved

apoelstra commented at 11:45 PM on January 11, 2023: contributor

ACK d4cf3f2da1e35118ede5b682082827f7d0393334

real-or-random commented at 11:34 AM on January 12, 2023: contributor

When running the sage script locally, I noticed that it outputs a group of order 7, too. Did you omit this on purpose when copying the output of the script the C files?

Anyway, the exhaustive tests break don't compile for this order of 7. Here's a branch that fixes this problem and also has fixups (please squash) to your commits which include the 7 group (plus further formatting nits, what I actually had in mind here #1192 (review)): https://github.com/real-or-random/secp256k1/commits/202301_small_b

This comment of mine is still unaddressed:

This should touch also touch the exhaustive tests code touched in b110c10, at least the comments.

Sorry, I didn't foresee that my comment about using mul_int in #1118 gets us sidetracked so much... ^^

sipa commented at 7:44 PM on January 13, 2023: contributor

When running the sage script locally, I noticed that it outputs a group of order 7, too. Did you omit this on purpose when copying the output of the script the C files?

No, for me the output does not include size 7:

Analyzing curve y^2 = x^3 + 6
- Finding subgroups
- Analyzing subgroup of order 2
  - Bad size
- Analyzing subgroup of order 7
  - No endomorphism for this subgroup
- Analyzing subgroup of order 2
  - Bad size
...

Anyway, the exhaustive tests break don't compile for this order of 7. Here's a branch that fixes this problem and also has fixups (please squash) to your commits which include the 7 group (plus further formatting nits, what I actually had in mind here #1192 (review)): https://github.com/real-or-random/secp256k1/commits/202301_small_b

Bizarre that 7 actually works (your branch compiles, and the exhaustive tests pass...).

This comment of mine is still unaddressed:

This should touch also touch the exhaustive tests code touched in b110c10, at least the comments.

I have no idea what you're trying to say.

sipa commented at 8:55 PM on January 13, 2023: contributor

Bizarre that 7 actually works (your branch compiles, and the exhaustive tests pass...).

Found it!

y^2 = x^3 + 6 actually has two subgroups of order 7, leading to 48 valid generators. Only 12 of those generators generate a group which admit a GLV endomorphism. Apparently Sage versions report different generators, which means the code in this PR may or may not find a GLV-compatible one. Fixing.

sipa commented at 9:11 PM on January 13, 2023: contributor

I have no idea what you're trying to say.

Oh, I had missed you were talking about the C code touched there. Indeed, will address.

Switch to exhaustive groups with small B coefficient 4934aa7995

Introduce SECP256K1_B macro for curve b coefficient ce60785b26

sipa force-pushed on Jan 13, 2023

sipa commented at 10:09 PM on January 13, 2023: contributor

Addressed comments, I think.

real-or-random approved

real-or-random commented at 8:07 PM on January 16, 2023: contributor

ACK ce60785b2654e60b43577dd75996b7020afbfec8 also ran the exhaustive tests with the group of size 7

I still think that https://github.com/real-or-random/secp256k1/commit/7eef8f4a305a72567db0b563260081712304b5fb is a good cleanup but we can also add it after this PR

edit: I guess we want to stick with the group of size 13 as a default? It's reasonably fast.

apoelstra approved

apoelstra commented at 9:04 PM on January 16, 2023: contributor

ACK ce60785b2654e60b43577dd75996b7020afbfec8

real-or-random merged this on Jan 16, 2023

real-or-random closed this on Jan 16, 2023

real-or-random commented at 8:54 AM on January 17, 2023: contributor

For our future curious minds:

00:44 <sipa> Let G1 and G2 be generators of the two endomorphism-compatible order-7 subgroups.
00:46 <sipa> Let C_i be the subgroup consisting of itG1 + tG2 for t=0..6 (with i=infinity for the group consisting of tG1).
00:47 <sipa> Then beta*C_i lands you in C_{2i}.
00:47 <sipa> If i=0 or i=inf, it's an endomorphism.
01:20 <sipa> Ah! And there is a much simpler explanation.
01:21 <sipa> With the same two generators G1,G2 above, beta-multiplying a*G1 + b*G2 gives 2*a*G1 + 4*b*G2.
01:21 <sipa> If you started off with a*G1, you get twice your input, so lambda=2.
01:22 <sipa> If you started off with b*G2, you get 4 times your input, so lambda=4.
01:22 <sipa> But if you started off with a linear combination with non-zero contributions from both, you get a different linear combination that's not a pure multiple back.
01:24 <sipa> Put otherwise, for any independent generators G1,G2 of the order-49 subgroup, if you think of the elements as vectors with basis G1,G2, then beta-multiplication is effectively a linear transformation on those vectors.
01:24 <sipa> That linear transformation has eigenvalues 2 and 4.
01:25 <sipa> The subgroup consisting of eigenvectors corresponding to eigenvalue 2 is the subgroup in which the endomorphism works, with lambda=2.
01:25 <sipa> Same with eigenvalue 4.

https://gnusha.org/secp256k1/2023-01-16.log

dhruv referenced this in commit 4d33046ce3 on Feb 1, 2023

dhruv referenced this in commit 55e7f2cf2b on Feb 2, 2023

stratospher referenced this in commit 647f63669e on Feb 6, 2023

dhruv referenced this in commit a4351c0df6 on Feb 20, 2023

stratospher referenced this in commit 23f825fc8b on Feb 21, 2023

hebasto referenced this in commit 7c0cc5d976 on Mar 7, 2023

dhruv referenced this in commit a5df79db12 on Mar 7, 2023

dhruv referenced this in commit 77b510d84c on Mar 7, 2023

sipa referenced this in commit 763079a3f1 on Mar 8, 2023

div72 referenced this in commit 945b094575 on Mar 14, 2023

vmta referenced this in commit e1120c94a1 on Jun 4, 2023

vmta referenced this in commit 8f03457eed on Jul 1, 2023

jonasnick cross-referenced this on Jul 20, 2023 from issue Upstream PRs 1160, 1193, 1169, 1190, 1192, 1194, 1196, 1195, 1170, 1172, 1200, 1199, 1203, 1201, 1206, 1078, 1209, 979, 1212, 1218, 1217, 1221, 1222 by jonasnick