Removes `_fe_equal_var`, and unwanted `_fe_normalize_weak` calls (in tests) #1062

pull siv2r wants to merge 2 commits into bitcoin-core:master from siv2r:doc-fe-equal-var changing 7 files +37 −57
  1. siv2r commented at 11:05 PM on January 4, 2022: contributor

    Fixes #946 and #1061

    Changes:

    • removes unwanted fe_normalize_weak calls to the second argument of fe_equal
    • removes fe_equal_var
  2. siv2r renamed this:
    update preconditions of `fe_equal_var` and remove unwanted `_fe_normalize_weak` calls
    update preconditions of `fe_equal_var` in doc and remove unwanted `_fe_normalize_weak` calls
    on Jan 4, 2022
  3. in src/field.h:68 in 77f5323d8c outdated 
      63 | @@ -64,10 +64,13 @@ static int secp256k1_fe_is_zero(const secp256k1_fe *a);
  64 |  /** Check the "oddness" of a field element. Requires the input to be normalized. */
  65 |  static int secp256k1_fe_is_odd(const secp256k1_fe *a);
  66 |  
  67 | -/** Compare two field elements. Requires magnitude-1 inputs. */
  68 | +/** Compare two field elements. Requires both the inputs to have magnitude = 1.
  69 | + *  i.e. a->magnitude = 1 and b->magnitude = 1 */
    real-or-random commented at 3:35 PM on January 5, 2022:

    Just a nit but why not just

    /** Compare two field elements. Requires both the inputs to have magnitude 1. */

    (Hm, in fact it's <= 1 even but that should go away when #1001 is solved).

    I don't think it's necessary to phrase it twice (and x->magnitude is only there #ifdef VERIFY -- but ok people would understands what is meant. ;))

    Same below.

    siv2r commented at 4:12 PM on January 5, 2022:

    Sure, I will remove this additional comment. I wanted to be more explicit, but I forgot that x->magnitude is used only in the VERIFY build.

  4. real-or-random commented at 3:35 PM on January 5, 2022: contributor

    Concept ACK

    I think then we should add (#ifdef VERIFY) magnitude checks to secp256k1_fe_equal_var and secp256k1_fe_equal.

    If you're up to it, I think the other field function could need an audit for similar checks.

  5. siv2r commented at 11:26 AM on January 13, 2022: contributor

    In fe_sqrt: https://github.com/bitcoin-core/secp256k1/blob/a1102b12196ea27f44d6201de4d25926a2ae9640/src/field_impl.h#L132-L135 Here, the secp256k1_fe_sqr function ensures that t1->magnitude = 1 but there is no guarantee for the magnitude of a to be one since it is passed into the function. Hence, some fe_sqrt tests are failing after adding magnitude checks inside fe_equal.

    We could do secp256k1_fe_normalize_weak(a) but this changes the value of a and we don't want that right? Alternatively, we could call fe_equal_var instead of fe_equal. Is it necessary for secp256k1_fe_sqrt to be of constant time?

  6. peterdettman commented at 12:01 PM on January 13, 2022: contributor

    @siv2r Regarding _fe_sqrt, there is an implicit magnitude restriction on a, since it is used as the input to _fe_mul and _fe_sqr at the top of the method. That magnitude restriction is <= 8. 8 is also a kind of global implicit limit for inputs where not otherwise stated (but we should definitely be working towards fully documenting and validating all such assumptions).

    I think it might be better to just say that both inputs to the equals methods can be magnitude <= 8 too (indeed tied to the mul/sqr limit whatever it is or changes to). There's no real obstacle to the implementation(s) (just change the third argument to _fe_negate to 8) and no performance hit AFAICT.

  7. peterdettman commented at 12:05 PM on January 13, 2022: contributor

    Is it necessary for secp256k1_fe_sqrt to be of constant time?

    It's only used in a single var-time caller, so technically it could be changed to sqrt_var, but preferably not.

  8. real-or-random commented at 12:58 PM on January 13, 2022: contributor

    Apparently secp256k1_fe_equal and secp256k1_fe_equal_var are identical up to the final call to normalizes_to_zero or normalizes_to_zero_var and so they both only require that a has magnitude 1. So we should just document that secp256k1_fe_equal only requires the magnitude of a to be 1.

    Edited because I first thought secp256k1_fe_equal and secp256k1_fe_equal_var are exactly identical.

  9. siv2r commented at 6:09 PM on January 13, 2022: contributor

    It's only used in a single var-time caller

    Oh, Okay. Then, creating a new function for secp256k1_fe_sqrt_var (while renaming the old one to _fe_sqrt_const) might be overkill.

    we should just document that secp256k1_fe_equal only requires the magnitude of a to be 1.

    Yes, I think this might be a better approach since it keeps the functionality of both fe_equal_var and fe_equal similar.

    After this, I felt we needed to remove the _fe_normalize_weak calls before _fe_equal, but surprisingly _fe_equal is used rarely in the code. The only other place where it is used is: https://github.com/bitcoin-core/secp256k1/blob/a1102b12196ea27f44d6201de4d25926a2ae9640/src/modules/extrakeys/tests_impl.h#L75-L77 Even here, the magnitude of y is two, so modifying the _fe_sqrt function (which I suggested) is a bad idea.

  10. real-or-random commented at 6:21 PM on January 13, 2022: contributor

    https://github.com/bitcoin-core/secp256k1/blob/a1102b12196ea27f44d6201de4d25926a2ae9640/src/modules/extrakeys/tests_impl.h#L75-L77

    Hehe ok, and here it's basically an oversight. This is just test code, so fe_equal_var could be used instead. I mean, not that it matters.

  11. peterdettman commented at 6:58 PM on January 13, 2022: contributor

    fe_equal_var is really a bit dubious. It only has a fast path when the inputs are not equal, and the only callers are for public key parsing and (ECDSA) verification, where that would mean an error condition and is probably uncommon. If the fast path is not hit, it actually costs a couple of cycles more. (Not to mention that the performance difference is tiny relative to those operations anyway).

  12. peterdettman commented at 7:05 PM on January 13, 2022: contributor

    While I'm on the subject, the other callers to _fe_normalizes_to_zero_var expect a false result and so will almost always hit the fast path. Depending on the level of inlining, _fe_equal_var could be "spoiling" the branch prediction for that fast path check for the other callers.

  13. siv2r force-pushed on Jan 14, 2022
  14. siv2r commented at 4:15 AM on January 14, 2022: contributor

    addressed #1062 (review) and #1062#pullrequestreview-844742940 (detailed explanation in 08186e8).

  15. siv2r commented at 4:25 AM on January 14, 2022: contributor

    I also benchmarked the tests.c file (using time ./tests) since a lot of secp256k1_fe_verify calls were added in this PR. These are the results (on 64-bit, i7-8750H) for three iterations:

    branch iter1 iter2 iter3
    master 2min 26.21sec 2min 26.44sec 2min 26.68sec
    this PR 2min 26.99sec 2min 26.91sec 2min 26.83sec
  16. siv2r renamed this:
    update preconditions of `fe_equal_var` in doc and remove unwanted `_fe_normalize_weak` calls
    document field functions assumptions and validate it using magnitude and `fe_verify` checks
    on Jan 14, 2022
  17. siv2r renamed this:
    document field functions assumptions and validate it using magnitude and `fe_verify` checks
    Document field functions assumptions and validate it using magnitude and `fe_verify` checks
    on Jan 14, 2022
  18. real-or-random commented at 5:58 PM on January 18, 2022: contributor

    @peterdettman Good points. Do you think we should remove fe_equal_var entirely and maybe document in fe_equal that this is intentional?

  19. real-or-random cross-referenced this on Jan 18, 2022 from issue call `fe_verfiy` for not normalized field element in `fe_set_b32` by siv2r
  20. peterdettman commented at 5:44 PM on January 19, 2022: contributor

    @peterdettman Good points. Do you think we should remove fe_equal_var entirely and maybe document in fe_equal that this is intentional?

    Yeah, pretty much. Until there's a performance-sensitive caller for whom a != b is the expected result, I don't see any value in _fe_equal_var. If such a caller does turn up, then there should be a fast path for inequality that doesn't even need the subtraction, so we'd rewrite it anyway.

  21. siv2r force-pushed on Jan 26, 2022
  22. siv2r commented at 7:14 PM on January 26, 2022: contributor

    addressed #1061

  23. real-or-random commented at 10:01 AM on January 27, 2022: contributor

    @siv2r Do you plan to also remove the fe_equal_var in a further commit? Or should we do this in a separate PR?

    (If you want to add it here, I think it's really ok to add it on top of the existing commits, no need to rewrite the existing commits).

  24. siv2r commented at 10:45 AM on January 27, 2022: contributor

    Okay, I will remove fe_equal_var in a new commit (this PR).

  25. siv2r commented at 11:22 PM on January 30, 2022: contributor
    • Removed fe_equal_var and documented the reason in fe_equal
    • Replaced the fe_equal_var calls with fe_equal
  26. real-or-random cross-referenced this on Feb 1, 2022 from issue Abstract out and merge all the magnitude/normalized logic by sipa
  27. in src/field.h:69 in ea1225bff5 outdated 
      63 | @@ -64,12 +64,12 @@ static int secp256k1_fe_is_zero(const secp256k1_fe *a);
  64 |  /** Check the "oddness" of a field element. Requires the input to be normalized. */
  65 |  static int secp256k1_fe_is_odd(const secp256k1_fe *a);
  66 |  
  67 | -/** Compare two field elements. Requires magnitude-1 inputs. */
  68 | +/** Compare two field elements. Requires the first input to have magnitude equal to 1. 
  69 | + *  The variable time counterpart of this function `secp256k1_fe_equal_var` was removed 
  70 | + *  since it hits fast path only when the inputs are unequal. This unequal inputs
    sipa commented at 5:43 PM on February 1, 2022:

    I think this is something you can document in the commit comment; it's weird to have it in the codebase. As in: there are many other things that aren't implemented because they're not worth it; they aren't exhaustively listed in the source code.

  28. in src/group_impl.h:244 in c6c44f4f58 outdated 
     240 | @@ -241,7 +241,7 @@ static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a)
 241 |      secp256k1_fe r, r2;
 242 |      VERIFY_CHECK(!a->infinity);
 243 |      secp256k1_fe_sqr(&r, &a->z); secp256k1_fe_mul(&r, &r, x);
 244 | -    r2 = a->x; secp256k1_fe_normalize_weak(&r2);
 245 | +    r2 = a->x;
    sipa commented at 5:45 PM on February 1, 2022:

    The r2 variable isn't needed anymore; you can just call return secp256k1_fe_equal_var(&r, &a->x); directly.

    siv2r commented at 7:25 PM on February 1, 2022:

    Nice catch, Thanks!

  29. sipa commented at 5:50 PM on February 1, 2022: contributor

    I missed the "field: add magnitude check and _fe_verify check for internal field APIs" commit being added here before writing #1066 (which duplicates some of its efforts, but also goes a lot further in a number of ways). Feel free to keep it in (and I'll rebase), but if you think #1066 covers everything you're doing here, perhaps it's easier to leave that for that PR.

  30. siv2r commented at 7:39 PM on February 1, 2022: contributor

    No worries, I will rebase this PR.

  31. real-or-random commented at 5:31 PM on May 11, 2023: contributor

    No worries, I will rebase this PR.

    Ok, merging #1066 took a while.... This PR here needs rebase now. :)

  32. real-or-random added the label assurance on May 11, 2023
  33. real-or-random added the label documentation on May 11, 2023
  34. siv2r force-pushed on Aug 15, 2023
  35. siv2r commented at 12:14 PM on August 15, 2023: contributor

    Rebased.

    #1066 took care of all the magnitude and fe_verify checks so, this PR currently does:

    • removes unwanted fe_normalize_weak calls to the second argument of fe_equal
    • removes fe_equal_var
  36. in src/tests.c:2994 in 79abdf0a50 outdated 
    2966 | @@ -2967,7 +2967,6 @@ static int check_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b) {
2967 |      secp256k1_fe an = *a;
2968 |      secp256k1_fe bn = *b;
2969 |      secp256k1_fe_normalize_weak(&an);
2970 | -    secp256k1_fe_normalize_var(&bn);
    siv2r commented at 12:23 PM on August 15, 2023:

    Not sure why normalize_var was used on bn. I assumed it intended to set bn's magnitude to 1 for the fe_equal call. So, I removed it. Please let me know if that's not the case, and I'll revert this.

    All test cases passed with this change.

  37. real-or-random commented at 3:01 PM on August 15, 2023: contributor

    Nice. :)

    #1066 took care of all the magnitude and fe_verify checks so, this PR currently does:

    Can you update the PR title and the initial comment, so that they reflect the current status?

  38. real-or-random removed the label documentation on Aug 15, 2023
  39. real-or-random removed the label assurance on Aug 15, 2023
  40. real-or-random added the label refactor/smell on Aug 15, 2023
  41. siv2r renamed this:
    Document field functions assumptions and validate it using magnitude and `fe_verify` checks
    Removes `_fe_equal_var`, and unwanted `_fe_normalize_weak` calls (in tests)
    on Aug 15, 2023
  42. real-or-random commented at 11:54 AM on August 16, 2023: contributor

    Needs rebase again, sorry, but should be trivial. :)

    Thanks for updating the PR title. Can you also update the initial post/PR description (e.g., replace the contents with #1062 (comment) )? It's just cosmetic, but the text of will be added to the merge commit, so it makes sense to keep this updated.

  43. tests: remove unwanted `secp256k1_fe_normalize_weak` call
    It is not neccessary for the second argument in `secp256k1_fe_equal_var`
(or `secp256k1_fe_equal`) to have magnitude = 1.
Hence, removed the `secp256k1_fe_normalize_weak` call for those argument.
    bb4efd6404
  44. field: remove `secp256k1_fe_equal_var`
    `fe_equal_var` hits a fast path only when the inputs are unequal, which is
uncommon among its callers (public key parsing, ECDSA verify).
    54058d16fe
  45. siv2r force-pushed on Aug 16, 2023
  46. siv2r commented at 12:11 PM on August 16, 2023: contributor

    Rebased and updated the description. I forgot about the merge commit including the description too. Thanks!

  47. real-or-random approved
  48. real-or-random commented at 12:13 PM on August 16, 2023: contributor

    utACK 54058d16feaa431520029335e2d56252859d3260

  49. jonasnick commented at 3:05 PM on August 17, 2023: contributor

    Until there's a performance-sensitive caller for whom a != b is the expected result, I don't see any value in _fe_equal_var.

    I don't think we know what the expected result of the caller is. The difference seems to be negligible though.

    ACK 54058d16feaa431520029335e2d56252859d3260

  50. real-or-random merged this on Aug 17, 2023
  51. real-or-random closed this on Aug 17, 2023
  52. fanquake referenced this in commit a2cadecc45 on Aug 21, 2023
  53. fanquake cross-referenced this on Aug 21, 2023 from issue libsecp256k1: remove secp256k1_fe_equal_var by fanquake
  54. sipa referenced this in commit c0da4f60e2 on Sep 4, 2023
  55. jonasnick cross-referenced this on Sep 19, 2023 from issue Upstream PRs 1391, 1290, 1389, 1397, 1399, 1400, 1348, 1402, 1274, 1394, 1404, 1062, 1401, 1373, 1403, 1398, 1405, 1396, 1406, 1410, 1409, 1411, 1412, 1414, 1413, 1415, 1417, 1390, 1416, 1422, 1424, 1395 by jonasnick
  56. Retropex referenced this in commit 5f62ed90f6 on Oct 4, 2023
  57. real-or-random referenced this in commit d575ef9aca on Oct 12, 2023
  58. siv2r deleted the branch on Mar 5, 2024
Contributors
siv2rreal-or-randompeterdettmansipajonasnick
Labels
refactor/smell
Linked (view graph)
#946 Preconditions of fe_equal_var are weaker than documented#1001 Make fe magnitude implied statically#1061 call `fe_verfiy` for not normalized field element in `fe_set_b32`#1066 Abstract out and merge all the magnitude/normalized logic
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-04-22 22:15 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me