Add x-only ecmult_const version with x specified as n/d #1118

pull sipa wants to merge 2 commits into bitcoin-core:master from sipa:202206_ecmult_xonly changing 4 files +263 −4
  1. sipa commented at 6:07 pm on July 3, 2022: contributor

    This implements a generalization of Peter Dettman’s sqrt-less x-only random-base multiplication algorithm from #262, using the Jacobi symbol algorithm from #979. The generalization is to permit the X coordinate of the base point to be specified as a fraction $n/d$:

    To compute $x(q \cdot P)$, where $x(P) = n/d$:

    • Compute $g=n^3 + 7d^3$.
    • Let $P’ = (ng, g^2, 1)$ (the Jacobian coordinates of $P$ mapped to the isomorphic curve $y^2 = x^3 + 7(dg)^3$).
    • Compute the Jacobian coordinates $(X’,Y’,Z’) = q \cdot P’$ on the isomorphic curve.
    • Return $X’/(dgZ’^2)$, which is the affine x coordinate on the isomorphic curve $X/Z’^2$ mapped back to secp256k1.

    This ability to specify the X coordinate as a fraction is useful in the context of x-only Elligator Swift, which can decode to X coordinates on the curve without inversions this way.

  2. sipa cross-referenced this on Jul 3, 2022 from issue x-only ECDH without sqrt by peterdettman
  3. peterdettman commented at 6:32 pm on July 3, 2022: contributor
    Hey @sipa, cool idea. Should that just be sqrt(g) in the second step?
  4. sipa commented at 6:42 pm on July 3, 2022: contributor

    @peterdettman I don’t think so.

    • x = X / Z^2 = n*g / sqrt(d*g)^2 = n*g / (d*g) = n/d = x
    • y = Y / Z^2 = g^2 / sqrt(d*g)^3 = (n^3 + B*d^3)^2 / sqrt(d^3) / (n^3 + B*d^3)^1.5 = sqrt(n^3 + B*d^3) / sqrt(d^3) = sqrt(n^3/d^3 + B) = y
  5. peterdettman commented at 6:48 pm on July 3, 2022: contributor
    OK, well it’s late here, so I’ll go over it when not so tired. A followup question: is there an assumption that d is square? If not, a better starting point might be (y*d^3)^2 =(x*d^2)^3 + B*d^6 i.e. g = (n.d)^3 + B*d^6, so that this will not be a quadratic twist if d is non-square.
  6. sipa commented at 6:49 pm on July 3, 2022: contributor

    @peterdettman It works for d square or non-square (obviously not for d=0). The reason is that g = y^2*d^3, and thus d*g = y^2*d^4 = (y*d^2)^2, which is always square if n/d is an x coordinate on the curve. In fact, that’s how the known_on_curve=0 check works: compute jacobi symbol of d*g.

    At least the unit tests here seem to agree that d does not need to be square.

  7. peterdettman commented at 7:05 pm on July 3, 2022: contributor
    Oh I see you meant that (n*g, +- g^2, sqrt(d*g)) is on the original curve, not the one implied in step 1.
  8. sipa commented at 7:57 pm on July 3, 2022: contributor

    Yeah, so just operationally, the algorithm is:

    • Input $n$, $d$, $q$
    • Compute $g = n^3 + 7d^3$
    • Construct affine point $P = (ng, g^2)$ on isomorphic curve
    • Compute Jacobian result point $R = (X, Y, Z) = q \cdot P$ on isomorphic curve
    • Return $X / (Z^2 d g)$, which is the affine x coordinate on the original curve
  9. sipa cross-referenced this on Jul 21, 2022 from issue ElligatorSwift + integrated x-only DH by sipa
  10. sipa force-pushed on Nov 2, 2022
  11. sipa force-pushed on Nov 4, 2022
  12. sipa force-pushed on Dec 12, 2022
  13. sipa commented at 6:08 pm on December 12, 2022: contributor
    Rebased on updated #979.
  14. in src/ecmult_const.h:31 in 2a04ee074e outdated 
    25+ * If known_on_curve is 0, a verification is performed that n/d is a valid X
26+ * coordinate, and 0 is returned if not. Otherwise, 1 is returned.
27+ *
28+ * d being NULL is interpreted as d=1.
29+ *
30+ * Constant time in the value of q, but not any other inputs.
    real-or-random commented at 3:48 pm on January 10, 2023:
    Just an orthogonal thought that occurred to me a few days ago: I think we should have a “formal” naming convention for secret parameters (in which the algorithm is constant-time), e.g., a prefix or a suffix or capitalization. I can open an issue if you think it’s a good idea.
    sipa commented at 4:09 pm on January 10, 2023:
    I like that idea.
  15. in src/ecmult_const.h:38 in 2a04ee074e outdated 
    33+    secp256k1_fe* r,
34+    const secp256k1_fe *n,
35+    const secp256k1_fe *d,
36+    const secp256k1_scalar *q,
37+    int bits,
38+    int known_on_curve);
    real-or-random commented at 3:49 pm on January 10, 2023:
    style micro nit: maybe move the ); to the next line then.
    sipa commented at 3:55 pm on January 11, 2023:
    Done.
  16. in src/ecmult_const_impl.h:249 in 2a04ee074e outdated 
    244+    secp256k1_fe_mul(&g, &g, n);
245+    if (d) {
246+        secp256k1_fe b;
247+        secp256k1_fe_sqr(&b, d);
248+        secp256k1_fe_mul(&b, &b, d);
249+        secp256k1_fe_mul(&b, &b, &secp256k1_fe_const_b);
    real-or-random commented at 3:56 pm on January 10, 2023:
    We have secp256k1_fe_mul_int for small ints.
    sipa commented at 4:10 pm on January 10, 2023:

    B is not small for exhaustive test curves.

    Maybe we can adapt the curve parameter generation script so that it is, though.

    real-or-random commented at 4:12 pm on January 10, 2023:
    Oh, I missed that fact.
    sipa commented at 10:22 pm on January 10, 2023:
    See #1192.
  17. in src/ecmult_const_impl.h:329 in 2a04ee074e outdated 
    252+            secp256k1_fe c;
253+            secp256k1_fe_mul(&c, &g, d);
254+            if (secp256k1_fe_jacobi_var(&c) < 0) return 0;
255+        }
256+    } else {
257+        secp256k1_fe_add(&g, &secp256k1_fe_const_b);
    real-or-random commented at 4:01 pm on January 10, 2023:
    not this PR: Now that I see this, I wonder if we should get rid of secp256k1_fe_const_b and simply call secp256k1_fe_set_int… I don’t think it makes a measurable difference in performance (or it may even be faster).
    sipa commented at 3:27 pm on January 11, 2023:
    I’m thinking about adding a secp256k1_fe_add_int which is likely even faster, but leaving that for another PR.
  18. real-or-random commented at 4:03 pm on January 10, 2023: contributor

    Concept ACK

    I might suggest some additions to the comments that may have helped me understanding. (I can’t remember, would this be the first “effective-affine” thing we merge?)

    Would it make sense to tests this in exhaustive tests?

    Can you rebase on #979?

  19. sipa force-pushed on Jan 11, 2023
  20. sipa commented at 0:22 am on January 11, 2023: contributor
    Rebased on #979, and also included #1192.
  21. sipa force-pushed on Jan 11, 2023
  22. sipa commented at 3:07 am on January 11, 2023: contributor
    @real-or-random Added a longer explanation, and an exhaustive test.
  23. in src/ecmult_const_impl.h:246 in f0bcb803a3 outdated 
    241+     * Let phi_u be the isomorphism that maps (x, y) on secp256k1 curve y^2 = x^3 + 7 to
242+     * x' = u^2*x, y' = u^3*y on curve y'^2 = x'^3 + u^6*7. This new curve has the same order as
243+     * the original (it is isomorphic), but moreover, has the same addition/doubling formulas, as
244+     * the curve b=7 coefficient does not appear in those formulas.
245+     *
246+     * This means any computation on secp256k1 can be peformed by applying phi_u for any non-zero
    real-or-random commented at 9:43 am on January 11, 2023:
    “performed”
    sipa commented at 3:54 pm on January 11, 2023:
    Rewritten.
  24. in src/ecmult_const_impl.h:244 in f0bcb803a3 outdated 
    239+     * Background: the effective affine technique
240+     *
241+     * Let phi_u be the isomorphism that maps (x, y) on secp256k1 curve y^2 = x^3 + 7 to
242+     * x' = u^2*x, y' = u^3*y on curve y'^2 = x'^3 + u^6*7. This new curve has the same order as
243+     * the original (it is isomorphic), but moreover, has the same addition/doubling formulas, as
244+     * the curve b=7 coefficient does not appear in those formulas.
    real-or-random commented at 9:49 am on January 11, 2023:
    maybe clarify that this may not be true for all formulas but for it’s true for the group laws we use (affine and jacobian)
    sipa commented at 3:54 pm on January 11, 2023:
    Done.
  25. in src/ecmult_const_impl.h:242 in f0bcb803a3 outdated 
    237+     *
238+     *
239+     * Background: the effective affine technique
240+     *
241+     * Let phi_u be the isomorphism that maps (x, y) on secp256k1 curve y^2 = x^3 + 7 to
242+     * x' = u^2*x, y' = u^3*y on curve y'^2 = x'^3 + u^6*7. This new curve has the same order as
    real-or-random commented at 9:53 am on January 11, 2023:
    A good reference here is is Example 9.5.3 in https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch9.pdf
    sipa commented at 3:54 pm on January 11, 2023:
    Added. I think you mean Example 9.5.2.
  26. real-or-random commented at 9:54 am on January 11, 2023: contributor
    That explanation is very clear indeed!
  27. sipa force-pushed on Jan 11, 2023
  28. in src/tests.c:4358 in 886bef588f outdated 
    4350@@ -4283,6 +4351,68 @@ void ecmult_const_mult_zero_one(void) {
4351     ge_equals_ge(&res2, &point);
4352 }
4353 
4354+void ecmult_const_mult_xonly(void) {
4355+    int i;
4356+
4357+    /* Test correspondence between secp256k1_ecmult_const and secp256k1_ecmult_const_xonly. */
4358+    for (i = 0; i < 2*count; ++i) {
    real-or-random commented at 4:50 pm on January 11, 2023: 
    0    for (i = 0; i < 2*COUNT; ++i) {
  29. in src/tests.c:4390 in 886bef588f outdated 
    4385+        secp256k1_fe_mul(&v, &v, &resx);
4386+        CHECK(check_fe_equal(&v, &resj.x));
4387+    }
4388+
4389+    /* Test that secp256k1_ecmult_const_xonly correctly rejects X coordinates not on curve. */
4390+    for (i = 0; i < 2*count; ++i) {
    real-or-random commented at 4:50 pm on January 11, 2023: 
    0    for (i = 0; i < 2*COUNT; ++i) {
  30. real-or-random commented at 4:50 pm on January 11, 2023: contributor
    that should fix the compilation failures on CI
  31. sipa force-pushed on Jan 11, 2023
  32. in src/tests_exhaustive.c:73 in 359031bf44 outdated 
    68+        if (!secp256k1_fe_is_zero(nz)) {
69+            break;
70+        }
71+    }
72+    /* Infinitesimal probability of spurious failure here */
73+    CHECK(tries >= 0);
    real-or-random commented at 5:10 pm on January 11, 2023:
    (Is random_fe biased towards zero? I don’t think so.)
    sipa commented at 5:15 pm on January 11, 2023:

    No, random_fe should create a uniformly random field element.

    Note that this code is copied from src/tests.c.

    real-or-random commented at 5:17 pm on January 11, 2023:

    Okay, I was about to say: then just use random_fe and don’t bother with zero at all?

    but if this is stolen from the other file, then let’s not touch it, yes.

  33. real-or-random commented at 5:13 pm on January 11, 2023: contributor
    ACK on the last two commits
  34. real-or-random cross-referenced this on Jan 12, 2023 from issue Switch to exhaustive groups with small B coefficient by sipa
  35. sipa force-pushed on Jan 26, 2023
  36. sipa cross-referenced this on Jan 27, 2023 from issue Add x-only ECDH support to ecdh module by sipa
  37. real-or-random commented at 2:46 pm on March 1, 2023: contributor
    needs rebase :)
  38. sipa force-pushed on Mar 1, 2023
  39. sipa commented at 3:33 pm on March 1, 2023: contributor
    Rebased after #979 merge.
  40. in src/ecmult_const_impl.h:316 in 263907296f outdated 
    304+    secp256k1_fe_sqr(&g, n);
305+    secp256k1_fe_mul(&g, &g, n);
306+    if (d) {
307+        secp256k1_fe b;
308+        secp256k1_fe_sqr(&b, d);
309+        secp256k1_fe_mul_int(&b, SECP256K1_B);
    real-or-random commented at 4:19 pm on March 1, 2023:

    b now has magnitude SECP256K1_B == 7, which happens to be just below 8, the maximum for the following fe_mul call.

    So, we better don’t switch to a different curve in the future. ;) On a more serious note, I don’t know how much our code depends on B, but I think it’s a good idea to avoid introducing further dependencies on the B in the code base.

    If you agree, we could do this:

    0        VERIFY_CHECK(SECP256K1_B <= 8); /* magnitude of b will be <= 8 after the next call */
1        secp256k1_fe_mul_int(&b, SECP256K1_B);

    Of course, the same is already checked now in fe_verify but this makes it a bit more explicit.

    sipa commented at 8:10 pm on March 1, 2023:
    Added.
  41. in src/ecmult_const_impl.h:285 in 263907296f outdated 
    280+     * = (n/d * sqrt^2(d*g), y * sqrt^3(d*g), sqrt(d*g))
281+     * = (n/d * d*g, y * +-sqrt(d^3*g^3), sqrt(d*g))
282+     * = (n/d * d*g, +-sqrt(g/d^3) * +-sqrt(d^3*g^3), sqrt(d*g))
283+     * = (n*g, +-sqrt(g/d^3 * d^3*g^3), sqrt(d*g))
284+     * = (n*g, +-sqrt(g^4), sqrt(d*g))
285+     * = (n*g, +-g^2, sqrt(d*g))
    real-or-random commented at 4:31 pm on March 1, 2023: 
    0     * The input point (n/d, y) also has Jacobian coordinates:
1     *   (n/d, y, 1)
2     * = (n/d * sqrt^2(d*g), y * sqrt^3(d*g), sqrt(d*g))
3     * = (n/d * d*g, y * sqrt(d^3*g^3), sqrt(d*g))
4     * = (n/d * d*g, +-sqrt(g/d^3) * sqrt(d^3*g^3), sqrt(d*g))
5     * = (n*g, +-sqrt(g/d^3 * d^3*g^3), sqrt(d*g))
6     * = (n*g, +-sqrt(g^4), sqrt(d*g))
7     * = (n*g, +-g^2, sqrt(d*g))
    sipa commented at 7:39 pm on March 1, 2023:

    I don’t believe these changes are correct.

    √(d3g3) may have the opposite sign of (√(dg))3 for example.

    real-or-random commented at 11:30 am on March 2, 2023:

    Ok, yes…

    (indepedent nit: adding more space left to the equation would make it more readable. The * from the comments make it hard to read.)

    sipa commented at 10:04 pm on March 2, 2023:
    Indented a bit.
  42. real-or-random commented at 4:32 pm on March 1, 2023: contributor
    ACK mod nits
  43. sipa force-pushed on Mar 1, 2023
  44. sipa cross-referenced this on Mar 1, 2023 from issue Add secp256k1_fe_add_int function by sipa
  45. real-or-random approved
  46. real-or-random commented at 11:31 am on March 2, 2023: contributor
    ACK c13f877da5f9de008a181df1bfb24342a2799b9b
  47. sipa force-pushed on Mar 2, 2023
  48. sipa force-pushed on Mar 2, 2023
  49. real-or-random approved
  50. real-or-random commented at 11:03 pm on March 2, 2023: contributor
    ACK a6412d2903d3e057d3806bf0132a4e4a62136f9c
  51. sipa force-pushed on Mar 7, 2023
  52. sipa commented at 2:40 pm on March 7, 2023: contributor
    Rebased on #1217, making use of the new secp256k1_fe_add_int.
  53. real-or-random approved
  54. real-or-random commented at 2:50 pm on March 7, 2023: contributor
    ACK 9c69617478c780233fe24cd7f9ada65f5c8d8763
  55. in src/ecmult_const.h:40 in 9c69617478 outdated 
    35+    const secp256k1_fe *n,
36+    const secp256k1_fe *d,
37+    const secp256k1_scalar *q,
38+    int bits,
39+    int known_on_curve
40+);
    jonasnick commented at 9:30 am on March 13, 2023:
    I think we should mention the *q == 0 edge case. Right now secp256k1_ecmult_const_xonly outputs *r == 0, which is maybe a reasonable value in that case but not an X coordinate on the curve. We can either disallow *q == 0 and VERIFY_CHECK it or document that it outputs invalid X-coordinate 0 (and also test this edge case in the regular tests). I’d prefer the former because outputting an X-coordinate that’s not on the curve seems confusing and it relies on our definition that 0^-1 = 0 (see secp256k1_fe_inv(&i, &i); in the function).
    sipa commented at 3:40 am on March 16, 2023:
    Good point, I also want to check what happens with d=0.
    sipa commented at 3:39 pm on April 7, 2023:
    Done. Made q=0 and d=0 illegal.
  56. jonasnick commented at 9:30 am on March 13, 2023: contributor
    Concept ACK. Thanks for the detailed description of the technique.
  57. sipa force-pushed on Apr 7, 2023
  58. in src/tests_exhaustive.c:199 in cc18237d29 outdated 
    198+    for (j = 0; j < EXHAUSTIVE_TEST_ORDER; j++) {
199+        for (i = 1; i < EXHAUSTIVE_TEST_ORDER; i++) {
200+            int ret;
201+            secp256k1_gej tmp;
202+            secp256k1_fe xn, xd, tmpf;
203+            secp256k1_scalar na, ng;
    jonasnick commented at 4:59 pm on April 8, 2023:
    na is unused.
    sipa commented at 7:25 pm on April 8, 2023:
    Nice catch, fixed.
  59. jonasnick commented at 5:00 pm on April 8, 2023: contributor
    ACK mod nit
  60. Add x-only ecmult_const version for x=n/d 4485926ace
  61. Add exhaustive tests for ecmult_const_xonly 0f8642079b
  62. sipa force-pushed on Apr 8, 2023
  63. jonasnick approved
  64. jonasnick commented at 8:41 pm on April 8, 2023: contributor
    ACK 0f8642079b0f2e4874393792f5854e3c33742cbd
  65. real-or-random approved
  66. real-or-random commented at 6:16 am on April 10, 2023: contributor
    ACK 0f8642079b0f2e4874393792f5854e3c33742cbd
  67. real-or-random merged this on Apr 10, 2023
  68. real-or-random closed this on Apr 10, 2023
  69. sipa referenced this in commit e1552d578e on Apr 11, 2023
  70. sipa referenced this in commit c981671e9b on Apr 14, 2023
  71. sipa cross-referenced this on Apr 20, 2023 from issue Remove secp256k1_fe_const_b by roconnor-blockstream
  72. sipa cross-referenced this on Apr 20, 2023 from issue Get rid of secp256k1_fe_const_b by sipa
  73. real-or-random referenced this in commit f6bef03c0a on Apr 21, 2023
  74. hebasto referenced this in commit 49c52ea2b1 on May 13, 2023
  75. RandyMcMillan referenced this in commit 3cc75121b3 on May 27, 2023
  76. vmta referenced this in commit e1120c94a1 on Jun 4, 2023
  77. vmta referenced this in commit 8f03457eed on Jul 1, 2023
  78. alokeutpal approved
  79. jonasnick cross-referenced this on Jul 21, 2023 from issue Upstream PRs 1228, 1236, 1243, 1238, 1246, 1247, 1242, 1250, 1244, 1241, 1257, 1226, 1252, 1118, 1245, 1266, 1269 by jonasnick
  80. jonasnick cross-referenced this on Jul 21, 2023 from issue Upstream PRs 1228, 1236, 1243, 1238, 1246, 1247, 1242, 1250, 1244, 1241, 1257, 1226, 1252, 1118, 1245, 1266, 1269 by jonasnick


sipa peterdettman real-or-random jonasnick alokeutpal

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: 2024-12-22 12:15 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me