Switch to exhaustive groups with small B coefficient #1192

pull sipa wants to merge 2 commits into bitcoin-core:master from sipa:202301_small_b changing 5 files +161 −115
  1. 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.

  2. sipa force-pushed on Jan 10, 2023
  3. sipa force-pushed on Jan 10, 2023
  4. 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,

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

  6. 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".

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

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

  9. apoelstra approved
  10. apoelstra commented at 2:17 PM on January 11, 2023: contributor

    ACK 28cba925eb8d6b434604595fad92bd9e1da54913

  11. sipa force-pushed on Jan 11, 2023
  12. sipa force-pushed on Jan 11, 2023
  13. apoelstra approved
  14. apoelstra commented at 11:45 PM on January 11, 2023: contributor

    ACK d4cf3f2da1e35118ede5b682082827f7d0393334

  15. 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... ^^

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

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

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

  19. Switch to exhaustive groups with small B coefficient 4934aa7995
  20. Introduce SECP256K1_B macro for curve b coefficient ce60785b26
  21. sipa force-pushed on Jan 13, 2023
  22. sipa commented at 10:09 PM on January 13, 2023: contributor

    Addressed comments, I think.

  23. real-or-random approved
  24. 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.

  25. apoelstra approved
  26. apoelstra commented at 9:04 PM on January 16, 2023: contributor

    ACK ce60785b2654e60b43577dd75996b7020afbfec8

  27. real-or-random merged this on Jan 16, 2023
  28. real-or-random closed this on Jan 16, 2023
  29. 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

  30. dhruv referenced this in commit 4d33046ce3 on Feb 1, 2023
  31. dhruv referenced this in commit 55e7f2cf2b on Feb 2, 2023
  32. stratospher referenced this in commit 647f63669e on Feb 6, 2023
  33. dhruv referenced this in commit a4351c0df6 on Feb 20, 2023
  34. stratospher referenced this in commit 23f825fc8b on Feb 21, 2023
  35. hebasto referenced this in commit 7c0cc5d976 on Mar 7, 2023
  36. dhruv referenced this in commit a5df79db12 on Mar 7, 2023
  37. dhruv referenced this in commit 77b510d84c on Mar 7, 2023
  38. sipa referenced this in commit 763079a3f1 on Mar 8, 2023
  39. div72 referenced this in commit 945b094575 on Mar 14, 2023
  40. vmta referenced this in commit e1120c94a1 on Jun 4, 2023
  41. vmta referenced this in commit 8f03457eed on Jul 1, 2023
  42. delta1 referenced this in commit 3f32c20932 on Aug 8, 2023
  43. delta1 referenced this in commit 31ac0c1081 on Aug 31, 2023
  44. janus referenced this in commit 4816e2a921 on Sep 3, 2023
  45. backpacker69 referenced this in commit 26f6d832fb on Mar 5, 2024
  46. str4d referenced this in commit b350ac56ac on Jun 4, 2025
  47. Fabcien referenced this in commit 966df441ee on Apr 8, 2026
  48. Fabcien referenced this in commit 1501d080d0 on Apr 8, 2026
Contributors
sipareal-or-randomapoelstra
github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin-core/secp256k1. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-05-19 06:52 UTC